问题标签 [fuzzy-search]

我需要将来自不同来源的产品名称（相机、笔记本电脑、电视等）自动匹配到数据库中的规范名称。

例如"Canon PowerShot a20IS"、"NEW powershot A20 IS from Canon"和"Digital Camera Canon PS A20IS" 应该都匹配"Canon PowerShot A20 IS"。我已经通过一些额外的启发式（删除明显的常用词，为数字更改分配更高的成本等）来处理 levenshtein 距离，这在某种程度上有效，但不幸的是还不够好。

主要问题是，即使是相关关键字的单个字母变化也会产生巨大的差异，但要检测哪些是相关关键字并不容易。以三个产品名称为例：
Lenovo T400
Lenovo R400
New Lenovo T-400, Core 2 Duo
前两个在任何标准上都是非常相似的字符串（好吧，soundex 在这种情况下可能有助于区分 T 和 R，但名称可能还有400T和400R），第一和第三作为琴弦相距很远，但是是同一个产品。

显然，匹配算法不可能 100% 精确，我的目标是自动匹配大约 80% 的名称，并且置信度很高。

非常感谢任何想法或参考

我正在寻找一种字符串相似性算法，它在可变长度字符串上产生比通常建议的更好的结果（levenshtein distance、soundex 等）。

例如，

给定字符串 A：“Robert”，

然后是字符串 B：“Amy Robertson”

会比

字符串 C：“理查德”

此外，最好该算法应该与语言无关（也适用于英语以外的语言）。

我正在使用 Zend Lucene 为 php 网站构建搜索功能，但遇到了问题。我的网站是店长（类似的东西）。

例如，我有一家名为“FooBar”的商店，但我的访客搜索“Foo Bar”并获得零结果。此外，如果一家商店被命名为“Foo Bar”并且访客搜索“FooBar”，则什么也找不到。

我试图搜索“foobar~”（模糊搜索）但没有找到名为“Foo Bar”的文章

是否有一种特殊的方式来构建索引或进行查询？

I am new to the field of approximate string matching.

I am exploring uses for the Bitap algorithm, but so far its limited pattern length has me troubled. I am working with Flash, and I dispose of 32 bit unsigned integers and a IEEE-754 double-precision floating-point Number type, which can devote up to 53 bits for integers. Still, I would rather have a fuzzy matching algorithm which can handle longer patterns than 50 chars.

The Wikipedia page of the Bitap algorithm mentions libbitap, which supposedly demonstrates an unlimited pattern length implementation of the algorithm, but I have trouble getting the idea from its sources.

Have you got any suggestions about how to generalise Bitap for patterns of unlimited length, or about another algorithm that can perform fuzzy string matching of a needle near a suggested location in the haystack?

I have a mapping of catalog numbers to product names:

and need a search that would find misspelled, mixed names like "warm cmfrter".

We have code using edit-distance (difflib), but it probably won't scale to the 18000 names.

I achieved something similar with Lucene, but as PyLucene only wraps Java that would complicate deployment to end-users.

SQLite doesn't usually have full-text or scoring compiled in.

The Xapian bindings are like C++ and have some learning curve.

Whoosh is not yet well-documented but includes an abusable spell-checker.

What else is there?

我有一张带有个人数据的表格Persons等等。有很多列，但这里曾经感兴趣的是：addressindex，lastname以及向下钻到公寓门口的唯一地址firstname在哪里。addressindex因此，如果我有“如下所示”的两个人，lastname其中一个firstnames是相同的，那么他们很可能是重复的。

我需要一种列出这些重复项的方法。

如果我要在所有列上完全匹配，我知道该怎么做，但我需要模糊匹配才能使用（来自上面的示例）结果如下：

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

我有一个包含大约 500 万条记录的 Postgres 表，我想找到与输入键最接近的匹配项。我尝试在 pg_trgm 模块中使用 trigram，但每次查询大约需要 5 秒，这对于我的需要来说太慢了。

有没有更快的方法在 Postgres 中进行模糊匹配？

我正在为建议和奖励系统开发一个共享点门户，并且需要提醒重复的建议。建议将采用自由文本格式，因此需要模糊搜索。我知道“Damerau-Levenshtein 算法”会进行模糊搜索，但如何在 Sharepoint 门户中实现？Microsoft 搜索服务器可以提供帮助吗？如果是，如何？

我有许多长方体，它们的位置和大小用 minimum 和 maximum和x坐标给出（所以它们平行于主轴）。yz

例如，我可能有以下 3 个长方体：

如果我然后给出一个点（例如(25.3,10.2,90.65)），有没有办法快速确定我在哪个长方体？

• 显然我可以迭代所有的长方体，但可能有数百万个，我需要它比简单的迭代更快（O（log n）或更好的东西会很棒）。

• 这对我来说听起来像是一个“模糊匹配”类型的问题，我注意到Apache Lucene支持范围查询，但这似乎以相反的方式工作（在长方体中找到一个点，而不是在包含一个点的长方体中找到一个点）。

• 稍微复杂一点的是，维度的数量可能大于 3（可能高达 20）；即我可能正在寻找“超长方体”而不是长方体。）

我不确定模糊是否是正确的表达方式，所以请允许我解释一下我想要做什么。

很多时候，我在本地 SVN 工作副本的特定目录中查找我知道的文件，并且我知道它们在哪个目录中，但不想考虑确切的路径，或者可能在不同的分支中有几个副本。例如，假设我想要一个文件“eligibility.py”，我知道它位于“trunk”目录下的某个位置，并且位于该目录下名为“interface”的目录中。

如果我可以在任何文件提示符处输入类似这样的内容，那将是理想的：

有什么办法可以做类似的事情吗？