Практическая задача: конкорданс

Обычной проблемой анализа текстов является определение частоты и расположения слов в документе. Эта информация запоминается в конкордансе, где различные слова перечислены в алфавитном порядке и каждое слово снабжено ссылками на строки текста, в которых оно встречается. Рассмотрим следующую цитату.

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;

// номер последней строки, где встретилось данное слово.

// используется для того, чтобы знать, когда вставлять

// номер строки в lineNumbers

int lastLineNo;

LinkedList<int> lineNumbers;

public:

// конструктор

Word(void);

// открытые операции класса

void CountWord (void);

String& Key(void);

// операторы сравнения, используемые классом BinSTree

int operator== (const Word& w) const;

int operator< (const Word& w) const;

// операторы потокового ввода/вывода

friend istream& operator >> (istream& istr, Word& w);

friend ostream& operator << (ostream& ostr, Word& w);

};

Реализация класса Word

Для каждого слова конструктор устанавливает начальное значение частоты в 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;

}

}

Оператор вывода "<<"

Оператор потокового вывода распечатывает слово и частоту, вслед за которыми идет упорядоченный список номеров строк, где это слово встречается.

<слово>......................<частота>: n1, n2, n3, ...

// вывести объект класса Word в поток

ostream& operator<< (ostream& ostr, Word& w)

{

// вывести слово

ostr << w.wordText;

// вывести выровненный вправо счетчик частоты.

// заполнить промежуток точками.

ostr.fill('.');

ostr << setw(25-w.wordText.Length()) << w.count << ": ";

// снова назначить пробел символом-заполнителем

ostr.fill(' ');

// пройтись по списку и распечатать номера строк

for(w.lineNumbers.Reset(); !w.lineNumbers.EndOfList();

w.lineNumbers.Next())

ostr << w.lineNumbers.Data() << " ";

ostr << endl;

return ostr;

}

Программа подсчета вхождений слов (Конкорданс)

В программе определено бинарное дерево поиска 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 в качестве параметра, результаты будут выглядеть так:

a.............................3: 1 2

if............................1: 2

is............................1: 3

of............................3: 1 2

peck..........................4: 1 2 3

peppers.......................3: 1 2 3

peter.........................4: 1 2 3

picked........................4: 1 2 3

pickled.......................3: 1 3

piper.........................4: 1 2 3

that..........................1: 3

the...........................1: 3

where.........................1: 3