logo标签列表

有哪些好用的 C++ 后缀字典树库？

c++algorithmtreenlptrie
23

有没有人知道一个非常可靠的C++后缀树库，除了Mummer中的库？
理想情况下，我希望：
一些并发概念。
良好的缓存行为。
宽松的许可证。
支持任意字母表。

看起来有人提出了一个关于Boost GSoC项目的建议 - http://lists.boost.org/Archives/boost/2009/04/150393.php，不过目前还没有找到任何结果。 - Flexo
似乎已经有至少一个有前途的库，实际上是从这个跟进中得出的结论：http://code.google.com/p/patl/ - Flexo
@awoodland：太棒了，我特别喜欢具有可选操作支持的Levenshtein迭代器的链接。 - Matthieu M.
Patl非常可靠，我忘记它有后缀tries。你想把它作为答案吗？ - Jake Kurzer
3个回答
10
作为一个生物信息学家，我的选择是SeqAn（请查看序列索引部分）。它实现了惰性后缀树和增强型后缀数组（一种等效的数据结构），两者都具有良好的缓存行为。
1
哦！这是我没听说过的一个，而且还带有后缀数组！太棒了。 - Jake Kurzer
1
点赞。我喜欢这个库的全局功能。我刚开始探索它。我认为应该提到的是，对于某些任务来说，它可能不够快。个人初步比较表明，例如使用seqan :: Alphabet时，即使使用Array-Alloc for Strings，事情也会显着变慢（与使用std :: vector of std :: string作为字母表相比）。可能是传统的舒适度与速度之间的抉择。 - Shadow
2

我曾经使用过PATL，但现在已经忘记了它，我想在回答中添加一个链接。
http://code.google.com/p/patl/
它有一些非常独特的功能，并且阅读起来也很愉快。

1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接