Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Построение набора стоп-слов
Отображение состоит из пар ключ/значение. Множество (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 не соответствовала текущему стандарту. Шаблоны не поддерживали значения аргументов по умолчанию. Возможно, вам придется изменить кое-что в этой программе, чтобы она компилировалась в вашей системе.
} Упражнение 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 мы покажем, как это делается. Какие еще параметры командной строки желательно реализовать? |
Последнее изменение этой страницы: 2019-04-09; Просмотров: 290; Нарушение авторского права страницы