Главная » Java, Структуры данных и алгоритмы » Компрессия (сжатие) текста

0

В этом разделе рассматривается еще одна из форм обработки текста — компрессия текста (сжатие). Допустим, имеется строка ^некоторого алфавита, например, ASCII или Unicode, и требуется эффективно перекодировать X в компактную бинарную строку Y (применяя только 0 и 1). Компрессия текста удобна тем, что можно пользоваться каналами с невысокой пропускной способностью типа модема или инфракрасного соединения, при этом сводя до Ьшнимума время передачи текста. Компрессия текста эффективна и в случае хранения наборов больших документов, чтобы разместить в хранилище с постоянным объемом наибольшее количество документов.

В этом разделе в качестве методики компрессии текста рассмотрим алгоритм Хаффмана (Huffman code). Стандартные системы кодирования (А5>СП и Unicode) использую^ бйнаркыб строки d фиксированной длиной (7 бит в ASCII и 16 в Unicode). Attfopkfto Хаффмана, напротив, использует кодирование с переменной длиной бинарной строки, оптимизированное специально для строки X. В основу этой оптимизации положено использование частотности употребления символа, где для каждого символа с имеется счетчик/(с) количества появлений с в, строке X. Алгоритм Хаффмана экономит место за счет использования коротких кодовых строк для кодирования часто повторяющихся символов и длинных кодовых строк — для кодирования редко повторяющихся символов.

Рис. 11.11. Алгоритм Хаффмана Для исходной строки Х = «а fast runner need never be afraid of the dark»: (а) частота каждого символа; (b) дерево Хаффмана для строки X. Код символа с определяется прослеживанием пути от корня Г до простого узла, в котором хранится с, причем левый дочерний элемент применяется равным 0, а правый — 1. Например, код символа «а» будет 010, а код «f» — 1100

(b)

Для кодирования строки ^конвертируем каждый символ Хиз его кодового слова с фиксированной длиной в кодовое слово с переменной длиной, а затем соединим полученные кодовые слова, чтобы получить перекодированную строку К Для простоты представим, что ни одно из кодовых слов в нашем кодировании не является префиксом другого. Такой код называется префиксным кодом (prefix code) и упрощает обратное раскодирование Yв J!f(cM. рис. 11.11). Даже с таким ограничением экономия места довольно значительна, в особенности при большом разнообразии частоты употребления символов (обычном для текстов на традиционных языках).

(а)

Алгоритм Хаффмана для создания префиксного кода оптимальной длины строки X основан на построении бинарного дерева Г, представляющего этот код. Каждый узел в Т, за исключением корня, представляет один бит кодового слова, где левый дочерний элемент ассоциируется с О, а правый — с 1. Каждый простой узел соответствует конкретному символу, а кодовое слово этого символа определяется последовательностью битов, связанных с узлами на пути от корня Тк узлу v (см. рис. 11.11). Каждый простой узел v имеет частоту повторения символа /(v), соответствующего v, в строке X. Кроме того, каждому составному узлу v устанавливается частота/(v), то есть сумма частот всех простых узлов ветви, корнем которой является v.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии