Обычной проблемой анализа текстов является определение частоты и расположения слов в документе. Эта информация запоминается в конкордансе, где различные слова перечислены в алфавитном порядке и каждое слово снабжено ссылками на строки текста, в которых оно встречается. Рассмотрим следующую цитату.
Peter Piper picked a peck of pickled peppers. A peck of pickled
peppers Peter Piper picked. If Peter Piper picked a peck of
pickled peppers, where is the peck that Peter Piper picked?
Слово "piper" встречается здесь 4 раза в строках 1, 2 и 3. Слово "pickled" встречается 3 раза в строках 1 и 3.
В этой задаче создается конкорданс для текстового файла следующим образом:
Вход: Открыть документ как текстовый файл и ввести текст по словам, отслеживая текущую строку.
Действие: Определить запись, которая состоит из слова, счетчика появлений и списка номеров строк, содержащих это слово. При первой встрече некоторого слова в тексте создать запись и вставить ее в дерево. Если слово уже есть в дереве, обновить частоту его появления и список номеров строк.
Выход: После ввода файла распечатать слова в алфавитном порядке вместе со счетчиками частоты и упорядоченными списками строк, где встречается каждое слово.
Структуры данных
Данными каждого узла является объект Word, содержащий символьную цепочку, счетчик частоты появлений и связанный список номеров строк текста. Объект Word содержит также номер строки, где данное слово встретилось последний раз. Это гарантирует, что мы сможем обработать несколько случаев появлений слова в строке и только один раз занести номер этой строки в список.
Функции-члены класса Word перегружают операторы отношения "==" и "<" и стандартные операторы потокового ввода/вывода.
class Word
{
private:
// wordText - слово из текста; count - его частота
String wordText;
int count;
// счетчик строк разделяется всеми объектами Word
static int lineno;
// номер последней строки, где встретилось данное слово.
// используется для того, чтобы знать, когда вставлять
Для каждого слова конструктор устанавливает начальное значение частоты в 0 и номер последней строки в -1. Перегружаемые операторы отношения "<" и "==" необходимы для операций вставки и поиска и реализуются путем сравнения строк двух объектов, содержащих слова.
В этом классе объявляется скрытая переменная lineno, доступная только элементам класса и друзьям. Word::lineno является статическим членом класса, и поэтому доступна всем экземплярам класса. И это правильно, так как всем этим объектам нужен доступ к номеру текущей строки входного файла. Статические элементы данных более предпочтительны, чем глобальные переменные.
Оператор ввода ">>".
Оператор ввода считывает данные из потока по одному слову за раз. Слово должно начинаться с буквы, за которой необязательно идет последовательность букв или цифр. Ввод слова начинается с чтения и выбрасывания всех небуквенных символов. Это гарантирует, что все межсловные промежутки и знаки пунктуации будут пропущены. Процесс ввода прекращается по достижении конца файла. Если встречается символ конца строки, происходит увеличение переменной lineno на единицу.
// пропустить все предшествующие пробелы и небуквенные символы
while (istr.get(c) && !isalpha(c))
// если встретился конец строки, увеличить счетчик строк текста
if (c == '\n')
w.lineno++;
Когда распознается начало слова, оператор ">>" накапливает символы, читая буквы и цифры до тех пор, пока не встретится не алфавитно-цифровой символ. Буквы слова преобразуются в строчные и запоминаются в локальной переменной wd. Это позволяет сделать наш конкорданс нечувствительным к регистру букв, из которых состоит слово. Если после очередного слова следует символ конца строки, он снова помещается в поток и обнаруживается во время ввода следующего слова. Функция завершается копированием переменной wd в wordText, сбросом счетчика count и присвоением переменной lastLineNo значения lineno.
// если не конец файла, ввести слово
if (!istr.eof())
{
// преобразовать первую букву в строчную, занести ее в wd
c = tolower(c);
wd[i++] = c;
// последовательно считывать буквы или цифры,
//преобразуя их в строчные
while (istr.get(c) && (isalpha(c) || isdigit(c)))
wd[i++] = tolower(c);
// завершить строку нулем
wd[i] = '\0';
// если после текущего слова встретился конец строки,
// возвратить его обратно в поток для следующего слова
if (c == '\n')
istr.putback(c);
// заключительные установки
w.wordText = wd;
w.count = 0;
w.lastLineNo = w.lineno;
}
Функция CountWord
После считывания слова из текста вызывается функция CountWord, которая обновляет значение частоты и список номеров строк. В начале функции значение счетчика count увеличивается на единицу. Если count = 1, то слово — новый элемент дерева, и номер строки, где впервые встретилось это слово, добавляется в список. Если слово уже есть в списке, то проверяется, изменился ли номер строки с момента последнего появления данного слова. Если да, то номер текущей строки заносится в список и используется для обновления lastLineNo.
// записать случай вхождения слова
void Word::CountWord (void)
{
// увеличить частоту вхождения слова
count++;
// если это слово встретилось впервые или на новой строке,
// вставить его в список и присвоить переменной lastLineNo
// номер текущей строки.
if (count == 1 || lastLineNo != lineno)
{
lineNumbers.InsertRear(lineno);
lastLineNo = lineno;
}
}
Оператор вывода "<<"
Оператор потокового вывода распечатывает слово и частоту, вслед за которыми идет упорядоченный список номеров строк, где это слово встречается.
В программе определено бинарное дерево поиска concordTree, в котором хранятся объекты класса Word. После открытия текстового файла concord.txt оператор ввода потока считывает слова, пока не встретится конец файла. Каждое слово либо включается в дерево, либо используется для обновления информации о себе, если оно уже встречалось ранее. После того как все слова обработаны, выполняется симметричное прохождение, в процессе которого слова распечатываются в алфавитном порядке.
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include "word.h" // класс Word
#include "bstree.h" // класс BinSTree
#include "treescan.h" // метод Inorder
// используется функцией Inorder
void PrintWord(Word& w)
{
cout << w;
}
void main(void)
{
// объявить дерево объектов Word; читать из потока fin
BinSTree<Word> concordTree;
ifstream fin;
Word w;
// открыть файл concord.txt
fin.open("concord.txt", ios::in | ios::nocreate);
if (!fin)
{
cerr << "Не могу открыть concord.txt" << endl;
exit(1);
}
// читать объекты Word из потока fin,
//пока не встретится конец файла
while(fin >> w)
{
// найти w на дереве
if (concordTree.Find(w) == 0)
{
// w нет на дереве.
//Обновить частоту слова и включить его в дерево
w.CountWord();
concordTree.Insert(w);
}
else
{
// w на дереве.
//Обновить информацию о слове
w.CountWord();
concordTree.Update(w);
}
}
// распечатать дерево в алфавитном порядке
Inorder(concordTree.GetRoot(), Print-Word);
}
Файл concord.txt выглядит так:
Peter Piper picked a peck of pickled peppers. A peck of pickled
peppers Peter Piper picked. If Peter Piper picked a peck of
pickled peppers, where is the peck that Peter Piper picked?
Если выполнить программу с файлом concord.txt в качестве параметра, результаты будут выглядеть так:
