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 
... 

此时您的线索有更高效的表现。您需要确定如何处理终端节点表示，以确保查找的准确性。