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

Zram же как то рандомно адресует. Любой алгоритм и жать блоками. Из быстрых lz4

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

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

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

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

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

Есть специализированные алгоритмы для коротких строк, например, https://github.com/antirez/smaz, http://ed-von-schleck.github.io/shoco. Но для сжатия текста на русском скорее всего придётся генерить свои словари

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

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

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

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

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

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

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

количество байт строки, потом содержимое строки

любое сжатие блоком, например zlib + compress

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.

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

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.

В issue на zstd интересное обсуждение на тему. Там в том числе отписались авторы многих проектов, которые добавляли индекс поверх существующих форматов сжатия.