資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究霍夫曼編碼和資料結構中的熵
霍夫曼編碼
霍夫曼編碼被定義為一種特定型別的最優字首碼，通常用於無損資料壓縮。
查詢或實現此類程式碼的過程透過霍夫曼編碼進行，該演算法由 David A. Huffman 在麻省理工學院攻讀 Sc.D. 學位期間開發，並於 1952 年發表在論文“一種構建最小冗餘程式碼的方法”中。
霍夫曼演算法的輸出可以顯示為一個可變長度程式碼表，用於對源符號（例如檔案中的字元）進行編碼。該演算法根據每個可能的源符號值的估計機率或出現頻率（權重）建立此表。與其他熵編碼方法一樣，更常見的符號通常用比不太常見的符號更少的位表示。霍夫曼方法可以有效地實現，如果這些權重已排序，則可以線上性時間內找到程式碼。
熵
在資訊理論中，夏農信源編碼定理（或無噪聲編碼定理）能夠確定資料壓縮的可能性極限，以及夏農熵的操作含義。
信源編碼定理表明（在極限情況下，當獨立同分布隨機變數（i.i.d.）資料流的長度趨於無窮大時），不可能壓縮資料，使得位元速率（每個符號的平均位元數）小於信源的夏農熵，而不會幾乎肯定地丟失資訊。但是，可以獲得任意接近夏農熵的位元速率，並且資訊丟失的機率可以忽略不計。
資訊熵被定義為隨機資料來源產生資訊的平均速率。
計算隨機變數的熵
我們還可以計算隨機變數中包含多少資訊。
例如，如果我們想要計算機率分佈為 p 的隨機變數 X 的資訊，這可能被寫成一個函式 H()；例如：H(X)
實際上，計算隨機變數的資訊與計算隨機變數事件的機率分佈的資訊類似。
計算隨機變數的資訊被稱為“資訊熵”、“夏農熵”或簡稱“熵”。
它與物理學中的熵概念透過類比相關聯，因為兩者都涉及不確定性這一概念。
熵的直覺是，它被定義為表示或傳輸從隨機變數的機率分佈中抽取的事件所需的平均位元數。
分佈的夏農熵被定義為從該分佈中抽取的事件中的資訊的期望量。
它為從分佈 P 中抽取的符號所需的平均編碼位元數提供了下界。
對於具有 k 個離散狀態的隨機變數 X，可以計算熵如下
H(X) = -sum(each k in K p(k) * log(p(k)))
這意味著每個事件的機率乘以每個事件機率的對數的總和的負數。
與資訊一樣，log() 函式使用以 2 為底的對數，單位為位元。可以改用自然對數。
對於機率為 1.0 的單個事件的隨機變數（確定性），計算出的熵最低。如果所有事件都等可能發生，則隨機變數的熵將達到最大。
2K+ 瀏覽量
