假设你在编写一个OST，或者一个网络错误纠正应用程序。你需要处理一个缺少一些字母的单词，比如，“*leph*nt”。你有一个存储在数组中的英语词典。你如何确定它是哪个单词？

回答：

计算你的查询与所有词典单词之间的Levenshtein距离肯定会很慢。

更好的策略是生物序列的BLAST程序所使用的方法。在BLAST中，首先建立一个序列数据库的索引，该索引将固定长度的小子串K与包含它们的单词列表相关联。

在查询时，BLAST会在索引中搜索查询字符串中的所有长度为K的子串。然后，可以通过扩展查询和索引字符串中的匹配子串来快速计算近似的Levenshtein距离，并返回距离低于某个阈值的索引字符串。