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

'''Алгоритм сжатия Барроуза-Уилера'''

Использование процедуры 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