¿Una forma eficiente de calcular las puntuaciones de similitud de las cadenas cuando el tamaño de la muestra es grande?

Question

Supongamos que tiene una lista de 10,000 direcciones de correo electrónico y le gustaría encontrar algunos de los más cercanos " vecinos " en esta lista se definen como direcciones de correo electrónico que están sospechosamente cerca de otras direcciones de correo electrónico en su lista.

Soy consciente de cómo calcular la distancia Levenshtein entre dos cadenas (gracias a esta pregunta ), que me dará una puntuación de cuántas operaciones son necesarias para transformar una cadena en otra.

Digamos que defino " sospechosamente cerca de otra dirección de correo electrónico " como dos cuerdas que tienen una puntuación Levenshtein menor que N.

¿Existe una forma más eficiente de encontrar pares de cadenas cuyo puntaje sea inferior a este umbral, además de comparar todas las cadenas posibles con todas las demás cadenas posibles en la lista? En otras palabras, ¿este tipo de problema se puede resolver más rápido que O (n ^ 2) ?

¿Levenshtein tiene una mala selección de algoritmos para este problema?

Answer 1

Sí: puede encontrar todas las cadenas dentro de una distancia determinada de una cadena en tiempo O (log n) utilizando BK-Tree . Las soluciones alternativas que implican generar cada cadena con distancia n pueden ser más rápidas para una distancia de levenshtein de 1, pero la cantidad de trabajo se hincha rápidamente fuera de control para distancias más largas.

Answer 2

Puedes hacerlo con Levenshtein en O (kl) , donde k es tu distancia máxima y l es la cadena máxima.

Básicamente, cuando sabes cómo calcular Levenshtein básico, es fácil darse cuenta de que cada resultado que está más allá de k de la diagonal principal tiene que ser más grande que k . Por lo tanto, si calcula la diagonal principal con el ancho 2k + 1 será suficiente.

Si tiene 10000 direcciones de correo electrónico, no necesitará un algoritmo más rápido. La computadora puede calcular con O (N ^ 2) lo suficientemente rápido.

Levenshtein es bastante bueno para este tipo de problema.

También lo que podría considerar es transformar los correos electrónicos con soundex antes de compararlos. Probablemente obtendrás mejores resultados.

Answer 3

Este problema se conoce como agrupación en clúster y es parte de un problema más grande de deduplicación (donde puede decidir qué miembro del clúster es " el correcto » ), también conocido como purge-purge .

Una vez leí algunos artículos de investigación sobre exactamente este tema (los nombres están debajo) y, básicamente, los autores usaron una ventana deslizante de tamaño limitado sobre una lista ordenada de cadenas. Solo compararían (utilizando un algoritmo distancia de edición ) N * N cadenas dentro la ventana, reduciendo así la complejidad computacional. Si cualquiera de las dos cadenas se veían similares, se combinaron en un grupo (insertando un registro en una tabla de grupos separados).

El primer paso a través de la lista fue seguido por un segundo paso donde las cadenas fueron invertidas antes de ser ordenadas. De esta manera, las cadenas con cabezas diferentes tuvieron otra oportunidad de acercarse lo suficiente como para ser evaluadas como parte de la misma ventana. En esta segunda pasada, si una cadena se viera lo suficientemente cerca de dos (o más) cadenas en la ventana, y esas cadenas ya formaban parte de sus propios grupos (encontrados por el primer paso), los dos grupos se fusionarían (actualizando la tabla de clústeres) y la cadena actual se agregará al clúster recién fusionado. Este enfoque de agrupación en clústeres se conoce como el algoritmo union-find .

Luego mejoraron el algoritmo al reemplazar la ventana con una lista de los principales prototipos sustancialmente únicos . Cada nueva cadena se compararía con cada uno de los mejores prototipos de X. Si la cadena se veía lo suficientemente cerca de uno de los prototipos, se agregaría al grupo de prototipos . Si ninguno de los prototipos parecía lo suficientemente similar, la cadena se convertiría en un nuevo prototipo, eliminando al prototipo más antiguo de la lista de las X principales. (Se empleó una lógica heurística para decidir cuál de las cadenas en el grupo del prototipo debería usarse como el nuevo prototipo que representa el grupo completo). Nuevamente, si la cadena fuera similar a varios prototipos, todos sus grupos se fusionarían.

Una vez implementé este algoritmo para la deduplicación de registros de nombre / dirección con tamaños de las listas de alrededor de 10-50 millones de registros y funcionó bastante rápido (y también encontré duplicados).

En general, para estos problemas, la parte más complicada es encontrar el valor correcto del umbral de similitud . La idea es capturar todos los dups sin producir demasiados falsos positivos . Los datos con diferentes características tienden a requerir umbrales diferentes. La elección de un algoritmo de distancia de edición también es importante ya que algunos algoritmos son mejores para los errores de OCR, mientras que otros son mejores para los errores tipográficos y otros son mejores para los errores fonéticos (como cuando se obtiene un nombre por teléfono).

Una vez que se implementa el algoritmo de agrupamiento, una buena manera de probarlo es obtener una lista de muestras únicas y mutar artificialmente cada muestra para producir sus variaciones, a la vez que se conserva el hecho de que todas las variaciones tienen provienen del mismo padre. Esta lista se baraja entonces y se alimenta al algoritmo. La comparación de la agrupación en clúster original con la agrupación en clúster producida por el algoritmo de deduplicación le dará la puntuación de eficiencia .

Bibliografía:

Hernandez M. 1995, El problema de fusión / purga para grandes bases de datos.

Monge A. 1997, Un algoritmo independiente de dominio eficiente para detectar registros de base de datos aproximadamente duplicados.

Answer 4

No creo que puedas hacerlo mejor que O (n ^ 2) pero puedes hacer algunas optimizaciones más pequeñas que podrían ser lo suficiente para acelerar tu aplicación:

• Primero puede ordenar todas las direcciones de correo electrónico por la parte después de la @ y solo comparar las direcciones donde sea la misma
• Puede dejar de calcular la distancia entre dos direcciones cuando se hace más grande que n

EDITAR: En realidad puedes hacerlo mejor que O (n ^ 2), solo mira la respuesta de Nick Johnson a continuación.

Answer 5

10.000 direcciones de correo electrónico no suenan demasiado. Para buscar similitudes en un espacio más grande, puede usar teja y min-hashing . Este algoritmo es un poco más complicado de implementar, pero es mucho más eficiente en un espacio grande.

Answer 6

Es posible hacerlo mejor, a condición de revertir el problema.

Supongo que aquí tus 10.000 direcciones están bastante 'fijas', de lo contrario tendrás que agregar un mecanismo de actualización.

La idea es usar la distancia Levenshtein, pero en modo 'inverso', en Python:

class Addresses:
  def __init__(self,addresses):
    self.rep = dict()
    self.rep[0] = self.generate_base(addresses)
      # simple dictionary which associate an address to itself

    self.rep[1] = self.generate_level(1)
    self.rep[2] = self.generate_level(2)
    # Until N

El método generate_level genera todas las variaciones posibles del conjunto anterior, menos las variaciones que ya existen en un nivel anterior. Conserva el 'origen' como el valor asociado a la clave.

Luego, solo tiene que buscar su palabra en los diferentes conjuntos:

  def getAddress(self, address):
    list = self.rep.keys()
    list.sort()
    for index in list:
      if address in self.rep[index]:
        return (index, self.rep[index][address]) # Tuple (distance, origin)
    return None

Al hacerlo, computas los distintos conjuntos una vez (esto toma algunas veces ... pero luego puedes serializarlo y mantenerlo para siempre).

Y luego la búsqueda es mucho más eficiente que O (n ^ 2), aunque darlo exactamente es un poco difícil ya que depende del tamaño de los conjuntos que se generan.

Para referencia, eche un vistazo a: http://norvig.com/spell-correct.html

Answer 7

Digamos que tienes 3 cadenas:

1 - " abc " 2 - " bcd " 3 - " cde "

La distancia L entre 1 y amp; 2 es 2 (restar 'a', agregar 'd'). La distancia L entre 2 y amp; 3 es 2 (restar 'b', agregar 'e').

Su pregunta es si podemos inferir una L Distancia entre 1 y amp; 3 utilizando las 2 comparaciones anteriores. La respuesta es no.

La distancia L entre 1 y amp; 3 es 3 (reemplaza cada carácter), no hay forma de que esto pueda inferirse debido a los puntajes de los primeros 2 cálculos. Las puntuaciones no revelan si se realizaron operaciones de eliminación, inserción o sustitución.

Por lo tanto, diría que Levenshtein es una mala elección para una gran lista.

Answer 8

Si realmente estás comparando direcciones de correo electrónico, una forma obvia de hacerlo sería combinar un algoritmo de levenshtein con la asignación de dominios. Puedo pensar en ocasiones en las que me he registrado para algo varias veces usando el mismo dominio, pero con variaciones en la parte del nombre de usuario de la dirección de correo electrónico.