21-я лекция Кнута «Не елка»

Ежегодная лекция Дональда Кнута в этом году — хранительница. Это по теме, которая будет понятна, даже если вы мало о ней знаете — коды без запятой.

Дональд Кнут должен быть вам известен, но на всякий случай — он изобрел компьютерную систему набора текста TeX, является автором монументального труда «Искусство компьютерного программирования» и многих алгоритмов. У него также странное чувство юмора, так что будьте осторожны, когда смотрите видео.

Традиция лекции о рождественской елке, которую читают в Стэнфордском университете в декабре, связана с чем-то новым, что узнали о деревьях в течение года. Впервые, в 21-м выпуске серии, речь идет не о деревьях, а о кодах без запятой:

«Код без запятых — это набор кодовых слов, которые можно легко прочитать без пробелов или других разделителей между словами.

В 1965 году Уиллард Истман открыл красивый, но недооцененный способ построения блочных кодов без запятой любой нечетной длины по бесконечному алфавиту. Профессор Кнут объяснит свою конструкцию и ее интересную связь с вопросами итерации по сравнению с рекурсией ».

Звучит просто или очевидно, но несколько попыток создать такую вещь убедят вас в том, что это сложно. Более современный термин — самосинхронизирующийся код. По сути, идея состоит в том, что вам не нужно отправлять маркеры в коде для разделения кодовых слов, потому что их можно разделить без таких маркеров. То есть, если вы возьмете набор слов и объедините их без пробелов и знаков препинания, тогда появится возможность снова разделить их, если они образуют код без запятых. Ключевая идея заключается в том, что невозможно найти одно из слов в результате сложения двух слов вместе или внутри другого слова.

Например, медведь, кольцо, серьга, ухо — это код без запятой. Собираем все слова вместе

медведь

очень ясно дает понять, что вы не можете однозначно разделить их.

Например

медведь

выбирает кодовое слово, которое не следует выбирать.

Вы также можете добавить условие, что все кодовые слова имеют одинаковую длину. Двоичный пример этого — двухбитовый код 00,11. В любой последовательности этих кодовых слов вы никогда не получите ложное кодовое слово из-за конкатенации 00 или 11, например. 00111100000011 можно разбить на кодовые слова только одним способом, независимо от того, с чего вы начинаете.

Если вас интересует эта тема, то хорошей новостью является то, что есть PDF-файл следующего фрагмента книги «Искусство компьютерного программирования при поиске с возвратом» перед публикацией, в котором рассматриваются алгоритмы, применимые к кодам без запятых:

Искусство программирования: Том 4, вводная часть 5B: Введение в поиск с возвратами