lect_13 (1119092), страница 2
Текст из файла (страница 2)
Каждому символу присваивается такой же код. В рассматриваемом варианте используется 12 битный код, коды 256 и 257 – зарезервированы, соответственно под коды строк остаются значения 258…4095.
-
Считываем из входного потока в строку символ.
-
Проверяем, есть ли в нашем дереве такая строка. Строка есть в дереве, если опускаясь от его вершины до некоторой ветви мы встретим все символы строки. Если строка есть, то запоминаем ее код, и переходим к шагу 2, иначе к шагу 4.
-
Если строки нет, то выделяем для нее новый код, создаем у соответствующей веточки сына, и полагаем строку равной последнему считанному символу. Далее переходим к шагу 2.
К примеру, если исходная строка будет [h00] [h01] [h00] [h01] то дерево примет вид
а в выходной файл запишется строка 0, 1, 258.
Данный алгоритм можно улучшить, заметив, что в компрессированном файле не может появится значение 512, до того как появилось 511. Таким образом, числа можно записывать сначала как 9, потом, после встречи числа 512 как 10 битные, и так далее. Это, кстати, является хорошим примером того, когда мы можем сказать, что новая реализация алгоритма лучше старой, не оглядываясь на класс архивируемых изображений.
1 Хотя, довольно часто, мы можем сказать, что одна реализация одного и того же алгоритма или даже просто принципа компрессии лучше другой.
2 В алгоритме Motion JPEG, например, изменили порядок записи коэффициентов, чтобы сначала шли низко, потом средне, а потом высокочастотные компоненты изображения. В алгоритме Interlaced GIF поступили еще проще, просто записывая строчки изображения не подряд, а через четыре.
3 Иногда ошибочно думают, что “классический” алгоритм Хаффмана как раз и является алгоритмом, который даже в худшем случае не увеличит исходную цепочку. При этом совершенно забывают о том, что саму таблицу тоже надо хранить.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
