algorithm - moore - Rango de similitud de cadenas/hash

distancias de levenshtein

Question

¿Hay algún método para calcular algo así como un "puntaje de similitud" general de una cuerda? De una manera que no estoy comparando dos cadenas juntas, sino que obtengo un número (hash) para cada cadena que luego puede decirme que dos cadenas son o no son similares. Dos cadenas similares deberían tener hashes similares (cercanos).

Consideremos estas cadenas y puntajes como un ejemplo:

Hello world                1000
Hello world!               1010
Hello earth                1125
Foo bar                    3250
FooBarbar                  3750
Foo Bar!                   3300
Foo world!                 2350

¡Puedes ver ese Hola mundo! y Hello World son similares y sus puntajes están cerca el uno del otro.

De esta forma, encontrar las cadenas más similares a una cadena dada se haría restando la puntuación de las cadenas dadas de otras puntuaciones y luego ordenando su valor absoluto.

Answer 1

Bueno, podrías sumar el valor de ascii de cada personaje y luego comparar los puntajes, teniendo un valor máximo en el que pueden diferir. Sin embargo, esto no garantiza que sean similares, por la misma razón que dos cadenas diferentes pueden tener el mismo valor hash.

Por supuesto, podría hacer una función más compleja, comenzando por verificar el tamaño de las cuerdas, y luego comparando cada caracter uno por uno, nuevamente con una diferencia máxima configurada.

Answer 2

Creo que lo que estás buscando se llama Locality Sensitive Hash . Mientras que la mayoría de los algoritmos hash están diseñados de forma tal que pequeñas variaciones en la entrada causan grandes cambios en la salida, estos hash intentan lo contrario: pequeños cambios en la entrada generan cambios proporcionalmente pequeños en la salida.

Como otros han mencionado, existen problemas inherentes al forzar un mapeo multidimensional a un mapeo bidimensional. Es análogo a crear un mapa plano de la Tierra ... nunca se puede representar con precisión una esfera sobre una superficie plana. Lo mejor que puede hacer es encontrar un LSH que esté optimizado para cualquier función que esté usando para determinar si las cadenas son "parecidas".

Answer 3

En el procesamiento del lenguaje natural , tenemos una cosa llamada Distancia mínima de edición (también conocida como Distancia Levenshtein)
Se define básicamente como la cantidad más pequeña de operación necesaria para transformar string1 en string2
Operaciones incluidas Inserción, Supresión, Sustitución , a cada operación se le asigna una puntuación a la que se agrega a la distancia
La idea de resolver su problema es calcular el MED de su cadena elegida, a todas las demás cadenas, ordenar esa colección y seleccionar la n-ésima cadena de distancia más pequeña
Por ejemplo:

{"Hello World", "Hello World!", "Hello Earth"}
Choosing base-string="Hello World"  
Med(base-string, "Hello World!") = 1  
Med(base-string, "Hello Earth") = 8  
1st closest string is "Hello World!"

Esto le ha dado un puntaje a cada cuerda de tu colección de cuerdas
Implementación de C # (Add-1, Deletion-1, Subsitution-2)

public static int Distance(string s1, string s2)
{
    int[,] matrix = new int[s1.Length + 1, s2.Length + 1];

    for (int i = 0; i <= s1.Length; i++)
        matrix[i, 0] = i;
    for (int i = 0; i <= s2.Length; i++)
        matrix[0, i] = i;

    for (int i = 1; i <= s1.Length; i++)
    {
        for (int j = 1; j <= s2.Length; j++)
        {
            int value1 = matrix[i - 1, j] + 1;
            int value2 = matrix[i, j - 1] + 1;
            int value3 = matrix[i - 1, j - 1] + ((s1[i - 1] == s2[j - 1]) ? 0 : 2);

            matrix[i, j] = Math.Min(value1, Math.Min(value2, value3));
        }
    }

    return matrix[s1.Length, s2.Length];
}

Complejidad O (nxm) donde n, m es la longitud de cada cuerda
Más información sobre la distancia mínima de edición se puede encontrar here

Answer 4

En un problema ilimitado, no existe una solución que pueda convertir cualquier secuencia posible de palabras o cualquier posible secuencia de caracteres en un solo número que describa la localidad.

Imagina similitud a nivel de personaje

stops
spots

hello world
world hello

En ambos ejemplos, los mensajes son diferentes, pero los caracteres en el mensaje son idénticos, por lo que la medida necesitaría mantener un valor de posición, así como un valor de carácter. (char 0 == ''h'', char 1 == ''e'' ...)

Luego compare los siguientes mensajes similares

hello world
ello world

Aunque las dos cadenas son similares, podrían diferir al principio o al final, lo que hace que la escala por posición sea problemática.

En el caso de

spots
stops

Las palabras solo difieren según la posición de los personajes, por lo que alguna forma de posición es importante.

Si las siguientes cadenas son similares

 yesssssssssssssss
 yessssssssssssss

Entonces tienes una forma de paradoja. Si agrega 2 s caracteres a la segunda cadena, debe compartir la distancia desde la primera cadena, pero debe ser distinta. Esto se puede repetir obteniendo cadenas progresivamente más largas, todas las cuales necesitan estar cerca de las cuerdas, más cortas y más largas que ellas. No puedo ver cómo lograr esto.

En general, esto se trata como un problema multidimensional: romper la cadena en un vector

[ ''h'', ''e'', ''l'', ''l'', ''o'', '' '', ''w'', ''o'', ''r'', ''l'', ''d'' ]

Pero los valores del vector no pueden ser

• representado por un número de tamaño fijo, o
• dar buena medida de diferencia de calidad.

Si el número de palabras, o la longitud de las cadenas fueron acotadas, entonces una solución de codificación puede ser posible.

Valores limitados

Utilizando algo así como la compresión aritmética, una secuencia de palabras se puede convertir en un número de punto flotante que representa la secuencia. Sin embargo, esto trataría los elementos más temprano en la secuencia como más significativos que el último elemento de la secuencia.

solución de minería de datos

Si acepta que el problema es de alta dimensión, puede almacenar sus cadenas en una wikipedia: árbol métrico . Esto limitaría su espacio de búsqueda, sin resolver su solución de "número único".

Tengo un código para tales en github: clustering

Los elementos que están juntos, deben almacenarse juntos en una parte del árbol, pero realmente no hay garantía. El radio de los subárboles se usa para podar el espacio de búsqueda.

Editar distancia o distancia Levenshtein

Esto se usa en una extensión sqlite para realizar búsquedas de similitud, pero sin una solución numérica única, determina cuántas ediciones cambian una cadena por otra. Esto luego da como resultado una puntuación, que muestra similitud.

Answer 5

Es poco probable que uno pueda obtener un número bastante pequeño de dos frases que, al ser comparadas, proporcionan una indicación relevante de la similitud de sus frases iniciales.
Una razón es que el número da una indicación en una dimensión, mientras que las frases evolucionan en dos dimensiones, longitud e intensidad.

El número podría evolucionar tanto en longitud como en intensidad, pero no estoy seguro de que ayude mucho.

En dos dimensiones, es mejor que mire una matriz, que algunas propiedades como el determinante (un tipo de derivado de la matriz) podría dar una idea aproximada de la tendencia de la frase.

Answer 6

Esto no es posible, en general, porque el conjunto de distancias de edición entre cadenas forma un espacio métrico , pero no uno con una dimensión fija. Eso significa que no puede proporcionar una asignación entre cadenas y enteros que preserve una medida de distancia entre ellos.

Por ejemplo, no puede asignar números a estas tres frases:

• uno dos
• uno seis
• dos seis

Tal que los números reflejan la diferencia entre las tres frases.

Answer 7

La distancia de Levenstein o sus derivados es el algoritmo que desea. Haga coincidir la cadena dada con cada una de las cadenas del diccionario. (Aquí, si solo necesita un número fijo de cadenas más similares, puede usar min-heap.) Si ejecutar la distancia de Levenstein para todas las cadenas del diccionario es demasiado costoso, utilice primero un algoritmo aproximado que excluya palabras demasiado distantes de lista de candidatos. Después de eso, corra la distancia levenstein en los candidatos de la izquierda.

Una forma de eliminar palabras distantes es indexar n-grams. Preprocesa el diccionario dividiendo cada una de las palabras en una lista de n-gramas. Por ejemplo, considere n = 3:

(0) "Hello world" -> ["Hel", "ell", "llo", "lo ", "o w", " wo", "wor", "orl", "rld"]
(1) "FooBarbar" -> ["Foo", "ooB", "oBa", "Bar", "arb", "rba", "bar"]
(2) "Foo world!" -> ["Foo", "oo ", "o w", " wo", "wor", "orl", "rld", "ld!"]

A continuación, crea el índice de n-gramms:

" wo" -> [0, 2]
"Bar" -> [1]
"Foo" -> [1, 2]
"Hel" -> [0]
"arb" -> [1]
"bar" -> [1]
"ell" -> [0]
"ld!" -> [2]
"llo" -> [0]
"lo " -> [0]
"o w" -> [0, 2]
"oBa" -> [1]
"oo " -> [2]
"ooB" -> [1]
"orl" -> [0, 2]
"rba" -> [1]
"rld" -> [0, 2]
"wor" -> [0, 2]

Cuando necesite encontrar cadenas más similares para una cadena dada, divida la cadena dada en n-grams y seleccione solo aquellas palabras del diccionario que tengan al menos un n-gram coincidente. Esto reduce el número de candidatos a una cantidad razonable y puede continuar con la cadena dada de equivalencia levenstein a cada uno de los candidatos izquierdos.

Si sus cadenas son lo suficientemente largas, puede reducir el tamaño del índice mediante el uso de min-hashing technnique: calcula el hash ordinario para cada uno de los n-grams y usa solo K hash más pequeños, otros se descartan.

PD, esta presentación parece una buena introducción a su problema.

Answer 8

Pienso en algo como esto:

1. eliminar todos los caracteres que no sean palabras
2. aplicar soundex

Answer 9

Si bien la idea parece extremadamente dulce ... nunca he oído hablar de esto.

He leído muchas, muchas, técnicas, tesis y artículos científicos sobre el tema de corrección de ortografía / corrección de errores tipográficos y las propuestas más rápidas giran en torno a un índice y la distancia levenshtein.

Hay técnicas bastante elaboradas, en la que estoy trabajando actualmente combina:

• Un Trie Bursted, con compacidad de nivel
• Un autómata de Levenshtein

Aunque esto no significa que sea "imposible" obtener un puntaje, de alguna manera creo que no habría tantas investigaciones recientes en las comparaciones de cuerdas si dicho método de "calificación" hubiera resultado eficiente.

Si alguna vez encuentras un método así, estoy extremadamente interesado :)

Answer 10

Su idea suena como ontology pero se aplica a frases completas. Cuanto más similares sean dos frases, más cercanas estarán en el gráfico (suponiendo que esté utilizando bordes pesados). Y viceversa: las frases no similares están muy lejos la una de la otra.

Otro enfoque, es usar la transformada de Fourier para obtener una especie de ''índice'' para una cadena dada (no será un solo número, sino siempre). Puede encontrar un poco más en ontology .

Y otra idea, que se basa en la distancia de Levenshtein: puedes comparar n-grams que te dará un índice de similitud para dos frases dadas: cuanto más similares sean, el valor estará más cerca de 1. Esto se puede usar para calcular la distancia en el grafico. escribió un artículo sobre esto hace unos años, si quieres puedo compartirlo.

De todos modos: a pesar de que no sé la solución exacta, también estoy interesado en lo que se te ocurre.

Answer 11

Tal vez use PCA , donde la matriz es una lista de las diferencias entre la cadena y un alfabeto fijo (à la ABCDEFGHI ...). La respuesta podría ser simplemente la longitud del componente principal.

Solo una idea.

PCA listo para ejecutar en C #

Answer 12

Levenshtein distancia trabajo para usted?