 |
Федотов А.А.
Институт Вычислительных Технологий СО РАН, Новосибирск
Деревья поиска предназначены для идентификации объектов в биологии, минералогии и пр. Мерой качества (стоимостью) дерева естественно считать среднее время определения объекта. Так как при практической проверке признаков возможны ошибки, очень важно строить деревья поиска, исправляющие и обнаруживающие заданное количество ошибок за счет некоторого повышения стоимости.
Известно, что построение наилучшего дерева поиска — NP-полная задача. В данной работе приведен быстрый алгоритм построения близкого к оптимальному дерева поиска, обнаруживающего и исправляющего заданное число ошибок, а также проведено его численное иследование в практически значимых случаях.
Дерево поиска — это форма записи алгоритма поиска в заданном множестве двоичных слов в виде бинарного дерева. Листьям этого дерева сопоставлены определяемые слова, а развилкам — номера проверяемых позиций. Алгоритм определения слова с помощью поискового дерева можно представить, как движение по этому дереву от корня к одному из листьев. При этом направление движения в развилке выбирается в зависимости от соответствующего разряда определяемого двоичного слова. Для примера на рисунке 1 приведены два дерева для поиска в множестве слов {000, 010, 110, 111}. Поясним, как происходит поиск в левом дереве. Сначала проверяется первый двоичный разряд рассматриваемого слова. Если он равен нулю, то мы идем по левой ветви дерева и проверяем второй двоичный разряд. В противном случае мы проверяем третий разряд слова. Таким образом, за две проверки мы всегда можем определить заданное слово.
Деревья поиска широко используются в различных задачах биологии, минералогии, теоретической информатики и математической кибернетики. При этом естественно возникает задача построения дерева, наиболее удобного для практического использования. Естественной оценкой качества дерева поиска принято считать стоимость дерева — среднее число проверяемых признаков, требуемых для определения одного объекта.
Известно, что задача построения поисковых деревьев эквивалентна задаче нахождения оптимального кода для конечного вероятностного источника [1, §2.1] при условии, что при построении дерева проверками разрешено разделять любые два подмножества исходного множества определяемых объектов. Алгоритм Хаффмана [1, §2.5, Лемма 2.1], решающий задачу построения оптимального кода, дает в нашем случае естественную нижнюю оценку стоимости дерева, зависящую только от количества объектов.
Здесь и далее мы ограничимся изучением комбинаторной модели, то есть будем предполагать, что определяемые объекты встречаются равновероятно. В этом случае стоимость дерева поиска в множестве из объектов не может быть меньше стоимости оптимального кода Хаффмана для конечного комбинаторного источника [1, §2.6, Утверждение 11], равной t*m = й log2 m щ + 1 – 2й log2 mщ / m. Таким образом, в данной модели левое дерево на рисунке 1 является оптимальным.
В данной работе мы будем рассматривать деревья поиска, обнаруживающие и исправляющие ошибки. Такие деревья изучались в теории кодирования [2], в биологических приложениях [4] и т. п. На рисунке 2 слева изображен пример дерева для поиска в множестве слов {010, 101}, обнаруживающего одну ошибку.
Объясним, почему это дерево можно так называть. Листья дерева, помеченные словом еrror, соответствуют словам, сумма первых двух бит в которых нечетна, а следовательно, продвигаясь по дереву от корня, в данный узел можно попасть, только совершив нечетное число ошибок, то есть одну. Если предположить, что совершено не более одной ошибки, то верно также, что в узел, соответствующий словам из заданного множества можно попасть только в случае, когда ни одной ошибки при проверках бит произведено не было. Таким образом, при данном предположении мы всегда либо правильно определяем двоичное слово, либо получаем сообщение о допущенной ошибке.
Деревья, исправляющие ошибки, не только сигнализируют о наличии ошибки, но и указывают, при проверке какого признака она была допущена. Пример дерева, исправляющего одну ошибку, изображен на рисунке 2 справа. Пути в этом дереве длины 2, начиная от корня, соответствуют безошибочному определению слова, а пути длины 3 — ошибке, допущенной при проверке бита, подчеркнутого на рисунке.
Естественно возникает задача построения оптимальных деревьев, то есть таких, стоимость которых минимальна. В этой работе мы будем предполагать, что ошибки совершаются с пренебрежимо малой вероятностью. Данная модель может быть рассмотрена в качестве простого и удобного ``первого приближения''. Так как выбрасывание из оптимального дерева, обнаруживающего одну ошибку, всех листьев, соответствующих ошибкам, и образовавшихся при этом тривиальных развилок, уменьшает стоимость дерева хотя бы на единицу, легко видеть, что нижняя граница стоимости такого дерева равна . Эта же нижняя граница, очевидно, справедлива и для деревьев, исправляющих одну ошибку. Так как для деревьев, изображенных на рисунке 2 данная нижняя граница достигается, эти деревья являются оптимальными.
Известно, что нахождение оптимального дерева поиска является NP-полной задачей [10]. Неформально говоря, это означает, что данная задача весьма требовательна к вычислительным ресурсам. Одним из подходов к решению данной проблемы является поиск быстрых приближенных алгоритмов, то есть алгоритмов, строящих дерево поиска, близкое к оптимальному за время, полиномиально зависящее от объема входных данных. Такие алгоритмы рассматривались в работах [5], [6], [7].
В частности, в работе [6] описан метод построения деревьев поиска, который авторы называют градиентным. Этот алгоритм строит деревья поиска следующим образом. Корню дерева сопоставляется проверка, которая делит все множество объектов на две по возможности равные части. Далее для каждой из этих частей дерево поиска строится аналогично. Было показано, что градиентный алгоритм строит деревья поиска достаточно хорошо — если число объектов не превосходит 200, то средняя стоимость деревьев, построенных градиентным алгоритмом, превышает естественную нижнюю оценку не более, чем на 0,07 признака с уровнем доверия 99,9%.
В данной работе показано, как обобщить градиентный алгоритм для построения деревьев, обнаруживающих и исправляющих ошибки. Более того, методом статистического моделирования [11] нами установлено, что если число объектов не превосходит 100, то градиентный алгоритм строит деревья, обнаруживающие и исправляющие одну ошибку, средняя стоимость которых отличается от естественной нижней границы менее, чем на 1,3 признака с достоверностью 99,9%.
Автор выражает благодарность научному руководителю Б. Я. Рябко за постановку задачи и внимание к работе.
Ваши комментарии
|
![[SBRAS]](/gif/s_sigma.gif)
[Головная страница] [Конференции] [СО РАН] |
© 2001, Сибирское отделение Российской академии наук, Новосибирск
© 2001, Объединенный институт информатики СО РАН, Новосибирск
© 2001, Институт вычислительных технологий СО РАН, Новосибирск
© 2001, Институт систем информатики СО РАН, Новосибирск
© 2001, Институт математики СО РАН, Новосибирск
© 2001, Институт цитологии и генетики СО РАН, Новосибирск
© 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
© 2001, Новосибирский государственный университет
Дата последней модификации Saturday, 29-Sep-2001 16:08:06 NOVST
