4430
правок
Преобразование Барроуза-Уилера: различия между версиями
Перейти к навигации
Перейти к поиску
Преобразование Барроуза-Уилера (посмотреть исходный код)
Версия от 22:27, 23 января 2017
, 23 января 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 116: | Строка 116: | ||
'''Алгоритм сжатия Барроуза-Уилера''' | '''Алгоритм сжатия Барроуза-Уилера''' | ||
Использование процедуры bwt для сжатия данных можно обосновать следующим образом. Рассмотрим строку w, которая k раз встречается внутри строки s. В bwt-матрице s будет k последовательных строк, префиксом которых является w – скажем, строки say rw + 1, rw + 2, ... , rw + k. Следовательно, позиции rw + 1, ... , rw + k в J = bwt(s) будут содержать в точности те символы, коорые непосредственно предшествуют w в s. Если в строке s некоторые шаблоны встречаются чаще других, то для многих подстрок w соответствующие позиции rw + 1, ... : : , rw + k строки s будут содержать только несколько различающихся символов. Например, если s – текст на английском языке, а w – строка «his», соответствующая часть J, скорее всего, будет содержать множество букв «t» и пустых символов и совсем немного других символов. Поскольку J является перестановкой s, она обычно оказывается локально гомогенной в том смысле, что ее «короткие» подстроки обычно содержат только несколько различающихся символов.2 | |||
Для того чтобы использовать это свойство, Барроуз и Уилер предложили обрабатывать строку s с использованием кодирования по модели «движение к началу» (move-to-front) [ ] (процедура mtf). mtf кодирует каждый символ количеством различных символов, встретившихся после предыдущего вхождения этого же символа. Для этого mtf ведет список символов, упорядоченный по давности вхождения; когда встречается следующий символ, алгоритм выводит его текущий ранг и перемещает его в начало списка. Заметим, что mtf вычисляет строку, имеющую ту же длину, что и J и в случае, если J является локально гомогенной, строка mtffs) будет в основном состоять из целых числе малой величины.3 Учитывая это смещенное распределение, можно легко сжать строку mtffs): Барроуз и Уилер предложили проделать это при помощи алгоритма Хаффмана или арифметического кодирования – возможно, после однократного прогона на наборах одинаковых целых чисел. | |||
2 Очевидно, что это верно в случае, если s обладает некоторой регулярностью: если строка s оказывается случайной, то и s также будет случайной. | |||
3 Если s – текст на английском языке, mtf(s) обычно содержит более 50% нулей. | |||
Барроуз и Уилер были заинтересованы главным образом в разработке алгоритма с высокой практической эффективностью. И в самом деле, их простая версия превосходила (по критерию коэффициента сжатия) инструмент gzip, бывший в то время стандартом сжатия бех потерь. Через несколько лет после публикации bwt в работах [9, 12] было показано, что коэффициент сжатия алгоритма Барроуза-Уилера может быть ограничен в терминах эмпирической энтропии k-го порядка входной строки для любого k > 0. К примеру, Каплан и др. [ ] показали, что для любой входной строки s и вещественного числа ji > 1 длина сжатой строки ограничена jinH^ (s) + n log(f (//.)) + jigi + O(logn) бит, где f (//.) – стандартная standard дзета-функция, а gk – функция, зависящая только от k и от размера S. Эта граница поточечно верна для любой строки s, одновременно для любых к > O и /x > 1; и это весьма примечательно, поскольку ни для одного другого алгоритма сжатия аналогичные границы не были доказаны. Теоретическое изучение эффективности алгоритмов сжатия на базе преобразования bwt в настоящее время является областью активных исследований. Дополнительную информацию см. в списке рекомендованной литературы. | |||
== Применение == | |||