中文字幕二区_国产精品免费在线观看_黄色网站观看_人人草人人澡_日本真实娇小xxxx

提示：有待解決的一些細(xì)節(jié)問題有
1.字典數(shù)組的長(zhǎng)度我們限制在 4096，這樣，字典的每個(gè)位置值，我們用 12 位的二進(jìn)制整數(shù)就足夠表示了，輸出時(shí)，我們把 4 個(gè)位置值（48 位）拼湊成 3 個(gè) unicode 字符（正好也是 48 位）輸出。
2.壓縮和解壓縮時(shí)，有可能最后一個(gè)代碼沒有被輸出，編程時(shí)需要注意，具體解決可以看我在前面發(fā)的完整程序。
3.解壓縮時(shí)，有可能某些代碼在字典中找不到對(duì)應(yīng)的解壓文本，通過仔細(xì)考察壓縮過程，可以知道這個(gè)代碼對(duì)應(yīng)的文本是dictionary[previous_code] + dictionary[previous_code].substr(0, 1)。其中 previous_code 是此代碼的前一個(gè)代碼。

下面我們來看一個(gè)棘手的問題：
字典應(yīng)該用什么樣的數(shù)據(jù)結(jié)構(gòu)來組織，以提高查找匹配串的效率。
為什么用哈希表來組織字典能有效減少程序的運(yùn)算量，使搜索字典的速度比遍歷普通一維數(shù)組提高幾千倍。

首先我們考察一下字典需要存儲(chǔ)哪些內(nèi)容：

1.前面我們知道字典需要存儲(chǔ) 4096 個(gè)字符串（key），內(nèi)容因輸入文件的不同而無法預(yù)知。
2.字典還需要存儲(chǔ)這些字符串相對(duì)應(yīng)的編號(hào)（code），內(nèi)容是 0 到 4095。
最直觀和最容易想到的是一維數(shù)組，像這樣：

dictionary[code] = key;

這樣的數(shù)組只能通過遍歷來搜索一個(gè)特定的 key，最壞的情況是 4096 個(gè)循環(huán)，考慮到輸入文件內(nèi)容的隨機(jī)性，搜索一個(gè) key 平均要循環(huán)兩千多次。

那么哈希表是怎么做的呢？
哈希表首先創(chuàng)建一些“桶”，再把元素分散到一個(gè)個(gè)的“桶”里，根據(jù)元素的 key（而不是 code），就可以確定這個(gè)元素是在哪一個(gè)“桶”里，然后去遍歷這個(gè)“桶”。
其中的關(guān)鍵是把元素分散到特定“桶”里的規(guī)則，其實(shí)，這個(gè)規(guī)則是由你自己定義的，一個(gè)好的規(guī)則應(yīng)該是：根據(jù) key 能夠確定唯一的“桶”；分配盡可能做到均勻，能確實(shí)降低元素的密度（單個(gè)“桶”里的元素盡可能少）；規(guī)則的算法盡可能簡(jiǎn)單，運(yùn)算量越少越好。這個(gè)規(guī)則被稱為哈希函數(shù)。

在我們的程序里，哈希表初始化時(shí)創(chuàng)建了 4099 個(gè)“桶”，采用的哈希函數(shù)是：keyword % 4099
其中 keyword 是由 key 所包含的單個(gè)字符的 ASC II 編碼值拼接而成。
由于字典里只要存儲(chǔ) 4096 個(gè)元素，所以“桶”里的元素的平均密度小于 1。搜索一個(gè) key 最壞的情況仍然只是 4096 個(gè)循環(huán)（出現(xiàn)這種情況幾乎不可能），而平均的循環(huán)次數(shù)降低到 1 次。

我們的“桶”是子數(shù)組，4099 個(gè)“桶”構(gòu)成的二維數(shù)組就是我們的哈希表。

總結(jié)：hash 是分散的意思，哈希表又稱為散列，它的實(shí)質(zhì)是把元素按照自定的規(guī)則分散開存儲(chǔ)，以有效降低搜索的密度。
我們生活中一直在運(yùn)用這個(gè)思想進(jìn)行搜索，比如尋找一個(gè)美眉，不需要比對(duì)地球上的每一個(gè)人，只需要 中國(guó) -> 上海 -> 淮海路 -> 哇，好多
:p

下面這個(gè)例子沒有使用哈希表而用普通一維數(shù)組遍歷查找（蠻干），速度慢到無法忍受：
運(yùn)行代碼框
<SCRIPT LANGUAGE="JavaScript"> <!-- function Compress(strSrcName, strDestName) { var fso = new ActiveXObject("Scripting.FileSystemObject"); var objSrc = fso.OpenTextFile(strSrcName, 1, false, -1); var objDest = fso.OpenTextFile(strDestName, 2, true, -1); var ht = new Array; for(i = 0; i < 128; i++) { ht[i]=i; } var used = 128; var intLeftOver = 0; var intOutputCode = 0; var pcode = 0; var ccode = 0; var k = 0; while(1) { if(!objSrc.AtEndOfStream) { ccode = objSrc.Read(1).charCodeAt(0); k = (pcode << 8) | ccode; } else { break; } if((intSearch = Search(ht, k)) != null) { pcode = intSearch; } else { intLeftOver += 12; intOutputCode <<= 12; intOutputCode |= pcode; pcode = ccode; if(intLeftOver >= 16) { objDest.Write( String.fromCharCode( intOutputCode >> ( intLeftOver - 16 ) ) ); intOutputCode &= (Math.pow(2,(intLeftOver - 16)) - 1); intLeftOver -= 16; } if(used < 4096) { used ++; ht[used - 1] = k; } } } if(pcode != 0) { intLeftOver += 12; intOutputCode <<= 12; intOutputCode |= pcode; } if(intLeftOver >= 16) { objDest.Write( String.fromCharCode( intOutputCode >> ( intLeftOver - 16 ) ) ); intOutputCode &= (Math.pow(2,(intLeftOver - 16)) - 1); intLeftOver -= 16; } if( intLeftOver > 0) { intOutputCode <<= (16 - intLeftOver); objDest.Write( String.fromCharCode( intOutputCode ) ); } objSrc.Close(); objDest.Close(); t1=new Date; } function Decompress(strSrcName, strDestName) { var fso = new ActiveXObject("Scripting.FileSystemObject"); var objSrc = fso.OpenTextFile(strSrcName, 1, false, -1); var objDest = fso.OpenTextFile(strDestName, 2, true, -1); var ht = new Array; for(i = 0; i < 128; i++) { ht[i] = String.fromCharCode(i); } var used = 128; var intLeftOver = 0; var intOutputCode = 0; var ccode = 0; var pcode = 0; var key = 0; while(1) { intLeftOver += 16; intOutputCode <<= 16; intOutputCode |= objSrc.Read(1).charCodeAt(0); while(1) { if(intLeftOver >= 12) { ccode = intOutputCode >> (intLeftOver - 12); if( typeof( key = ht[ccode] ) != "undefined" ) { objDest.Write(key); if(used > 128) { ht[ht.length] = ht[pcode] + key.substr(0, 1); } pcode = ccode; } else { key = ht[pcode] + ht[pcode].substr(0, 1); objDest.Write(key); ht[ht.length] = ht[pcode] + key.substr(0, 1); pcode = ht.length - 1; } used ++; intLeftOver -= 12; intOutputCode &= (Math.pow(2,intLeftOver) - 1); } else { break; } } if(objSrc.AtEndOfStream) { break; } } objSrc.Close(); objDest.Close(); } function Search(arr, key) { for(i = 0; i < arr.length; i++) { if(arr[i] == key) return i; } return null; } //--> </SCRIPT> <body> 源：<br> <input name=inputSrc><br> 目的：<br> <input name=inputDest><br> <br> <input type=button value=壓縮 onclick="Compress(inputSrc.value, inputDest.value)"> &nbsp;&nbsp;&nbsp;&nbsp; <input type=button value=解壓 onclick="Decompress(inputSrc.value, inputDest.value)"> </body>
[Ctrl+A 全部選擇 提示：你可先修改部分代碼，再按運(yùn)行]

最后推薦兩本比較經(jīng)典的《數(shù)據(jù)結(jié)構(gòu)和算法》的教程：
book.ddvip.net/SoftView/SoftView_241.html
（這本書據(jù)說是被炒得火熱的，里面就有 lzw 方法的介紹和代碼實(shí)現(xiàn)）
book.ddvip.net/SoftView/SoftView_244.html

出處：藍(lán)色理想
責(zé)任編輯：帥青蛙

上一頁 文本的無損壓縮和還原 [1] 下一頁

◎進(jìn)入論壇網(wǎng)頁制作、網(wǎng)站綜合版塊參加討論