DEMO.DESIGN
Frequently Asked Questions
 
оглавление | demo party в ex-СССР | infused bytes e-mag | новости от ib/news | другие проекты | письмо | win koi lat

следующий фpагмент (2)
LZW - История этого алгоритма начинается с опубликования в мае 1977 г. Дж. Зивом ( J. Ziv ) и А. Лемпелем ( A. Lempel ) статьи в журнале " Информационные теории " под названием " IEEE Trans ". В последствии этот алгоритм был доработан Терри А. Велчем ( Terry A. Welch ) и в окончательном варианте отражен в статье " IEEE Compute " в июне 1984 . В этой статье опи- сывались подробности алгоритма и некоторые общие проблемы с которыми можно столкнуться при его реализации. Позже этот алгоритм получил название - LZW ( Lempel - Ziv - Welch ) . Алгоритм LZW представляет собой алгоритм кодирования последовательностей неодинаковых символов. Возьмем для примера строку " Объект TSortedCollection порожден от TCollection.". Анализируя эту строку мы можем видеть, что слово "Collection" повторяется дважды. В этом слове 10 символов - 80 бит. И если мы сможем заменить это слово в выходном файле, во втором его включении, на ссылку на первое включение, то получим сжатие информации. Если рассматривать входной блок информации размером не более 64К и ограничится длинной кодируе- мой строки в 256 символов, то учитывая байт "флаг" получим, что строка из 80 бит заменяется 8+16+8 = 32 бита. Алгоритм LZW как-бы "обучается" в процессе сжатия файла. Если существуют повторяющиеся строки в файле , то они будут закодированны в таблицу. Очевидным преимуществом алгоритма является то, что нет необходимости включать таблицу кодировки в сжатый файл. Другой важной особенностью является то, что сжатие по алгоритму LZW является однопроходной операцией в противоположность алгоритму Хаффмана ( Huffman ) , которому требуется два прохода.
следующий фpагмент (3)|пpедыдущий фpагмент (1)
LZ78 есть новый подход к адаптированному словарному сжатию, важный как с теоретической, так и с практической точек зрения [119]. Он был первым в семье схем, развивающихся параллельно (и в путанице) с LZ77. езависимо от возможно- сти указателей обращаться к любой уже просмотренной строке, просмотренный текст разбирается на фразы, где каждая новая фраза есть самая длинная из уже просмотренных плюс один символ. Она кодируется как индекс ее префикса плюс до- полнительный символ. После чего новая фраза добавляется к списку фраз, на ко- торые можно ссылаться. апример, строка "aaabbabaabaaabab", как показано на pисунку 6, делится на 7 фраз. Каждая из них кодируется как уже встречавшаяся ранее фраза плюс теку- щий символ. апример, последние три символа кодируются как фраза номер 4 ("ba"), за которой следует символ "b". Фраза номер 0 - пустая строка. Input: a aa b ba baa baaa bab Phrase number: 1 2 3 4 5 6 7 Output: (0,a) (1,a) (0,b) (3,a) (4,a) (5,a) (4,b) Рисунок 6. LZ78-кодирование строки "aaabbabaabaaabab"; запись (i,a) обозначает копирование фразы i перед символом a. Дальность пpодвижения впеpед указателя неограниченна (т.е. нет окна), поэ- тому по мере выполнения кодирования накапливается все больше фраз. Допущение произвольно большого их количества тpебует по меpе pазбоpа увеличения размера указателя. Когда разобрано p фраз, указатель представляется [log p] битами. а практике, словарь не может продолжать расти бесконечно. При исчерпании доступ- ной памяти, она очищается и кодирование продолжается как бы с начала нового текста. Привлекательным практическим свойством LZ78 является эффективный поиск в деpеве цифpового поиска пpи помощи вставки. Каждый узел содержит номер предс- тавляемой им фразы. Т.к. вставляемая фраза будет лишь на одни символ длиннее одной из ей предшествующих, то для осуществления этой операции кодировщику бу- дет нужно только спуститься вниз по дереву на одну дугу. Важным теоретическим свойством LZ78 является то, что пpи пpозводстве ис- ходного текста стационарным эргодическим источником, сжатие является приблизи- тельно оптимальным по мере возрастания ввода. Это значит, что LZ78 приведет бесконечно длинную строку к минимальному размеру, опpеделяемому энтропией ис- точника. Лишь немногие методы сжатия обладают этим свойством. Источник являет- ся эргодическим, если любая производимая им последовательность все точнее ха- рактеризует его по мере возрастания своей длины. Поскольку это довольно слабое огpаничение, то может показаться, что LZ78 есть решение проблемы сжатия текс- тов. Однако, оптимальность появляется когда размер ввода стремится к бесконеч- ности, а большинство текстов значительно короче! Она основана на размере явно- го символа, который значительно меньше размера всего кода фразы. Т.к. его дли- на 8 битов, он будет занимать всего 20% вывода при создании 2^40 фраз. Даже если возможен продолжительный ввод, мы исчерпаем память задолго до того, как сжатие станет оптимальным. Реальная задача - посмотреть как быстро LZ78 сходится к этому пределу. Как показывает практика, сходимость эта относительно медленная, в этом метод срав- ним с LZ77. Причина большой популярности LZ-техники на практике не в их приб- лижении к оптимальности, а по более прозаической причине - некоторые варианты позволяют осуществлять высоко эффективную реализацию.

Всего 2 фpагмент(а/ов) |пpедыдущий фpагмент (2)

Если вы хотите дополнить FAQ - пожалуйста пишите.

design/collection/some content by Frog,
DEMO DESIGN FAQ (C) Realm Of Illusion 1994-2000,
При перепечатке материалов этой страницы пожалуйста ссылайтесь на источник: "DEMO.DESIGN FAQ, http://www.enlight.ru/demo/faq".