Изменения

Перейти к: навигация, поиск

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

1121 байт добавлено, 00:58, 1 ноября 2010
Описание алгоритма
|}
Результат вкратце запишем так: <tex>BWT(s)=</tex>(''"BCABAAA"'', 3), где 3 - это номер исходной строки в отсортированной матрице, так как он может понадобиться для обратного преобразования.  Следует заметить, что иногда в исходной строке приводится так называемый символ конца строки ''$'', который в преобразовании будет считаться последним символом, тогда сохранение номера исходной строки не требуется. При аналогичном вышеприведённом преобразовании та строчка в матрице, которая будет заканчиваться на символ конца строки и будет исходной. При этом при сортировке матрицы данный символ будет рассматриваться как самый последний после всех символов алфавита. Тогда результат можно записать так <tex>BWT(s)=</tex>''"$CBBAAAA"''. Он будет эквивалентен первому, так как также содержит все символы исходной строки.
== Обратное преобразование ==
7
правок

Навигация