Алгоритмы текстовой обработки.

См. преамбулу "Алгоритмы символьной обработки"

Итак, формальная обработка текстов связана с взглядом на последовательности f как текст в некотором алфавите tChar, f Î tWord=NàtChar или слова - подпоследовательности (интервалы) текста. Примеры - операции вставки, исключения и замены слов, обычные при редактировании текстов.

В реальности, мы в этом пункте нигде далее не используем даже какие-либо специфические особенности типа tChar как множества символов. На деле, здесь tChar - произвольный тип.

type

tChar=?;

tPosition=?;

tWord=?;

procedure

Вставка(var ОсновнойТекст:tWord;ВставляемоеСлово: tWord; Позиция:tPosition);

Варианты - слово вставляется после, начиная с и до заданной позиции.

procedure Исключение

(var ОсновнойТекст:tWord; var Новое: tWord; НачалоИсключения,КонецИсключения :tPosition);

Варианты - те же, а также удаление подслова - процедура не порождает нового слова.

Все остальные операции формальной обработки текстов можно свести к операциям вставки и исключения. Так, например, операцию замены можно свести к исключению из текста одного слова и вставки другого, операцию порождения текста можно трактовать как вставку в пустой текст, а операцию уничтожения текста - как исключение (удаление) содержимого текста "из себя".

Другое дело - нужно ли это делать при заданной реализации текста. См. далее - при реализации текста списком мы в действительности выражаем вставку через порождение, удаление и копирование символов текста.

В свою очередь, операции вставки и исключения слов сводятся к кратной вставке и исключения символов.

Вставка и замена при представлении слов (псевдодинамическими) массивами.

type

tIndex=1..nMax; {максимальная длина текста+1}

tPosition=tIndex;

tWord=record Content: array[tPosition] of tChar; {содержимое слова/текста}

Len: tPosition {фактическая длина текста}

end;

procedure Insert {ВставкаПосле}

(var T {ОсновнойТекст} :tWord; W {ВставляемоеСлово}: tWord; P {Позиция}: tPosition);

var

i, {текущая позиция в W}

k: tPosition ; {=p+i, текущая позиция в T }

begin

i:=1;k:=p+1;

while (i<=W.Len) and (k<=nMax) do

begin {вставка i-го символа W}

{сдвиг текста вправо на 1, начиная с позиции k}

for j:= T.Len+1 downto k do T.Content[j+1]:= T.Content[j];

T.Content[k]:=V.Content[i];

inc(i);inc(k)

end; end;

procedure Exclude {Исключение}

(var T {ОсновнойТекст}:tWord; var V { Новое}: tWord; Start, Finish {НачалоИсключения,КонецИсключения} : tPosition);

begin

var

k: tPosition; {текущая позиция в T, k Î [Start,Finish] }

begin

V.Len:=0;k:=Start;

while k<=Finish do

begin {исключение i-го символа W}

inc(V.Len); V.Content[V.Len]:=T.Content[k];

{ удаление T.Content[k] - сдвиг текста влево на 1, начиная с позиции k+1}

for j:= k to T.Len do T.Content[j]:= T.Content[j+1];

inc(k)

end; end;