Дерево Морзе: код зі змінною довжиною за сто років до Хаффмана
Абетку Морзе зазвичай показують таблицею: літера, навпроти неї крапки й тире. У такому вигляді вона виглядає як довільний список, який лишається тільки визубрити.
Насправді це двійкове дерево, і в ньому видно інженерне рішення, ухвалене в 1840-х: частота літери задає її глибину. E — одна крапка, T — одне тире, бо це найчастіші літери англійського тексту. Q, J, Z сидять аж на четвертому рівні. Альфред Вейл дійшов до цього не теорією, а підрахунком: він рахував літери в шухлядах друкарського набору місцевої газети.
Код зі змінною довжиною, розподілений за частотою символів. За сто з гаком років до того, як Шеннон і Хаффман пояснили, чому це працює.
Дерево
Ліворуч — крапка, праворуч — тире. Чотири рівні літер заповнені повністю — вільних вузлів там немає. Цифри довші за будь-яку літеру, тож лежать рівнем нижче.
Дерево Морзе
Доріжка ліворуч — крапка, праворуч — тире; біля кожної стоїть шовкографічна позначка: · одна одиниця часу, ▬ три. Діаметр площадки — частота літери в англійському тексті. Натисніть будь-яку літеру, щоб почути її окремо. Порожні площадки — вузли, яких англійська абетка не займає. Нижній ряд — цифри: вони довші за будь-яку літеру й тому лежать рівнем глибше.
Скільки це триває
та сама передача в часі: 117 одиниць, 9,4 с на 15 WPM. Видно те, чого дерево не показує, — тире коштує втричі більше за крапку, і саме тому «оптимальність» тут вимірюється часом, а не кількістю знаків.
прочитано: —
Дві речі, які видно одразу й не видно в таблиці.
Часті літери сидять близько до кореня. Не приблизно, а систематично: діаметр площадки тут — частота літери, і найбільші зібралися вгорі.
Тире коштує втричі більше за крапку. Тому глибина вузла й ціна літери — різні речі:
O (---) стоїть на третьому рівні, як і S (...), але звучить більш ніж удвічі
довше — одинадцять одиниць часу проти п’яти. Часова діаграма під деревом показує це прямо.
Наскільки точно Вейл поцілив
Частота літери й ціна її коду
стовпці — частота в англійському тексті, %; лінія — тривалість коду в одиницях часу (права вісь). Чим частіша літера, тим дешевший код — і тим помітніші винятки
Кореляція між частотою літери й тривалістю її коду — рангова, за Спірменом — виходить сильна й від’ємна. Для роботи, зробленої перелічуванням літер у друкарських шухлядах, це майже неприлично добре.
Винятки на графіку помітні неозброєним оком. Найгучніший — O: четверта за частотою літера англійської має найдовший можливий код третього рівня.
Чому це все-таки не код Хаффмана
Тут починається цікаве, бо аналогія «Морзе — це Хаффман» приємна й неправильна одразу з двох причин.
Морзе не є префіксним кодом. E це ., а I це .. — код однієї літери є початком коду
іншої. У префіксному коді таке заборонено, і саме заборона дозволяє декодувати потік без
розділювачів. Хаффман завжди дає код, у якому символи стоять тільки в листках дерева; у
Морзе символ сидить у кожному вузлі, включно з внутрішніми.
Тому телеграф і не можна передавати суцільним потоком: між літерами обов’язкова пауза завдовжки три одиниці. Тобто алфавіт насправді не двійковий, а трійковий — крапка, тире й пауза, — і саме пауза несе те, що в Хаффмана несе форма дерева.
І оптимальність тут вимірюється не тим. Хаффман мінімізує кількість символів, виходячи з того, що всі символи коштують однаково. У телеграфі тире коштує втричі більше за крапку, тож мінімізувати треба час, а не кількість знаків. Це інша задача — кодування з нерівною вартістю символів, і розв’язали її аж у 1961-му (Карп, через ціле лінійне програмування), а зручні наближення — ще пізніше.
Коротко: Морзе не Хаффман і не мав ним бути. Але питання «а наскільки близько?» лишається законним, і на нього можна відповісти точно.
Скільки коштує помилка роздачі
Порівнювати будемо чесно: беремо ті самі двадцять шість кодів і роздаємо їх літерам найкращим можливим чином — найдешевший код найчастішій літері й так далі. Що це справді оптимум, випливає з нерівності про перестановки: жодна інша роздача меншого середнього часу не дасть.
Середній час літери, одиниць
однакові коди, різна роздача
| Літера | Код | Коштує | Мала б | Втрата |
|---|---|---|---|---|
| O | --- | 11 | 5 | 0,45 |
| A | .- | 5 | 3 | 0,16 |
| L | .-.. | 9 | 7 | 0,08 |
| Y | -.-- | 13 | 9 | 0,08 |
| C | -.-. | 11 | 9 | 0,06 |
Сім відсотків. Тобто розподіл, зроблений у 1840-х на око й на слух, програє точному оптимуму для того самого набору кодів менш ніж на десятину.
У таблиці видно, де саме втрачається час, і O очолює її з великим відривом: одинадцять одиниць там, де мало би бути п’ять.
Але звинувачувати в цьому Вейла не можна. Код, який ми щойно розібрали, — не його. Американська абетка Морзе мала інші коди для доброго десятка літер і використовувала паузи всередині символів (O там передавалася двома крапками з широким проміжком). У 1848-му Фрідріх Ґерке переробив її для гамбурзької телеграфної лінії — прибрав внутрішні паузи й вирівняв довжини. У 1851-му цю редакцію прийняв Німецько-австрійський телеграфний союз, і з неї виросла міжнародна абетка.
Тобто частотну оптимізацію робив Вейл, а конкретну роздачу, яку ми міряємо, — Ґерке, і його метою була регулярність, а не найкоротший час. Сім відсотків — це ціна цієї регулярності.
І практичний висновок, зворотний до очікуваного
Дерево пояснює, чому абетка саме така. Але вчити за ним телеграф не можна.
Той, хто веде пальцем по дереву, поки в навушниках іде передача, ставить рахунок на місце слуху: почув → порахував → згадав. Цей проміжний крок упирається в стелю близько десяти слів за хвилину, і розібрати його потім важче, ніж вивчити з нуля правильно. Робочий метод — Коха з Фарнсвортом: символи одразу на швидкості 20–25 WPM, розтягнуті тільки паузи, жодної таблиці перед очима.
Дерево — гарна відповідь на питання «як це влаштовано» і погана на питання «як цього навчитися». Це різні питання, і плутати їх коштує півроку.
Відкрите питання, яке лишаю на потім: усе пораховане вище — для англійських частот. Скільки коштує українському операторові код, оптимізований під чужу мову, і як виглядає та сама таблиця для кириличної абетки Морзе — тема окремого разу, і починати її треба зі звірки кириличної таблиці з першоджерелом, а не з пам’яті.