uFuzzy
1.0.17
Une petite recherche floue efficace qui ne craint pas. C'est mon flou ?. Il y en a beaucoup comme ça, mais celui-ci est le mien.¹
uFuzzy est une bibliothèque de recherche floue conçue pour faire correspondre une expression de recherche relativement courte (aiguille) à une grande liste d'expressions courtes à moyennes (botte de foin). Il pourrait être mieux décrit comme un String.includes() plus indulgent. Les applications courantes incluent le filtrage de listes, la saisie semi-automatique/suggérée et la recherche de titres, de noms, de descriptions, de noms de fichiers et de fonctions.
Dans le mode MultiInsert par défaut d'uFuzzy, chaque correspondance doit contenir tous les caractères alphanumériques de l'aiguille dans la même séquence ; en mode SingleError , des fautes de frappe uniques sont tolérées dans chaque terme (distance Damerau – Levenshtein = 1). Son API .search() peut faire correspondre efficacement les termes dans le désordre, prend en charge plusieurs exclusions de sous-chaînes (par exemple fruit -green -melon ) et des termes exacts avec des caractères non alphanumériques (par exemple "C++" , "$100" , "#hashtag" ). Lorsqu'il est tenu correctement , il peut également correspondre efficacement à plusieurs propriétés d'objet.
Array.sort() qui donne accès aux statistiques/compteurs de chaque match. Il n’y a pas de « score » composite en boîte noire à comprendre.
uFuzzy est optimisé pour l'alphabet latin/romain et s'appuie en interne sur des expressions régulières non Unicode.
La prise en charge d'un plus grand nombre de langues fonctionne en augmentant les expressions rationnelles latines intégrées avec des caractères supplémentaires ou en utilisant la variante {unicode: true} plus lente et universelle. Une alternative {alpha: "..."} plus simple, mais moins flexible, remplace les parties AZ et az des expressions rationnelles latines intégrées par les caractères de votre choix (la casse des lettres sera automatiquement adaptée lors du remplacement).
La fonction util uFuzzy.latinize() peut être utilisée pour supprimer les accents/diacritiques courants de la botte de foin et de l'aiguille avant la recherche.
// 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" ,
} ;Toutes les recherches ne sont actuellement pas sensibles à la casse ; il n'est pas possible d'effectuer une recherche sensible à la casse.
REMARQUE : Le fichier testdata.json est un ensemble de données diversifié de 162 000 chaînes/expressions d'une taille de 4 Mo, le premier chargement peut donc être lent en raison du transfert réseau. Essayez d'actualiser une fois qu'il a été mis en cache par votre navigateur.
Tout d’abord, uFuzzy isolément pour démontrer ses performances.
https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy&search=super%20ma
Maintenant la même page de comparaison, démarrée avec fuzzysort, QuickScore et Fuse.js :
https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=super%20ma
Voici la liste complète des bibliothèques mais avec un ensemble de données réduit (juste hearthstone_750 , urls_and_titles_600 ) pour éviter de planter votre navigateur :
https://leeoniya.github.io/uFuzzy/demos/compare.html?lists=hearthstone_750,urls_and_titles_600&search=moo
Réponses :
Sinon : 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 fournit un uf.search(haystack, needle, outOfOrder = 0, infoThresh = 1e3) => [idxs, info, order] qui combine les étapes filter , info , sort ci-dessus. Cette méthode implémente également une logique efficace pour faire correspondre les termes de recherche dans le désordre et prend en charge plusieurs exclusions de sous-chaînes, par exemple fruit -green -melon .
Obtenez d'abord vos correspondances commandées :
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 ) ; Surligneur innerHTML de base ( plages enveloppées de <mark> ) :
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 ) ; Surligneur innerHTML avec fonction de marquage personnalisée ( <b> -plages enveloppées) :
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 ) ;Surligneur d'éléments DOM/JSX avec fonctions de marquage et d'ajout personnalisées :
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 a deux modes opérationnels qui diffèrent par la stratégie de correspondance :
example - exactexamplle - insertion unique (ajout)exemple - substitution simple (remplacement)exmaple - transposition unique (swap)exmple - suppression unique (omission)xamp - partielxmap - partiel avec transpositionIl y a 3 phases dans une recherche :
haystack complète avec une RegExp rapide compilée à partir de votre needle sans effectuer d'opérations supplémentaires. Il renvoie un tableau d'index correspondants dans l'ordre d'origine.needle en deux RegExps plus coûteuses qui peuvent partitionner chaque correspondance. Par conséquent, il doit être exécuté sur un sous-ensemble réduit de la botte de foin, généralement renvoyé par la phase Filter. La démo uFuzzy est limitée à <= 1 000 éléments filtrés, avant de passer à cette phase.Array.sort() pour déterminer l'ordre final des résultats, en utilisant l'objet info renvoyé par la phase précédente. Une fonction de tri personnalisée peut être fournie via une option uFuzzy : {sort: (info, haystack, needle) => idxsOrder} .Un fichier uFuzzy.d.ts de 200 LoC généreusement commenté.
Les options avec un préfixe inter s'appliquent aux tolérances entre les termes de recherche, tandis que celles avec un préfixe intra s'appliquent aux tolérances au sein de chaque terme de recherche.
| Option | Description | Défaut | Exemples |
|---|---|---|---|
intraMode | Comment effectuer la correspondance des termes | 0 | 0 MultiInsertion1 seule erreurVoir comment ça marche |
intraIns | Nombre maximum de caractères supplémentaires autorisés entre chaque caractère d'un terme | Correspond à la valeur de intraMode (soit 0 ou 1 ) | Recherche de "chat"...0 peut correspondre à : cat , s cat , cat ch, va cat e1 correspond également à : chariot , chapitre , exclu |
interIns | Nombre maximum de caractères supplémentaires autorisés entre les termes | Infinity | Recherche "où est"...Infinity peut correspondre : où est , où est bla w est dom5 ne peut pas correspondre : où est la sagesse blabla |
intraSubintraTrnintraDel | Pour intraMode: 1 uniquement,Types d'erreurs à tolérer dans les termes | Correspond à la valeur de intraMode (soit 0 ou 1 ) | 0 Non1 Oui |
intraChars | Expression rationnelle partielle pour l'insertion autorisée caractères entre chaque caractère dans un terme | [azd'] | [azd] correspond uniquement aux caractères alphanumériques (insensible à la casse)[w-] correspondrait aux caractères alphanumériques, au trait de soulignement et au trait d'union |
intraFilt | Rappel pour exclure les résultats en fonction du terme et de la correspondance | (term, match, index) => true | Faites votre propre truc, peut-être... - Seuil de différence de longueur - Distance de Levenshtein - Terme décalage ou contenu |
interChars | Expression rationnelle partielle pour les caractères autorisés entre les termes | . | . correspond à tous les caractères[^azd] ne correspondrait qu'aux espaces et à la ponctuation |
interLft | Détermine la limite gauche du terme autorisé | 0 | Vous recherchez "mania"...0 n'importe où - n'importe où : roumanie n1 en vrac - espaces, ponctuation, alpha-num, transitions de changement de casse : Track Mania , mania c2 strict - espaces, ponctuation : manie |
interRgt | Détermine la limite droite du terme autorisé | 0 | Vous recherchez "mania"...0 n'importe où - n'importe où : roumanie n1 en vrac - espaces, ponctuation, alpha-num, transitions de changement de casse : Mania Star2 strict - espaces, ponctuation : mania _foo |
sort | Fonction de tri des résultats personnalisé | (info, haystack, needle) => idxsOrder | Par défaut : tri de recherche, donne la priorité aux correspondances de termes complets et à la densité des caractères Démo : tri par saisie anticipée, donne la priorité au décalage de début et à la longueur de correspondance |
Cette évaluation est extrêmement étroite et, bien sûr, biaisée en faveur de mes cas d'utilisation, de mon corpus de textes et de mon expertise complète dans l'exploitation de ma propre bibliothèque. Il est fort probable que je ne profite pas pleinement de certaines fonctionnalités d'autres bibliothèques qui pourraient améliorer considérablement les résultats sur certains axes ; J'apprécie les PR d'amélioration de toute personne ayant des connaissances plus approfondies en bibliothèque que celles offertes par mon survol précipité de 10 minutes sur n'importe quel exemple « d'utilisation de base » et le document README.
Boîte de vers #1.
Avant de discuter des performances, parlons de la qualité de la recherche, car la vitesse n'a pas d'importance lorsque vos résultats sont un étrange mélange de « Oh ouais ! et "WTF?".
La qualité de la recherche est très subjective. Ce qui constitue une bonne correspondance supérieure dans un cas de type « saisie anticipée/suggestion automatique » peut être une mauvaise correspondance dans un scénario de « recherche/trouver tout ». Certaines solutions optimisent pour les seconds, d'autres pour les premiers. Il est courant de trouver des boutons qui faussent les résultats dans les deux sens, mais ils sont souvent imparfaits et imparfaits, n'étant guère plus qu'un proxy pour produire un « score » de correspondance unique et composite.
MISE À JOUR (2024) : La critique ci-dessous concernant les correspondances bizarres n'est vraie que pour la configuration par défaut de Fuse.js. Contre-intuitivement, la définition de ignoreFieldNorm: true a considérablement amélioré les résultats, mais l'ordre des correspondances de haute qualité reste médiocre.
Jetons un coup d'œil à certaines correspondances produites par la bibliothèque de recherche floue la plus populaire, Fuse.js, et à quelques autres pour lesquelles la mise en évidence des correspondances est implémentée dans la démo.
En recherchant le terme partiel "twili" , nous voyons ces résultats apparaître au-dessus de nombreux résultats évidents de "crépuscule" :
https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=twili
Non seulement ces mauvaises correspondances sont isolées, mais elles sont en fait plus classées que les sous-chaînes littérales.
En terminant le terme de recherche par "crépuscule" , on obtient toujours des résultats bizarres plus élevés :
https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=twilight
Certains moteurs fonctionnent mieux avec des correspondances de préfixes partielles, au détriment de coûts de démarrage/indexation plus élevés :
https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,FlexSearch,match-sorter,MiniSearch&search=twili
Ici, match-sorter renvoie 1 384 résultats, mais seuls les 40 premiers sont pertinents. Comment savoir où se situe la coupure ?
Boîte de vers #2.
Tous les benchmarks sont nuls, mais celui-ci pourrait être plus nul que d’autres.
Pourtant, quelque chose vaut mieux qu’un licenciement YMMV/fait-le soi-même et certainement mieux que rien.
Environnement
| Date | 2023-10 |
|---|---|
| Matériel | Processeur : Ryzen 7 PRO 5850U (1,9 GHz, 7 nm, TDP 15 W) RAM : 48 Go SSD : Samsung SSD 980 PRO 1 To (NVMe) |
| Système d'exploitation | EndeavourOS (Arch Linux) v6.5.4-arch2-1 x86_64 |
| Chrome | v117.0.5938.132 |
libs par le nom de bibliothèque souhaité : https://leeoniya.github.io/uFuzzy/demos/compare.html?bench&libs=uFuzzybench pour éviter de comparer le DOM.test , chest , super ma , mania , puzz , prom rem stor , twil . Pour évaluer les résultats de chaque librairie, ou pour en comparer plusieurs, visitez simplement la même page avec plus de libs et sans bench : https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore ,Fuse&search=super%20ma.
Plusieurs mesures sont évaluées :
| Lib | Étoiles | Taille (min) | Initialisation | Recherche (x86) | Tas (pic) | Conservé | CG |
|---|---|---|---|---|---|---|---|
| uFuzzy (essayer) | ★ 2,3k | 7,6 Ko | 0,5 ms | 434 ms | 28,4 Mo | 7,4 Mo | 18 ms |
| uFuzzy (essayer) (mise en cache des préfixes externes) | 210 ms | 27,8 Mo | 7,4 Mo | 18 ms | |||
| uFuzzy (essayer) (hors ordre, plus flou) | 545 ms | 29,5 Mo | 7,4 Mo | 18 ms | |||
| uFuzzy (essayer) (hors ordre, plus flou, SingleError) | 508 ms | 30,0 Mo | 7,4 Mo | 18 ms | |||
| ------- | |||||||
| Fuse.js (essayer) | ★ 16,6k | 24,2 Ko | 31 ms | 33875 ms | 245 Mo | 13,9 Mo | 25 ms |
| FlexSearch (Léger) (essayer) | ★ 10,7k | 6,2 Ko | 3210 ms | 83 ms | 670 Mo | 316 Mo | 553 ms |
| Lunr.js (essayer) | ★ 8,7k | 29,4 Ko | 1704 ms | 996 ms | 380 Mo | 123 Mo | 166 ms |
| Orama (anciennement Lyra) (essayer) | ★ 6,4k | 41,5 Ko | 2650 ms | 225 ms | 313 Mo | 192 Mo | 180 ms |
| MiniRecherche (essayer) | ★ 3,4k | 29,1 Ko | 504 ms | 1453 ms | 438 Mo | 67 Mo | 105 ms |
| trieur de correspondances (essayer) | ★ 3,4k | 7,3 Ko | 0,1 ms | 6245 ms | 71 Mo | 7,3 Mo | 12 ms |
| tri flou (essayer) | ★ 3,4k | 6,2 Ko | 50 ms | 1321 ms | 175 Mo | 84 Mo | 63 ms |
| Wade (essayer) | ★ 3k | 4 Ko | 781 ms | 194 ms | 438 Mo | 42 Mo | 130 ms |
| recherche floue (essayer) | ★ 2,7k | 0,2 Ko | 0,1 ms | 529 ms | 26,2 Mo | 7,3 Mo | 18 ms |
| js-search (essayer) | ★ 2,1k | 17,1 Ko | 5620 ms | 1190 ms | 1740 Mo | 734 Mo | 2600 ms |
| Elasticlunr.js (essayer) | ★ 2k | 18,1 Ko | 933 ms | 1330 ms | 196 Mo | 70 Mo | 135 ms |
| Fuzzyset (essayer) | ★ 1,4k | 2,8 Ko | 2962 ms | 606 ms | 654 Mo | 238 Mo | 239 ms |
| index de recherche (essayer) | ★ 1,4k | 168 Ko | RangeError : taille maximale de la pile d'appels dépassée | ||||
| tamis.js (essayer) | ★ 1,1k | 7,5 Ko | 3 ms | 1070 ms | 46,2 Mo | 10,6 Mo | 18 ms |
| fzf-for-js (essayer) | ★ 831 | 15,4 Ko | 50 ms | 6290 ms | 153 Mo | 25 Mo | 18 ms |
| flou (essayez) | ★ 819 | 1,4 Ko | 0,1 ms | 5427 ms | 72 Mo | 7,3 Mo | 14 ms |
| rapide-flou (essayer) | ★ 346 | 18,2 Ko | 790 ms | 19266 ms | 550 Mo | 165 Mo | 140 ms |
| ItemsJS (essayer) | ★ 305 | 109 Ko | 2400 ms | 11304 ms | 320 Mo | 88 Mo | 163 ms |
| LiquidMetal (essayer) | ★ 292 | 4,2 Ko | (accident) | ||||
| Recherche floue (essayer) | ★ 209 | 3,5 Ko | 2 ms | 3948 ms | 84 Mo | 10,5 Mo | 18 ms |
| FuzzySearch2 (essayer) | ★ 186 | 19,4 Ko | 93 ms | 4189 ms | 117 Mo | 40,3 Mo | 40 ms |
| QuickScore (essayer) | ★ 153 | 9,5 Ko | 10 ms | 6915ms | 133 Mo | 12,1 Mo | 18 ms |
| ndx (essayer) | ★ 142 | 2,9 Ko | 300 ms | 581 ms | 308 Mo | 137 Mo | 262 ms |
| fzy (essayer) | ★ 133 | 1,5 Ko | 0,1 ms | 3932 ms | 34 Mo | 7,3 Mo | 10 ms |
| outils flous (essayer) | ★ 13 | 3 Ko | 0,1 ms | 5138ms | 164 Mo | 7,5 Mo | 18 ms |
| fuzzyMatch (essayer) | ★ 0 | 1 Ko | 0,1 ms | 2415 ms | 83,5 Mo | 7,3 Mo | 13 ms |
