Новиков Ф.А. Дискретная математика для программистов (860615), страница 43
Текст из файла (страница 43)
Таким образом, можно задаться некоторым набором букв и частотами их228Глава 6. Кодирование 228появления в тексте и с помощью алгоритма Хаффмена построить оптимальноеалфавитное кодирование текстов (для заданного алфавита и языка). Простыерасчёты показывают, что такое кодирование для распространенных естественных языков будет иметь цену кодирования несколько меньше 6, то есть даствыигрыш по сравнению с кодом ASCII на 25% или несколько больше.ЗАМЕЧАНИЕМетоды кодирования, позволяющие построить (без потери информации!) коды сообщений меньшей длины по сравнению с исходным сообщением, называются методами сжатия (или упаковки) данных. Качество сжатия определяется коэффициентом сжатия, который обычно измеряется в процентах и показывает, на сколько процентов кодированноесообщение; короче исходного.Известно, что практические программы сжатия (гаг, zip и др.) имеют гораздолучшие показатели, чем код Хаффмена: при сжатии текстовых файлов коэффициент сжатия достигает 70% и более.
Это означает, что в таких программахиспользуется не алфавитное кодирование.6.4.2. Предварительное построение словаряРассмотрим следующий способ кодирования:1. Исходное сообщение по некоторому алгоритму разбивается на последовательности букв, называемые словами (слово может иметь одно или нескольковхождений в исходный текст сообщения).2. Полученное множество слов считается буквами нового алфавита. Для этогоалфавита строится разделимая схема алфавитного кодирования (равномерного кодирования или оптимального кодирования, если для каждого словаподсчитать число вхождений в текст). Полученная схема обычно называетсясловарем, так как она сопоставляет слову код.3.
Далее код сообщения строится как пара — код словаря и последовательностькодов слов из данного словаря.4. При декодировании исходное сообщение восстанавливается путем замены кодов слов на слова из словаря.Пример Допустим, что требуется кодировать тексты на русском языке. В качестве алгоритма деления па слова примем естественные правила языка: словаотделяются друг от друга пробелами или знаками препинания. Можно принятьдопущение, что в каждом конкретном тексте имеется пе более 2 16 различныхслов (обычно гораздо меньше). Таким образом, каждому слову можно сопоставить помер — целое число из двух байтов (равномерное кодирование).
Посколькув среднем слова русского языка состоят более чем из двух букв, такое кодирование даёт существенное сжатие текста (около 75% для обычных текстов нарусском языке). Если текст достаточно велик (сотни тысяч или миллионы букв,то есть сотни и тысячи страниц), то дополнительные затраты на храпение словаряоказываются сравнительно небольшими.6.4. Сжатие данных229ЗАМЕЧАНИЕДанный метод попутно позволяет решить задачу полнотекстового поиска, то есть определить, содержится ли заданное слово (или слова) в дампом тексте, причём для этого ненужно просматривать весь текст (достаточно просмотреть только словарь).Указанный метод можно усовершенствовать следующим образом. На шаге 2 следует применить алгоритм Хаффмена для построения оптимального кода, а пашаге 1 — решить экстремальную задачу разбиения текста на слова таким образом,чтобы среди всех возможных разбиений выбрать то, которое даёт наименьшуюцепу кодирования на шаге 2.
Такое кодирование будет «абсолютно» оптимальным. К сожалению, указанная экстремальная задача очень трудоёмка, поэтомуна практике не используется — время на предварительную обработку большого текста оказывается чрезмерно велико даже при использовании современныхбыстродействующих компьютеров.6.4.3. Алгоритм Лемпела-ЗиваНа практике используется следующая идея, которая известна также как адаптивное сжатие. За один проход по тексту одновременно динамически строитсясловарь и кодируется текст. При этом пет необходимости хранить словарь: за счёттого, что при декодировании используется тот же самый алгоритм построениясловаря, словарь динамически восстанавливается.Ниже приведена простейшая реализация этой идеи, известная как алгоритм Лемпела1 -Зива2.
Вначале словарь D : array [int] of string содержит пустое слово,имеющее код 0. Далее в тексте последовательно выделяются слова. Выделяемое слово — это максимально длинное слово из уже имеющихся в словаре плюсещё один символ. В сжатое представление записываются найденный код словаи расширяющая буква, а словарь пополняется расширенной комбинацией.ЗАМЕЧАНИЕВ алгоритмах этого раздела знак +, применённый к целым числам, означает сложение, априменённый к словам или символам — конкатенацию.Алгоритм 6.3 Упаковка по методу Лемпела-ЗиваВход: исходный текст, заданный массивом кодов символов / : array [l..n] ofchar.Выход: сжатый текст, представленный последовательностью пар (p,q), где р —номер слова в словаре, q — код дополняющей буквы..D[0]: = £• d: = 0 { начальное состояние словаря }к: = 1 { номер текущей буквы в исходном тексте }while к ^ п doр: — FD(fc) { р — индекс найденного слова в словаре }12Абрахам Лсмпел (р.
1936).Якоб Зив (р. 1931).230Глава 6. Кодирование 230I: = Length(D[p]) { I — длина найденного слова в словаре }yield {р, f [к+ 1]) { код найденного слова и ещё одна буква }d: = d + 1; D[d]: = D\p] + f[k + /] { пополнение словаря }к: = к + I + 1 { продвижение вперед по исходному тексту }end whileСлово в словаре ищется с помощью несложной функции FD.Вход: к — номер символа в исходном тексте, начиная с которого нужно искать в текстеслова из словаря.Выход: р — индекс самого длинного слова в словаре, совпадающего с символами f[k]..f[k + I].Если такого слова в словаре нет, то р = 0.I: = 0; р: = 0 { начальное состояние }for г from 1 to d dom: = Length(D[i]) { длина слова в словаре }if £>[»] = f[k..k + m - 1] km>lthenp: = i; i: = m { нашли более подходящее слово }end ifend forreturn pРаспаковка осуществляется следующим алгоритмом.Алгоритм 6.4 Распаковка по методу Лемпела-ЗиваВход: сжатый текст, представленный массивом пар д : array [1 ..тп] of record р :int; q : char end record, где p — номер слова в словаре, q — код дополняющейбуквы.Выход: исходный текст, заданный последовательностью строк и символов.D[0]: = е\ d: = 0 { начальное состояние словаря }for к from 1 to m doр: = д[к].р { р — индекс слова в словаре }q: = g[k].q { q — дополнительная буква }yield D\p] + q { вывод слова и ещё одной буквы }d: = d+l-,D[d]: = D\p] + q { пополнение словаря }end forЗАМЕЧАНИЕНа практике применяют различные усовершенствования этой схемы:1.
Словарь можно сразу инициализировать, например, кодами символов (то есть считать,что однобуквенные слова уже известны).2. В текстах часто встречаются регулярные последовательности: пробелы и табуляции втаблицах и т. п. Сопоставлять каждой подпоследовательности такой последовательности отдельное слово в словаре нерационально. В таких случаях лучше применить специальный приём, например, закодировать последовательность пробелов парой (k,s),где к — количество пробелов, a s — код пробела.6.5. Шифрование2316.5. ШифрованиеЗащита информации, хранящейся в компьютере, от несанкционированного доступа, искажения и уничтожения в настоящее время является серьёзной социальной проблемой. Применяются различные подходы к решению этой проблемы:• Поставить между злоумышленником и данными в компьютере непреодолимый «физический» барьер, то есть исключить саму возможность доступа кданным путем изоляции компьютера с данными в охраняемом помещении,применения аппаратных ключей защиты и т.
п. Такой подход надёжен, но онзатрудняет доступ к данным для законных пользователей, а потому постепенно уходит в прошлое.• Поставить между злоумышленником и данными в компьютере «логический»барьер, то есть проверять наличие прав на доступ к данным и блокироватьдоступ при отсутствии таких прав. Для этого применяются различные системы паролей, регистрация и идентификация пользователей, разграничениеправ доступа и т.
п. Практика показывает, что борьба между «хакерами» иразработчиками модулей защиты операционных систем идёт с переменнымуспехом.• Хранить данные таким образом, чтобы они могли «сами за себя постоять».Другими словами, так закодировать данные, чтобы, даже получив к ним доступ, злоумышленник не смог бы нанести ущерба.Этот раздел посвящён обсуждению методов кодирования, применяемых в последнем случае.6.5.1.
КриптографияШифрование — это кодирование данных с целью защиты от несанкционированного доступа. Процесс кодирования сообщения называется шифрованием (илизашифровкой), а процесс декодирования — расшифровыванием (или расшифровкой). Само кодированное сообщение называется шифрованным (или простошифровкой), а применяемый метод называется шифром.Основное требование к шифру состоит в том, чтобы расшифровка (и, можетбыть, зашифровка) была возможна только при наличии санкции, то есть некоторой дополнительной информации (или устройства), которая называется ключомшифра. Процесс декодирования шифровки без ключа называется дешифрованием(или дешифрацией, или просто раскрытием шифра).Область знаний о методах создания и раскрытия шифров называется криптографией (или тайнописью).Свойство шифра противостоять раскрытию называется криптостойкостью (илинадёжностью) и обычно оценивается сложностью алгоритма дешифрации.ОТСТУПЛЕНИЕВ практической криптографии криитостойкость шифра оценивается из экономических соображений.
Если раскрытие шифра стоит (в денежном выражении, включая необходимыекомпьютерные ресурсы, специальные устройства, услуги специалистов и т. п.) больше, чемсама зашифрованная информация, то шифр считается достаточно надёжным.232Глава 6. Кодирование 232Криптография известна с глубокой древности и использует самые разнообразныешифры, как чисто информационные, так и механические. В настоящее времянаибольшее практическое значение имеет защита данных в компьютере, поэтомудалее рассматриваются программные шифры для сообщений в алфавите {0,1}.6.5.2. Шифрование с помощью случайных чиселПусть имеется датчик псевдослучайных чисел, работающий по некоторому определённому алгоритму. Часто используют следующий алгоритм:Ti+i: =(а • Ti + b)mode,где Ti — предыдущее псевдослучайное число, Ti + 1 — следующее псевдослучайноечисло, а коэффициенты а, Ь, с постоянны и хорошо известны.
Обычно с — 2П,где п — разрядность процессора, a mod 4 = 1, а Ь — нечётное. В этом случаепоследовательность псевдослучайных чисел имеет период с (см. [15]).Процесс шифрования определяется следующим образом. Шифруемое сообщение представляется в виде последовательности слов So, S i , .
. . , каждое длины п,которые складываются по модулю 2 со словами последовательности To,Ti,...,то естьCi'— S{+2 Ti.ЗАМЕЧАНИЕПоследовательность То, Т\,...называется гаммой шифра.Процесс расшифровывания заключается в том, чтобы ещё раз сложить шифрованную последовательность с той же самой гаммой шифра:Si'. = Ci +2 Ti.Ключом шифра является начальное значение То, которое является секретным идолжно быть известно только отправителю и получателю шифрованного сообщения.ЗАМЕЧАНИЕШифры, в которых для зашифровки и расшифровки используется один и тот же ключ,называются симметричными.Если период последовательности псевдослучайных чисел достаточно велик, чтобы гамма шифра была длиннее сообщения, то дешифровать сообщение можно только подбором ключа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
