Действительно, массив суффиксов, предполагающий, что метод сжатия не используется, является массивом целых чисел. Но целое число не требует ровно 8 байтов.
Сколько бит нужно для хранения целого числа? Ответ зависит от диапазона целого числа. Если диапазон равен [0,2), т. е. единственные числа, которые вы когда-либо хотели бы представлять, это 0 и 1, тогда вам нужен 1 бит для хранения этого целого числа.
Если ваш диапазон равен [0,4), т. е. вы хотите представить 0, 1, 2 и 3, вам понадобятся два бита: 00, 01, 10 и 11 — четыре возможные комбинации двух битов, которые вы можете использовать для представления четыре разных числа.
Если диапазон до 8 номеров, вам нужно 3 бита, до 16 вам нужно 4 и т. д. Вообще говоря, для диапазона R различных чисел вам нужно ceil(log2(R) ) биты.
Сколько бит вам нужно для массива суффиксов? Я предполагаю, что длина текста составляет N символов. Тогда длина массива суффиксов также равна N, и каждое из его целых чисел относится к текстовой позиции, т.е. диапазон каждого целого числа равен [0,N). Следовательно, вам нужно ceil(log2(N)) битов для хранения каждого целого числа, а поскольку всего имеется N целых чисел, общее требование к пространству составляет N ceil(log2< /sub>(N)) бит (без учета места, занимаемого самим текстом).
(Но обратите внимание, что большая часть недавних исследований массивов суффиксов посвящена их сжатию, то есть поиску способов использовать только O(N) битов (это называется кратким представлением) или даже меньше, то есть o(N) битов (истинное сжатие). ) Приведенный выше простой расчет применим только к стандартному случаю, когда вообще не используются методы сжатия.)
(Также обратите внимание, что на практике многие реализации просто используют unsigned int или что-то подобное для представления целого числа, а затем вы получаете N*sizeof(int)*CHAR_BIT для требования к размеру в битах.)
person
jogojapan
schedule
25.06.2013
