Поскольку сжатие без потерь работает лучше в некоторых областях, чем в других,
если вы храните сжатые данные в блоках удобной длины BLOCKSIZE, даже если каждый блок имеет одинаковое количество сжатых байтов, некоторые сжатые блоки будут расширяться до гораздо более длинного фрагмента открытого текста, чем другие.
Вы можете посмотреть на
«Сжатие: ключ к системам поиска текста следующего поколения»
Нивио Зивиани, Эдлено Сильва де Моура, Гонсало Наварро и Рикардо Баеза-Йейтс
в
Компьютер журнал Ноябрь 2000
http://doi.ieeecomputersociety.org/10.1109/2.881693
Их декомпрессор берет 1, 2 или 3 целых байта сжатых данных и распаковывает (используя словарный список) в целое слово.
Можно непосредственно искать в сжатом тексте слова или фразы,
что оказывается даже быстрее, чем поиск несжатого текста.
Их декомпрессор позволяет вам указывать на любое слово в тексте с помощью обычного (байтового) указателя и сразу же начинать распаковку с этой точки.
Вы можете дать каждому слову уникальный 2-байтовый код, поскольку в вашем тексте, вероятно, содержится менее 65 000 уникальных слов.
(В Библии KJV есть почти 13 000 уникальных слов).
Даже если существует более 65 000 слов, довольно просто назначить первые 256 двухбайтовых кодовых «слов» для всех возможных байтов, так что вы можете прописать слова, которые не входят в лексикон из 65 000 или около того «наиболее часто» слова и фразы".
(Сжатие, полученное путем упаковки частых слов и фраз в два байта
обычно стоит «расширение» случайного произнесения слова, используя два байта на букву).
Существует множество способов выбрать лексикон «частых слов и фраз», которые дадут адекватное сжатие.
Например, вы можете настроить компрессор LZW для вывода «фраз», которые он использует более одного раза, в файл лексикона, по одной строке на фразу, и запустить его для всех ваших данных.
Или вы можете произвольно разделить несжатые данные на 5-байтовые фразы в файле лексикона, по одной строке на фразу.
Или вы можете нарезать свои несжатые данные на настоящие английские слова и поместить каждое слово, включая пробел в начале слова, в файл лексикона.
Затем используйте "sort --unique", чтобы удалить дубликаты слов в этом файле лексикона.
(Выбор идеального «оптимального» словарного словаря все еще считается NP-сложным?)
Сохраните лексикон в начале вашего огромного сжатого файла, добавьте его к удобному BLOCKSIZE, а затем сохраните сжатый текст - серию из двух байтовых «слов» - оттуда до конца файла.
Предположительно, поисковик прочтет этот лексикон один раз и сохранит его в каком-либо формате быстрого декодирования в ОЗУ во время распаковки, чтобы ускорить распаковку «двухбайтового кода» до «фразы переменной длины».
Мой первый черновик начинался с простой строки в каждой фразе, но позже вы могли бы перейти к сохранению лексикона в более сжатой форме с использованием некоторого инкрементного кодирования или zlib.
Вы можете выбрать любое произвольное четное смещение байта в сжатый текст и начать декомпрессию оттуда.
Я не думаю, что возможно сделать более тонкий формат сжатого файла произвольного доступа.