如何在不使用大型数据库的情况下进行模糊字符串搜索？

Question

我有一个目录编号和产品名称的对应关系：

35  cozy comforter
35  warm blanket
67  pillow

我需要一个搜索功能，可以找到拼写错误或混合名称，比如“warm cmfrter”。

我们有使用编辑距离（difflib）的代码，但可能无法处理18000个名称。

我用Lucene实现过类似的功能，但因为PyLucene只是Java的一个封装，这样会让最终用户的部署变得复杂。

SQLite通常没有完整的文本搜索或评分功能。

Xapian绑定像C++一样，有一定的学习曲线。

Whoosh的文档还不够完善，但它包含一个可以用的拼写检查器。

还有其他的选择吗？

Answer 1

Nucular 这个工具可以进行全文搜索，但它默认不支持拼写错误的匹配。你可以尝试给每个条目添加一个额外的字段，用来存储这些词的SOUNDEX 转换结果，然后用用户输入的声音转换来进行搜索。我其实也不太确定这样做效果如何...

你可以看看 advas 的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 2

使用SOUNDEX这个方法，你会遇到很多错误的匹配结果。因为SOUNDEX代码最多只有26,000种可能。

虽然Metaphone算法是为英语姓氏设计的，但它对拼写错误的处理效果也不错。我曾经在一个查找分支的项目中用过这个算法，效果还挺好的。

可以添加一个字段来存储Metaphone的转换结果，如果找不到完全匹配的结果，就用这个字段来进行匹配。这样你还是会遇到一些错误的匹配，但比其他算法要少一些。

Answer 3

显然，要让模糊比较变得快速，最好的办法就是减少比较的次数；)

我们没有再写一个新的n-gram搜索，也没有改进Whoosh里的那个。现在我们保持一个单词索引，找出所有与查询中至少有一个（拼写正确的）单词相同的条目，然后用difflib来给这些条目排序。在这种情况下，这个方法效果还不错。