3622
правки
Изменения
м
→Сведение задачи о генерации оптимального префиксного кода с длиной кодового слова не более L бит к задаче о рюкзаке
Важно заметить следующий факт: в худшем случае все кодовые слова будут иметь длину <tex>L</tex> бит. Тогда мы можем закодировать <tex> 2^L </tex> символов. Таким образом, нельзя получить описанный выше код, если <tex> n > 2^L </tex>.
== Сведение задачи о генерации оптимального префиксного кода с длиной кодового слова не более L бит к задаче о рюкзаке ==
Пусть <tex>L</tex> — ограничение на длину кодового слова, а <tex>P=\{p_{1},p_{2},\dots,p_{n}\}</tex> — частоты символов алфавита. Алгоритм генерации кода будет следующим:
Таким образом, мы набрали необходимую сумму, используя все предметы. Но так как мы рассматривали граничный случай, при бОльших значениях <tex>L</tex> данную сумму гарантированно можно набрать.
Оптимальность же кода следует из оптимальности решения задачи о рюкзаке. Действительно, частота символа {{- --}} это вес предеметовпредметов, соответствующих ему. Значит, чем чаще символ встречается в тексте, тем реже он будет попадать в наш рюкзак (будет выгоднее брать предметы аналогичной ценности, но меньшего веса, соответствующие более редким символам), а значит, его код будет короче. Таким образом, код, сгенерированный данным алгоритмом, будет оптимальным среди кодов с длиной кодового слова не более <tex>L</tex>.
== Восстановление ответа. ==
