İngilizce sözlüğün Entropisi

Question

İngilizce kelimeler dizisini saklayan bir veri yapısı yapıyorum. Örneğin, bu kelimeler göz önüne alındığında, sözlük şudur:

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 

mavi düğümler bir kelime bitmiş olduğu olanlardır. Ben kaydedilen her düğümünde

:

• o
• düğüm kaç kelime "geçiş" gösterir
• bir sayaç bulunduğu düzey temsil ettiği karakter Bu düğüm için, düğümün bir sonraki karakterinin entropisi
• .

Ağacın her düzeyine ilişkin entropiyi ve sözlüğün toplam entropisini bulurum.

Bu

tek bir düğüm rapresent sınıf TrieNode bir parçasıdır:

class TrieNode { 

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

    ... 
} 

Bu tray veri yapısını değiştirmek için bazı yöntemler ile sınıf Trie bir parçasıdır: Artık

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)); 
    } 

    ... 
} 

Ağacın her seviyesinin entropisini bulurum.

Bunu yapmak için iki veri yapısı (level ve levelArray) oluşturan aşağıdaki yöntemi oluşturdum. levelArray sonucu içeren bir çift dizidir, yani i dizininde i-düzeyinin entropisi vardır. level, diziList dizilimidir. Her bir liste, her düğümün ağırlıklı entropisini içerir. Ben örnek sözlüğe bu yöntemi çalıştırırsanız

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); 
    } 
} 

alıyorum:

[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 

sorun sonucu muhtemel veya tamamen yanlışsa ne anlamıyorum olmasıdır.

Başka bir sorun: Tüm sözlüğün entropisini hesaplamak istiyorum. Bunu yapmak için levelArray'da bulunan değerleri ekleyeceğimi düşündüm. Bunun gibi bir prosedür var mı? Bunu yaparsam, tüm sözlüğün entropisinin 11.64 olduğunu öğrenirim.

Bazı önerilere ihtiyacım var. Acaba kod yok, ama iki sorunu çözmek için önerdiğim çözümlerin düzeltilip giderilmediğini anlarım.

Önerdiğim örnek çok basit. Gerçekte bu yöntemler yaklaşık 200800 kelimelik gerçek bir ingilizce sözlük üzerinde çalışmalıdır. Ve bu yöntemleri bu sözlükte uygularsam, bu gibi sayıları alırım (bence aşırı).her seviye için

Entropi:

[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 

ben yanlış olduğunu düşünüyorum. Ve tüm sözlüğün entropisi hesaplanamaz, sonuca ulaşamadığım için toplamın çok uzun bir süreç olduğunu düşünüyorum.

Bunun için yazdığım yöntemlerin doğru olup olmadığını anlayacağım.

sayesinde sözlüğe durumunda peşin

---

bir sürü: aaaab ve abcd, ben:

Yani düğüm * sayaç çünkü bu düğüm için 2'dir iki kelimeyi geç. seviyeye 1.

---

de düğüm a için aynı bu şekilde yöntem entropyNextChar değiştirdi:

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); 
     } 
    } 
} 

Yani else ekleyin.

Answer 1

Ne tür bir entropiye sahip olmak istediğiniz tamamen açık değil (kelimeler ?, karakterler ?, trie düğümleri?), Bu yüzden kelimelerin entropisi ve bahsettiğiniz sözlüğün çiftleri içerebileceğini kastediyorum.

Trie ve seviyelerindeki kelimelerin entropisini hesaplamak istiyorsanız olasılık fonksiyonunuz bana doğru gözükmemektedir. senin entryNextChar fonksiyonunu düşünün: Eğer (tray düğümleri isabet olasılığını hesaplamak gibi

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); 
     } 
    } 
} 

Özellikle ben şu satırda ilgileniyorum

p[i] = child.count/node.count; 

görünüyor yani eklerken bir düğümü isabet olasılığı Seviye en üst karakterden başlayan kelime). Eğer gerçekten istediğin buysa, o zaman bunu doğru yaptığını söylerdim, ama benim için mantıklı değil.

Aksi takdirde, sözcüklerin her bir seviyedeki entropisini hesaplamak isterseniz o zaman olasılık fonksiyonunuz yanlıştır. düzeyinde her kelimenin olasılığı sayımı (word_i)/gibi bir şey olmalıdır total_words nerede sayımı (word_i) her kelime seviye tutan kelimelerin toplam sayısı seviye içinde gerçekleşir ve total_words kaç kez . totWords sayacınız var, ancak tek tek kelimelerin sayaçlarını kaçırıyorsunuz. sayım alanını yalnızca isEnd değerini true olarak ayarladığınızda artırmanızı öneririm. Bu durumda, her kelimenin düzeyin içinde kaç kez oluştuğunu gösterir.

p[i] = child.count/totWords; // make sure totWords is not 0 

başka sorunu: Ve olasılık fonksiyonu gibi görünecektir Ben tüm sözlüğe entropi hesaplamak istiyoruz. Bunu yapmak için levelArray'da bulunan değerleri ekleyeceğimi düşündüm. Böyle bir prosedür var mı? Bunu yaparsam, tüm sözlüğün entropisinin 11.64 olduğunu öğrenirim.

Bunu yapmak için doğru bir yol olduğunu düşünmüyorum çünkü olasılık dağılımınız değişiyor. Bu sefer tüm trie'de toplam kelime sayısını hesaplamanız ve doğru olasılıkları elde etmek için her kelimenin frekans sayacını bu sayıya bölmeniz gerekir.