algorithm - fuzzy search npm
Algoritmos para cadenas de "combinación difusa" (6)
De hecho, estoy construyendo algo similar a los complementos Command-T y ctrlp de Vim para Emacs, solo por diversión. Acabo de tener una discusión productiva con algunos compañeros de trabajo inteligentes sobre las formas de hacer esto de la manera más eficiente. El objetivo es reducir el número de operaciones necesarias para eliminar archivos que no coinciden. Entonces creamos un mapa anidado, donde en el nivel superior cada clave es un personaje que aparece en algún lugar del conjunto de búsqueda, mapeando los índices de todas las cadenas en el conjunto de búsqueda. Cada uno de esos índices se correlaciona con una lista de compensaciones de caracteres en la que ese personaje en particular aparece en la cadena de búsqueda.
En pseudo código, para las cadenas:
- controlador
- modelo
- ver
Construiríamos un mapa como este:
{
"c" => {
0 => [0]
},
"o" => {
0 => [1, 5],
1 => [1]
},
"n" => {
0 => [2]
},
"t" => {
0 => [3]
},
"r" => {
0 => [4, 9]
},
"l" => {
0 => [6, 7],
1 => [4]
},
"e" => {
0 => [9],
1 => [3],
2 => [2]
},
"m" => {
1 => [0]
},
"d" => {
1 => [2]
},
"v" => {
2 => [0]
},
"i" => {
2 => [1]
},
"w" => {
2 => [3]
}
}
Entonces ahora tienes un mapeo como este:
{
character-1 => {
word-index-1 => [occurrence-1, occurrence-2, occurrence-n, ...],
word-index-n => [ ... ],
...
},
character-n => {
...
},
...
}
Ahora buscando la cadena "oe":
- Inicialice un nuevo mapa donde las claves serán los índices de las cadenas que coinciden y los valores que el desplazamiento ha leído hasta ese momento.
- Consuma el primer carácter de la cadena de búsqueda "o" y búsquelo en la tabla de búsqueda.
- Como las cadenas en los índices 0 y 1 coinciden con la "o", colócalas en el mapa
{0 => 1, 1 => 1}. - Ahora la búsqueda consume el siguiente carácter en la cadena de entrada, "e" y lo sube en la tabla.
- Aquí coinciden 3 cadenas, pero sabemos que solo nos importan las cadenas 0 y 1.
- Compruebe si hay desplazamientos> los desplazamientos actuales. De lo contrario, elimine los elementos de nuestro mapa; de lo contrario, actualice el desplazamiento:
{0 => 9, 1 => 3}.
Ahora, al observar las claves en nuestro mapa que hemos acumulado, sabemos qué cadenas coinciden con la búsqueda difusa.
Idealmente, si la búsqueda se realiza a medida que el usuario escribe, podrá hacer un seguimiento del hash de resultados acumulado y volver a pasarlo a su función de búsqueda. Creo que esto será mucho más rápido que repetir todas las cadenas de búsqueda y realizar una búsqueda de comodín completa en cada una.
Lo interesante de esto es que también puedes almacenar eficientemente la Distancia de Levenstein junto con cada coincidencia, asumiendo que solo te importan las inserciones, no las sustituciones o eliminaciones. Aunque tal vez no sea difícil agregar esa lógica también.
Por coincidencia aproximada no me refiero a cadenas similares por distancia Levenshtein o algo similar, sino por la forma en que se usa en TextMate / Ido / Icicles: dada una lista de cadenas, encuentre aquellas que incluyan todos los caracteres en la cadena de búsqueda, pero posiblemente con otras personajes entre, prefiriendo el mejor ajuste.
Dos algoritmos que he encontrado hasta ahora:
Finalmente entendí lo que estabas buscando. El problema es interesante; sin embargo, al observar los 2 algoritmos que encontraste parece que las personas tienen opiniones muy diferentes sobre las especificaciones;)
Creo que sería útil exponer el problema y los requisitos más claramente.
Problema :
Estamos buscando una forma de acelerar la escritura al permitir que los usuarios escriban solo unas pocas letras de la palabra clave que realmente intentaron y les propongan una lista para seleccionar.
- Se espera que todas las letras de la entrada estén en la palabra clave
- Se espera que las letras en la entrada estén en el mismo orden en la palabra clave
- La lista de palabras clave devuelta debe presentarse en un orden consistente (reproducible)
- El algoritmo debe ser insensible a mayúsculas y minúsculas
Análisis :
Los dos primeros requisitos se pueden resumir así: para un axg entrada buscamos palabras que coincidan con esta expresión regular [^a]*a[^x]*x[^g]*g.*
El tercer requisito es deliberadamente suelto. El orden en que deben aparecer las palabras en la lista debe ser coherente ... sin embargo, es difícil adivinar si un enfoque de puntuación sería mejor que el orden alfabético. Si la lista es extremadamente larga, entonces un enfoque de puntuación podría ser mejor, sin embargo, para la lista breve es más fácil para el ojo buscar un elemento determinado en una lista ordenada de manera obvia.
Además, el orden alfabético tiene la ventaja de la consistencia durante el tipeo: es decir, agregar una letra no reordena por completo la lista (es dolorosa para el ojo y el cerebro), simplemente filtra los elementos que ya no coinciden.
No hay precisión sobre el manejo de caracteres Unicode, por ejemplo, es similar a a u otro personaje en total? Como no conozco ningún idioma que utilice actualmente dichos caracteres en sus palabras clave, lo dejaré pasar por el momento.
Mi solución:
Para cualquier entrada, construiría la expresión regular expresada anteriormente. Es adecuado para Python porque el lenguaje ya presenta una coincidencia insensible a mayúsculas y minúsculas.
Luego, coincidiría con mi lista (ordenada alfabéticamente) de palabras clave y la publicaría de manera filtrada.
En pseudo-código:
WORDS = [''Bar'', ''Foo'', ''FooBar'', ''Other'']
def GetList(input, words = WORDS):
expr = [''[^'' + i + '']*'' + i for i in input]
return [w for w in words if re.match(expr, w, re.IGNORECASE)]
Podría haber usado un trazador de líneas, pero pensé que oscurecería el código;)
Esta solución funciona muy bien para situaciones incrementales (es decir, cuando coincide con el tipo de usuario y así mantener la reconstrucción) porque cuando el usuario agrega un carácter, simplemente puede volver a filtrar el resultado que acaba de calcular. Así:
- O bien hay pocos caracteres, por lo tanto, la coincidencia es rápida y la longitud de la lista no importa mucho
- O bien hay un montón de personajes, y esto significa que estamos filtrando una lista corta, por lo tanto, no importa demasiado si la coincidencia lleva un poco más de tiempo sabio
También debería tener en cuenta que esta expresión regular no implica retroceso y, por lo tanto, es bastante eficiente. También podría modelarse como una máquina de estado simple.
Los algoritmos de Levenshtein ''Edit Distance'' definitivamente funcionarán en lo que estás tratando de hacer: te darán una medida de qué tan cerca dos palabras o direcciones o números de teléfono, salmos, monólogos y artículos académicos coinciden entre sí, permitiéndote clasificar el resultados y elige la mejor coincidencia.
Una aplicación más ligera es contar las subcadenas comunes: no es tan buena como Levenshtein, pero proporciona resultados útiles y se ejecuta rápidamente en idiomas lentos que tienen acceso a funciones rápidas de ''InString''.
Publiqué Excel ''Fuzzy Lookup'' en Excellerando hace unos años, usando la función ''FuzzyMatchScore'' que, hasta donde sé, es exactamente lo que necesita:
http://excellerando.blogspot.com/2010/03/vlookup-with-fuzzy-matching-to-get.html
Es, por supuesto, en Visual Basic para Aplicaciones. Proceda con precaución, crucifijos y ajo:
Public Function SumOfCommonStrings( _ ByVal s1 As String, _ ByVal s2 As String, _ Optional Compare As VBA.VbCompareMethod = vbTextCompare, _ Optional iScore As Integer = 0 _ ) As Integer Application.Volatile False '' N.Heffernan 06 June 2006 '' THIS CODE IS IN THE PUBLIC DOMAIN '' Function to measure how much of String 1 is made up of substrings found in String 2 '' This function uses a modified Longest Common String algorithm. '' Simple LCS algorithms are unduly sensitive to single-letter '' deletions/changes near the midpoint of the test words, eg: '' Wednesday is obviously closer to WedXesday on an edit-distance '' basis than it is to WednesXXX. So it would be better to score '' the ''Wed'' as well as the ''esday'' and add up the total matched '' Watch out for strings of differing lengths: '' '' SumOfCommonStrings("Wednesday", "WednesXXXday") '' '' This scores the same as: '' '' SumOfCommonStrings("Wednesday", "Wednesday") '' '' So make sure the calling function uses the length of the longest '' string when calculating the degree of similarity from this score. '' This is coded for clarity, not for performance. Dim arr() As Integer '' Scoring matrix Dim n As Integer '' length of s1 Dim m As Integer '' length of s2 Dim i As Integer '' start position in s1 Dim j As Integer '' start position in s2 Dim subs1 As String '' a substring of s1 Dim len1 As Integer '' length of subs1 Dim sBefore1 '' documented in the code Dim sBefore2 Dim sAfter1 Dim sAfter2 Dim s3 As String SumOfCommonStrings = iScore n = Len(s1) m = Len(s2) If s1 = s2 Then SumOfCommonStrings = n Exit Function End If If n = 0 Or m = 0 Then Exit Function End If ''s1 should always be the shorter of the two strings: If n > m Then s3 = s2 s2 = s1 s1 = s3 n = Len(s1) m = Len(s2) End If n = Len(s1) m = Len(s2) '' Special case: s1 is n exact substring of s2 If InStr(1, s2, s1, Compare) Then SumOfCommonStrings = n Exit Function End If For len1 = n To 1 Step -1 For i = 1 To n - len1 + 1 subs1 = Mid(s1, i, len1) j = 0 j = InStr(1, s2, subs1, Compare) If j > 0 Then '' We''ve found a matching substring... iScore = iScore + len1 '' Now clip out this substring from s1 and s2... '' And search the fragments before and after this excision: If i > 1 And j > 1 Then sBefore1 = left(s1, i - 1) sBefore2 = left(s2, j - 1) iScore = SumOfCommonStrings(sBefore1, _ sBefore2, _ Compare, _ iScore) End If If i + len1 < n And j + len1 < m Then sAfter1 = right(s1, n + 1 - i - len1) sAfter2 = right(s2, m + 1 - j - len1) iScore = SumOfCommonStrings(sAfter1, _ sAfter2, _ Compare, _ iScore) End If SumOfCommonStrings = iScore Exit Function End If Next Next End Function Private Function Minimum(ByVal a As Integer, _ ByVal b As Integer, _ ByVal c As Integer) As Integer Dim min As Integer min = a If b < min Then min = b End If If c < min Then min = c End If Minimum = min End Function
Recientemente tuve que resolver el mismo problema. Mi solución implica marcar cadenas con letras coincidentes consecutivamente y excluyendo cadenas que no contienen las letras escritas en orden.
He documentado el algoritmo en detalle aquí: http://blog.kazade.co.uk/2014/10/a-fuzzy-filename-matching-algorithm.html