|
Из учебника по теорверу я так понял алгоритм кодирования (будем для простоты говорить о побуквенном кодировании).
- берём весь алфавит и сортируем по вероятностям встречания букв
- где-то не посередине алфавит разбиваем на две группы так, чтобы суммарные вероятности букв до и после раздела примерно совпадали (и были близки к 1/2)
- договариваемся, что первый бит кода указывает, в какой из этих двух групп находится буква
- далее, каждую группу разбиваем на подгруппы по тому же принципу и договариваемся, что каждый очередной бит выбирает из двух очередных подгрупп одну из двух равновероятных
- по теории информации доказывается, что таким образом, информация, приходящаяся на каждый бит максимальна, а сам код -- оптимален
- параллельно показывается, что для редких букв код оказывается длиннее, а для частых короче -- что является наглядным доказательством оптимальности
Вопросы.
1. Не это ли самое называется кодом Хафмана? Не тоже ли это самое?
2. Изменим алгоритм.
Будем сортировать буквы, но записывать их в две колонки, например
ое
аи
тн
ср
и так далее.
При разбивке будем получать группы путём разбиения получающейся таблицы по вертикали, на два столбца.
Ясно, что вероятности этих групп тоже будут примерно одинаковыми (не теряя сути рассуждений предположим, что вероятности соседних букв отличаются слабо). То есть, по теории информации, каждый бит снова будет выбирать между двумя равновероятными группами. И тоже, стало быть, должен оказаться оптимальным. Однако, поскольку теперь в каждой группе примерно по одинаковому числу букв, то коды всех букв будут иметь примерно одинаковую длину и уже нельзя будет объяснить, что код оптимален потому, что короче для более частых букв.
Где я ошибся?
|
29.09.2006, 16:12 
