|
|
Реализация поиска с использованием “wildcard” символов на базе регулярных выражений Автор: Мартинов Г.М.
Лаборатория систем ЧПУ кафедры КСУ, МГТУ "СТАНКИН" Опубликовано: 05.07.2004
Версия текста: 1.0 Постановка задачи Нередки случаи, когда в пользовательском интерфейсе необходимо реализовать функциональность поиска. Хороший поиск это быстрый поиск, предоставляющий гибкость работы с шаблонами. Шаблоны не предполагают точное задание поискового слова, можно обойтись его фрагментом или смежным выражением для поиска целой группы. Это весьма удобно, если слово которые вы ищете длиннее 5-7 символов. Шаблоны поиска бывают двух видов: - На базе "wildcard" символов;
- На базе регулярных выражений (regular expression).
В таких продуктах как Microsoft Word или Microsoft VisualStudio можно искать используя оба варианта, хотя поиск с помощю "wildcard" символов более привычен и интуитивно понятен. Лично мне, знакомому с регулярными выражениями не первый год и проводившему не менее 50 часов в неделю с VisualStudio, приходилось использовать в поиске регулярные выражения всего не более 2-3 раз. Поиск с использованием "wildcard" символов предполагает использовать симавол "?" для замены любого одиночного символа и символ "*" для замены любой группы символов. Наверняка "wildcard" вам приходилось использовать при работе с файловой системой DOS или Windows. Правила конвертации Для трансляции шаблона с набором "wildcard" символов в шаблон с регулярными выражениями были сформированы следующие 4 правила: - Заменить "wildcard" символ "?" на выражение "[^n]";
- Заменить "wildcard" символ "*" на выражение "[^n]*";
- Добавить "^" в начале регулярного выражения;
- Добавить "$" в конец регулярного выражения.
ПРЕДУПРЕЖДЕНИЕ
Пример: Согласно правилам шаблон поиска с "wildcard" символами "Пра?ил*" конвертируется в регулярном выражение "^Пра[^n]ил[^n]*$". | Реализация на C++ Реализация алгоритма ориентирована на работу с UNICODE и использует шаблон CAtlRegExp (см. [1]) для Visual С++ 6.0. Не следует забывать, что некоторые символы применяемые в регулярных выражениях являются служебными и их нужно экранировать посредством символа "" (см. [2]), этим и занимается функция utility_ShadeMetacharacters(). ПРЕДУПРЕЖДЕНИЕ
Символ "" является не только служебным символом для регулярных выражений, но и для языка C++ и это надо учитывать. | Функция замены "wildcard" символов Листинг функции
static _bstr_t utility_ReplaceWildcards(_bstr_t bstrString)
{
bstrString = utility_ShadeMetacharacters(bstrString, L"{[\\|+{}[\]()^$.]}");
_bstr_t bstrRegExpresion = L"{[*?]}";
CAtlRegExp<> re;
REParseError status = re.Parse(bstrRegExpresion);
if(status != REPARSE_ERROR_OK)
return L"";
const wchar_t* pEnd = bstrString;
_bstr_t bstrRes = L"";
do
{
CAtlREMatchContext<> mc;
const wchar_t *szBegin = pEnd;
if ( !re.Match(pEnd, &mc, &pEnd) )
{
bstrRes += szBegin;
break;
}
if ( mc.m_uNumGroups > 0 )
{
const wchar_t* szStart, * szEnd;
mc.GetMatch(0, &szStart, &szEnd);
if ( szEnd == szStart )
{
bstrString = pEnd;
continue;
}
wchar_t wchBuff[1024];
if ( szBegin != szStart )
{
swprintf(wchBuff, L"%.*s", szStart -szBegin, szBegin);
bstrRes += _bstr_t(wchBuff);
}
swprintf(wchBuff, L"%.*s", szEnd -szStart, szStart);
bstrRes += ( _bstr_t(wchBuff) == _bstr_t(L"*") )
? L"[^n]" +_bstr_t(wchBuff)
: L"[^n]";
}
}
while ( _bstr_t(pEnd) != _bstr_t(L"") );
bstrRes = L"^" +bstrRes +L"$";
return bstrRes;
}
| Функции экранированияЛистинг функции
static _bstr_t utility_ShadeMetacharacters(_bstr_t bstrString, _bstr_t bstrRegExpr = L"")
{
_bstr_t bstrRegExpresion = ( bstrRegExpr ==_bstr_t(L"") )
? L"{[\\|+{}[\]()^$.*?]}"
: bstrRegExpr;
CAtlRegExp<> re;
REParseError status = re.Parse(bstrRegExpresion);
if(status != REPARSE_ERROR_OK)
return L"";
const wchar_t* pEnd = bstrString;
_bstr_t bstrRes = L"";
do
{
CAtlREMatchContext<> mc;
const wchar_t *szBegin = pEnd;
if ( !re.Match(pEnd, &mc, &pEnd) )
{
bstrRes += szBegin;
break;
}
if ( mc.m_uNumGroups > 0 )
{
const wchar_t* szStart, * szEnd;
mc.GetMatch(0, &szStart, &szEnd);
if ( szEnd == szStart )
{
bstrString = pEnd;
continue;
}
wchar_t wchBuff[1024];
if ( szBegin != szStart )
{
swprintf(wchBuff, L"%.*s", szStart -szBegin, szBegin);
bstrRes += _bstr_t(wchBuff);
}
swprintf(wchBuff, L"%.*s", szEnd -szStart, szStart);
bstrRes += L"\" +_bstr_t(wchBuff);
}
}
while ( _bstr_t(pEnd) != _bstr_t(L"") );
return bstrRes;
}
|
В заключениеРеализуя свой алгоритм поиска в пользовательском интерфейсе незабудьте вывести информацию о количество найденный слов, потому что если результат поиска более чем 20-30, то нужно сужать границы поиска или конкретизировать шаблон. Другая деталь, на которую хотелось бы обратить внимание - это наличие второго окна с результатами поиска, функциональности знакомой всем кто работал с VisualStudio и весма удобной для опытных пользователей. Список ссылок- Козак Н.В. Использование регулярных выражений для фильтрации ввода.
- Регулярные выражения. 2-е изд. /Дж. Фридл.- СПб.: Питер, 2003.- 464 с.: ил. - (Серия "Библиотека программиста"). ISBN 5-272-00331-4.
Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав.
|