Частотный словарь

В качестве примера использования упорядоченного списка рассмотрим построение частотного словаря. Эта задача возникает при анализе некоторого текста, когда необходимо определить, сколько и каких слов в нем встретилось, то есть определить частоту появления каждого слова. Решение заключается в следующем.

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

type TInfo = string;

PNode = ^TNode;

TNode = record

Info: TInfo; // слово

cnt : integer; // счетчик повторений слова

Next: PNode

end;

А структуру частотного словаря можно будет выбрать такой:

type alphabet = ’a’..’z’;

TfreqWord = array[alphabet] of PNode

То есть частотный словарь — это массив указателей. Индекс массива — это буква, с которой начинаются все слова данного списка. Когда считывается очередное слово, то по его первой букве определяется соответствующий список.

Примечание

В приведенном описании для простоты предполагается, что слова могут начинаться только с маленькой латинской буквы. В реальном случае alphabet должно содержать все те символы, с которых могут начинаться слова обрабатываемого текста.

Сначала необходимо осуществить поиск слова в списке. А поиск в упорядоченном списке происходит быстрее, чем в неупорядоченном. Для переменных типа string упорядочение понимается в лексикографическом смысле, то есть роза меньше, чем роса, а роса меньше, чем соловей. В этой задаче мы также не касаемся филологического аспекта, то есть мы не приводим различные словоформы к некоторому общему виду, и слова люблю и любит считаем разными.

В основе алгоритма лежит процедура Insert, всегда вставляющая новый элемент в упорядоченный список. Однако теперь требуется дополнительная проверка на наличие в списке слова. Далее для сравнения приведены блок-схемы алгоритмов вставки в упорядоченный список (рис. 9.2, а) и обработки слова в списке частотного словаря (рис. 9.2, б). Дополнительные действия выделены серым цветом.

а б

Рис. 9.2.Блок-схемы алгоритмов вставки в упорядоченный список (а) и обработки слова в списке частотного словаря (б)

Программные дополнения учтены в процедуре InsertWord, приведенной в листинге 9.3.

Листинг 9.3 Вставка слова в список частотного словаря

procedure InsertWord(var p: PNode; e: TInfo);

var q,r : PNode;

Found: Boolean;

begin

if p=nil then begin // список пуст, создание первого элемента

new(p);

with p^ do begin

Info:=e; Next:=Nil;

cnt:=1; // инициализация счетчика

end;

end

else begin // вставка элемента в список

if e<=p^.Info then begin

if e=p^.Info then inc(p^.cnt)

else begin // вставка перед списком

new(q);

with q^ do begin

Info:=e; Next:=p; cnt:=1;

end;

p:=q

end;

end

else begin // поиск и вставка

found:=false; q:=p^.Next; r:=p;

while not found and (q<>Nil) do // поиск места для вставки

if e<=q^.Info then found:=true // место найдено

else begin // двигаемся дальше

r:=q; q:=q^.Next;

end;

if found then begin // найдено место в списке

if e=q^.Info then inc(q^.cnt)

//увеличение счетчика элемента

else begin // вставка нового элемента в список

new(r^.Next); r:=r^.Next;

with r^ do begin

Info:=e; Next:=q; cnt:=1;

end;

end

end

else begin // добавление элемента в конец списка

new(r^.Next); r:=r^.Next;

with r^ do begin

Info:=e; Next:=q; cnt:=1;

end;

end;

end ;

end;

end;

Создадим форму для работы с частотным словарем. Выставим компоненты:

q компонент Edit для ввода слова;

q кнопка ввода ;

q кнопка Очистить;

q компонент StringGrid — для вывода слов и частоты их повторений.

Форма показана на рис. 9.3.

Рис. 9.3. Форма для работы с частотным словарем.

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

Листинг 9.4. Заполнение словами и их частотами ячейки StringGrid

procedure TFormFreWord.ButtonInsertClick(Sender: TObject);

var r:PNode;

x:TInfo;

i:integer;

begin

x:=EditInsert.Text;

InsertWord(q,x);

r:=q; i:=1;

while r<>nil do begin // для каждого слова в списке

with StringGridWord do begin

Cells[i,0]:=r^.Info; // слово

Cells[i,1]:=IntToStr(r^.cnt); // счетчик повторений

end;

r:=r^.Next; i:=i+1;

end;

EditInsert.Text:='';

EditInsert.SetFocus;

end;