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

Фриланс
Новости
Статьи
   
Рубрики:

Error. Page cannot be displayed. Please contact your service provider for more details. (30)


Поиск частичных совпадений

Поиск:
Чтобы изучить этот феномен, мы провели эксперименты как на словаре, так и на случайных данных (близких к словарю). Ограниченный объем данной статьи не позволяют нам описать эти эксперименты, подтверждающие приведенные в вышеуказанной таблице факты. Ключом к пониманию является то, что на верхних уровнях бора, представляющего словарь, велик фактор ветвления; начальный нефиксированный символ обычно приводит к 52 рекурсивным поискам. Ближе к концу слова, фактор ветвления напротив, становится небольшим; нефиксированный символ в конце слова часто дает всего лишь один рекурсивный поиск. Именно по этой причине Ривест полагает, что бинарные боры должны 'ветвиться в первом бите представления каждого символа ... до того, как ветвиться на втором бите каждого'. Флажолет и Пьюч [7] подробно проанализировали этот феномен для битовых боров; их методы можно расширить, чтобы обеспечить подробное представление цены поиска как функции от положения нефиксированного символа.

Таблица 1. Представление поиска частичных совпадений
Структура Совпадения

Узлы

Сбалансированное Случайное

television 1 18 24
tele...... 17 261 265
t.l.v.s..n 1 153 164
....vision 1 36,484 37,178
banana 1 15 17
ban... 15 166 166
.a.a.a 19 2829 2746
...ana 8 14,056 13,756
abracadabra 1 21 17
.br.c.d.br. 1 244 266
a..a.a.a..a 1 1127 1104
xy....... 3 67 66
.......xy 3 156,145 157,449
.45 1 285,807 285,807



Наконец, мы обращаемся к проблеме поиска 'соседей' в множестве строк: мы должны найти все слова словаря, находящиеся не дальше заданного расстояния Хемминга от запрашиваемого слова. Например, поиск всех слов, находящихся от soda на расстоянии, не большем двух, даст code, coma и 117 других слов. Программа 5 выполняет поиск соседей в троичном дереве поиска. Ее аргументами являются узел дерева, строка и расстояние. Первый if обеспечивает возврат в случае, если узел пуст или расстояние отрицательно. Второй и четвертый if симметричны: они просматривают подходящее поддерево, если расстояние положительно, или если символ запроса с подходящей стороны от splitchar. Третий if либо проверяет совпадение, либо рекурсивно просматривает срединное поддерево.


Код

void nearsearch(Tptr p, char *s, int d)
{
if (!p || d < 0) return;
nodecnt++;
if (d > 0 || *s < p->splitchar)
nearsearch(p->lokid, s, d);
if (p->splitchar == 0) {
if ((int) strlen(s) <= d)
srcharr[srchtop++] = (char *) p->eqkid;
} else
nearsearch(p->eqkid, *s ? s+1:s, (*s==p->splitchar) ? d:d-1);
if (d > 0 || *s > p->splitchar)
nearsearch(p->hikid, s, d);
}






Просмотров: 4124

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную