Ich habe eine Trie-Datenstruktur, die eine Folge von englischen Wörtern speichert. Zum Beispiel angesichts dieser Worte ist das Wörterbuch diese:Entropie des englischen Wörterbuchs
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
Die Knoten in blau sind solche, bei denen ein Wort beendet ist.
in jedem Knoten I gespeichert:
- das Zeichen, dass es bei dem
- der Pegel repräsentiert der Knoten
- einen Zähler befindet, die, wie viele Wörter "pass" bedeutet, für diesen Knoten
- die Entropie des nächsten Zeichens des Knotens.
Ich würde die Entropie für jede Ebene des Baumes und die gesamte Entropie des Wörterbuchs finden.
Dies ist ein Stück der Klasse TrieNode, die einen einzelnen Knoten rapresent:
class TrieNode {
public char content;
public boolean isEnd;
public double count;
public LinkedList<TrieNode> childList;
public String path = "";
public double entropyNextChar;
public int level;
...
}
Und das ist ein Stück der Klasse Trie mit einigen Methoden der Trie-Datenstruktur zu manipulieren:
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));
}
...
}
Jetzt Ich würde die Entropie jeder Ebene des Baumes finden.
Dazu habe ich die folgende Methode erstellt, die zwei Datenstrukturen erstellt (level und levelArray). levelArray ist ein Array von Doppel mit dem Ergebnis, das heißt, in dem Index i gibt es die Entropie der i-Ebene. level ist eine ArrayList von ArrayList. Jede Liste enthält die gewichtete Entropie jedes Knotens.
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);
}
}
Wenn ich diese Methode auf die Probe Wörterbuch betreibe ich bekommen:
[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
Das Problem ist, dass ich nicht verstehe, wenn das Ergebnis wahrscheinlich oder völlig falsch ist.
Ein weiteres Problem: Ich möchte die Entropie des gesamten Wörterbuchs berechnen. Um dies zu tun, dachte ich, ich würde die Werte in levelArray hinzufügen. Es ist richtig ein Verfahren so? Wenn ich das tue, bekomme ich, dass die Entropie des gesamten Wörterbuchs 11.64 ist.
Ich brauche einen Rat. Kein Wunder Code, aber ich würde verstehen, wenn die Lösungen, die ich vorgeschlagen habe, um die beiden Probleme zu beheben, korrigiert werden.
Das von mir vorgeschlagene Beispiel ist sehr einfach. In der Realität müssen diese Methoden auf einem echten englischen Wörterbuch von ungefähr 200800 Wörtern funktionieren. Und wenn ich diese Methoden in diesem Wörterbuch anwende, bekomme ich Zahlen wie diese (meiner Meinung nach exzessiv).
Entropy für jede Ebene:
[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
Ich glaube, sie sind falsch. Und die Entropie des gesamten Wörterbuchs kann nicht berechnet werden, ich denke, dass die Summe ein Prozess zu lang ist, so dass ich nicht in der Lage bin, das Ergebnis zu sehen.
Dafür würde ich verstehen, wenn die Methoden, die ich geschrieben habe, richtig sind.
Vielen Dank im Voraus
Bei Wörterbuch ist: aaaab und abcd, ich habe: weil für diesen Knoten
So wird der Zähler des Knotens * 2 Pass zwei Wörter. Das gleiche gilt für den Knoten a auf Stufe 1.
I geändert Methode entropyNextChar auf diese Weise:
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);
}
}
}
So füge ich die else.
Danke für die Antwort. Inzwischen hat das Wörterbuch keine wiederholten Wörter, aber ich denke nicht, dass dies das Problem ist, und ich interessiere mich für die Entropie von Zeichen (in den Knoten gibt es die Zeichen, nicht die ganzen Wörter). Ich verstehe nicht, warum 'p [i] = child.count/node.count;' falsch ist. Die Methode 'entropyNextChar' möchte die Entropie jedes Knotens im Baum berechnen, dh die Entropie des nächsten Zeichens, das bedingt ist durch die Tatsache, dass ich in diesem Knoten bin. Warum ist 'p [i]' falsch? Wie würdest du diese Wahrscheinlichkeit berechnen? Und 'totWords' ist die Anzahl aller Wörter, die im Wörterbuch enthalten sind – marielle
@marielle Stellen Sie sich vor, Sie würden die Strings" aaaab "und" abcd "in Ihren Radix-Trie einfügen. Beide werden unter dem Level mit dem höchsten Charakter "a" enden. Die Gesamtanzahl der Zeichen unter dem Level ist 9, die Wahrscheinlichkeit des Charakters 'a' ist 5/9, von 'b' ist 2/9, usw. Aber es wird sehr anders, wenn man anfängt, an Trie-Knoten zu denken. "aaaab" wird "a" -> "a" -> "a" -> "a" -> "b" und "abcd" - "a" -> "b" -> "c" -> "d" . Die Zahl deines obersten Knotens wird nur 2 sein, da es angibt, wie oft du den Knoten getroffen hast, nicht wie viele "a" Buchstaben unter dem Level –
@marielle verwendet wurden. Also würde ich vorschlagen, eine Karte von Charakteren auf Zählern zu speichern könnte nur ein Array [size_of_your_alphabet]) für jedes Level sein. Immer wenn Sie ein Wort einfügen, erhalten Sie die Karte der Ebene, in die das Wort eingefügt wird. Jedes Mal, wenn Sie das nächste Zeichen des Wortes bekommen, erhöhen Sie den entsprechenden Zähler (map [''] ++) –