英语词典的熵

我有一个trie数据结构，存储一系列英语单词 . 例如，给定这些词，字典是这样的：

aa abc aids aimed ami amo b browne brownfield brownie browser brut
butcher casa cash cicca ciccio cicelies cicero cigar ciste conv cony
crumply diarca diarchial dort eserine excursus foul gawkishly he
insomniac mehuman occluding poverty pseud rumina skip slagging
socklessness unensured waspily yes yoga z zoo

蓝色的节点是单词结束的节点 .

在我保存的每个节点中：

• 它代表的字符

• 节点所在的级别

• 一个计数器，指示该节点有多少字"pass"

• 节点的下一个字符的熵 .

我会找到树的每个级别的熵和字典的总熵 .

这是一个类 TrieNode ，它只存在一个节点：

class TrieNode {

    public char content; 
    public boolean isEnd; 
    public double count; 
    public LinkedList<TrieNode> childList; 
    public String path = "";
    public double entropyNextChar;
    public int level;

    ...
 }

这是一个类 Trie ，有一些方法可以操作trie数据结构：

public class Trie {

    ...

    private double totWords = 0; 
    public double totChar = 0; 

    public double[] levelArray; //in each i position of the array there is the entropy of level i 
    public ArrayList<ArrayList<Double>> level; //contains a list of entropies for each level

    private TrieNode root;

    public Trie(String filenameIn, String filenameOut) {
        root = new TrieNode('*'); //blank for root 
        getRoot().level = 0;
        totWords = 0;
    }

    public double getTotWords() {
        return totWords;
    }

    /** 
     * Function to insert word, setta per ogni nodo il path e il livello.
     */
    public void insert(String word) {
        if(search(word) == true) { 
            return;
        }
        int lev = 0;
        totChar += word.length(); 
        TrieNode current = root;
        current.level = getRoot().level;
        for(char ch : word.toCharArray()) { 
            TrieNode child = current.subNode(ch); 
            if(child != null) {
                child.level = current.level + 1;
                current = child;
            }
            else {
                current.childList.add(new TrieNode(ch, current.path, current.level + 1));
                current = current.subNode(ch);
            }
            current.count++;
        }
        totWords++;
        getRoot().count = totWords;
        current.isEnd = true; 
    }

    /**
     * Function to search for word.
     */
    public boolean search(String word) {
        ...
    }

    /**
     * Set the entropy of each node.
     */
    public void entropyNextChar(TrieNode node) {
        for(TrieNode childToCalculate : node.childList) {
            int numberChildren = node.childList.size();
            int i = 0; 
            double entropy = 0.0;
            if(numberChildren > 0) {
                double[] p = new double[numberChildren]; 
                for(TrieNode child : node.childList) { 
                    p[i] = child.count / node.count;
                    i++;
                }
                for(int j = 0; j < p.length; j++) {
                    entropy -= p[j] * log2(p[j]);
                }
                node.entropyNextChar = entropy;
                entropyNextChar(childToCalculate);
            }
        }
    }

    /**
     * Return the number of levels (root has lev = 0).
     */
    public int getLevels(TrieNode node) {
        int lev = 0;
        if(node != null) {
            TrieNode current = node;
            for(TrieNode child : node.childList) {
                lev = Math.max(lev, 1 + getLevels(child));
            }      
        }   
        return lev;
    }

    public static double log2(double n) {
        return (Math.log(n) / Math.log(2));
    }

    ...
}

现在我会找到树的每个级别的熵 .

为此，我创建了以下创建两个数据结构的方法（ level 和 levelArray ） . levelArray 是一个包含结果的double数组，也就是说，在索引 i 中有 i -level的熵 . level 是arrayList的arrayList . 每个列表包含每个节点的加权熵 .

public void entropyEachLevel() {
    int num_levels = getLevels(getRoot());
    levelArray = new double[num_levels + 1];
    level = new ArrayList<ArrayList<Double>>(num_levels + 1);
    for(int i = 0; i < num_levels + 1; i++) {
        level.add(new ArrayList<Double>()); 
        levelArray[i] = 0; //inizializzo l'array
    }
    entropyNextChar(getRoot()); 
    fillListArray(getRoot(), level);
    for(int i = 1; i < levelArray.length; i++) {
        for(Double el : level.get(i)) {
            levelArray[i] += el; 
        }
    }
}

public void fillListArray(TrieNode node, ArrayList<ArrayList<Double>> level) {
    for(TrieNode child : node.childList) { 
        double val = child.entropyNextChar * (node.count / totWords);
        level.get(child.level).add(val);
        fillListArray(child, level);
    }
}

如果我在示例字典上运行此方法，我得到：

[lev 1]  10.355154029112995
[lev 2]  0.6557748405420764
[lev 3]  0.2127659574468085
[lev 4]  0.23925771271992619
[lev 5]  0.17744361708265158
[lev 6]  0.0
[lev 7]  0.0
[lev 8]  0.0
[lev 9]  0.0
[lev 10] 0.0
[lev 11] 0.0
[lev 12] 0.0

问题是我不明白结果是否可能或完全错误 .

另一个问题：我想计算整个字典的熵 . 为此，我想我会添加 levelArray 中的值 . 这是一个类似的程序吗？如果我这样做，我会得到整个字典的熵是 11.64 .

我需要一些建议 . 难怪代码，但我会理解，如果我提出的解决这两个问题的解决方案得到纠正 .

我提出的例子非常简单 . 实际上，这些方法必须适用于大约200800字的真实英语词典 . 如果我在这本词典中应用这些方法，我会得到这样的数字（在我看来是过分的） .

每个级别的熵：

[lev 1]  65.30073504641602
[lev 2]  44.49825655981045
[lev 3]  37.812193162250765
[lev 4]  18.24599038562219
[lev 5]  7.943507700803994
[lev 6]  4.076715421729149
[lev 7]  1.5934893456776191
[lev 8]  0.7510203704630074
[lev 9]  0.33204345165280974
[lev 10] 0.18290941591943546
[lev 11] 0.10260282173581108
[lev 12] 0.056284946780556455
[lev 13] 0.030038717136269627
[lev 14] 0.014766733727532396
[lev 15] 0.007198162552512713
[lev 16] 0.003420610593927708
[lev 17] 0.0013019239303215001
[lev 18] 5.352246905990619E-4
[lev 19] 2.1483959981088307E-4
[lev 20] 8.270156797847352E-5
[lev 21] 7.327868866691726E-5
[lev 22] 2.848394217759738E-6
[lev 23] 6.6648152186416716E-6
[lev 24] 0.0
[lev 25] 8.545182653279214E-6
[lev 26] 0.0
[lev 27] 0.0
[lev 28] 0.0
[lev 29] 0.0
[lev 30] 0.0
[lev 31] 0.0

我认为他们错了 . 并且无法计算整个字典的熵，我认为这个过程的总和太长，以至于我无法看到结果 .

为此，我会理解我所写的方法是否正确 .

非常感谢提前

如果字典是： aaaab 和 abcd ，我有：

所以节点 * 的计数器是2，因为该节点传递两个字 . 对于级别1的节点 a 也是如此 .

我用这种方式改变了方法 entropyNextChar ：

public void entropyNextChar(TrieNode node) {
    for(TrieNode childToCalculate : node.childList) {
        int numberChildren = node.childList.size();
        int i = 0; 
        double entropy = 0.0;
        if(numberChildren > 1) {
            double[] p = new double[numberChildren];
            for(TrieNode child : node.childList) { 
                p[i] = child.count / node.count;
                i++;
            }
            for(int j = 0; j < p.length; j++) {
                entropy -= p[j] * log2(p[j]);
            }
            node.entropyNextChar = entropy;
            entropyNextChar(childToCalculate);
        }
        else {
            node.entropyNextChar = entropy;
            entropyNextChar(childToCalculate);
        }
    }
}

所以我添加 else .