PukiWiki/1.4/Diff

差分表示の改造†

文書比較を行う問題は、２つの文書Ａ，Ｂの最長共通部分（ＬＣＳ Longuest Common Subsequence）、または最小エディット距離（ＳＥＤ 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のコードが書いてあったんで、そいつをパクろうと思ったんですが、具体的に追加／削除された行をどうやって算出するのかがよくわからなかったので、そのあたりを適当(≒かなりいい加減)にでっち上げてしまいました。

↑

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

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

↑

仕掛け†

編集フォームに、編集開始時点のページ内容を（隠しフィールドで）仕込んでおく。
更新が衝突したら、以下のデータをつき合わせる。
- 編集開始時のページ内容と、現在のページ内容の差分 (l)
- 編集開始時のページ内容と、ポストしたページ内容の差分 (r)

決定表に基づき、ページデータを再構成する

l	r	現在のページ	ポストしたページ	処置
		変更無し	変更無し	維持
	-	変更無し	削除	削除
-		削除	変更無し	削除
-	-	削除	削除	削除
	+	該当行無し	追加	追加
+		追加	該当行無し	追加

更新衝突の警告を表示し、再構成したデータをフォームに表示する。

↑

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

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

編集前
```
元の行
```
現在のページ(l)
```
現在のページに書かれた行
```

ポストしたページ(r)

ポストしたページに書かれた行

処理

l r text

- - 元の行

+ 現在のページに書かれた行

+ ポストしたページに書かれた行

結果、双方の行がマージ後のページに含まれることになります。
```
現在のページに書かれた行
ポストしたページに書かれた行
```

↑

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

元ネタ
```
1
2
3
4
```
現在のページ
```
3
4
1 <-移動
2 <-移動
```
ポストしたページ
```
1
1のつづき <-追記
2
3
4
```
結果

l r text

- 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
  + + - -
  
  a b c d
  
  e b a b
- 現状のdiff.phpで得られるEdit Sequence
  - + - - + +
  
  a b c d
  
  e b a b
ちょっと書き換えてみました。このサイトで試せます -- ぱんだ 2003-01-28 (火) 21:13:58
$fp[$k]にいたるまでの一致点を$path[]に記録しておいて、そこから枝を伸ばすときに内容をコピーする、って言うのはいいアイデアだと思うんですが。 -- ぱんだ 2003-01-28 (火) 21:20:21

total:
today:
yesterday:
now: 1

l	r	text
-	-	元の行
+		現在のページに書かれた行
	+	ポストしたページに書かれた行

l	r	text
-		1
	+	1のつづき
-		2
		3
		4
+		1
+		2

差分表示の改造†

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

仕掛け†

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

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

メモ†

最新の16件