C＃中的內存不足異常＃

Question

我試圖構造一個後綴trie，並且由於嚴格的要求，它必須在內存中編入索引。

編輯：問題不是樹本身，而是實際上我讀取文件的方式。

Answer 1

如果您將整個文本文件作爲一個單獨的string傳遞，您可能很容易在第一個循環中遇到內存不足異常！

// imagine if s.Length was 100k or so 
for (int i = 0; i < s.Length; i++) 
{ 
    AddString(s.Substring(i, s.Length-i)); 
} 

當讀取文件，構建線索，你需要拆分每一行，並可能正常化的人物：（從dir /b c:\windows的輸出）

string line; 
while (null != (line = reader.ReadLine())) 
{ 
    string[] parts = line.Split(' ', ',', '.', '!', '\t', '?'); // naive 
    foreach (string part in parts) 
    { 
     if (part.Length > 0) 
     { 
      // make each string uppercase so as to avoid Hello and hello being 
      // two trie entries 
      trie.AddSuffix(part.ToUpperInvariant()); 
     } 
    } 
} 

例如：

A 
D 
    D 
    I 
    N 
    S 
    E 
    D 
P 
    P 
    C 
    O 
    M 
     P 
     A 
     T 
    P 
    A 
    T 
     C 
     H 
... 

---

爲了適當地處理較大的文件，需要更緊湊的特里結構。我只想有存儲在一個單獨的字典非共享後綴：

// If you add a character, but there is no entry in m_children 
// just park the tail end of it here 
Dictionary<char, string> m_tails; 

你會然後將每個字符的邏輯，你的AddString的SuffixNode：

public void AddString(string s) 
{ 
    if (s.Length == 0) return; 

    char c = s[0]; 
    if (m_children.ContainsKey(c)) 
    { 
     if (s.Length > 1) m_children[c].AddString(s.Substring(1)); 
    } 
    else if (m_tails.ContainsKey(c)) 
    { 
     SuffixNode node = new SuffixNode(); 
     node.AddString(m_tails[c]); 
     if (s.Length > 1) node.AddString(s.Substring(1)); 

     m_children.Add(c, node); 
     m_tails.Remove(c); 
    } 
    else 
    { 
     m_tails.Add(c, s.Length > 1 ? s.Substring(1) : ""); 
    } 
} 

現在你有一個更緊湊版這將大大減少爲任何給定語料庫創建的兒童數量。返回到dir /b c:\windows例子中，我們可以看到在節點實際減少：

A 
P 
    P 
    COMPAT 
    PATCH 
    I 
T 
    I 
    O 
    N 
    S 
... 

此時您的線索有更高效的表現。您需要確定如何處理終端節點表示，以確保查找的準確性。