7跳表和Hash技术.ppt

7.5.3 LZW解压缩算法 将单一字母编码加入字典 顺序检查压缩文件，对每个编码p，对两种不同情况进行处理 情况1：p在字典中 q——p之前的编码 压缩时，输出q之后，必为sx分配了一个新编码？ 将(新编码，sx)插入字典 对应压缩过程中添加新编码的操作，在s?q之后进行 而解压缩时，q?s之后，尚不知xt，只能推后进行 文本：…text(q) text(p)… s x t 编码：… q p… 情况2：p不在字典中 在压缩时，必然文本s压缩为q，并与随后的字符x产生新编码p，对应文本t=sx 关键：紧随s之后的文本即为t（与p对应）！否则，如果p是之前的某个u压缩后生成的，则解压完u后，必然已经将p加入字典了 t在s之后?t = sx = xs’x?x=fc(s)?p解压缩的结果应为：text(q)fc(q)，将(新编码，text(q)fc(q))加入字典 文本： u … text(q) text(p)… xs’ xs’x xs’=s 编码： r … q p… 解压缩例 输入：0214537 初始，为每个字母编码：a—0，b—1 0：输出a 2：不在字典中，输出text(0)fc(0)=aa，(2, aa)?字典 1：输出b，(3, text(2)fc(1))=(3, aab)?字典 解压缩例 4：不在字典中，输出text(1)fc(1)=bb，(4, bb)?字典 5：不在字典，输出text(4)fc(4)=bbb，(5, bbb)?字典 3：输出aab，(6, text(5)fc(3))=(6, bbba)?字典 7：不在字典，输出text(3)fc(3)=aaba 结果：aaabbbbbbaabaaba 7.5.4 解压缩的实现 创建文件流 void SetFiles(int argc, char* argv[]) {// Determine file name. char OutputFile[50], InputFile[50]; // see if file name provided if (argc == 2) strcpy(OutputFile,argv[1]); else {// name not provided, ask for it cout Enter name of file to decompress endl; cout Omit the extension .zzz endl; cin OutputFile;} // name should not have an extension if (strchr(OutputFile,.)) {cerr File name has extension endl; exit(1);} 创建文件流（续） strcpy(InputFile, OutputFile); strcat(InputFile, .zzz); // open files in binary mode in.open(InputFile,ios::binary); // in.open(InputFile); for g++ if (in.fail()) {cerr Cannot open InputFile endl; exit(1);} out.open(OutputFile,ios::binary); // out.open(OutputFile); for g++ } 输出函数 void Output(int code) {// Output string corresponding to code. size = -1; while (code = alpha) {// suffix in dictionary s[++size] = ht[code].suffix; code = ht[code].prefix; } s[++size] = code; // code alpha // decompressed string is s[size] ... s[0] for (int i =