信息熵
網(wǎng)址：https://blog.csdn.net/am290333566/article/details/81187124
又叫香農(nóng)熵，是香農(nóng)在1948年引入的一個概念丧慈，他指出主卫，一個系統(tǒng)越是有序，信息熵就越低簇搅，一個系統(tǒng)越混亂信息熵就越高瘩将，信息熵被認為是一個系統(tǒng)有序程度的度量凹耙。
1．信息量
指一個樣本所蘊含的信息肠仪，如果一個事件發(fā)生的概率越大，那么就認為該事件所蘊含的信息量越少异旧。例如：
極端情況下，“太陽從東邊升起”荤崇，因為是確定事件匹涮，所以不攜帶任何信息。
“昨兒逛街碰上了周杰倫”喜每，這句話就包含很多信息
2．信息熵
信息熵公式如圖所示：
隨機變量X中的有m個事件雳攘，每個事件平均需要bit位的個數(shù)就是信息熵得概念。如果某一個事件的概率特別大刚照，那么該變量蘊含的信息量就會變少喧兄，從而信息熵就會變小。例子如下：
對于第一組而言概率一樣郭变，很難猜測哪匹馬會贏涯保，對于第二組來說，很明顯可以得出結(jié)論A馬更容易獲勝未荒。算出信息熵第一組H(X)=2;第二組H(X)=1.336
條件熵（H(Y|X)）
總體來說就是熵的期望撇他。
1．定義
給定條件X的情況下狈蚤，隨機變量Y的熵就叫條件熵：
例如圖所示：
互信息
互信息就是知道X潭枣，給Y的信息量帶來多少損失（或者知道Y，給X的信息量帶來多少損失）盆犁。
左右鄰字信息熵
就是計算一個詞的左鄰字的信息熵谐岁。我們用信息熵來衡量一個文本片段的左鄰字集合和右鄰字集合有多隨機
- 例子
考慮這么一句話“吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮”，“葡萄”一詞出現(xiàn)了四次伊佃，其中左鄰字分別為 {吃, 吐, 吃, 吐} ，右鄰字分別為 {不, 皮, 倒, 皮} 塞祈。根據(jù)公式帅涂，“葡萄”一詞的左鄰字的信息熵為 – (1/2) · log(1/2) – (1/2) · log(1/2) ≈ 0.693 ，它的右鄰字的信息熵則為 – (1/2) · log(1/2) – (1/4) · log(1/4) – (1/4) · log(1/4) ≈ 1.04 媳友。可見捅位，在這個句子中搂抒，“葡萄”一詞的右鄰字更加豐富一些。
- 觀點
1焰雕、當(dāng)該詞的左信息熵比較低時候芳杏，該詞很難是一個詞
在人人網(wǎng)用戶狀態(tài)中矩屁，“被子”一詞一共出現(xiàn)了 956 次，“輩子”一詞一共出現(xiàn)了 2330 次泊脐，兩者的右鄰字集合的信息熵分別為 3.87404 和 4.11644 烁峭，數(shù)值上非常接近。但“被子”的左鄰字用例非常豐富：用得最多的是“曬被子”约郁，它一共出現(xiàn)了 162 次鬓梅；其次是“的被子”，出現(xiàn)了 85 次绽快；接下來分別是“條被子”、“在被子”娄柳、“床被子”艘绍，分別出現(xiàn)了 69 次、 64 次和 52 次诱鞠；當(dāng)然，還有“疊被子”航夺、“蓋被子”、“加被子”始衅、“新被子”缭保、“掀被子”、“收被子”艺骂、“薄被子”、“踢被子”别伏、“搶被子”等 100 多種不同的用法構(gòu)成的長尾??所有左鄰字的信息熵為 3.67453 。但“輩子”的左鄰字就很可憐了厘肮， 2330 個“輩子”中有 1276 個是“一輩子”，有 596 個“這輩子”调卑，有 235 個“下輩子”大咱，有 149 個“上輩子”注益，有 32 個“半輩子”，有 10 個“八輩子”丑搔，有 7 個“幾輩子”，有 6 個“哪輩子”煮仇，以及“n 輩子”谎仲、“兩輩子”等 13 種更罕見的用法。所有左鄰字的信息熵僅為 1.25963 夹姥。因而辙诞，“輩子”能否成詞，明顯就有爭議了飞涂〗系辏“下子”則是更典型的例子， 310 個“下子”的用例中有 294 個出自“一下子”泽西， 5 個出自“兩下子”， 5 個出自“這下子”陕见，其余的都是只出現(xiàn)過一次的罕見用法。事實上评甜，“下子”的左鄰字信息熵僅為 0.294421 忍坷，我們不應(yīng)該把它看作一個能靈活運用的詞。當(dāng)然佩研，一些文本片段的左鄰字沒啥問題，右鄰字用例卻非常貧乏晰骑，例如“交響”绊序、“后遺”、“鵝卵”等抚官，把它們看作單獨的詞似乎也不太合適阶捆。我們不妨就把一個文本片段的自由運用程度定義為它的左鄰字信息熵和右鄰字信息熵中的較小值
計算
利用trie樹計算互信息和左右信息熵
https://github.com/zhanzecheng/The-Art-Of-Programming-By-July/blob/master/ebook/zh/06.09.md
trie樹
Trie樹（字典樹）
方法介紹
1.1、什么是Trie樹
Trie樹刊咳，即字典樹儡司，又稱單詞查找樹或鍵樹，是一種樹形結(jié)構(gòu)捕犬。典型應(yīng)用是用于統(tǒng)計和排序大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計柴钻。它的優(yōu)點是最大限度地減少無謂的字符串比較垢粮，查詢效率比較高。
Trie的核心思想是空間換時間毫蚓，利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。
它有3個基本性質(zhì)：
- 根節(jié)點不包含字符元潘，除根節(jié)點外每一個節(jié)點都只包含一個字符翩概。
- 從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來钥庇，為該節(jié)點對應(yīng)的字符串牍鞠。
- 每個節(jié)點的所有子節(jié)點包含的字符都不相同上沐。
1.2参咙、樹的構(gòu)建
咱們先來看一個問題：假如現(xiàn)在給你10萬個長度不超過10的單詞硫眯，對于每一個單詞，我們要判斷它出沒出現(xiàn)過两入，如果出現(xiàn)了裹纳，求第一次出現(xiàn)在第幾個位置。對于這個問題剃氧，我們該怎么解決呢？
如果我們用最傻的方法已添，對于每一個單詞滥酥，我們都要去查找它前面的單詞中是否有它。那么這個算法的復(fù)雜度就是O(n^2)缆蝉。顯然對于10萬的范圍難以接受。
換個思路想：
- 假設(shè)我要查詢的單詞是abcd贝搁，那么在它前面的單詞中，以b雷逆，c污尉，d，f之類開頭的顯然不必考慮被碗，而只要找以a開頭的中是否存在abcd就可以了锐朴。
- 同樣的，在以a開頭中的單詞中焚志，我們只要考慮以b作為第二個字母的酱酬，一次次縮小范圍和提高針對性，這樣一個樹的模型就漸漸清晰了膳沽。
即如果現(xiàn)在有b，abc陨界，abd痛阻，bcd，abcd麻车，efg斗这，hii 這6個單詞，我們可以構(gòu)建一棵如下圖所示的樹：
如上圖所示赁咙，對于每一個節(jié)點彼水，從根遍歷到他的過程就是一個單詞，如果這個節(jié)點被標(biāo)記為紅色凤覆，就表示這個單詞存在，否則不存在慈俯。
那么拥峦，對于一個單詞，只要順著他從根走到對應(yīng)的節(jié)點刑峡，再看這個節(jié)點是否被標(biāo)記為紅色就可以知道它是否出現(xiàn)過了玄柠。把這個節(jié)點標(biāo)記為紅色，就相當(dāng)于插入了這個單詞阳似。
這樣一來我們查詢和插入可以一起完成铐伴，所用時間僅僅為單詞長度（在這個例子中俏讹，便是10）。這就是一棵trie樹户矢。
我們可以看到殉疼，trie樹每一層的節(jié)點數(shù)是26^i級別的。所以為了節(jié)省空間挂洛，我們還可以用動態(tài)鏈表眠砾，或者用數(shù)組來模擬動態(tài)。而空間的花費柒巫，不會超過單詞數(shù)×單詞長度。
1.3应结、查詢
Trie樹是簡單但實用的數(shù)據(jù)結(jié)構(gòu)泉唁，通常用于實現(xiàn)字典查詢。我們做即時響應(yīng)用戶輸入的AJAX搜索框時砾层，就是Trie開始贱案。本質(zhì)上，Trie是一顆存儲多個字符串的樹侨糟。相鄰節(jié)點間的邊代表一個字符瘩燥，這樣樹的每條分支代表一則子串，而樹的葉節(jié)點則代表完整的字符串溶耘。和普通樹不同的地方是服鹅，相同的字符串前綴共享同一條分支。
下面庐扫，再舉一個例子仗哨。給出一組單詞，inn, int, at, age, adv, ant, 我們可以得到下面的Trie：
[圖片上傳失敗...(image-c0e559-1555409498421)]
可以看出：
- 每條邊對應(yīng)一個字母萨醒。
- 每個節(jié)點對應(yīng)一項前綴桩卵。葉節(jié)點對應(yīng)最長前綴倍宾，即單詞本身胜嗓。
- 單詞inn與單詞int有共同的前綴“in”, 因此他們共享左邊的一條分支辞州，root->i->in。同理变过，ate, age, adv, 和ant共享前綴"a"媚狰，所以他們共享從根節(jié)點到節(jié)點"a"的邊。
查詢操縱非常簡單崭孤。比如要查找int辨宠，順著路徑i -> in -> int就找到了。
搭建Trie的基本算法也很簡單嗤形，無非是逐一把每則單詞的每個字母插入Trie赋兵。插入前先看前綴是否存在。如果存在霹期，就共享经伙，否則創(chuàng)建對應(yīng)的節(jié)點和邊勿锅。比如要插入單詞add，就有下面幾步：
- 考察前綴"a"垮刹，發(fā)現(xiàn)邊a已經(jīng)存在张弛。于是順著邊a走到節(jié)點a酪劫。
- 考察剩下的字符串"dd"的前綴"d"寺董，發(fā)現(xiàn)從節(jié)點a出發(fā)遮咖，已經(jīng)有邊d存在。于是順著邊d走到節(jié)點ad
- 考察最后一個字符"d"御吞，這下從節(jié)點ad出發(fā)沒有邊d了陶珠，于是創(chuàng)建節(jié)點ad的子節(jié)點add，并把邊ad->add標(biāo)記為d诀蓉。
問題實例
1寝姿、一個文本文件，大約有一萬行埃篓，每行一個詞根资，要求統(tǒng)計出其中最頻繁出現(xiàn)的前10個詞，請給出思想部脚，給出時間復(fù)雜度分析
提示：用trie樹統(tǒng)計每個詞出現(xiàn)的次數(shù)裤纹，時間復(fù)雜度是O(n*le)（le表示單詞的平均長度），然后是找出出現(xiàn)最頻繁的前10個詞锡移。當(dāng)然漆际，也可以用堆來實現(xiàn)，時間復(fù)雜度是O(n*lg10)施符。所以總的時間復(fù)雜度，是O(n*le)與O(n*lg10)中較大的哪一個浩销。
2骨坑、尋找熱門查詢
原題：搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來欢唾，每個查詢串的長度為1-255字節(jié)。假設(shè)目前有一千萬個記錄礁遣，這些查詢串的重復(fù)讀比較高祟霍，雖然總數(shù)是1千萬，但是如果去除重復(fù)和醇王，不超過3百萬個崭添。一個查詢串的重復(fù)度越高，說明查詢它的用戶越多棘伴，也就越熱門屁置。請你統(tǒng)計最熱門的10個查詢串，要求使用的內(nèi)存不能超過1G阱穗。
提示：利用trie樹使鹅，關(guān)鍵字域存該查詢串出現(xiàn)的次數(shù)，沒有出現(xiàn)為0。最后用10個元素的最小推來對出現(xiàn)頻率進行排序麦乞。
