[http://www.wccm6-apcom04.org.cn/gongsizhuce 注册公司]
[http://www.cnfti.org.cn/zuche 租车]
[http://www.go4it.com.cn/shujuhuifu 数据恢复]
[http://www.cnfti.org.cn/jianfei 减肥]
[http://www.czwin.com.cn/jianfei 减肥]
[http://zxmr.futurenet.com.cn/ 整形]
[http://www.go4it.com.cn/zigongjiliu 子宫肌瘤]
[http://www.go4it.com.cn/fuke 妇科] 
[http://www.go4it.com.cn/tzxl 拓展训练]
[http://www.cnfti.org.cn/wangshanggouwu 网上购物] 
[http://www.cnfti.org.cn/duijiangji 对讲机]
[http://www.necsi.com.cn/duijiangji 对讲机]
[http://www.go4it.com.cn/tzxl 拓展训练]
[http://www.cnfti.org.cn/ecnfti.htm 注册外资公司]
[http://www.go4it.com.cn/shuangseqiu 双色球]
[http://www.go4it.com.cn/zhaopin 招聘]
[http://www.cnfti.org.cn/huojia 货架]
[http://www.wccm6-apcom04.org.cn/gPS gPS]
[http://www.necsi.com.cn/fz 服装]
[http://www.necsi.com.cn/dazhejipiao 机票] 
[http://www.necsi.com.cn/lipin 礼品] 
[http://www.necsi.com.cn/meirong 美容] 
[http://www.necsi.com.cn/fanyi 翻译]
[http://www.necsi.com.cn/zufang 租房]
[http://www.necsi.com.cn/xianhua 鲜花]
[http://www.cnfti.org.cn/lvyou 旅游]
[http://www.cnfti.org.cn/jiaoyou 交友]
[http://lllhhh.freewebpage.org 六合彩]
[http://www.cnfti.org.cn/xianhua 鲜花]
[http://www.cnfti.org.cn/xdocs/HuaXianXieHui/hxxhEjj.htm 数据恢复]
[http://www.cnfti.org.cn/fanyigongsi 翻译公司]
[http://www.cnfti.org.cn/ganzsb 干燥设备]
[http://www.cnfti.org.cn/meirong 美容]
[http://www.cnfti.org.cn/jipiao 机票]
[http://www.cnfti.org.cn/wto.htm 六合彩]
[http://www.cnfti.org.cn/lipin 礼品]
[http://www.czwin.com.cn/jipiao 机票]
[http://www.cnfti.org.cn/shangbiao 商标]
[http://www.cnfti.org.cn/fanyi 翻译]
[http://www.cnfti.org.cn/shangbiao 注册]
[http://www.cnfti.org.cn/zufang 租房]
[http://www.czwin.com.cn/xianhua 鲜花]
[http://www.necsi.com.cn/zuche 租车]
[http://www.wccm6-apcom04.org.cn/postour/pt3.htm 礼品]
[http://www.wccm6-apcom04.org.cn/postour 美容]
[http://www.wccm6-apcom04.org.cn/wccmvii.htm 机票]
[http://www.wccm6-apcom04.org.cn/download.htm 翻译]
[http://www.wccm6-apcom04.org.cn/huojia 货架]
[http://www.wccm6-apcom04.org.cn/zuche 租车]
[http://www.wccm6-apcom04.org.cn/xianhua 鲜花]
[http://www.wccm6-apcom04.org.cn/zufang 租房]
[http://www.wccm6-apcom04.org.cn/diaocha 调查]
[http://www.wccm6-apcom04.org.cn/zhentan 侦探]
[http://www.futurenet.com.cn/meirong 美容]
[http://www.wccm6-apcom04.org.cn/gongsizhuce 上海公司注册]
[http://www.wccm6-apcom04.org.cn/gongsizhuce 注册上海公司]
[http://www.wccm6-apcom04.org.cn/gongsizhuce 注册外资公司]
[http://www.wccm6-apcom04.org.cn/gongsizhuce 注册上海公司]
[http://www.wccm6-apcom04.org.cn/gongsizhuce 上海注册公司]
[http://www.wccm6-apcom04.org.cn/gongsizhuce 代理注册公司]
[http://www.wccm6-apcom04.org.cn/gongsizhuce 代理公司注册]
[http://www.wccm6-apcom04.org.cn/gongsizhuce 代办营业执照]
[http://www.wccm6-apcom04.org.cn/gongsizhuce 代办公司注册]
[http://www.wccm6-apcom04.org.cn/gongsizhuce 代办公司]
[http://www.wccm6-apcom04.org.cn/gongsizhuce 代办执照]
[http://zcgs.futurenet.com.cn 注册外资公司]
[http://zcgs.futurenet.com.cn 注册上海公司]
[http://www.cnfti.org.cn/ecnfti.htm 上海注册公司]
[http://www.cnfti.org.cn/ecnfti.htm 代理注册公司]
[http://www.cnfti.org.cn/ecnfti.htm 代理公司注册]
[http://www.cnfti.org.cn/ecnfti.htm 代办营业执照]
[http://www.cnfti.org.cn/ecnfti.htm 代办公司注册]
[http://www.cnfti.org.cn/ecnfti.htm 代办公司]
[http://www.cnfti.org.cn/ecnfti.htm 代办执照]
[http://www.futurenet.com.cn/xianhua 鲜花]
[http://dzjp.futurenet.com.cn 机票] 
[http://fygs.futurenet.com.cn 翻译公司]
[http://www.necsi.com.cn/tz 投资]
[http://www.necsi.com.cn/xmgl 项目管理]
[http://www.necsi.com.cn/ls 律师]
[http://www.necsi.com.cn/gjg 钢结构]
[http://www.necsi.com.cn/google google左侧排名]
[http://www.necsi.com.cn/zhengxing 整形] 
[http://www.necsi.com.cn/zhuce 注册]
[http://www.necsi.com.cn/zhucegongsi 注册公司]
[http://www.cnfti.org.cn/wangzhantuiguang 网站推广]
[http://www.cnfti.org.cn/liuxue 留学]
[http://www.cnfti.org.cn/chuanqisifu 传奇私服]
[http://www.cnfti.org.cn/wangzhanjianshe 网站建设]
[http://www.cnfti.org.cn/sheji 设计]
[http://www.cnfti.org.cn/chuguo 出国]
[http://www.cnfti.org.cn/jianruishiyou 尖锐湿疣]
[http://www.cnfti.org.cn/yunnanlvyou 云南旅游]
[http://www.cnfti.org.cn/tzxl 拓展训练]
[http://www.cnfti.org.cn/shipinliaotian 视频聊天]
[http://www.czwin.com.cn/hainanlvyou 海南旅游]
[http://www.czwin.com.cn/zhengxing 整形]
[http://www.czwin.com.cn/fanyi 翻译公司]
[http://www.czwin.com.cn/zufang 租房]
[http://www.czwin.com.cn/meirong 美容]
[http://www.czwin.com.cn/bjb 笔记本]
[http://www.czwin.com.cn/zhuce 注册]
[http://www.wccm6-apcom04.org.cn/postour/pt1.htm 整形]
[http://www.wccm6-apcom04.org.cn/gongsizhuce 公司注册]
[http://www.wccm6-apcom04.org.cn/fyj 复印机]
[http://www.wccm6-apcom04.org.cn/cmp 触摸屏]
[http://www.wccm6-apcom04.org.cn/shangbiao 商标]
[http://www.wccm6-apcom04.org.cn/jiankong 监控]
[http://www.wccm6-apcom04.org.cn/zufang 租房]
[http://www.wccm6-apcom04.org.cn/bjb 笔记本]
[http://www.wccm6-apcom04.org.cn/guangduanji 光端机]
[http://www.wccm6-apcom04.org.cn/biaoqiandayinji 标签打印机]
[http://www.wccm6-apcom04.org.cn/canyinguanli 餐饮管理]
[http://www.wccm6-apcom04.org.cn/chuangshangyongpin 床上用品]
[http://www.wccm6-apcom04.org.cn/dengju 灯具]
[http://www.wccm6-apcom04.org.cn/kaiguandianyuan 开关电源]
[http://www.wccm6-apcom04.org.cn/upsdianyuan ups电源]
[http://www.wccm6-apcom04.org.cn/wenyadianyuan 稳压电源]
[http://www.wccm6-apcom04.org.cn/bujindianji 步进电机]
[http://www.wccm6-apcom04.org.cn/diaosu 雕塑]
[http://www.wccm6-apcom04.org.cn/diaokeji 雕刻机]
[http://www.wccm6-apcom04.org.cn/duanxinqunfa 短信群发]
[http://www.wccm6-apcom04.org.cn/erp erp]
[http://www.wccm6-apcom04.org.cn/falvzixun 法律咨询]
[http://www.wccm6-apcom04.org.cn/guanlipeixun 管理培训]
[http://www.wccm6-apcom04.org.cn/guangchumei 光触媒]
[http://www.wccm6-apcom04.org.cn/guanliguwen 管理顾问]
[http://www.wccm6-apcom04.org.cn/bangonghaocai 办公耗材]
[http://www.wccm6-apcom04.org.cn/huagongshebei 化工设备]
[http://www.wccm6-apcom04.org.cn/huanreqi 换热器]
[http://www.wccm6-apcom04.org.cn/jixiang 机箱]
[http://www.wccm6-apcom04.org.cn/jidianqi 继电器]
[http://www.wccm6-apcom04.org.cn/bangongjiaju 办公家具]
[http://www.wccm6-apcom04.org.cn/jixiang 驾校]
[http://www.wccm6-apcom04.org.cn/jiaohuanji 交换机]
[http://www.wccm6-apcom04.org.cn/KVM KVM]
[http://www.wccm6-apcom04.org.cn/zhiwenkaoqinji 指纹考勤机]
[http://www.wccm6-apcom04.org.cn/tingchechang 停车场]
[http://www.wccm6-apcom04.org.cn/menjingongsi 门禁系统]
[http://www.wccm6-apcom04.org.cn/qianzheng 签证]
[http://www.wccm6-apcom04.org.cn/pingmiansheji 平面设计]
[http://www.wccm6-apcom04.org.cn/shuibeng 水泵]
[http://www.wccm6-apcom04.org.cn/zhenkongben 真空泵]
[http://www.wccm6-apcom04.org.cn/suji 速记]
[http://www.wccm6-apcom04.org.cn/sujipeixun 速记培训]
[http://www.wccm6-apcom04.org.cn/shoubiao 手表]
[http://www.wccm6-apcom04.org.cn/taoci 陶瓷]
[http://www.wccm6-apcom04.org.cn/touyingjiweixiu 投影机维修]
[http://www.wccm6-apcom04.org.cn/dianji 电机]
[http://www.wccm6-apcom04.org.cn/tuliao 涂料]
[http://www.wccm6-apcom04.org.cn/tuopan 托盘]
[http://www.wccm6-apcom04.org.cn/wajueji 挖掘机]
[http://www.wccm6-apcom04.org.cn/tiezhixiangji 贴纸相机]
[http://www.wccm6-apcom04.org.cn/yeya 液压]
[http://www.wccm6-apcom04.org.cn/yeyaji 液压机]
[http://www.wccm6-apcom04.org.cn/youqi 油漆]
[http://www.wccm6-apcom04.org.cn/zhanlan 展览]
[http://www.wccm6-apcom04.org.cn/zhuangshi 装饰]
[http://www.wccm6-apcom04.org.cn/ershoufang 二手房]
[http://www.wccm6-apcom04.org.cn/sijiazhentan 私家侦探]
[http://www.wccm6-apcom04.org.cn/sirenzhentan 私人侦探]
[http://www.wccm6-apcom04.org.cn/tangniaobing 糖尿病]
[http://www.wccm6-apcom04.org.cn/liuliangji 流量计]
[http://www.wccm6-apcom04.org.cn/ganbing 肝病]
[http://www.futurenet.com.cn/zhengxing 整形]
[http://sjhf.futurenet.com.cn 数据恢复] 
[http://jdyd.futurenet.com.cn 酒店预订]  
[http://wztg.futurenet.com.cn 网站推广]  
[http://google1.futurenet.com.cn google推广]
[http://google2.futurenet.com.cn google排名] 
[http://fygs.futurenet.com.cn 翻译]
[http://www.cnfti.org.cn/jixiang 驾校][[PukiWiki/1.4]]
[[PukiWiki/1.4]]

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

*差分表示の改造 [#vc0ccaa5]

[[文書比較アルゴリズム:http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm]]より...
>
文書比較を行う問題は、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 

[[論文:http://www.cs.arizona.edu/people/gene/PAPERS/np_diff.ps]]をがんばって読んだんですが、まだぼんやりとしか理解できていません。  :)

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

*更新の衝突時に、衝突した更新をマージする [#n657a02d]
更新の衝突を自動的に何とかするような仕掛けを考えてみました。

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

**ある行を双方が書き換えていた場合 [#qb4f5019]
行の書き換えは、「一行削除+一行追加」とみなされます。
-編集前
 元の行
-現在のページ(l)
 現在のページに書かれた行
-ポストしたページ(r)
 ポストしたページに書かれた行
-処理
,l,r,text
,-,-,元の行
,+, ,現在のページに書かれた行
, ,+,ポストしたページに書かれた行
結果、双方の行がマージ後のページに含まれることになります。
 現在のページに書かれた行
 ポストしたページに書かれた行

**ある行がどこかに移動した場合 [#ke535db7]
-元ネタ
 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のつづき'を適切な場所に手動で移動してください。 ;(

*メモ [#z3b7449c]
-いちいち行の内容を比較するんじゃなくて、ハッシュ値か何かを先に作っておいたほうが速いのか…? -- [[ぱんだ]] SIZE(10){2002-10-22 (火) 17:37:23}
--ハッシュを計算するコストの方が大きいか。 -- [[ぱんだ]] SIZE(10){2002-10-22 (火) 17:37:44}
-空行の差分の取り方に一考の余地あり。 -- [[ぱんだ]] SIZE(10){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)の計算は省略できるのかな。%%~
やはり計算する必要はあるそうですね。-- [[こじま]] SIZE(10){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から逆にたどるしかないようです。-- [[こじま]] SIZE(10){2003-01-27 (月) 21:12:30}
-そうですね。その例でいうと、bが見つかってしまった時点で同列(対角線)の枝を刈ってしまいます。似た行が少ないときは現状でも十分使い物になるんですが、PukiWikiでよく使われる''空行''がマッチしてしまった時点で、それ以降のsnakeの結果を無視してしまう問題があって、直さなきゃなぁ、と思っていました。 -- [[ぱんだ]] SIZE(10){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|
-ちょっと書き換えてみました。このサイトで試せます -- [[ぱんだ]] SIZE(10){2003-01-28 (火) 21:13:58}
-$fp[$k]にいたるまでの一致点を$path[]に記録しておいて、そこから枝を伸ばすときに内容をコピーする、って言うのはいいアイデアだと思うんですが。 -- [[ぱんだ]] SIZE(10){2003-01-28 (火) 21:20:21}

#comment

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
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.062 sec.

OSDN