python - levenshtein - Construye eficientemente un gráfico de palabras con la distancia de Hamming dada

damerau levenshtein distancia

Question

Quiero construir un gráfico a partir de una lista de palabras con la distancia de Hamming de (digamos) 1, o para ponerlo de manera diferente, dos palabras están conectadas si solo difieren de una letra ( lo l -> lo t ).

por lo que dado

words = [ lol, lot, bot ]

la gráfica sería

{
  ''lol'' : [ ''lot'' ],
  ''lot'' : [ ''lol'', ''bot'' ],
  ''bot'' : [ ''lot'' ]
}

La forma más fácil es comparar cada palabra de la lista con las demás y contar los diferentes caracteres; Lamentablemente, este es un algoritmo O(N^2) .

¿Qué estrategias / ds / estrategia puedo usar para lograr un mejor rendimiento?

Además, asumamos solo caracteres latinos, y todas las palabras tienen la misma longitud.

Answer 1

Aquí está el algoritmo O (N) lineal, pero con un factor constante grande (R * L * 2). R es radix (para el alfabeto latino es 26). L es una longitud media de la palabra. 2 es un factor para agregar / reemplazar caracteres comodín. Así que abc y aac y abca son dos operaciones que llevan a una distancia de hamming de 1.

Está escrito en ruby. Y para 240k palabras se necesitan ~ 250Mb de RAM y 136 segundos en hardware promedio

Plan de implementación de la gráfica.

class Node
  attr_reader :val, :edges

  def initialize(val)
    @val = val
    @edges = {}
  end

  def <<(node)
    @edges[node.val] ||= true
  end

  def connected?(node)
    @edges[node.val]
  end

  def inspect
    "Val: #{@val}, edges: #{@edges.keys * '', ''}"
  end
end

class Graph
  attr_reader :vertices
  def initialize
    @vertices = {}
  end

  def <<(val)
    @vertices[val] = Node.new(val)
  end

  def connect(node1, node2)
    # print "connecting #{size} #{node1.val}, #{node2.val}/r"
    node1 << node2
    node2 << node1
  end

  def each
    @vertices.each do |val, node|
      yield [val, node]
    end
  end

  def get(val)
    @vertices[val]
  end
end

El algoritmo en sí.

CHARACTERS = (''a''..''z'').to_a
graph = Graph.new

# ~ 240 000 words
File.read("/usr/share/dict/words").each_line.each do |word|
  word = word.chomp
  graph << word.downcase
end

graph.each do |val, node|
  CHARACTERS.each do |char|
    i = 0
    while i <= val.size
      node2 = graph.get(val[0, i] + char + val[i..-1])
      graph.connect(node, node2) if node2
      if i < val.size
        node2 = graph.get(val[0, i] + char + val[i+1..-1])
        graph.connect(node, node2) if node2
      end
      i += 1
    end
  end
end

Answer 2

No hay necesidad de depender del tamaño del alfabeto. Dada una palabra bot , por ejemplo, insértela en un diccionario de listas de palabras debajo de las teclas ?ot, b?t, bo? . Luego, para cada lista de palabras, conecta todos los pares.

import collections


d = collections.defaultdict(list)
with open(''/usr/share/dict/words'') as f:
    for line in f:
        for word in line.split():
            if len(word) == 6:
                for i in range(len(word)):
                    d[word[:i] + '' '' + word[i + 1:]].append(word)
pairs = [(word1, word2) for s in d.values() for word1 in s for word2 in s if word1 < word2]
print(len(pairs))

Answer 3

Suponiendo que almacene su diccionario en un set() , de modo que la búsqueda sea O (1) en el promedio (caso más desfavorable O (n) ) .

Puede generar todas las palabras válidas a una distancia de hamming 1 a partir de una palabra:

>>> def neighbours(word):
...     for j in range(len(word)):
...         for d in string.ascii_lowercase:
...             word1 = ''''.join(d if i==j else c for i,c in enumerate(word))
...             if word1 != word and word1 in words: yield word1
...
>>> {word: list(neighbours(word)) for word in words}
{''bot'': [''lot''], ''lol'': [''lot''], ''lot'': [''bot'', ''lol'']}

Si M es la longitud de una palabra, L la longitud del alfabeto (es decir, 26), la complejidad en el peor de los casos para encontrar palabras vecinas con este enfoque es O (L * M * N) .

La complejidad temporal del enfoque de "manera fácil" es O (N ^ 2) .

Cuando este enfoque es mejor? Cuando L*M < N , es decir, si solo se consideran letras minúsculas, cuando M < N/26 . (Consideré el peor de los casos aquí)

Nota: la longitud promedio de una palabra en inglés es de 5,1 letras . Por lo tanto, debe considerar este enfoque si el tamaño de su diccionario es más grande que 132 palabras.

Probablemente es posible lograr un mejor rendimiento que esto. Sin embargo, esto fue realmente fácil de implementar.

Punto de referencia experimental:

El algoritmo de "manera fácil" ( A1 ):

from itertools import zip_longest
def hammingdist(w1,w2): return sum(1 if c1!=c2 else 0 for c1,c2 in zip_longest(w1,w2))
def graph1(words): return {word: [n for n in words if hammingdist(word,n) == 1] for word in words}

Este algoritmo ( A2 ):

def graph2(words): return {word: list(neighbours(word)) for word in words}

Código de referencia:

for dict_size in range(100,6000,100):
    words = set([''''.join(random.choice(string.ascii_lowercase) for x in range(3)) for _ in range(dict_size)])
    t1 = Timer(lambda: graph1()).timeit(10)
    t2 = Timer(lambda: graph2()).timeit(10)
    print(''%d,%f,%f'' % (dict_size,t1,t2))

Salida:

100,0.119276,0.136940
200,0.459325,0.233766
300,0.958735,0.325848
400,1.706914,0.446965
500,2.744136,0.545569
600,3.748029,0.682245
700,5.443656,0.773449
800,6.773326,0.874296
900,8.535195,0.996929
1000,10.445875,1.126241
1100,12.510936,1.179570
...

Corrí otro punto de referencia con pasos más pequeños de N para verlo más de cerca:

10,0.002243,0.026343
20,0.010982,0.070572
30,0.023949,0.073169
40,0.035697,0.090908
50,0.057658,0.114725
60,0.079863,0.135462
70,0.107428,0.159410
80,0.142211,0.176512
90,0.182526,0.210243
100,0.217721,0.218544
110,0.268710,0.256711
120,0.334201,0.268040
130,0.383052,0.291999
140,0.427078,0.312975
150,0.501833,0.338531
160,0.637434,0.355136
170,0.635296,0.369626
180,0.698631,0.400146
190,0.904568,0.444710
200,1.024610,0.486549
210,1.008412,0.459280
220,1.056356,0.501408
...

Verá que la compensación es muy baja (100 para los diccionarios de palabras con longitud = 3). Para diccionarios pequeños, el algoritmo O (N ^ 2) tiene un rendimiento ligeramente mejor, pero el algoritmo O (LMN) lo supera fácilmente a medida que N crece.

Para diccionarios con palabras más largas, el algoritmo O (LMN) permanece lineal en N, solo tiene una pendiente diferente, por lo que la compensación se mueve ligeramente hacia la derecha (130 para longitud = 5).

Answer 4

Ternary Search Trie soporta la búsqueda de vecinos cercanos bastante bien.

Si su diccionario se almacena como TST, entonces, creo que la complejidad promedio de las búsquedas mientras construye su gráfica sería cercana a O(N*log(N)) en los diccionarios de palabras del mundo real.

Y marque Efficient auto-complete con un artículo del árbol de búsqueda ternario .