JAN*_*JAN 5 algorithm tree suffix-tree trie data-structures
我已经看了这个问题,但我仍然没有看到后缀树和Trie之间的区别.
两者都具有给定字符串的所有子字符串,因此它们彼此之间有何不同？
Bau*_*han 14
后缀树 - 给出了一个大文本.查询 - 多次搜索文本中的任何单词.
示例:您正在实现自己的酷文本编辑器与纸牌和小猫=)您将实现CTRL+F功能.可能的实现 - 索引文档(创建后缀树)以及当用户查找某个单词时 - 在树中搜索它.
Trie - 给出了一个大文本.查询 - 在文本中多次搜索预定义的单词.
示例:您正在使用扑克和Justin Bieber的粉丝实施您自己的酷Facebook =)您不希望您的用户发布脏话.可能的实现 - 创建一些发誓的话.当用户键入一些文本搜索biiden字时,用*替换它们.
通常,后缀tree = trie.后缀树是某些单词的所有后缀的trie.当你想在字典中搜索某些东西时使用trie.当您在纯文本中搜索某些内容时,请使用后缀树.
重要说明 - 为大文本构建/重建后缀树是一项复杂的操作.更改文本后,必须重新创建后缀树.重建trie是一项微不足道的操作 - 只需添加新词即可O(wordLength)
结论
后缀树.您对未来的查询一无所知.为创建后缀树花费一次时间,您就可以处理请求了.已知信息是一个文本.请求未知但给出文本而不会经常更改的情况是使用后缀树的候选者.例如,你不能在CTRL+F实现中使用trie(aho-corasick算法)- 因为你根本不能将字典作为基于trie的aho-corasick算法的输入.
特里.您对将要执行搜索的文本一无所知. 但是你知道未来的疑问.花时间为您的查询预处理/准备数据结构,您可以在任何文本中执行搜索查询.例如,在替换禁止的单词任务时,您不知道用户将发布什么文本但您知道禁止的单词.为每个简短的新帖子创建后缀树太愚蠢了=)