|
Построение набора стоп-слов
Отображение состоит из пар ключ/значение. Множество (set), напротив, содержит неупорядоченную совокупность ключей. Например, бизнесмен может составить “черный список” bad_checks, содержащий имена лиц, в течение последних двух лет присылавших фальшивые чеки. Множество полезно тогда, когда нужно узнать, содержится ли определенное значение в списке. Скажем, наш бизнесмен, принимая чек от кого-либо, может проверить, есть ли его имя в bad_checks.
Для нашей поисковой системы мы построим набор стоп-слов – слов, имеющих семантически нейтральное значение (артикли, союзы, предлоги), таких, как the, and, into, with, but и т.д. (это улучшает качество системы, однако мы уже не сможем найти первое предложение из знаменитого монолога Гамлета: “To be or not to be?”). Прежде чем добавлять слово к word_map, проверим, не содержится ли оно в списке стоп-слов. Если содержится, проигнорируем его.
Определение объекта set и заполнение его элементами
Перед использованием класса set необходимо включить соответствующий заголовочный файл:
#include <set>
Вот определение нашего множества стоп-слов:
set<string> exclusion_set;
Отдельные элементы могут добавляться туда с помощью операции insert(). Например:
| exclusion_set.insert( "the" );
| exclusion_set.insert( "and" );
Передавая insert() пару итераторов, можно добавить целый диапазон элементов. Скажем, наша поисковая система позволяет указать файл со стоп-словами. Если такой файл не задан, берется некоторый набор слов по умолчанию:
| typedef set< string >::difference_type diff_type;
set< string > exclusion_set;
ifstream infile( "exclusion_set" );
if ( ! infile )
{
static string default_excluded_words[25] = {
"the","and","but","that","then","are","been",
"can"."can't","cannot","could","did","for",
"had","have","him","his","her","its","into",
"were","which","when","with","would"
};
cerr << "предупреждение! невозможно открыть файл стоп-слов! -- "
<< "используется стандартный набор слов \n";
copy( default_excluded_words, default_excluded_words+25,
inserter( exclusion_set, exclusion_set.begin() ));
}
else {
istream_iterator<string,diff_type> input_set(infile),eos;
copy( input_set, eos, inserter( exclusion_set,
exclusion_set.begin() ));
| }
В этом фрагменте кода встречаются два элемента, которые мы до сих пор не рассматривали: тип difference_type и класс inserter. difference_type – это тип результата вычитания двух итераторов для нашего множества строк. Он передается в качестве одного из параметров шаблона istream_iterator.
copy() –один из обобщенных алгоритмов. (Мы рассмотрим их в главе 12 и в Приложении.) Первые два параметра – пара итераторов или указателей – задают диапазон. Третий параметр является либо итератором, либо указателем на начало контейнера, в который элементы копируются.
Проблема с этой функцией вызвана ограничением, вытекающим из ее реализации: количество копируемых элементов не может превосходить числа элементов в контейнере-адресате. Дело в том, что copy() не вставляет элементы, она только присваивает каждому элементу новое значение. Однако ассоциативные контейнеры не позволяют явно задать размер. Чтобы скопировать элементы в наше множество, мы должны заставить copy() вставлять элементы. Именно для этого служит класс inserter (детально он рассматривается в разделе 12.4).
Поиск элемента
Две операции, позволяющие отыскать в наборе определенное значение, – это find() и count(). find() возвращает итератор, указывающий на найденный элемент, или значение, равное end(), если он отсутствует. count() возвращает 1 при наличии элемента и 0 в противном случае. Добавим проверку на существование в функцию build_word_map():
| if ( exclusion_set.count( textword ))
continue;
| // добавим отсутствующее слово
Навигация по множеству
Для проверки наших кодов реализуем небольшую функцию, выполняющую поиск по одному слову (поддержка языка запросов будет добавлена в главе 17). Если слово найдено, мы будем показывать каждую строку, в которой оно содержится. Слово может повторяться в строке, например:
tomorrow and tomorrow and tomorrow
однако такая строка будет представлена только один раз.
Одним из способов не учитывать повторное вхождение слова в строку является использование множества, как показано в следующем фрагменте кода:
| // получим указатель на вектор позиций
loc ploc = (*text_map)[ query_text ];
// переберем все позиции
// вставим все номера строк в множество
set< short > occurrence_lines;
loc::iterator liter = ploc->begin(),
liter_end = ploc->end();
while ( liter != liter_end ) {
occurrence_lines.insert( occurrence_lines.end(),
(*liter).first );
++liter;
| }
Контейнер set не допускает дублирования ключей. Поэтому можно гарантировать, что occurrence_lines не содержит повторений. Теперь нам достаточно перебрать данное множество, чтобы показать все номера строк, где встретилось данное слово:
| register int size = occurrence_lines.size();
cout << "\n" << query_text
<< " встречается " << size
<< " раз(а):")
<< "\n\n";
set< short >::iterator it=occurrence_lines.begin();
for ( ; it != occurrence_lines.end(); ++it ) {
int line = -it;
cout << "\t( строка "
<< line + 1 << " ) "
<< (*text_file)[line] << endl;
| }
(Полная реализация query_text() представлена в следующем разделе.)
Класс set поддерживает операции size(), empty() и erase() точно таким же образом, как и класс map, описанный выше. Кроме того, обобщенные алгоритмы предоставляют набор специфических функций для множеств, например set_union() (объединение) и set_difference() (разность). (Они использованы при реализации языка запросов в главе 17.)
Упражнение 6.23
Добавьте в программу множество слов, в которых заключающее 's' не подчиняется общим правилам и не должно удаляться. Примерами таких слов могут быть Pythagoras, Brahms и Burne_Jones. Включите в функцию suffix_s() из раздела 6.10 проверку этого набора.
Упражнение 6.24
Определите вектор, содержащий названия книг, которые вы собираетесь прочесть в ближайшие шесть виртуальных месяцев, и множество, включающее названия уже прочитанных произведений. Напишите программу, которая выбирает для вас книгу из вектора при условии, что вы ее еще не прочитали. Выбранное название программа должна заносить в множество прочитанных. Однако вы могли отложить книгу; следовательно, нужно обеспечить возможность удалять ее название из множества прочитанных. По окончании шести виртуальных месяцев распечатайте список прочитанного и непрочитанного.
Окончательная программа
Ниже представлен полный текст программы, разработанной в этой главе, с двумя модификациями: мы инкапсулировали все структуры данных и функции в класс TextQuery (в последующих главах мы обсудим подобное использование классов), кроме того, текст был изменен, так как наш компилятор поддерживал стандарт С++ не полностью.
Например, библиотека iostream не соответствовала текущему стандарту. Шаблоны не поддерживали значения аргументов по умолчанию. Возможно, вам придется изменить кое-что в этой программе, чтобы она компилировалась в вашей системе.
| // стандартные заголовочные файлы С++
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <map>
#include <set>
// заголовочный файл iostream, не отвечающий стандарту
#include <fstream.h>
// заголовочные файлы С
#include <stddef.h>
#include <ctype.h>
// typedef для удобства чтения
typedef pair<short,short> location;
typedef vector<location,allocator> loc;
typedef vector<string,allocator> text;
typedef pair<text*,loc*> text_loc;
class TextQuery {
public:
TextQuery() { memset( this, 0, sizeof( TextQuery )); }
static void
filter_elements( string felems ) { filt_elems = felems; }
void query_text();
void display_map_text();
void display_text_locations();
void doit() {
retrieve_text();
separate_words();
filter_text();
suffix_text();
strip_caps();
build_word_map();
}
private:
void retrieve_text();
void separate_words():
void filter_text();
void strip_caps();
void suffix_textQ;
void suffix_s( string& );
void build_word_map();
private:
vector<string,allocator> *lines_of_text;
text_loc *text_locations;
map< string,loc*,
less<string>,allocator> *word_map;
static string filt_elems;
};
string TextQuery::filt_elems( "\", •;: !?)(\V" );
int main()
{
TextQuery tq;
tq.doit();
tq.query_text();
tq.display_map_text();
}
void
TextQuery::
retrieve_text()
{
string file_name;
cout << "please enter file name: ";
cin >> file_name;
ifstream infile( file_name.c_str(), ios::in );
if ( !infile ) {
cerr << "oops' unable to open file "
<< file_name << " -- bailing out!\n";
exit( -1 );
}
else cout << "\n";
lines_of_text = new vector<string,allocator>;
string textline;
while ( getline( infile, textline, '\n' ))
lines_of_text->push_back( textline );
}
void
TextQuery::
separate_words()
{
vector<string,allocator> *words =
new vector<string,allocator>;
vector<location,allocator> *locations =
new vector<location,allocator>;
for ( short line_pos = 0; line_pos < lines_of_text->size();
line_pos++ )
{
short word_pos = 0;
string textline = (*lines_of_text)[ line_pos ];
string::size_type eol = textline.1ength();
string::size_type pos = 0, prev_pos = 0;
while (( pos = textline.find_first_of( ' ', pos ))
!= string::npos )
{
words->push_back(
textline.substr( prev_pos, pos - prev_pos ));
locations->push_back(
make_pair( line_pos, word_pos ));
word_pos++; pos++; prev_pos = pos;
}
words->push_back(
textline.substr( prev_pos, pos - prev_pos ));
locations->push_back(make_pair(line_pos,word_pos));
}
text_locations = new text_loc( words, locations );
}
void
TextQuery::
filter_text()
{
if ( filt_elems.empty() )
return;
vector<string,allocator> *words = text_locations->first;
vector<string,allocator>::iterator iter = words->begin();
vector<string,allocator>::iterator iter_end = words->end();
while ( iter != iter_end )
{
string::size_type pos = 0;
while ((pos = (*iter).find_first_of(filt_elems, pos))
!= string::npos )
(*iter).erase(pos,l);
++iter;
}
}
void
TextQuery::
suffix_text()
{
vector<string,allocator> *words = text_locations->first;
vector<string,allocator>::iterator iter = words->begin();
vector<string,allocator>::iterator iter_end = words->end() ;
while ( iter != iter_end ) {
if ( (*iter).size() <= 3 )
{ iter++; continue; }
if ( (*iter)[ (*iter).size()-l ] == 's' )
suffix_s( *iter );
// дополнительная обработка суффиксов...
iter++;
}
}
void
TextQuery::
suffix_s( string &word )
{
string::size_type spos = 0;
string::size_type pos3 = word.size()-3;
// "ous", "ss", "is", "ius"
string suffixes( "oussisius" );
if ( ! word.compare( pos3, 3, suffixes, spos, 3 ) ||
! word.compare( pos3, 3, suffixes, spos+6, 3) ||
! word.compare( pos3+l, 2, suffixes, spos+2, 2 ) ||
! word.compare( pos3+l, 2, suffixes, spos+4, 2 ))
return;
string ies( "ies" );
if ( ! word.compare( pos3, 3, ies ))
{
word.replace( pos3, 3, 1, 'у' );
return;
}
string ses( "ses" );
if ( ! word.compare( pos3, 3, ses ))
{
word.erase( pos3+l, 2 );
return;
}
// удалим 's' в конце
word.erase( pos3+2 );
// удалим "'s"
if ( word[ pos3+l ] == '\'' )
word.erase( pos3+l );
}
void
TextQuery::
strip_caps()
{
vector<string,allocator> *words = text_locations->first;
vector<string,allocator>::iterator iter = words->begin();
vector<string,allocator>::iterator iter_end = words->end();
string caps( "ABCDEFGHI3KLMNOPQRSTUVWXYZ" );
while ( iter != iter_end ) {
string::size_type pos = 0;
while (( pos = (*iter).find_first_of( caps, pos ))
!= string::npos )
(*iter)[ pos ] = to1ower( (*iter)[pos] );
++iter;
}
}
void
TextQuery::
build_word_map()
{
word_map = new map<string,loc*,less<string>,allocator>;
typedef map<string,loc*,less<string>,allocator>::value_type
value_type;
typedef set<string,less<string>,allocator>::difference_type
diff_type;
set<string,less<string>,allocator> exclusion_set;
ifstream infile( "exclusion_set" );
if ( !infile )
{
static string default_excluded_words[25] = {
"the","and","but","that","then","are","been",
"can","can't","cannot","could","did","for",
"had","have","him","his","her","its"."into",
"were","which","when","with","would"
};
cerr <<
"warning! unable to open word exclusion file! -- "
<< "using default set\n";
copy( default_excluded_words,
default_excluded_words+25,
inserter(exclusion_set, exclusion_set.begin()));
}
else {
istream_iterator< string, diff_type >
input_set( infile ), eos;
copy( input_set, eos,
inserter( exclusion_set, exclusion_set.begin() ));
}
// пробежимся по всем словам, вставляя пары
vector<string,allocator> *text_words =
text_locations->first;
vector<location,allocator> *text.locs =
text_locations->second;
register int elem_cnt = text_words->size();
for ( int ix = 0; ix < elem_cnt; ++-ix )
{
string textword = ( *text_words )[ ix ];
if ( textword.size() < 3 ||
exclusion_set.count( textword ))
continue;
if ( ! word_map->count((*text_words)[ix] ))
{ // слово отсутствует, добавим:
loc *ploc = new vector<location,allocator>;
ploc->push_back( (*text_locs)[ix] );
word_map->
insert( value_type( (*text_words)[ix],ploc ));
}
else (*word_map) [(*text_words) [ix]]->
push_back( (*text_locs) [ix] );
}
}
void
TextQuery::
query_text()
{
string query_text;
do {
cout
<< "enter a word against which to search the text.\n"
<< "to quit, enter a single character ==> ";
cin >> query_text;
if ( query_text.size() < 2 ) break;
string caps( "ABCDEFGHIJKLMNOPQRSTUVWXYZ" );
string::size_type pos = 0;
while (( pos = query_text.find_first_of( caps, pos ))
!= string::npos )
query_text[ pos ] = to1ower( query_text[pos] );
// query_text должно быть введено
if ( !word_map->count( query_text )) {
cout << "\nSorry. There are no entries for "
<< query_text << ".\n\n";
continue;
}
loc *ploc = (*word_map) [ query_text ];
set<short,less<short>,allocator> occurrence_1i nes;
loc::iterator liter = ploc->begin(),
liter_end = ploc->end();
while ( liter != liter_end ) {
occurrence_lines.1nsert(
occurrence_lines.end(), (*liter).first);
++liter;
}
register int size = occurrence_lines.size();
cout << "\n" << query_text
<< " occurs " << size
<< (size == 1 ? " time:" : " times:")
<< "\n\n";
set<short,less<short>,allocator>::iterator
it=occurrence_lines.begin();
for ( ; it != occurrence_"lines.end(); ++it ) {
int line = *it;
cout << "\t( line "
// будем нумеровать строки с 1,
// как это принято везде
<< line + 1 << " ) "
<< (*lines_of_text)[line] << endl;
}
cout << endl;
}
while ( ! query_text.empty() );
cout << "Ok, bye!\n";
}
void
TextQuery::
display_map_text()
{
typedef map<string,loc*, less<string>, allocator> map_text;
map_text::iterator iter = word_map->begin(),
iter_end = word_map->end();
while ( iter != iter_end ) {
cout << "word: " << (*iter).first << " (";
int loc_cnt = 0;
loc *text_locs = (*iter).second;
loc::iterator liter = text_locs->begin(),
liter_end = text_locs->end();
while ( liter != liter_end )
{
if ( loc_cnt )
cout << ",";
else ++loc_cnt;
cout << "(" << (*liter).first
<< "," << (*liter).second << ")";
++"liter;
}
cout << ")\n";
++iter;
}
cout << endl;
}
void
TextQuery::
disp1ay_text_locations()
{
vector<string,allocator> *text_words =
text_locations->first;
vector<location,allocator> *text_locs =
text_locations->second;
register int elem_cnt = text_words->size();
if ( elem_cnt != text_locs->size() )
{
cerr
<< "oops! internal error: word and position vectors "
<< "are of unequal size\n"
<< "words: " << elem_cnt << " "
<< "locs: " << text_locs->size()
<< " -- bailing out!\n";
exit( -2 );
}
for ( int ix=0; ix < elem_cnt; ix++ )
{
cout << "word: " << (*text_words)[ ix ] << "\t"
<< "location: ("
<< (*text_locs)[ix].first << ","
<< (*text.locs)[ix].second << ")"
<< "\n";
}
cout << endl;
| }
Упражнение 6.25
Объясните, почему нам потребовался специальный класс inserter для заполнения набора стоп-слов (это упоминается в разделе 6.13.1, а детально рассматривается в 12.4.1).
| set<string> exclusion_set;
ifstream infile( "exclusion_set" );
copy( default_excluded_words, default_excluded_words+25,
| inserter(exclusion_set, exclusion_set.begin() ));
Упражнение 6.26
Первоначальная реализация поисковой системы отражает процедурный подход: набор глобальных функций оперирует набором независимых структур данных. Окончательный вариант представляет собой альтернативный подход, когда мы инкапсулируем функции и данные в класс TextQuery. Сравните оба способа. Каковы недостатки и преимущества каждого?
Упражнение 6.27
В данной версии программы имя файла с текстом вводится по запросу. Более удобно было бы задавать его как параметр командной строки; в главе 7 мы покажем, как это делается. Какие еще параметры командной строки желательно реализовать?
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|
