Олег Деревенец - Песни о Паскале

Предположим, вы подсчитали, что слово «Паскаль» упомянуто в этой книге 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; { Тип указатель на запись }