有意义的 Javascript 模糊搜索

我正在寻找一个模糊搜索 JavaScript 库来过滤一个数组。我试过使用 Fuzzyset.js和 保险丝 JS，但结果很糟糕(有演示，你可以尝试在链接页面)。

在阅读了一些关于莱文斯坦距离的文章之后，我发现它并不能很好地反映用户在打字时所寻找的内容。对于那些不知道的人，系统计算需要多少 插入、 删除和 替代品才能使两个字符串匹配。

Levenshtein-Demerau 模式的一个明显缺陷是，哇和 咪咪被认为与 灯泡同样相似(每种模式都需要两种替代)。然而，很明显，灯泡比 咪咪更类似于 哇，我刚才提到的模型通过考虑到 换位而认识到了这一点。

我想在文本完成的上下文中使用它，所以如果我有一个数组 ['international', 'splint', 'tinder']，我的查询是 Int，我认为 国际的应该比 夹板排名更高，即使前者的得分(更高 = 更差)为10比后者的3。

因此，我所寻找的(如果它不存在，我将创建)是一个具有以下功能的库:

  • 加权不同的文本操作
  • 根据每个操作在单词中出现的位置，对它们进行不同的权重(早期操作比晚期操作成本更高)
  • 返回按相关性排序的结果列表

有人见过这样的东西吗？我意识到 StackOverflow 不是一个需要软件推荐的地方，而是一个隐含的地方(不再是了!)以上是: 我是否正确地思考这个问题？

剪辑

我找到了一个关于这个主题的 好文件(pdf)。一些注释和摘录:

仿射编辑距离函数为插入或删除序列分配相对较低的成本

Monger-Elkan 距离函数(Monge & Elkan 1996) ，它是 Smith-Waterman 距离函数的仿射变体，具有特定的成本参数

对于 史密斯-沃特曼距离(维基百科)，“ Smith-Waterman 算法比较所有可能长度的片段并优化相似性度量，而不是查看总序列。”这是 n-gram 方法。

一个非常类似的度量指标(不基于编辑距离模型)是 Jaro 度量(Jaro 1995; 1989; Winkler 1999年)。在记录连接文献中，基于两个字符串之间公共字符的数量和顺序，使用这种方法的变体已经取得了很好的结果。

Winkler (1999)的一个变体也使用了最长公共前缀的长度 P

(似乎主要用于短的字符串)

出于文本完成的目的，Monger-Elkan 和 Jaro-Winkler 方法似乎是最有意义的。Winkler 对 Jaro 度量的添加有效地加重了单词开头的权重。Monger-Elkan 的仿射方面意味着完成一个单词的必要性(这只是一个简单的添加序列)不会对它产生太大的不利影响。

结论:

TFIDF 在几个基于令牌的距离中表现最好的排名 以及由 Monge 和 Elkan 提出的调谐仿射间隙编辑距离度量，在几个指标中表现最好 字符串编辑距离度量。一个惊人的好距离 度量是一个快速的启发式方案，由 Jaro 提出，后来由 Winkler 扩展。 这几乎和蒙格-埃尔坎计划一样有效，但是 数量级更快。 一种将 TFIDF 方法与 Jaro-Winkler 将替换 基于 Jaro-的近似令牌匹配的 TFIDF 温克勒计划。这种组合的平均表现略好于 Jaro-Winkler 或 TFIDF，有时表现得更好。它的性能也接近于几个最好的度量标准的学习组合 在本文中考虑。

92295 次浏览
小开
最佳答案

问得好！但我的想法是，与其试图修改 Levenshtein-Demerau，不如尝试不同的算法，或者将两个算法的结果合并/加权。

我突然意识到，与“起始前缀”完全匹配或接近匹配的东西，Levenshtein-Demerau 没有给予特别的重视——但你明显的用户期望值会给予重视。

我搜索了“比 Levenshtein 更好”，除了其他东西，还发现了这个:

Http://www.joyofdata.de/blog/comparison-of-string-distance-algorithms/

这里提到了一些“字符串距离”度量，其中有三个看起来与你的需求特别相关，它们是:

  1. 最长的公共子字符串距离: 必须在两个字符串中删除的最小符号数，直到产生的子字符串相同。

  2. Q-gram 距离: 两个字符串的 N-gram 向量之间的强绝对值差和。

  3. 雅可比相似度系数: 1分钟共享的 n-gram 和所有观察到的 n-gram 的商。

也许您可以使用这些指标的一个加权组合(或最小值) ，与 Levenshtein ——公共子字符串、公共 N-gram 或 Jaccard 都将强烈偏好 相似字符串——或者也许尝试只使用 Jaccard？

根据您的列表/数据库的大小，这些算法可能相当昂贵。对于我实现的模糊搜索，我使用一个可配置数量的 N-gram 作为数据库中的“检索键”，然后运行代价高昂的字符串距离度量，按照优先顺序对它们进行排序。

我写了一些关于 SQL 中的模糊字符串搜索的注释。参见:

小开

这里有一个我曾经使用过几次的技巧... 它给出了非常好的结果。虽然不是你要求的一切。此外，如果列表很大，这可能会很昂贵。

get_bigrams = (string) ->
s = string.toLowerCase()
v = new Array(s.length - 1)
for i in [0..v.length] by 1
v[i] = s.slice(i, i + 2)
return v


string_similarity = (str1, str2) ->
if str1.length > 0 and str2.length > 0
pairs1 = get_bigrams(str1)
pairs2 = get_bigrams(str2)
union = pairs1.length + pairs2.length
hit_count = 0
for x in pairs1
for y in pairs2
if x is y
hit_count++
if hit_count > 0
return ((2.0 * hit_count) / union)
return 0.0

将两个字符串传递给 string_similarity，string_similarity将返回一个介于 0和 1.0之间的数字，具体取决于它们的相似程度。此示例使用 Lo-Dash

用法例子... 。

query = 'jenny Jackson'
names = ['John Jackson', 'Jack Johnson', 'Jerry Smith', 'Jenny Smith']


results = []
for name in names
relevance = string_similarity(query, name)
obj = {name: name, relevance: relevance}
results.push(obj)


results = _.first(_.sortBy(results, 'relevance').reverse(), 10)


console.log results

还有... 有一个 小提琴

确保您的控制台是打开的，否则您将看不到任何东西:)

小开 
(function (int) {
$("input[id=input]")
.on("input", {
sort: int
}, function (e) {
$.each(e.data.sort, function (index, value) {
if ( value.indexOf($(e.target).val()) != -1
&& value.charAt(0) === $(e.target).val().charAt(0)
&& $(e.target).val().length === 3 ) {
$("output[for=input]").val(value);
};
return false
});
return false
});
}(["international", "splint", "tinder"]))

Jsfiddle http://jsfiddle.net/guest271314/QP7z5/

小开

你可以看看 Atom 的 https://github.com/atom/fuzzaldrin/库。

它可以在 npm 上使用，有简单的 API，对我来说还不错。

> fuzzaldrin.filter(['international', 'splint', 'tinder'], 'int');
< ["international", "splint"]
小开

我尝试使用现有的模糊库，比如 fuse.js，但是也发现它们很糟糕，所以我写了一个基本上就像升华搜索一样的库。https://github.com/farzher/fuzzysort

它唯一允许的拼写错误是一个转位。它是相当坚固的 (1k 颗星，0期)，非常快，并处理你的情况很容易:

fuzzysort.go('int', ['international', 'splint', 'tinder'])
// [{highlighted: '*int*ernational', score: 10}, {highlighted: 'spl*int*', socre: 3003}]

小开

这是模糊匹配的简短函数:

function fuzzyMatch(pattern, str) {
pattern = '.*' + pattern.split('').join('.*') + '.*';
const re = new RegExp(pattern);
return re.test(str);
}
小开

2019年11月最新情况。我发现保险丝有一些相当不错的升级。但是，我不能让它使用 bool 的(即 OR、 AND 等操作符) ，也不能使用 API 搜索界面来过滤结果。

我发现了 nextapps-de/flexsearch: https://github.com/nextapps-de/flexsearch，我相信它远远超过了我所尝试过的其他很多 javascript 搜索库，并且它支持 bool、过滤搜索和分页。

您可以为您的搜索数据(即存储)输入一个 javascript 对象列表，并且这个 API 有很好的文档说明: https://github.com/nextapps-de/flexsearch#api-overview

到目前为止，我已经索引了近10,000条记录，而且我的搜索是紧挨着即时的; 也就是说，每次搜索所花费的时间是不可察觉的。

小开

下面是@InternalFX 提供的解决方案，但是在 JS 中(我使用它来共享) :

function get_bigrams(string){
var s = string.toLowerCase()
var v = s.split('');
for(var i=0; i<v.length; i++){ v[i] = s.slice(i, i + 2); }
return v;
}


function string_similarity(str1, str2){
if(str1.length>0 && str2.length>0){
var pairs1 = get_bigrams(str1);
var pairs2 = get_bigrams(str2);
var union = pairs1.length + pairs2.length;
var hits = 0;
for(var x=0; x<pairs1.length; x++){
for(var y=0; y<pairs2.length; y++){
if(pairs1[x]==pairs2[y]) hits++;
}}
if(hits>0) return ((2.0 * hits) / union);
}
return 0.0
}
小开

我通过 InternalFx 修复了 CoffeeScript 二元解决方案的问题，并使其成为一个通用的 n-gram 解决方案(您可以自定义 g 的大小)。

这是 TypeScript，但是您可以删除类型注释，它也可以像普通的 JavaScript 一样工作。

/**
* Compares the similarity between two strings using an n-gram comparison method.
* The grams default to length 2.
* @param str1 The first string to compare.
* @param str2 The second string to compare.
* @param gramSize The size of the grams. Defaults to length 2.
*/
function stringSimilarity(str1: string, str2: string, gramSize: number = 2) {
function getNGrams(s: string, len: number) {
s = ' '.repeat(len - 1) + s.toLowerCase() + ' '.repeat(len - 1);
let v = new Array(s.length - len + 1);
for (let i = 0; i < v.length; i++) {
v[i] = s.slice(i, i + len);
}
return v;
}


if (!str1?.length || !str2?.length) { return 0.0; }


//Order the strings by length so the order they're passed in doesn't matter
//and so the smaller string's ngrams are always the ones in the set
let s1 = str1.length < str2.length ? str1 : str2;
let s2 = str1.length < str2.length ? str2 : str1;


let pairs1 = getNGrams(s1, gramSize);
let pairs2 = getNGrams(s2, gramSize);
let set = new Set<string>(pairs1);


let total = pairs2.length;
let hits = 0;
for (let item of pairs2) {
if (set.delete(item)) {
hits++;
}
}
return hits / total;
}

例子:

console.log(stringSimilarity("Dog", "Dog"))
console.log(stringSimilarity("WolfmanJackIsDaBomb", "WolfmanJackIsDaBest"))
console.log(stringSimilarity("DateCreated", "CreatedDate"))
console.log(stringSimilarity("a", "b"))
console.log(stringSimilarity("CreateDt", "DateCreted"))
console.log(stringSimilarity("Phyllis", "PyllisX"))
console.log(stringSimilarity("Phyllis", "Pylhlis"))
console.log(stringSimilarity("cat", "cut"))
console.log(stringSimilarity("cat", "Cnut"))
console.log(stringSimilarity("cc", "Cccccccccccccccccccccccccccccccc"))
console.log(stringSimilarity("ab", "ababababababababababababababab"))
console.log(stringSimilarity("a whole long thing", "a"))
console.log(stringSimilarity("a", "a whole long thing"))
console.log(stringSimilarity("", "a non empty string"))
console.log(stringSimilarity(null, "a non empty string"))

在 TypeScript 游乐场中尝试

小开

模糊排序是一个有助于执行字符串匹配的 javascript 库从大量的数据收集。

下面的代码将有助于在 react.js 中使用模糊排序。

  1. 通过 npm 安装模糊排序,

    npm install fuzzysort

  2. 创建一个引用变量,

    const fuzzysort = require('fuzzysort')

  3. 使用 go ()方法查找匹配的字符串

    search(keyword, category) {
return fuzzysort.go(keyword, data[category]);
}

React.js 中的完整演示代码

import React from 'react';
import './App.css';
import data from './testdata';
const fuzzysort = require('fuzzysort');


class App extends React.Component {
constructor(props){
super(props)
this.state = {
keyword: '',
results: [],
}
console.log("data: ", data["steam_games"]);
}


search(keyword, category) {
return fuzzysort.go(keyword, data[category]);
}


render(){
return (
<div className="App">
<input type="text" onChange={(e)=> this.setState({keyword: e.target.value})}
value={this.state.keyword}
/>
<button onClick={()=>this.setState({results: this.search(this.state.keyword, "steam_games")})}>Search</button>
{this.state.results !== null && this.state.results.length > 0 ?
<h3>Results:</h3> : null
}
<ul>
{this.state.results.map((item, index) =>{
return(
<li key={index}>{item.score} : {item.target}</li>
)
})
}
</ul>
</div>
);
}
}


export default App;

详情请参阅 模糊排序

小开

我喜欢模糊匹配已经很久了然后就遇到了这个问题。这里的讨论比大多数讨论都要深入，而且看起来涉及到了实现者。这些年来，我已经用不同的语言编写了几个这样的算法，并且希望传递一些技巧给那些编写 JS 版本的人:

蒙哥-埃尔坎的规则！

结合了 n-gram 的许多优点和最好的短字符串比较算法，比如 Jaro-Winkler，这真是太棒了。(这就是我在 Monge-Elkan 代码中使用的方法。)几年前，我偶然发现一篇文章，你可以在网上找到一个 PDF 文件，名为 近似文本串比较的广义 Mongue-Elkan 方法。要点是，与其使用 算术平均数，不如使用 二次均值。我尝试了一下，它在搜索结果的 意义重大改进，跨越各种各样的文本。

N 格拉姆规则！

非常健壮，跨多种源语言和文本类型的高质量性能。如果你正在寻找数据库，在 Postgres 有可能实现高质量、快速、索引化的 K-NN 搜索。它需要正确地排列一些不同的特性，但它不是太糟糕。

在任何情况下，当分割 n-gram 时，有不同的方法来处理前端填充。比如，如果你有一个传统的 N(问或者 K)为3，那么你就像这样分割‘ ander’

'  a'
' an'
'and'
'nde'
'der'
'er '
'r  '

或者

'  a'
' an'
'and'
'nde'
'der'

或者

'and'
'nde'
'der'

本能地，我总是期望第一个列表最好，但实际上，它可以是第二个或第三个。值得尝试填充和窗口规则，看看它们在您的上下文中的表现。很少有库提供对这种行为的控制，这将是一个很好的支持特性。提示。

小开

这可以通过使用正则表达式来实现。

例如:

  const fuzzySearch = (list, searchValue) => {
let buf = ".*" + searchValue.replace(/(.)/g, "$1.*").toLowerCase();
var reg = new RegExp(buf);
let newList = list.filter(function (e) {
return reg.test(e.title.toLowerCase());
});
return newList;
};

实例: Https://codesandbox.io/s/jovial-fermat-cilh1?file=/src/app.js:28894-29167


提交答案