Два варианта кодирования длин серий — это кодирование диаграмм и алгоритмы замены шаблонов. Кодирование диаграмм на самом деле очень простой алгоритм. В отличие от кодирования по длине прогона, где входной поток должен состоять из множества повторяющихся элементов, например , «aaaaaaaa» , что очень редко встречается на естественном языке, существует много так называемых «диаграмм» почти на любом естественном языке. В простом английском языке есть некоторые диаграммы, такие как «the» , «and» , «ing» (например, в слове «ожидание»), «a» , «t» , «e» и много сдвоенных букв.
На самом деле мы можем расширить эти диаграммы, добавив окружающие пробелы. Таким образом, мы можем закодировать не только «, но и», то есть 5 символов (2 пробела и 3 буквы) с чем-то более коротким. С другой стороны, как я уже сказал, на простом английском языке слишком много двойных букв, что, к сожалению, не является чем-то особенным для кодирования длин серий, и степень сжатия будет небольшой. Еще хуже то, что закодированный текст может оказаться длиннее входного сообщения. Давайте посмотрим несколько примеров.
Допустим, нам нужно закодировать сообщение «успешно выполнено», которое состоит из четырех сдвоенных букв. Однако, чтобы сжать его кодированием по длине прогона, нам понадобится как минимум 8 символов, что нам мало поможет.
// 8 chars replaced by 8 chars!? input: "successfully accomplished" output: "su2ce2sfu2ly a2complished"
Проблема в том, что если входной текст содержит числа, в частности «2», нам нужно выбрать управляющий символ (например, «@»), который мы будем использовать, чтобы отметить начало кодированного прогона. Таким образом, если входное сообщение представляет собой «2 успешно выполненные задачи», оно будет закодировано как «2 su @ 2ce @ 2sfu @ 2ly a @ 2comported заданий». Теперь вывод сообщения длиннее !!! чем входная строка.
// the compressed message is longer!!! input: "2 successfully accomplished" output: "2 su@2ce@2sfu@2ly a@2complished tasks"
Опять же, если входной поток содержит escape-символ, мы должны найти другой, и проблема в том, что часто слишком сложно найти короткий escape-символ, который не появляется во входном тексте, без полного сканирования текста.
Вот почему кодирование по длине прогона не является хорошим решением при сжатии простого текста, где длинные прогоны редко появляются. Ну, конечно, есть исключения. Например, таким исключением является сжатие текста с потерями с кодированием длины строки. Интуитивно понятно, что сжатие текста с потерями редко бывает полезно, особенно если вам нужно распаковать точно такой же текст. Однако в некоторых случаях может быть полезно сжатие с потерями. Такой случай может быть удаление пробелов. Действительно, текст «успешно выполнено» приносит нам ту же информацию, что и «успешно выполнено» . В этом случае мы можем просто удалить эти пробелы. На самом деле мы можем использовать маркер для обозначения длинных пробелов типа «успешно @ 6 выполнено»чтобы распаковать входную строку без потерь, но мы также можем выбросить эти символы. Это решение зависит от цели. Точно с той же целью мы можем удалить новые строки и вкладки, только если мы уверены, что смысл текста сохранен. Еще раз, проблема в том, что такие длинные периоды не случаются в случайных текстах. Вот почему лучше использовать кодирование диаграмм для сжатия простого текста, а не кодирование по длине прогона.
Несколько вопросов
После понимания принципов кодирования диаграмм давайте рассмотрим несколько примеров. В приведенном выше примере лучше заменить дублированные буквы чем-то более коротким. Допустим, # для «cc», @ для «ss» и% для «ll». Таким образом, входной текст будет сжат как «su # e @ fu% ya # omplished», что короче. Но опять же, что произойдет, если входное сообщение содержит одну из замен? Также мы не можем сказать, есть ли много удвоенных букв и достаточно ли разумных замен для них. Лучший подход — заменить шаблоны.
Кодирование длин серий не является подходящим подходом для сжатия текста, поскольку длинные циклы редко появляются на естественном языке.
Замена шаблона
The pattern substitution algorithm is a variant of the diagram encoding. As I said above in plain English a very commonly used pattern can be “ the “, which is five characters long. We can now replace it with something like “$%” for example. In this case the message “I send the message” will become “I send$%message”. However there are some obstacles to overcome.
The first problem is that we need to know the language and somehow to define commonly used patterns in a dictionary. What would happen with a message written in some language we don’t know nothing about. Let’s say – Latin like the example bellow.
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Cras venenatis, sapien eget suscipit placerat, justo quam blandit mauris, quis tempor ante sapien sodales augue. Praesent ut mauris quam. Phasellus scelerisque, ante quis consequat tristique, metus turpis consectetur leo, vitae facilisis sapien mi eu sapien. Praesent vitae ligula elit, et faucibus augue. Sed rhoncus sodales dolor ut gravida. In quis augue ac nulla auctor mattis sed sed libero. Donec eget purus eget enim tempor porta vitae eget diam. Mauris aliquet malesuada ipsum, non pulvinar urna vestibulum ac. Donec feugiat velit vitae nunc cursus imperdiet. Donec accumsan faucibus dictum. Phasellus sed mauris sapien. Maecenas mi metus, tincidunt sed rhoncus nec, sodales non sapien.
Clearly without knowing Latin it isn’t easy to define which are those commonly used patterns. The thing is that it’s better to use pattern substitution if you know in advance the set of words and characters.
The second problem is related to decompression. It is obvious that we need to define a dictionary and this dictionary must be used when decoding the message. It will be great also if we find more patterns longer than three characters. If not, the compression ratio will be low. Unfortunately such patterns aren’t very common in any natural language.
Diagram encoding and pattern substitution are far more suitable for text compression than run-length encoding. In fact, pattern substitution is very effective on compressing programming languages.
Application
It is interesting to answer the question, how to use diagram encoding or patter substitution to compress text in natural language, especially when we don’t know the language in detail? The answer hides in the question. We wont compress natural languages, but machine language. Exactly machine (programming) languages are limited to a smaller sets of words and symbols. Isn’t it true for any programing language? Like PHP, where words like “function”, “while”, “for”, “break”, “switch”, “foreach” happen to be often in use, or HTML with its defined set of tags. Perhaps the best example is CSS, where only the values of the properties can vary. CSS files also tend to have multiple new lines, tabs and spaces, which only humans read.
The question here is why should we compress those file types. It’s clear that after the compression they will be completely useless, both for humans and machines. Yes, that is true, but what if we have to store versions of those files into a DB. Kind of a backup. Imagine you’re working for a web hosting company that has to store daily versions of the sites it’s hosting. Thus the volume of stored information even for small companies hosting only few sites can be enormous. The problem is that compressing those files with some conventional compressing tool isn’t a good idea. Thus we’ve to save a copy of the entire site every day, but as we know the difference between daily versions of a site can be small. A version control system is another solution, but then you’ve to store the plain text of the files.
Perhaps a better approach is to compress the text using pattern substitution and then saving only differences – kind of version control, which can be done with “relative encoding”.
Using the above method we can save lots of disk space and in the same time we can compress/decompress easily. Another good thing is that you can save only changes to the initial files, like version control, which can also be compressed.
Implementation
The implementation of this algorithm is again on PHP and tries only to describe the main principles of compression. In this case I tried to compress a CSS file using the compression above. Although this example is quite primitive we can see some interesting facts. First of all you only need encoding and decoding dictionaries. Practically the encoding and decoding processes are equal, so you don’t need to implement two different functions. Here in this example a native PHP function is used – str_replace, because the purpose of this algorithm is not to describe pattern substitution techniques, but pattern substitution. It assumes that today’s programming languages have string manipulation functions for the purposes of this task.
$str = file_get_contents('large_style_file.css');
$encoding_dict = array(
"\n" => '$0',
'text' => '$1',
'color' => '$2',
'display' => '$3',
'font' => '$4',
'width' => '$5',
'height' => '$6',
' ' => '',
);
function replace_patterns($input, $dict)
{
foreach ($dict as $pattern => $replace) {
$input = str_replace($pattern, $replace, $input);
}
return $input;
}
$result = replace_patterns($str, $encoding_dict);
By only replacing few CSS properties I achieved almost 40% of compression ratio (as shown the diagram bellow). The initial file is 202 KB, while compressed it’s only 131 KB. Of course, it all depends on the CSS file, but how about replacing all property names with shorter ones. Perhaps then the compression will be even better.
