2

私がする必要があるのは、2 つの文字列を比較し、変更の開始/終了マークで違いをマークすることです。例：

これは弦番号 1 です。
この弦は弦番号 2 です。

出力は

この[は|文字列は]文字列番号[1|2]です。

私はしばらくの間、これを理解しようとしてきました。そして、これを行うのに役立つと信じていた何かが見つかりましたが、これを実現することはできません.
http://www.angusj.com/delphi/textdiff.html

ここでは約 80% 動作していますが、やりたいことを正確に実行する方法がわかりません。どんな助けでも大歓迎です。


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

type
  TForm2 = class(TForm)
    Edit1: TEdit;
    Edit2: TEdit;
    Button1: TButton;
    Memo1: TMemo;
    Diff: TDiff;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form2: TForm2;
  s1,s2:string;

implementation

{$R *.dfm}

procedure TForm2.Button1Click(Sender: TObject);
var
  i: Integer;
  lastKind: TChangeKind;

  procedure AddCharToStr(var s: string; c: char; kind, lastkind: TChangeKind);
  begin
    if (kind  lastkind) AND (lastkind = ckNone) and (kind  ckNone) then s:=s+'[';
    if (kind  lastkind) AND (lastkind  ckNone) and (kind = ckNone) then s:=s+']';
    case kind of         
      ckNone: s := s  + c;
      ckAdd: s := s + c;         
      ckDelete: s := s  + c;
      ckModify: s := s + '|' + c;
    end;
  end;

begin
  Diff.Execute(pchar(edit1.text), pchar(edit2.text), length(edit1.text), length(edit2.text));

  //now, display the diffs ...
  lastKind := ckNone;
  s1 := ''; s2 := '';
  form2.caption:= inttostr(diff.Count);
  for i := 0 to Diff.count-1 do
  begin

    with Diff.Compares[i] do
    begin
      //show changes to first string (with spaces for adds to align with second string)
      if Kind = ckAdd then 
      begin 
        AddCharToStr(s1,' ',Kind, lastKind); 
      end
      else 
      AddCharToStr(s1,chr1,Kind,lastKind);
      if Kind = ckDelete then 
      begin 
        AddCharToStr(s2,' ',Kind, lastKind)
      end
      else AddCharToStr(s2,chr2,Kind,lastKind);

      lastKind := Kind;
    end;
  end;
    memo1.Lines.Add(s1);
    memo1.Lines.Add(s2);
end;

end.

angusj.com から basicdemo1 を取得し、これを修正してここまで到達しました。

4

2 に答える 2

4

あなたが説明する問題を解決するには、本質的に、DNAまたはタンパク質データの生物学的配列アラインメントで行われるようなことをしなければなりません. 文字列が 2 つ (または定数参照文字列が 1 つ) しかない場合は、 Needleman Wunsch アルゴリズム* や関連アルゴリズムなどの動的プログラミングベースのペアワイズ アラインメント アルゴリズムによってアプローチできます。(複数の配列アラインメントはさらに複雑になります。)

[* 編集: リンク先: http://en.wikipedia.org/wiki/Needleman –Wunsch_algorithm ]

編集2：

文字ではなく単語のレベルで比較することに関心があるように見えるので、(1) 入力文字列を文字列の配列に分割し、各配列要素が単語を表し、(2) レベルで整列を実行することができます。これらの言葉の。これには、アライメントの検索スペースが小さくなるという利点があるため、全体的に高速になることが期待できます。それに応じて、ウィキペディアの記事からの擬似コードの例を適応させ、「Delphified」しました。


program AlignWords;



{$APPTYPE CONSOLE}



function MaxChoice (C1, C2, C3: integer): integer;
begin
  Result:= C1;
  if C2 > Result then Result:= C2;
  if C3 > Result then Result:= C3;
end;



function WordSim (const S1, S2: String): integer; overload;
//Case-sensitive!
var i, l1, l2, minL: integer;
begin
  l1:= length(S1);
  l2:= length(S2);
  Result:= l1-l2;
  if Result > 0 then Result:= -Result;
  if (S1='') or (S2='') then exit;
  minL:= l1;
  if l2 < l1 then minL:= l2;
  for i := 1 to minL do if S1[i]<>S2[i] then dec(Result);
end;



procedure AlignWordsNW (const A, B: Array of String; GapChar: Char; const Delimiter: ShortString; GapPenalty: integer; out AlignmentA, AlignmentB: string);
// Needleman-Wunsch alignment
// GapPenalty should be a negative value!
var
  F: array of array of integer;
  i, j,
  Choice1, Choice2, Choice3,
  Score, ScoreDiag, ScoreUp, ScoreLeft :integer;
  function GapChars (const S: String): String;
  var i: integer;
  begin
    assert (length(S)>0);
    Result:='';
    for i := 0 to length(S) - 1 do Result:=Result + GapChar;
  end;
begin
  SetLength (F, length(A)+1, length(B)+1);
  for i := 0 to length(A) do F[i,0]:= GapPenaltyi;
  for j := 0 to length(B) do F[0,j]:= GapPenaltyj;
  for i:=1 to length(A) do begin
    for j:= 1 to length(B) do begin
      Choice1:= F[i-1,j-1] + WordSim(A[i-1], B[j-1]);
      Choice2:= F[i-1, j] + GapPenalty;
      Choice3:= F[i, j-1] + GapPenalty;
      F[i,j]:= maxChoice (Choice1, Choice2, Choice3);
    end;
  end;
  AlignmentA:= '';
  AlignmentB:= '';
  i:= length(A);
  j:= length(B);
  while (i > 0) and (j > 0) do begin
    Score := F[i,j];
    ScoreDiag:= F[i-1,j-1];
    ScoreUp:= F[i,j-1];
    ScoreLeft:= F[i-1,j];
    if Score = ScoreDiag + WordSim(A[i-1], B[j-1]) then begin
      AlignmentA:= A[i-1] + Delimiter + AlignmentA;
      AlignmentB:= B[j-1] + Delimiter + AlignmentB;
      dec (i);
      dec (j);
    end else if Score = ScoreLeft + GapPenalty then begin
      AlignmentA:= A[i-1] + Delimiter + AlignmentA;
      AlignmentB:= GapChars (A[i-1]) + Delimiter + AlignmentB;
      dec(i);
    end else begin
      assert (Score = ScoreUp + GapPenalty);
      AlignmentA:= GapChars(B[j-1]) + Delimiter + AlignmentA;
      AlignmentB:= B[j-1] + Delimiter + AlignmentB;
      dec (j);
    end;
  end;
  while (i > 0) do begin
    AlignmentA:= A[i-1] + Delimiter + AlignmentA;
    AlignmentB:= GapChars(A[i-1]) + Delimiter + AlignmentB;
    dec(i);
  end;
  while (j > 0) do begin
    AlignmentA:= GapChars(B[j-1]) + Delimiter + AlignmentA;
    AlignmentB:= B[j-1] + Delimiter + AlignmentB;
    dec(j);
  end;
end;



Type
  TStringArray = Array Of String;



Var
  as1, as2: TStringArray;
  s1, s2: string;



BEGIN
    as1:= TStringArray.create ('this','is','string','number','one.');
    as2:= TStringArray.Create ('this','string','is','string','number','two.');



AlignWordsNW (as1, as2, '-',' ',-1, s1,s2);
writeln (s1);
writeln (s2);




END.

この例の出力は次のとおりです。

これ ------ は文字列番号 ---- 1 です。
この弦は弦番号 2 です。----

完璧ではありませんが、アイデアはわかります。この種の出力から、やりたいことができるはずです。ニーズに合わせてGapPenaltyと 類似性スコアリング関数を微調整したい場合があることに注意してください。WordSim

于 2010-01-26T18:31:26.453 に答える
1

役立つかもしれないObject Pascal Diff Engineが利用可能です。比較のために各「単語」を別々の行に分割するか、アルゴリズムを変更して単語ごとに比較することができます。

于 2010-01-26T21:14:21.447 に答える