Технологии сжатия

По этому поводу сразу можно посмотреть:

Compression and Fast Indexing for Multi-Gigabyte Text Databases

Justin Zobel, Alistair Moffat, Ron Sacks-Davis: An Efficient Indexing Technique for Full Text Databases

ну или ссылку.

Для меня критична независимость алгоритма сжатия от структуры данных так как я сжимаю не только обычный инвертированный позиционный индекс описанный в первой предложенной вам книге но и другие структуры данных которые нужны для других задач

Просто хотелось одолеть эту проблему малыми силами

Может тогда стоит начать с http://www.datacompression.info/ или http://www.compression.ru/ и выбирать алгоритм сжатия под ваши проблемы.

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

В конце концов, может оказаться, что не так важно даже однозначное восстановление, например, JPEG. На этом можно очень много выиграть и по сжатию, и по скорости.

В статье http://www.dialog-21.ru/directions/Segalovich_vorprint.doc упоминается

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

ЖЕНЩИНА: [Быт.1],[+11],[0],[+2],[+4],[+2],[+4],..

Дополнительно на разностный способ хранения адресов накладывают какой-нибудь простенький способ упаковки: зачем отводить небольшому целому числу фиксированное "огромное" количество байт, ведь можно отвести ему почти столько байт, сколько оно заслуживает. Здесь уместно упомянуть коды Голомба или встроенную функцию популярного языка Perl: pack("w").

Староватые ссылки, Вячеслав, староватые. :)

Во первых, у этих австралийских ребят вышла в 99-м году книжка Managing Gigabytes. Код для нее валяется в сети. Я от нее не в восторге, но если вам надо непременно про все знать, про что написали Зобель с Моффатом, купите ее на Амазоне.

А во-вторых на предпоследнем SIGIR-е (кажется) до Зобеля наконец дошло то, что мне стало предельно ясно в 1993-м, а именно, что сжимать надо до границам байта. По пространству проигрыш копеешный, а по скорости распаковки/запаковки - в разы быстрее.

Ссылку на статью не даю - она все равно на ACM. А предложить русскому человеку платить за контент, все равно, что в душу плюнуть :))

In experiments on large collections of data, we show two surprising results: use of simple byte-aligned codes halves the query evaluation time compared to the most compact Golomb-Rice bitwise compression schemes.

Тоже мне бином товарища Ньютона. В общем странные они ребята.

Я не понял, вы что пишете для PDA или ракетоносителей? У вас что, дефицит простарнства для сегмента кода?

Если это не так, то вам нужно взять два РАЗНЫХ алгоритма, и не морочить людям голову.

Можно пояснить что вы имеете ввиду упоминая сегмент кода?

Может это внесло неясность но фразу "малыми силами" я имел ввиду применительно к затратам на программирование

То есть мне не хотелось бы разрабатывать различные алгоритмы под различные структуры данных(которые могут быть достаточно сложными) поэтому я и попросил совета: возможно кто нибудь поможет с подбором универсального и производительного алгоритма и его готовой реализации

CS - Code Segment, где размещается исполняемый код. Неплохо было бы просмотреть курс программирования на ассемблере :)

iseg вроде уже описал оптимальный алгоритм сжатия инвертированных файлов:

Считаете в координатах смещение и храните его в индексе.

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