udpa.pas

动态规划算法求字符串的相似性（编辑距离）

unit uDpa;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, Grids;

type
  TForm1 = class(TForm)
    StringGrid1: TStringGrid;
    Edit1: TEdit;
    Edit2: TEdit;
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    procedure TraceBack(const row1, row2, row3: string; i, j: Integer);
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.TraceBack(const row1, row2, row3: string; i, j: Integer);
// recover the alignment of s1 and s2
var
  diag: integer;
  diagCh: char;
begin
   if (i > 1) and (j > 1) then
   begin
      diag := strtoint(StringGrid1.cells[j-1,i-1]);
      diagCh := '|';
      if StringGrid1.cells[j,0]<>StringGrid1.cells[0,i] then
      begin
        inc(diag); diagCh := ' ';
      end;

      if strtoint(StringGrid1.cells[j,i]) = diag  then//LAllison comp sci monash uni au
         traceBack(StringGrid1.cells[0,i]+row1, diagCh+row2, StringGrid1.cells[j,0]+row3, i-1, j-1)    // change or match
      else if strtoint(StringGrid1.cells[j,i]) = strtoint(StringGrid1.cells[j,i-1]) + 1 then // delete
         traceBack(StringGrid1.cells[0,i]+row1, ' '+row2, '-'+row3, i-1, j)
      else
         traceBack('-'+row1, ' '+row2, StringGrid1.cells[j,0]+row3, i, j-1);      // insertion
   end
   else if(i > 1) then
      traceBack(StringGrid1.cells[0,i]+row1, ' '+row2, '-'+row3, i-1, j)
   else if(j > 1) then
      traceBack('-'+row1, ' '+row2, StringGrid1.cells[j, 0]+row3, i, j-1)
   else // i==0 and j==0
      memo1.Lines.Text := row1+#13#10+row2+#13#10+row3+#13#10;
end;//traceBack

procedure TForm1.Button1Click(Sender: TObject);
var
  i,j,k, v1, v2, v3: integer;
begin
  if (edit1.text='') or (edit2.Text='') then exit;
  StringGrid1.RowCount := length(edit1.text)+2;
  StringGrid1.ColCount := length(edit2.text)+2;
  for I := 1 to StringGrid1.ColCount-1 do    // Iterate
  begin
    StringGrid1.Cells[i+1, 0]:=edit2.Text[i];
    StringGrid1.Cells[i, 1]:=inttostr(i-1);
  end;    // for
  for I := 1 to StringGrid1.RowCount-1 do    // Iterate
  begin
    StringGrid1.Cells[0, i+1]:=edit1.Text[i];
    StringGrid1.Cells[1, i]:=inttostr(i-1);
  end;    // for

  for I := 2 to StringGrid1.RowCount - 1 do    // Iterate
  begin
    for j := 2 to StringGrid1.ColCount - 1 do    // Iterate
    begin
      v1 := strtoint(StringGrid1.Cells[j-1,i-1]);
      if StringGrid1.Cells[j,0]<>StringGrid1.Cells[0,i] then
        inc(v1);
      v2 := strtoint(StringGrid1.Cells[j-1,i])+1;
      v3 := strtoint(StringGrid1.Cells[j,i-1])+1;
      if (v1<=v2) and (v1<=v3) then
        v3:=v1
      else if (v2<=v1) and (v2<=v3) then
        v3:=v2;
      StringGrid1.Cells[j,i]:=inttostr(v3);
    end;    // for
  end;    // for
  TraceBack('','','', StringGrid1.RowCount-1, StringGrid1.ColCount-1);
  memo1.Lines.Add(format('edit-distance=%s',[
    StringGrid1.Cells[StringGrid1.ColCount-1,StringGrid1.RowCount-1]]));
end;

end.