是的,我读到了如何在字符串之间使用编辑距离来决定两个字符串彼此之间的“接近”程度。该算法作为动态问题实现,需要 O(mn) 时间,其中 m 和 n 分别是文本和模式的长度。因此,如果我必须将一个字符串与 5000 多个其他字符串进行匹配,这将花费大量时间,这在我的应用程序中是完全不能接受的。有没有可以实现的更快的解决方案?我不介意用存储空间换取时间。
我在 Android 上看到一个名为“Swype”的应用程序,它执行类似的操作。它根据自己的数据库搜索您的查询并建议结果。怎么会这么快?
注意:请不要推荐像Lucene这样的框架,因为我无法在J2ME上运行。
最佳答案
splix 的回答很好。作为另一种选择(对于非常大的字符串集),您可能需要考虑使用 n-gram 表示:
http://en.wikipedia.org/wiki/N-gram
这些被用于许多数据库包中的近似模式匹配,因为它们使用传统的索引方法可以快速且容易地实现。
关于java - 近似搜索字符串列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6488993/