Файл: Технологии программирования (Возникновение теории кодирования).pdf

2.7 Преобразование Барроуза-Уилера

Преобразование Барроуза-Уилера применяется в алгоритмах сжатия для предварительной обработки данных, для того чтобы с помощью перестановки элементов придать исходным данным со сложными зависимостями такие структурные свойства, которые легче смоделировать и учесть при кодировании.[]

Метод преобразования был опубликован в 1994 году в работе Д.Уилера и М.Барроуза и получил сокращенное название BWT. Преобразование Барроуза-Уилера применяется обычно вместе с методами кодирования, специально для него предназначенными (кодирование длин серий, сжатие с помощью «стопки книг» и др.).

Преобразование BWT - это способ перестановки символов в блоке данных. В нем можно выделить четыре этапа:

1. выделяется блок из входного потока;
2. формируется матрица всех перестановок, полученных в результате циклического сдвига блока;
3. все перестановки сортируются в соответствии с лексикографическим порядком символов каждой перестановки;
4. на выход подается последний столбец матрицы и номер строки, соответствующей исходному блоку

2.7.1 Пример преобразования Барроуза-Уилера

Обычно принято иллюстрировать преобразование на примере блока данных, состоящего из слова «абракадабра». Сформируем матрицу циклических перестановок слова «абракадабра», где первой строкой будет исходное слово, второй строкой – слово, сдвинутое на один символ влево, и т.д. Получим следующую матрицу:

Абракадабра
бракадабраа
ракадабрааб
акадабраабр
кадабраабра
адабраабрак
дабраабрака
абраабракад
браабракада
раабракадаб
аабракадабр

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

Аабракадабр
абраабракад
абракадабра - исходная строка
адабраабрак
акадабраабр
браабракада
бракадабраа
дабраабрака
кадабраабра
раабракадаб
ракадабрааб

Результатом преобразования Барроуза-Уилера является последний столбец полученной матрицы: «рдакраааабб».

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

Рассмотрим процесс восстановления отсортированной лексикографически исходной матрицы. Для этого отсортируем все символы последнего столбца.

0 а
1 а
2 а
3 а
4 а
5 б
6 б
7 д
8 к
9 р
10 р

Так как строки матрицы были отсортированы по лексикографическому порядку, отсортировав последний столбец, мы получили первый столбец отсортированной матрицы. Таким образом, мы имеем два столбца матрицы: первый - аааааббдкрр и последний – рдакраааабб:

0 а р
1 а д
2 а а
3 а к
4 а р
5 б а
6 б а
7 д а
8 к а
9 р б
10 р б

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

0 аа р
1 аб д
2 аб а
3 ад к
4 ак р
5 бр а
6 бр а
7 да а
8 ка а
9 ра б
10 ра б

Сортируя тройки символов последнего, первого и второго столбцов, восстановим третий столбец, и т.д.

Таблица 17

Декодирование слова «абракадабра»

Восстановив все столбцы матрицы, по номеру исходной строки в матрице найдем саму строку. Таким образом, для восстановления всей матрицы достаточно помнить лишь ее последний столбец.

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

Чтобы получить вектор обратного преобразования, следует определить порядок получения символов первого столбца из символов последнего, т.е. отсортировать матрицу по номерам новых строк.

Таблица 18

Сортировка таблицы

Вектор обратного преобразования образуют полученные значения номеров строк Т={2,5,6,7,8,9,10,1.3,0,4}. Чтобы получить исходную строку, возьмем элемент вектора, соответствующий номеру исходной строки в матрице циклических перестановок, Т[2]=6.

В качестве первого символа в исходной строке следует взять шестой символ из строки «рдакраааабб» - это символ «а». Для определения второго символа возьмем Т[6]=10, это символ «б», и т.д.

Таблица 19

Соотношение букв и номеров строк

Главное свойство преобразования Барроуза-Уилера состоит в том, что оно группирует вместе символы, соответствующие похожим контекстам. Практика показывает, что в результате преобразования обычных текстов более половины всех символов следует за такими же.

Чаще всего вместе с преобразованием BWT используется кодирование с помощью алгоритма сжатия «стопкой книг» (англо-язычное название move to front). Алгоритм легко понять, если представить стопку книг, каждая из которых соответствует определенному символу. По мере востребования из стопки вытаскивается нужная книга и помещается сверху. Через некоторое время те книги, которые используются часто, оказываются ближе к верхушке стопки.

Рассмотрим наш пример слова «рдакраааабб», полученного в результате преобразования Барроуза-Уилера. Символы слова принадлежат алфавиту из пяти символов. Начальный список содержит эти символы в следующем порядке: {а,б,д,к,р}. Символ «р» стоит на пятом месте в списке, поэтому первый код становится равным 4. После перемещения символа «р» на первое место список символов принимает вид {р,а,б,д,к}, и т.д.

Таблица 20

Декодирование шифрования Барроуза-Уилера на примере слова «рдакраааабб»

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

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

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

ЗАКЛЮЧЕНИЕ

Решение задачи выбора оптимального кода для передачи информации от источника к получателю (приёмнику) является одной из ключевых задач в современном мире. Переоценить качество этого невозможно, ведь при потере части информации или невозможности расшифровать исходные данные, сигнал становится бесполезным. Так же важна и скорость передачи, на которую сильно влияет объем сжатия.

Существует множество разнообразных методов и алгоритмов кодирования данных. Их число и разнообразие растёт в связи с развитием технических средств, изменением физического оборудования передачи данных, внедрением высокоскоростных технологий и других факторов.

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

Я считаю, что цель курсовой работы - изучение основных методов кодирования данных в информационных системах и определение связи с такими научными дисциплинами, как теория кодирования и теория информации, была раскрыта в полной мере.

Список литературы

1. Ван Леувен, Ян (1976). «О построении деревьев Хаффмана» (PDF) . ICALP : 382–410 .
2. Кудряшов Б. Д. Теория информации, СПбГУ НИУ ИТМО
3. Левитин А. В. Глава 9. Жадные методы: Алгоритм Хаффмана // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 392–398. — 576 с. — ISBN 978-5-8459-0987-9
4. Марков А. А. Введение в теорию кодирования. — М.: Наука, 1982. — 192 с.
5. Русский перевод: Шеннон К. Э. Математическая теория связи // Работы по теории информации и кибернетике / Пер. С. Карпова. — М.: ИИЛ, 1963. — 830 с.
6. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459
7. Хаффман, Д. (1952). «Метод построения кодов минимальной избыточности» (PDF) . Труды IRE . 40 (9): 1098–1101. doi : 10.1109 / JRPROC.1952.273898 .
8. Фурсов В. А. Лекции по теории информации ISBN 5-7883-0458-X
9. Claude E. Shannon, Warren Weaver. The Mathematical Theory of Communication. Univ of Illinois Press, 1963. ISBN 0-252-72548-4
10. Thomas M. Cover, Joy A. Thomas. Elements of information theory New York: Wiley, 1991. ISBN 0-471-06259-6
11. Types of Coding // James Irvine, David Harle Data Communications and Networks. John Wiley & Sons, 2002. pp. 268