如何在没有大量数据库的情况下进行模糊字符串搜索？

Question

我有目录号到产品名称的映射：

35  cozy comforter
35  warm blanket
67  pillow

并且需要进行搜索以查找拼写错误的混合名称，例如“warm cmfrter”。

我们有使用编辑距离 (difflib) 的代码，但它可能无法扩展到 18000 个名称。

我使用 Lucene 实现了类似的目标，但由于 PyLucene 只包装了 Java，这会使最终用户的部署变得复杂。

SQLite 通常不会编译全文或评分。

Xapian 绑定 是喜欢 C++ 并且有一些学习曲线。

Whoosh 尚未有详细记录，但包含一个可滥用的拼写检查器。

那里还有什么？

Answer 1

显然，快速进行模糊比较的唯一方法是少做一些；）

我们现在保留一个单词索引，而不是编写另一个 n-gram 搜索或改进 Whoosh 中的搜索，而是检索至少具有一个（拼写正确）的所有条目与查询相同的单词，并使用 difflib 对它们进行排名。 在这种情况下效果很好。

Answer 2

使用 SOUNDEX 实现时，您会收到太多误报。 仅有 26,000 个（最多）可能的 SOUNDEX 代码。

尽管 Metaphone 算法是为英语姓氏设计的，但它对于拼写错误也非常有效。 我在分支定位器中使用过一次，非常成功。

添加一个包含变音位翻译的字段，如果未找到完全匹配，则与其进行匹配。 您仍然会得到误报，但使用其他算法时会更少。

Answer 3

核
有全文搜索，但不支持拼写错误的匹配
盒子外面。 您可以尝试为每个条目添加一个附加字段
它索引了
SOUNDEX 术语翻译，然后使用 soundex 翻译进行搜索
用户输入的。 我真的不知道这会有多好...

看看 advas < a href="http://advas.sourceforge.net/news.php" rel="nofollow noreferrer">http://advas.sourceforge.net/news.php 其中有一个很好的演示比较各种 soundex -类似的方法：

advas/examples Aaron$ python phonetic_algorithms.py 
                    soundex       metaphone           nyiis      caverphone 
====================================================================================================
 schmidt :             S253           sxmtt          sssnad      SKMT111111
  schmid :             S253            sxmt          sssnad      SKMT111111
 schmitt :             S253            sxmt         sssnatt      SKMT111111
   smith :             S530            sm0h           snatt      SMT1111111
  smythe :             S530           smy0h           snatt      SMT1111111
 schmied :             S253            sxmt         sssnaad      SKMT111111
   mayer :             M600             myr           naaar      MA11111111
   meier :             M600              mr           naaar      MA11111111
....

我不知道它们是否适合您的未命名语言......

Answer 4

计算两个字符串之间的编辑距离的常用方法是一种相当昂贵的算法（如果我没记错的话，它的时间复杂度是二次的）。 也许如果您使用不同的字符串相似性度量，那么您的问题就会消失。

我最喜欢的模糊字符串匹配方法之一是三元组匹配。 使用此方法比较两个字符串具有线性时间复杂度，这比提到的编辑距离要好得多。 您可以在 Github 上找到我的 Python 实现。 还有一个 PostgreSQL contrib 模块 正是用于此目的。 使其与 SQLite3 配合使用应该不会太困难。

Answer 5

Sybase SQL Anywhere 有免费的网络版/开发版，并附带全文索引/搜索和 FUZZY 运算符（以及一些实现限制）。

引用文档：

Specifying 'FUZZY "500 main street"' is equivalent to 
'500 OR mai OR ain OR str OR tre OR ree OR eet'. 

另一种方法是对全文搜索使用评分。

Answer 6

sqlite3支持python回调函数。 Matthew Barnett 的正则表达式 (http://code.google.com/p/mrab-regex-hg/) 现在支持近似匹配。

所以，像这样：

try:
    import regex
except ImportError:
    sys.stderr.write("Can't import mrab-regex; see http://pypi.python.org/pypi/regex\n")
    sys.exit(1)

def _sqlite3_regex(expr, item):
    return (not (not regex.search(expr, item)))

def main():
    ...
    database = sqlite3.connect(dbfile)
    database.create_function("regexp", 2, _sqlite3_regex)
    pattern = '(?:%s){e<=%d}' % (queriedname, distance)
    print [x for x in database.cursor().execute(
         "SELECT * FROM products WHERE (productname regexp '%s')" % pattern)]