标签: fuzzy-search

我正在寻找一种字符串相似度算法,它可以在变长字符串上产生比通常建议的更好的结果(levenshtein距离,soundex等).

例如,

鉴于字符串A:"罗伯特",

然后是字符串B:"Amy Robertson"

会比一个更好的比赛

字符串C:"理查德"

此外,优选地,该算法应该是语言不可知的(也可以用于除英语之外的语言).

我正在寻找一个模糊搜索JavaScript库来过滤数组.我已经尝试过使用fuzzyset.js和fuse.js,但结果非常糟糕(你可以尝试在链接页面上进行演示).

在对Levenshtein距离进行一些阅读之后,它让我感到很难接近用户在打字时所寻找的内容.对于那些不知道的人,系统会计算需要多少插入,删除和替换才能使两个字符串匹配.

在Levenshtein-Demerau模型中固定的一个明显的缺陷是blub和boob被认为与灯泡同样相似(每个需要两次替换).然而,很明显,灯泡更像blub而不是bob,而我刚才提到的模型通过允许换位来识别它.

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

所以我正在寻找(并且如果它不存在则会创建),是一个执行以下操作的库:

• 权衡不同的文本操作
• 每个操作的权重取决于它们在单词中出现的位置(早期操作比后期操作更昂贵)
• 返回按相关性排序的结果列表

有没有人遇到这样的事情？我意识到StackOverflow不是要求软件推荐的地方,但上面隐含的(不再是!)是:我正在考虑这个正确的方法吗？

编辑

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

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

Monger-Elkan距离函数(Monge&Elkan 1996),它是Smith-Waterman距离函数的一个仿射变体(Durban et al.1998),具有特定的成本参数

对于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扩展.这几乎与Monge-Elkan方案一样,但速度提高了一个数量级.组合TFIDF方法和Jaro-Winkler的一种简单方法是使用基于Jaro-Winkler方案的近似令牌匹配替换TFIDF中使用的确切令牌匹配.这种组合平均比Jaro-Winkler或TFIDF略好,并且偶尔表现得更好.对于本文中考虑的几个最佳指标的学习组合,它的性能也很接近.

我正在寻找一个用于模糊字符串搜索的高性能Java库.

有许多算法可以找到类似的字符串,Levenshtein距离,Daitch-Mokotoff Soundex,n-gram等.

存在哪些Java实现？他们的利弊？我知道Lucene,任何其他解决方案或Lucene最好吗？

我找到了这些,有没有人有过这些经历？

• SimMetrics
• NGramJ

我有一个表的人与personaldata等.有很多专栏,但这里曾经感兴趣的是:addressindex,lastname以及firstname在addressindex公寓门口钻一个独特的地址.因此,如果我"喜欢下面"两个人和lastname一个人firstnames相同,他们很可能是重复的.

我需要一种方法来列出这些重复项.

tabledata:

personid     1
firstname    "Carl"
lastname     "Anderson"
addressindex 1

personid     2
firstname    "Carl Peter"
lastname     "Anderson"
addressindex 1

我知道如果我要在所有列上完全匹配,但是我需要模糊匹配来完成这个技巧(来自上面的例子),结果如下:

Row     personid      addressindex     lastname     firstname
1       2             1                Anderson     Carl Peter
2       1             1                Anderson     Carl
.....

关于如何以一种好的方式解决这个问题的任何提示？

我的用户将通过剪切和粘贴一个包含公司名称的大字符串来导入.

我有一个现有的,不断增长的公司名称MYSQL数据库,每个都有一个独特的company_id.

我希望能够解析字符串并为每个用户输入的公司名称分配模糊匹配.

现在,只是做一个直接的字符串匹配,也很慢.**Soundex索引会更快吗？如何在用户输入时为用户提供一些选项？**

例如,某人写道:

Microsoft       -> Microsoft
Bare Essentials -> Bare Escentuals
Polycom, Inc.   -> Polycom

我发现以下线程似乎与此问题类似,但海报尚未批准,我不确定他们的用例是否适用:

如何在大型字符串数据库中找到字符串的最佳模糊匹配

在Java中匹配不精确的公司名称

在我的工作中,我得到了很好的结果,使用了近似字符串匹配算法,如Damerau-Levenshtein距离,使我的代码不易受到拼写错误的影响.

现在我需要将字符串与简单的正则表达式匹配TV Schedule for \d\d (Jan|Feb|Mar|...).这意味着字符串TV Schedule for 10 Jan应返回0,同时T Schedule for 10. Jan应返回2.

这可以通过在正则表达式中生成所有字符串(在这种情况下为100x12)并找到最佳匹配来完成,但这并不实用.

您有任何想法如何有效地做到这一点？

我想创建一个模糊搜索算法.然而,经过数小时的研究,我真的很挣扎.

我想创建一个算法,在学校名称列表上执行模糊搜索.

这是我到目前为止所看到的:

我的大部分研究都指向Google和Stackoverflow上的" 字符串指标 ",例如:

• Levenshtein距离
• Damerau-Levenshtein距离
• Needleman-Wunsch算法

然而,这仅仅给出了两个字符串相似的分数.我可以想到将其实现为搜索算法的唯一方法是执行线性搜索并对每个字符串执行字符串度量算法,并返回分数高于某个阈值的字符串.(原来我把我的琴弦存放在一棵树上,但这显然不会帮助我!)

虽然这对于小型列表来说并不是一个坏主意,但对于名为100,000个名称的列表来说,这将是一个问题,并且用户执行了许多查询.

我看到的另一种算法是拼写检查方法,您只需搜索所有可能的拼写错误.然而,这也是非常低效的,因为对于长度为7的单词而言需要超过75,000个单词并且错误计数仅为2.

我需要的？

有人可以建议我一个很好的高效模糊搜索算法.有:

• 算法的名称
• 它是如何工作的或它是如何工作的链接
• Pro和cons以及何时最佳使用(可选)

我知道所有算法都有其优点和缺点,没有最好的算法.

我在哪里可以找到一些真实的拼写错误统计数据？

我试图将人们的输入文本与内部对象进行匹配,人们往往会犯拼写错误.
有两种错误:

1. typos - "Helllo"而不是"Hello"/"Satudray"而不是"Saturday"等.
2. Spelling - "Shikago"而不是"芝加哥"

我使用 Damerau-Levenshtein距离进行拼写错误,使用Double Metaphone进行拼写(Python实现此处和此处).

我想专注于Damerau-Levenshtein(或简单地说edit-distance).教科书实现总是使用'​​1'来表示删除,插入替换和转置的权重.虽然这很简单并且允许很好的算法但它与"现实"/"真实世界概率"不匹配.

例子:

• 我确定"Helllo"("Hello")的可能性大于"Helzlo",但它们距离都是1个编辑距离.
• 在QWERTY键盘上,"Gello"比"Qello"更接近"Hello".
• Unicode音译:"慕尼黑"和"慕尼黑"之间的"真实"距离是多少？

删除,插入,替换和转置的"真实世界"权重应该是什么？

即使是Norvig非常酷的拼写校正器也使用非加权编辑距离.

BTW-我确定权重需要是函数而不是简单的浮点数(根据上面的例子)......

我可以调整算法,但在哪里可以"学习"这些权重？我无法访问Google规模的数据 ...

我应该猜猜他们吗？

编辑 - 尝试回答用户问题:

• 由于上述原因,我当前的非加权算法在遇到拼写错误时经常失败."星期四回归":每个"真人"都可以很容易地告诉周四比周二更有可能,但他们都是1编辑距离!(是的,我会记录并衡量我的表现).
• 我正在开发NLP旅行搜索引擎,因此我的词典包含~25K目的地(预计将增长到100K),时间表达式~200(预期1K),人物表达式~100(预期300),货币表达式~100(预期500 ),"胶水逻辑词"("从","美丽","公寓")~2K(预计10K)等...
• 对于上述每个单词组,编辑距离的使用是不同的.我尝试"在明显时自动纠正",例如,与字典中的另一个单词相距1个编辑距离.我有许多其他手动调整的规则,例如Double Metaphone修复,距离长度> 4的字典单词不超过2个编辑距离...当我从现实世界输入中学习时,规则列表继续增长.
• "你的门槛中有多少对字典条目？":嗯,这取决于"花式加权系统"和现实世界(未来)输入,不是吗？无论如何,我进行了大量的单元测试,因此我对系统所做的每一项更改都会使其更好(当然,基于过去的输入).大多数6个字母的单词距离与另一个字典条目相距1个编辑距离的单词在1个编辑距离内.
• 今天,当有两个字典条目与输入相同的距离时,我尝试应用各种统计数据来更好地猜测用户的意思(例如,巴黎,法国更有可能出现在我的搜索中,而不是Pārīz,伊朗).
• 选择错误单词的成本是将半随机(通常是荒谬的)结果返回给最终用户并可能失去客户.不理解的成本稍微低一些:用户将被要求改写.
• 复杂的成本值得吗？是的,我确定是的.你不会相信人们在系统中投入的拼写错误,并希望它能理解,我确信可以使用Precision和Recall中的提升.

使用像leveinstein(leveinstein或difflib)这样的算法,很容易找到近似匹配.

>>> import difflib
>>> difflib.SequenceMatcher(None,"amazing","amaging").ratio()
0.8571428571428571

可以通过根据需要确定阈值来检测模糊匹配.

当前要求:根据较大字符串中的阈值查找模糊子字符串.

例如.

large_string = "thelargemanhatanproject is a great project in themanhattincity"
query_string = "manhattan"
#result = "manhatan","manhattin" and their indexes in large_string

一个强力解决方案是生成长度为N-1到N + 1(或其他匹配长度)的所有子串,其中N是query_string的长度,并且逐个使用levenstein并查看阈值.

python中是否有更好的解决方案,最好是python 2.7中包含的模块,或外部可用的模块.

更新:Python正则表达式模块工作得很好,虽然它比re模糊子字符串情况的内置模块慢一点,由于额外的操作,这是一个明显的结果.期望的输出是良好的,并且可以容易地定义对模糊度的控制.

>>> import regex
>>> input = "Monalisa was painted by Leonrdo da Vinchi"
>>> regex.search(r'\b(leonardo){e<3}\s+(da)\s+(vinci){e<2}\b',input,flags=regex.IGNORECASE)
<regex.Match object; span=(23, 41), match=' Leonrdo da Vinchi', fuzzy_counts=(0, 2, 1)>

有没有人根据模糊匹配创建或看到一个闪亮的应用程序,其中包含搜索框小部件,在您键入时提供上下文建议？

彭博终端使用它,谷歌使用它.其中一种可能的底层技术叫做elasticsearch.org模糊查询,有两个R实现:

1. duncantl/RElasticSearch
2. ropensci/elastic

搜索框过滤器的基本到来Shiny的数据表并不完全切断它.

如果这是尚未与Shiny集成的内容,那么任何粗略的指南如何构建它？我怀疑当你想查找特定的行而没有显示完整的表时,它对于包含大量文本的biggish表(或文档)非常有用.