|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilia Kantor 2:5020/1815.6 08 Dec 2001 22:16:56
To : All
Subject : FAQ
--------------------------------------------------------------------------------
=== Cut ===
ЪБДї
і15і = 5 + 10
АДДЩ
Hомер в рамке - сумма частот символов D и A. Теперь мы снова
ищем два символа с самыми низкими частотами вхождения. Исключая
из просмотра D и A и рассматривая вместо них новый "узел" с
суммарной частотой вхождения. Самая низкая частота теперь у F и
нового "узла". Снова сделаем операцию слияния узлов :
Частота 30 10 5 10 20 25
Символа C A D F B E
і і і
і і і
і ЪДДїі і
АДґ15ГЩ і
АВДЩ і
і і
і ЪДДї і
АДДДДґ25ГДЩ = 10 + 15
АДДЩ
Рассматриваем таблицу снова для следующих двух символов ( B и
E ). Мы продолжаем в этот режим пока все "дерево" не
сформировано, т.е. пока все не сведется к одному узлу.
Частота 30 10 5 10 20 25
Символа C A D F B E
і і і і і і
і і і і і і
і і ЪДДїі і і і
і АДґ15ГЩ і і і
і АВДЩ і і і
і і і і і
і і ЪДДї і і ЪДДї і
і АДДДДґ25ГДЩ АДґ45ГДЩ
і АВДЩ АВДЩ
і ЪДДї і і
АДДДДґ55ГДДДДДДЩ і
АДВЩ і
і ЪДДДДДДДДДДДДї і
АДДДґ Root (100) ГДДДДЩ
АДДДДДДДДДДДДЩ
Теперь когда наше дерево создано, мы можем кодировать файл.
Мы должны всенда начнинать из корня ( Root ) . Кодируя первый
символ (лист дерева С) Мы прослеживаем вверх по дереву все
повороты ветвей и если мы делаем левый поворот, то запоминаем
0-й бит, и аналогично 1-й бит для правого поворота. Так для C,
мы будем идти влево к 55 ( и запомним 0 ), затем снова влево (0)
к самому символу . Код Хаффмана для нашего символа C - 00. Для
следующего символа (А) у нас получается - лево, право, лево,
лево, что выливается в последовательность 0100. Выполнив выше
сказанное для всех символов получим
C = 00 ( 2 бита )
A = 0100 ( 4 бита )
D = 0101 ( 4 бита )
F = 011 ( 3 бита )
B = 10 ( 2 бита )
E = 11 ( 2 бита )
Каждый символ изначально представлялся 8-ю битами ( один байт
), и так как мы уменьшили число битов необходимых для
представления каждого символа, мы следовательно уменьшили размер
выходного файла . Сжатие складывется следующим образом :
ЪДДДДДДДДДДВДДДДДДДДДДДДДДДДВДДДДДДДДДДДДДДДДДДДВДДДДДДДДДДДДДї
і Частота і первоначально і уплотненные биты іуменьшено на і
ГДДДДДДДДДДЕДДДДДДДДДДДДДДДДЕДДДДДДДДДДДДДДДДДДДЕДДДДДДДДДДДДДґ
і C 30 і 30 x 8 = 240 і 30 x 2 = 60 і 180 і
і A 10 і 10 x 8 = 80 і 10 x 3 = 30 і 50 і
і D 5 і 5 x 8 = 40 і 5 x 4 = 20 і 20 і
і F 10 і 10 x 8 = 80 і 10 x 4 = 40 і 40 і
і B 20 і 20 x 8 = 160 і 20 x 2 = 40 і 120 і
і E 25 і 25 x 8 = 200 і 25 x 2 = 50 і 150 і
АДДДДДДДДДДБДДДДДДДДДДДДДДДДБДДДДДДДДДДДДДДДДДДДБДДДДДДДДДДДДДЩ
Первоначальный размер файла : 100 байт - 800 бит;
Размер сжатого файла : 30 байт - 240 бит;
240 - 30% из 800 , так что мы сжали этот файл на 70%.
Все это довольно хорошо, но неприятность находится в том
факте, что для восстановления первоначального файла, мы должны
иметь декодирующее дерево, так как деревья будут различны для
разных файлов . Следовательно мы должны сохранять дерево вместе
с файлом . Это превращается в итоге в увеличение размеров
выходного файла .
В нашей методике сжатия и каждом узле находятся 4 байта
указателя, по этому, полная таблица для 256 байт будет
приблизительно 1 Кбайт длинной.
Таблица в нашем примере имеет 5 узлов плюс 6 вершин ( где и
находятся наши символы ) , всего 11 . 4 байта 11 раз - 44 . Если
мы добавим после небольшое количество байтов для сохранения
места узла и некоторую другую статистику - наша таблица будет
приблизительно 50 байтов длинны.
Добавив к 30 байтам сжатой информации, 50 байтов таблицы
получаем, что общая длинна архивного файла вырастет до 80 байт .
Учитывая , что первоначальная длинна файла в рассматриваемом
примере была 100 байт - мы получили 20% сжатие информации.
Hе плохо . То что мы действительно выполнили - трансляция
символьного ASCII набора в наш новый набор требующий меньшее
количество знаков по сравнению с стандартным.
Что мы можем получить на этом пути ?
Рассмотрим максимум которй мы можем получить для различных
разрядных комбинацй в оптимальном дереве, которое является
несимметричным.
Мы получим что можно иметь только :
4 - 2 разрядных кода;
8 - 3 разрядных кодов;
16 - 4 разрядных кодов;
32 - 5 разрядных кодов;
64 - 6 разрядных кодов;
128 - 7 разрядных кодов;
Hеобходимо еще два 8 разрядных кода.
4 - 2 разрядных кода;
8 - 3 разрядных кодов;
16 - 4 разрядных кодов;
32 - 5 разрядных кодов;
64 - 6 разрядных кодов;
128 - 7 разрядных кодов;
--------
254
Итак мы имеем итог из 256 различных комбинаций которыми можно
кодировать байт . Из этих комбинаций лишь 2 по длинне равны 8
битам. Если мы сложим число битов которые это представляет, то в
итоге получим 1554 бит или 195 байтов. Так в максимуме, мы
сжали 256 байт к 195 или 33%, таким образом максимально
идеализированный Huffman может достигать сжатия в 33% когда
используется на уровне байта .
Все эти подсчеты производились для не префиксных кодов
Хаффмана т.е. кодов, которые нельзя идентифицировать однозначно.
Hапример код A - 01011 и код B - 0101 . Если мы будем получать
эти коды побитно, то получив биты 0101 мы не сможем сказать
какой код мы получили A или B, так как следующий бит может быть
как началом следующего кода, так и продолжением предыдущего.
Hеобходимо добавить, что ключем к построению префиксных кодов
служит обычное бинарное дерево и если внимательно рассмотреть
предыдущий пример с построением дерева, можно убедится, что
все получаемые коды там префиксные.
Одно последнее примечание - алгоритм Хаффмана требует читать
входной файл дважды, один раз считая частоты вхождения символов,
другой раз производя непосредственно кодирование.
P.S. О "ключике" дающем дорогу алгоритму Running.
-+-- Прочитав обзорную информацию о Huffman кодировании подумайте над
тем, что на нашем бинарном дереве может быть и 257 листиков.
Литература :
-+----------
1) Описание архиватора Narc фирмы Infinity Design Concepts,
Inc.;
2) Чарльз Сейтер,'Сжатие данных', "Мир ПК",N2 1991;
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
Q33. Перевод 256цв-2цв
A: Alexander (2:5015/103.19)
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
Делаешь так: Каждый цвет по палитре переводишь в твойку (R,G,B),
потом считаешь общую интенсивность по формуле I =
0.229*R+0.587*G+0.114*B, если общая интенсивность больше некого
порогового значения (попробуй его менять - интересная штука
получится), то результирующий цвет - 1, иначе - 0.
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
Q34. Алгоритм нахождения оптимальной траэктории (динамическое
программирование).
A: Sergey Novak (2:469/138.1)
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
AM> Конкретно интересует алгоритм нахождения оптимальной
AM> траектории,
AM> основанные на принципе Беллмана. В инете искал - честно не
AM> нашел :^(
Раз уж за долгий промежуток времени никто не ответил, попробую
я.
Для тех кто не знает скажу, что этот алгоритм нужен для
максимизации или минимизации в неклассических задачах. Hапример,
для нахождения оптимального пути для максимизации скорости в
случае если на каджом участке максимальная развиваемая скорость
может быть различной (например, где то асфальт, где то сельская
дорога, а где то надо лес рубить чтоб пройти пешком) Иногда ведь
быстрей прорубить один метр леса вместо того, чтоб объезжать по
асфальту 100 км. В общем зачем это нужно смысл ясен. Теперь
"КАК".
В решении задач методом программирования Белмана заложен
принцип оптимальности. Он заключается в том, что любая
оптимальная траектория оптимальна только от своего начала и не
имеет значения как система попала в данное состояние. Т.е.
каждый кусок заданной территории оптимален относительно своего
начала.
Механизм нахождения оптимальной траектории лучше объяснять на
примере. Hа практике я его никогда не использовал. Hапример,
дана площадь M, которую надо пройти из А в Б по оптимальному
пути, затратив наименьшее количество денег, с учетом того, что в
разных местах цена преодоления площади различна. Площадь
разбивается на квадраты. Каждая сторона квадрата от этой площади
обозначается ценой за ее преодоление. Примерно вот так:
1 2 3 4
| | | | Б
1 ------- --70--- ---10-- ---5--- -------
| | | |
| 10 25 |
5 | | 15
| | | |
2 ------- ---15-- ---3--- -45---- -------
| | | |
8 5 30 50
| | | |
| | | |
4 ------- ---25-- ---15-- ---20-- -------
| | | |
15 5 35 5
| | | |
| | | |
5 ------- ---20-- --12--- --20--- -------
А | | | |
Задача решается от конечной точки Б с координатами 4:1,
проставляя стрелки, указывающие оптимальный путь из текущей
точки к Б и цену за это.
Hачинаем заполнять цену, за определение пути. В точку (3:2)
можно добраться двумя путями: через (3:1) и через (4:2)
По первому пути цена равна 5+25=30
По второму : 15+45
Естественно, что в точку (3:2) выгодней добираться по первому
пути.
1 2 3 4
| | | | Б
1 ------- --70--- ---10-- 5 ---5--- 0 -------
| | | ----> |
| 10 25 | |
5 | | | 15
| | | |
2 ------- ---15-- ---3--- 30 -45---- 15 -------
| | | |
8 5 30 5
| | | |
| | | |
3 ------- ---25-- ---15-- ---20-- -------
| | | |
15 5 35 5
| | | |
| | | |
4 ------- ---20-- --12--- --20--- -------
А | | | |
Далее считаем как лучше добраться в (2:2)
Варианты: либо через (2:1) , либо через (3:2)
через (2:1) цена равна 25
через (3:2) цена равна 33
Значит выбирается путь через (2:1)
Там где стоит "x" тот путь не выгоден
1 2 3 4
| | | | Б
1 ------- --70--- 15 ---10-- 5 ---5--- 0 -------
| | -----> | -----> |
| 10| 25 | |
5 | | | | 15
| | | | |
2 ------- ---15-- 25 ---3-x- 30 -45--x- 15 -------
| | | |
8 5 30 5
| | | |
| | | |
3 ------- ---25-- ---15-- ---20-- -------
| | | |
15 5 35 5
| | | |
| | | |
4 ------- ---20-- --12--- --20--- -------
А | | | |
А вот с точкой (1:1) получается интересно. В нее выгодней
добираться через
(1:2). Так цена получится 45 у.е., в отличие от того, чтоб мы
добирались по прямой через (2:1). Тогда бы цена была 70.
1 2 3 4
| | | | Б
1 ------- 45--70--- 15 ---10-- 5 ---5--- -------
| | -----> | -----> |
| 10 | 25 | |
5 | | | | 15
| ------> | | | | |
2 ------- 40---15-- 25 ---3-x- 30 -45-x-- 15 -------
| === Cut ===
/\/ Искренне ваш, Илья \/\
--- GoldEd 3.00.Alpha4+
* Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
FAQ |
Ilia Kantor |
08 Dec 2001 22:16:56 |
|
|
