差分検出アルゴリズム三種盛り - Object.create(null)
こんばんは. 気がつけばもうずいぶんと涼しくなってきました. 勢い余って凍ってしまったりせぬよう, くれぐれも普段の言動にはお気をつけください. はじめに さて, 我々人類にはどうしても二つの文字列 (あるいは行ごとに区切られたテキスト) 間の差分を求めなければいけない瞬間が発生します. 先人たちはそういった時のために diff のようなツールを開発し, それを利用することで文明はめざましい発展を遂げてきました. しかしながら, 使用するアルゴリズムを比較検討したい場合, 「差分」の定義を変えるなどして既存のアルゴリズムに変更を加えたい場合, diff のない異世界に飛ばされて自分で実装しなければいけない時などにおいては, 差分検出アルゴリズムについての理解が必要不可欠です. というわけで, この記事では文字列間の差分検出とは何かということと, 差分を求める三種類のアルゴリズムの紹介・解説
javascriptでdiff実装
高速とされるO(NP)のアルゴリズムをベースに 、javascriptで実装してみた。 [1]E.W.Myers, "An O(ND) difference algorithm and its variations", Algorithmixa, 1 (1986), pp.251-266 に論文を日本語に訳したものが載っており、参考になりました。 http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm 上記の論文中のコードは「ＳＥＤ Shotest Edit Distance」の値を求めるだけで、 Diffの結果をどう組み立て格納していくかについてと、fpという配列の初期値を 何で埋めればよいのかが分からず、 かなり苦労しました。 アルゴリズムは上記のO(NP)そのままですが、javascriptで実装していく中で、 メイン処理と
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
