Материал: Теория скрытности. Часть 1, Основы теории скрытности. Каневский З.М., Литвиненко В.П

скрытности.

Выражение (5.14) является не вполне точным решением задачи определения потенциальной скрытности, так как при оптимизации использовались непрерывные значения длин ветвей дерева поиска (5.12), а фактически они всегда имеют целочисленные значения, то есть длина ветви li является це-

лым числом, удовлетворяющим неравенству

Тогда точное значение потенциальной скрытности S находится в границах неравенства (4.13),

Таким образом, полученные выражения позволяют опре-

делять потенциальную скрытность объекта при отсутствии ошибочных измерений. Однако проведенный анализ не позволяет получить правило формирования оптимального дерева и соответствующий ему алгоритм поиска. Для этого необходимо провести дополнительные исследования на базе известных результатов теории кодирования.

Как видно из (5.12) или (5.15), оптимальные длины ветвей дерева поиска тем больше, чем меньше вероятности соответствующих реасобытий, то есть

Это условие, которое будем называть иерархическим принципом, полезно для выбора и анализа оптимального алгоритма поиска.

39

5.3. Оптимизация поиска на основе методов безызбыточного кодирования сообщений

5.3.1. Двоичное кодирование

В проводной и радиосвязи широко используются различные методы кодирования дискретных сообщений посредством двоичных символов 0 и 1.

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

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

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

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

Остановимся на двух известных методах безызбыточного кодирования, описываемых ниже.

5.3.2. Метод Шеннона-Фано

Исходное множество элементов сообщения (состояний объекта) с заданным распределением их вероятностей разбивается на два подмножества с номерами 0 и 1 так, чтобы ве-

40

роятности попадания в них были максимально близки (равны 0,5). Затем каждое из полученных подмножеств отдельно разбивается на два подмножества с тем же условием и ном5ерами соответственно 00, 01 и 10, 11. Разбиение заканчивается, когда все подмножества будут иметь только по одному элементу.

В качестве примера рассмотрим множество состояний из A 5 элементов с распределением вероятностей, представленном в табл.5.1.

Таблица 5.1

можно близкими суммарными значениями вероятностей входящих в них элементов. В рассматриваемом случае получим

Так как полученные подмножества содержат по одному элементу, то в этом направлении разбиения прекращаются.

Аналогично проводится разбиение множества X1(1,1) на

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

Описанный метод Шенно- на-Фано позволяет построить показанное на рис. 5.2 дерево поиска с отмеченными двоичными кодами соответствующих подмножеств, разрядность которых равна длинам ветвей.

Рис. 5.2 Оптимальность кода Шен- нона-Фано обусловлена рациональным сочетанием длин ветвей дерева поиска с частостью

употребления состояний объекта и последовательным делением множества Х на равновероятные подмножества с максимумом получения информации при каждом измерении. Выполняется иерархический принцип сочетания Pi и li (5.18).

Среднее число двоичных измерений в соответствии с де42

ревом поиска (рис. 5.2) равно

Как видно, среднее число двоичных измерений R для полученного оптимального алгоритма поиска близко к энтропии множества, причем H(X ) R H(X ) 1, что соответствует оценке потенциальной скрытности (5.17).

5.3.3. Метод Циммермана – Хаффмена

Разработанный независимо Циммерманом для задач поиска и Хаффменом для кодирования сообщений – метод позволяет находить оптимальные алгоритмы и строить соответствующие деревья поиска применительно к нашим задачам.

Алгоритм формирования дерева поиска состоит в следующем. Производится ранжирование состояний по мере уменьшения их вероятностей в виде (5.2). Два наименее вероятных состояния объединяются о одно, образуя узел дерева поиска. Эти состояния исключаются из множества X и заменяются объединенным состоянием, образуя новое множество X (1) . В нем проводится ранжирование состояний по мере снижения их вероятностей. Процесс повторяется до тех пор, пока в преобразованном множестве не окажется лишь два

x4 , их суммарное значение равно 0,25. Тогда получается множество, представленное в табл. 5.2.

Минимальные вероятности имеют состояния x3 и объединенное состояние x4 , x5 , суммарная вероятность равна 0,45. Получается множество, представленное в табл. 5.3.

ным на рис. 5.2 для метода Шеннона-Фано с той же эффективностью процесса оптимизации.

44

5.4. Изменение оптимального алгоритма поиска и потенциальной скрытности

5.4.1. Влияние распределения вероятностей

Рассмотренные процедуры формирования оптимального алгоритма поиска и соответствующего ему дерева свидетельствуют о сильном влиянии на них распределения вероятностей состояний объекта. Не умаляя общности результатов, будем рассматривать ранжированные распределения (5.2). Тогда форма дерева поиска зависит прежде всего от диапазона изменения вероятностей от P1 до PA .

Рассмотрим закон распределения вероятностей состояний объекта в виде показательной функции

тель, i 1, A . Так как сумма вероятностей равно единице, то величина в соответствии с выражением для суммы членов геометрической прогрессии (5.21) будет равна

том номера состояния.

Используя (5.22), можно имитировать различные законы распределения вероятностей состояний объекта с разными

Рис. 5.3

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

Такого рода алгоритм раскрытия реасобытия называют дихотомическим. Длины всех ветвей дерева поиска одинаковы и равны l0 log2 A , что является нижней границей усло-

вия регулярности (5.9). Таким образом, дихотомический алгоритм поиска имеет минимальное значение максимальной длины дерева поиска.

При равновероятном распределении вероятностей со-

стояний и их арсенале A 2n ( n - целое число) потенциальная скрытность определяется выражением

то сумма вероятностей двух последних состояний меньше вероятности предшествующего состояния. Тогда в соответствии с методом Циммермана – Хаффмена оптимальным оказывается последовательный алгоритм поиска, при котором проверка начинается с одного первого (наиболее вероятного) элемента x1 , затем следующего и так далее до предпоследнего xA 1 . Если при этом реасобытие не обнаружено, значит, оно соответствует элементу xA . В качестве примера на рис. 5.4а показано

распределение вероятностей вида (5.21) при 1 и A 8 , а на рис. 5.4б – соответствующее дерево поиска для последовательного алгоритма.

Для последовательного алгоритма максимальная продолжительность поиска равна (A 1) диз, что существенно выше, чем у дихотомического.

Рис. 5.4

Если выполняется (5.24), то оптимальным всегда является последовательный алгоритм поиска, а потенциальная скрытность определяется выражением

Сумма представляет собой арифметико-геометрическую

47

летворяющих условию (5.24) при последовательном алгоритме поиска. Как видно, в этом случае потенциальная скрытность ограничена величиной (5.27) при неограниченном увеличении числа состояний. В

верить, что значения S близки к энтропийной скрытности и удовлетворяют неравенству

(5.17).

Если параметр не удовлетворяет условию (5.24), Рис. 5.5 то последовательный поиск не является оптимальным, а

дерево поиска изменяется по сравнению с рис. 5.4б. Например, при 0,3 распределение вероятностей при-

ведено в табл. 5.5 и ближе к равномерному, чем показанное на рис. 5.4а

Соответствующее дерево поиска приведено на рис. 5.6.

48