4446
правок
Усиление степени сжатия текста: различия между версиями
Материал из WEGA
Усиление степени сжатия текста (посмотреть исходный код)
Версия от 19:13, 2 февраля 2017
, 2 февраля 2017→Преобразование Барроуза-Уилера
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 42: | Строка 42: | ||
(1) добавить в концу строки s специальный символ $, который меньше любого другого символа в <math>\Sigma \;</math>; | (1) добавить в концу строки s специальный символ $, который меньше любого другого символа в <math>\Sigma \;</math>; | ||
(2) сформировать ''концептуальную'' матрицу <math>\mathcal{M} \;</math>, строки которой содержат | (2) сформировать ''концептуальную'' матрицу <math>\mathcal{M} \;</math>, строки которой содержат циклические сдвиги строки s$, отсортированные в лексикографическом порядке; | ||
(3) построить преобразованный текст <math>\hat{s} = bwt(s) \;</math>, взяв последний столбец матрицы <math>\mathcal{M} \;</math> (см. рис. 1). | (3) построить преобразованный текст <math>\hat{s} = bwt(s) \;</math>, взяв последний столбец матрицы <math>\mathcal{M} \;</math> (см. рис. 1). | ||
