我正在寻找一种简短、简单的 Java 后缀树构建/使用算法。到目前为止，我发现的最好的是 Semantic Discovery Toolkit，但它的实现有几千行长并且跨越了几个类。理想情况下，实现应该尽可能短，并且不超过几百行。
有没有人有这样的实现？
问问题
9965 次
3 回答
5
我刚刚完成了后缀树的 Java 实现。在我的博客文章中，您可以找到有关后缀树的更多信息，了解如何使用我的库，以及使用 Subversion 和 Maven 下载和构建库。是的，它不仅仅是一个类文件中的几行，但它是高度记录的，并且是为了实际目的而在现实世界中使用而创建的。此外，它使用 Ukkonen 方法进行线性时间构造。（这里提到的大多数实现至少有 O(n^2) 的运行时间。）
于 2011-12-15T20:00:08.623 回答
1
Karkkainen 和 Sanders 的文章“简单线性工作后缀数组构造”以 50 行 C++ 结束。您可能还需要一些东西来生成 LCP 阵列。谷歌搜索“在给定 S 和后缀数组 POS 的情况下，以线性时间计算 LCP 数组。” 应该找到你。
于 2010-01-11T18:57:24.077 回答
0
您也可以采用我的算法，但这不是 Ukkonen 的算法 - 与所有其他简单方法一样，它以二次时间运行。我同意一个简单的算法（对于较短的序列可能工作正常）最多半天就很容易编写。
于 2011-03-07T12:50:29.017 回答