 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
ДЕРЕВЬЯ ОПТИМАЛЬНОГО ПОИСКА
В той же работе Вирта [3] рассматриваются и деревья оптимального поиска. Рассматривая выше поиск по таблице, мы исходили из предположения, что частота обращения ко всем элементам таблицы одинакова, т.е. все ключи с равной вероятностью фигурируют как аргументы поиска. Однако встречаются ситуации, когда есть информация о вероятности обращения к отдельным элементам таблицы. Обычно для таких ситуаций характерно “постоянство” элементов, то есть в дерево поиска элементы не включаются и не исключаются из него. Типичный пример – как раз сканер транслятора, определяющий, не относится ли идентификатор к классу терминалов (ключевых или зарезервированных слов). Статистические измерения на сотнях транслируемых программ могут в этом случае дать точную картину об относительных частотах появления отдельных элементов (обращений к ним). Для этих деревьев вместо понятия средней длины пути по дереву вводится понятие взвешенной длины пути – суммы всех путей от корня каждой из вершин, умноженных на вероятность обращения к этим вершинам.
В качестве примера рассмотрим множество из трех ключей 1, 2, 3 с вероятностями обращения к ним P1=1/7; P2=2/7; P3=4/7. Эти три ключа можно расставить в дерево поиска пятью различными способами, представленными на рис. 3.7. Там же приведены и взвешенные длины пути для каждого дерева.
Таким образом, оптимальным оказывается не идеально сбалансированное дерево (3.7 в), а вырожденное (3.7 а).
Сканер транслятора, предполагает, что задачу следует ставить при несколько больших общих условиях: слова встречающиеся в тексте не всегда ключевые, на самом деле эта ситуация скорее исключение, чем правило. Обнаружение, что данный ключ не является ключом дерева поиска, можно считать обращением к некоторой гипотетической вершине, включенной между следующей большей и следующей меньшой вершиной. Теория этого вопроса довольно сложна и не является задачей нашего курса. Отметим только, что оптимальное дерево поиска ключевых слов большинства языков программирования весьма далеко от сбалансированного.
Поиск по сайту: