АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

ДЕРЕВЬЯ ОПТИМАЛЬНОГО ПОИСКА

Читайте также:
  1. II. Методы прогнозирования и поиска идей
  2. БУДУЩЕЕ – ОТ ВАС СКРЫТА ВАЖНАЯ ЧАСТЬ ИНФОРМАЦИИ. УВЕЛИЧЬТЕ РАДИУС ПОИСКА.
  3. В ПОИСКАХ ОБЪЯСНЕНИЙ
  4. В поисках ответа
  5. В ПОИСКАХ УТРАЧЕННОГО ВИТЬКА
  6. Визначення оптимального варіанту розв’язання проблем на основі порівняльного аналізу можливих варіантів
  7. Визначення оптимального рівня товарних запасів та точки замовлення
  8. Выбор оптимального портфеля
  9. Генетический алгоритм поиска.
  10. Задача оптимального развития сети автомобильных дорог
  11. Источники поиска работы

В той же работе Вирта [3] рассматриваются и деревья оптимального поиска. Рассматривая выше поиск по таблице, мы исходили из предположения, что частота обращения ко всем элементам таблицы одинакова, т.е. все ключи с равной вероятностью фигурируют как аргументы поиска. Однако встречаются ситуации, когда есть информация о вероятности обращения к отдельным элементам таблицы. Обычно для таких ситуаций характерно “постоянство” элементов, то есть в дерево поиска элементы не включаются и не исключаются из него. Типичный пример – как раз сканер транслятора, определяющий, не относится ли идентификатор к классу терминалов (ключевых или зарезервированных слов). Статистические измерения на сотнях транслируемых программ могут в этом случае дать точную картину об относительных частотах появления отдельных элементов (обращений к ним). Для этих деревьев вместо понятия средней длины пути по дереву вводится понятие взвешенной длины путисуммы всех путей от корня каждой из вершин, умноженных на вероятность обращения к этим вершинам.

В качестве примера рассмотрим множество из трех ключей 1, 2, 3 с вероятностями обращения к ним P1=1/7; P2=2/7; P3=4/7. Эти три ключа можно расставить в дерево поиска пятью различными способами, представленными на рис. 3.7. Там же приведены и взвешенные длины пути для каждого дерева.

Таким образом, оптимальным оказывается не идеально сбалансированное дерево (3.7 в), а вырожденное (3.7 а).

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


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.002 сек.)