Эффективный алгоритм сжатия коротких текстовых строк [закрыто]

Я ищу алгоритм для сжатия небольших текстовых строк: 50-1000 байт (то есть URL-адресов). Какой алгоритм лучше всего подходит для этого?

Проверьте Smaz :

Smaz - это простая библиотека сжатия, подходящая для сжатия очень коротких строк.

У Хаффмана есть статическая стоимость, таблица Хаффмана, поэтому я не согласен, что это хороший выбор.

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

В целом алгоритмы семейства Lempel-Ziv имеют очень хорошее сжатие и производительность, а библиотек для них предостаточно. Я бы пошел с этим.

Имея информацию о том, что сжимаются URL-адреса, я бы предложил, чтобы перед сжатием (с помощью любого легко доступного алгоритма) вы их КОДИФИРОВАТЬ. URL-адреса следуют четко определенным шаблонам, и некоторые их части очень предсказуемы. Используя эти знания, вы можете для начала кодировать URL-адреса во что-то меньшее, и идеи, лежащие в основе кодирования Хаффмана, могут вам здесь помочь.

Например, переводя URL-адрес в битовый поток, вы можете заменить «http» битом 1, а все остальное - битом «0», за которым следует фактический протокол (или использовать таблицу для получения других общих протоколов, таких как https, ftp, файл). Знак ": //" можно вообще отбросить, если вы можете отметить конец протокола. И т. Д. Прочтите о формате URL и подумайте, как их можно кодировать, чтобы они занимали меньше места.

У меня нет кода под рукой, но мне всегда нравился подход к построению 2D-таблицы поиска размером 256 * 256 символов ( RFC 1978 , PPP Predictor Compression Protocol ). Чтобы сжать строку, вы перебираете каждый символ и используете таблицу поиска, чтобы получить «предсказанный» следующий символ, используя текущий и предыдущий символы в качестве индексов в таблице. Если есть совпадение, вы записываете один бит 1, в противном случае пишете 0, символ и обновляете таблицу поиска текущим символом. Этот подход в основном поддерживает динамическую (и грубую) таблицу поиска наиболее вероятного следующего символа в потоке данных.

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

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

Любой алгоритм / библиотека, поддерживающая предустановленный словарь, например zlib .

Таким образом, вы можете заполнить компрессор тем же текстом, который может появиться во входных данных. Если файлы в чем-то похожи (например, все URL-адреса, все программы на C, все сообщения StackOverflow, все рисунки в формате ASCII), то определенные подстроки появятся в большинстве или во всех входных файлах.

Каждый алгоритм сжатия экономит место, если одна и та же подстрока повторяется несколько раз в одном входном файле (например, «the» в английском тексте или «int» в коде C.)

Но в случае URL-адресов определенные строки (например, « http: // www .», «.Com», «.html», «.aspx» обычно появляются один раз в каждом входном файле. Таким образом, вам необходимо поделиться ими между файлами. каким-то образом вместо того, чтобы иметь по одному сжатому экземпляру для каждого файла - этого можно добиться, поместив их в предустановленный словарь.

Кодирование Хаффмана обычно подходит для этого.

Если вы говорите о фактическом сжатии текста, а не просто об его сокращении, тогда Deflate / gzip (оболочка вокруг gzip), zip хорошо работает для файлов и текста меньшего размера. Другие алгоритмы очень эффективны для больших файлов, таких как bzip2 и т. Д.

В Википедии есть список времен сжатия. (ищите сравнение эффективности)

Name       | Text         | Binaries      | Raw images
-----------+--------------+---------------+-------------
7-zip      | 19% in 18.8s | 27% in  59.6s | 50% in 36.4s
bzip2      | 20% in  4.7s | 37% in  32.8s | 51% in 20.0s
rar (2.01) | 23% in 30.0s | 36% in 275.4s | 58% in 52.7s
advzip     | 24% in 21.1s | 37% in  70.6s | 57& in 41.6s
gzip       | 25% in  4.2s | 39% in  23.1s | 60% in  5.4s
zip        | 25% in  4.3s | 39% in  23.3s | 60% in  5.7s

Возможно, вы захотите взглянуть на стандартную схему сжатия для Unicode .

SQL Server 2008 R2 использует его для внутренних целей и может обеспечить сжатие до 50%.