Быстрый поиск в сжатых текстовых файлах

Question

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

заранее спасибо

Answer 1

Большинство текстовых файлов сжимаются с помощью одного из семейств LZ алгоритмов, которые объединяют словарный кодер вместе с энтропийным кодером , таким как Хаффман.

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

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

Второе предложение - сделать кодирование Хаффмана английскими словами и забыть о части словаря кодировщика. Каждое английское слово сопоставляется с уникальным кодом без префиксов.

Наконец, @SHODAN дал наиболее разумное предложение: индексировать файлы, сжимать индекс и связывать сжатые текстовые файлы. Чтобы выполнить поиск, распакуйте только индексный файл и найдите слова. На самом деле это улучшение по сравнению с кодированием по Хаффману для слов - когда вы нашли частоту слов (для оптимального назначения префиксного кода), вы уже создали индекс, так что вы можете сохранить индекс для поиска.

Answer 2

Поиск текста в сжатых файлах может быть быстрее, чем поиск того же самого в несжатых текстовых файлах.

Одна техника сжатия, которую я видел, жертвует некоторым пространством для быстрого поиска:

• поддерживает словарь с 2 ^ 16 записями каждого слова в тексте.Зарезервируйте первые 256 записей для буквенных байтов, на случай, если вы встретите слово, которого нет в словаре - даже если во многих больших текстах содержится менее 32 000 уникальных слов, поэтому им не нужно использовать эти буквенные байты.
• Сжать исходный текст, заменив 16-битный индекс словаря для каждого слова.
• (необязательно) В обычном случае, когда два слова разделены одним пробелом, отбросьте этот пробел;в противном случае поместите все байты в строке между словами в словарь как специальное «слово» (например, «.» и «,» и «\ n»), помеченное атрибутом «без пробелов по умолчанию», а затем «сжатие»."эти строки, заменив их соответствующим индексом словаря.
• Поиск слов или фраз путем сжатия фразы аналогичным образом и поиск сжатой строки байтов в сжатом тексте точно так же, как выбудет искать исходную строку в исходном тексте.

В частности, поиск одного слова обычно сводится к сравнению 16-разрядного индекса в сжатом тексте, что быстрее, чем поиск этого словав исходном тексте, потому что

• каждое сравнение требует сравнения меньшего числа байтов - 2, а не столько байтов в этом слове, а
• мы делаем меньше сравнений, потому чтосжатый файл короче.

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

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

Для более изощренных методов вы можете взглянуть на

• MG4J: Управление гигабайтами для Java
• «Управление гигабайтами: сжатие и индексация документов и изображений» , Ян Х. Виттен, Алистер Моффат и Тимоти К. Белл

Answer 3

Маловероятно, что вы сможете искать несжатые строки в сжатом файле.Я думаю, один из ваших лучших вариантов - как-то индексировать файлы.Возможно, вы используете Lucene?

Answer 4

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

Answer 5

Это возможно и может быть сделано довольно эффективно.Есть много захватывающих исследований по этой теме, более формально известных как сжатая структура данных.Некоторые темы, которые я бы порекомендовал изучить: дерево вейвлетов, FM-индекс / RRR, массивы суффиксов с кратким изложением.Вы также можете эффективно искать строки, закодированные Хаффманом, как показали многочисленные публикации.