对字符串列表进行近似搜索

Question

所以是的,我读到了如何在字符串之间使用编辑距离来决定两个字符串彼此之间的"接近".该算法作为动态问题实现需要O(mn)时间,其中m和n分别是文本和模式的长度.因此,如果我必须将一个字符串与5000多个其他字符串匹配,则需要花费很多时间,这在我的应用程序中根本不可接受.是否有更快的解决方案可以实施？我不介意交易存储空间的时间.

我在Android上看过一个名为"Swype"的应用程序,它做了类似的事情.它会根据自己的数据库搜索您的查询并建议结果.这怎么快这么快？

注意:请不要建议像Lucene这样的框架,因为我无法在J2ME上运行.

Answer 1

splix的回答很好。作为另一种选择（对于非常大的字符串集），您可能需要考虑使用 n-gram 表示：

http://en.wikipedia.org/wiki/N-gram

它们在许多数据库包中用于近似模式匹配，因为它们使用传统的索引方法可以快速且轻松地实现。