简短,Java实现后缀树和用法？

Question

我正在寻找一个简短的,简单的后缀树构建/使用Java的算法.到目前为止,我发现的最好的东西在于语义发现工具包,但实现是几千行,并跨越几个类.理想情况下,实现将尽可能短,跨度不超过几百行.

有人有这样的实现吗？

Answer 1

我刚刚完成了后缀树的Java实现.在我的博客文章中,您可以找到有关后缀树的更多信息,了解如何使用我的库,以及使用Subversion和Maven下载和构建库.是的,它比单个类文件中的几行更长,但它是高度记录的,并且是为了实际目的而在现实世界中创建的.此外,它使用Ukkonen方法进行线性时间构造.(这里提到的大多数实现至少有O(n ^ 2)运行时间.)

Answer 2

Karkkainen 和 Sanders 撰写的文章“简单线性工作后缀数组构造”以 50 行 C++ 结尾。您可能还需要一些东西来生成 LCP 阵列。谷歌搜索“给定 S 和后缀数组 POS，以线性时间计算 LCP 数组”。应该找到你。