хранение сжатой строки

Question

Допустим, у меня есть много объектов, содержащих строки нетривиальной длины (около ~ 3-4 КБ).Строки все отличаются друг от друга, но в то же время содержат много общих частей / подпоследовательностей.В среднем, возможно, 80-90% любой отдельной строки содержится вместе с другими.Есть ли простой способ автоматически использовать эту огромную избыточность для сжатия данных?
В идеале решение должно быть C ++ и прозрачным для пользователя (т.е. я могу использовать его так, как если бы я обращался к обычному const std :: string только для чтения)но вместо чтения из сжатого хранилища).

Answer 1

Вы можете использовать кодирование Хаффмана Реализация не сложно, также есть алгоритмы zip на языках (например, C # и Java), и вы можете использовать их.

Также Если вы уверены, что 80-90% повторяется всего, создайте словарь всех слов, затем для каждой строки сохраняйте позицию словарного слова, значит, имеете битовый массив большого размера (т.е. 10000 т. Е.) И отмечайте соответствующую позицию от bits[i] до 1, еслиwords[i] существует в текущей строке.Думайте, что длина каждого слова составляет 5 символов, тогда сокращение занимает около 1/5 размера.

Answer 2

Алгоритмически, Лемпель-Зив-Уэлч с одним словарем для всех объектов / строк может быть хорошим началом.

Answer 3

Если общие части строк являются общими, потому что они составлены из других строк, то вы можете получить некоторую тягу, используя класс stlport rope, который выглядит для всего мира как std :: string, но использует представление дерева подстрок с копией при записи, что делает их очень экономящими место (общие подстроки разделяются) и очень хорошо вставляет и удаляет (log (n))

Когда использовать веревку:

• вы делаете шаблонный движок. экземпляры документа создаются из шаблона путем замены в шаблоне различных данных, а затем кэшируются для использования в будущем. Части, которые являются общими для шаблонов и экземпляров, сохраняются только один раз и разделяются между экземплярами, вставки и удаления дешевы.

Когда не использовать веревку:

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

Answer 4

Как упомянуто @Saeed, простое кодирование Хаффмана будет хорошо работать здесь.

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