П О Р Т А Л                            
С Е Т Е В Ы Х                          
П Р О Е К Т О В                        
  
Поиск по сайту:
                                                 
Главная

О проекте

Web-мастеру
     HTML & JavaScript
     SSI
     Perl
     PHP
     XML & XSLT
     Unix Shell

MySQL

Безопасность

Хостинг

Другое








Самое читаемое:

Учебник PHP - "Для Чайника".
Просмотров 180584 раз(а).

Иллюстрированный самоучитель по созданию сайтов.
Просмотров 79036 раз(а).

Учебник HTML.
Просмотров 75804 раз(а).

Руководство по PHP5.
Просмотров 46837 раз(а).

Хостинг через призму DNS.
Просмотров 54304 раз(а).

Подборка текстов стандартных документов.
Просмотров 46680 раз(а).

Учебник PHP - Самоучитель
Просмотров 52889 раз(а).

Документация на MySQL (учебник & справочное руководство)
Просмотров 53495 раз(а).

Внешние атаки...
Просмотров 43248 раз(а).

Учебник PHP.
Просмотров 38775 раз(а).

SSI в примерах.
Просмотров 28689 раз(а).



 
 
| Добавить в избранное | Сделать стартовой | Помощь





Глава 3. Кодирование информации

12. Сжатие данных по методу Лемпеля-Зива.

Лемель и Зив используют следующую идею: если в тексте сообщения появляется последовательность из двух ранее уже встречавшихся символов, то эта последовательсность объявляется новым символом, для нее назначается код, который при определенных условиях может быть значительно короче исходной последовательности. В дальнейшем в сжатом сообщении вместо исходной последовательности записывается назначенный код. При декодировании повторяются аналогичные действия и потому становятся известными последовательности символов для каждого кода.

Одна из алгоритмических реализаций этой идеи включает следующие операции. Первоначально каждому символу алфавита присваивается определенный код (коды - порядковые номера, начиная с 0). При кодировании:

1. Выбирается первый символ сообщения и заменяется на его код.

2. Выбираются следующие два символа и заменяются своими кодами. Одновременно этой комбинации двух символов присваивается свой код. Обычно это номер, равный числу уже использованных кодов. Так, если алфавит включает 8 символов, имеющих коды от 000 до 111, то первая двухсимвольная комбинация получит код 1000, следующая - код 1001 и т.д.

3. Выбираются из исходного текста очередные 2, 3,...N символов до тех пор, пока не образуется еще не встречавшаяся комбинация. Тогда этой комбинации присваивается очередной код, и поскольку совокупность А из первых N-1 символов уже встречалась, то она имеет свой код, который и записывается вместо этих N-1 символов. Каждый акт введения нового кода назовем шагом кодирования.

4. Процесс продолжается до исчерпания исходного текста.

При декодировании код первого символа, а затем второго и третьего заменяются на символы алфавита. При этом становится известным код комбинации второго и третьего символов. В следующей позиции могут быть только коды уже известных символов и их комбинаций. Процесс декодирования продолжается до исчерпания сжатого текста.

Сколько двоичных разрядов нужно выделять для кодирования? Ответ может быть следующим: число разрядов R на каждом шаге кодирования равно числу разрядов в наиболее длинном из использованных кодов (т.е. числу разрядов в последнем использованном порядковом номере). Поэтому если последний использованный код (порядковый номер) равен 13=1101, то коды А всех комбинаций должны быть четырехразрядными при кодировании вплоть до появления номера 16, после чего все коды символов начинают рассматриваться как пятиразрядные (R=5).

Пример. Пусть исходный текст представляет собой двоичный код (первая строка таблицы 1), т.е. символами алфавита являются 0 и 1. Коды этих символов соответственно также 0 и 1. Образующийся по методу Лемпеля-Зива код (LZ-код) показан во второй строке таблицы 1. В третьей строке отмечены шаги кодирования, после которых происходит переход на представление кодов А увеличенным числом разрядов R. Так, на первом шаге вводится код 10 для комбинации 00 и поэтому на следующих двух шагах R=2, после третьего шага R=3, после седьмого шага R=4, т.е. в общем случае R=K после шага 2K-1-1.

В приведенном примере LZ-код оказался даже длиннее исходного кода, так как обычно короткие тексты не дают эффекта сжатия. Эффект сжатия проявляется в достаточно длинных текстах и особенно заметен в графических файлах.

Таблица 1
Исходный текст 0.00.000. 01. 11. 111.1111. 110. 0000.00000. 1101. 1110.
LZ-код 0.00.100.001.0011.1011.1101.1010.00110.10010.10001.10110.
2 3 4
Вводимые коды - 10 11 100 101 110 111 1000 1001 1010 1011 1100

В другой известной реализации LZ-метода любая ранее встречавшаяся последовательность в сжатом тексте представляет собой совокупность следующих данных:

  • номер первого символа в ранее встречавшейся последовательности;
  • число символов в последовательности;
  • следующий символ в текущей позиции кодируемого текста.





[ Общее Содержание ]   

[ Назад ] [ Содержание раздела ] [ Вперед ]



Если Вы не нашли что искали, то рекомендую воспользоваться поиском по сайту:
 





Copyright © 2005-2016 Project.Net.Ru