🌟 Чтобы максимально эффективно кодировать текстовые сообщения, удобнее всего составлять кодовых слов, удовлетворяющих условию Фано.
Дерево вариантов — структура, принцип работы которой состоит в том, что в её узлах будут находиться кодовые слова, а из узла могут выходить два ребра, соответствующие добавлению в конец кодового слова 0 и 1.
💅 Правила построения дерева Фано
- Дерево начинается с двух направлений, обозначающих ноль и единицу
- От каждого направления можно рисовать только два направления (также ноль и единицу).
- Если ветка занята символом, то дальше строить дерево по этой веке нельзя, иначе правило Фано будет нарушено.
- Значение считывается сверху вниз: начинать надо с «корня» и двигаться по «веткам».
- Чем чаще встречается какой-либо символ, тем короче нужно выбрать для него двоичный код.
- Если не получается однозначно закодировать символы, на помощь придут дополнительные условия.
В большинстве случаев в условиях встречается формулировка «укажите наименьшее по длине кодовое слово» — поэтому чем короче кодовое слово для символов, встречающихся чаще других, тем лучше! Так искомая длина последовательности получится меньше всего.
Авторизуйтесь, чтобы оставить комментарий.