簡短的Java後綴樹的實現和用法？

我正在尋找一種簡短的，簡單的後綴樹構建/ Java使用算法。迄今爲止，我發現的最好的東西就是使用語義發現工具包，但實現長達數千行，並且跨越多個類。理想情況下，實施將盡可能短並且不超過幾百行。簡短的Java後綴樹的實現和用法？

有沒有人有這樣的實施？

2010-01-11 Stefan Kendall

不，但是我在ruby中寫了一段。如果你想要一個簡短的實現，你應該自己編寫它... char [] c = string.toCharArray（）; for（int i = c.length-1; i> = 0; i ++）recurse（c [i]）... – twolfe18 2010-01-11 15:47:09

將其作爲答案發布，以便我可以對其進行提升。我只需要一些適合我可以輕鬆查閱的紙張。不久，我需要能夠用最少的文檔生成許多算法，所以簡短的實現就是很好的實現。 – 2010-01-11 22:36:59

Karkkainen和Sanders撰寫的文章「簡單的線性工作後綴數組結構」，終止於50行C++。您可能還需要一些產生LCP陣列的東西。谷歌搜索「以線性時間計算LCP陣列，給定S和後綴數組POS。」應該找到你。

來源

2010-01-11 18:57:24 mcdowella

您也可以採取mine但這不是Ukkonen的算法 - 與所有其他簡單方法一樣，它運行在二次時間。我同意一個天真的算法（對於較短的序列可能工作正常）最多可以在半天內輕鬆寫入。

來源

2011-03-07 12:50:29

我剛剛完成了一個後綴樹的Java實現。在我的blog entry中，您可以找到更多關於後綴樹的信息，瞭解如何使用我的庫，以及使用Subversion和Maven下載和構建庫。是的，它不僅僅是一個類文件中的幾行，而且它是高度文檔化的，並且在實際中用於現實世界。此外，它使用Ukkonen方法進行線性時間構造。（這裏提到的大多數實現至少有O（n^2）的運行時間。）

來源

2011-12-15 20:00:08

+1儘管OP沒有規定可擴展性/性能作爲標準，但這些幾乎總是適合我的;因此，獲得線性時間非常重要 - 這也是Uknonnen的方法。當包括這些標準時，這是一個高質量的答案。 – javadba 2013-09-08 18:54:06

簡短的Java後綴樹的實現和用法？

回答

相關問題