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. 更新衝突の警告を表示し、再構成したデータをフォームに表示する。

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

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

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

メモ



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

PukiWiki 1.5.3+ © 2001-2020 PukiWiki Development Team. Powered by PHP 5.6.40-0+deb8u12. HTML convert time: 0.309 sec.

OSDN