分1234UNIXの基本的なコマンドの1つであるdiff。これに実装されているアルゴリズムは実に興味深い世界が広がっています。本稿では,筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。2009年6月号の記事を,現在の状態に合わせて加筆/修正しています。はじめにdiffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。ソフトウェア開発を行っている方であれば,SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。差分を計算するというのは次の3つを計算することに帰結します。Script)ある要素列を別の要素列に変換するための最短手順dtlを使って文字列の差分を計算する本稿ではdtlというdiffライブラリとそのサンプルプログラムを利用して,これらの用語について具体的に解説します。libraryの略で,筆者が開発しているC++製のdiffライブラリです(注1⁠)⁠。dtlのサンプルプログラムのビルドにはSCons(注2)を使用しているので,まずはSConsをインストールしてください。DebianやUbuntuであれば次のコマンドでインストールできます。sconsまた,C++プログラムをコンパイルするために,次のパッケージもインストールします。build-essentialその後,次のコマンドを実行してください。strdiffこれで準備が整いました。dtlのサンプルプログラムの1つであるstrdiffを使って2つの文字列の差分を計算してみます。,「⁠abcdef」と「dacfea」という文字列があるとしましょう。strdiffにこの2つの文字列を引数として与えて実行すると,図1のようにeditDistance(編集距離⁠)⁠,LCS,SESを計算してその結果を出力してくれます。---┛まず,1のeditDistance(編集距離)の説明からいきたいところですが,これは3のSESと関連するため,先に2のLCSについて解説し,そのあとで残りの2つをまとめて解説します。注1)執筆時点での最新版は1.12です。注2)Python製のビルドツール。Subsequence)LCSは最長共通部分列であると書きましたが,単に2つの要素列に共通して含まれる要素の列ではなく,2つの要素列の中で共通する部分で最も長い列を指します。LCSはつねに連続しているわけではありませんが,もとの要素列の順序どおりに並んでいる必要があります。これはどういうことかと言うと,「⁠abcdef」と「dacfea」に共通して含まれる文字は「a⁠」⁠,「⁠c⁠」⁠,「⁠d⁠」⁠,「⁠e⁠」⁠,「⁠f」の5つになります。これに対して,図1の結果を見ると,2つの文字列「abcdef」と「dacfea」のLCSは「acf」でした。「d」と「e」がLCSに含まれていないのは,この2つの文字がLCSに含まれてしまうと,もとの文字列のどちらかの順序どおりに並ばなくなるからです。要素「d」は文字列「abcdef」では,LCSの要素である「a」と「c」よりも後ろに出現し,そのあとは出現しません。これに対して文字列「dacfea」では「a」と「c」よりも前にだけ出現します。「e」と「f」についても,「⁠abcdef」と「dacfea」とでは順序が逆になってしまうため,両方がLCSに含まれることはあり得ません。逆に,片方だけが含まれるLCSは存在します。いうのも,図1の結果ではLCSは「acf」になっていますが,「⁠ace」もまたLCSです。「⁠acf」も「ace」も長さは3で同じなので,どちらもLCSであると言えます。このように,LCSはつねに1つとは限りません。LCSが変わると後述するSESも変わってしまうので,注意が必要です。Script)図1の結果からSESは3のようになりました。SESは先述したように「ある要素列を別の要素列に変換するための最短手順」を表します。3は「abcdef」という文字列を「dacfea」という文字列に変換するための最短手順を表しています。ふだんdiffを使っている人にとっては,これが一番なじみの深いものではないかと思います。3のSESをもう少し詳細にすると,表1のようになります。表1から読み取れるように編集距離とはSESにおける要素の「追加」と「削除」の合計を表しています。図1の1を見るとeditDistance(編集距離)は6ですので,計算どおりです。UNIX著者プロフィール久保達彦(くぼたつひこ)インフラ兼ソフトウェアエンジニア。ピクシブ株式会社所属。pixivのインフラの最適化や運用の省力化を提案・実行する傍らレコメンド・エンジンなどのソフトウェアの開発も行っている。2019」を開催しました。DAY1・DAY2の様子を注目セッションとともにお伝えします。LINEのエンジニア3名がイベントに先駆けて見どころを紹介します。コードの安全性・安定性を高める開発サイクル~テスト管理の効率を上げ,脆弱性診断を自動で行う~本連載では,連載「業務を改善する情報共有の仕掛け」を受けつつ,安全性・安定性を加えた開発サイクルについて考えていきます。若者世代から圧倒的な人気を誇るライブ配信&動画投稿コミュニティアプリ「MixChannel」(ミクチャ)の裏側(レコメンドシステムやサーバサイド開発など)について解説していきます。その他の連載CSS3アニメーションでつくるインターフェイス表現CSS3によるアニメーション表現を紹介していきます。その中でも,幅広い読者に応用してもらえるだろうインターフェイスを主なお題とします。MySQL道普請便り本連載では,MySQLを使ったアプリ開発・運用に関するノウハウをご紹介していきます。RecipeUbuntuの強力なデスクトップ機能を活用するための,いろいろなレシピをお届けします。JavaScriptセキュリティの基礎知識JavaScriptに関するセキュリティ上の問題はどこで発生し,どうすれば防ぐことができるのか?について解説していきます。〜システムをきちんと運用するための基礎知識システムは「作って終わり」ではなく,運用の中でさまざまな問題が発生します。問題の発生に備えて事前にどのような対応をしておくべきなのか,問題発生時に何をしなければならないのか,ポイントを解説していきます。きたみりゅうじの聞かせて珍プレーソフトウェア開発の現場で体験したトホホな失敗,思わずうなる珍プレーをきたみりゅうじ氏が四コママンガで紹介。Linuxのメンテナンスの傍ら,Linuxやオープンソースソフトと日々を過ごす著者が,その魅力とつきあい方を,エッセイ風味でお届けします。PRESS特別編集部員,さわやか笑顔のスーパーハカーはまちちゃんとネット大好き14歳わかばちゃんが,毎号,読者の皆さんから寄せられたおたよりを紹介します。皆さんの日頃の悩みにも答えちゃいますよ。]メールでのお知らせメールで次の案内をお送りしております。メールの配信を希望する方は,利用したい項目をチェックしてメールアドレスを入力し,[登録]ボタンをクリックしてください。UPDATES[ほぼ週間に1回]新刊メールマガジン[ほぼ週間に1回]電脳会議の各号案内[ほぼ1ヵ月半に1回]※変更する場合や停止する場合は,登録情報変更ページをご覧ください。※登録いただいたメールアドレスには,そのお知らせ以外,配信いたしません。Ltd.ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。