Какие языки программирования наиболее всего подходят для создания игр?
3 ответа:
Читайте также
Необходимо составить дерево, так, чтобы каждый узел с символом был окончанием ветки,
обычно такой узел называют листом, а количество повторений символа является весом этого узла.
Алгоритм построения дерева Хаффмана состоит в том, что на каждом шаге пары узлов с минимальнм весом соединяются
в общий узел, с весом равным сумме этих узлов, до тех пор пока не останется один узел, с весом равным длине сообщения.
При этом узлу с меньшим весом ставится в соответствие ребро с кодом 0,
а узлу с большим весом ставится в соответствие ребро с кодом 1.
Все коды рёбер по пути от корня до листа составляют код символа.
Построим двоичное дерево Хаффмана для фразы НА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА
по частоте появления символов (по количеству повторений символа)
Считаем сколько раз в сообщении встречается каждый символ:
Символ "Н" встречается 2 раза
Символ "А" встречается 6 раз
Символ " " встречается 5 раз
Символ "Д" встречается 2 раза
Символ "В" встречается 4 раза
Символ "О" встречается 2 раза
Символ "Р" встречается 4 раза
Символ "," встречается 1 раз
Символ "Е" встречается 2 раза
Расположим узлы, для построения дерева Хаффмана в порядке возрастания веса:
- {","(1)}
- {"Н"(2)}
- {"Д"(2)}
- {"О"(2)}
- {"Е"(2)}
- {"Т"(2)}
- {"В"(4)}
- {"Р"(4)}
- {" "(5)}
- {"А"(6)}
Объединим узлы {","(1)} и {"Н"(2)} в узел 1 с весом 3 и запишем в порядке возрастания веса
Шаг 1
- {"Д"(2)}
- {"О"(2)}
- {"Е"(2)}
- {"Т"(2)}
- {"1 (3)":[{","(1)},{"Н"(<wbr />2)}]}
- {"В"(4)}
- {"Р"(4)}
- {" "(5)}
- {"А"(6)}
Шаг 2
- {"Е"(2)}
- {"Т"(2)}
- {"1 (3)":[{","(1)},{"Н"(<wbr />2)}]}
- {{"2 (4)"[{"Д"(2)},{"О"(2<wbr />)}]}
- "В"(4)}
- {"Р"(4)}
- {" "(5)}
- {"А"(6)}
Шаг 3
- {"1 (3)":[{","(1)},{"Н"(<wbr />2)}]}
- {"3 (4)":[{"Е"(2)},{"Т"(<wbr />2)}]}
- {"2 (4)":[{"Д"(2)},{"О"(<wbr />2)}]}
- {"В"(4)}
- {"Р"(4)}
- {" "(5)}
- {"А"(6)}
Шаг 4
- {"2 (4)":[{"Д"(2)},{"О"(<wbr />2)}]}
- {"В"(4)}
- {"Р"(4)}
- {" "(5)}
- {"А"(6)}
- {"4 (7)":[{"1 (3)":[{","(1)},{"Н"(<wbr />2)}]},{"3 (4)":[{"Е"(2)},{"Т"(<wbr />2)}]}]}
Шаг 5
- {"А"(6)}
- {"4 (7)":[{"1 (3)":[{","(1)},{"Н"(<wbr />2)}]},{"3 (4)":[{"Е"(2)},{"Т"(<wbr />2)}]}]}
- {"5 (8)":[{"2 (4)":[{"Д"(2)},{"О"(<wbr />2)}]},{"В"(4)}]}
- {"6 (9)":[{"Р"(4)},{" "(5)}]}
Шаг 6
- {"А"(6)}
- {"4 (7)":[{"1 (3)":[{","(1)},{"Н"(<wbr />2)}]},{"3 (4)":[{"Е"(2)},{"Т"(<wbr />2)}]}]}
- {"5 (8)":[{"2 (4)":[{"Д"(2)},{"О"(<wbr />2)}]},{"В"(4)}]}
- {"6 (9)":[{"Р"(4)},{" "(5)}]}
Шаг 7
- {"5 (8)":[{"2 (4)":[{"Д"(2)},{"О"(<wbr />2)}]},{"В"(4)}]}
- {"6 (9)":[{"Р"(4)},{" "(5)}]}
- {"7 (13)":[{"А"(6)},{"4 (7)":[{"1 (3)":[{","(1)},{"Н"(<wbr />2)}]},{"3 (4)":[{"Е"(2)},{"Т"(<wbr />2)}]}]}]}
Шаг 8
- {"7 (13)":[{"А"(6)},{"4 (7)":[{"1 (3)":[{","(1)},{"Н"(<wbr />2)}]},{"3 (4)":[{"Е"(2)},{"Т"(<wbr />2)}]}]}]}
- {"8 (17)":[{"5 (8)":[{"2 (4)":[{"Д"(2)},{"О"(<wbr />2)}]},{"В"(4)}]},{"6 (9)":[{"Р"(4)},{" "(5)}]}]}
После шага 9 получается полное кодовое дерево Хаффмана:
Код каждого символа определяется кодами ребер на пути от корня к листьям:
Символ "А" код равен 00
Символ " " код равен 111
Символ "Р" код равен 110
Символ "В" код равен 101
Символ "Т" код равен 0111
Символ "Е" код равен 0110
Символ "О" код равен 1001
Символ "Д" код равен 1000
Символ "Н" код равен 0101
Символ "," код равен 0100
Ни один символ не является началом другого символа, т.е. выполняется условие Фано.
Длина кодированного сообщения равна сумме произведений количества повторений каждого символа на длину его кода:
2*4+6*2+5*3+2*4+4*3+<wbr />2*4+4*3+2*4+1*4+2*4=9<wbr />5 бит
Кодированноое сообщение выглядит так:
01010011110001011001<wbr />110011001001110111110<wbr />001010011101010011101<wbr />111100010101101111000<wbr />11100110100
Длина исходного сообщения 30 байт или 240 бит в ASCII или 480 бит в Юникоде:
сообщение содержит 10 различных символов.
Длина кода одного символа при равномерном кодировании равна log₂(10)=4 бит
при равномерном кодировании длина текста равна 30*4=120 бит
Коэффициэнт сжатия по отношению к восьмибитному коду равен 240/95 =~2.526
Коэффициэнт сжатия по отношению к равномерному коду равен 120/95 =~1.263