聪明的以色列人(下)：LZ78 和 LZW

LZ78 的算法描述：

for (;;)

{

current_match = 1;

current_length = 0;

memset(test_string, '\0', MAX_STRING);

for (;;)

{

test_string[current_length ++] = getc(input);

new_match = find_match(test_string);

if (new_match) == -1)

break;

current_match = new_match;

}

output_code(current_match);

output_char(test_string[current_letgth - 1];

add_string_to_dictionary(test_string);

}

LZ78 示例：

输入正文： "DAD DADA DADDY DADO..."

输出短语 输出字符 编码后的串

0 'D' "D"

0 'A' "A"

1 ' ' "D"

1 'A' "DA"

4 ' ' "DA "

4 'D' "DAD"

1 'Y' "DY"

0 ' ' " "

6 'O' "DADO"

此时字典的情况：

0 ""

1 "D"

2 "A"

3 "D "

4 "DA"

5 "DA "

6 "DAD"

7 "DY"

8 " "

9 "DADO"