uFuzzy
1.0.17
Una búsqueda difusa pequeña y eficiente que no apesta. ¿Este es mi peludito?. Hay muchos iguales, pero este es el mío.¹
uFuzzy es una biblioteca de búsqueda difusa diseñada para hacer coincidir una frase de búsqueda relativamente corta (aguja) con una lista grande de frases cortas a medianas (pajar). Podría describirse mejor como un String.includes() más indulgente. Las aplicaciones comunes incluyen filtrado de listas, autocompletar/sugerencias y búsquedas de títulos, nombres, descripciones, nombres de archivos y funciones.
En el modo MultiInsert predeterminado de uFuzzy, cada coincidencia debe contener todos los caracteres alfanuméricos de la aguja en la misma secuencia; en el modo SingleError , se toleran errores tipográficos únicos en cada término (distancia Damerau-Levenshtein = 1). Su API .search() puede encontrar eficientemente términos desordenados, admite múltiples exclusiones de subcadenas (por ejemplo, fruit -green -melon ) y términos exactos con caracteres que no son alfanum (por ejemplo, "C++" , "$100" , "#hashtag" ). Cuando se mantiene en la posición correcta , también puede comparar de manera eficiente múltiples propiedades de objetos.
Array.sort() que obtiene acceso a las estadísticas/contadores de cada partido. No hay una "puntuación" compuesta de caja negra que debamos entender.
uFuzzy está optimizado para el alfabeto latino/romano y se basa internamente en expresiones regulares no Unicode.
La compatibilidad con más idiomas funciona aumentando las expresiones regulares latinas integradas con caracteres adicionales o utilizando la variante {unicode: true} más lenta y universal. Una alternativa {alpha: "..."} más simple, pero menos flexible, reemplaza las partes AZ y az de las expresiones regulares latinas integradas con caracteres de su elección (las letras entre mayúsculas y minúsculas coincidirán automáticamente durante el reemplazo).
La función de utilidad uFuzzy.latinize() se puede utilizar para eliminar acentos/diacríticos comunes del pajar y la aguja antes de realizar la búsqueda.
// Latin (default)
let opts = { alpha : "a-z" } ;
// OR
let opts = {
// case-sensitive regexps
interSplit : "[^A-Za-z\d']+" ,
intraSplit : "[a-z][A-Z]" ,
intraBound : "[A-Za-z]\d|\d[A-Za-z]|[a-z][A-Z]" ,
// case-insensitive regexps
intraChars : "[a-z\d']" ,
intraContr : "'[a-z]{1,2}\b" ,
} ;
// Latin + Norwegian
let opts = { alpha : "a-zæøå" } ;
// OR
let opts = {
interSplit : "[^A-Za-zæøåÆØÅ\d']+" ,
intraSplit : "[a-zæøå][A-ZÆØÅ]" ,
intraBound : "[A-Za-zæøåÆØÅ]\d|\d[A-Za-zæøåÆØÅ]|[a-zæøå][A-ZÆØÅ]" ,
intraChars : "[a-zæøå\d']" ,
intraContr : "'[a-zæøå]{1,2}\b" ,
} ;
// Latin + Russian
let opts = { alpha : "a-zа-яё" } ;
// OR
let opts = {
interSplit : "[^A-Za-zА-ЯЁа-яё\d']+" ,
intraSplit : "[a-z][A-Z]|[а-яё][А-ЯЁ]" ,
intraBound : "[A-Za-zА-ЯЁа-яё]\d|\d[A-Za-zА-ЯЁа-яё]|[a-z][A-Z]|[а-яё][А-ЯЁ]" ,
intraChars : "[a-zа-яё\d']" ,
intraContr : "'[a-z]{1,2}\b" ,
} ;
// Unicode / universal (50%-75% slower)
let opts = {
unicode : true ,
interSplit : "[^\p{L}\d']+" ,
intraSplit : "\p{Ll}\p{Lu}" ,
intraBound : "\p{L}\d|\d\p{L}|\p{Ll}\p{Lu}" ,
intraChars : "[\p{L}\d']" ,
intraContr : "'\p{L}{1,2}\b" ,
} ;Actualmente, todas las búsquedas no distinguen entre mayúsculas y minúsculas; no es posible realizar una búsqueda que distinga entre mayúsculas y minúsculas.
NOTA: El archivo testdata.json es un conjunto de datos diverso de 162 000 cadenas/frases de 4 MB de tamaño, por lo que la primera carga puede ser lenta debido a la transferencia de red. Intente actualizar una vez que su navegador lo haya almacenado en caché.
Primero, uFuzzy de forma aislada para demostrar su rendimiento.
https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy&search=super%20ma
Ahora la misma página de comparación, iniciada con fuzzysort, QuickScore y Fuse.js:
https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=super%20ma
Aquí está la lista completa de bibliotecas, pero con un conjunto de datos reducido (solo hearthstone_750 , urls_and_titles_600 ) para evitar que su navegador falle:
https://leeoniya.github.io/uFuzzy/demos/compare.html?lists=hearthstone_750,urls_and_titles_600&search=moo
Respuestas:
Más: https://github.com/leeoniya/uFuzzy/issues
npm i @leeoniya/ufuzzy
const uFuzzy = require ( '@leeoniya/ufuzzy' ) ; < script src = "./dist/uFuzzy.iife.min.js" > < / script > let haystack = [
'puzzle' ,
'Super Awesome Thing (now with stuff!)' ,
'FileName.js' ,
'/feeding/the/catPic.jpg' ,
] ;
let needle = 'feed cat' ;
let opts = { } ;
let uf = new uFuzzy ( opts ) ;
// pre-filter
let idxs = uf . filter ( haystack , needle ) ;
// idxs can be null when the needle is non-searchable (has no alpha-numeric chars)
if ( idxs != null && idxs . length > 0 ) {
// sort/rank only when <= 1,000 items
let infoThresh = 1e3 ;
if ( idxs . length <= infoThresh ) {
let info = uf . info ( idxs , haystack , needle ) ;
// order is a double-indirection array (a re-order of the passed-in idxs)
// this allows corresponding info to be grabbed directly by idx, if needed
let order = uf . sort ( info , haystack , needle ) ;
// render post-filtered & ordered matches
for ( let i = 0 ; i < order . length ; i ++ ) {
// using info.idx here instead of idxs because uf.info() may have
// further reduced the initial idxs based on prefix/suffix rules
console . log ( haystack [ info . idx [ order [ i ] ] ] ) ;
}
}
else {
// render pre-filtered but unordered matches
for ( let i = 0 ; i < idxs . length ; i ++ ) {
console . log ( haystack [ idxs [ i ] ] ) ;
}
}
} uFuzzy proporciona un contenedor uf.search(haystack, needle, outOfOrder = 0, infoThresh = 1e3) => [idxs, info, order] que combina los pasos de filter , info y sort anteriores. Este método también implementa una lógica eficiente para hacer coincidir términos de búsqueda desordenados y admite múltiples exclusiones de subcadenas, por ejemplo, fruit -green -melon .
Obtenga sus coincidencias ordenadas primero:
let haystack = [
'foo' ,
'bar' ,
'cowbaz' ,
] ;
let needle = 'ba' ;
let u = new uFuzzy ( ) ;
let idxs = u . filter ( haystack , needle ) ;
let info = u . info ( idxs , haystack , needle ) ;
let order = u . sort ( info , haystack , needle ) ; Resaltador HTML interno básico ( <mark> -rangos envueltos):
let innerHTML = '' ;
for ( let i = 0 ; i < order . length ; i ++ ) {
let infoIdx = order [ i ] ;
innerHTML += uFuzzy . highlight (
haystack [ info . idx [ infoIdx ] ] ,
info . ranges [ infoIdx ] ,
) + '<br>' ;
}
console . log ( innerHTML ) ; Resaltador InnerHTML con función de marcado personalizado ( <b> -rangos envueltos):
let innerHTML = '' ;
const mark = ( part , matched ) => matched ? '<b>' + part + '</b>' : part ;
for ( let i = 0 ; i < order . length ; i ++ ) {
let infoIdx = order [ i ] ;
innerHTML += uFuzzy . highlight (
haystack [ info . idx [ infoIdx ] ] ,
info . ranges [ infoIdx ] ,
mark ,
) + '<br>' ;
}
console . log ( innerHTML ) ;Resaltador de elementos DOM/JSX con marcado personalizado y funciones de adición:
let domElems = [ ] ;
const mark = ( part , matched ) => {
let el = matched ? document . createElement ( 'mark' ) : document . createElement ( 'span' ) ;
el . textContent = part ;
return el ;
} ;
const append = ( accum , part ) => { accum . push ( part ) ; } ;
for ( let i = 0 ; i < order . length ; i ++ ) {
let infoIdx = order [ i ] ;
let matchEl = document . createElement ( 'div' ) ;
let parts = uFuzzy . highlight (
haystack [ info . idx [ infoIdx ] ] ,
info . ranges [ infoIdx ] ,
mark ,
[ ] ,
append ,
) ;
matchEl . append ( ... parts ) ;
domElems . push ( matchEl ) ;
}
document . getElementById ( 'matches' ) . append ( ... domElems ) ;uFuzzy tiene dos modos operativos que se diferencian en la estrategia de coincidencia:
example - exactoexamplle : inserción única (suma)exemple : sustitución única (reemplazo)exmaple : transposición única (intercambio)exmple : eliminación única (omisión)xamp - parcialxmap - parcial con transposiciónHay 3 fases para una búsqueda:
haystack con una RegExp rápida compilada desde su needle sin realizar operaciones adicionales. Devuelve una serie de índices coincidentes en el orden original.needle en dos RegExps más caras que pueden dividir cada coincidencia. Por lo tanto, se debe ejecutar en un subconjunto reducido del pajar, generalmente devuelto por la fase de Filtrado. La demostración de uFuzzy está limitada a <= 1000 elementos filtrados, antes de continuar con esta fase.Array.sort() para determinar el orden del resultado final, utilizando el objeto info devuelto de la fase anterior. Se puede proporcionar una función de clasificación personalizada a través de una opción de uFuzzy: {sort: (info, haystack, needle) => idxsOrder} .Un archivo uFuzzy.d.ts de 200 LoC generosamente comentado.
Las opciones con un prefijo inter se aplican a las asignaciones entre términos de búsqueda, mientras que aquellas con un prefijo intra se aplican a las asignaciones dentro de cada término de búsqueda.
| Opción | Descripción | Por defecto | Ejemplos |
|---|---|---|---|
intraMode | Cómo se debe realizar la comparación de términos | 0 | 0 Multiinserción1 error únicoVea cómo funciona |
intraIns | Número máximo de caracteres adicionales permitidos entre cada carácter dentro de un término | Coincide con el valor de intraMode (ya sea 0 o 1 ) | Buscando "gato"...0 puede coincidir: cat , s cat , cat ch, va cat e1 también coincide con: c a r t , c a p t e r, p a r a d |
interIns | Número máximo de caracteres adicionales permitidos entre términos | Infinity | Buscando "dónde está"...Infinity puede coincidir: dónde está , dónde tiene bla, w es dom5 no pueden igualar: ¿dónde tiene la sabiduría bla? |
intraSubintraTrnintraDel | Para intraMode: 1 solamente,Tipos de errores a tolerar dentro de los términos | Coincide con el valor de intraMode (ya sea 0 o 1 ) | 0 Sí1 si |
intraChars | expresión regular parcial para inserción permitida caracteres entre cada carácter dentro de un término | [azd'] | [azd] solo coincide con caracteres alfanuméricos (no distingue entre mayúsculas y minúsculas)[w-] coincidiría con caracteres alfanuméricos, subrayados y guiones |
intraFilt | Devolución de llamada para excluir resultados según términos y coincidencias | (term, match, index) => true | Haz lo tuyo, tal vez... - Umbral de diferencia de longitud - distancia de Levenshtein - Término compensado o contenido |
interChars | expresión regular parcial para caracteres permitidos entre términos | . | . coincide con todos los caracteres[^azd] solo coincidiría con espacios en blanco y puntuación |
interLft | Determina el límite izquierdo del término permitido | 0 | Buscando "manía"...0 cualquiera - en cualquier lugar: ro mania n1 suelto: espacios en blanco, puntuación, alfa-num, transiciones de cambio de mayúsculas y minúsculas: Track Mania , mania c2 estricto - espacios en blanco, puntuación: maníacamente |
interRgt | Determina el límite derecho del término permitido | 0 | Buscando "manía"...0 cualquiera - en cualquier lugar: ro mania n1 suelto: espacios en blanco, puntuación, alfanumérico, transiciones de cambio de mayúsculas y minúsculas: Mania Star2 estricto - espacios en blanco, puntuación: mania _foo |
sort | Función de clasificación de resultados personalizada | (info, haystack, needle) => idxsOrder | Valor predeterminado: ordenación de búsqueda, prioriza coincidencias de términos completos y densidad de caracteres Demostración: clasificación anticipada, prioriza el desplazamiento inicial y la longitud coincidente |
Esta evaluación es extremadamente limitada y, por supuesto, está sesgada hacia mis casos de uso, mi corpus de texto y mi completa experiencia en el manejo de mi propia biblioteca. Es muy probable que no esté aprovechando al máximo alguna característica de otras bibliotecas que pueda mejorar significativamente los resultados en algún eje; Agradezco las relaciones públicas de mejora de cualquier persona con un conocimiento de la biblioteca más profundo que el que ofrece mi apresurado vistazo de 10 minutos a cualquier ejemplo de "Uso básico" y documento README.
Lata de gusanos #1.
Antes de discutir el rendimiento, hablemos de la calidad de la búsqueda, porque la velocidad es irrelevante cuando los resultados son una extraña mezcla de "¡Oh, sí!" y "¿Qué carajo?".
La calidad de la búsqueda es muy subjetiva. Lo que constituye una buena coincidencia principal en un caso de "escritura anticipada/sugerencia automática" puede ser una mala coincidencia en un escenario de "búsqueda/encontrar todo". Algunas soluciones se optimizan para lo último, otras para lo primero. Es común encontrar botones que distorsionan los resultados en cualquier dirección, pero a menudo son imperfectos y son poco más que un sustituto para producir una única "puntuación" compuesta de una coincidencia.
ACTUALIZACIÓN (2024): La siguiente crítica sobre coincidencias extrañas solo es cierta para la configuración predeterminada de Fuse.js. Contrariamente a la intuición, configurar ignoreFieldNorm: true mejoró considerablemente los resultados, pero el orden de las coincidencias de alta calidad sigue siendo deficiente.
Echemos un vistazo a algunas coincidencias producidas por la biblioteca de búsqueda difusa más popular, Fuse.js y algunas otras para las cuales se implementa el resaltado de coincidencias en la demostración.
Al buscar el término parcial "twili" , vemos que estos resultados aparecen encima de numerosos resultados obvios de "crepúsculo" :
https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=twili
Estas malas coincidencias no sólo son aisladas, sino que en realidad tienen una clasificación más alta que las subcadenas literales.
Al finalizar el término de búsqueda con "crepúsculo" , aún obtiene resultados extraños más altos:
https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=twilight
Algunos motores funcionan mejor con coincidencias parciales de prefijos, a expensas de un mayor costo de inicio/indexación:
https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,FlexSearch,match-sorter,MiniSearch&search=twili
Aquí, match-sorter arroja 1384 resultados, pero solo los primeros 40 son relevantes. ¿Cómo sabemos dónde está el límite?
Lata de gusanos #2.
Todos los puntos de referencia apestan, pero este podría apestar más que otros.
Aún así, algo es mejor que un despido YMMV/hágalo usted mismo ondulado a mano y ciertamente mejor que nada.
Ambiente
| Fecha | 2023-10 |
|---|---|
| Hardware | Procesador: Ryzen 7 PRO 5850U (1,9 GHz, 7 nm, 15 W TDP) RAM: 48GB SSD: Samsung SSD 980 PRO 1TB (NVMe) |
| SO | EndeavourOS (Arco Linux) v6.5.4-arch2-1 x86_64 |
| Cromo | v117.0.5938.132 |
libs al nombre de la biblioteca deseada: https://leeoniya.github.io/uFuzzy/demos/compare.html?bench&libs=uFuzzybench para evitar la evaluación comparativa del DOM.test , chest , super ma , mania , puzz , prom rem stor , twil . Para evaluar los resultados de cada biblioteca, o comparar varias, simplemente visite la misma página con más libs y sin bench : https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore ,Fusible&búsqueda=super%20ma.
Hay varias métricas evaluadas:
| librería | estrellas | Tamaño (mín.) | inicio | Buscar (x86) | Montón (pico) | Retenido | GC |
|---|---|---|---|---|---|---|---|
| uFuzzy (intenta) | ★ 2.3k | 7,6 KB | 0,5 ms | 434ms | 28,4MB | 7,4MB | 18ms |
| uFuzzy (intenta) (almacenamiento en caché de prefijo externo) | 210ms | 27,8MB | 7,4MB | 18ms | |||
| uFuzzy (intenta) (fuera de orden, más borroso) | 545ms | 29,5MB | 7,4MB | 18ms | |||
| uFuzzy (intenta) (fuera de orden, más borroso, SingleError) | 508ms | 30.0MB | 7,4MB | 18ms | |||
| ------- | |||||||
| Fuse.js (probar) | ★ 16,6k | 24,2 KB | 31ms | 33875ms | 245 MB | 13,9MB | 25 ms |
| FlexSearch (ligero) (probar) | ★ 10,7k | 6,2 KB | 3210 ms | 83ms | 670MB | 316 MB | 553ms |
| Lunr.js (probar) | ★ 8,7k | 29,4 KB | 1704ms | 996ms | 380MB | 123MB | 166ms |
| Orama (anteriormente Lyra) (intenta) | ★ 6.4k | 41,5 KB | 2650ms | 225ms | 313 MB | 192MB | 180ms |
| Minibúsqueda (probar) | ★ 3.4k | 29,1 KB | 504ms | 1453ms | 438MB | 67MB | 105ms |
| clasificador de coincidencias (intentar) | ★ 3.4k | 7.3KB | 0,1 ms | 6245ms | 71 MB | 7,3MB | 12 ms |
| clasificación difusa (intentar) | ★ 3.4k | 6,2 KB | 50 ms | 1321ms | 175MB | 84MB | 63ms |
| Wade (intenta) | ★ 3k | 4 KB | 781ms | 194ms | 438MB | 42MB | 130ms |
| búsqueda difusa (intenta) | ★ 2.7k | 0.2KB | 0,1 ms | 529ms | 26,2MB | 7,3MB | 18ms |
| js-buscar (probar) | ★ 2.1k | 17,1 KB | 5620ms | 1190ms | 1740MB | 734MB | 2600ms |
| Elasticlunr.js (probar) | ★ 2k | 18,1 KB | 933ms | 1330ms | 196MB | 70MB | 135ms |
| Fuzzyset (inténtalo) | ★ 1.4k | 2,8 KB | 2962ms | 606ms | 654MB | 238MB | 239ms |
| índice de búsqueda (probar) | ★ 1.4k | 168KB | RangeError: se excedió el tamaño máximo de la pila de llamadas | ||||
| tamiz.js (probar) | ★ 1.1k | 7,5 KB | 3ms | 1070ms | 46,2MB | 10,6MB | 18ms |
| fzf-para-js (intentar) | ★ 831 | 15.4KB | 50 ms | 6290ms | 153MB | 25MB | 18ms |
| borroso (intenta) | ★ 819 | 1.4KB | 0,1 ms | 5427ms | 72MB | 7,3MB | 14ms |
| rápido y difuso (intenta) | ★ 346 | 18,2 KB | 790 ms | 19266ms | 550 MB | 165MB | 140ms |
| ArtículosJS (probar) | ★ 305 | 109KB | 2400ms | 11304ms | 320MB | 88MB | 163ms |
| LiquidMetal (probar) | ★ 292 | 4.2KB | (chocar) | ||||
| Búsqueda difusa (probar) | ★ 209 | 3,5 KB | 2 ms | 3948ms | 84MB | 10,5MB | 18ms |
| FuzzySearch2 (probar) | ★ 186 | 19.4KB | 93ms | 4189ms | 117MB | 40,3MB | 40 ms |
| QuickScore (probar) | ★ 153 | 9.5KB | 10 ms | 6915ms | 133MB | 12,1MB | 18ms |
| ndx (intenta) | ★ 142 | 2,9 KB | 300 ms | 581ms | 308MB | 137MB | 262ms |
| fzy (intenta) | ★ 133 | 1,5 KB | 0,1 ms | 3932ms | 34MB | 7,3MB | 10 ms |
| herramientas difusas (probar) | ★ 13 | 3 KB | 0,1 ms | 5138ms | 164MB | 7,5MB | 18ms |
| fuzzyMatch (probar) | ★ 0 | 1 KB | 0,1 ms | 2415ms | 83,5MB | 7,3MB | 13ms |
