内存有效搜索后缀列表

发布时间：2020-12-16 05:04:07 所属栏目：百科来源：网络整理

导读：有一项任务是为其构建某种字典实例的后缀列表： [.,.com.,a.com.,a.b.com.,org.,some.org.,...] 对于每个传入的字符串,对于一个实例“test.some.org”.找到构建字典中最长的后缀.存在一些内存限制.这种情况下最合适的算法/数据结构是什么？对我来说最明显

有一项任务是为其构建某种字典
实例的后缀列表：

[.,.com.,a.com.,a.b.com.,org.,some.org.,...]

对于每个传入的字符串,对于一个实例“test.some.org”.找到构建字典中最长的后缀.存在一些内存限制.这种情况下最合适的算法/数据结构是什么？

对我来说最明显的选择是反向字符串的trie,但它似乎非常耗费内存.我试过使用后缀数组,但看起来它不适合任务.

字典是不可变的,它必须构建一次.不可变尝试的内存效率表示是否更高？

解决方法

对于一组不可变的字符串,compressed trie非常有效.主要思想是将trie中的单个分支表示为一个节点.网上有很多这种方法的有用描述/论文.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!