uFuzzy下载 - uFuzzy源代码下载

▒ μ模糊

一个小而高效的模糊搜索，但并不糟糕。这是我的模糊？有很多类似的东西，但这一个是我的。

概述

uFuzzy 是一个模糊搜索库，旨在将相对较短的搜索短语（needle）与大量中短短语（haystack）进行匹配。最好将其描述为更宽容的 String.includes()。常见的应用程序包括列表过滤、自动完成/建议以及搜索标题、名称、描述、文件名和功能。

在 uFuzzy 的默认MultiInsert模式下，每个匹配项必须以相同的顺序包含针中的所有字母数字字符；在SingleError模式下，每个术语都允许出现单个拼写错误（Damerau-Levenshtein 距离 = 1）。它的.search() API 可以有效地匹配无序术语，支持多个子字符串排除（例如fruit -green -melon ）以及非字母字符的精确术语（例如"C++" 、 "$100" 、 "#hashtag" ）。如果握得恰到好处，它也可以有效地匹配多个对象属性。

特征

任何数据集都不会产生垃圾、高质量的结果。无需微调索引选项或提升参数即可获得任意相关性分数截止。
遵循简单规则的精确模糊控制，不会返回意外的匹配项。
您可以使用简单的Array.sort()进行推理和自定义排序，该 Array.sort() 可以访问每场比赛的统计数据/计数器。没有复合的黑匣子“分数”可供理解。
一组简洁的选项不会以神秘的方式相互作用来彻底改变组合行为。
速度快，资源使用率低- 无需构建索引，因此启动时间低于 1 毫秒，内存开销接近于零。在包含无序术语的情况下，在 162,000 个短语数据集中搜索一个三术语短语需要 5 毫秒。
Micro，零依赖性- 目前最小约为 7.5KB

u模糊演示

字符集、字母表、变音符号

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://news.ycombinator.com/item?id=33035580
https://old.reddit.com/r/javascript/comments/xtrszc/ufuzzyjs_a_tiny_efficient_fuzzy_search_that/

其他：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有两种运行模式，其匹配策略有所不同：

intraMode：0 （默认值）要求每个搜索词中的所有字母数字字符在所有匹配中都以相同的顺序存在。例如，当搜索“ cat ”时，该模式能够匹配以下字符串。实际匹配的内容取决于附加的模糊性设置。
- 猫
- 外套
- 划痕
- 卡蒂纳
- 拖拉机相关
intraMode：1允许搜索短语的每个术语中存在单个错误，其中错误是以下之一：替换（替换）、转置（交换）、插入（添加）或删除（省略）。以下有错误的搜索字符串可能会返回包含“ example ”的匹配项。实际匹配的内容取决于附加的模糊性设置。与之前的模式相反，搜索“ example ”永远不会匹配“ ex tr a m a ple ”。
- example - 精确
- examplle - 单次插入（加法）
- exemple - 单一替换（替换）
- exmaple - 单次换位（交换）
- exmple - 单个删除（省略）
- xamp - 部分
- xmap - 部分转置

搜索分为 3 个阶段：

Filter使用从您的needle编译的快速正则表达式来过滤整个haystack ，而无需执行任何额外的操作。它按原始顺序返回匹配索引的数组。
Info收集有关过滤匹配的更详细统计信息，例如起始偏移、模糊级别、前缀/后缀计数器等。它还收集子字符串匹配位置以进行范围突出显示。最后，它会过滤掉任何不符合所需前缀/后缀规则的匹配项。为了完成这一切，它将needle重新编译成两个更昂贵的正则表达式，可以对每个匹配进行分区。因此，它应该在 haystack 的缩减子集上运行，通常由 Filter 阶段返回。在继续此阶段之前，uFuzzy 演示的门限为 <= 1,000 个过滤项目。
Sort使用从前一阶段返回的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 、 chap t er 、 out ca s t
`interIns`	术语之间允许的最大额外字符数	`Infinity`	搜索“在哪里”... `Infinity`可以匹配： where is , where have blah w is dom `5`无法匹配：哪里有废话智慧
`intraSub` `intraTrn` `intraDel`	对于`intraMode: 1` ，术语内可容忍的错误类型	匹配`intraMode`的值（ `0`或`1` ）	`0`否 `1`是
`intraChars`	允许插入的部分正则表达式术语内每个字符之间的字符	`[azd']`	`[azd]`仅匹配字母数字（不区分大小写） `[w-]`将匹配字母数字、下划线和连字符
`intraFilt`	根据术语和匹配排除结果的回调	`(term, match, index) => true`	做你自己的事情，也许...... - 长度差异阈值 - 编辑距离 - 术语偏移或内容
`interChars`	术语之间允许的字符的部分正则表达式	`.`	`.`匹配所有字符 `[^azd]`只匹配空格和标点符号
`interLft`	确定允许的项左边界	`0`	搜索“狂热”... `0`任何 - 任何地方：ro mania n `1`宽松 - 空格、标点符号、字母数字、大小写转换转换： Track Mania 、 mania c `2`严格 - 空格、标点符号： mania cally
`interRgt`	确定允许的术语右边界	`0`	搜索“狂热”... `0`任何 - 任何地方：罗马狂热n `1`宽松 - 空格、标点符号、字母数字、大小写转换： Mania Star `2`严格 - 空格、标点符号： 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

旋转林
收到的无效警报总数。
Tom Clancy's Ghost Recon Wildlands - AS I A 预购标准 Uplay 激活
t heHunter™：野性的呼唤 - Bearclaw Li te CB-60

这些糟糕的匹配不仅是孤立的，而且它们的排名实际上比字面子字符串要高。

完成搜索词“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。

所有基准测试都很糟糕，但这个基准测试可能比其他基准测试更糟糕。

当我可以在每个库的文档中找到任何“最佳性能”建议时，我尝试遵循它，但可以肯定的是，在实现大约 20 个不同的搜索引擎时，有些石头没有被挖掘。
尽管我尽了最大努力，但库之间、甚至搜索词之间的结果质量仍然差异很大。在某些情况下，结果很差，但库速度很快；在其他情况下，结果更好，但库相当慢。当搜索质量低于标准时，极快的速度有什么用呢？这是一个主观的、微妙的话题，肯定会影响你如何解释这些数字。我认为 uFuzzy 的搜索质量是首屈一指的，所以我对大多数更快的库的看法通常是我很高兴没有做出的质量权衡之一。我鼓励您手动评估所有搁置搜索短语的结果，以便自己决定。
这里比较的许多全文和文档搜索库旨在与精确术语而不是部分匹配（此基准偏向于部分匹配）配合得最好。

尽管如此，有什么比用手挥手 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=uFuzzy
结果输出在bench模式下被抑制，以避免对 DOM 进行基准测试。
通过记录工作台页面的多次重新加载以及其间的强制垃圾回收，在 Chrome 开发工具的性能部分中进行测量。中间/典型运行用于收集数字。
搜索语料库包含 162,000 个单词和短语，从 4MB testdata.json 加载。
基准测试会逐个字符（每 20 毫秒）键入并删除以下搜索词，触发每次按键的搜索： 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。

个人资料示例

评估了几个指标：

初始化时间 - 加载库并构建执行搜索所需的索引所需的时间。
基准运行时间 - 执行所有搜索所需的时间。
所需内存 - 测试期间使用的峰值 JS 堆大小以及最后强制垃圾回收后仍保留的内存量。
GC cost - 最后需要多少时间来收集垃圾（主线程卡顿）

库	星星	尺寸（最小）	初始化	搜索（×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毫秒