|
提示：有待解决的一些细节问题有
1.字典数组的长度我们限制在 4096，这样，字典的每个位置值，我们用 12 位的二进制整数就足够表示了，输出时，我们把 4 个位置值（48 位）拼凑成 3 个 unicode 字符（正好也是 48 位）输出。
2.压缩和解压缩时，有可能最后一个代码没有被输出，编程时需要注意，具体解决可以看我在前面发的完整程序。
3.解压缩时，有可能某些代码在字典中找不到对应的解压文本，通过仔细考察压缩过程，可以知道这个代码对应的文本是dictionary[previous_code] + dictionary[previous_code].substr(0, 1)。其中 previous_code 是此代码的前一个代码。
下面我们来看一个棘手的问题：
字典应该用什么样的数据结构来组织，以提高查找匹配串的效率。
为什么用哈希表来组织字典能有效减少程序的运算量，使搜索字典的速度比遍历普通一维数组提高几千倍。
首先我们考察一下字典需要存储哪些内容：
1.前面我们知道字典需要存储 4096 个字符串（key），内容因输入文件的不同而无法预知。
2.字典还需要存储这些字符串相对应的编号（code），内容是 0 到 4095。
最直观和最容易想到的是一维数组，像这样：
dictionary[code] = key;
这样的数组只能通过遍历来搜索一个特定的 key，最坏的情况是 4096 个循环，考虑到输入文件内容的随机性，搜索一个 key 平均要循环两千多次。
那么哈希表是怎么做的呢？
哈希表首先创建一些“桶”，再把元素分散到一个个的“桶”里，根据元素的 key（而不是 code），就可以确定这个元素是在哪一个“桶”里，然后去遍历这个“桶”。
其中的关键是把元素分散到特定“桶”里的规则，其实，这个规则是由你自己定义的，一个好的规则应该是：根据 key 能够确定唯一的“桶”；分配尽可能做到均匀，能确实降低元素的密度（单个“桶”里的元素尽可能少）；规则的算法尽可能简单，运算量越少越好。这个规则被称为哈希函数。
在我们的程序里，哈希表初始化时创建了 4099 个“桶”，采用的哈希函数是：keyword % 4099
其中 keyword 是由 key 所包含的单个字符的 ASC II 编码值拼接而成。
由于字典里只要存储 4096 个元素，所以“桶”里的元素的平均密度小于 1。搜索一个 key 最坏的情况仍然只是 4096 个循环（出现这种情况几乎不可能），而平均的循环次数降低到 1 次。
我们的“桶”是子数组，4099 个“桶”构成的二维数组就是我们的哈希表。
总结：hash 是分散的意思，哈希表又称为散列，它的实质是把元素按照自定的规则分散开存储，以有效降低搜索的密度。
我们生活中一直在运用这个思想进行搜索，比如寻找一个美眉，不需要比对地球上的每一个人，只需要 中国 -> 上海 -> 淮海路 -> 哇，好多
:p
下面这个例子没有使用哈希表而用普通一维数组遍历查找（蛮干），速度慢到无法忍受：
运行代码框
[Ctrl+A 全部选择 提示：你可先修改部分代码，再按运行]
最后推荐两本比较经典的《数据结构和算法》的教程：
book.ddvip.net/SoftView/SoftView_241.html
（这本书据说是被炒得火热的，里面就有 lzw 方法的介绍和代码实现）
book.ddvip.net/SoftView/SoftView_244.html
出处：蓝色理想
责任编辑：帅青蛙
上一页 文本的无损压缩和还原 [1] 下一页
◎进入论坛网页制作、网站综合版块参加讨论
|
第 1 页 
第 2 页 文本的无损压缩和还原 [2]
