字典太大了

本文关键字：大了 字典 | 更新日期: 2023-09-27 18:17:44

我为字典查找类构建了一个tree。它似乎工作得很好，只是这个树非常非常大。大概有80mb，据我所知应该只有5mb大。我不确定是什么让这个trie气球达到80mb，一旦加载，它运行得非常快。

单词查找树类

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个单词的字典:

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

字典太大了

  1. 问题是您正在使用26项的子节点数组。大多数都是空的。基于32位或64位机器，每个节点平均需要26*4或26*8字节。
  2. 你在构造函数中初始化子节点，这意味着，即使你的节点是叶节点，你仍然分配26*字节，这是完全无用的。只有在需要存储子元素时才分配数组。
  3. 为了进一步减小尺寸，您可以简单地使用bit - wise Trie，它只需要两个节点，但是，它增加了计算时间并降低了性能。
    4. cpu使用位尝试来识别要执行的机器指令。
  4. 你可以使用字典代替数组，它不会分配所有26个字母，正如在这个回答中提到的如何在c#中创建一个trie。你也可以减少默认容量。

你可以做的一件事是把TrieNode变成一个结构体，然后在初始化后避免修改它…然而，你可能也想做一个内存转储和检查内存，因为它可能不会占用你想象的那么多空间…任务管理器中报告的进程内存不是应用程序使用的内存，而是. net运行时为应用程序保留的内存。

我在从一个大字典创建一个trie时遇到了完全相同的问题。因此，我用这些单词构造了一个DAWG(有向无循环词图)，它占用的空间非常小(甚至比我的单词字典还小)，保留了与trie相同的性能，甚至更快。它的工作原理是识别单词中常见的后缀和前缀，并从中产生有限的自动机。如果字典是静态的，则可以创建DAWG并将其持久化到磁盘，并且可以轻松地在应用程序中加载它(它是使用整数数组实现的)。下面是一个实现:

相关文章：