Сжатый суффиксный массив: различия между версиями

Тогда <math>A = A_0</math> может быть представлен с использованием только <math>\Psi_0, B^0</math> и <math>A_1</math>. Чтобы извлечь A[i], сначала проверим, выполняется ли <math>B^0[i] = 1</math>. Если это так, то A[i] (деленное на 2) встречается где-то в <math>A_1</math>. Точное положение зависит от того, сколько единиц встречается в <math>B^0</math> до позиции i, обозначенной как <math>rank(B^0, i)</math>, т. е. <math>A[i] = 2 \cdot A_1[rank_1(B^0, i)]</math>. Если <math>B^0[i] = 0</math>, то A[i] является нечетным и не представлен в <math>A_1</math>. Однако в этом случае элемент <math>A[i] + 1 = A[\Psi(i)]</math> должен быть четным и, таким образом, должен быть представлен в <math>A_1</math>. Так как <math>\Psi_0</math> содержит только значения <math>\Psi</math>, у которых <math>B^0[i] = 0</math>, из этого следует, что <math>A[\Psi(i)] = A[\Psi_0[rank_0(B^0, i)]]</math>. После вычисления <math>A[\Psi(i)]</math> (для четных <math>\Psi(i)</math>) элементарно получаем <math>A[i] = A[\Psi(i)] - 1</math>.

Эта идея может быть использована рекурсивно. Вместо того, чтобы представлять <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].

Удобно использовать <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>. Можно использовать следующую закономерность, обусловленную лексикографическим порядком: