【問題描述】

我們準(zhǔn)備根據(jù)一份文本編碼表對一篇文本進(jìn)行壓縮。編碼表的每一項(xiàng)包含兩個(gè)部分:要編碼的字符串和對應(yīng)的編碼。編碼是二進(jìn)制的01串，用來替代文本中相應(yīng)的字符串以實(shí)現(xiàn)壓縮編碼的目的。這些01串不一定是等長的。文本壓縮所要考慮的問題是對給定的文本和編碼表，求出能令整個(gè)文本的編碼最短的二進(jìn)制串的長度。例如文本:abcdef
編碼表
a | abc | abcd |bcd|def|ef
01 | 0 | 1011 |1 |10 |11
下面有3種不同的方式進(jìn)行編碼：
方式1：長度為5
a bcd ef
01 1 11
方式2：長度為3
abc def
0 10
方式3:長度為6
abcd ef
1011 11
很明顯，方式2長度最短，你的任務(wù)是找出編碼后文本的最短長度，若不能進(jìn)行編碼，則輸出0.

【輸入格式】

輸入可能包含多個(gè)文本壓縮問題。
第一行是一個(gè)整數(shù)n，表示有n個(gè)文本壓縮問題。(n≤10)
每個(gè)文本壓縮問題的描述第一行是要壓縮的文本（不超過210個(gè)字符），接下來是編碼表，每項(xiàng)一行，不超過100項(xiàng)，只包含小寫字母，外側(cè)有小括號。

【輸出格式】

對應(yīng)每個(gè)文本壓縮問題，每行輸出一個(gè)最小長度。

【輸入輸出樣例】

輸入樣例：

2
abcdef
(a,01)
(abc,0)
(abcd,1011)
(bcd,1)
(def,10)
(ef,11)
aa
(a,1)
(ab,10)

輸出樣例：

3
2

---

分割線君又來調(diào)皮了 _ (:з」∠)_

---

賽后和老師討論了一下這道 t ，發(fā)現(xiàn)雖說是有點(diǎn)麻煩，但是也不是很坑[ 遠(yuǎn)沒有t1坑 _ ( :з」∠) _ ] , 如果用字典樹優(yōu)化的話（其實(shí)不優(yōu)化也能A過去,而且優(yōu)不優(yōu)化都是0ms，可以說數(shù)據(jù)水么？）可以降降時(shí)間復(fù)雜度,但是我又測了一下效率之后發(fā)現(xiàn)可能這么做絲毫沒有優(yōu)化時(shí)間復(fù)雜度(原因:原題目中的編碼表項(xiàng)數(shù)太小+原數(shù)據(jù)太水),如果說編碼表項(xiàng)數(shù)的上線是一萬(1e4)的話那么用字典樹做優(yōu)化很明顯…不然隨隨便便枚舉編碼表然后加個(gè)dp這道題也能水過去[PS: 測試點(diǎn)只有5個(gè)]
但是字典樹貌似也有個(gè)缺陷就是要開較大的數(shù)組(這道題在數(shù)據(jù)水的情況下我輕松就能在字典樹210個(gè)節(jié)點(diǎn)的情況下A了,還是數(shù)據(jù)水…),最最最最關(guān)鍵的就是要開多大的數(shù)組還很難算,本題數(shù)據(jù)賤的話貌似要2X1e4個(gè)節(jié)點(diǎn)的樣子(最壞情況),如上所說如果說編碼表項(xiàng)數(shù)是1萬的話就是2X1e6的樣子.(所以說這題數(shù)據(jù)真心水,210個(gè)節(jié)點(diǎn)也就這么劃過去了)

然后這題我就A了20。。。TAT 所以第一個(gè)程序的源代碼我就不放了 （還有一個(gè)原因就是我懶）_ (:з」∠)_

那么這道題既然說了字典樹就用字典樹講吧，順便讓童鞋們（也和我一起）科普科普字典樹這玩意兒。另外，本篇blog不會詳細(xì)講字典樹的內(nèi)容，所以請童鞋們自行百度。

---

然后我就先簡要概括一下字典樹這（辣雞）玩意兒吧：

Trie樹，又稱字典樹，單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結(jié)構(gòu)，如英文字母的字典樹是一個(gè)26叉樹，數(shù)字的字典樹是一個(gè)10叉樹。與二叉查找樹不同，Trie樹的鍵不是直接保存對應(yīng)的字符串，而根節(jié)點(diǎn)對應(yīng)空字符串。一般情況下，不是所有的節(jié)點(diǎn)都有對應(yīng)的值，只有葉子節(jié)點(diǎn)和部分內(nèi)部節(jié)點(diǎn)所對應(yīng)的鍵才有相關(guān)的值。它的優(yōu)點(diǎn)是:利用字符串的公共前綴來減少查詢時(shí)間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。搜索字典項(xiàng)目的方法為:1. 從根結(jié)點(diǎn)開始一次搜索;2. 取得要查找關(guān)鍵詞的第一個(gè)字母，并根據(jù)該字母選擇對應(yīng)的子樹并轉(zhuǎn)到該子樹繼續(xù)進(jìn)行檢索;3. 在相應(yīng)的子樹上，取得要查找關(guān)鍵詞的第二個(gè)字母,并進(jìn)一步選擇對應(yīng)的子樹進(jìn)行檢索。4. 迭代過程……（我也搞不懂是神馬玩意兒，反正在這里應(yīng)該就是下標(biāo)一類的玩意兒了）5. 在某個(gè)結(jié)點(diǎn)處，關(guān)鍵詞的所有字母已被取出，則讀取附在該結(jié)點(diǎn)上的信息，即完成查找。

順便盜個(gè)圖

emm…都是借鑒來的介紹、、、其他關(guān)于字典樹的東西這里就不贅述了，如有興趣自行百度。

好了，上代碼吧。（對了，程序里的主函數(shù)中有許多字符串的函數(shù)，如有不懂的可以去搜一下，順便當(dāng)做復(fù)習(xí)）

---

include<bits/stdc++.h> //運(yùn)用字典樹來處理查找問題 using namespace std; int n,k,h,rt; string s,p; int len,v,dp[210]; //dp[i]表示在做到i號位置時(shí)付出的最小價(jià)值 int trie[210][26]; //trie[i][j]表示在第i號節(jié)點(diǎn)的后繼中，有無j字母，//如果有，那么這個(gè)后繼的編號則記錄在trie[i][j]中 int val[210]; //val[i]表示在字典樹的第i號節(jié)點(diǎn)上有無完整字符串//如果有，那么這個(gè)字符串的價(jià)值就記錄在val[i]中 void work() {len=s.length(); //len賦值為s的（有效）長度s=" "+s; //s前加個(gè)空格方便操作for(int i=1;i<=len;++i) //從前往后做dp{rt=0; //從根節(jié)點(diǎn)開始查找for(int j=i;j>=1;--j)//一直往前找，按照要壓縮的文本字符串查找是否已有此字符串編碼{int x=s[j]-'a';if(!trie[rt][x]) break; //查無此字符串，則直接退出 //（找不到當(dāng)前節(jié)點(diǎn)的話后面也不用再找下去了，相當(dāng)于樹到這里已經(jīng)斷了， //字符串在字典樹中已經(jīng)不可能匹配了） rt=trie[rt][x]; //獲得該節(jié)點(diǎn)的后繼 x 字母的節(jié)點(diǎn)編號if(val[rt]!=0x3f3f3f3f && dp[j-1]!=0x3f3f3f3f)dp[i]=min(dp[i] , dp[j-1]+val[rt]); //取最小值}}cout<< (dp[len]==0x3f3f3f3f ? 0 : dp[len]) <<endl; //直接輸出dp[len] }int main() {ios::sync_with_stdio(false); //輸入輸出流的優(yōu)化，你懂的 (o^.^o)cin>>n>>s; while(n--) {k=0; h=0;memset(trie , 0 , sizeof(trie));memset(val , 0x3f , sizeof(val));memset(dp , 0x3f , sizeof(dp)); dp[0]=0; //將整個(gè)dp數(shù)組賦值inf之后，//要把dp[0]賦為0，作為dp的基礎(chǔ)while(cin>>p && p[0]=='('){ //這里就是對讀入的數(shù)據(jù)是否是編碼表項(xiàng)len=p.find(',')-p.find('(')-1; // 運(yùn)用字符串函數(shù)得到p的長度 和 價(jià)值v=p.find(')')-p.find(',')-1;p=p.substr(1,len); //取出真正的 編碼rt=0;for(int i=len-1;i>=0;--i)//這里從后往前存點(diǎn)，因?yàn)榈葧旱膁p也是從后往前匹配的{int x=p[i]-'a'; //得到的x代表了26個(gè)字母之一if(!trie[rt][x]) //如果尚未有點(diǎn)就自己建一個(gè)點(diǎn)trie[rt][x]=++h;rt=trie[rt][x]; //然后rt指向當(dāng)前節(jié)點(diǎn)的后繼 x 字母}val[rt]=min(val[rt] , v); //最終在樹的字符串底端}work();s=p; //之前讀入的非編碼表項(xiàng)其實(shí)是要壓縮的文本，直接賦值給s }return 0; }

ok，這就是字典樹的做法了。希望童鞋們看完后能有所收獲 QAQ

另外附上我的實(shí)驗(yàn)結(jié)果（十組數(shù)據(jù)時(shí)）：

編碼表項(xiàng)數(shù)\優(yōu)化方法無優(yōu)化線性枚舉區(qū)間預(yù)處理字典樹優(yōu)化

100	70ms	40ms	50ms
1000	350ms	90ms	60ms
10000	3200ms	570ms	240ms

然后……再見 _ (:з」∠)_

轉(zhuǎn)載于:https://www.cnblogs.com/Judge/p/9383040.html

總結(jié)

以上是生活随笔為你收集整理的#1117. 编码 ( 字典树版 ) 题解分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。