эффективный алгоритм сжатия коротких текстовых строк

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

<p>проверьте <a href="https://github.com/antirez/smaz">смаз</a> :</p><blockquote> <p>smaz - простая библиотека сжатия, подходящая для сжатия очень коротких строк.</p> </blockquote>

<p>у хаффмана статическая цена, стол хаффмана, поэтому я не согласен, что это хороший выбор.</p><p>есть адаптивные версии, которые устраняют это, но степень сжатия может пострадать. на самом деле, вопрос, который вы должны задать, это "какой алгоритм сжатия текстовых строк с этими характеристиками". например, если ожидаются длинные повторения, может быть достаточно простого кодирования run-lengh. если вы можете гарантировать наличие только английских слов, пробелов, знаков препинания и случайных цифр, то хаффман с заранее определенной таблицей хаффмана может дать хорошие результаты.</p><p>как правило, алгоритмы семейства lempel-ziv имеют очень хорошее сжатие и производительность, и библиотек для них предостаточно. я бы пошел с этим.</p><p>имея информацию о том, что сжимаются url-адреса, я бы посоветовал, чтобы перед сжатием (с любым легкодоступным алгоритмом) вы их кодировали. url-адреса следуют четко определенным шаблонам, а некоторые его части весьма предсказуемы. используя эти знания, вы можете с самого начала систематизировать url-адреса во что-то меньшее, и в этом вам могут помочь идеи кодирования хаффмана.</p><p>например, переводя url в битовый поток, вы можете заменить "http" битом 1, а все остальное - битом "0", за которым следует фактический протокол (или использовать таблицу для получения других распространенных протоколов, таких как https, ftp, файл). ": //" может быть полностью удален, если вы можете отметить конец протокола. и т.д. пойдите, прочитайте о формате url, и подумайте, как их можно кодифицировать, чтобы занять меньше места.</p>

<p>у меня нет кода под рукой, но мне всегда нравился подход к созданию двумерной справочной таблицы размером 256 * 256 символов ( <a href="http://tools.ietf.org/html/rfc1978">rfc 1978</a> , <em> сжатие предиктора ppp протокол </em>). чтобы сжать строку, вы перебираете каждый символ и используете таблицу поиска, чтобы получить "предсказанный" следующий символ, используя текущий и предыдущий символы в качестве индексов в таблице. если есть совпадение, вы записываете 1 бит, в противном случае пишите 0, символ и обновите таблицу поиска текущим символом. этот подход в основном поддерживает динамическую (и грубую) таблицу поиска наиболее вероятного следующего символа в потоке данных.</p><p>вы можете начать с нулевой таблицы поиска, но, очевидно, она лучше всего работает с очень короткими строками, если она инициализируется наиболее вероятным символом для каждой пары символов, например, для английского языка. пока исходная таблица поиска одинакова для сжатия и распаковки, вам не нужно отправлять ее в сжатые данные.</p><p>этот алгоритм не дает блестящей степени сжатия, но он невероятно экономен с памятью и ресурсами цп, а также может работать с непрерывным потоком данных - декомпрессор сохраняет свою собственную копию таблицы поиска по мере распаковки, таким образом, таблицу поиска настраивается на тип сжатых данных.</p>

<p>любой алгоритм/библиотека, которая поддерживает предустановленный словарь, например <a href="http://www.zlib.net/manual.html">zlib</a> .</p><p>таким образом, вы можете заполнить компрессор тем же текстом, который может появиться на входе. если файлы в некотором роде похожи (например, все url-адреса, все программы на c, все сообщения stackoverflow, все рисунки в формате ascii), то определенные подстроки появятся в большинстве или во всех входных файлах.</p><p>каждый алгоритм сжатия будет экономить место, если одна и та же подстрока повторяется несколько раз в одном входном файле (например, "the" в английском тексте или "int" в коде c.)</p><p>но в случае url-адресов определенные строки (например, " <a href="http://www">http: // www</a> .", ".com", ".html", ".aspx" обычно появляются один раз в каждом входном файле. вам нужно как-то делиться ими между файлами, а не иметь одно сжатое вхождение на файл, это можно сделать, поместив их в заданный словарь.</p>

<p>если вы говорите о фактическом сжатии текста, а не только об укорочении, тогда deflate/gzip (обертка вокруг gzip), zip хорошо работают для небольших файлов и текста. другие алгоритмы очень эффективны для больших файлов, таких как bzip2 и т.д.</p><p> <a href="http://en.wikipedia.org/wiki/comparison\_of\_file\_archivers">википедия</a> есть список времени сжатия. (посмотрите на сравнение эффективности)</p><pre><code>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 </code></pre>

<p> <a href="http://en.wikipedia.org/wiki/huffman\_coding">кодирование хаффмана</a> как правило, работает хорошо для этого.</p>

<p>возможно, вы захотите взглянуть на <a href="http://en.wikipedia.org/wiki/standard\_compression\_scheme\_for\_unicode">стандартная схема сжатия для unicode</a> .</p><p>sql server 2008 r2 использует его внутри и может обеспечить сжатие до 50%.</p>