Преобразование Барроуза-Уилера: различия между версиями

Доказательство. Алгоритм вычисления s практически дословно воспроизводить процедуру, вкратце описанную в доказательстве теоремы 5. Единственное отличие заключается в том, что для большей эффективности все значения отображения 4> вычисляются за один проход. Это выполняется при помощи процедуры bwt2psi на рис. 2. Вместо работы со столбцом F процедура bwt2psi использует счетчик массива, представляющий собой «компактное» представление F. В момент начала работы процедуры для любого символа c 2 E счетчик count[c] выдает индекс первой строки матрицы <math>\mathcal{M} \;</math>, префиксом которой является c. Например, на рис. 1 count[i] = 1, count[m] = 5 и т.д. В основной части процедуры bwt2psi с циклом сканируется счетчик массива bwt, и значение count[c] увеличивается каждый раз при обнаружении вхождения символа c (строка 6). Строка 6 также присваивает переменной h индекс l-го вхождения элемента c в F. Согласно лемме 3, строка 7 корректно сохраняет в psi [h] значение i = Ф(И). После вычисления массива psi строка s восстанавливается при помощи процедуры psi2text на рис. 2, корректность которой непосредственно следует из теоремы 5.

Использование процедуры 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): Барроуз и Уилер  предложили проделать это при помощи алгоритма Хаффмана или арифметического кодирования – возможно, после однократного прогона на наборах одинаковых целых чисел.

 

 

3 Если s – текст на английском языке, mtf(s) обычно содержит более 50% нулей.