Учебное пособие 800326

скрытности.

Выражение (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

Таблица 5.5

Рис. 5.6

Для дерева поиска на рис.5.6 и вероятностей из табл.5.5 значение потенциальной скрытности равно

X (1,1)

весьма близко к 0 . Если бы алгоритм поиска остался последовательным, то алгоритмическая скрытность была бы равна 3,402 диз, что заметно выше потенциальной.

Как видно, при выравнивании распределения вероятностей состояний объекта в оптимальном дереве поиска появляются дихотомические фрагменты (рис. 5.6), оно трансформируется от последовательного (рис. 5.4б) до дихотомическо-

го (рис. 5.3б).

49

5.4.2. Влияние ограничения ветвей на продолжительность поиска

При проектировании оптимальной поисковой процедуры могут налагаться ограничения на ее максимальную продол-

то величина l0 не влияет на алгоритм поиска. Таким образом,

ограничение максимальной длины ветви дерева поиска влияет на его форму, если

во поиска представлено на рис. 5.4б (последовательный алгоритм). Максимальная длина ветви равна 7 диз, а минимально допустимое значение l0 равно 3 диз.

На рис. 5.7а показано оптимальное дерево поиска при l0 6 , а на рис. 5.7б – при l0 5 . При l0 4 дерево принимает вид, показанный на рис. 5.6.

Рис.5.7

50

Как видно, укорочение ветвей дерева поиска приводит к появлению в нем дихотомических фрагментов, а если задано l0 3 диз (минимально возможное значение), то дерево поис-

ка становится полностью дихотомическим (рис. 5.3б).

вии ограничений) до S 3 диз (при минимальном l0 ). При

больших значениях A рассмотренные эффекты проявляются намного сильнее.

51

Глава 6. КРИВЫЕ СНЯТИЯ НЕОПРЕДЕЛЕННОСТИ

6.1. Изменение неопределенности в процессе поиска

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

Информационные характеристики поиска рассмотрены в главе 4. Общее описание дерева поиска приведено на рис.2.3. При выполнении N -го измерения проверяется наличие реа-

Продвижение по ветвям дерева поиска рис. 2.1 (перебор индексов k , k1 и q ) зависит от значения реасобытия xr , и для каждого из них можно записать

N 1

то есть, как отмечалось в главе 4, сумма декрементов неопределенности равна энтропии множества состояний объекта.

Усредняя (6.2) по всем реасобытиям, с учетом равенства единице суммы их вероятностей можно записать

а изменив порядок суммирования по r и N , получим

N 1 r X ( N )

где lmax - максимальное число измерений в ветвях дерева поиска, X (N) - множество состояний объекта, не обнаруженных после N двоичных измерений. Величина

измерения. Согласно главе 4 эта величина не более единицы. После N -го измерения при заданном реасобытии xr ос-

где индексы k и q определяется составом множества X (N) .

6.2. Кривая снятия неопределенности

Назовем кривой снятия неопределенности (КСН) гра-

фически выраженную зависимость средней остаточной неопределенности (энтропии) состояния объекта H (N) от числа

53

выполненных двоичных измерений N согласно (6.6).

При отсутствии ошибочных измерений функция H (N) из (6.6) не возрастает при увеличении N и стремится к нулю при N lmax .

Вычисление КСН при заданном дереве поиска проводится следующим образом.

После первого измерения выделяются два подмножества

и среднюю остаточную энтропию после первого двоичного измерения

Далее процесс продолжается аналогично. При N -м измерения определяется множество X (N) реасобытий, поиск которых не заканчивается после (N 1) измерений, для каждой части ветви дерева поиска длиной не менее (N 1) диз выде-

54

ляются пары подмножеств X 0( N ,q) и X 1( N ,q ) ( q 1,2... - индек-

сы подмножеств) и вычисляются вероятности вида (6.7) и условные энтропии (6.8). Остаточная энтропия после N измерений равна

Помимо усредненной КСН H (N) можно рассматривать частные кривые снятия неопределенности в виде зависимостей H ( X k( N ,q) ) для определенных значений реасобытия., от выбора которого зависят значения индексов k и q .

6.3. Примеры КСН

6.3.1. Показательный закон распределения вероятностей состояний объекта и последовательный поиск

Обратимся к рассмотренному ранее закону распределения вероятностей состояний объекта (5.21) и (5.22),

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

Рис. 6.2

Исходная энтропия множества X для рассматриваемого распределения вероятностей из(4.1) с учетом (6.11) и (6.12) равна

Далее расчет проводится аналогично, а если реасобытием являются xA 1 или xA , то после измерения с номером N A 1

поиск завершится, и неопределенность состояния объекта будет равна нулю.

На рис. 6.4 представлены зависимости условной энтропии H ( X1( N ,1) ) и усредненной энтропии H (N) от номера измерения N при A 8 . Условная энтропия H ( X 0( N ,1) ) 0 , так как в состав подмножества X 0( N ,1) xN входит только один элемент,

переход к ней показан на рис. 6.4 пунктирными линиями.

Как видно, первое измерение снижает среднюю энтропию

57

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

Условная энтропия H ( X1( N ,1) ) уменьшается с ростом N существенно медленнее, чем средняя H (N) . Это обусловлено

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

Рис. 6.4

Среднее число измерений (потенциальная скрытность) в рассматриваемом примере определяется выражением (5.26) и при A 8 равна S 1,965. Максимальное число измерений

для последовательного алгоритма равно lmax A 1 и сущест-

венно больше S . Это означает, что продолжительность поиска может быть различной в зависимости от реасобытия.

Для оценки этого эффекта целесообразно рассматривать