2

我为字典查找类构建了一个 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 个单词的字典对 Gen the trie：

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

3 回答 3

2
  1. 问题是您正在使用 26 个项目的子节点数组。其中大部分是空的。平均而言，基于 32 位或 64 位机器，每个节点将需要 26*4 或 26*8 字节。
  2. 您在构造函数中初始化子节点，这意味着，即使您的节点是叶节点，您仍然分配 26*BYTES 这是完全没用的。只有在需要存储子项时才分配数组。TRIE 中的叶节点不需要子数组。
  3. 要进一步减小大小，您可以简单地使用按位 Trie，它只需要两个节点，但是，它会增加计算时间并降低性能。CPU 使用逐位树来识别要执行的机器指令。
  4. 您可以使用 Dictionary 而不是数组，它不会分配所有 26 个字母，如this answer How to create a trie in c#中所述。您还可以减少默认容量。
于 2013-08-21T10:03:16.797 回答
0

您可以做的一件事是将 TrieNode 制作成一个结构，然后避免在初始化后对其进行修改...但是您可能还想做一个内存转储并检查内存，因为它可能不会像您想象的那样占用那么多空间.. . 任务管理器中为进程报告的内存不是您的应用程序使用的内存，而是.NET运行时为您的应用程序保留的内存。

于 2013-06-11T01:07:56.227 回答
0

从大字典创建 trie 时，我遇到了完全相同的问题。所以我用这些词构建了一个DAWG（有向无环词图），它占用的空间非常小（甚至比我的字典还少），保持与 trie 相同的性能，甚至可能更快。它的工作原理是识别单词中的常见后缀和前缀，并从中制作一个有限自动机。如果您的字典是静态的，您可以创建 DAWG 并将其保存到磁盘，然后您可以在应用程序中轻松加载它（它是使用整数数组实现的）。这是一个实现。

于 2013-10-06T07:38:13.303 回答