Эффективный алгоритм сжатия для коротких текстовых строк
Я ищу алгоритм для сжатия небольших текстовых строк: 50-1000 байт (т.е. URL). Какой алгоритм лучше всего подходит для этого?
7 ответов
Проверьте Смаз:
Smaz - простая библиотека сжатия, подходящая для сжатия очень коротких строк.
У Хаффмана статическая цена, стол Хаффмана, поэтому я не согласен, что это хороший выбор.
Есть адаптивные версии, которые покончили с этим, но степень сжатия может пострадать. На самом деле, вопрос, который вы должны задать, это "какой алгоритм сжимать текстовые строки с этими характеристиками". Например, если ожидаются длинные повторения, может быть достаточно простого кодирования Run-Lengh. Если вы можете гарантировать, что будут присутствовать только английские слова, пробелы, знаки препинания и случайные цифры, то Хаффман с заранее определенной таблицей Хаффмана может дать хорошие результаты.
Как правило, алгоритмы семейства Lempel-Ziv имеют очень хорошее сжатие и производительность, и библиотек для них предостаточно. Я бы пошел с этим.
Имея информацию о том, что сжимаются URL-адреса, я бы посоветовал, чтобы перед сжатием (с любым легкодоступным алгоритмом) вы их кодировали. URL-адреса следуют четко определенным шаблонам, а некоторые его части весьма предсказуемы. Используя эти знания, вы можете с самого начала систематизировать URL-адреса во что-то меньшее, и в этом вам могут помочь идеи кодирования Хаффмана.
Например, переводя URL-адрес в битовый поток, вы можете заменить "http" на бит 1, а все остальное на бит "0", за которым следует фактический протокол (или использовать таблицу для получения других распространенных протоколов, таких как https, ftp, файл). "://" может быть полностью удален, если вы можете отметить конец протокола. И т.д. Читайте о формате URL и подумайте, как их можно кодифицировать, чтобы занять меньше места.
У меня нет кода под рукой, но мне всегда нравился подход к созданию двумерной справочной таблицы размером 256 * 256 символов ( RFC 1978, протокол сжатия PPP Predictor). Чтобы сжать строку, вы перебираете каждый символ и используете таблицу поиска, чтобы получить "предсказанный" следующий символ, используя текущий и предыдущий символы в качестве индексов в таблице. Если есть совпадение, вы записываете 1 бит, в противном случае пишите 0, символ и обновите таблицу поиска текущим символом. Этот подход в основном поддерживает динамическую (и грубую) таблицу поиска наиболее вероятного следующего символа в потоке данных.
Вы можете начать с нулевой таблицы поиска, но, очевидно, она лучше всего работает с очень короткими строками, если она инициализируется наиболее вероятным символом для каждой пары символов, например, для английского языка. Пока исходная таблица поиска одинакова для сжатия и распаковки, вам не нужно передавать ее в сжатые данные.
Этот алгоритм не дает блестящей степени сжатия, но он невероятно экономен с памятью и ресурсами ЦП, а также может работать с непрерывным потоком данных - декомпрессор сохраняет свою собственную копию таблицы поиска по мере ее распаковки, таким образом, таблицу поиска приспосабливается к типу сжимаемых данных.
Любой алгоритм / библиотека, которая поддерживает предустановленный словарь, например, zlib.
Таким образом, вы можете заполнить компрессор тем же текстом, который может появиться на входе. Если файлы в некотором роде похожи (например, все URL-адреса, все программы на C, все сообщения Stackru, все рисунки в формате 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%.