Trie:Java中的Trie和Levenshtein距离混合实现可实现极快的前缀字符串搜索和字符串相似性 源码

Java中的Trie和Levenshtein距离混合实现,可实现极快的前缀字符串搜索和字符串相似性。 作者:Umberto Griffo 推特:@UmbertoGriffo 内容 特里定义 Trie [1]是使用字符串作为键的有序树数据结构。 这是一种有效的信息检索数据结构,可用于在O(M)时间内搜索单词,其中M是最大字符串长度。 但是,惩罚是根据Trie存储要求。 特里的一种常见应用是存储诸如在移动电话上找到的预想文本或自动完成词典。 这样的应用程序利用了trie的能力来快速搜索,插入和删除条目。 下图显示了带有键“ Joe”,“ John”,“ Johnny”,“ Johnny”,“