Оболочка Delphi TStringList для реализации сжатия на лету

Question

У меня есть приложение для хранения многих строк в TStringList.Строки будут в значительной степени похожи друг на друга, и мне приходит в голову, что их можно сжать на лету - то есть сохранить заданную строку в виде смеси уникальных текстовых фрагментов плюс ссылки на ранее сохраненные фрагменты.Строковые списки, такие как списки полностью определенных путей и имен файлов, должны быть в состоянии сильно сжаты.

Кто-нибудь знает о потомке TStringlist, который реализует это - то есть предоставляет доступ для чтения и записи к несжатым строкам, но хранит их внутреннесжатый, так что TStringList.SaveToFile создает сжатый файл?

Хотя вы могли бы реализовать это, распаковывая весь список строк перед каждым доступом и повторно сжимая его впоследствии, это было бы излишне медленным.Я за чем-то, что эффективно для инкрементальных операций и случайных «ищет» и читает.

TIA Ross

Answer 1

Я не думаю, что есть какая-либо свободно доступная реализация для этого (не то, что я знаю в любом случае, хотя я написал по крайней мере 3 подобных конструкции в коммерческом коде), так что вам придется свернуть свою собственную.

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

Еще одна вещь, о которой вы, возможно, захотите прочитать, это «веревки» - концептуально иной тип, нежели струны, которые я уже предложил Марко Канту некоторое время назад. Ценой следующего указателя на «шпагат» (из-за отсутствия лучшего слова) вы можете объединять части строки без сохранения дублирующих данных. Основная проблема заключается в том, как извлечь части, которые можно объединить в новую «веревку», представляющую исходную строку. Как только эта проблема будет решена, вы можете в любое время восстановить данные в виде строки, сохраняя компактное хранилище.

Если вы не хотите идти по «веревочному» маршруту, вы также можете попробовать что-то под названием «сокращение префикса», что является простой формой сжатия - просто начните каждую строку с индекса предыдущей строки и количество символов, которые должны рассматриваться как префикс для новой строки. Помните, что вы должны не повторять это слишком далеко назад, иначе скорость доступа сильно пострадает. В одной простой реализации я сделал mod 16 для индекса, чтобы установить запись, с которой началось уменьшение префикса, что дало мне в среднем около 40% экономии памяти (это число, конечно, полностью зависит от данных).

Answer 2

Не думаю, что вы действительно хотите сжать элементы TStrings в памяти, потому что это ужасно неэффективно. Я предлагаю вам взглянуть на реализацию TStream в модуле Zlib. Просто поместите обычный поток в TDecompressionStream при загрузке и TCompressionStream при сохранении (вы даже можете создать там заголовок gzip). Подсказка: вы захотите переопределить LoadFromStream / SaveToStream вместо LoadFromFile / SaveToFile

Answer 3

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

• Вы разбиваете строку на слова и сохраняете отдельный растущий словарь для ссылки на слова и внутренне сохраняете список индексов

• Вы реализуете что-то связанное с потоком zlib, доступным в Delphi, но работает с блоком, который, например, может содержать 10-100 строк.В этом случае вам все равно придется повторно сжать / сжать весь блок, но «цена», которую вы платите, ниже.

Answer 4

Вы можете попытаться обернуть Delphi или COM API вокруг массивов Джуди .Тип JudySL справится с задачей и имеет довольно простой интерфейс.

РЕДАКТИРОВАТЬ: я предполагаю, что вы храните уникальные строки и хотите (или рады) хранить их в лексикографическом порядке.Если эти ограничения не приемлемы, то массивы Джуди не для вас.Имейте в виду, любая система сжатия пострадает, если вы не сортируете свои строки.