Как реализовать произвольный доступ к сжатому буфферу

[Bulat Ziganshin]

* Originally in RU.COMPRESS
Приятного тебе дня и незабываемой ночи, Alexander!

3) использовать lz78/ppm с превдварительно построенным деревом (см.

AL> ppmtrain)

AL> Термин "дерево" - здесь нужно понимать как "словарь"?

это в lz77 - словарь, а в lz78 - именно дерево

AL> т.е. в реализации алгоритма lz78 нужно просто подсунуть это готовое
AL> дерево (оно же словарь), и не формировать его в lz78?

да, в лююом случае нужно взять уже готовые данные, которые бы сформировал к
этому моменту распаковщик

AL> PS: В данной области (сжатие данных) я не специалист.

если ты опишешь свою задачу более подробно (зачем это делается) и дашь
характеристики оборудования и своей системы программирования (можно ли
использовать внешние библриотеки на Си и т.п.), то я тебе смогу подсказать
более конкретные враианты

Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833

... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир

[Alexander Lysenko]

Post by Bulat Ziganshin
* Originally in RU.COMPRESS
если ты опишешь свою задачу более подробно (зачем это делается) и дашь
характеристики оборудования и своей системы программирования (можно ли
использовать внешние библриотеки на Си и т.п.), то я тебе смогу подсказать
более конкретные враианты

Ну, вобщем задача:

Из базы данных выбирается набор записей (может миллион, а может 10
миллионов) с несколькими десятками полей,
причем поля часто повторяются (проверено, что rar-ом све это сжимается раз в
10-15 а может быть и больше), другими словами - денормализованная таблица -
ключевые поля могут быть строками (и строки могут повторяться десятки тысяч
раз). Вобщем интересно это все сохранить на клиентской машине в сжатом виде,
причем таблица только хранится и не редактируется, информация только
"показывается" и "обрабатывается". Интересно было бы поиметь доступ к
произвольной записи или блоку записей по их номеру с минимальными затратами
процессорного времени.

Железо Celeron 1700, 256 Мб, WinXP. Инструмент Delphi7

ранее спасибо. Саша.

[Maxim Smirnov]

Wed Jan 26 2005 09:55, Alexander Lysenko wrote to Bulat Ziganshin:

AL> Из базы данных выбирается набор записей (может миллион, а может 10
AL> миллионов) с несколькими десятками полей,

Точно речь идет о миллионах записей?
Какова средняя длина строки? Каков реальный размер данных?
Судя по всему, данные не будут помещаться в ОЗУ клиента.

AL> причем поля часто повторяются (проверено, что rar-ом све это сжимается
AL> раз в 10-15 а может быть и больше), другими словами - денормализованная
AL> таблица - ключевые поля могут быть строками (и строки могут повторяться
AL> десятки тысяч раз). Вобщем интересно это все сохранить на клиентской
AL> машине в сжатом виде, причем таблица только хранится и не редактируется,
AL> информация только "показывается" и "обрабатывается". Интересно было бы
AL> поиметь доступ к произвольной записи или блоку записей по их номеру с
AL> минимальными затратами процессорного времени.

Если данные целиком не помещаются в ОЗУ клиента, то возможность произвольного
доступа к строке на низком уровне (не API, предоставляемым для верхних
уровней) не особо актуальна. Выигрыш будет достигаться за счет сокращения
числа I/O и объема считываемых данных. Можно считывать и декодировать
сразу блоки. Тогда требования к алгоритму сжатия становятся менее
жесткими.

В общем, если блоками жать, то через учет вертикальных зависимостей.
Если набор уже отсортирован, то кодируем разность относительно
значения колонки для предыдущей строки или, что может быть
быстрее, относительно значения колонки для первой строки блока.
Если не отсортирован, то лучше по возможности отсортировать.

Желательно обратить денормализацию. Вероятно, мы знаем, как выглядит
схема в нормальной форме, поэтому нет нужды писать анализатор,
выявляющий факты денормализованности.

Если обеспечивать произвольный доступ, то примерно так:

- формируем словарь для колонки, заменяем значения на их
индексы в словаре; (если предварительно словарь отсортировать,
то можно сравнивать индексы с точно таким же результатом,
как сравнение исходных строк -- т.е. сохраняется упорядочивание);

- убираем ведущие, оконечные нули и пробелы по вкусу;

- в качестве альтернативы словарю для числовых колонок можно
рассмотреть такой вариант: находим нижнюю и верхнюю границу
для реальной области значений, кодируем текущее значение как смещение
относительно границы;

- устраняем поля-константы;

- если знаем, что значение одного поля однозначно или почти
однозначно определяется значением другой колонки (или пары других
колонок -- большее число крайне редко оправдано), то может быть
выгодно для каждого значения независимого поля составить словарь
возможных значений зависимого поля; если зависимость функциональная,
то зависимая колонка может вообще не записываться; иначе
кодируем значение зависимой колонки через его индекс в
соответствующем словаре (словаре для текущего значения
независимой колонки).

В общем, есть еще много других финтов ушами, надо смотреть
конкретно.

Кстати, м.б. имеет смысл использовать MySQL с включенным сжатием
ISAM-таблицы.

Посмотрите:
http://www.compression.ru/download/articles/db/smirnov_2003_database_compressio
n_review/part3.html#_Toc73095291
(и вообще пролистайте)

Hа странице http://www.compression.ru/download/db.html
есть ссылки на:
Westmann T., Kossmann D., Helmer S., Moerkotte G. The implementation and
performance of compressed databases.
Roth M.A., Van Horn S. Database compression.
Ng W.K., Ravishankar C.V. Block-Oriented Compression Techniques for Large
Statistical Databases.

Maxim

[Alexander Lysenko]

Post by Maxim Smirnov
Кстати, м.б. имеет смысл использовать MySQL с включенным сжатием
ISAM-таблицы.

http://www.compression.ru/download/articles/db/smirnov_2003_database_compres
sio

Post by Maxim Smirnov
n_review/part3.html#_Toc73095291
(и вообще пролистайте)
Hа странице http://www.compression.ru/download/db.html
Westmann T., Kossmann D., Helmer S., Moerkotte G. The implementation and
performance of compressed databases.
Roth M.A., Van Horn S. Database compression.
Ng W.K., Ravishankar C.V. Block-Oriented Compression Techniques for Large
Statistical Databases.
Maxim

За инфу большое спасибо, буду изучать.
Саша