Фундаментальные алгоритмы и структуры данных в Delphi

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

Однако вместо того, чтобы их удалять, мы просто их пропустим. Соответствующий алгоритм достаточно прост: необходимо выполнить считывание всех состояний. Для каждого состояния необходимо следовать по ссылке, указанной в его поле NextStatel. Если она устанавливает связь с одним из фиктивных состояний, связь нужно заменить связью NextStatel фиктивного состояния. Это же потребуется выполнить для связи NextState2 каждого состояния, если она существует. Код выполнения этой итерационной процедуры приведен в листинге 10.13.

Листинг 10.13. Оптимизация фиктивных состояний

procedure TtdRegexEngine.rcLevel1Optimize;

var

i : integer;

Walker : PNFAState;

begin

{оптимизация первого уровня удаляет все состояния, которые содержат только один бесплатный переход к другому состоянию}

{циклически обработать все записи состояний, кроме последней}

for i := 0 to (FTable.Count - 2) do

begin {получить данное состояние}

with PNFAState (FTable [ i ])^ do

begin

{выполнить проход по цепочке, указанной первым следующим состоянием, и разорвать связи с состояниями, которые являются простыми одиночными бесплатными переходами}

Walker := PNFAState(FTable[sdNextState1]);

while (Walker^.sdMatchType = mtNone) and

(Walker^.sdNextState2 = UnusedState) do

begin

sdNextState1 := Walker^.sdNextState1;

Walker := PNFAState(FTable[sdNextState1]);

end;

{выполнить проход по цепочке, указанной вторым следующим состоянием, и разорвать связи с состояниями, которые являются простыми одиночными бесплатными переходами}

if (sdNextState2 <> UnusedState) then begin

Walker := PNFAState(FTable[sdNextState2]);

while (Walker^.sdMatchType = mtNone) and

(Walker^.sdNextState2 = UnusedState) do

begin

sdNextState2 := Walker^.sdNextState1;

Walker := PNFAState(FTable[sdNextState2]);

end;

end;

end;

end;

end;

Сопоставление строк с регулярными выражениями

Пора решить заключительную часть задачи использования регулярных выражений - выполнить сопоставление с ними строк. Вместо того чтобы использовать уже рассмотренный алгоритм обратной трассировки, мы применим другой алгоритм. Используя входную строку, мы выполним обход конечного NFA-автомата (т.е. таблицы переходов), при этом одновременно отслеживая все возможные пути через конечный автомат. Со временем символы в строке будут исчерпаны, причем к этой точке будет вести один или более путей, либо возможных путей обработки строки больше не останется.

Однако для реализации этого алгоритма потребуется реализация очереди с двусторонним доступом (deque). Очередь с двусторонним доступом - это двусторонняя очередь, в которой постановку в очередь и исключение из очереди можно выполнять с любого конца. Нам потребуется возможность постановки элементов в конец очереди и их заталкивания в начало и из начала очереди (иначе говоря, исключение элементов из очереди должно выполняться только из ее начала и никогда из ее конца). Элементы, которые нужно будет ставить в очередь, представляют собой целочисленные значения (фактически, номера состояний). Код реализации этой простой очереди с двусторонним доступом показан в листинге 10.14 (его также можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDIntDeq.pas).

Листинг 10.14. Класс очереди целочисленных значений с двусторонним доступом type

TtdIntDeque = class private

FList : TList;

FHead : integer;

FTail : integer;

protected procedure idGrow;

procedure idError(aErrorCode : integer;

const aMethodName : TtdNameString);

public

constructor Create(aCapacity : integer);

destructor Destroy; override;

function IsEmpty : boolean;

procedure Enqueue(aValue : integer);

procedure Push(aValue : integer);

function Pop : integer;

end;

constructor TtdIntDeque.Create(aCapacity : integer);

begin

inherited Create;

FList := TList.Create;

FList.Count := aCapacity;

{для облегчения задачи пользователя очереди с двусторонним доступом поместить указатели начала и конца очереди в ее середину - вероятно, это более эффективно}

FHead := aCapacity div 2;

FTail := FHead;

end;

destructor TtdIntDeque.Destroy;

begin

FList.Free;

inherited Destroy;

end

procedure TtdIntDeque.Enqueue(aValue : integer);

begin

FList.List^[FTail] := pointer(aValue);

inc(FTail);

if (FTail = FList.Count) then

FTail := 0;

if (FTail = FHead) then

idGrow;

end;

procedure TtdIntDeque.idGrow;

var

OldCount : integer;

i, j : integer;

begin

{увеличить размер списка на 50%}

OldCount := FList.Count;

FList.Count := (OldCount * 3) div 2;

{распределить данные по увеличенной области, поддерживая при этом очередь с двусторонним доступом}

if (FHead= 0) then

FTail := OldCount else begin

j := FList.Count;

for i := pred(OldCount) downto FHead do

begin

dec(j);

FList.List^[j] := FList.List^[i] end;

FHead := j;

end;

end;

function TtdIntDeque.IsEmpty : boolean;

begin

Result := FHead = FTail;

end;

procedure TtdIntDeque.Push(aValue : integer);

begin

if (FHead = 0) then