а всё-таки, какой размер блока BWT на практике

Имя (желательно полное):

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).
> Здравствуйте, единомышленники! > никак не могу могу понять, какой же размер блока > применяется в BWT-преобразовании. 1 Кб? 10 Кб? > 1 Мб и более? > Объясню, к чему вопрос: кажется, я научился проводить > BWT для кусков в 4 и более мегабайт с весьма небольшими > затратами времени, грубо оценивая - линейными от размера > блока. И не могу понять: новый это результат, либо всем > давно известный и неинтересный. > В рунете данные по BWT можно пересчитать по пальцам > и в этом вопросе они все противоречат друг другу :) > (1) BWT-FAQ by Юкин Вадим Анатольевич > >В научных кругах сейчас идет борьба за достижение > >линейного роста времени сжатия от размера блока и уже > >существует ряд публикаций по этому поводу... > >К примеру, для YBS в худшем случае все равно должно бы > >получаться n*logn, но мне такие случаи не попадались. > >Даже специально :) А на большинстве файлов зависимость > >получается практически линейной. > вроде бы оптимистично. > (2) линуксовый bzip2 на запрос bzip2 --help выдаёт > (среди других опций) > -1 .. -9 = set block size to 100k .. 900k > получается, у него размер блока BWT аж 900 килобайт ? > (3) frame_bwt.html > >Главной проблемой в реализации BWT является выбор > >быстрого алгоритма сортировки данных с большой длиной > >ключа. Отметим, что прямые методы в данной ситуации > >проблему не решают: алгоритм поразрядной сортировки, > >имеющий линейную сложность k·O(n), вырождается в > >O(n2) - не трудно представить, сколько времени у него > >уйдет на сортировку хотя бы 65 тысяч элементов > т.е. агитирует за N Не стоит пугаться увеличения размера блока, в реальной > >ситуации (блок в 1-2 Кб) добавление одного символа > >несущественно по сравнению с выигрышем, получаемым от > >применения BWT > вполне определённо говорит об 1-2 Кб. > (3' - тот же автор) frame_sht.html / Преобразование > Шиндлера (Schindler Transformation) > >Эффективность ST во многом определяется возможностью > >обработки намного больших, по сравнению с BWT, блоков > >за счет экономии памяти (не нужно хранить n·(n-k) > >символов). Так, при наличии 512 Мб оперативной памяти, > >алгоритм BWT может обрабатывать блоки не более, чем из > >n = 23170 элементов (n·n ~ 512 Мб), тогда как ST-3 > >уже из n = 178956970 элементов (3·n ~ 512 Мб) > ----------------- > ...так всё-таки?

Пожалуйста, заполните все поля.
И не нажимайте по два раза на кнопку! Дождитесь ответа сервера.