4551
правка
Сжатый суффиксный массив: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 42: | Строка 42: | ||
Эта идея может быть использована рекурсивно. Вместо того, чтобы представлять | Эта идея может быть использована рекурсивно. Вместо того, чтобы представлять <math>A_1</math>, замените его на <math>B^2</math>, <math>\Psi_2</math> и <math>A_2</math>. Продолжайте процесс до тех пор, пока <math>A_h</math> не станет достаточно мал, чтобы быть представленным в явном виде. Сложность будет равна O(h), предполагая выполнение операции rank за постоянное время; к битовому вектору длины n можно прикрепить o(n) бит структур данных так, чтобы ответы на запросы rank могли быть даны за постоянное время [4,7]. | ||
Удобно использовать h = | Удобно использовать <math>h = \lceil log \; log \; n \rceil</math>, так что <math>n/2^h</math> записей <math>A_h</math>, каждая из которых требует O(log n) бит, занимают суммарно O(n) бит. Все массивы <math>B^{\ell}</math> добавляют максимум 2n бит, так как их длина уменьшается вдвое на каждом следующем уровне, а их дополнительные структуры rank добавляют дополнительно o(n) бит. Единственной нерешенной задачей остается представление массивов <math>\Psi_{\ell}</math>. Можно использовать следующую закономерность, обусловленную лексикографическим порядком: | ||
Лемма 1. Пусть дан текст T[1; n], его суффиксный массив A[1; n] и соответствующая функция 4>. Тогда неравенство ^(i) < ^{i + 1) выполняется всякий раз, когда TA[i] = TA[i+1]. | Лемма 1. Пусть дан текст T[1; n], его суффиксный массив A[1; n] и соответствующая функция 4>. Тогда неравенство ^(i) < ^{i + 1) выполняется всякий раз, когда TA[i] = TA[i+1]. | ||