C++ для начинающих

Элемент контейнера set содержит только ключ, поэтому set эффективно реализует операцию проверки его существования. Этот контейнер можно применить, например, при реализации системы текстового поиска для хранения списка так называемых стоп-слов – слов, не используемых при поиске, таких, как и, или, не, так и тому подобных. Программа обработки текста считывает каждое слово и проверяет, есть ли оно в указанном списке. Если нет, то слово добавляется в базу данных.

В контейнерах map и set не может быть дубликатов – повторяющихся ключей. Для поддержки дубликатов существуют контейнеры multimap и multiset. Например, multimap можно использовать при реализации такого телефонного справочника, в котором содержится несколько номеров одного абонента.

В последующих разделах мы детально рассмотрим контейнерные типы и разработаем небольшую программу текстового поиска.

6.1. Система текстового поиска

В систему текстового поиска входят текстовый файл, указанный пользователем, и средство для задания запроса, состоящего из слов и, возможно, логических операторов.

Если одно или несколько слов запроса найдены, печатается количество их вхождений. По желанию пользователя печатаются предложения, содержащие найденные слова. Например, если нужно найти все вхождения словосочетаний Civil War и Civil Rights, запрос может выглядеть таким образом :

Civil ( War || Rights )

Результат запроса:

Civil: 12 вхождений

War: 48 вхождений

Rights: 1 вхождение

Civil War: 1 вхождение

Civil Rights: 1 вхождение

(8) Civility, of course, is not to be confused with

Civil Rights, nor should it lead to Civil War

Здесь (8) представляет собой номер предложения в тексте. Наша система должна печатать фразы, содержащие найденные слова, в порядке возрастания их номеров (т.е. предложение номер 7 будет напечатано раньше предложения номер 9), не повторяя одну и ту же несколько раз.

Наша программа должна уметь:

* запросить имя текстового файла, а затем открыть и прочитать этот файл;

организовать внутреннее представление этого файла так, чтобы впоследствии соотнести

* найденное слово с предложением, в котором оно встретилось, и определить порядковый номер этого слова;

понимать определенный язык запросов. В нашем случае он включает следующие операторы:

два слова непосредственно следуют одно за другим в строке

|| одно или оба слова встречаются в строке

! слово не встречается в строке

() группировка слов в запросе

*

Используя этот язык, можно написать:

Lincoln

чтобы найти все предложения, включающие слово Lincoln, или

! Lincoln

для поиска фраз, не содержащих такого слова, или же

( Abe || Abraham ) Lincoln

для поиска тех предложений, где есть словосочетания Abe Lincoln или Abraham Lincoln.

Представим две версии нашей системы. В этой главе мы решим проблему чтения и хранения текстового файла в отображении, где ключом является слово, а значением – номер строки и позиции в строке. Мы обеспечим поиск по одному слову. (В главе 17 мы реализуем полную систему поиска, поддерживающую все указанные выше операторы языка запросов с помощью класса Query.) .

Возьмем шесть строчек из неопубликованного детского рассказа Стена Липпмана (Stan Lippman) :

Рис. 2.

Alice Emma has long flowing red hair. Her Daddy says when the wind blows through her hair, it looks almost alive, like a fiery bird in flight. A beautiful fiery bird, he tells her, magical but untamed. "Daddy, shush, there is no such thing," she tells him, at the same time wanting him to tell her more. Shyly, she asks, "I mean. Daddy, is there?"

После считывания текста его внутреннее представление выглядит так (процесс считывания включает ввод очередной строки, разбиение ее на слова, исключение знаков препинания, замену прописных букв строчными, минимальная поддержка работы с суффиксами и исключение таких слов, как and, a, the):

alice ((0,0))

alive ((1,10))

almost ((1,9))

ask ((5,2))

beautiful ((2,7))

bird ((2,3),(2,9))

blow ((1,3))

daddy ((0,8),(3,3),(5,5))

emma ((0,1))

fiery ((2,2),(2,8))

flight ((2,5))

flowing ((0,4))

hair ((0,6),(1,6))