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

Huffman has a static cost, the Huffman table, so I disagree it's a good choice.

There are adaptative versions which do away with this, but the compression rate may suffer. Собственно, вопрос, который вы должны задать, - «какой алгоритм сжатия текстовых строк с такими характеристиками». Например, если ожидается долгое повторение, может быть достаточно простого кодирования Run-Lengh. Если вы можете гарантировать, что будут присутствовать только английские слова, пробелы, пунктиры и случайные цифры, то Хаффман с предварительно определенной таблицей Хаффмана может дать хорошие результаты.

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

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

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

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

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

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

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

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

Any algorithm/library that supports a preset dictionary, e.g. zlib.

This way you can prime the compressor with the same kind of text that is likely to appear in the input. If the files are similar in some way (e.g. all URLs, all C programs, all StackOverflow posts, all ASCII-art drawings) then certain substrings will appear in most or all of the input files.

Every compression algorithm will save space if the same substring is repeated multiple times in one input file (e.g. "the" in English text or "int" in C code.)

But in the case of URLs certain strings (e.g. "http://www.", ".com", ".html", ".aspx" will typically appear once in each input file. So you need to share them between files somehow rather than having one compressed occurrence per file. Placing them in a preset dictionary will achieve this.

Если вы говорите о фактическом сжатии текста, а не просто об его сокращении, тогда 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

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