Java：在Trie中存儲子字符串

我正在實現一個Trie，它將在字符串中存儲子字符串和它們的出現次數。我的特里結構中的每個節點都有一個名爲children的Map，它將存儲主節點的任何子節點。Java：在Trie中存儲子字符串

我的問題是，最終，這些子節點將擁有自己的子節點，我不知道如何從「地圖內的地圖內的地圖...」中檢索數據。

這是我到目前爲止有：

private class TrieNode 
{ 
    private T data; //will hold the substring 
    int count; //how many occurrences of it were in the string 
    private Map<TrieNode, Integer> children; //will hold subnodes 
    private boolean isWord; //marks the end of a word if a substring is the last substring of a String 

    private TrieNode(T data) 
    { 
     this.data = data; 
     count = 1; 
     children = new HashMap<TrieNode, Integer>(); 
     isWord = false; 
    } 
}

如何從子節點檢索數據，誰自己有可能在他們之下的其他子節點？

P.S.我很抱歉，如果我不能夠清楚地解釋它 - 我有遞歸問題。謝謝。

來源

2012-10-28 Haque1

我不明白爲什麼要將一個字符串存儲在名爲T的類型中。這聽起來像是泛型類型，但是您尚未在類中聲明它。

無論如何，我認爲你需要一個Map<T, TrieNode>，它會保存每個子字段的子字符串。這樣你又回到另一個TrieNode，它又有另一個相同的地圖。

來源

2012-10-28 21:40:30

爲了這篇文章的緣故，讓它更易於理解 - 我說它是一個字符串，但它確實是一個泛型類型。順便說一下，這個節點類是另一個名爲「Trie」的類中的私有類。我在標題中聲明瞭T。 – Haque1

你需要一些東西。首先，你想要Map<T, TrieNode>，因爲你正在將一段數據映射到子Trie。其次，您需要知道如何將您的數據拆分爲頭部和尾部，以及如何在稍後重新組合它們。在字符串的標準情況下，您使用子字符串和concateation。例如：

private TrieNode(String currChar, String rest) { 
    this.data = currChar; 
    this.children = new HashMap<String, TrieNode>(); 
    if(rest.isEmpty()) { 
     this.isWord = true; 
    } else { 
     String head = rest.substring(0, 1); 
     String tail = rest.substring(1, rest.length()); 
     this.children.add(head, new TrieNode(head, tail); 
    } 
}

你T需要能夠做同樣的事情，或擺在首位使用特里就沒有意義了。

此外，您很少需要重新編譯Trie中的字符串。通常，你只是檢查Trie中是否存在字符串，或者有多少個字符串是子字符串。

來源

2012-10-28 22:23:24 ILMTitan

Java：在Trie中存儲子字符串

回答

相關問題