uFuzzy
1.0.17
一個小而高效的模糊搜索，但並不糟糕。這是我的模糊？有很多類似的東西，但這一個是我的。
uFuzzy 是一個模糊搜尋庫，旨在將相對較短的搜尋短語（needle）與大量中短短語（haystack）進行配對。最好將其描述為更寬容的 String.includes()。常見的應用程式包括清單過濾、自動完成/建議以及搜尋標題、名稱、描述、檔案名稱和功能。
在 uFuzzy 的預設MultiInsert模式下，每個匹配項必須以相同的順序包含針中的所有字母數字字元；在SingleError模式下，每個術語都允許出現單一拼字錯誤（Damerau-Levenshtein 距離 = 1）。它的.search() API 可以有效地匹配無序術語，支援多個子字串排除（例如fruit -green -melon ）以及非字母字元的精確術語（例如"C++" 、 "$100" 、 "#hashtag" ）。如果握得恰到好處，它也可以有效地匹配多個物件屬性。
Array.sort()進行推理和自訂排序，該 Array.sort() 可以存取每場比賽的統計資料/計數器。沒有復合的黑盒子「分數」可供理解。
uFuzzy 針對拉丁/羅馬字母進行了最佳化，並在內部依賴非 unicode 正規表示式。
透過使用附加字元增強內建拉丁語正規表示式或使用速度較慢的通用{unicode: true}變體，可以支援更多語言。更簡單但不太靈活的{alpha: "..."}替代方案將內建拉丁語正規表示式的AZ和az部分替換為您選擇的字元（替換期間將自動匹配字母大小寫）。
uFuzzy.latinize() util 函數可用於在搜尋之前從大海撈針和針中移除常見的重音符號/變音符號。
// 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" ,
} ;目前所有搜尋均不區分大小寫；無法進行區分大小寫的搜尋。
注意： testdata.json 檔案是一個包含 162,000 個字串/短語、大小為 4MB 的多樣化資料集，因此由於網路傳輸的原因，首次載入可能會很慢。瀏覽器快取後嘗試刷新。
首先，uFuzzy 單獨展示了它的性能。
https://leoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy&search=super%20ma
現在是相同的比較頁面，使用 fuzzysort、QuickScore 和 Fuse.js 啟動：
https://leoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=super%20ma
這是完整的庫列表，但減少了資料集（只有hearthstone_750 、 urls_and_titles_600 ）以避免瀏覽器崩潰：
https://leoniya.github.io/uFuzzy/demos/compare.html?lists=hearthstone_750,urls_and_titles_600&search=moo
答案：
其他：https://github.com/leoniya/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 提供了一個uf.search(haystack, needle, outOfOrder = 0, infoThresh = 1e3) => [idxs, info, order]包裝器，它結合了上面的filter 、 info 、 sort步驟。該方法還實現了無序匹配搜尋詞的高效邏輯，並支援多個子字串排除，例如fruit -green -melon 。
首先取得您訂購的比賽：
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 ) ;基本的innerHTML螢光筆（ <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 ) ;具有自訂標記功能的innerHTML螢光筆（ <b> -包裹範圍）：
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 ) ;具有自訂標記和附加功能的 DOM/JSX 元素螢光筆：
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有兩種運行模式，其匹配策略有所不同：
example - 精確examplle - 單次插入（加法）exemple - 單一替換（替換）exmaple - 單次換位（交換）exmple - 單一刪除（省略）xamp - 部分xmap - 部分轉置搜尋分為 3 個階段：
needle編譯的快速正規表示式來過濾整個haystack ，而無需執行任何額外的操作。它按原始順序傳回匹配索引的陣列。needle重新編譯成兩個更昂貴的正則表達式，可以對每個匹配進行分區。因此，它應該在 haystack 的縮減子集上運行，通常由 Filter 階段傳回。在繼續此階段之前，uFuzzy 演示的門限為 <= 1,000 個過濾項目。info物件執行Array.sort()來決定最終結果順序。可以透過 uFuzzy 選項提供自訂排序函數： {sort: (info, haystack, needle) => idxsOrder} 。自由註釋的 200 LoC uFuzzy.d.ts 檔案。
帶有inter前綴的選項適用於搜尋字詞之間的限額，而帶有intra前綴的選項適用於每個搜尋字詞內的限額。
| 選項 | 描述 | 預設 | 範例 |
|---|---|---|---|
intraMode | 應如何進行術語匹配 | 0 | 0多插入1單一錯誤看看它是如何運作的 |
intraIns | 允許的最大額外字元數 術語內的每個字元之間 | 匹配intraMode的值（ 0或1 ） | 正在搜尋“貓”...0可以配對： cat , s cat , cat ch, va cat e1也符合： car t 、 chap t er 、 out ca s t |
interIns | 術語之間允許的最大額外字元數 | Infinity | 搜尋“在哪裡”...Infinity可以匹配： where is , where have blah w is dom5無法配對：哪裡有廢話智慧 |
intraSubintraTrnintraDel | 對於intraMode: 1 ，術語內可容忍的錯誤類型 | 匹配intraMode的值（ 0或1 ） | 0否1是 |
intraChars | 允許插入的部分正規表示式 術語內每個字符之間的字符 | [azd'] | [azd]僅符合字母數字（不區分大小寫）[w-]將匹配字母數字、底線和連字符 |
intraFilt | 根據術語和匹配排除結果的回調 | (term, match, index) => true | 做你自己的事情，也許... - 長度差異閾值 - 編輯距離 - 術語偏移或內容 |
interChars | 術語之間允許的字元的部分正規表示式 | . | .匹配所有字符[^azd]只符合空格和標點符號 |
interLft | 確定允許的項左邊界 | 0 | 搜尋“狂熱”...0任何 - 任何地方：羅馬狂熱n1寬鬆 - 空格、標點符號、字母數字、大小寫轉換轉換： Track Mania 、 mania c2嚴格 - 空格、標點符號： mania cally |
interRgt | 確定允許的術語右邊界 | 0 | 搜尋“狂熱”...0任何 - 任何地方：羅馬狂熱n1寬鬆 - 空格、標點符號、字母數字、大小寫轉換： Mania Star2嚴格 - 空格、標點符號： mania _foo |
sort | 自訂結果排序功能 | (info, haystack, needle) => idxsOrder | 預設：搜尋排序，優先考慮完整術語匹配和字元密度 示範：預先輸入排序，優先考慮起始偏移量和匹配長度 |
這個評估非常狹窄，當然，偏向我的用例、文字語料庫以及我經營自己的圖書館的完整專業知識。我很可能沒有充分利用其他庫中的某些功能，這些功能可能會顯著改善某些軸上的結果；我歡迎任何擁有更深入圖書館知識的人提出改進 PR，而不是我匆忙瀏覽 10 分鐘的「基本用法」範例和自述文件。
蠕蟲罐#1。
在討論性能之前，讓我們先討論一下搜尋質量，因為當您的結果是「哦耶！」的奇怪混合時，速度就無關緊要了。和“WTF？”。
搜尋品質是非常主觀的。在「預先輸入/自動建議」情況下構成良好頂部匹配的內容在「搜尋/尋找全部」情況下可能是較差匹配。有些解決方案針對後者進行最佳化，有些則針對前者進行最佳化。通常會發現旋鈕使結果向任一方向傾斜，但這些旋鈕通常是憑感覺且不完美的，只不過是產生單一複合匹配「分數」的代理。
更新（2024）：以下關於奇怪匹配的批評僅適用於 Fuse.js 的預設配置。與直覺相反，設定ignoreFieldNorm: true顯著改善了結果，但高品質匹配的排序仍然不太好。
讓我們來看看最受歡迎的模糊搜尋庫 Fuse.js 產生的一些匹配項以及在演示中實現了匹配突出顯示的其他一些匹配項。
搜尋部分術語「twili」 ，我們看到這些結果出現在許多明顯的「twilight」結果之上：
https://leoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=twili
這些糟糕的匹配不僅是孤立的，而且它們的排名實際上比字面子字串要高。
完成搜尋字詞“twilight” ，仍然獲得更高的奇怪結果：
https://leoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=twilight
有些引擎在部分前綴匹配方面做得更好，但代價是啟動/索引成本更高：
https://leoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,FlexSearch,match-sorter,MiniSearch&search=twili
在這裡， match-sorter傳回 1,384 個結果，但只有前 40 個是相關的。我們如何知道截止點在哪裡？
蠕蟲罐#2。
所有基準測試都很糟糕，但這個基準測試可能比其他基準測試更糟。
儘管如此，有什麼比用手揮手 YMMV/自己動手解僱要好，而且肯定比什麼都沒有好。
環境
| 日期 | 2023年10月 |
|---|---|
| 硬體 | CPU：銳龍 7 PRO 5850U（1.9GHz，7nm，15W TDP） 記憶體：48GB 固態硬碟：三星固態硬碟 980 PRO 1TB (NVMe) |
| 作業系統 | EndeavourOS（Arch Linux） v6.5.4-arch2-1 x86_64 |
| 鉻合金 | v117.0.5938.132 |
libs參數更改為所需的庫名稱來運行：https://leeoniya.github.io/uFuzzy/demos/compare.html?bench&libs=uFuzzybench模式下被抑制，以避免對 DOM 進行基準測試。test 、 chest 、 super ma 、 mania 、 puzz 、 prom rem stor 、 twil 。要評估每個庫的結果，或比較多個庫，只需訪問具有更多libs但沒有bench同一頁面：https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy ,fuzzysort,QuickScore ,保險絲&搜尋=超級%20ma。
評估了幾個指標：
| 庫 | 星星 | 尺寸（最小） | 初始化 | 搜尋 （×86） | 堆（峰值） | 保留 | 氣相層析 |
|---|---|---|---|---|---|---|---|
| uFuzzy（嘗試） | ★ 2.3k | 7.6KB | 0.5毫秒 | 434毫秒 | 28.4MB | 7.4MB | 18毫秒 |
| uFuzzy（嘗試） （外部前綴緩存） | 210毫秒 | 27.8MB | 7.4MB | 18毫秒 | |||
| uFuzzy（嘗試） （亂序，模糊） | 545毫秒 | 29.5MB | 7.4MB | 18毫秒 | |||
| uFuzzy（嘗試） （亂序、模糊、單一錯誤） | 508毫秒 | 30.0MB | 7.4MB | 18毫秒 | |||
| -------- | |||||||
| Fuse.js（嘗試） | ★ 16.6k | 24.2KB | 31毫秒 | 33875毫秒 | 245MB | 13.9MB | 25毫秒 |
| FlexSearch（輕量）（嘗試） | ★ 10.7k | 6.2KB | 3210毫秒 | 83毫秒 | 670MB | 316MB | 553毫秒 |
| Lunr.js（嘗試） | ★ 8.7k | 29.4KB | 1704毫秒 | 996毫秒 | 380MB | 123MB | 166毫秒 |
| Orama（以前的 Lyra）（嘗試） | ★ 6.4k | 41.5KB | 2650毫秒 | 225毫秒 | 313MB | 192MB | 180毫秒 |
| 迷你搜尋（嘗試） | ★ 3.4k | 29.1KB | 504毫秒 | 1453毫秒 | 438MB | 67MB | 105毫秒 |
| 匹配排序器（嘗試） | ★ 3.4k | 7.3KB | 0.1毫秒 | 6245毫秒 | 71MB | 7.3MB | 12毫秒 |
| 模糊排序（嘗試） | ★ 3.4k | 6.2KB | 50毫秒 | 1321毫秒 | 175MB | 84MB | 63毫秒 |
| 韋德（嘗試） | ★ 3k | 4KB | 781毫秒 | 194毫秒 | 438MB | 42MB | 130毫秒 |
| 模糊搜尋（嘗試） | ★ 2.7k | 0.2KB | 0.1毫秒 | 529毫秒 | 26.2MB | 7.3MB | 18毫秒 |
| js-搜尋（嘗試） | ★ 2.1k | 17.1KB | 5620毫秒 | 1190毫秒 | 1740MB | 734MB | 2600毫秒 |
| Elasticlunr.js（嘗試） | ★ 2k | 18.1KB | 933毫秒 | 1330毫秒 | 196MB | 70MB | 135毫秒 |
| 模糊集合（嘗試） | ★ 1.4k | 2.8KB | 2962毫秒 | 606毫秒 | 654MB | 238MB | 239毫秒 |
| 搜尋索引（嘗試） | ★ 1.4k | 168KB | RangeError：超出最大呼叫堆疊大小 | ||||
| sifter.js（嘗試） | ★ 1.1k | 7.5KB | 3毫秒 | 1070毫秒 | 46.2MB | 10.6MB | 18毫秒 |
| fzf-for-js（嘗試） | ★831 | 15.4KB | 50毫秒 | 6290毫秒 | 153MB | 25MB | 18毫秒 |
| 模糊（嘗試） | ★819 | 1.4KB | 0.1毫秒 | 5427毫秒 | 72MB | 7.3MB | 14毫秒 |
| 快速模糊（嘗試） | ★ 346 | 18.2KB | 790毫秒 | 19266毫秒 | 550MB | 165MB | 140毫秒 |
| ItemsJS（嘗試） | ★ 305 | 109KB | 2400毫秒 | 11304毫秒 | 320MB | 88MB | 163毫秒 |
| 液態金屬（嘗試） | ★292 | 4.2KB | （碰撞） | ||||
| 模糊搜尋（嘗試） | ★209 | 3.5KB | 2毫秒 | 3948毫秒 | 84MB | 10.5MB | 18毫秒 |
| 模糊搜尋2（嘗試） | ★186 | 19.4KB | 93毫秒 | 4189毫秒 | 117MB | 40.3MB | 40毫秒 |
| 快速得分（嘗試） | ★ 153 | 9.5KB | 10毫秒 | 6915毫秒 | 133MB | 12.1MB | 18毫秒 |
| ndx（嘗試） | ★ 142 | 2.9KB | 300毫秒 | 581毫秒 | 308MB | 137MB | 262毫秒 |
| fzy（嘗試） | ★ 133 | 1.5KB | 0.1毫秒 | 3932毫秒 | 34MB | 7.3MB | 10毫秒 |
| 模糊工具（嘗試） | ★ 13 | 3KB | 0.1毫秒 | 5138毫秒 | 164MB | 7.5MB | 18毫秒 |
| 模糊匹配（嘗試） | ★ 0 | 1KB | 0.1毫秒 | 2415毫秒 | 83.5MB | 7.3MB | 13毫秒 |
