|
|
Опубликовано Штука Александр в Сб, 03/08/2008 - 18:13
|
Написать программу, осуществляющую поиск множества ключевых слов {beta, begin, green} в текстовом файле. Результатом работы программы должен быть список найденных слов и номера позиций этих слов в тексте. Символ новой строки не учитывать при подсчете позиции слова.
Использовать теории регулярных выражений и конечных автоматов:
1. Упростить, если это возможно, регулярное выражение;
2. Для заданного регулярного выражения построить соответствующий ему КА; Представление – диаграмма.
3. Если автомат, полученный в предыдущем пункте, недетерминированный, то преобразовать его в ДКА, используя метод “ленивого” вычисления подмножеств;
4. Если это удобно, переобозначить состояния полученного ДКА;
5. Используя ДКА, написать программу поиска ключевых слов в текстовом файле.
Решение.
1. Регулярное выражение: be( ta | gin ) | green
2. Диаграмма НКА, соответствующего этому регулярному выражению: ( рис )
НКА может быть представлен в виде таблицы переходов. В такой таблице: строки – состояния КА, столбцы – входные символы. Запись в строке для символа a - подмножество состояний, которые могут быть достигнуты из состояния при входном символе a. Строка, соответствующая начальному состоянию, отмечена стрелкой. Строки, соответствующие заключительным состояниям, отмечены «*».
Изначально таблица переходов ДКА содержит только одно состояние – eps( {S0} ). Это состояние объявляется текущим подмножеством .
Для текущего состояния по каждому символу из входного алфавита строим подмножество eps( move( T, a ) ).
Тем самым происходит заполнение текущей строки в таблице переходов ДКА. Если при этом образуются новые подмножества, те, которые еще не включены в эту таблицу, то дописываем их в новую строку как еще одно состояние ДКА.
Процесс останавливается после заполнения всей таблицы. В построенной таблице строка, соответствующая eps( {S0} ), объявляется начальным состоянием для ДКА.
Заключительными объявляются те из полученных подмножеств, в состав которых входит хотя бы одно из заключительных состояний исходного НКА.
//Программа поиска слов "beta", "begin", "green" в заданном тексте
#include <stdio.h>
#include <fstream.h>
#include <string.h>
#include <ctype.h>
//таблица переходов ДКА
int M[13][9] =
{
1, 0, 0, 0, 2, 0, 0, 0, 0,
1, 3, 0, 0, 2, 0, 0, 0, 0,
1, 0, 0, 0, 2, 0, 0, 4, 0,
1, 0, 5, 0, 6, 0, 0, 0, 0,
1, 7, 0, 0, 2, 0, 0, 0, 0,
1, 0, 0, 8, 2, 0, 0, 0, 0,
1, 0, 0, 0, 2, 9, 0, 4, 0,
1, 10, 0, 0, 2, 0, 0, 0, 0,
1, 0, 0, 0, 2, 0, 0, 0, 0,
1, 0, 0, 0, 2, 0, 11, 0, 0,
1, 0, 0, 0, 2, 0, 12, 0, 0,
1, 0, 0, 0, 2, 0, 0, 0, 0,
1, 0, 0, 0, 2, 0, 0, 0, 0
};
// Шаблон части входного алфавита
// Используется функцией NumbCol для
// определения по символу номера столбца в
// таблице переходов
char PatternStr[] = "betaginr";
// Прототип функции переходов
int Move(int S, char C);
// массив, R[i] содержит номер
// столбца в таблице переходов символа i
int R[26] = { 3, 0, 8, 8, 1, 8, 4, 8, 5, 8, 8, 8, 8, 6, 8, 8, 8, 7, 8, 2, 8, 8, 8, 8, 8, 8 };
int main()
{
cout << "Searching words \"beta, begin, green\"";
cout << "\nFind:\t\t Word Position" << endl;
// Текущий входной символ
char C;
// num[] - Количество найденных ключевых слов
// S - Текущее состояние ДКА
int i = 0, num[3] = {0}, S;
// Открытие файла с данными
ifstream fin( "dka.txt", ios::in );
// Начальное состояние
S = 0;
// Первый символ входной строки
fin.get(C);
i++;
// Пропуск символа новой строки
while( C == '\n' ) fin.get(C);
while( C != EOF )
{
// Переход к следующему состоянию
S = Move( S, C );
// Проверка заключительных состояний
switch( S )
{
// Найдено beta
case 8:
// Увеличиваем счетчик на 1
num[0]++;
// Выводим найденное слово, позицию слова в тексте
cout << "\t\t beta " << i-strlen("beta")+1 << endl;
break;
// Найдено begin
case 11:
num[1]++;
cout << "\t\t begin " << i-strlen("begin")+1 << endl;
break;
// Найдено green
case 12:
num[2]++;
cout << "\t\t green " << i-strlen("green")+1 << endl;
break;
}
// Следующий символ входной строки
fin.get(C);
i++;
// Пропуск символа новой строки
while (C == '\n')
fin.get(C);
}
// Закрытие файла
fin.close();
// Статистика поиска
cout << "\nStatistic:\t Word Quantity" << endl;
cout << "\t\t beta " << num[0] << endl;
cout << "\t\t begin " << num[1] << endl;
cout << "\t\t green " << num[2] << endl;
return 0;
}
// Функция переходов по ДКА
int Move(int S, char C)
{
// Следующее состояние из таблицы M
return M[ S ][ R[tolower(C)-'a'] ];
}
Ключевые слова:
регулярные выражения, недетерминированные конечные автоматы, поисковая система
|
|
