Кодирование

Итак, пусть мы сжимаем последовательность «abacabadabacabae».

· Шаг 1: Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке “a” и проверим, есть ли строка “a” в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка “a” есть в таблице.

· Шаг 2: Далее мы читаем следующий символ «b» из входного потока и проверяем, есть ли строка “ab” в таблице. Такой строки в таблице пока нет.

· Добавляем в таблицу <5> “ab”. В выход: <0>;

· Шаг 3: “ba” — нет. В словарь: <6> “ba”. В выход: <1>;

· Шаг 4: “ac” — нет. В словарь: <7> “ac”. В выход: <0>;

· Шаг 5: “ca” — нет. В словарь: <8> “ca”. В выход: <2>;

· Шаг 6: “ab” — есть в словаре; “aba” — нет. В словарь: <9> “aba”. В выход: <5>;

· Шаг 7: “ad” — нет. В словарь: <10> “ad”. В выход: <0>;

· Шаг 8: “da” — нет. В словарь: <11> “da”. В выход: <3>;

· Шаг 9: “aba” — есть в словаре; “abac” — нет. В словарь: <12> “abac”. В выход: <9>;

· Шаг 10: “ca” — есть в таблице; “cab” — нет. В словарь: <13> “cab”. В выход: <8>;

· Шаг 11: “ba” — есть в таблице; “bae” — нет. В словарь: <14> “bae”. В выход: <6>;

· Шаг 12: И, наконец последняя строка “e”, за ней идет конец сообщения, поэтому мы просто выводим <4>.

Итак, мы получаем закодированное сообщение «0 1 0 2 5 0 3 9 8 6 4», что на 11 бит короче. При этом для расшифровки необходимо дополнительно хранить начальный словарь: 0-a, 1-b, 2-c, 3-d, 4-e.

Дата добавления: 2014-01-04