Песни о Паскале

Глава 55 Слова, слова, слова…

Односвязные списки подоспели как раз вовремя, – сейчас они поработают в необычном проекте.

Однажды разгорелся спор об известном романе «Тихий Дон», – некоторые литераторы усомнились в авторстве Михаила Шолохова. Их сомнения развеяли программисты, вычислившие частотные характеристики нескольких его произведений. Что это за характеристики такие?

Предположим, вы подсчитали, что слово «Паскаль» упомянуто в этой книге 150 раз, а всего в книге 10000 слов. Тогда относительная частота слова «Паскаль» в книге составит 150 / 10000 = 0,015 или 1,5%. Если найти частоту употребления других слов книги, и расположить эти результаты в некотором порядке, то получится картина, подобная отпечатку пальца. У разных авторов эти «отпечатки» разные, зато у одного автора в разных произведениях – очень похожи! Обработав таким частотным анализатором несколько книг Михаила Шолохова, специалисты сравнили результаты и обнаружили на романе «Тихий Дон» «пальчики» донского писателя.

Итак, мы беремся за разработку слегка упрощенного частотного анализатора. Это опять тот случай, где заранее неизвестен объём обрабатываемых данных. В самом деле, определить приблизительное количество слов в тексте не так уж сложно: посчитаем их на одной странице и умножим на число страниц. Но сколько из этих слов несовпадающих, разных? Не слышу ответа!

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

Begin, NIL, P1, q2, Words_Count, _1_

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

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

    TRec = record { Тип записи для подсчета слов }

    mWord : string;     { Слово из текста – 256 байт }

    mCount : Longint;     { Счетчик слов – 4 байта }

    mNext : PRec;     { Указатель на следующий – 4 байта }

    end;

Сколько памяти займет один такой элемент? Сейчас посчитаем: 256+4+4=264 байта, – не так уж мало! Полагаю, что для слова достаточно и тридцати символов. Но, прежде, чем окончательно выбрать длину строки, открою небольшой секрет, – он касается выделения динамической памяти. Сколько бы памяти ни запросила программа, операционная система выделит кусочек, кратный восьми байтам. То есть, часть байтов в выделяемой порции может быть лишней. Значит, предпочтительный размер записи для динамических переменных кратен восьми байтам. В нашем случае размер записи можно уменьшить до 40 байтов, если объявить её так:

    TRec = record { Тип записи для подсчета слов }

    mWord : string[31]; { Слово из текста – 32 байта }

    mCount : Longint;     { Счетчик слов – 4 байта }

    mNext : PRec;     { Указатель на следующий – 4 байта }

    end;

С одной стороны, число 40 кратно 8, а с другой стороны, 31-го символа для слова вполне достаточно.

Теперь обсудим алгоритм обнаружения и обработки слов. В чем состоит эта обработка? Найдя выделенное слово в списке, нарастим его счетчик – поле mCount, а если слова в списке ещё нет, добавим запись с этим словом и счетчиком, равным единице.

Можно придумать много способов выборки слов из файла. Один из них – построчная обработка, когда каждую строку можно обработать так.

1. Перекодировать все символы строки в верхний регистр.

2. Удалить из начала строки все символы, которые не являются латинской буквой или подчеркиванием, и, если строка стала пустой, то завершить процедуру.

3. Выделить из строки очередное слово и удалить его из строки.

4. Искать слово в списке.

5. Если слово найдено, нарастить его счетчик, а иначе вставить в список запись со счетчиком, равным единице.

6. Прейти к пункту 2.

В перечисленных действиях нет ничего нового. В самом деле, обработка строк – дело привычное, так же, как поиск в сортированном списке и вставка в него данных. Таким образом, нам остается лишь собрать все это воедино, что и сделано в программе «P_55_1».

Процедуры этой программы сходны с аналогичными из полицейской базы данных, их отличает лишь порядок сортировки. Если там сортировка выполнялась по номерам автомобилей, то здесь – по словам.

{ P_55_1 – Частотный анализатор текста }

type

    PRec = ^TRec; { Тип указатель на запись }

    TRec = record { Тип записи для подсчета слов }

    mWord : string[31]; { Слово из текста }

    mCount : Longint;     { Счетчик слов }

    mNext : PRec;     { Указатель на следующий элемент }

    end;

var List : PRec; { Указатель на начало списка (голова) }

    { Поиск в сортированном списке }

function Find(const aWord: string): PRec;

var p: PRec;

begin

p:= List; { Поиск начинаем с головы }

{ Двигаемся по списку, пока следующий элемент существует

и слово в нём меньше искомого }

while Assigned(p) and Assigned(p^.mNext) and (p^.mNext^.mWord <= aWord)

    do p:=p^.mNext;

{ Если конец списка не достигнут и слово совпадает… }

if Assigned(p) and (p^.mWord = aWord)

    then Find:= p { … то успешно! }

    else Find:= nil; { … а иначе не нашли }

end;

    { Размещение нового элемента в сортированном списке слов }

procedure AddToSortList(const aWord : string);

var p, q : PRec;

begin

New(p); { Создаем динамическую переменную-запись }

{ Размещаем данные в полях записи }

p^.mCount:= 1; p^.mWord:= aWord; p^.mNext:=nil;

{ Если список пуст… }

if not Assigned(List)

then List:= p { …голова указывает на первую запись }

else begin

    q:= List; { Поиск места вставки начинаем с головы }

    { Двигаемся по списку, пока следующий элемент существует

    и его номер меньше вставляемого }

    while Assigned(q^.mNext) and (q^.mNext^.mWord < aWord)

    do q:=q^.mNext;

    if q^.mWord > aWord then begin

    { вставка на первое место }

    p^.mNext:=List;     { первый становится вторым }

    List:=p;     { а текущий- первым }

    end else begin

    { вставка в середине или в конце списка }

    p^.mNext:=q^.mNext; { связываем текущий со следующим }

    q^.mNext:=p;     { связываем предыдущий с текущим }

    end

    end

end;

    { Добавление слова либо увеличение его счетчика }

procedure AddWord(const aWord : string);

var P : PRec;

begin

P:= Find(aWord);

if Assigned(p)

    then Inc(P^.mCount)

    else AddToSortList(aWord);

end;

    { Выделение и добавление слов из прочитанной строки }

procedure AddLine(S: string);

const CLetter = ['A'..'Z','_'];

    CDigits = ['0'..'9'];

var W : string; i : integer;

begin

{ переводим все буквы строки в верхний регистр }

for i:=1 to Length(S) do S[i]:= UpCase(S[i]);

while Length(S)>0 do begin

{ удаляем все небуквы в начале строки }

while (Length(S)>0) and not (S[1] in CLetter) do Delete(S,1,1);

if Length(S)>0 then begin

    W:='';

    { копируем все буквы и цифры в слово W и удаляем из строки }

    while (Length(S)>0) and (S[1] in CLetter+CDigits) do begin

    W:= W+S[1];

    Delete(S,1,1);

    end;

    if Length(W)>1 then AddWord(W); { Если не буква, вставляем в список }

end;

end;

end;

    { Распечатка списка }

procedure PrintList(var F: text);

var P : PRec;

begin

Rewrite(F); P:= List;

while Assigned(P) do begin

Writeln(F, P^.mWord, '':(20-Length(P^.mWord)), P^.mCount:5 );

P:= P^.mNext;

end;

Close(F);

end;

var S: string; F: text;

begin {--- Главная программа ---}

List:= nil;

Assign(F, 'P_55_1.pas');

Reset(F);

while not Eof(F) do begin

Readln(F, S);

AddLine(S);

end;

Close(F); Assign(F, 'P_55_1.OUT');

PrintList(F); { Распечатка списка }

end.

Полагаю, что моих комментариев и вашего опыта хватит для понимания программы. Обязательно проверьте её. Вот результат исследования программой своего собственного текста (приведена только часть слов).

ADDLINE     2

ADDTOSORTLIST     2

ADDWORD     2

AND     6

ASSIGN     2

ASSIGNED     7

AWORD     10

BEGIN     14

CLETTER     3

А) Дополните программу средствами для подсчета:

• общего количества слов в файле;

• общего количества разных слов.

Напишите для этого подобающие функции.

Б) Измените программу так, чтобы при распечатке списка выводилась относительная частота слов в процентах от общего их количества с двумя знаками после точки.

В) Создайте программу для подсчета в файле слов, составленных из одних и тех же символов: цифр и букв, например: «end» и «deen», «121» и «221». Для каждой такой группы слов программа должна напечатать перечень входящих в них символов (каждый символ – по разу) и количество обнаруженных слов этой группы, например, для приведенных выше слов будет напечатано:

1 2 – 2

d e n – 2

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