¿Cómo se diseña el algoritmo de búsqueda difusa en Sublime Text? ¿Cómo diseñarías algo similar?

También es muy interesante observar el sistema de puntuación utilizado por este algoritmo:

Podemos ver aquí que la distancia entre golpes reduce su puntaje y la primera letra de cada palabra tiene un puntaje adicional (tal vez aún más para la primera letra de toda la cadena).

La coincidencia en cadena tiene un puntaje adicional para que las palabras completas coincidan mejor

Otras pequeñas cosas diferentes afectan la puntuación, intentará hacer coincidir sus resultados con letras invertidas (reduciendo la puntuación un poco también) para que sea tolerante a fallas.

También intentará recursivamente hacer coincidir las partes más profundas de la cadena y asegurarse de devolver el mejor resultado de puntuación para la cadena y no la primera coincidencia.

como :

no coincidió así, lo que habría resultado en una puntuación más baja:

Agregue a eso el almacenamiento de sus opciones seleccionadas para saltar el cursor al resultado más común para esta búsqueda y tendrá un algoritmo bastante bueno 🙂

Hice una biblioteca que proporciona resultados similares al texto sublime, que no es el caso de ningún otro que encontré (sistema de puntaje medio evaluado, sin recursividad, etc.)

fuzzi Debería escribir un documento para él y publicarlo en github pero en realidad no está listo para lanzar

Es una variante del problema de subsecuencia común más largo

No sé cómo se implementa, porque no he visto el código fuente, pero una de las ideas que usaría es primero preprocesar la lista de cadenas de manera que sea posible responder a esas consultas en tiempo sublineal.

Un truco particular que conozco es calcular un “histograma” para cada cadena, que para cada letra indica el número de apariciones de esta letra en esta cadena. Por ejemplo para “json.js” da j: 2, n: 1, o: 1, s: 2,.: 1.
También puede crear un histograma de su consulta.
Claramente, el histograma de la consulta debe ser “más pequeño” que el histograma de cualquier resultado, por lo que puede crear un índice de una manera que permita omitir rápidamente todas las cadenas que son “demasiado pequeñas”.

No estoy diciendo, sé cómo hacerlo, pero tengo algunas ideas.
Por ejemplo, podría para cada letra y cada número de ocurrencias crear una lista de todas las cadenas que contienen esta letra en particular con tantas ocurrencias. Esto podría significar que nuestra cadena “json.js” se puede encontrar en 5 listas: lista para j2, lista para n1, etc.
Ahora, cuando ingresa una consulta, crea un histograma de la consulta.
Por ejemplo, si escribo “jjs”, el histograma es j: 2, s: 1.
Ahora, tengo dos opciones: atravesar una lista para j2 o una lista para s1. En realidad, en el primer caso, también tengo que atravesar j3, j4, j5..etc (lo mismo ocurre con s2, s3, …).
Dadas las longitudes de todas las listas, puede determinar rápidamente cuál de estas opciones es más rápida.
Digamos, hay menos cadenas con al menos 2j, luego hay palabras con al menos una ‘s’, entonces debe usar la primera opción.

Ahora, este método usó solo una letra (ya sea j o s) para acotar la búsqueda.
Puede crear listas similares para todas las combinaciones de letras de 256 × 256, con la esperanza de que las listas sean aún más cortas. Una forma prometedora de optimizarlo es dejar solo estas combinaciones para las cuales hay una ganancia significativa (digamos 50%). Por ejemplo, si hay 1000 cadenas con dos ‘j’, 2000 cadenas con ‘s’, pero solo ‘254’ cadenas con dos ‘j’ y una ‘s’, entonces podría valer la pena crear una lista separada para este caso. Para hacerlo más serio, consideraría no solo las estadísticas del conjunto de datos sino también las consultas: ¿qué posibilidades hay de que el usuario escriba “js”?

Todo esto hasta ahora se concentró en los histogramas, que obviamente se pierden una información importante: el orden de las letras.
¿Quizás haya una ganancia significativa al tratar “jjs” y “jsj” como dos consultas separadas, ya que la secuencia posterior es menos probable?

Así que al final sugeriría este algoritmo para construir un índice: comience por construir índices para letras individuales. Es decir, construir un mapa en el que una sola letra es una clave, y una lista de cadenas que contienen esta letra es un valor. Luego, recursivamente, intente extender cada clave con una letra más y ver si esto conduce a una reducción del 50% de la longitud de la lista. Si es así, agregue la nueva clave y la lista al índice.
De esta manera, el tamaño del índice está limitado (ya que en cada nivel las listas son un 50% más cortas que en el anterior), y la velocidad es probablemente lo suficientemente buena.

Obviamente, esto es heurístico, y el “50%” es una regla inventada. Podría intentar el 20% o tratar de “dar una oportunidad” a una clave incluso si no redujo el tamaño significativamente, porque tal vez después de agregar una letra más se reducirá en un 75% o algo así.

¡Tengo curiosidad por saber cuál es el algoritmo real también!

Una coincidencia de subsecuencia lo acercará bastante, pero, como anon observa a continuación, la búsqueda de Sublime parece tener algunas peculiaridades extrañas relacionadas con la forma en que favorece los inicialismos. Cuando implementé mi algoritmo de búsqueda de autocompletado, no pensé en nada que pudiera explicar esas peculiaridades. Tendré que admitir, entonces, que mi implementación, a pesar de responder perfectamente a las listas de resultados de varios cientos de entradas (no la he probado con más), probablemente carece de ciertas optimizaciones de rendimiento relacionadas con la preferencia de intialismo. Sin embargo, creo que lo compensa con un esmalte adicional. Al ignorar (por ahora, al menos) las restricciones con las que uno tendría que trabajar para escalar conjuntos de datos más allá de 1000 elementos, podemos agregar prácticamente cualquier característica que queramos a CleverMatcher con un mínimo de fricción y, al menos para conjuntos de datos menores de 1000, podemos proporcionar mejores resultados que Sublime.

He integrado mi solución en una interfaz de usuario robusta de autocompletado para aplicaciones web aquí: makoConstruct / shac.js. Las solicitudes de funciones son bienvenidas.
El algoritmo de coincidencia subyacente está aquí: makoConstruct / CleverMatcher. Y puede usarlo en sus propios menús desplegables de autocompletado si no le gusta shac.js, aunque me resulta difícil imaginar lo que alguien querría hacer aquí que no puede hacer con el shac.js correcto configuración.

Ah, y lo siento, no es javascript, lo hice en coffeescript. Sin embargo, la diferencia es pequeña. Para un desarrollador de JavaScript, si puede comprender cómo f = (a)-> a + 1 , significa que f(1) == 2 , el resto será obvio.

Creo que la coincidencia de trigram es la mejor manera de usar algoritmos difusos para la corrección ortográfica. Utilizamos este método para el portal b2b grande, donde la funcionalidad de búsqueda adecuada es obligatoria. Puede leer acerca de nuestro trabajo en la corrección ortográfica automática utilizando el algoritmo de coincidencia de cadenas de trigrama. Estamos usando PHP5, debido a Sphinx Search Engine.

Encontré una biblioteca JS de búsqueda difusa. Fue inspirado por una biblioteca en GO lang.
https://github.com/renstrom/fuzz …

No podemos conocer el algoritmo de sublime-text porque tiene un origen cercano.

Pero dado que otro editor de texto de código abierto como Emacs ha implementado un algoritmo similar y es 200% más rápido que el texto sublime , tal vez podamos investigar Emacs. Ver abo-abo / swiper (ivy.el). Es poco probable que la implementación de Sublime Text sea diferente.

Es realmente simple, suponga que ya tiene la lista de archivos en el proyecto, podemos construir la expresión regular desde el cuadro de entrada (marque la función “ivy – regex-fuzzy” y “ivy-sort”), luego usamos la expresión regular para filtrar la lista de archivos. La correspondencia eficiente de expresiones regulares está escrita en C / C ++, hay varias bibliotecas de expresiones regulares C / C ++ que podemos usar (por ejemplo, PCRE – Expresiones regulares compatibles con Perl).

Ahora, ¿cómo hacerlo en javascript? Use la propia expresión regular de javascript.

Una cosa que noté sobre la coincidencia de subcadena de sublime es que es exigente sobre qué partes de los resultados coincidentes se tienen en cuenta. Por ejemplo, dado un resultado de coincidencia “AbcDefHijKlmNop”, “adhkn” coincidirá, pero “bcefi” no. Esto probablemente sugiere algunas de las optimizaciones subyacentes.