JavaScriptでdiffを書いた
必要になったので JavaScript で diff を書いた． 軽く調べたところ Wu のアルゴリズム[1]が優秀ということだったのでそのままコードに起こした． 編集距離や SES(Shortest Edit Script)，LCS(Longest Common Subsequence)といった概念やエディットグラフを学んだ．
できあがったもの
学んだこと
- 編集距離とはどれくらい変化しているかを表したもの
- SES は編集距離が最短になる書き換えの方法
- LCS は一番長い共通部分のこと
- 編集距離を求める時に SES がわかり，SES がわかれば LCS もわかる
- 2 つのテキストを縦軸と横軸に置いたエディットグラフを考えると削除や追加の処理が縦横の移動になり，書き換えない部分は斜めの移動になる
- 経路探索の問題に落とし込める
- Wu のアルゴリズムでは遠回りをしない部分からだんだんと探索する領域を広げることで効率よく探索を行う
- 適当に再帰で探索を書いたらとても遅かったので，良いアルゴリズムを使うと良いと思った
参考
- [1] Sun Wu, Udi Manber, Gene Myers and Webb Miller, “An O(NP) sequence comparison algorithm,” Information Processing Letters, Volume 35, Issue 6, pp. 317-323, 1990, doi: 10.1016/0020-0190(90)90035-V.
- [2] convto, “Wu らによる差分検出の O(NP) アルゴリズム実装シリーズ ① 仕組み、考え方,” https://qiita.com/convto/items/e05d8147d9808a27b8ff, 2020 年 8 月 26 日閲覧.
- [3] convto, “Wu らによる差分検出の O(NP) アルゴリズム実装シリーズ ② 探索方法,” https://qiita.com/convto/items/8faf530d304024a22769, 2020 年 8 月 26 日閲覧.
- [4] convto, “Wu らによる差分検出の O(NP) アルゴリズム実装シリーズ ③Go による実装,” https://qiita.com/convto/items/39efea78e23a944d0760, 2020 年 8 月 26 日閲覧.
- [5] 久保達彦, “diff の動作原理を知る～どのようにして差分を導き出すのか,” https://gihyo.jp/dev/column/01/prog/2011/diff_sd200906?page=1, 2020 年 8 月 26 日閲覧.