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 .