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


Сайт о сжатии >> Форум #Компрессор# >> [Ответить] [Ответы]

Автор: Пётр Карцев,
Россия, 13 января 2004 года в 15:24:12

Здравствуйте, единомышленники!

никак не могу могу понять, какой же размер блока
применяется в 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 Мб)

-----------------
...так всё-таки?

Ответы:



Ответить на это сообщение

Тема:

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

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).

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