Obteniendo la cadena más cercana

397

Necesito una forma de comparar varias cadenas con una cadena de prueba y devolver la cadena que se parece mucho a ella:

TEST STRING: THE BROWN FOX JUMPED OVER THE RED COW

CHOICE A   : THE RED COW JUMPED OVER THE GREEN CHICKEN
CHOICE B   : THE RED COW JUMPED OVER THE RED COW
CHOICE C   : THE RED FOX JUMPED OVER THE BROWN COW

(Si hice esto correctamente) La cadena más cercana a "TEST STRING" debería ser "CHOICE C". ¿Cuál es la forma más fácil de hacer esto?

Planeo implementar esto en varios idiomas, incluidos VB.net, Lua y JavaScript. En este punto, el pseudocódigo es aceptable. Si puede proporcionar un ejemplo para un idioma específico, ¡esto también se agradece!

Freesnöw
fuente
3
Los algoritmos que generalmente hacen este tipo de cosas funcionan para determinar cuántos cambios se necesitan para convertir una cadena examinada en la cadena de destino. Esos tipos de algoritmos no funcionan bien en una situación como esta. Creo que conseguir una computadora para lograr esto será muy difícil.
Matt Greer
3
Código fuente de distancia de Levenshtein en muchos idiomas: Java, Ruby, Python, PHP, etc. en.wikibooks.org/wiki/Algorithm_Implementation/Strings/…
joelparkerhenderson
99
En general, lo que cuenta como "cadena más cercana" dependerá de la medida de similitud utilizada y las penalizaciones utilizadas para introducir espacios en la alineación. Por ejemplo, ¿considera que "vaca" y "pollo" son más similares que "vaca" y "rojo" (porque son conceptos relacionados), o es al revés (porque "pollo" tiene más letras que "vaca" )? Pero dada una medida de similitud y una penalización de espacio, se puede demostrar que el siguiente algoritmo de Levenshtein te garantiza encontrar la cadena más cercana. Lo mismo ocurre con Needleman-Wunsch y Smith-Waterman (más abajo).
Sten L
Hacer agrupación de caracteres o agrupación de palabras. Dale puntaje.
Casey

Respuestas:

952

Me presentaron este problema hace aproximadamente un año cuando se trataba de buscar información ingresada por el usuario sobre una plataforma petrolera en una base de datos de información diversa. El objetivo era hacer algún tipo de búsqueda de cadena difusa que pudiera identificar la entrada de la base de datos con los elementos más comunes.

Parte de la investigación implicó la implementación del algoritmo de distancia de Levenshtein , que determina cuántos cambios se deben realizar en una cadena o frase para convertirla en otra cadena o frase.

La implementación que se me ocurrió fue relativamente simple e implicó una comparación ponderada de la longitud de las dos frases, el número de cambios entre cada frase y si cada palabra se podía encontrar en la entrada de destino.

El artículo está en un sitio privado, así que haré todo lo posible para agregar los contenidos relevantes aquí:


Fuzzy String Matching es el proceso de realizar una estimación similar a la humana de la similitud de dos palabras o frases. En muchos casos, implica identificar palabras o frases que son más similares entre sí. Este artículo describe una solución interna al problema de coincidencia de cadenas difusas y su utilidad para resolver una variedad de problemas que pueden permitirnos automatizar tareas que anteriormente requerían una tediosa participación del usuario.

Introducción

La necesidad de hacer una coincidencia difusa de cadenas surgió originalmente mientras se desarrollaba la herramienta Validator del Golfo de México. Lo que existía era una base de datos de plataformas y plataformas petroleras conocidas del golfo de México, y las personas que compran seguros nos darían información mal escrita sobre sus activos y tuvimos que hacerla coincidir con la base de datos de plataformas conocidas. Cuando se proporcionó muy poca información, lo mejor que pudimos hacer es confiar en que un asegurador "reconozca" al que se refería y solicite la información adecuada. Aquí es donde esta solución automatizada es útil.

Pasé un día investigando métodos de coincidencia de cadenas difusas, y finalmente me topé con el muy útil algoritmo de distancia de Levenshtein en Wikipedia.

Implementación

Después de leer sobre la teoría detrás de esto, implementé y encontré formas de optimizarlo. Así es como se ve mi código en VBA:

'Calculate the Levenshtein Distance between two strings (the number of insertions,
'deletions, and substitutions needed to transform the first string into the second)
Public Function LevenshteinDistance(ByRef S1 As String, ByVal S2 As String) As Long
    Dim L1 As Long, L2 As Long, D() As Long 'Length of input strings and distance matrix
    Dim i As Long, j As Long, cost As Long 'loop counters and cost of substitution for current letter
    Dim cI As Long, cD As Long, cS As Long 'cost of next Insertion, Deletion and Substitution
    L1 = Len(S1): L2 = Len(S2)
    ReDim D(0 To L1, 0 To L2)
    For i = 0 To L1: D(i, 0) = i: Next i
    For j = 0 To L2: D(0, j) = j: Next j

    For j = 1 To L2
        For i = 1 To L1
            cost = Abs(StrComp(Mid$(S1, i, 1), Mid$(S2, j, 1), vbTextCompare))
            cI = D(i - 1, j) + 1
            cD = D(i, j - 1) + 1
            cS = D(i - 1, j - 1) + cost
            If cI <= cD Then 'Insertion or Substitution
                If cI <= cS Then D(i, j) = cI Else D(i, j) = cS
            Else 'Deletion or Substitution
                If cD <= cS Then D(i, j) = cD Else D(i, j) = cS
            End If
        Next i
    Next j
    LevenshteinDistance = D(L1, L2)
End Function

Simple, rápido y una métrica muy útil. Usando esto, creé dos métricas separadas para evaluar la similitud de dos cadenas. Una que llamo "valuePhrase" y otra que llamo "valueWords". valuePhrase es solo la distancia de Levenshtein entre las dos frases, y valueWords divide la cadena en palabras individuales, en función de delimitadores como espacios, guiones y cualquier otra cosa que desee, y compara cada palabra entre sí, resumiendo la más corta Distancia de Levenshtein que conecta dos palabras cualquiera. Esencialmente, mide si la información en una 'frase' está realmente contenida en otra, solo como una permutación de palabras. Pasé unos días como proyecto paralelo para encontrar la forma más eficiente posible de dividir una cadena basada en delimitadores.

Función valueWords, valuePhrase y Split:

Public Function valuePhrase#(ByRef S1$, ByRef S2$)
    valuePhrase = LevenshteinDistance(S1, S2)
End Function

Public Function valueWords#(ByRef S1$, ByRef S2$)
    Dim wordsS1$(), wordsS2$()
    wordsS1 = SplitMultiDelims(S1, " _-")
    wordsS2 = SplitMultiDelims(S2, " _-")
    Dim word1%, word2%, thisD#, wordbest#
    Dim wordsTotal#
    For word1 = LBound(wordsS1) To UBound(wordsS1)
        wordbest = Len(S2)
        For word2 = LBound(wordsS2) To UBound(wordsS2)
            thisD = LevenshteinDistance(wordsS1(word1), wordsS2(word2))
            If thisD < wordbest Then wordbest = thisD
            If thisD = 0 Then GoTo foundbest
        Next word2
foundbest:
        wordsTotal = wordsTotal + wordbest
    Next word1
    valueWords = wordsTotal
End Function

''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' SplitMultiDelims
' This function splits Text into an array of substrings, each substring
' delimited by any character in DelimChars. Only a single character
' may be a delimiter between two substrings, but DelimChars may
' contain any number of delimiter characters. It returns a single element
' array containing all of text if DelimChars is empty, or a 1 or greater
' element array if the Text is successfully split into substrings.
' If IgnoreConsecutiveDelimiters is true, empty array elements will not occur.
' If Limit greater than 0, the function will only split Text into 'Limit'
' array elements or less. The last element will contain the rest of Text.
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Function SplitMultiDelims(ByRef Text As String, ByRef DelimChars As String, _
        Optional ByVal IgnoreConsecutiveDelimiters As Boolean = False, _
        Optional ByVal Limit As Long = -1) As String()
    Dim ElemStart As Long, N As Long, M As Long, Elements As Long
    Dim lDelims As Long, lText As Long
    Dim Arr() As String

    lText = Len(Text)
    lDelims = Len(DelimChars)
    If lDelims = 0 Or lText = 0 Or Limit = 1 Then
        ReDim Arr(0 To 0)
        Arr(0) = Text
        SplitMultiDelims = Arr
        Exit Function
    End If
    ReDim Arr(0 To IIf(Limit = -1, lText - 1, Limit))

    Elements = 0: ElemStart = 1
    For N = 1 To lText
        If InStr(DelimChars, Mid(Text, N, 1)) Then
            Arr(Elements) = Mid(Text, ElemStart, N - ElemStart)
            If IgnoreConsecutiveDelimiters Then
                If Len(Arr(Elements)) > 0 Then Elements = Elements + 1
            Else
                Elements = Elements + 1
            End If
            ElemStart = N + 1
            If Elements + 1 = Limit Then Exit For
        End If
    Next N
    'Get the last token terminated by the end of the string into the array
    If ElemStart <= lText Then Arr(Elements) = Mid(Text, ElemStart)
    'Since the end of string counts as the terminating delimiter, if the last character
    'was also a delimiter, we treat the two as consecutive, and so ignore the last elemnent
    If IgnoreConsecutiveDelimiters Then If Len(Arr(Elements)) = 0 Then Elements = Elements - 1

    ReDim Preserve Arr(0 To Elements) 'Chop off unused array elements
    SplitMultiDelims = Arr
End Function

Medidas de similitud

Utilizando estas dos métricas, y una tercera que simplemente calcula la distancia entre dos cadenas, tengo una serie de variables que puedo ejecutar un algoritmo de optimización para lograr el mayor número de coincidencias. La coincidencia de cadenas difusas es, en sí misma, una ciencia difusa, por lo que al crear métricas linealmente independientes para medir la similitud de cadenas y al tener un conjunto conocido de cadenas que deseamos unir entre sí, podemos encontrar los parámetros que, para nuestros estilos específicos de cadenas, da los mejores resultados de partidos difusos.

Inicialmente, el objetivo de la métrica era tener un valor de búsqueda bajo para una coincidencia exacta y aumentar los valores de búsqueda para medidas cada vez más permutadas. En un caso poco práctico, esto fue bastante fácil de definir usando un conjunto de permutaciones bien definidas, y diseñando la fórmula final de modo que tuvieran resultados de valores de búsqueda crecientes según lo deseado.

Permutaciones coincidentes con cadenas difusas

En la captura de pantalla anterior, modifiqué mi heurística para encontrar algo que sentí que se adaptaba bien a mi diferencia percibida entre el término de búsqueda y el resultado. La heurística que utilicé Value Phraseen la hoja de cálculo anterior fue =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2)). Estaba reduciendo efectivamente la penalización de la distancia de Levenstein en un 80% de la diferencia en la longitud de las dos "frases". De esta manera, las "frases" que tienen la misma longitud sufren la penalización completa, pero las "frases" que contienen "información adicional" (más larga) pero aparte de eso aún comparten los mismos caracteres sufren una penalización reducida. Usé elValue Words función tal como está, y luego mi SearchValheurística final se definió como=MIN(D2,E2)*0.8+MAX(D2,E2)*0.2- un promedio ponderado. Cualquiera de los dos puntajes más bajos obtuvo una ponderación del 80% y el 20% del puntaje más alto. Esto fue solo una heurística que se adaptaba a mi caso de uso para obtener una buena tasa de coincidencia. Estos pesos son algo que uno podría ajustar para obtener la mejor tasa de coincidencia con sus datos de prueba.

Frase de valor de coincidencia de cadena difusa

Palabras de valor coincidente de cadena difusa

Como puede ver, las dos últimas métricas, que son métricas de coincidencia de cadenas difusas, ya tienen una tendencia natural a dar puntajes bajos a las cadenas que deben coincidir (en la diagonal). Esto es muy bueno.

Aplicación Para permitir la optimización de la coincidencia difusa, ponderé cada métrica. Como tal, cada aplicación de coincidencia de cadena difusa puede ponderar los parámetros de manera diferente. La fórmula que define el puntaje final es simplemente una combinación de las métricas y sus pesos:

value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight
      + Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight
      + lengthWeight*lengthValue

Usando un algoritmo de optimización (la red neuronal es mejor aquí porque es un problema discreto y multidimensional), el objetivo ahora es maximizar el número de coincidencias. Creé una función que detecta el número de coincidencias correctas de cada conjunto entre sí, como se puede ver en esta captura de pantalla final. Una columna o fila obtiene un punto si se asigna el puntaje más bajo a la cadena que debía coincidir, y se otorgan puntos parciales si hay un empate para el puntaje más bajo, y la coincidencia correcta se encuentra entre las cadenas empatadas. Entonces lo optimicé. Puede ver que una celda verde es la columna que mejor coincide con la fila actual, y un cuadrado azul alrededor de la celda es la fila que mejor coincide con la columna actual. El puntaje en la esquina inferior es aproximadamente el número de coincidencias exitosas y esto es lo que le decimos a nuestro problema de optimización para maximizar.

Fuzzy String Matching Métrica optimizada

El algoritmo fue un éxito maravilloso, y los parámetros de la solución dicen mucho sobre este tipo de problema. Notará que el puntaje optimizado fue 44, y el mejor puntaje posible es 48. Las 5 columnas al final son señuelos y no tienen ninguna coincidencia con los valores de las filas. Cuantos más señuelos haya, más difícil será encontrar la mejor combinación.

En este caso de coincidencia particular, la longitud de las cadenas es irrelevante, porque esperamos abreviaturas que representen palabras más largas, por lo que el peso óptimo para la longitud es -0.3, lo que significa que no penalizamos cadenas que varían en longitud. Reducimos la puntuación en anticipación de estas abreviaturas, dando más espacio para que las coincidencias parciales de palabras reemplacen las coincidencias que no son palabras que simplemente requieren menos sustituciones porque la cadena es más corta.

El peso de la palabra es 1.0, mientras que el peso de la frase es solo 0.5, lo que significa que penalizamos las palabras enteras que faltan en una cadena y valoramos más que la frase entera esté intacta. Esto es útil porque muchas de estas cadenas tienen una palabra en común (el peligro) donde lo que realmente importa es si la combinación (región y peligro) se mantiene o no.

Finalmente, el peso mínimo se optimiza en 10 y el peso máximo en 1. Lo que esto significa es que si la mejor de las dos puntuaciones (frase de valor y palabras de valor) no es muy buena, la coincidencia se penaliza enormemente, pero no No penaliza en gran medida el peor de los dos puntajes. Esencialmente, esto pone énfasis en exigir que valueWord o valuePhrase tengan una buena puntuación, pero no ambas. Una especie de mentalidad de "tomar lo que podemos obtener".

Es realmente fascinante lo que dice el valor optimizado de estos 5 pesos sobre el tipo de coincidencia de cadena difusa que tiene lugar. Para casos prácticos completamente diferentes de coincidencia de cadenas difusas, estos parámetros son muy diferentes. Lo he usado para 3 aplicaciones separadas hasta ahora.

Si bien no se utilizó en la optimización final, se estableció una hoja de evaluación comparativa que hace coincidir las columnas entre sí para obtener todos los resultados perfectos en la diagonal, y permite al usuario cambiar los parámetros para controlar la velocidad a la que los puntajes difieren de 0 y observar similitudes innatas entre las frases de búsqueda ( que en teoría podría usarse para compensar los falsos positivos en los resultados)

Punto de referencia de coincidencia de cadena difusa

Aplicaciones adicionales

Esta solución tiene potencial para usarse en cualquier lugar donde el usuario desee que un sistema informático identifique una cadena en un conjunto de cadenas donde no hay una coincidencia perfecta. (Como una coincidencia aproximada vlookup para cadenas).


Entonces, lo que debe tomar de esto es que probablemente quiera usar una combinación de heurística de alto nivel (encontrar palabras de una frase en la otra frase, longitud de ambas frases, etc.) junto con la implementación del algoritmo de distancia de Levenshtein. Debido a que decidir cuál es la "mejor" coincidencia es una determinación heurística (difusa): tendrá que encontrar un conjunto de ponderaciones para cualquier métrica que se le ocurra para determinar la similitud.

Con el conjunto apropiado de heurísticas y pesos, tendrá su programa de comparación tomando rápidamente las decisiones que habría tomado.

Alain
fuente
13
Bonificación: si alguien quiere incluir métricas adicionales en su heurística ponderada (ya que solo proporcioné 3 que no eran tan linealmente independientes), aquí hay una lista completa en wikipedia: en.wikipedia.org/wiki/String_metric
Alain
1
Si S2 tiene muchas palabras (y crear muchos objetos pequeños no es prohibitivamente lento en el idioma que elija), un trie puede acelerar las cosas. La distancia rápida y fácil de Levenshtein usando un Trie es un gran artículo sobre los intentos.
JanX2
1
@Alain ¡Este es un enfoque interesante! Solo estoy jugando un poco con tu idea (en C ++) pero no entiendo un punto, el valor de valuePhrase. Si veo bien en su código, es el valor de retorno de la función de distancia de Levenshtein. ¿Cómo es que es un valor doble / flotante en la tabla de búsqueda 'abcd efgh'? La distancia de Levenshtein es un valor entero y no puedo ver más cálculos en su código que lo hagan flotante. ¿Qué extraño?
Andreas W. Wylach el
1
@ AndreasW.Wylach Gran observación. El VBA que mostré fue solo para calcular la distancia de Levenshtein, pero la heurística que utilicé en mi hoja de cálculo fue =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2))Así que estaba reduciendo la penalización de la distancia de levenstein en un 80% de la diferencia en la longitud de las dos "frases". De esta manera, las "frases" que tienen la misma longitud sufren la penalización completa, pero las "frases" que contienen "información adicional" (más larga) pero aparte de eso, en su mayoría comparten los mismos caracteres, sufren una penalización reducida.
Alain el
1
@Alain Gracias por volver a mi pregunta, lo aprecio. Su explicación aclara las cosas ahora. Mientras tanto, implementé un método value_phrase que profundiza un poco más en el análisis de los tokens de una frase, ese es el orden / posiciones de los tokens de frase, secuencias de token que no son de consulta y acepta un poco más de confusión cuando se trata de algo como "acbd" en comparación con "abcd". La tendencia de los puntajes de frase_valor es igual a la suya, pero baja un poco aquí y allá Una vez más, ¡excelente entrenamiento y me inspiró para el algoritmo de búsqueda difusa!
Andreas W. Wylach
88

Este problema aparece todo el tiempo en bioinformática. La respuesta aceptada anteriormente (que fue genial por cierto) se conoce en bioinformática como los algoritmos Needleman-Wunsch (compare dos cadenas) y Smith-Waterman (encuentre una subcadena aproximada en una cadena más larga). Funcionan muy bien y han sido caballos de batalla durante décadas.

Pero, ¿qué pasa si tienes un millón de cadenas para comparar? ¡Eso es un billón de comparaciones por pares, cada una de las cuales es O (n * m)! Los secuenciadores de ADN modernos generan fácilmente mil millones de secuencias cortas de ADN, cada una de aproximadamente 200 "letras" de ADN de largo. Por lo general, queremos encontrar, para cada cadena, la mejor coincidencia con el genoma humano (3 mil millones de letras). Claramente, el algoritmo Needleman-Wunsch y sus parientes no funcionarán.

Este llamado "problema de alineación" es un campo de investigación activa. Los algoritmos más populares actualmente pueden encontrar coincidencias inexactas entre mil millones de cadenas cortas y el genoma humano en cuestión de horas en hardware razonable (por ejemplo, ocho núcleos y 32 GB de RAM).

La mayoría de estos algoritmos funcionan al encontrar rápidamente coincidencias exactas (semillas) y luego extenderlas a la cadena completa utilizando un algoritmo más lento (por ejemplo, el Smith-Waterman). La razón por la que esto funciona es que en realidad solo estamos interesados ​​en algunos partidos cercanos, por lo que vale la pena deshacerse del 99.9 ...% de pares que no tienen nada en común.

¿Cómo ayuda encontrar coincidencias exactas para encontrar coincidencias inexactas ? Bueno, digamos que permitimos solo una única diferencia entre la consulta y el objetivo. Es fácil ver que esta diferencia debe ocurrir en la mitad derecha o izquierda de la consulta, por lo que la otra mitad debe coincidir exactamente. Esta idea puede extenderse a múltiples desajustes y es la base para ELAND algoritmo comúnmente utilizado con los secuenciadores de ADN Illumina.

Hay muchos algoritmos muy buenos para hacer una coincidencia exacta de cadenas. Dada una cadena de consulta de longitud 200 y una cadena objetivo de longitud 3 mil millones (el genoma humano), queremos encontrar cualquier lugar en el objetivo donde haya una subcadena de longitud k que coincida exactamente con una subcadena de la consulta. Un enfoque simple es comenzar indexando el objetivo: tome todas las subcadenas de longitud k, colóquelas en una matriz y ordénelas. Luego tome cada subcadena de k-long de la consulta y busque el índice ordenado. La ordenación y la búsqueda se pueden realizar en tiempo O (log n).

Pero el almacenamiento puede ser un problema. Un índice del objetivo de 3 mil millones de letras debería contener 3 mil millones de punteros y 3 mil millones de palabras de longitud k. Parecería difícil ajustar esto en menos de varias decenas de gigabytes de RAM. Pero, sorprendentemente, podemos comprimir en gran medida el índice, utilizando la transformación Burrows-Wheeler , y seguirá siendo eficientemente consultable. Un índice del genoma humano puede caber en menos de 4 GB de RAM. Esta idea es la base de alineadores de secuencia populares como Bowtie y BWA .

Alternativamente, podemos usar una matriz de sufijos , que almacena solo los punteros, pero representa un índice simultáneo de todos los sufijos en la cadena de destino (esencialmente, un índice simultáneo para todos los valores posibles de k; lo mismo es cierto para la transformación Burrows-Wheeler ) Un índice de matriz de sufijo del genoma humano tomará 12 GB de RAM si usamos punteros de 32 bits.

Los enlaces anteriores contienen una gran cantidad de información y enlaces a documentos de investigación primarios. El enlace ELAND va a un PDF con figuras útiles que ilustran los conceptos involucrados y muestra cómo lidiar con las inserciones y eliminaciones.

Finalmente, si bien estos algoritmos básicamente han resuelto el problema de la (re) secuenciación de genomas humanos individuales (mil millones de cadenas cortas), la tecnología de secuenciación de ADN mejora aún más rápido que la ley de Moore, y nos estamos acercando rápidamente a conjuntos de datos de billones de letras. Por ejemplo, actualmente hay proyectos en curso para secuenciar los genomas de 10,000 especies de vertebrados , cada una de un billón de letras de largo. Naturalmente, querremos hacer una coincidencia de cadena inexacta por pares en los datos ...

Sten L
fuente
3
Muy buena decadencia. Un par de correcciones: la clasificación de los infijos requiere O (n) al menos, no O (log n). Y dado que la búsqueda de O (log n) en realidad es demasiado lenta en la práctica, normalmente construiría una tabla adicional para obtener la búsqueda de O (1) (índice de q-gramo). Además, no estoy seguro de por qué trata esto de manera diferente a la matriz de sufijos: es solo una optimización de este último, no (ordenar infijos de longitud fija en lugar de sufijos ya que en realidad no necesitamos más que una longitud fija).
Konrad Rudolph
1
Además, estos algoritmos aún no son prácticos para la secuenciación de novo . Han resuelto la secuenciación de genomas humanos solo en la medida en que tengamos una secuencia de referencia que pueda usarse para mapear. Pero para el ensamblaje de novo se necesitan otros algoritmos (bueno, hay algunos alineadores que se basan en el mapeo, pero unir los contigs es un problema completamente diferente). Finalmente, un complemento descarado: mi tesis de licenciatura contiene una descripción detallada del algoritmo ELAND.
Konrad Rudolph
1
Gracias. Edité el error. La razón por la que comencé describiendo la matriz de longitud fija fue porque es fácil de entender. Las matrices de sufijos y BWT son un poco más difíciles de comprender, pero en realidad a veces queremos usar un índice con diferentes valores de k. Por ejemplo, STAR usa matrices de sufijos para encontrar eficientemente alineaciones empalmadas . Por supuesto, esto es útil para alinear el ARN con el genoma.
Sten L
30

Confieso que la opción B está más cerca de la cadena de prueba, ya que solo son 4 caracteres (y 2 eliminaciones) de ser la cadena original. Mientras que usted ve C como más cerca porque incluye marrón y rojo. Sin embargo, tendría una mayor distancia de edición.

Hay un algoritmo llamado Distancia de Levenshtein que mide la distancia de edición entre dos entradas.

Aquí hay una herramienta para ese algoritmo.

  1. Elección de tarifas A como una distancia de 15.
  2. Tarifas de elección B como una distancia de 6.
  3. Tasas de elección C como una distancia de 9.

EDITAR: Lo siento, sigo mezclando cadenas en la herramienta levenshtein. Actualizado a las respuestas correctas.

adorablepuppy
fuente
2
Ok, supongo que es verdad. Echaré un vistazo a esto. Personalmente, no me importa lo cerca que esté del objetivo, siempre y cuando esté bastante cerca. No hay necesidad de perfección;) puntos para usted hasta que pueda verificar los resultados de su respuesta :)
Freesnöw
18

Implementación de Lua, para la posteridad:

function levenshtein_distance(str1, str2)
    local len1, len2 = #str1, #str2
    local char1, char2, distance = {}, {}, {}
    str1:gsub('.', function (c) table.insert(char1, c) end)
    str2:gsub('.', function (c) table.insert(char2, c) end)
    for i = 0, len1 do distance[i] = {} end
    for i = 0, len1 do distance[i][0] = i end
    for i = 0, len2 do distance[0][i] = i end
    for i = 1, len1 do
        for j = 1, len2 do
            distance[i][j] = math.min(
                distance[i-1][j  ] + 1,
                distance[i  ][j-1] + 1,
                distance[i-1][j-1] + (char1[i] == char2[j] and 0 or 1)
                )
        end
    end
    return distance[len1][len2]
end
Barro
fuente
14

Puede que te interese esta publicación de blog.

http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python

Fuzzywuzzy es una biblioteca de Python que proporciona medidas de distancia fáciles, como la distancia de Levenshtein para la coincidencia de cadenas. Está construido sobre difflib en la biblioteca estándar y hará uso de la implementación C Python-levenshtein si está disponible.

http://pypi.python.org/pypi/python-Levenshtein/

jseabold
fuente
Para otros que leen esto, Fuzzywuzzy implementa muchas de las ideas en la maravillosa publicación de Alain. Si realmente está buscando utilizar algunas de esas ideas, es un buen lugar para comenzar.
Gregory Arenius
12

¡Puede que le resulte útil esta biblioteca! http://code.google.com/p/google-diff-match-patch/

Actualmente está disponible en Java, JavaScript, Dart, C ++, C #, Objective C, Lua y Python

Funciona bastante bien también. Lo uso en un par de mis proyectos de Lua.

¡Y no creo que sea demasiado difícil portarlo a otros idiomas!

SatheeshJM
fuente
2

Si está haciendo esto en el contexto de un motor de búsqueda o frontend contra una base de datos, puede considerar usar una herramienta como Apache Solr , con ComplexPhraseQueryParser complemento . Esta combinación le permite buscar en un índice de cadenas con los resultados ordenados por relevancia, según lo determinado por la distancia de Levenshtein.

Lo hemos estado utilizando contra una gran colección de artistas y títulos de canciones cuando la consulta entrante puede tener uno o más errores tipográficos, y funcionó bastante bien (y notablemente rápido considerando que las colecciones están en millones de cadenas).

Además, con Solr, puede buscar en el índice bajo demanda a través de JSON, por lo que no tendrá que reinventar la solución entre los diferentes idiomas que está viendo.

Spoom
fuente
1

Un muy, muy buen recurso para este tipo de algoritmos es Simmetrics: http://sourceforge.net/projects/simmetrics/

Desafortunadamente, el increíble sitio web que contiene mucha documentación desapareció :( En caso de que vuelva a aparecer, su dirección anterior era esta: http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Voila (cortesía de "Wayback Machine"): http://web.archive.org/web/20081230184321/http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Puede estudiar la fuente del código, hay docenas de algoritmos para este tipo de comparaciones, cada uno con una compensación diferente. Las implementaciones están en Java.

oblio
fuente
1

Para consultar un gran conjunto de texto de manera eficiente, puede usar el concepto de Editar Distancia / Prefijo Editar Distancia.

Editar distancia ED (x, y): número mínimo de transfroms para obtener del término x al término y

Pero calcular la DE entre cada término y texto de consulta requiere muchos recursos y tiempo. Por lo tanto, en lugar de calcular ED para cada término primero, podemos extraer posibles términos coincidentes utilizando una técnica llamada Qgram Index. y luego aplique el cálculo ED en esos términos seleccionados.

Una ventaja de la técnica de índice de Qgram es que es compatible con Fuzzy Search.

Un posible enfoque para adaptar el índice QGram es construir un índice invertido usando Qgrams. Allí almacenamos todas las palabras que consisten en Qgram en particular, debajo de ese Qgram. (En lugar de almacenar una cadena completa, puede usar una identificación única para cada cadena). Puede usar la estructura de datos de Tree Map en Java para esto. El siguiente es un pequeño ejemplo sobre el almacenamiento de términos

col: col mbia, col ombo, gan col a, ta col ama

Luego, al realizar consultas, calculamos el número de Qgrams comunes entre el texto de la consulta y los términos disponibles.

Example: x = HILLARY, y = HILARI(query term)
Qgrams
$$HILLARY$$ -> $$H, $HI, HIL, ILL, LLA, LAR, ARY, RY$, Y$$
$$HILARI$$ -> $$H, $HI, HIL, ILA, LAR, ARI, RI$, I$$
number of q-grams in common = 4

cantidad de q-gramos en común = 4.

Para los términos con un alto número de Qgrams comunes, calculamos el ED / PED contra el término de la consulta y luego sugerimos el término al usuario final.

Puede encontrar una implementación de esta teoría en el siguiente proyecto (consulte "QGramIndex.java"). No dude en hacer cualquier pregunta. https://github.com/Bhashitha-Gamage/City_Search

Para estudiar más sobre Editar Distancia, Prefijo Editar Distancia Qgram índice, vea el siguiente video de la Prof. Dra. Hannah Bast https://www.youtube.com/embed/6pUg2wmGJRo (La lección comienza desde las 20:06)

Baxter
fuente
1

El problema es difícil de implementar si los datos de entrada son demasiado grandes (digamos millones de cadenas). Utilicé la búsqueda elástica para resolver esto.

Inicio rápido: https://www.elastic.co/guide/en/elasticsearch/client/net-api/6.x/elasticsearch-net.html

Simplemente inserte todos los datos de entrada en DB y puede buscar cualquier cadena en función de cualquier distancia de edición rápidamente. Aquí hay un fragmento de C # que le dará una lista de resultados ordenados por distancia de edición (de menor a mayor)

var res = client.Search<ClassName>(s => s
    .Query(q => q
    .Match(m => m
        .Field(f => f.VariableName)
        .Query("SAMPLE QUERY")
        .Fuzziness(Fuzziness.EditDistance(5))
    )
));
cegprakash
fuente
¿Qué biblioteca estás usando? Se necesita más información para que esto sea útil.
apuesta el
0

Aquí puede tener un POC de golang para calcular las distancias entre las palabras dadas. Puede sintonizar minDistancey differencepara otros ámbitos.

Área de juegos: https://play.golang.org/p/NtrBzLdC3rE

package main

import (
    "errors"
    "fmt"
    "log"
    "math"
    "strings"
)

var data string = `THE RED COW JUMPED OVER THE GREEN CHICKEN-THE RED COW JUMPED OVER THE RED COW-THE RED FOX JUMPED OVER THE BROWN COW`

const minDistance float64 = 2
const difference float64 = 1

type word struct {
    data    string
    letters map[rune]int
}

type words struct {
    words []word
}

// Print prettify the data present in word
func (w word) Print() {
    var (
        lenght int
        c      int
        i      int
        key    rune
    )
    fmt.Printf("Data: %s\n", w.data)
    lenght = len(w.letters) - 1
    c = 0
    for key, i = range w.letters {
        fmt.Printf("%s:%d", string(key), i)
        if c != lenght {
            fmt.Printf(" | ")
        }
        c++
    }
    fmt.Printf("\n")
}

func (ws words) fuzzySearch(data string) ([]word, error) {
    var (
        w      word
        err    error
        founds []word
    )
    w, err = initWord(data)
    if err != nil {
        log.Printf("Errors: %s\n", err.Error())
        return nil, err
    }
    // Iterating all the words
    for i := range ws.words {
        letters := ws.words[i].letters
        //
        var similar float64 = 0
        // Iterating the letters of the input data
        for key := range w.letters {
            if val, ok := letters[key]; ok {
                if math.Abs(float64(val-w.letters[key])) <= minDistance {
                    similar += float64(val)
                }
            }
        }

        lenSimilarity := math.Abs(similar - float64(len(data)-strings.Count(data, " ")))
        log.Printf("Comparing %s with %s i've found %f similar letter, with weight %f", data, ws.words[i].data, similar, lenSimilarity)
        if lenSimilarity <= difference {
            founds = append(founds, ws.words[i])
        }
    }

    if len(founds) == 0 {
        return nil, errors.New("no similar found for data: " + data)
    }

    return founds, nil
}

func initWords(data []string) []word {
    var (
        err   error
        words []word
        word  word
    )
    for i := range data {
        word, err = initWord(data[i])
        if err != nil {
            log.Printf("Error in index [%d] for data: %s", i, data[i])
        } else {
            words = append(words, word)
        }
    }
    return words

}

func initWord(data string) (word, error) {
    var word word

    word.data = data
    word.letters = make(map[rune]int)
    for _, r := range data {
        if r != 32 { // avoid to save the whitespace
            word.letters[r]++
        }

    }
    return word, nil
}
func main() {
    var ws words
    words := initWords(strings.Split(data, "-"))
    for i := range words {
        words[i].Print()
    }
    ws.words = words

    solution, _ := ws.fuzzySearch("THE BROWN FOX JUMPED OVER THE RED COW")
    fmt.Println("Possible solutions: ", solution)

}
alessiosavi
fuente