假设你在编写一个OST,或者一个网络错误纠正应用程序。你需要处理一个缺少一些字母的单词,比如,“*leph*nt”。你有一个存储在数组中的英语词典。你如何确定它是哪个单词?
回答:
计算你的查询与所有词典单词之间的Levenshtein距离肯定会很慢。
更好的策略是生物序列的BLAST程序所使用的方法。在BLAST中,首先建立一个序列数据库的索引,该索引将固定长度的小子串K与包含它们的单词列表相关联。
在查询时,BLAST会在索引中搜索查询字符串中的所有长度为K的子串。然后,可以通过扩展查询和索引字符串中的匹配子串来快速计算近似的Levenshtein距离,并返回距离低于某个阈值的索引字符串。