Теория информации

Таким образом, выходная последовательность имеет вид: 1011001. 2.1.2.6. Словарные методы сжатия Алгоритмы , использующие методы словарного сжатия , заменяют подстроки кодируемой последовательности символов ссылками в словарь на идентичные подстроки. Рассмотрим метод LZ77 , который является одним из наиболее распространенных словарных методов сжатия. Алгоритм метода словарного сжатия LZ77 : 1. Выделить область памяти под буфер. 2. Выделить область памяти под словарь. 3. Заполнить буфер символами исходной последовательности 4. Определить максимальную часть буфера ( L символов от начала буфера), совпадающих с частью словаря ( L символов с позиции P в словаре). 5. Выдать тройку < L , P , S >, где S – ( L + 1) – ый символ в буфере. 6. Переместить L + 1 символ из начала буфера (с удалением их в буфере) в конец словаря. 7. Переместить на освободившиеся позиции в начале буфера оставшиеся символы и дополнить его символами исходной последовательности. 8. Повторять пп. 4 – 7 до тех пор, пока буфер не станет пуст после выполнения п. 7. Приведенный алгоритм является общим описанием метода. Его более конкретную реализацию рассмотрим на следующем примере. Пример 5.14. Сжать методом LZ77 последовательность: aaaabaabbb . Пусть буфер имеет длину 4 символа, а словарь – 8 символов. 1. Выделить память под буфер и словарь.