假设您正在编写 OST 或网络纠错应用程序。所以你正在处理一个缺少一些字母的单词，比如“*leph*nt”。您将英语词典存储在一个数组中。你如何确定它是哪个词？
问问题
178 次
2 回答
5
一种常见的方法是使用由Levenshtein distance测量的最接近的词。可以任意解决平局，通常使用最大允许距离。
于 2013-03-03T08:10:54.810 回答
3
计算您的查询和所有字典单词之间的 Levenstein 距离肯定会很慢。
BLAST程序对生物序列使用了更好的策略。在 BLAST 中，索引首先建立了一个序列数据库，该数据库将固定长度的小子字符串 K 与包含它们的所有单词的列表相关联。
在查询中，BLAST 在索引中搜索查询字符串中的所有 K 长度子字符串。然后可以扩展查询和索引字符串中的匹配子字符串以快速计算近似 Levenstein 距离，并返回距离低于某个阈值的索引字符串。
于 2013-03-06T01:56:29.833 回答