Какое будет кратчайшее возможное кодовое слово для буквы й , чтобы кодирование было однозначно декодируемым

Морской_Шторм

69

Кодирование Фано – это метод кодирования, при котором наиболее часто используемым символам присваиваются более короткие кодовые слова, а реже используемым символам – более длинные кодовые слова. Задача состоит в том, чтобы найти кратчайшее возможное кодовое слово для буквы "й" при использовании неравномерного двоичного кода Фано.

Для начала нам понадобится частотная таблица символов, включающая букву "й" и их частоты использования. Предположим, что у нас есть следующая таблица:

| Символ | Частота |
|--------|---------|
| "а" | 10 |
| "б" | 5 |
| "в" | 8 |
| "г" | 4 |
| "д" | 3 |
| "е" | 12 |
| "ж" | 2 |
| "з" | 6 |
| "и" | 15 |
| "й" | ? |
| ... | ... |

Заметим, что буква "й" не указана в таблице. Но нам также известно, что общая частота использования всех символов равна 100.


Сначала мы сортируем таблицу в порядке убывания частоты использования символов:

| Символ | Частота |
|--------|---------|
| "и" | 15 |
| "е" | 12 |
| "а" | 10 |
| "в" | 8 |
| "з" | 6 |
| "б" | 5 |
| "г" | 4 |
| "д" | 3 |
| "ж" | 2 |
| "й" | ? |
| ... | ... |

Далее мы создаем дерево, начиная с двух самых часто встречающихся символов. Мы объединяем их в один узел и записываем сумму их частот в этот узел. То есть, в данном случае, мы объединяем "и" и "е":

\[
\begin{align*}
&\phantom{=} \cfrac{}{27} \\
&\phantom{=} / \phantom{=} \\
&\phantom{=}\cfrac{}{} \\
&\phantom{=} / \phantom{=} \\
&\cfrac{ие}{27} \\
&\phantom{=}\phantom{=} / \phantom{=} \\
&\phantom{=}\phantom{=}\pect{и}{15} \\
&\phantom{=}\phantom{=}\phantom{=} \phantom{=} / \phantom{=} \\
&\phantom{=}\phantom{=}\pect{е}{12} \\
\end{align*}
\]

Теперь мы выполняем те же самые шаги для следующих двух наиболее часто встречающихся символов, то есть объединяем "а" и "в":

\[
\begin{align*}
&\phantom{=} \cfrac{}{37} \\
&\phantom{=} / \phantom{=} \\
&\phantom{=}\cfrac{}{} \\
&\phantom{=} / \phantom{=} \\
&\cfrac{\phantom{ие}}{37} \\
&\phantom{=}\phantom{=} / \phantom{=} \\
&\cfrac{ие}{27} \quad \pect{a}{10} \\
&\phantom{=} / \phantom{=} \\
&\phantom{=}\pect{в}{8} \\
\end{align*}
\]

Продолжаем этот процесс, пока не достигнем 100. На каждом шаге мы объединяем два узла и записываем сумму их частот в этот узел. В конечном итоге мы получим следующее дерево:

\[
\begin{align*}
&\phantom{=} \cfrac{}{100} \\
&\phantom{=} / \phantom{=} \\
&\phantom{=}\cfrac{}{} \\
&\phantom{=} / \phantom{=} \\
&\cfrac{\phantom{=}\phantom{=}\phantom{=}\phantom{=}\phantom{=} \phantom{=}\phantom{=}\phantom{=}\phantom{=}\phantom{=}}{100} \\
&\phantom{=}\phantom{=} / \phantom{=} \\
&\cfrac{\phantom{=}\phantom{=}\phantom{=}\phantom{=}\phantom{=}\phantom{=}\phantom{=}\phantom{=}\phantom{=}}{73} \quad \cfrac{\phantom{=}\phantom{=}\phantom{=}\phantom{=}\phantom{=}}{27} \\
&\phantom{=}\phantom{=} / \phantom{=} \phantom{=} / \phantom{=} \\
&\cfrac{\phantom{=}\phantom{=}\phantom{=}\phantom{=}\phantom{=}\phantom{=}\phantom{=}\phantom{=}\phantom{=}}{27} \quad \cfrac{\phantom{=}\phantom{=} \phantom{=}\phantom{=}}{46} \\
&\phantom{=}\phantom{=} / \phantom{=} \phantom{=} / \phantom{=} \\
&\cfrac{\phantom{=}\phantom{=}\phantom{=}\phantom{=}\phantom{=}\phantom{=} \phantom{=}\phantom{=} \phantom{=}\phantom{=}}{15} \quad \cfrac{\phantom{=}\phantom{=}\phantom{=} \phantom{=}\phantom{=}\phantom{=}\phantom{=}}{12} \\
\end{align*}
\]

Теперь можем назначить кодовые слова для каждого символа. При кодировании Фано мы добавляем "1" для каждого перехода влево и "0" для каждого перехода вправо. Таким образом, получим следующую таблицу кодов для наших символов:

| Символ | Частота | Код |
|--------|---------|-----|
| "и" | 15 | 0 |
| "е" | 12 | 10 |
| "а" | 10 | 110|
| "в" | 8 | 111|
| "з" | 6 | 1100|
| "б" | 5 | 1101|
| "г" | 4 | 1110|
| "д" | 3 | 1111|
| "ж" | 2 | 11000|
| "й" | ? | 11001|

Таким образом, кратчайшее возможное кодовое слово для буквы "й" при использовании неравномерного двоичного кода Фано составляет "11001".