Перетворення Барроуза-Уілера

Размещено на http://www.allbest.ru/

Міністерство освіти і науки, молоді та спорту України

Львівський національний університет імені Івана Франка

Кафедра програмування

Реферат

Перетворення Барроуза - Уілера

Виконав:

Студент III курсу

факультету прикладної

математики та інформатики

Групи ПМІ-33

Левченко Андрій

Львів 2012



Зміст

1. Вступ

2. Опис алгоритму

2.1 Перетворення Барроуза-Уїлера

2.2 Оборотність перетворення Барроуза-Уілера

2.3 Вектор зворотного перетворення

2.4 Реалізація зворотного перетворення

3. Використання BWT в стисненні даних

4. Перетворення Шиндлера

5. Методи, які використовуються спільно з BWT

6. Характеристики та ефективність метода в порівнянні з іншими методами

Висновок

Список використаної літератури



1. Вступ

Алгоритм стиснення даних на основі перетворення Барроуза-Уїлера(Burrows-Wheeler Transform, далі BWT) уперше був описаний порівняно недавно - в 1994 році. Він був опублікований 10 травня в статті "A Block-sorting Lossless Data Compression Algorithm" Хоча стверджується, що один з його авторів, Майкл Уїлер, придумав його набагато раніше, в 1983 році, але тоді не надав йому належного значення. Перетворення Барроуза-Уїлера застосовується як для стиснення текстів без втрат, так і для стиснення додаткової індексної інформації до тексту. Тим не менш, до цих пір відсутня математично ясне обґрунтування деяких фактів про перетворення, зокрема, оборотності і можливості відновити суффіксний масив. Перетворення Барроуза-Уїлера також називається BW-перетворенням або просто BWT від Burrows-Wheeler Transformation.

Зараз цей метод стрімко набуває популярності серед дослідників в області стиснення даних, з'являється все більше і більше наукових статей. Hе обділяють його увагою і програмісти, що розробляють нові архіватори. Цей метод привабливий своєю простотою.

Алгоритм являє собою сукупність трьох методів:

- Метод сортування блоку даних (власне який і називається перетворенням Барроуза-Уїлера),

- MoveToFront-перетворення (відоме також, як метод переміщення стоси книжок),

- Простий статистичний кодер для стиснення перетворених на перших двох етапах даних.



2. Опис алгоритму

2.1 Перетворення Барроуза-Уїлера

Це перетворення, звичайно, є основою описуваного алгоритму стиснення. Його можна описати як спосіб перестановки символів в блоці даних, що дозволяє здійснити ефективне стиснення. Процедуру перетворення можна умовно розділити на чотири етапи:

1) виділяється блок з вхідного потоку.

2) формується матриця всіх перестановок, отриманих в результаті циклічного зсуву блоку.

3) всі перестановки сортуються відповідно до лексикографічним порядком символів кожної перестановки.

4) на вихід подається останній стовпець матриці і номер рядка, відповідної оригінальному блоку.

Hа всякий випадок слід прийняти спеціальні заходи, здатні запобігти можливому зациклення при спробі порівняти дві однакові рядки. Наприклад, при переході через границю блоку переривати порівняння і приймати однозначне рішення на користь однієї з рядків. Слід зазначити, що можлива реалізація стиснення даних на основі BWT, обробна дані послідовно по символах, а не по блокам. Але швидкісні характеристики програм, що використовують таку реалізацію, будуть дуже далекі від досконалості. Перша фаза перетворення - виділення з безперервного потоку блоку даних. Далі, потрібно з отриманого блоку даних створити матрицю всіх можливих його циклічних перестановок. Першим рядком матриці буде початкова послідовність, другим рядком - вона ж, зрушена циклічно на один символ вліво і т.д. Розглянемо перетворення на прикладі рядки "абракадабра". Таким чином, отримаємо наступну матрицю:

абракадабра

бракадабраа

ракадабрааб

акадабраабр

кадабраабра

адабраабрак

дабраабрака

абраабракад

браабракада

раабракадаб

аабракадабр

Позначимо в цій матриці вихідний рядок і відсортуємо всі рядки відповідно до лексикографічного порядку символів. Будемо вважати, що один рядок повинен знаходитися в матриці вище іншого в тому випадку, якщо в найлівішій з позицій, починаючи з якого рядки відрізняються, у цьому рядку знаходиться символ лексикографічно менший, ніж у іншого рядка. Іншими словами, слід відсортувати рядки спочатку по першому символу, потім рядки, у яких перші символи рівні - по другому і т. д.

0 аабракадабр

1 абраабракад

2 абракадабра - вихідний рядок

3 адабраабрак

4 акадабраабр

5 браабракада

6 бракадабраа

7 дабраабрака

8 кадабраабра

9 раабракадаб

10 ракадабрааб

Тепер залишився останній крок - виписати символи останнього стовпця і запам'ятати номер початкового рядка серед відсортованих. У нашому прикладі "рдакраааабб", 2 - це результат отриманий в результаті перетворення Барроуза-Уїлера.

Тепер залишилося зробити наступне:

Довести, що перетворення оборотне. Показати, що воно не вимагає величезної кількості ресурсів. Показати, що воно корисне для наступного стиску.

2.2 Оборотність перетворення Барроуза-Уілера

вектор барроуз уїлер перетворення

Нехай нам відомі тільки результат перетворення, тобто останній стовпець матриці, і номер початкового рядка. Розглянемо процес відновлення початкової матриці. Для цього відсортуємо всі символи останнього стовпця.

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 ра ........ б

Легко помітити, що відсортовані пари разом з символами останнього стовпця складають трійки. Аналогічно відновлюється вся матриця.

0 ААБ ....... р аабр ...... р. . . аабракада.р аабракадабр

1 абр ....... д абра ...... д. . . абраабрак.д абраабракад

2 абр ....... а абра ...... а. . . абракадаб.а абракадабра

3 пекла ....... до адаб ...... до. . . адабраабр.к адабраабрак

4 ака ....... р акад ...... р. . . акадабраа.р акадабраабр

5 бра ....... а браа ...... а. . . браабрака.а браабракада

6 бра ....... а шлюб ...... а. . . бракадабр.а бракадабраа

7 даб ....... а дабр ...... а. . . дабраабра.а дабраабрака

8 кад ....... а када ...... а. . . кадабрааб.а кадабраабра

9 раа ....... б Рааб ...... б. . . раабракад.б раабракадаб

10 рак ....... б раку ...... б. . . ракадабра.б ракадабрааб

2.3 Вектор зворотного перетворення

Після того, як вдалося показати принципову можливість зворотного перетворення, прийшов час зізнатися, що насправді немає необхідності відтворювати всі рядки матриці по одному символу. Зверніть увагу, що при кожному прояві досі невідомого стовпця виконувалися одні і ті ж дії. А саме, з рядка, що починається з деякого символу останнього стовпця, виходить рядок, в якого цей символ знаходиться на першій позиції. З рядка 0 виходить рядок 9, з 1 - 7 і т.д.:

0 а ......... р 9

1 а ......... д 7

2 а ......... а 0

3 а ......... до 8

4 а ......... р 10

5 б ......... а 1

6 б ......... а 2

7 д. ........ а 3

8 к. ........ а 4

9 р. ......... б 5

10 р. ......... б 6

Для отримання вектора зворотного перетворення, визначимо порядок отримання символів першого стовпця із символів останнього. Тобто відсортувати матрицю за номерами нових рядків:

2 а ......... а 0

5 б ......... а 1

6 б ......... а 2

7 д. ........ а 3

8 к. ........ а 4

9 р. ......... б 5

10 р. ......... б 6

1 а ......... д 7

3 а ......... до 8

0 а ......... р 9

4 а ......... р 10

Отримані значення номерів рядків T = {2, 5, 6, 7, 8, 9, 10, 1, 3, 0, 4} і є шуканий вектор, що містить номери позицій символів, впорядкованих відповідно до положення в алфавіті, в рядку, яку нам треба декодувати. Тепер отримати вихідний рядок зовсім просто. Першим ділом візьмемо елемент вектора зворотного перетворення, відповідний номеру початкового рядка в матриці циклічних перестановок, T [2] = 6. Інакше кажучи, в якості першого символу в заданій стрічці слід взяти шостий символ з рядка "рдакраааабб". Це символ 'а'. Потім потрібно визначити, який символ змусив опуститися знайдений символ 'а' на другу позицію серед рівних. Шуканий символ знаходиться в останньому стовпці шостого рядка матриці. А оскільки T [6] = 10, в перетвореної рядку він знаходиться в десятій позиції. Це символ 'б'. І т. д.

6

a> 10

б> 4

р> 8

а> 3

до> 7

а> 1

д> 5

а> 9

б> 0

р> 2

а

2.4 Реалізація зворотного перетворення

Проробимо теж саме за допомогою найпростішої програми. Введемо наступні позначення:

n - кількість символів в блоці з вхідного потоку;

N - кількість символів в алфавіті;

pos - номер початкового рядка в матриці перестановок;

in - вхідний потік;

count - частоти кожного символу алфавіту у вхідному потоці;

T - вектор зворотного перетворення, розмір вектора дорівнює n.

Насамперед слід порахувати частоти символів і пронумерувати всі вихідні символи в порядку їх появи в алфавіті. По суті, це еквівалентно побудові першого стовпця матриці циклічних перестановок.

for (i = 0; i <N; i + +) count [i] = 0;

for (i = 0; i <n; i + +) count [in [i]] + +;

sum = 0;

for (i = 0; i <n; i + +) {

sum + = count [i];

count [i] = sum - count [i];

}

Тепер count [i] вказує на першу позицію символу з кодом i в першому стовпці матриці.

Наступний крок - створення вектора зворотного перетворення.

for (i = 0; i <n; i + +) T [count [in [i]] + +]] = i;

Далі, за допомогою отриманого вектора відновимо початковий текст.

for (i = 0; i <n; i + +) {

putc (in [pos], output);

pos = T [pos];

}



3. Використання BWT в стисненні даних

Головна задача перетворення Барроуза-Уїлера полягає в тому, щоб переставити символи таким чином, щоб їх можна було легко стиснути. Для розуміння цього процесу достатньо уявити потік даних складається з набору деяких стабільних сполучень символів. Поєднання символів, що дозволяє передбачити деякий невідомий символ, називається контекстом. Наприклад, якщо нам відома послідовність символів "реобразованіе", то швидше за все їй передує символ "п". Назвемо стійким (стабільним) такий контекст, для якого розподіл частот символів, що безпосередньо примикають до нього ліворуч і праворуч, змінюється незначно в межах блоку. Якщо нам буде потрібно піддати перетворенню текст даної глави, можна з упевненістю сказати, що рядки, що починаються з символів "реобразованіе", будуть розташовуватися поряд в відсортованої матриці. І в відповідних цим рядкам позиціях останнього стовпця матриці буде знаходиться символ "п". Таким чином, головна властивість перетворення в тому, що воно збирає разом символи, відповідні схожим контекстам. Чим більше стабільних контекстів у блоці даних, тим краще буде стискатися отриманий в результаті перетворення блок. Практика показує, що в результаті перетворення звичайних текстів більше половини з усіх символів слід за такими ж.



4. Перетворення Шиндлера

Слід зазначити ще одне перетворення, засноване на сортуванні блоку даних - перетворення Шиндлера (ST). На відміну від BWT полягає в тому, що рядки матриці перестановок упорядковуються не по всій довжині, а тільки за вказаною кількістю перших символів. Число таких символів називається порядком перетворення Шиндлера. У разі, якщо ці символи однакові у двох чи більше рядків, вони упорядковуються відповідно до номера позиції, в якій ці рядки зустрічаються у вихідній послідовності. Справедливості заради треба відзначити, що ST є не різновидом перетворення Барроуза-Уїлера, а скоріше його узагальненням. Можна сказати, що BWT - це перетворення Шиндлера порядку, рівного розміру блоку.



5. Методи, які використовуються спільно з BWT

Як вже було сказано, саме по собі перетворення Барроуза-Уїлера не стискає. Цю роботу проробляють інші методи, що дозволяють розпорядитися тими властивостями, якими володіють перетворені дані. Серед таких методів можна відзначити наступні:

- кодування довжин повторів (RLE);

- метод переміщення стоси книжок (MTF);

- кодування відстаней (DC);

- метод Хаффмана;

- арифметичне кодування.

Послідовність застосування методів, використовуваних спільно з BWT:

Крок Використовуваний алгоритм

1 RLE (необов'язково)

2 BWT або Часткове сортують перетворення

3 MTF або DC

4 RLE (необов'язково)

5 Метод Хаффмана або арифметичне кодування



6. Характеристики та ефективність метода в порівнянні з іншими методами

Порівняння буде проводитися з архіваторами, що використовують LZ77 і метод Хаффман (скорочено LZHuf). Ці архіватори отримали найбільшу застосування ще з часів, коли комп'ютери не мали потужності і обсягу пам'яті, достатніх для того, щоб користувачам комп'ютерів були привабливі більш витончені методи. В якості представників можна назвати PKZIP, WinZIP, 7ZIP, RAR, ACE, CABARC, ARJ, JAR. Також варто порівняти з архіваторами, що використовують метод PPM (Prediction by Partial Matching). Серед них - HA, RK (а також RKUC, RKIVE), BOA, PPMD. Швидкість стиснення - на рівні архіваторів, що застосовують LZHuf Хаффмана від 1Mb - і швидше. У архіваторів, що використовують перетворення Шиндлера, SZIP, швидкість стиснення для

малих порядків ще вища. Швидкість розжаття у архіваторів, що використовують BWT, в 3-4 рази швидше стиснення. В цілому, класичні LZHuf розтискають, звичайно, швидше. Ступінь стиснення сильно залежить від типу стисливих даних. Найбільш ефективне використання BWT для текстів і будь-яких потоків даних зі стабільними контекстами. Hа неоднорідних даних відомі BWT-архіватори помітно поступаються застисненню кращим сучасним сжіматель на LZHuf і трохи не дотягують до результатів, що показуються представникам PPM-стиснення. Витрати пам'яті при стисненні досить близькі у всіх розглянутих методів і можуть коливатися у великих межах. Якщо не розглядати специфічні економні реалізації - LZHuf з маленьким словником, PPM з малим числом контекстів і BWT з кластерної сортуванням, то основні відмінності у вимогах до пам'яті спостерігаються при декодуванні. Найбільш скромними в цьому відношенні є архіватори, що використовують LZHuf. PPM'и пам'яті вимагають стільки ж, скільки ж і при стисненні. Проміжне становище займають BWT-компресори.



Висновок

Перетворення Барроуза-Уїлера активно використовується в програмах стиснення даних. Цей метод відрізняється від інших простотою реалізації, хорошою швидкістю роботи прямого перетворення, швидкою роботою зворотного перетворення при розмірі виходу з дотискати алгоритму порядку найбільш сильних за ступенем стиснення методів. Якщо для прямого перетворення використовувати в якості методу упорядкування звичайне швидке сортування, то це буде досить повільно. Пропонований алгоритм дозволяє виконати лексикографічне впорядкування швидше, ніж вищеописаний підхід. До того ж, на практиці було встановлено, що нижчеописаний метод дозволяє швидко проводити пряме перетворення на так званих водяних даних, на яких більшість існуючих на даний момент сортувальників працюють за часом неефективно. У категорію водяних даних відносять дані, в яких при упорядкуванні існує велика кількість довгих порівнянь, при встановленні лексикографічного порядку двох окремо взятих рядків.



Список використаної літератури

Кадач А.В. “Ефективні алгоритми стиснення текстової інформації”.

Юкіно В.А. “Операція BWT, або нові методи стиснення”.

Семіков М.А. “Алгоритм прискореного лексикографічного впорядкування для перетворення BWT”.

Хмельов Д.В. “Перетворення Барроуза-Уїлера, масив суфіксів і стиснення словників”.

Большаков М. “ Алгоритми обробки та перетворення інформації”.

Размещено на Allbest.ru