blogこの広告は、90日以上更新していないブログに表示しています。2013-12-08Mercurialのextdiffツールを改良する先日、自作のextdiffツールcudiffを公開しました。2013これにはひとつ心残りがありました。行内差分を比較するペアの決定方法が単純で、関係ない行を比較してしまうことです。行の追加と行の変更が続くと、以下のように残念なことになります。None,'bbbb']となっています。None,'xxxx'],['bbb','bbbb']となってほしいところです。difflibのドキュメントをぼんやり眺めていたら、ndiffがまさに期待する通りに動作していました。+さっそくdifflibのソースコードLib/difflib.pyを見ると、以下のようになっていました。b)SequenceMatcherは文字列を引数にとるものだと思っていたので、配列を入れていることに面食らったのですが、考えてみれば文字列とは「文字の配列」でもあるわけで、文字列の比較ができるなら「文字列の配列」の比較もできるわけですね。Differクラスを読んだところ、Differ.compare()で行レベルの比較をして、変更のある行についてはDiffer._fancy_replace()で文字レベルの比較をしている、ということがわかりました。_fancy_replaceには、どの行とどの行を比較するかペアを決めるアルゴリズムがあり、この機能を組み込むため移植することにしました。行レベルの差分はdiffコマンドに丸投げしているので、compareの処理は特に必要ありません。ちなみに、difflibにはもともとside-by-side形式のHTMLを出力する機能があるのですが、ソースコードを見たところ嫌な予感がしたので再利用するのは避けました。処理の流れは軽くしか追ってないのですが、HtmlDiffはndiffの出力結果をわざわざパースしています。diff_lines_iteratorを解析する長い処理...ndiffはDifferを使い、DifferはSequenceMatcherの解析データをもとに出力文字列を生成しています。SequenceMatcherの解析データを直接利用すれば、Differの出力する文字列を解析する手間はかからないわけです。diffをわざわざパースするプログラム書いてる私が言うのもなんですが。移植にあたり、_fancy_replaceのcutoffの値を変えました。この値が高すぎると、行内差分が見たいのにまるごと置き換わったことになってしまいますし、低すぎると、内容はまったく関係の無い行なのに句読点が一致しているといった意味のない行内差分を見せられることになります。0.75なのですが、高すぎると感じたので0.59にしてみました。値が0.6を超えると、シーケンスがよく似ていることを示します」とあります。移植は成功し、めでたく気の利いたdiffが見れるようになりました。変更したソースコードはBitbucketで公開しています。・cudiff.pydifflibのソースコードと翻訳ドキュメントを公開してくれている方々に感謝。スクリプトMercurialとSubversionのメンタルモデルの違い月別アーカイブはてなブログをはじめよう!toruotさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。