38. Алфавитное кодирование: теорема Маркова, алгоритм Маркова.

Пусть А - исходный алфавит, содержащий буквы . В нем записывается исходное сообщение – слово, составленное из одной или нескольких букв. В кодирующем алфавитезаписывается закодированное сообщение. Правила, по которым осуществляется кодирование, могут быть разными. Алфавитное кодирование, как одно из возможных правил, задается схемой Σ вида

где - слова в кодирующем алфавите. Их называюткодовыми словами. Для того чтобы с помощью такой схемы закодировать некоторое слово, состоящее из нескольких букв (разрядов), надо каждую букву этого слова закодировать соответствующим ей кодовым словом.

Алфавитное кодирование – кодирование, выполняющееся поразрядно.

Определение. Схема алфавитного кодирования называется однозначно декодируемой, если любое закодированное слово допускает только один способ декодирования.

Определение. Схема алфавитного кодирования называется равномерной, если все её кодовые слова попарно различны, но имеют одинаковую длину.

Теорема Маркова. Для любой схемы алфавитного кодирования Σ существует такое числоN_Σ, что схема Σ является однозначно декодируемой тогда и только тогда, когда однозначно декодируемы все слова из множества.

Число N₀можно вычислить через характеристики самой схемы Σ. Для этого нужно рассмотреть все возможные префиксы и суффиксы кодовых словсхемы Σ. Пусть кодовое слово В_kимеет вид, где р – префикс,s– суффикс,- кодовые слова, причем префикс (суффикс) может быть пустым словом Λ, но не должен совпадать ни с одним из кодовых слов. Т - максимальное число кодовых слов, которые могут содержаться в разложении другого кодового слова. Тогда числоN_Σиз теоремы Маркова удовлетворяет неравенству, гдеL– суммарная длина всех кодовых словсхемы Σ.

Пример. Требуется оценить сверху числоN_Σдля схемы Σ с кодовыми словами В₁ =ab, В₂ =bc, В₃ =acb, В₄ =abac, В₅ =babbc. Проверить, является ли схема однозначно декодируемой. В этой схемеL= 16, r = 5. Для нахождения параметра Т рассмотрим все возможные разложения кодовых слов:

В₁ = ab = (a)(b),

В₂ = bc = (b)(c),

В₃ = acb = (a)(cb) = (ac)(b),

В₄ = abac = (a)(bac) = [ab](ac) = (aba)(c),

В₅ = babbc = (b)[ab][bc] = (ba)(bbc) =(bab)[bc] = (babb)(c),

где для удобства префиксы и суффиксы заключены в круглые скобки, а кодовые слова – в квадратные. В некоторых разложениях префикс или суффикс – пустое слово Λ. Поскольку в разложении кодового слова В₅ = (b)[ab][bc] = (b)В₁В₂содержится два других кодовых слова, и это максимально возможное количество для данной схемы Σ, то параметр Т = 2. Следовательно,.

Алгоритм проверки однозначности декодирования. Опираясь на разложения, построим множество S, включающее все такие префиксы, которые также являются и суффиксами кодовых слов. Также добавим в множествоSпустое слово Λ. В данном случае получится множествоS= {b,ac, Λ}.

Построим ориентированный граф G_Σс помеченными вершинами и ребрами. Каждая его вершина помечается некоторым элементом множестваS. Две вершины соединяются ребром только тогда, когда их метки являются префиксом и суффиксом одного и того же кодового слова. Само ребро помечают частью этого слова, заключенной между префиксом и суффиксом, и ориентируют от вершины-префикса к вершине-суффиксу. В данном случае кодовое слово В₅разложимо в виде В₅ =babbc= (b)[ab][bc] = (b)В₁В₂,

т.е. начинается с префикса bи заканчивается пустым суффиксом. Поэтому в графеG_Σимеется ребро, помеченное словами В₁В₂и направленное от вершиныbк вершине Λ. Другое ребро графаG_Σ, помеченное словом В₁, выходит из вершины Λ в вершинуac, поскольку кодовое слово В₄ =abac= [ab](ac) = В₁(ac).

Третье ребро помечено пустым словом Λ и направлено от вершины acк вершинеb, так как кодовое слово В₃ =acb= (ac)(b). Таким образом, получаем графG_Σ, в нем есть ориентированный цикл, проходящий через вершину Λ. Данная схема Σ не является однозначно декодируемой.

Утверждение .Схема алфавитного кодирования Σ является однозначно декодируемой тогда и только тогда, когда в её графеG_Σнет ориентированного цикла, проходящего через вершину Λ.