c# - Dictionary Trie 太大了

Question

我为字典查找类构建了一个 trie。它似乎工作正常，除了 trie 非常大。似乎大约有 80 MB，据我所知，它应该只有 5 MB。我不确定是什么使 trie 气球达到 80 MB，但一旦加载它，它运行的速度非常快。

特里类

public class Trie {


private TrieNode root = new TrieNode();
public const int ASCIIA = 97;

public TrieNode Insert(string word) {

    char[] charArray = word.ToLower().ToCharArray();
    TrieNode node = root;

    foreach (char character in charArray) {
        node = Insert(character, node);

    }

    node.IsEnd = true;
    return root;
}

private TrieNode Insert(char character, TrieNode node) {
    if (node.Contains(character)) {
        return node.GetChild(character);
    } else {
        int number = System.Convert.ToByte(character) - TrieNode.ASCIIA;
        TrieNode treeNode = new TrieNode();
        node.nodes[number] = treeNode;
        treeNode.Value = number;
        return treeNode;
    }

}

TrieNode 类:

public class TrieNode {

public TrieNode[] nodes;
public bool IsEnd {get; set;}
public int Value {get; set;}
public const int ASCIIA = 97;
public const int ENGL = 26;

public TrieNode() {
    nodes = new TrieNode[ENGL]; 
}

public bool Contains(char character) {
    if (character == 0) 
        return false;

    int number = System.Convert.ToByte(character) - ASCIIA;

    if (number > ENGL)
        return false;

    return (nodes[number] != null);
}


public bool Contains(int character) {

    if (character == 0) 
        return false;

    return (nodes[character] != null);
}

public TrieNode GetChild(char character) {
    int number = System.Convert.ToByte(character) - ASCIIA;
    return nodes[number];
}

public TrieNode GetChild(int character) {
    return nodes[character];
}

然后使用包含 170,000 个单词的字典来生成 trie:

    string[] lines = fileTXT.Split("\n"[0]);
for (int i = 0; i < data.Length;i++) {
        trieDict.Insert(data[i]);
}

Answer 1

1. 问题是您正在使用包含 26 个项目的子节点数组。他们中的大多数是空的。基于 32 位或 64 位机器，平均每个节点将需要 26*4 或 26*8 字节。
2. 您正在构造函数中初始化子节点，这意味着，即使您的节点是叶节点，您仍在分配 26*BYTES，这是完全无用的。如果你需要存储 child ，你只分配数组。 TRIE 中的叶节点不需要子数组。
3. 要进一步减小大小，您可以简单地使用按位 Trie，它只需要两个节点，但是，它会增加计算时间并降低性能。 CPU 使用按位 trie 来识别要执行的机器指令。
4. 您可以使用字典而不是数组，它不会分配所有 26 个字母，如本答案 How to create a trie in c# 中所述.您还可以减少默认容量。