Алгоритм распознавания однозн-ти

Используя нетривиальные разложения элементарных кодов, опишем алгоритм для схемы кодирования Σ.

1. Для каждого элементарного кода выполним всевозможные нетривиальные разложения.

2. Строим множество М следующим образом. В него включаем пустой символ L, а также каждое слово типа β, которое встречается в нетривиальных разложениях элементарных кодов как в роли префикса, так и в роли окончания. В разных ролях это слово не обязательно используется в разложении одного и того же элементарного кода.

3. Каждому слову из М сопоставляем вершину графа. Пусть слова , содержатся в М. Выделим среди нетривиальных разложений элементарных кодов схемы Σ разложения вида … . Для каждого из них проведем дугу из в , пометив ее элементарными кодами … . Полученный граф обозначим G(Σ).

4. Анализируем граф G(Σ), отыскивая в нем ориентированный цикл, содержащий вершину L. Если цикл существует, то кодирование не однозначно, иначе кодирование однозначно.

Date: 2015-09-05; view: 386; Нарушение авторских прав