python - levenshtein distance javascript

¿Cómo puedo optimizar este código de Python para generar todas las palabras con la palabra distancia 1?

Question

La creación de perfiles muestra que este es el segmento más lento de mi código para un pequeño juego de palabras que escribí:

def distance(word1, word2):
    difference = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            difference += 1
    return difference

def getchildren(word, wordlist):
    return [ w for w in wordlist if distance(word, w) == 1 ]

Notas:

• distance() se llama más de 5 millones de veces, la mayoría de los cuales provienen de getchildren, que se supone que tiene todas las palabras en la lista de palabras que difieren de la word por exactamente 1 letra.
• la lista de palabras está filtrada previamente para que solo tenga palabras que contengan el mismo número de letras que la word por lo que se garantiza que la word1 y la word2 tengan el mismo número de caracteres.
• Soy bastante nuevo en Python (lo comencé a aprender hace 3 días) así que los comentarios sobre convenciones de nombres u otras cosas de estilo también son apreciados.
• para la lista de palabras, tome la lista de palabras de 12 decidos usando el archivo "2 + 2lemma.txt"

Resultados:

Gracias a todos, con combinaciones de diferentes sugerencias conseguí que el programa funcionara el doble de rápido ahora (además de las optimizaciones que hice antes de preguntar, por lo que 4 veces la velocidad aumenta aproximadamente desde mi implementación inicial)

Probé con 2 juegos de entradas que llamaré A y B

Optimization1: iterar sobre los índices de word1,2 ... de

for i in range(len(word1)):
        if word1[i] != word2[i]:
            difference += 1
    return difference

para iterar en pares de letras usando zip(word1, word2)

for x,y in zip (word1, word2):
        if x != y:
            difference += 1
    return difference

Tiempo de ejecución de 11.92 a 9.18 para la entrada A y de 79.30 a 74.59 para la entrada B

Optimización2: se agregó un método separado para diferir-por-uno además del método de distancia (que todavía necesitaba en otro lugar para la heurística A *)

def is_neighbors(word1,word2):
    different = False
    for c1,c2 in zip(word1,word2):
        if c1 != c2:
            if different:
                return False
            different = True
    return different

Se obtuvo un tiempo de ejecución de 9.18 a 8.83 para la entrada A, y de 74.59 a 70.14 para la entrada B

Optimization3: el gran ganador aquí fue utilizar izip lugar de zip

Obtuve tiempo de ejecución de 8.83 a 5.02 para la entrada A, y de 70.14 a 41.69 para la entrada B

Probablemente podría escribir mejor en un lenguaje de nivel inferior, pero estoy contento con esto por ahora. ¡Gracias a todos!

Editar de nuevo: más resultados Usar el método de Mark para verificar el caso en el que la primera letra no coincide bajó de 5.02 -> 3.59 y 41.69 -> 29.82

Sobre la base de eso y la incorporación de izip lugar de range , terminé con esto:

def is_neighbors(word1,word2):
    if word1[0] != word2[0]:
        return word1[1:] == word2[1:]
    different = False
    for x,y in izip(word1[1:],word2[1:]):
        if x != y:
            if different:
                return False
            different = True
    return different

Lo cual exprimió un poco más, bajando los tiempos de 3.59 -> 3.38 y 29.82 -> 27.88

¡Aún más resultados!

Al intentar la sugerencia de Sumudu de generar una lista de todas las cadenas que tienen 1 letra de "palabra" y luego verificar para ver cuáles estaban en la lista de palabras , en lugar de la función is_neighbor terminé con esto:

def one_letter_off_strings(word):
    import string
    dif_list = []
    for i in xrange(len(word)):
        dif_list.extend((word[:i] + l + word[i+1:] for l in string.ascii_lowercase if l != word[i]))
    return dif_list

def getchildren(word, wordlist):
    oneoff = one_letter_off_strings(word)
    return ( w for w in oneoff if w in wordlist )

Que terminó siendo más lento (3.38 -> 3.74 y 27.88 -> 34.40) pero parecía prometedor. Al principio pensé que la parte que necesitaría optimizar era "one_letter_off_strings", pero los perfiles mostraban lo contrario y que la parte lenta era de hecho

( w for w in oneoff if w in wordlist )

Pensé que si hubiera alguna diferencia si cambiaba "oneoff" y "wordlist" e hice la comparación al otro lado cuando me di cuenta de que estaba buscando la intersección de las 2 listas. Sustituyo eso con set-intersection en las letras :

return set(oneoff) & set(wordlist)

Bam! 3.74 -> 0.23 y 34.40 -> 2.25

Esto es realmente sorprendente, la diferencia de velocidad total de mi implementación ingenua original: 23.79 -> 0.23 y 180.07 -> 2.25, por lo que aproximadamente 80 a 100 veces más rápido que la implementación original.

Si alguien está interesado, hice una publicación de blog describiendo el programa y describiendo las optimizaciones realizadas, incluida una que no se menciona aquí (porque está en una sección de código diferente).

El gran debate

Ok, yo y Desconocido estamos teniendo un gran debate que puedes leer en los comentarios de su respuesta . Afirma que sería más rápido usar el método original (utilizando is_neighbor en lugar de usar los sets) si fue portado a C. Intenté durante 2 horas obtener un módulo C que escribí para compilarlo y poder vincularlo sin mucho éxito luego de intentar sigue this y this ejemplo, y parece que el proceso es un poco diferente en Windows? No lo sé, pero renuncié a eso. De todos modos, aquí está el código completo del programa, y ​​el archivo de texto proviene de la lista de palabras 12dict usando el archivo "2 + 2lemma.txt". Lo siento si el código es un poco desordenado, esto fue algo que pirateé juntos. También me olvidé de quitar las comas de la lista de palabras, así que en realidad es un error que puedes dejar por la misma comparación o solucionarlo agregando una coma a la lista de caracteres en los artículos.

from itertools import izip
def unique(seq):  
    seen = {} 
    result = [] 
    for item in seq: 
        if item in seen:
            continue 
        seen[item] = 1 
        result.append(item) 
    return result
def cleanentries(li):
    pass
    return unique( [w.strip(''[]'') for w in li if w != "->"] )
def distance(word1, word2):
    difference = 0
    for x,y in izip (word1, word2):
        if x != y:
            difference += 1
    return difference
def is_neighbors(word1,word2):
    if word1[0] != word2[0]:
        return word1[1:] == word2[1:]
    different = False
    for x,y in izip(word1[1:],word2[1:]):
        if x != y:
            if different:
                return False
            different = True
    return different
def one_letter_off_strings(word):
    import string
    dif_list = []
    for i in xrange(len(word)):
        dif_list.extend((word[:i] + l + word[i+1:] for l in string.ascii_lowercase if l != word[i]))
    return dif_list

def getchildren(word, wordlist):
    oneoff = one_letter_off_strings(word)
    return set(oneoff) & set(wordlist)
def AStar(start, goal, wordlist):
    import Queue
    closedset = []
    openset = [start]
    pqueue = Queue.PriorityQueue(0)
    g_score = {start:0}         #Distance from start along optimal path.
    h_score = {start:distance(start, goal)}
    f_score = {start:h_score[start]}
    pqueue.put((f_score[start], start))
    parent_dict = {}
    while len(openset) > 0:
        x = pqueue.get(False)[1]
        if x == goal:
            return reconstruct_path(parent_dict,goal)
        openset.remove(x)
        closedset.append(x)
        sortedOpen = [(f_score[w], w, g_score[w], h_score[w]) for w in openset]
        sortedOpen.sort()
        for y in getchildren(x, wordlist):
            if y in closedset:
                continue
            temp_g_score = g_score[x] + 1
            temp_is_better = False
            appended = False
            if (not y in openset): 
                openset.append(y)
                appended = True
                h_score[y] = distance(y, goal)
                temp_is_better = True
            elif temp_g_score < g_score[y] :
                temp_is_better = True
            else :
                pass
            if temp_is_better:
                parent_dict[y] = x
                g_score[y] = temp_g_score
                f_score[y] = g_score[y] + h_score[y]
                if appended :
                    pqueue.put((f_score[y], y))
    return None


def reconstruct_path(parent_dict,node):
     if node in parent_dict.keys():
         p = reconstruct_path(parent_dict,parent_dict[node])
         p.append(node)
         return p
     else:
         return []        

wordfile = open("2+2lemma.txt")
wordlist = cleanentries(wordfile.read().split())
wordfile.close()
words = []
while True:
    userentry = raw_input("Hello, enter the 2 words to play with separated by a space:/n ")
    words = [w.lower() for w in userentry.split()]
    if(len(words) == 2 and len(words[0]) == len(words[1])):
        break
print "You selected %s and %s as your words" % (words[0], words[1])
wordlist = [ w for w in wordlist if len(words[0]) == len(w)]
answer = AStar(words[0], words[1], wordlist)
if answer != None:
    print "Minimum number of steps is %s" % (len(answer))
    reply = raw_input("Would you like the answer(y/n)? ")
    if(reply.lower() == "y"):
        answer.insert(0, words[0])
        print "/n".join(answer)
    else:
        print "Good luck!"
else:
    print "Sorry, there''s no answer to yours"
reply = raw_input("Press enter to exit")

Dejé el método is_neighbors aunque no se use. Este es el método que se propone portar a C. Para usarlo, simplemente reemplace getchildren con esto:

def getchildren(word, wordlist):
    return ( w for w in wordlist if is_neighbors(word, w))

En cuanto a hacer que funcione como un módulo C, no llegué tan lejos, pero esto es lo que se me ocurrió:

#include "Python.h"

static PyObject *
py_is_neighbor(PyObject *self, Pyobject *args)
{
    int length;
    const char *word1, *word2;
    if (!PyArg_ParseTuple(args, "ss", &word1, &word2, &length))
        return NULL;

    int i;
    int different = 0;
    for (i =0; i < length; i++)
    {
        if (*(word1 + i) != *(word2 + i))
        {
            if (different)
            {
                return Py_BuildValue("i", different);
            }
            different = 1;
        }
    }
    return Py_BuildValue("i", different);
}

PyMethodDef methods[] = {
    {"isneighbor", py_is_neighbor, METH_VARARGS, "Returns whether words are neighbors"},
    {NULL, NULL, 0, NULL}
};

PyMODINIT_FUNC
initIsNeighbor(void)
{
    Py_InitModule("isneighbor", methods);
}

Yo perfilé esto usando:

python -m cProfile "Wordgame.py"

Y el tiempo registrado fue el tiempo total de la llamada al método AStar. El conjunto de entrada rápida era "poetas de verso" y el conjunto de entrada largo era "verso de poetas". Los tiempos variarán obviamente entre las diferentes máquinas, por lo que si alguien termina intentando esto, dé una comparación de resultados del programa tal como está, así como también con el módulo C.

Answer 1

¿Con qué frecuencia se llama a la función de distancia con los mismos argumentos? Una optimización fácil de implementar sería usar memoization .

Probablemente también puedas crear algún tipo de diccionario con conjuntos congelados de letras y listas de palabras que difieran en uno y buscar valores en eso. Esta estructura de datos podría almacenarse y cargarse mediante pickle o generarse desde cero al inicio.

Cortocircuitar la evaluación solo le dará ganancias si las palabras que está utilizando son muy largas, ya que el algoritmo de distancia de hamming que está utilizando es básicamente O (n) donde n es la longitud de la palabra.

Hice algunos experimentos con timeit para algunos enfoques alternativos que pueden ser ilustrativos.

Resultados de Timeit

Tu solución

d = """/
def distance(word1, word2):
    difference = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            difference += 1
    return difference
"""
t1 = timeit.Timer(''distance("hello", "belko")'', d)
print t1.timeit() # prints 6.502113536776391

Un trazador de líneas

d = """/
from itertools import izip
def hamdist(s1, s2):
    return sum(ch1 != ch2 for ch1, ch2 in izip(s1,s2))
"""
t2 = timeit.Timer(''hamdist("hello", "belko")'', d)
print t2.timeit() # prints 10.985101179

Evaluación de acceso directo

d = """/
def distance_is_one(word1, word2):
    diff = 0
    for i in xrange(len(word1)):
        if word1[i] != word2[i]:
            diff += 1
        if diff > 1:
            return False
    return diff == 1
"""
t3 = timeit.Timer(''hamdist("hello", "belko")'', d)
print t2.timeit() # prints 6.63337

Answer 2

Bueno, puedes comenzar rompiendo tu loop si la diferencia es 2 o más.

También puedes cambiar

for i in range(len(word1)):

a

for i in xrange(len(word1)):

Porque xrange genera secuencias bajo demanda en lugar de generar todo el rango de números a la vez.

También puede intentar comparar longitudes de palabra que serían más rápidas. También tenga en cuenta que su código no funciona si word1 es mayor que word2

No hay mucho más que pueda hacer algorítmicamente después de eso, lo que quiere decir que probablemente encontrará más aceleración al portar esa sección a C.

Editar 2

Intento explicar mi análisis del algoritmo de Sumudu en comparación con la verificación de las diferencias char por char.

Cuando tiene una palabra de longitud L, el número de palabras "diferentes por uno" que generará será de 25L. Sabemos por implementaciones de conjuntos en computadoras modernas, que la velocidad de búsqueda es aproximadamente log (n) base 2 , donde n es el número de elementos que se deben buscar.

Al ver que la mayoría de los 5 millones de palabras con las que prueba no están en el conjunto, la mayoría de las veces atravesará todo el conjunto, lo que significa que realmente se convierte en log (25L) en lugar de solo log (25L) / 2. (y esto es asumiendo el mejor escenario para conjuntos que comparar cadena por cadena es equivalente a comparar char por char)

Ahora echamos un vistazo a la complejidad del tiempo para determinar un "difiere por uno". Si suponemos que debe verificar la palabra completa, entonces el número de operaciones por palabra se convierte en L. Sabemos que la mayoría de las palabras difieren en 2 muy rápidamente. Y sabiendo que la mayoría de los prefijos ocupan una pequeña porción de la palabra, podemos suponer lógicamente que dividirá la mayor parte del tiempo en L / 2 , o la mitad de la palabra (y esta es una estimación conservadora).

Así que ahora trazamos las complejidades de tiempo de las dos búsquedas, L / 2 y log (25L), y teniendo en cuenta que esto incluso considera que la cadena coincide con la misma velocidad que la coincidencia de caracteres (muy a favor de los conjuntos). Tiene el registro de ecuaciones (25 * L)> L / 2, que se puede simplificar hasta log (25)> L / 2 - log (L). Como puede ver en el gráfico, debería ser más rápido usar el algoritmo de coincidencia de caracteres hasta llegar a números muy grandes de L.

Además, no sé si estás contando rompiendo la diferencia de 2 o más en tu optimización, pero de la respuesta de Mark ya rompo una diferencia de 2 o más, y en realidad, si la diferencia en la primera letra, se rompe después de la primera letra, e incluso a pesar de todas esas optimizaciones, cambiar a usar sets simplemente los saca del agua. Aunque estoy interesado en probar tu idea

Fui la primera persona en esta pregunta que sugirió romper una diferencia de 2 o más. La cuestión es que la idea de Mark de cortar cuerdas (si word1 [0]! = Word2 [0]: return word1 [1:] == word2 [1:]) es simplemente poner lo que estamos haciendo en C. ¿Cómo lo haces? ¿crees que se calcula word1 [1:] == word2 [1:] ? De la misma manera que lo estamos haciendo.

Leí tu explicación algunas veces, pero no la seguí, ¿te importaría explicarla un poco más? Además, no estoy muy familiarizado con C y he estado trabajando en lenguajes de alto nivel durante los últimos años (lo más parecido ha sido aprender C ++ en la escuela secundaria hace 6 años).

En cuanto a producir el código C, estoy un poco ocupado. Estoy seguro de que podrá hacerlo ya que ha escrito en C anteriormente. También podría probar C #, que probablemente tenga características de rendimiento similares.

Más Explicación

Aquí hay una explicación más profunda para Davy8

def getchildren(word, wordlist):
    oneoff = one_letter_off_strings(word)
    return set(oneoff) & set(wordlist)

Su función one_letter_off_strings creará un conjunto de cadenas de 25L (donde L es el número de letras).

La creación de un conjunto a partir de la lista de palabras creará un conjunto de cadenas D (donde D es la longitud de su diccionario). Al crear una intersección a partir de esto, DEBES iterar sobre cada uno de los offoffs y ver si existe en la lista de palabras .

La complejidad de tiempo para esta operación se detalla más arriba. Esta operación es menos eficiente que la comparación de la palabra que desea con cada palabra en la lista de palabras . El método de Sumudu es una optimización en C en lugar de en algoritmo.

Más Explicación 2

Solo hay 4500 palabras en total (porque la lista de palabras está filtrada previamente para palabras de 5 letras antes de pasarla al algoritmo), y se cruza con 125 palabras de una sola letra. Parecía que estaba diciendo que la intersección es log (más pequeña) o en otras palabras, log (125, 2). Compara esto para asumir nuevamente lo que dijiste, cuando comparando una palabra se rompe en letras L / 2, redondearé esto a 2, aunque para una palabra de 5 letras es más probable que sea 3. Esta comparación se hace 4500 veces, entonces 9000. log (125,2) es aproximadamente 6.9, y log (4500,2) es aproximadamente 12. Déjenme saber si malinterpreté sus números.

Para crear la intersección de 125 palabras de una sola letra con un diccionario de 4500, debe hacer comparaciones de 125 * 4500. Esto no es log (125,2). En el mejor de los casos, 125 * log (4500, 2), suponiendo que el diccionario esté ordenado previamente. No hay un atajo mágico para los conjuntos. También está haciendo una cadena por cadena en lugar de char por comparación aquí.

Answer 3

La distance su función es calcular la distancia total, cuando realmente solo le importa la distancia = 1. En la mayoría de los casos sabrá que es> 1 dentro de unos pocos caracteres, por lo que puede volver temprano y ahorrar mucho tiempo.

Más allá de eso, podría haber un algoritmo mejor, pero no puedo pensar en eso.

Editar: Otra idea.

Puedes hacer 2 casos, dependiendo de si el primer personaje coincide. Si no coincide, el resto de la palabra tiene que coincidir exactamente, y puedes probar eso en una sola toma. De lo contrario, hazlo de manera similar a lo que estabas haciendo. Incluso podrías hacerlo recursivamente, pero no creo que sea más rápido.

def DifferentByOne(word1, word2):
    if word1[0] != word2[0]:
        return word1[1:] == word2[1:]
    same = True
    for i in range(1, len(word1)):
        if word1[i] != word2[i]:
            if same:
                same = False
            else:
                return False
    return not same

Editar 2: he eliminado el cheque para ver si las cadenas tienen la misma longitud, ya que dices que es redundante. Al ejecutar las pruebas de Ryan en mi propio código y en la función is_neighbors proporcionada por MizardX , obtengo lo siguiente:

• Distancia original (): 3.7 segundos
• My DifferentByOne (): 1.1 segundos
• Is_neighbors de MizardX (): 3.7 segundos

Editar 3: (Probablemente ingresar al territorio wiki de la comunidad aquí, pero ...)

Intentando tu definición final de is_neighbors () con izip en lugar de zip: 2.9 segundos.

Aquí está mi última versión, que todavía está en 1.1 segundos:

def DifferentByOne(word1, word2):
    if word1[0] != word2[0]:
        return word1[1:] == word2[1:]
    different = False
    for i in range(1, len(word1)):
        if word1[i] != word2[i]:
            if different:
                return False
            different = True
    return different

Answer 4

La gente está haciendo esto principalmente tratando de escribir una función más rápida, pero podría haber otra manera ...

"distancia" se llama más de 5 millones de veces

¿Por qué es esto? Tal vez una forma mejor de optimizar es tratar de reducir el número de llamadas a distance , en lugar de afeitar milisegundos del tiempo de ejecución de la distance''s . Es imposible saber sin ver el guión completo, pero la optimización de una función específica generalmente no es necesaria.

Si eso es imposible, ¿quizás podrías escribirlo como un módulo C?

Answer 5

Lo primero que se me ocurre:

from operator import ne

def distance(word1, word2):
    return sum(map(ne, word1, word2))

que tiene una posibilidad decente de ir más rápido que otras funciones que la gente ha publicado, porque no tiene bucles interpretados, solo llamadas a primitivas de Python. Y es lo suficientemente corto como para que pueda alinearlo razonablemente con la persona que llama.

Para su problema de nivel superior, examinaría las estructuras de datos desarrolladas para la búsqueda de similitud en espacios métricos, por ejemplo, este documento o este , ninguno de los cuales he leído (aparecieron en una búsqueda de un documento que leí). pero no puedo recordar).

Answer 6

No sé si afectará significativamente su velocidad, pero podría comenzar convirtiendo la comprensión de la lista en una expresión de generador. Todavía es iterable por lo que no debería ser muy diferente en el uso:

def getchildren(word, wordlist):
    return [ w for w in wordlist if distance(word, w) == 1 ]

a

def getchildren(word, wordlist):
    return ( w for w in wordlist if distance(word, w) == 1 )

El principal problema sería que una lista de comprensión se construiría en la memoria y ocuparía bastante espacio, mientras que el generador creará su lista sobre la marcha para que no haya necesidad de almacenar todo.

Además, siguiendo la respuesta de unknown, esta puede ser una forma más "pitonica" de escribir la distancia ():

def distance(word1, word2):
    difference = 0
    for x,y in zip (word1, word2):
        if x == y:
            difference += 1
    return difference

Pero es confuso lo que se pretende cuando len (word1)! = Len (word2), en el caso de zip solo devolverá tantos caracteres como la palabra más corta. (Que podría ser una optimización ...)

Answer 7

Para una función tan simple que tiene una implicación de rendimiento tan grande, probablemente crearía una biblioteca C y la llamaría usando ctypes . Uno de los fundadores de reddit afirma que creó el sitio web 2 veces más rápido con esta técnica.

También puede usar psyco en esta función, pero tenga en cuenta que puede consumir mucha memoria.

Answer 8

Prueba esto:

def distance(word1, word2):
  return sum([not c1 == c2 for c1, c2 in zip(word1,word2)])

Además, ¿tienes un enlace a tu juego? Me gusta ser destruido por los juegos de palabras

Answer 9

Si su lista de palabras es muy larga, ¿podría ser más eficiente generar todas las posibles diferencias de 1 letra de ''palabra'', y luego verificar cuáles están en la lista? No conozco ningún Python, pero debería haber una estructura de datos adecuada para la lista de palabras que permita búsquedas en tiempo de registro.

Sugiero esto porque si tus palabras son longitudes razonables (~ 10 letras), entonces solo estarás buscando 250 palabras potenciales, que probablemente sean más rápidas si tu lista de palabras es más grande que unos pocos cientos de palabras.

Answer 10

Todos los demás se centraron solo en cálculos explícitos de distancias sin hacer nada para construir los candidatos de distancia 1. Puede mejorar utilizando una estructura de datos conocida llamada Trie para fusionar el cálculo de distancia implícito con la tarea de generar todas las palabras vecinas de distancia 1 . A Trie es una lista enlazada donde cada nodo representa una letra, y el campo ''siguiente'' es un dict con hasta 26 entradas, apuntando al siguiente nodo.

Aquí está el pseudocódigo: recorre el Trie iterativamente por tu palabra dada; en cada nodo, agregue todos los vecinos de distancia 0 y distancia 1 a los resultados; mantener un contador de distancia y disminuirlo. No necesita recursión, solo una función de búsqueda que toma un argumento extra distance_so_far integer.

Se puede obtener un intercambio menor de velocidad extra por O (N) aumento de espacio mediante la creación de pruebas independientes para longitud-3, longitud-4, longitud-5, etc.

Answer 11

para este fragmento:

for x,y in zip (word1, word2):
    if x != y:
        difference += 1
return difference

Yo usaría este:

return sum(1 for i in xrange(len(word1)) if word1[i] == word2[i])

el mismo patrón seguiría todo el código provisto ...

Answer 12

from itertools import izip

def is_neighbors(word1,word2):
    different = False
    for c1,c2 in izip(word1,word2):
        if c1 != c2:
            if different:
                return False
            different = True
    return different

O tal vez alineando el código de izip :

def is_neighbors(word1,word2):
    different = False
    next1 = iter(word1).next
    next2 = iter(word2).next
    try:
        while 1:
            if next1() != next2():
                if different:
                    return False
                different = True
    except StopIteration:
        pass
    return different

Y un getchildren reescrito:

def iterchildren(word, wordlist):
    return ( w for w in wordlist if is_neighbors(word, w) )

• izip(a,b) devuelve un iterador sobre pares de valores de b .
• zip(a,b) devuelve una lista de pares de b .