<< Пред.           стр. 26 (из 121)           След. >>

Список литературы по разделу

 typedef pair text_loc;
 
 text_loc*
 separate_words( const vector *text_file )
 {
  // words: содержит набор слов
  // locations: содержит информацию о строке и позиции
  // каждого слова
  vector *words = new vector;
  vector * locations = new vector;
 
  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 );
 }
 Теперь функция main()выглядит следующим образом:
 int main()
 {
  vector *text_file = retrieve_text();
  text_loc *text_locations = separate_words( text_file );
  // ...
 }
 Вот часть распечатки, выданной тестовой версией 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, предназначенные для поиска. Функция rfind() ищет последнее, т.е. самое правое, вхождение указанной подстроки:
 string river( "Mississippi" );
 string::size_type first_pos = river.find( "is" );
 string::size_type 1ast_pos = river.rfind( "is" );
 find() вернет 1, указывая позицию первого вхождения подстроки "is", а rfind() – 4 (позиция последнего вхождения "is").
 find_first_not_of() ищет первый символ, не содержащийся в строке, переданной как параметр. Например, чтобы найти первый символ, не являющийся цифрой, можно написать:
 string elems( "0123456789" );
 string dept_code( "03714p3" );
 
 // возвращается позиция символа 'p'
 string::size_type pos = dept_code.find_first_not_of(elems) ;
 find_last_of() ищет последнее вхождение одного из указанных символов. find_last_not_of() – последний символ, не совпадающий ни с одним из заданных. Все эти функции имеют второй необязательный параметр – позицию в исходной строке, с которой начинается поиск.
 Упражнение 6.13
 Напишите программу, которая ищет в строке
 
 "ab2c3d7R4E6"
 
 цифры, а затем буквы, используя сначала find_first_of(), а потом find_first_not_of().
 Упражнение 6.14
 Напишите программу, которая подсчитывает все слова и определяет самое длинное и самое короткое из них в строке sentence:
 string linel = "We were her pride of 10 she named us --";
 string line2 = "Benjamin, Phoenix, the Prodigal"
 string line3 = "and perspicacious pacific Suzanne";
 
 string sentence = linel + line2 + line3;
 Если несколько слов имеют длину, равную максимальной или минимальной, учтите их все.
 6.9. Обрабатываем знаки препинания
 После того как мы разбили каждую строку на слова, необходимо избавиться от знаков препинания. Пока из строки
 
 magical but untamed. "Daddy, shush, there is no such thing,"
 
 у нас получился такой набор слов:
 
 magical
 but
 untamed.
 "Daddy,
 shush,
 there
 is
 no
 such
 thing,"
 
 Как нам теперь удалить ненужные знаки препинания? Для начала определим строку, содержащую все символы, которые мы хотим удалить:
 string filt_elems( "\",.;:!?)(\\/" );
 (Обратная косая черта указывает на то, что следующий за ней символ должен в данном контексте восприниматься буквально, а не как специальная величина. Так, \" обозначает символ двойной кавычки, а не конец строки, а \\ – символ обратной косой черты.)
 Теперь можно применить функцию-член find_first_of() для поиска всех вхождений нежелательных символов:
 while (( pos = word.find_first_of( filt_elems, pos ))
  != string::npos )
 Найденный символ удаляется с помощью функции-члена erase():
 word.erase(pos,1);
 Первый аргумент этой функции означает позицию подстроки, а второй – ее длину. Мы удаляем один символ, находящийся в позиции pos. Второй аргумент является необязательным; если его опустить, будут удалены все символы от pos до конца строки.
 Вот полный текст функции filter_text(). Она имеет два параметра: указатель на вектор строк, содержащий текст, и строку с символами, которые нужно убрать.
 void
 filter_text( vector *words, string filter )
 {
  vector::iterator iter = words->begin();
  vector::iterator iter_end = words->end();
 
  // Если filter не задан, зададим его сами
  if ( ! filter.size() )
  filter.insert( 0, "\".," );
 
  while ( iter != iter_end ) {
  string::size_type pos = 0;
 
  // удалим каждый найденный элемент
  while (( pos = (*iter).find_first_of( filter, pos ))
  != string::npos )
  (*iter).erase(pos,1);
  iter++;
  }
 }
 Почему мы не увеличиваем значение pos на каждой итерации? Что было бы, если бы мы написали:
 while (( pos = (*iter).find_first_of( filter, pos ))
  != string::npos )
 {
  (*iter).erase(pos,1);
  ++ pos; // неправильно...
 }
 Возьмем строку
 
 thing,"
 
 На первой итерации pos получит значение 5 , т.е. позиции, в которой находится запятая. После удаления запятой строка примет вид
 
 thing"
 
 Теперь в 5-й позиции стоит двойная кавычка. Если мы увеличим значение pos, то пропустим этот символ.
 Так мы будем вызывать функцию filter_text():
 string filt_elems( "\",.;:!?)(\\/" );
 filter_text( text_locations->first, filt_elems );
 А вот часть распечатки, сделанной тестовой версией filter_text():
 
 filter_text: untamed.
 found! : pos: 7.
 after: untamed
 
 filter_text: "Daddy,
 found! : pos: 0.
 after: Daddy,
 found! : pos: 5.
 after: Daddy
 
 filter_text: thing,"
 found! : pos: 5.
 after: thing"
 found! : pos: 5.
 after: thing
 
 filter_text: "I
 found! : pos: 0.
 after: I
 
 filter_text: Daddy,
 found! : pos: 5.
 after: Daddy
 
 filter_text: there?"
 found! : pos: 5.
 after: there"
 found! : pos: 5.
 after: there
 
 Упражнение 6.15
 Напишите программу, которая удаляет все символы, кроме STL из строки:
 
 "/.+(STL).$1/"
 
 используя сначала erase(pos,count), а затем erase(iter,iter).
 Упражнение 6.16
 Напишите программу, которая с помощью разных функций вставки из строк
 string sentence( "kind of" );
 string s1 ( "whistle" )
 string s2 ( "pixie" )
 составит предложение
 
 "A whistling-dixie kind of walk"
 
 6.10. Приводим слова к стандартной форме
 Одной из проблем при разработке текстовых поисковых систем является необходимость распознавать слова в различных словоформах, такие, как cry, cries и cried, baby и babies, и, что гораздо проще, написанные заглавными и строчными буквами, например home и Home. Первая задача, распознавание словоформ, слишком сложна, поэтому мы приведем здесь ее заведомо неполное решение. Сначала заменим все прописные буквы строчными:
 void
 strip_caps( vector *words )
 {
  vector::iterator iter=words->begin() ;
  vector::iterator iter_end=words->end() ;
 
  string caps( "ABCDEFGHIJKLMNOPQRSTUVWXYZ" );
 
  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;
  }
 }
 Функция
 to1ower( (*iter)[pos] );
 входит в стандартную библиотеку С. Она заменяет прописную букву соответствующей ей строчной. Для использования tolower() необходимо включить заголовочный файл:
 #include
 (В этом файле объявлены и другие функции, такие, как isalpha(), isdigit(), ispunct(), isspace(), toupper(). Полное описание этих функций см. [PLAUGER92]. Стандартная библиотека С++ включает класс ctype, который инкапсулирует всю функциональность стандартной библиотеки Си, а также набор функций, не являющихся членами, например toupper(), tolower() и т.д. Для их использования нужно включить заголовочный файл
 #include
 Однако наша реализация компилятора еще не поддерживала класс ctype, и нам пришлось использовать стандартную библиотеку Си.)
 Проблема словоформ слишком сложна для того, чтобы пытаться решить ее в общем виде. Но даже самый примитивный вариант способен значительно улучшить работу нашей поисковой системы. Все, что мы сделаем в данном направлении, – удалим букву 's' на концах слов:
 void suffix_text( vector *words )
 {
  vector::iterator
  iter = words->begin(),
  iter_end = words->end();
 
  while ( iter != iter_end ) {
  // оставим слова короче трех букв как есть
  if ( (*iter).size() <= 3 )
  { ++iter; continue; }
  if ( (*iter)[ (*iter).size()-1 ] == 's' )
  suffix_s( *iter );
 
  // здесь мы могли бы обработать суффиксы
  // ed, ing, 1y
 
  ++iter;
  }
 }
 Слова из трех и менее букв мы пропускаем. Это позволяет оставить без изменения, например, has, its, is и т.д., однако слова tv и tvs мы не сможем распознать как одинаковые.
 Если слово кончается на "ies", как babies и cries, необходимо заменить "ies" на "y":
 string::size_type pos() = word.size()-3;
 string ies( "ies" );
 if ( ! word.compare( pos3, 3, ies )) {
  word.replace( pos3, 3, 1, 'у' );
  return;
 }
 compare() возвращает 0, если две строки равны. Первый аргумент, pos3, обозначает начальную позицию, второй – длину сравниваемой подстроки (в нашем случае 3). Третий аргумент, ies, – строка-эталон. (На самом деле существует шесть вариантов функции compare(). Остальные мы покажем в следующем разделе.)
 replace() заменяет подстроку набором символов. В данном случае мы заменяем подстроку "ies" длиной в 3 символа единичным символом 'y'. (Имеется десять перегруженных вариантов функции replace(). В следующем разделе мы коснемся остальных вариантов.)
 Если слово заканчивается на "ses", как promises или purposes, нужно удалить суффикс "es":
 string ses( "ses" );
 if ( ! word.compare( pos3, 3, ses )) {
  word.erase( pos3+l, 2 );
  return;
 }
 Если слово кончается на "ous", как oblivious, fulvous, cretaceous, или на "is", как genesis, mimesis, hepatitis, мы не будем изменять его. (Наша система несовершенна. Например, в слове kiwis надо убрать последнее 's'.) Пропустим и слова, оканчивающиеся на "ius" (genius) или на "ss" (hiss, lateness, less). Нам поможет вторая форма функции compare():

<< Пред.           стр. 26 (из 121)           След. >>

Список литературы по разделу