PukiWiki/1.4

しろくろのへや:do_diffから移動してきました。 -- ぱんだ

差分表示の改造

文書比較アルゴリズムより...

文書比較を行う問題は、2つの文書A,Bの最長共通部分(LCS Longuest Common Subsequence)、または最小エディット距離(SED Shotest Edit Distance)を求める問題と等価である。

…だそうです。なんとなく速そうだったので、PukiWikiの差分表示ルーチンをO(NP)アルゴリズムで作ってみようと思った次第で。

http://www.cs.arizona.edu/people/gene

[1] E.W.Myers, "An O(ND) difference algorithm and its variations", Algorithmixa, 1 (1986), pp.251-266

[2] S.W.maner, "G.Myers, W.Miller, An O(NP) Sequence Comparison Algorith", August 1989

論文をがんばって読んだんですが、まだぼんやりとしか理解できていません。 :)

論文にはPascalのコードが書いてあったんで、そいつをパクろうと思ったんですが、具体的に追加/削除された行をどうやって算出するのかがよくわからなかったので、そのあたりを適当(≒かなりいい加減)にでっち上げてしまいました。

更新の衝突時に、衝突した更新をマージする

更新の衝突を自動的に何とかするような仕掛けを考えてみました。

仕掛け

  1. 編集フォームに、編集開始時点のページ内容を(隠しフィールドで)仕込んでおく。
  2. 更新が衝突したら、以下のデータをつき合わせる。
    • 編集開始時のページ内容と、現在のページ内容の差分 (l)
    • 編集開始時のページ内容と、ポストしたページ内容の差分 (r)
  3. 決定表に基づき、ページデータを再構成する
    lr現在のページポストしたページ処置
    変更無し変更無し維持
    -変更無し削除削除
    - 削除変更無し削除
    --削除削除削除
    +該当行無し追加追加
    + 追加該当行無し追加
  4. 更新衝突の警告を表示し、再構成したデータをフォームに表示する。

ある行を双方が書き換えていた場合

行の書き換えは、「一行削除+一行追加」とみなされます。

  • 編集前
    元の行
  • 現在のページ(l)
    現在のページに書かれた行
  • ポストしたページ(r)
    ポストしたページに書かれた行
  • 処理
    lrtext
    --元の行
    + 現在のページに書かれた行
    +ポストしたページに書かれた行
    結果、双方の行がマージ後のページに含まれることになります。
    現在のページに書かれた行
    ポストしたページに書かれた行

ある行がどこかに移動した場合

  • 元ネタ
    1
    2
    3
    4
  • 現在のページ
    3
    4
    1 <-移動
    2 <-移動
  • ポストしたページ
    1
    1のつづき <-追記
    2
    3
    4
  • 結果
    lrtext
    - 1
    +1のつづき
    - 2
    3
    4
    + 1
    + 2
    1のつづき ←生き別れ
    3
    4
    1
    2
    こういう場合は、'1のつづき'を適切な場所に手動で移動してください。 ;(

メモ

  • いちいち行の内容を比較するんじゃなくて、ハッシュ値か何かを先に作っておいたほうが速いのか…? -- ぱんだ 2002-10-22 (火) 17:37:23
    • ハッシュを計算するコストの方が大きいか。 -- ぱんだ 2002-10-22 (火) 17:37:44
  • 空行の差分の取り方に一考の余地あり。 -- ぱんだ 2002-10-22 (火) 19:00:59
  • こんにちは。pukiwikiの話じゃないですが。 僕も、diffのプログラムをしていて、 O(NP)で具体的にShortest Edit Sequenceを計算する方法が分からなくて 困ってました。
    fp(p,k)をすべて記憶しておくことで、sinkからアルゴリズムを逆にたどって、SESを計算していたのですが、ぱんださんのソースを見て、目からうろこです。
    非常にうまい方法ですね。たしかに、snake()の中で現在位置と比較すると、 ちょうど、max計算に使ったパスになります!。
    -- [[こじま]] SIZE(10){2003-01-13 (月) 05:50:00}
  • ということは、fp(k)を -p <= 0 <= p+DELTA まですべて計算する必要はないような。
    現在位置より左上の頂点に関してのfp(k)の計算は省略できるのかな。
    やはり計算する必要はあるそうですね。-- こじま? 2003-01-13 (月) 05:57:08
  • やはり、よく考えると、この方法では、最短のSESを見つけられない場合があります。
    例) 記号列abcdとebabのとき。
    最短は、+e, +b, ab, -c, -d ですが、この方法だと、-a, +e, b, -c, -d, +a, +b になってしまうと思われます。
    たいした問題ではないと思いますが、一応、報告です。
    やはり、fp(p,k)をすべて記憶しておき、sinkから逆にたどるしかないようです。-- こじま? 2003-01-27 (月) 21:12:30
  • そうですね。その例でいうと、bが見つかってしまった時点で同列(対角線)の枝を刈ってしまいます。似た行が少ないときは現状でも十分使い物になるんですが、PukiWikiでよく使われる空行がマッチしてしまった時点で、それ以降のsnakeの結果を無視してしまう問題があって、直さなきゃなぁ、と思っていました。 -- ぱんだ 2003-01-27 (月) 22:17:42
    • 最短の(Shortest)Edit Sequence
      ++--
      abcd
      ebab
    • 現状のdiff.phpで得られるEdit Sequence
      -+--++
      abcd
      ebab
  • ちょっと書き換えてみました。このサイトで試せます -- ぱんだ 2003-01-28 (火) 21:13:58
  • $fp[$k]にいたるまでの一致点を$path[]に記録しておいて、そこから枝を伸ばすときに内容をコピーする、って言うのはいいアイデアだと思うんですが。 -- ぱんだ 2003-01-28 (火) 21:20:21


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2005-03-09 (水) 16:25:47
Site admin: PukiWiki Development Team

PukiWiki 1.5.2+ © 2001-2019 PukiWiki Development Team. Powered by PHP 5.6.40-0+deb8u7. HTML convert time: 0.234 sec.

OSDN