Дискретная математика (998286), страница 32
Текст из файла (страница 32)
Затрачивая дополнительные усилия при кодировании и декодировании, можно сэкономить память, и, наоборот, пренебрегая оптимальным использованием памяти, можно существенно выиграть во времени кодирования и декодирования. Конечно, этот баланс имеет место только в определенных пределах, и нельзя сократить расход памяти до нуля или построить мгновенно работающие алгоритмы кодирования.
Для алфавитного кодирования пределы возможного установлены в разделе 6.2. Для достижения дальнейшего прогресса нужно рассмотреть неалфавитное кодирование. 6.4.1. Сжатие текстов Допустим, что имеется некоторое сообщение, которое закодировано каким-то общепринятым способом (для текстов зто, например, код АБСП) и хранится в памяти компьютера. Заметим, что равномерное кодирование (в частности, АБСП) не является оптимальным для текстов.
Действительно, в текстах обычно используется существенно меньше, чем 256 символов (в зависимости от языка — примерно 60-80 с учетом знаков препинания, цифр, строчных и прописных букв). Кроме того, вероятности появления букв различны и для каждого естественного языка известны (с некоторой точностью) частоты появления букв в тексте. Таким образом, можно задаться некоторым набором букв и частотами их появления в тексте и с помощью алгоритма Хаффмена построить оптимальное алфавитное кодирование текстов (для заданного алфавита и языка). Простые расчеты показывают, что такое кодирование для распространенных естественных языков будет иметь цену кодирования несколько меньше 6, то есть даст выигрыш по сравнению с кодом АЗСП на 25% или несколько больше.
ЗАМЕЧАНИЕ Методы кодирования, которые позеоляют построить (без потери информации!) коды сообщений, имеющие меньшую длину по сраенению с исходным сообщением, называются методами сжатия (илн упаковки) данных. Качество сжатия определяьтся козффицеятои сжатия, который обычно измеряется з процентах и показывает, на сколько процентов кодированное сообщение короче исходного. 178 Глава Б. Кодирование Известно, что практические программы сжатия (аг), агр и другие) имеют гораздо лучшие показатели: при сжатии текстовых файлов коэффициент сжатия достигает 707гл и более. Это означает, что в таких программах используется не алфавитное кодирование. 6.4.2. Предварительное построение словаря Рассмотрим следующий способ кодирования.
Е Исходное сообщение по некоторому алгоритму разбивается на последовательности символов, называемые словами (слово может иметь одно или несколько вхождений в исходный текст сообщения). 2. Полученное множество слов считается буквами нового алфавита. Для этого алфавита строится разделимая схема алфавитного кодирования (равномерного кодирования или оптимального кодирования, если для каждого слова подсчитать число вхождений в текст). Полученная схема обычно называется словарем, так как она сопоставляет слову код. 3. Далее код сообщения строится как пара — код словаря и последовательность кодов слов из данного словаря. 4. При декодировании исходное сообщение восстанавливается путем замены кодов слов на слова из словаря. Пример Допустим, что требуется кодировать тексты иа русском языке.
В качестве алгоритма деления на слова примем естественные правила языка: слова отделяются друг от друга пробелами или знаками препинания, Можно принять допущение, что в каждом конкретном тексте имеется не более 2ге различных слов (обычно гораздо меньше). Таким образом, каждому слову можно сопоставить номер — целое число из двух байтов (равномерное кодирование). Поскольку в среднем слова русского языка состоят более чем рз двух букв, такое кодирование дает существенное сжатие текста (около 75 для обычных текстов на русском языке).'Если текст достаточно велик (сотни тысяч или миллионы букв), то дополнительные затраты на хранение словаря оказываются сравнительно небольшими. ЗАМЕЧАНИЕ данный метод попутно позволяет решить задачу лолномглслюеого лоиска, то есть опрелелить, содержится ли заданное слово (эли слова) в данном тексте, причем лля этого не нужно просматривать весь текст (лостаточяо просмотреть только словарь).
Указанный метод можно усодершенствовать следующим образом. На шаге 2 следует применить алгоритм Хаффмена для построения оптимального кода, а на шаге 1 — решить экстремальную задачу разбиения текста на слова таким образом, чтобы среди всех возможных разбиений выбрать то, которое дает наименьшую 6.4. Сжатие данных цену кодирования на шаге 2. Такое кодирование будет «абсолютно» оптимальным. К сожалению, указанная экстремальная задача очень трудоемка, поэтому на практике не используется — время на предварительную обработку большого текста оказывается чрезмерно велико. 6.4.3.
Алгоритм Лемпела — Зива На практике используется следующая идея, которая известна также как адаптивное сжатие. За один проход по тексту одновременно динамически строится словарь и кодируется текст. При этом словарь не хранится — за счет того, что при декодировании используется тот же самый алгоритм построения словаря, словарь динамически восстанавливается. Здесь приведена простейшая реализация этой идеи, известная как алгоритм Лемпела — Зива. Вначале словарь Р: аггау [ш1] оЕ а1ппн содержит пустое слово, имеющее код О. Далее в тексте последовательно выделяются слова. Выделяемое слово — это максимально длинное слово из уже имеющихся в словаре плюс еще один символ. В сжатое представление записывается найденный код слова и расширяющая буква, а словарь пополняется расширенной комбинацией.
Алгоритм 6.3. Упаковка по методу Лемпепа-Зива Вход: исходный текст, заданный массивом кодов символов Е: аггау [1..п] оЕ сЬаг. Выход: сжатый текст, представленный последовательностью пар (р,ч), где р — номер слова в словаре, д — код дополняющей буквы. Р[0]: = ""; о': = 0 ( начальное состояние словаря ) Й г = 1 ( номер текупгей буквы в исходном тексте ) ггЬ1!е к ( и г(о р: = РР(гг) ( р — индекс найденного слова в словаре ) 1: = ЕепдгЬ(Р[р]) ( 1 — длина найденного слова в словаре ) у1е1д (р,1[в+ 1]) [ код найденного слова и еще одна буква ) ге: = о+ 1; Р[о]: = Р[р] гг Е[ь+ 1] ( пополнение словаря, здесь гг — зто конкатенация ) ь: = ь+ 1+ 1 ( продвижение вперед по исходному тексту ) епг[ жййе Слово в словаре ищется с помощью несложной функции ГР.
Вход: Ег — номер символа в исходном тексте, начиная с которого нужно искать в тексте слова из словаря. Выход: р — индекс самого длинного слова в словаре, совпадающего с символами Е[Ь]..1[в+ 1]. Если такого слова в словаре нет, то р = О. 1: = 0; р: = 0 ( начальное состояние ) Еог г Егощ 1 Го г( бо 1Е Р[г] = /[Ь,Ь + Е,епдгЬ(Р[г]) — Ц й ЬепкгЬ(Р[г]) ) 1 гЬеп гп = г; 1: = ЬепдгЬ(Р[г]) ( нашли более подходящее слово ) епг] 1Е епд Еог гегпгп р Распаковка осуществляется следующим алгоритмом.
180 Глава 6. Кодирование Алгоритм 6.4. Распаковка по методу Лемпепа-Знее Вход: сжатый текст, представленный массивом пар д: апву [1..гп] оГ гесогг) р: 1пй д сваг епг)гесогг), где р — помер слова в словаре, ч — код дополняюшей буквы. Выход: исходный текст, заданный последовательностью строк и символов.
О(0]: = ""; о'; = 0 ( начальное состояние словаря ) Гог Ь < п Йо р: = д[гг].Р [ р — индекс слова в словаре ) Ч: = д[к]4 1 Ч вЂ” дополнительная буква ) у]еЫ р ы ч 1 вывод слона и еще одной буквы ) и: = и+ 1; 11[о]: = В[р] 0 ч 1 пополнение словаря, здесы.~ — зто конкатенация ) епй Гог ЗАМЕЧАНИЕ" На практике применяют различные усовершенствования этой схемы. 1.
Словарь можно сразу инициализировать, например, кодами символов (то есть считать, что олпобуквснxые слова уже известны). 2. В текс ах часто встречаются регулярные последовательности: пробелы и табуляции в таблпьах и т. п. Сопоставлять каждой подпослеловательпости такой последовательности отдельное слово в словаре нерационально. В таких случаях лучше применить спецналы.ый прием, например, закодировать последовательность пробелов парой (а, д), где Й вЂ” количество пробелов, а з — код пробела 6.5.
Шифрование Защита компьютерных данных от несанкционированного доступа, искажения и уничтожения в настоящее время является серьезной социальной проблемой. Применяются различные подходы к решению этой проблемы. в Поставить между злоумышленником и данными в компьютере непреодолимый барьер, то есть исключить саму возможность доступа к данным путем физической изоляции компьютера с данными, применения аппаратных ключей защиты и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
