文本的无损压缩和还原（lzw 算法实现）

原贴地址：http://www.blueidea.com/bbs/newsdetail.asp?id=1470461&posts=current 

你所需要具备的技术基础：了解 javascript 基本语法。
当然如果学习过 vc vb 或 delphi，可以用这个原理来压缩任何文件，gif 也是基于这个算法
lzw 压缩原理：
为了简化问题，下面用的是伪代码：

1.首先初始化一个“字典”，“字典”里包含了 128 个 ASC II 码。

    var dictionary = new Array;
    for(i = 0; i < 128; i++)
    {
        dictionary[i]=String.fromCharCode(i);
    }

2.不断地在输入文件中寻找在字典中出现的最长的匹配p，并输出其在字典中的位置值到目的文件。若输入文件中下一个字符为c，把pc插入字典。
    
    StringInDictionary = input_first_char();

    while( ! AtEndOfFile )
    {

        if( search_dictionary(StringInDictionary) ) != null)
        {
            CodeInDictionary = search_dictionary(StringInDictionary);

            NextChar = input_next_char();
            StringInDictionary += NextChar;
        }
        else
        {
            Output(CodeInDictionary);
            dictionary[dictionary.length] = StringInDictionary;
            StringInDictionary = NextChar;
        }
    }


    /*在字典里搜索特定字符串*/

    function search_dictionary(str)
    {
        for( i = 0; i < dictionary.length; i ++ )
        {
            if( dictionary[i] == str )
                return i;
        }

        return null;
    }

这样就得到了压缩文件。
可以看出，压缩文件里并没有包含字典，事实上，解压缩时字典是可以根据压缩文件里的内容重建的。
下面我们来看一下解压缩的代码：

    var dictionary = new Array;
    for(i = 0; i < 128; i++)
    {
        dictionary[i] = String.fromCharCode(i);
    }

    previous_code = ReadFirstCode();
    OutPutString = dictionary[previous_code];
    Output(OutPutString);

    while( ! AtEndOfFile )
    {
        current_code = ReadNextCode();
        OutPutString = dictionary[current_code];
        Output(OutPutString);
        dictionary[dictionary.length] = dictionary[previous_code] + OutPutString.substr(0, 1);
        previous_code = current_code;
    }


如果你看懂了上面的伪代码，一定会觉得这十分简单，确实，即使把伪代码改写成真实的代码，并解决其中的一些细节问题，对大多数有一定编程经验的朋友来说，只是工作量的问题而已。如果学习过 vc vb 或 delphi，可以用这个原理来压缩任何文件，gif 也是基于这样的原理，只不过字典初始化时不是存储 ASC II 码，而是 256 种（或更少）预定义的颜色值。对于通用文件压缩，字典初始化时存储一个字节的所有可能的取值（0 到 255）。

实现的例子1：
（用了 fso ，要拷到本地运行的。由于 javascript 不支持二进制流读写，而且字符编码是 unicode 的，所以这个程序只支持 unicode 格式的英文文本文件的压缩和解压。）

运行代码框
<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 HashTable; for(i = 0; i < 128; i++) { var e = new HashTableElement; e.key = i; e.code = i; ht.Insert(e); } 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 = ht.Search(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 ++; var e = new HashTableElement; e.key = k; e.code = used - 1; ht.Insert(e); } } } 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(); } 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 HashTableElement() { this.key = null; this.code = null; } function HashTable() { this.ht = new Array(4099); this.Search = function(keyword) { var arr = this.ht[keyword%4099]; if(typeof(arr) != "undefined") { for(i = 0; i < arr.length; i ++) { if(arr[i].key == keyword) return arr[i].code; } } return null; } this.Insert = function(e) { var arr = this.ht[e.key%4099]; if(typeof(arr) == "undefined") { arr = new Array(); arr[0] = e; this.ht[e.key%4099] = arr; } else { arr[arr.length] = e; } } } //--> </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 全部选择 提示：你可先修改部分代码，再按运行]

出处：蓝色理想
责任编辑：帅青蛙

上一页 下一页 文本的无损压缩和还原 [2]

◎进入论坛网页制作、网站综合版块参加讨论