LINUX.ORG.RU
Форум — Development  

Подскажите подходящий алгоритм сжатия

 ,


0

1

Вопрос к тем, кто интересуется алгоритмами сжатия без потерь, может можете подсказать?

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

Интересует в первую очередь название какого-нибудь уже известного алгоритма.

★

Любой алгоритм, сжимать блоками по N килобайт, где N выбирается как компромисс между степенью сжатия и оверхедом по времени работы. Рядом с блоками хранить отображение номера строки в оффсет начала блока + оффсет внутри блока, распаковывать целиком блок и вытаскивать оттуда. Чем больше блок, тем лучше будет сжатие, но тем больше нерелевантных данных придётся распаковывать на каждый запрос.

Если что, все ФС с прозрачным сжатием устроены точно так же.

Алгоритмов сжатия, в которых можно было бы разжимать с произвольного места побайтово, я не знаю.

intelfx ★★★★★
()
Последнее исправление: intelfx (всего исправлений: 2)
Ответ на: комментарий от intelfx

Рядом с блоками хранить отображение номера строки

Ему не нужны номера строк, только номера байтов. Так что этот пункт отменяется, а остальное становится ещё проще.

firkax ★★★★★
()
Последнее исправление: firkax (всего исправлений: 1)

zlib с его gzseek вполне подходит для бегония по сжатому массиву байт.

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

Как-то дурно пахнет. Доступ к i-ому элементу за O(n). Вынеси указатель + размер в отдельный массив.

Если нужно эти строки ещё и менять, то смотри key-value хранилище в твоём языке программирования.

на самом деле их много таких массивов

И их больше нескольких гигобайт?

З.Ы.: Ну и все варианты прогони через benchmark. А то современные ОС вполне не плохо кешируют в памяти файлы.

AlexVR ★★★★★
()
Ответ на: комментарий от AlexVR

zlib с его gzseek вполне подходит для бегония по сжатому массиву байт.

If file is open for reading, the implementation may still need to uncompress all of the data up to the new offset. As a result, gzseek() may be extremely slow in some circumstances.

А на практике как оно работает?

intelfx ★★★★★
()

https://github.com/siara-cc/Unishox

https://github.com/kampersanda/xcdat

Compressed string dictionary. Xcdat implements a (static) compressed string dictioanry that stores a set of strings (or keywords) in a compressed space while supporting several search operations. For example, Xcdat can store an entire set of English Wikipedia titles at half the size of the raw data.

dataman ★★★★
()
Последнее исправление: dataman (всего исправлений: 1)
Development