我們如何使用Ukkonen的後綴樹來識別文檔中的所有常見子字符串。 vC++

Question

我想用ukkonen的後綴樹來比較文檔。

在這一點上，我就兩件事：

1. 首先，我試圖生成後綴樹的一個文件，然後使用該後綴樹來查找文檔中所有常見的字符串。

2. 接下來是識別兩個文檔之間的所有常見子字符串。

我能夠基於http://marknelson.us/1996/08/01/suffix-trees/爲文檔生成ukkonen後綴樹。並搜索給定的子字符串。 但我仍然無法找到一種方法來識別給定文檔中的所有常見子字符串。 你能告訴我一個方法來做到這一點。我使用visual C++。

我們可以使用ukkonen的算法來比較兩個documetns並確定它們之間的所有常見子字符串嗎？如果是這樣，請一步一步解釋。

有一個在Ukkonen's suffix tree algorithm in plain English?

Answer 1

對Ukkonen的後綴樹一個很好的解釋。如果你有兩個文件，就可以構造使用Ukkonen算法，接着是後處理步驟來清理不可能配置兩個文件一個generalized suffix tree。

一旦你有一個通用的後綴樹，你可以在樹上運行一個DFS來識別樹中每個具有與每個文檔的後綴對應的葉子的內部節點。這些節點中的每一個對應於兩個文檔共有的子字符串，因爲每個節點都對應於這兩個字符串的後綴的前綴。

從那裏，你可以做任何最合理的與這些子字符串。如果您想要最長的公共子字符串，只需搜索您在第一步中標記的具有最高字符串深度的節點。如果你想找到所有這樣的子字符串，你可以迭代所有這些節點，並打印出你沿途積累的每個子字符串。