Алгоритм Сардин-Паттерсона - Sardinas–Patterson algorithm

В теория кодирования, то Алгоритм Сардин-Паттерсона классический алгоритм определения в полиномиальное время ли данный код переменной длины уникально декодируемый, названный в честь Августа Альберта Сардинаса и Джорджа Паттерсона, опубликовавших его в 1953 году.^[1] Алгоритм выполняет систематический поиск строки, допускающей два разных разложения на кодовые слова. В качестве Knuth сообщает, что алгоритм был переоткрыт примерно десятью годами позже, в 1963 г. Флойд, несмотря на то, что в то время это было уже хорошо известно в теории кодирования.^[2]

Идея алгоритма

Рассмотрим код ${displaystyle {,amapsto 1,bmapsto 011,cmapsto 01110,dmapsto 1110,emapsto 10011,}}$. Этот код, основанный на примере Berstel,^[3] является примером кода, который нельзя однозначно декодировать, поскольку строка

011101110011

можно интерпретировать как последовательность кодовых слов

01110 – 1110 – 011,

но также как последовательность кодовых слов

011 – 1 – 011 – 10011.

Таким образом, два возможных декодирования этой закодированной строки даются следующим образом: cdb и младенец.

В общем, кодовое слово может быть найдено по следующей идее: в первом раунде мы выбираем два кодовых слова ${displaystyle x_{1}}$ и ${displaystyle y_{1}}$ такой, что ${displaystyle x_{1}}$ это префикс из ${displaystyle y_{1}}$, то есть,${displaystyle x_{1}w=y_{1}}$ для какого-то "висячего суффикса" ${displaystyle w}$. Если кто-то попробует сначала ${displaystyle x_{1}=011}$ и ${displaystyle y_{1}=01110}$, свисающие суффикс является ${displaystyle w=10}$. Если нам удастся найти две последовательности ${displaystyle x_{2},ldots ,x_{p}}$ и ${displaystyle y_{2},ldots ,y_{q}}$ кодовых слов таких, что${displaystyle x_{2}cdots x_{p}=wy_{2}cdots y_{q}}$, тогда мы закончили: Ибо тогда строка ${displaystyle x=x_{1}x_{2}cdots x_{p}}$ в качестве альтернативы можно разложить как ${displaystyle y_{1}y_{2}cdots y_{q}}$, и мы нашли искомую строку, имеющую как минимум два различных разложения на кодовые слова.

Во втором раунде мы пробуем два разных подхода: первая попытка - поиск кодового слова, ш как префикс. Тогда мы получаем новый висячий суффикс w ', с которым мы можем продолжить наши поиски. Если в конце концов мы встретим висящий суффикс, который сам по себе является кодовым словом (или пустое слово ), то поиск прекратится, поскольку мы знаем, что существует строка с двумя разбиениями. Вторая попытка заключается в поиске кодового слова, которое само по себе является префиксом ш. В нашем примере у нас есть ${displaystyle w=10}$, а последовательность 1 это кодовое слово. Таким образом, мы также можем продолжить w '= 0 как новый висячий суффикс.

Точное описание алгоритма

Для описания алгоритма удобнее всего использовать частные формальные языки. В общем, для двух наборов струн D и N, (левое) частное ${displaystyle N^{-1}D}$ определяется как остаточные слова, полученные из D удалив префикс в N. Формально, ${displaystyle N^{-1}D={,ymid xyin D~{ extrm {and}}~xin N,}}$. Теперь позвольте ${displaystyle C}$ обозначим (конечный) набор кодовых слов в данном коде.

Алгоритм выполняется циклами, при этом мы поддерживаем в каждом раунде не только один висячий суффикс, как описано выше, но (конечный) набор всех потенциальных висячих суффиксов. Начиная с раунда ${displaystyle i=1}$, множество потенциальных свисающих суффиксов обозначим через ${displaystyle S_{i}}$. Наборы ${displaystyle S_{i}}$ определены индуктивно следующее:

${displaystyle S_{1}=C^{-1}Csetminus {varepsilon }}$. Здесь символ ${displaystyle varepsilon }$ обозначает пустое слово.

${displaystyle S_{i+1}=C^{-1}S_{i}cup S_{i}^{-1}C}$, для всех ${displaystyle igeq 1}$.

Алгоритм вычисляет множества ${displaystyle S_{i}}$ в порядке возрастания ${displaystyle i}$. Как только один из ${displaystyle S_{i}}$ содержит слово из C или пустое слово, то алгоритм завершается и отвечает, что данный код не является однозначно декодируемым. В противном случае после набора ${displaystyle S_{i}}$равно ранее встреченному набору ${displaystyle S_{j}}$ с ${displaystyle j<i}$, то алгоритм в принципе войдет в бесконечный цикл. Вместо того, чтобы продолжать бесконечно, он отвечает, что данный код однозначно декодируется.

Завершение и правильность алгоритма

Поскольку все наборы ${displaystyle S_{i}}$ являются наборами суффиксов конечного набора кодовых слов, существует лишь конечное число различных кандидатов на ${displaystyle S_{i}}$. Поскольку повторное посещение одного из наборов приведет к остановке алгоритма, алгоритм не может продолжаться бесконечно и, следовательно, должен всегда прекратить. Точнее, общее количество висящих суффиксов, которые рассматривает алгоритм, не более чем равно сумме длин кодовых слов на входе, поэтому алгоритм работает в полиномиальное время как функция этой входной длины. Используя суффиксное дерево для ускорения сравнения между каждым висящим суффиксом и кодовыми словами время алгоритма может быть ограничено O (нк), куда п - общая длина кодовых слов и k - количество кодовых слов.^[4] Алгоритм может быть реализован с использованием машины сопоставления с образцом. ^[5] Алгоритм также может быть реализован для работы на недетерминированная машина Тьюринга который использует только логарифмическое пространство; проблема проверки уникальной дешифрируемости NL-полный, поэтому эта оценка пространства оптимальна.^[6]

Доказательство того, что алгоритм правильный, т.е. что он всегда дает правильный ответ, встречается в учебниках Саломаа^[7] и Berstel et al.^[8]

Смотрите также

• Неравенство Крафт в некоторых случаях предоставляет быстрый способ исключить возможность однозначного декодирования данного кода.
• Коды префикса и блочные коды являются важными классами кодов, однозначно декодируемых по определению.
• Хронология теории информации

Примечания

1. Сардины и Паттерсон (1953).
2. Кнут (2003), стр. 2
3. Berstel et al. (2009), Пример 2.3.1 с. 63
4. Родех (1982).
5. Апостолико и Джанкарло (1984). Ошибка sfnp: нет цели: CITEREFApostolico_and_Giancarlo1984 (помощь)
6. Риттер (1986) доказывает, что дополнительная проблема проверки существования строки с двумя декодированиями является NL-полной, и, следовательно, эта уникальная дешифрируемость является co-NL-полной. Эквивалентность NL-полноты и ко-NL-полноты следует из Теорема Иммермана – Селепсеньи.
7. Саломаа (1981)
8. Berstel et al. (2009), Глава 2.3

Рекомендации

• Берстель, Жан; Перрен, Доминик; Ройтенауэр, Кристоф (2010). Коды и автоматы. Энциклопедия математики и ее приложений. 129. Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-88831-8. Zbl  1187.94001.
• Берстель, Жан; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями. Энциклопедия математики и ее приложений. 137. Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-19022-0. Zbl  1250.68007.
• Кнут, Дональд Э. (Декабрь 2003 г.). «Памяти Роберта У. Флойда». Новости SIGACT. 34 (4): 3–13. Дои:10.1145/954092.954488.
• Родех М. (1982). «Быстрый тест на уникальную дешифрируемость на основе деревьев суффиксов (Корр.)». IEEE Transactions по теории информации. 28 (4): 648–651. Дои:10.1109 / TIT.1982.1056535..
• Апостолико, А .; Джанкарло, Р. (1984). «Реализация машины сопоставления шаблонов быстрого теста на уникальную дешифрируемость». Письма об обработке информации. 18 (3): 155–158. Дои:10.1016/0020-0190(84)90020-6..
• Риттер, Войцех (1986). «Космическая сложность проблемы уникальной дешифрируемости». Письма об обработке информации. 23 (1): 1–3. Дои:10.1016/0020-0190(86)90121-3. МИСТЕР  0853618..
• Саломаа, Арто (1981). Драгоценности теории формального языка. Pitman Publishing. ISBN  0-273-08522-0. Zbl  0487.68064.
• Сардины, Август Альберт; Паттерсон, Джордж У. (1953), "Необходимое и достаточное условие для уникального разложения закодированных сообщений", Конференция Запись I.R.E., Национальное собрание 1953 г., Часть 8: Теория информации, стр. 104–108.

дальнейшее чтение

• Роберт Г. Галлагер: Теория информации и надежная коммуникация. Вайли, 1968 год.