6.7. Читаем текстовый файл

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

Как получить одну строку текста? Стандартная библиотека предоставляет для этого

istream&

функцию getline():

getline( istream &is, string str, char delimiter );

getline()берет из входного потока все символы, включая пробелы, и помещает их в объект типа string, до тех пор пока не встретится символ delimiter, не будет достигнут конец файла или количество полученных символов не станет равным величине, возвращаемой функцией-членом max_size()класса string.

Мы будем помещать каждую такую строку в вектор.

Мы вынесли код, читающий файл, в функцию, названную retrieve_text(). В объекте типа pair дополнительно сохраняется размер и номер самой длинной строки. (Полный текст программы приводится в разделе 6.14.)

Вот реализация функции ввода файла:15

15 Программа компилировалась компилятором, не поддерживающим значений параметров по умолчанию шаблонов. Поэтому нам пришлось явно указать аллокатор:

vector<string,allocator> *lines_of_text;

Для компилятора, полностью соответствующего стандарту С++, достаточно отметить тип элементов:

vector<string> *lines_of_text;

// возвращаемое значение - указатель на строковый вектор vector<string,allocator>*

retrieve_text()

{

string file_name;

cout << "please enter file name: "; cin >> file_name;

// откроем файл для ввода ...

ifstream 1nfile( file_name.c_str(), ios::in ); if ( ! infile ) {

cerr << "oops! unable to open file "

<< file_name << " -- bailing out!\n"; exit( -1 );

}

else cout << '\n';

vector<string, allocator> *1ines_of_text = new vector<string, allocator>;

string textime;

typedef pair<string::size_type, int> stats; stats maxline;

int linenum = 0;

while ( getline( infile, textline, '\n' )) { cout << "line read: " << textline << '\n';

if ( maxline.first < textline.size() ) { maxline.first = textline.size() ; maxline.second = linenum;

}

1ines_of_text->push_back( textline ); linenum++;

}

return lines_of_text;

}

Вот как выглядит вывод программы (размер страницы книги недостаточен, чтобы расположить напечатанные строки во всю длину, поэтому мы сделали в тексте отступы, показывающие, где реально заканчивалась строка):

please enter file name: a1ice_emma

line read: Alice Emma has long flowing red hair. Her Daddy says line read: when the wind blows through her hair, it looks

almost alive,

line read: like a fiery bird in flight. A beautiful fiery bird, he tells her,

line read: magical but untamed. "Daddy, shush, there is no such thing, "

line read: she tells him, at the same time wanting him to tell her more.

line read: Shyly, she asks, "I mean. Daddy, is there?"

number of lines: 6 maximum length: 66

longest line: like a fiery bird in flight. A beautiful fiery bird, he tells her,

После того как все строки текста сохранены, нужно разбить их на слова. Сначала мы отбросим знаки препинания. Например, возьмем строку из части “Anna Livia Plurrabelle”

романа “Finnegans Wake”.

"For every tale there's a telling, and that's the he and she of it."

В приведенном фрагменте есть следующие знаки препинания:

"For

there's

telling,

that's

it."

А хотелось бы получить:

For there telling that

it

Можно возразить, что

there's

должно превратиться в

there is

но мы-то движемся в другом направлении: следующий шаг – это отбрасывание семантически нейтральных слов, таких, как is, that, and, it и т.д. Так что для данной строчки из “Finnegans Wake” только два слова являются значимыми: tale и telling, и только по этим словам будет выполняться поиск. (Мы реализуем набор стоп-слов с помощью контейнерного типа set, который подробно рассматривается в следующем разделе.)

После удаления знаков препинания нам необходимо превратить все прописные буквы в строчные, чтобы избежать проблем с поиском в таких, например, строках:

Home is where the heart is.

A home is where they have to let you in.

Несомненно, запрос слова home должен найти обе строки.

Мы должны также обеспечить минимальную поддержку учета словоформ: отбрасывать окончания слов, чтобы слова dog и dogs, love, loving и loved рассматривались системой как одинаковые.

В следующем разделе мы вернемся к описанию стандартного класса string и рассмотрим многочисленные операции над строками, которые он поддерживает, в контексте дальнейшей разработки нашей поисковой системы.

6.8. Выделяем слова в строке

Нашей первой задачей является разбиение строки на слова. Мы будем вычленять слова, находя разделяющие их пробелы с помощью функции find(). Например, в строке

Alice Emma has long flowing red hair.

насчитывается шесть пробелов, следовательно, эта строка содержит семь слов.

Класс string имеет несколько функций поиска. find() – наиболее простая из них. Она ищет образец, заданный как параметр, и возвращает позицию его первого символа в строке, если он найден, или специальное значение string::npos в противном случае.

#include <string> #include <iostream>

int main() {

string name( "AnnaBelle" ); int pos = name.find( "Anna" ); if ( pos == string::npos )

cout << "Anna не найдено!\n";

else cout << "Anna найдено в позиции: " << pos << endl;

Например:

}

Хотя позиция подстроки почти всегда имеет тип int, более правильное и переносимое объявление типа результата, возвращаемого find(), таково:

string::size_type

Например:

string::size_type pos = name.find( "Anna" );

Функция find() делает не совсем то, что нам надо. Требуемая функциональность обеспечивается функцией find_first_of(), которая возвращает позицию первого символа, соответствующего одному из заданных в строке-параметре. Вот как найти первый символ, являющийся цифрой:

#include <string> #include <iostream>

int main() {

string numerics( "0123456789" ); string name( "r2d2" );

string:: size_type pos = name.find_first_of( numerics ); cout << "найдена цифра в позиции: "

<< pos << "\tэлемент равен " << name[pos] << endl;

}

В этом примере pos получает значение 1 (напоминаем, что символы строки нумеруются с

0).

Но нам нужно найти все вхождения символа, а не только первое. Такая возможность реализуется передачей функции find_first_of() второго параметра, указывающего позицию, с которой начать поиск. Изменим предыдущий пример. Можете ли вы сказать,

#include <string> #include <iostream> int main() {

string numerics( "0123456789" ); string name( "r2d2" );

string::size_type pos = 0;

// где-то здесь ошибка!

while (( pos = name.find_first_of( numerics, pos )) != string::npos )

что в нем все еще не вполне удовлетворительно?

}

В начале цикла pos равно 0, поэтому поиск идет с начала строки. Первое вхождение обнаружено в позиции 1. Поскольку найденное значение не совпадает с string::npos, выполнение цикла продолжается. Для второго вызова find_first_of()значение pos равно 1. Поиск начнется с 1-й позиции. Вот ошибка! Функция find_first_of() снова найдет цифру в первой позиции, и снова, и снова... Получился бесконечный цикл. Нам необходимо увеличивать pos на 1 в конце каждой итерации:

// исправленная версия цикла

while (( pos = name.find_first_of( numerics, pos )) != string::npos )

{

<<name[pos] << endl;

//сдвинуться на 1 символ

++pos;

}

Чтобы найти все пустые символы (к которым, помимо пробела, относятся символы табуляции и перевода строки), нужно заменить строку numerics в этом примере строкой, содержащей все эти символы. Если же мы уверены, что используется только символ

// фрагмент программы

while (( pos = textline.find_first_of( ' ', pos )) != string::npos )

пробела и никаких других, то можем явно задать его в качестве параметра функции:

//...

//фрагмент программы

//pos: позиция на 1 большая конца слова

//prev_pos: позиция начала слова

string::size_type pos = 0, prev_pos = 0;

while (( pos = textline.find_first_of( ' ', pos )) != string::npos )

{

//...

//запомнить позицию начала слова prev_pos = ++pos;

Чтобы узнать длину слова, введем еще одну переменную:

}

На каждой итерации prev_pos указывает позицию начала слова, а pos – позицию следующего символа после его конца. Соответственно, длина слова равна:

pos - prev_pos; // длина слова

После того как мы выделили слово, необходимо поместить его в строковый вектор. Это можно сделать, копируя в цикле символы из textline с позиции prev_pos до pos -1. Функция substr() сделает это за нас:

// фрагмент программы vector<string> words;

while (( pos = textline.find_first_of( ' ', pos )) != string::npos )

{

words.push_back( textline.substr( prev_pos, pos-prev_pos));

prev_pos = ++pos;

}

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

В нашей реализации допущена ошибка: последнее слово не будет помещено в контейнер. Почему? Возьмем строку:

seaspawn and seawrack

После каждого из первых двух слов поставлен пробел. Два вызова функции find_first_of() вернут позиции этих пробелов. Третий же вызов вернет string::npos, и цикл закончится. Таким образом, последнее слово останется необработанным.

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

typedef pair<short,short> location; typedef vector<location> loc; typedef vector<string> text; typedef pair<text* ,loc*> text_loc;

text_loc*

separate_words( const vector<string> *text_file )

{

//words: содержит набор слов

//locations: содержит информацию о строке и позиции

//каждого слова

short line_pos = 0; // текущий номер строки // iterate through each line of text

for ( ; line_pos < text_file->size(); ++line_pos )

//textline: обрабатываемая строка

//word_pos: позиция в строке

short word_pos = 0;

string textline = (*text_file) [ line_pos ];

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; prev_pos = ++pos;

}

// обработаем последнее слово words->push_back(

textline.substr( prev_pos, pos - prev_pos ));

locations->push_back(

make_pair( line_pos, word_pos ));

}

return new text_loc( words, locations );

}

int main()

{

vector<string> *text_file = retrieve_text();

text_loc *text_locations = separate_words( text_file ); // ...

Теперь функция main()выглядит следующим образом:

}

Вот часть распечатки, выданной тестовой версией separate_words():

textline: Alice Emma has long flowing red hair. Her Daddy says

eol: 52 pos: 5 line: 0 word: 0 substring: Alice eol: 52 pos: 10 line: 0 word: 1 substring: Emma eol: 52 pos: 14 line: 0 word: 2 substring: has eol: 52 pos: 19 line: 0 word: 3 substring: long eol: 52 pos: 27 line: 0 word: 4 substring: flowing eol: 52 pos: 31 line: 0 word: 5 substring: red eol: 52 pos: 37 line: 0 word: 6 substring: hair. eol: 52 pos: 41 line: 0 word: 7 substring: Her eol: 52 pos: 47 line: 0 word: 8 substring: Daddy last word on line substring: says

...

textline: magical but untamed. "Daddy, shush, there is no such thing,"

eol: 60 pos: 7 line: 3 word: 0 substring: magical eol: 60 pos: 11 line: 3 word: 1 substring: but eol: 60 pos: 20 line: 3 word: 2 substring: untamed eol: 60 pos: 28 line: 3 word: 3 substring: "Daddy, eol: 60 pos: 35 line: 3 word: 4 substring: shush, eol: 60 pos: 41 line: 3 word: 5 substring: there eol: 60 pos: 44 line: 3 word: 6 substring: is

eol: 60 pos: 47 line: 3 word: 7 substring: no eol: 60 pos: 52 line: 3 word: 8 substring: such last word on line substring: thing,":

...

textline: Shy1y, she asks, "I mean, Daddy: is there?"

eol: 43 pos: 6 line: 5 word: 0 substring: Shyly, eol: 43 pos: 10 line: 5 word: 1 substring: she eol: 43 pos: 16 line: 5 word: 2 substring: asks, eol: 43 pos: 19 line: 5 word: 3 substring: "I eol: 43 pos: 25 line: 5 word: 4 substring: mean, eol: 43 pos: 32 line: 5 word: 5 substring: Daddy, eol: 43 pos: 35 line: 5 word: 6 substring: is last word on line substring: there?":

Прежде чем продолжить реализацию поисковой системы, вкратце рассмотрим оставшиеся функции-члены класса string, предназначенные для поиска. Функция

string river( "Mississippi" );

string::size_type first_pos = river.find( "is" );

rfind() ищет последнее, т.е. самое правое, вхождение указанной подстроки: string::size_type 1ast_pos = river.rfind( "is" );

find() вернет 1, указывая позицию первого вхождения подстроки "is", а rfind() – 4 (позиция последнего вхождения "is").

find_first_not_of() ищет первый символ, не содержащийся в строке, переданной как параметр. Например, чтобы найти первый символ, не являющийся цифрой, можно написать: