uFuzzy
1.0.17
小さくて効率的なあいまい検索ですが、面倒ではありません。これは私のモヤモヤです?。似たようなものはたくさんありますが、これは私のものです¹。
uFuzzy は、比較的短い検索フレーズ (ニードル) を短から中程度のフレーズの大きなリスト (ヘイスタック) と照合するように設計されたファジー検索ライブラリです。これは、より寛容な String.includes() として説明するのが最も適切かもしれません。一般的なアプリケーションには、リストのフィルタリング、オートコンプリート/提案、タイトル、名前、説明、ファイル名、および機能の検索が含まれます。
uFuzzy のデフォルトのMultiInsertモードでは、各一致には、針からのすべての英数字が同じ順序で含まれている必要があります。 SingleErrorモードでは、各用語で 1 つのタイプミスが許容されます (Damerau-Levenshtein 距離 = 1)。その.search() API は、順序どおりでない用語を効率的に照合でき、複数の部分文字列の除外 (例: fruit -green -melon )、および英字以外の文字を含む正確な用語 (例: "C++" 、 "$100" 、 "#hashtag"サポートします。 "#hashtag" )。正しく保持すると、複数のオブジェクトのプロパティに対して効率的に照合することもできます。
Array.sort()を使用して推論し、カスタマイズできます。理解するための複合的なブラックボックス「スコア」はありません。
uFuzzy はラテン語/ローマ字用に最適化されており、内部的に非 Unicode 正規表現に依存しています。
より多くの言語のサポートは、組み込みのラテン語正規表現を追加の文字で強化するか、低速で汎用的な{unicode: true}バリアントを使用することによって機能します。よりシンプルですが、柔軟性に劣る{alpha: "..."}代替方法は、組み込みラテン正規表現のAZおよびaz ～ Z の部分を選択した文字に置き換えます (大文字と小文字は置換中に自動的に照合されます)。
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 ファイルは、サイズが 4MB の多様な 162,000 文字列/フレーズ データセットであるため、ネットワーク転送により最初の読み込みが遅くなる可能性があります。ブラウザにキャッシュされたら、更新してみてください。
まず、uFuzzy を単独で使用してそのパフォーマンスを実証します。
https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy&search=super%20ma
同じ比較ページが fuzzysort、QuickScore、および Fuse.js で起動されました。
https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=super%20ma
以下に完全なライブラリのリストを示しますが、ブラウザのクラッシュを避けるためにデータセットが縮小されています ( hearthstone_750 、 urls_and_titles_600のみ)。
https://leeoniya.github.io/uFuzzy/demos/compare.html?lists=hearthstone_750,urls_and_titles_600&search=moo
答え:
それ以外の場合: 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 は、上記のfilter 、 info 、 sortステップを組み合わせたuf.search(haystack, needle, outOfOrder = 0, infoThresh = 1e3) => [idxs, info, order]ラッパーを提供します。このメソッドは、検索語を順不同で照合するための効率的なロジックも実装し、複数の部分文字列の除外 (例: 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 には、マッチング戦略が異なる 2 つの動作モードがあります。
example - 正確なexamplle - 単一の挿入 (追加)exemple - 単一の置換 (置換)exmaple - 単一の転置 (スワップ)exmple - 単一削除（省略）xamp - 部分的xmap - 転置を伴う部分的検索には 3 つのフェーズがあります。
needleからコンパイルされた高速 RegExp を使用して、干し草のhaystack全体をフィルタリングします。一致したインデックスの配列を元の順序で返します。needle 2 つのより高価な RegExp に再コンパイルし、各一致を分割できます。したがって、通常はフィルターフェーズによって返される干し草の山の縮小されたサブセットで実行する必要があります。 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 e に一致します。1 、 car t 、 Chapter 、 out castにも一致します。 |
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厳密 - 空白、句読点:マニア向き |
interRgt | 許容される用語の右境界を決定します | 0 | 「マニア」で検索すると…0任意 - どこでも:ローマn1緩い - 空白、句読点、英数字、大文字と小文字の切り替えトランジション: Mania Star2厳密 - 空白、句読点: mania _foo |
sort | カスタム結果ソート機能 | (info, haystack, needle) => idxsOrder | デフォルト: 検索ソート、完全な用語一致と文字密度を優先します。 デモ: 先行入力ソート、開始オフセットと一致長を優先する |
この評価は非常に限定的であり、もちろん、私の使用例、テキスト コーパス、および私自身のライブラリの運用に関する完全な専門知識に偏っています。ある軸に沿って結果を大幅に改善する可能性がある他のライブラリの機能を最大限に活用していない可能性が非常に高いです。私が「基本的な使用法」の例と README ドキュメントを 10 分ほどざっと読んだだけでは理解できないほど深いライブラリ知識を持つ方からの改善 PR を歓迎します。
ワーム缶 #1。
パフォーマンスについて説明する前に、検索の品質について話しましょう。検索結果が「ああ、そうそう！」という奇妙なおどけの場合、速度は重要ではないからです。そして「一体何？」。
検索の品質は非常に主観的なものです。 「先行入力 / 自動提案」の場合に適切な上位一致を構成するものは、「検索 / すべて検索」のシナリオでは不適切な一致となる可能性があります。後者向けに最適化するソリューションもあれば、前者向けに最適化するソリューションもあります。どちらかの方向に結果を歪めるノブを見つけるのはよくあることですが、これらは多くの場合、感覚によるもので不完全であり、単一の複合一致「スコア」を生成するための代理にすぎません。
更新 (2024):奇妙な一致に関する以下の批判は、Fuse.js のデフォルト設定にのみ当てはまります。直感に反しますが、 ignoreFieldNorm: trueを設定すると結果は大幅に改善されましたが、高品質の一致の順序付けは依然として優れていません。
最も人気のあるあいまい検索ライブラリである Fuse.js によって生成されたいくつかの一致と、デモで一致の強調表示が実装されているその他のいくつかを見てみましょう。
部分的な用語「twili」を検索すると、多数の明白な「twilight」結果の上に次の結果が表示されます。
https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=twili
これらの不適切な一致は単独で存在するだけでなく、実際にはリテラルの部分文字列よりも上位にランクされます。
検索語を「twilight」で終わらせても、奇妙な結果のスコアが高くなります。
https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=twilight
一部のエンジンは、起動/インデックス作成コストが高くなりますが、部分的なプレフィックス一致の方が優れています。
https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,FlexSearch,match-sorter,MiniSearch&search=twili
ここで、 match-sorter 1,384 件の結果を返しますが、関連するのは最初の 40 件のみです。どこがカットオフなのかをどうやって知ることができるのでしょうか?
ワーム缶その２。
どのベンチマークも最悪ですが、これは他のベンチマークよりもひどいかもしれません。
それでも、YMMV/日曜大工による解雇よりは何かあった方が良いし、何もしないよりは確かに良いです。
環境
| 日付 | 2023-10 |
|---|---|
| ハードウェア | CPU：Ryzen 7 PRO 5850U（1.9GHz、7nm、15W TDP） RAM: 48GB SSD: Samsung SSD 980 PRO 1TB (NVMe) |
| OS | EndeavourOS (アーチ Linux) v6.5.4-arch2-1 x86_64 |
| クロム | v117.0.5938.132 |
libsパラメーターを目的のライブラリ名に変更することで実行できます: https://leeoniya.github.io/uFuzzy/demos/compare.html?bench&libs=uFuzzybenchモードでは結果の出力が抑制されます。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) | ヒープ (ピーク) | 保持 | GC |
|---|---|---|---|---|---|---|---|
| uFuzzy (試してください) | ★ 2.3k | 7.6KB | 0.5ミリ秒 | 434ミリ秒 | 28.4MB | 7.4MB | 18ミリ秒 |
| uFuzzy (試してください) (外部プレフィックスキャッシュ) | 210ミリ秒 | 27.8MB | 7.4MB | 18ミリ秒 | |||
| uFuzzy (試してください) (outOfOrder、曖昧) | 545ミリ秒 | 29.5MB | 7.4MB | 18ミリ秒 | |||
| uFuzzy (試してください) (outOfOrder、ファジー、SingleError) | 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ミリ秒 |
| オラマ (旧ライラ) (試してください) | ★6.4k | 41.5KB | 2650ミリ秒 | 225ミリ秒 | 313MB | 192MB | 180ミリ秒 |
| ミニサーチ（お試しください） | ★3.4k | 29.1KB | 504ミリ秒 | 1453ミリ秒 | 438MB | 67MB | 105ミリ秒 |
| マッチソーター (試してみてください) | ★3.4k | 7.3KB | 0.1ms | 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-search（試してください） | ★ 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.1ms | 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ミリ秒 |
| FuzzySearch2 (お試しください) | ★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.1ms | 5138ミリ秒 | 164MB | 7.5MB | 18ミリ秒 |
| ファジーマッチ (試してみる) | ★0 | 1KB | 0.1ms | 2415ミリ秒 | 83.5MB | 7.3MB | 13ミリ秒 |
