Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
х Е А?
В случае положительного ответа разбиваем А на два подмножества
А = А' + А', А' С А
и спрашиваем:
х Е А'?
и т.д., пока не получим точное значение элемента х. Возникает вопрос: как
следует выбирать множество А? С точки зрения распознавания образов
требуется раскрыть неопределенность признака (слова) У, где
У = (а, Ь, с, d, е, f).
Мы пытаемся раскрыть эту неопределенность с помощью косвенного признака
ХА = (1, 1, О, О, О, 0),
который получается, когда мы отождествляем все буквы из множества А,
приписывая им значение 1. При этом все буквы
из А получают значение 0. Информативность признака ХА, равная
Iq(Xa:Y), должна быть максимальна.
64
Переход от Y к ХА соответствует группировке наблюдений (квантованию). В
предложении 1.8 было показано, что
V*A:y) - W s N-Таким образом, максимальное количество информации мы
получаем, когда разбиваем исходное множество R на два равномощных
множества:
\А\ = N/2, /0(^л) = N.
Следовательно, идентифицировать объект х можно, задавая ] log [ бинарных
вопросов, на которые можно ответить лишь "да" или "нет". Меньшее
количество таких вопросов не позволит нам раскрыть неопределенность
признака Y. Действительно, энтропия слова Y равна
/0(У) = N log N,
а признак ХА уменьшает эту неопределенность максимум на N бит.
Пусть теперь каждый элемент множества R соответствует некоторой записи в
компьютере. Каждая запись однозначно определяется своим ключом К. (целым
числом). Множество R
записей называется файлом. Предполагается, что файл отсортирован:
К, < К, < ... < К".
12 N
Требуется найти запись с ключом К. Как мы показали только что, самый
быстрый поиск связан с делением файла пополам.
4.6. Быстрая сортировка
Произвольный файл, в котором встречаются одинаковые записи, можно
представить в виде слова длины N:
R = (acbaabcdabda).
Допустим, что композиция этого слова равна
(ffij, тг ..., mk).
Всего существует
N = п\/т^. ... т
слов, являющихся перестановками слова R, и только одно из них является
отсортированным:
Rq = (aaaaabbbccdd).
В этом слове все буквы лексикографически упорядочены.
Отсортировать слово R-это значит распознать подстановку ст, с помощью
которой это слово переводится в слово R^:
*0 = OR-
-• В.Д.Гоппа 65
Как было показано в предыдущем пункте, для этого потребуется по крайней
мере
log N = Iq(R)
бинарных вопросов (сравнений). Таким образом, сложность сортировки не
может быть меньше, чем /0(Л). В том случае,
когда все записи различны, имеем
УЛ) = я log п,
где л-длина файла.
Существует простой метод сортировки, на котором достигается эта граница-
сортировка слиянием.
Пусть заданы два отсортированных файла длины тип соответственно:
х
у
Оба файла хранятся в регистре сдвига. Первые числа обоих регистров
поступают на устройство сравнения. Минимальное из этих чисел вводится в
регистр Z на выходе. Если это число было взято из регистра У, то
содержимое этого регистра сдвигается влево и сравнению подвергаются новые
числа.
В результате после т + п сравнений получаем отсортированный файл длины т
+ п. Последовательная реализация этой идеи приводит к следующей схеме
сортировки:
а а а а b b b с с d d
aabd
aabd
66
1.2.6.7
Допустим для простоты, что п = 2 . Исходный файл разбивается на п/2
отрезков длины 2. Каждый из отрезков сортируется; для этого потребуется
п/2 сравнений. Затем образуется п/4 отрезков длины 4 путем слияния. Для
этого потребуется еще (п/4)-4 = п сравнений. Затем п/8 отрезков длины 8
потребуют еще п сравнений, и т. д. В результате получаем отсортированный
файл после
п/2 + n(log п - 1)
сравнений. Ниже показана сортировка слиянием 16 различных чисел:
1
2 3
4
5
6
7
8
9
10
11 12
13
14
15
16
9.10.11.14
1.2.6.7.9.10.11.14
3.4.5.16
3.4.5.8.12.13.15.16___
8.12.13.15
4.7. Дерево поиска
Бинарный поиск является самым быстрым методом поиска, но для его
применения требуется, чтобы исходный файл был отсортирован.
В том случае, когда файл является динамическим, т.е. регулярно
добавляются новые записи или стираются старые, частое применение
сортировки снижает эффективность бинарного поиска. В этом случае более
пригодной является иерархическая организация записей файла, при которой
поиск осуществляется с помощью бинарного дерева.
Допустим, что записи с ключами К. поступают в следующем порядке:
*1 *2 *3 *4 % *6 *7 *8
643 123 276 850 720 087 061 321
Первую запись объявляем корнем дерева:
643
При поступлении записи с ключом К2 производим сравнение
*2 < V
При положительном ответе помещаем запись К в левой ветви, в противном
случае-в правой ветви дерева:
?ЛИ
Точно так же поступаем со следующей записью:
В результате получаем ордерево поиска:
Полученное дерево хранится в памяти компьютера в виде набора записей
(узлов) Р. Каждый узел Р содержит следующие поля:
Address(P) -адрес в памяти;
Key (Р) -ключ;
L(P) -указатель левого поддерева, равный адресу со-
ответствующего узла;
R(P) -указатель правого поддерева;
1п}огт(Р) -информация, содержащаяся в данной записи. Корень дерева
