Приветствую,

Мне нужно реализовать следующую задачу: имеется множество пар "шаблон - значение". Когда я получаю на вход некоторую строку, необходимо быстро найти значение, шаблон которого наиболее точно соответствует введённой строке. Допустим у меня есть следующие пары:

"deck*" => 1
"de*" => 2
"*" => 3

Если я получаю на вход строку "deck123", должно быть выбрано значение 1. Если входная строка - "dekxxx", выбирается значение 2. Входная строка "pos123" выбирает значение 3.

Сейчас я делаю это с помощью двух списков: первый содержит все шаблоны, начинающиеся не с метасимвола, второй - все шаблоны, первый символ которых - метасимвол (*, ? , [ и т.д.). Первый список отсортирован по первой букве шаблона а в пределах буквы - по убыванию длины префикса шаблона, не включаещего метасимволы. Второй список отсортирован по убыванию длины шаблона.

Вначале я ищу первый элемент в списке 1, который начинается на ту же букву, что и введённая строка. Затем я просматриваю список последовательно до тех пор, пока первая буква остаётся неизменной и вызываю функцию сопоставления строки с шаблоном. Если сопоставление выполнено успешно, значение найдено. Если для выбранного отрезка из первого списка ни один шаблон не был успешно сопоставлен со входным значением, я последовательно просматриваю второй список от начала до конца, пока не будет найден совпадающий шаблон.

Существуют ли готовые контейнеры (аналогичные STL map), которые позволяют выполнять подобного рода поиск?



Это сообщение отредактировал(а) ivans - 10.12.2009, 13:21

Смотрите в сторону 'Регулярных Выражений' (и 'Конечных Автоматов', конкретно NFA & DFA). DFA позволяет выяснить принадлежность строки к конкретному шаблону за 1 посимвольный просмотр этой строки

Как раз способ сопоставления строки с отдельным шаблоном меня не сильно волнует. Я скорее всего буду использовать обычный glob из libc, даже не regexp. Вопрос именно в наличии ассоциативного контейнера, который бы позволял находить элемент по наиболее точному соответствию ключа (который представляет собой шаблон) со входной строкой.

КА - это способ произвести сопоставление со ВСЕМИ шаблонами за 1 проход по исходной строке. 
Вот где такое взять готовое - не знаю (в свое время делал сам)


Присоединённый файл ( Кол-во скачиваний: 10 )
 pm.zip 24,63 Kb

Спасибо за пример! Попробую теперь понять, что там к чему...