字符串匹配算法

Question

我有一个商业数据库的Python应用程序，我希望能够按名称搜索业务（用于自动完成的目的）。
例如，考虑名称“最好买”，“麦当劳”，“索尼”和“苹果”。

我想“应用程序”返回“苹果”，以及“APPEL”和“PLE”。 “麦当劳”应该返回“麦当劳”。 “bst b”和“best-buy”都应该返回“best buy”。

我正在寻找哪种算法，并且它是否具有python实现？

谢谢！

Answer 1

该Levenshtein distance应该做的。

环顾四周 - 有许多语言的实现。

Answer 2

Soundex或Metaphone可能工作。

Answer 3

我想你正在寻找的是数据质量和数据清理的一个巨大的领域。我担心如果你能找到一个关于这个python的实现，因为它必须能够清理大量数据库中可能具有商业价值的数据。

Answer 4

Levenshtein距离将做到这一点。

注：这是一个距离，你必须把它计算到数据库中的每一个字符串，它可以是一个大问题，如果你有很多条目。

如果你有那么这个问题记录所有的错别字用户作出（错字=没有直接匹配）和离线建立包含所有typo->修改映射修正数据库。有些公司这样做更聪明，例如：谷歌观察用户如何纠正自己的拼写错误，并从中学习映射。

Answer 5

Levensthein距离走向正确的方向，但只有一半的路。有几个技巧可以让它使用半场比赛。

一个将是使用一个子序列动态时间规整（DTW实际上是levensthein距离的概括）。为此，您在计算成本矩阵时放宽开始和结束案例。如果您只放松其中一个条件，则可以通过拼写检查自动完成。我不确定是否有可用的python实现，但如果你想自己实现它，它不应该超过10-20 LOC。

另一个想法是使用一个特里的加快，它可以在多个结果呢DTW/Levensthein同时放（速度大大提高了，如果你的数据库很大）。在IEEE的Tries上有一篇关于Levensthein的论文，所以你可以在那里找到算法。再次为此，您需要放松最终边界条件，以便获得部分匹配。然而，由于你在树中下台，你只需要检查什么时候你已经完全消耗了输入，然后返回所有树叶。

Answer 6

检查这一项http://docs.python.org/library/difflib.html 它应该帮助你