|
文本的无损压缩和还原（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 格式的英文文本文件的压缩和解压。）
运行代码框
[Ctrl+A 全部选择 提示：你可先修改部分代码，再按运行]
|
