X

A blog about Oracle Technology Network Japan

コマンドライン・ユーティリティを書く楽しさ(パート1):重複ファイルの検索

Guest Author

※本記事は、Andrew Binstockによる"The joy of writing command-line utilities, Part 1: Finding duplicate files"を翻訳したものです。


実用的なユーティリティを含む小さなプロジェクトをステップ・バイ・ステップで作成する

著者:Andrew Binstock

2020年8月14日

自分用のコマンドライン・ユーティリティを書くというのは、Javaの知識を深めるとともに、実際に完成させるサイド・プロジェクトを作る方法としてふさわしく、実り多いものです。

たとえば、重複ファイルについて考えてみます。多くの人と同様に、筆者もラップトップに大量の音楽や写真を保存しています。時には、こういった内容を含むフォルダの管理が面倒なこともあります。ある写真や曲が重複しているかもしれないと思うものの、実際にどうなっているかがよくわからない場合は、特にそうです。この問題に対処する場合、1つまたは複数のディレクトリをスキャンして重複ファイルを見つけるユーティリティを実行できれば便利です。

本記事では、そのようなユーティリティを作成するプロジェクトについて説明します。これは、Java言語を使いこなすことができ、さらにスキルを伸ばしたいと思っている中級プログラマーにとって格好のプロジェクトです。あまり使われていないJava APIを紹介しつつ、設計やテストで発生する、予期しない問題のいくつかにも触れたいと思います。

また、本記事の全体を通して、無害と思われる小さな決断がもたらす影響に特に注目し、その代案について考えてみます。コーディングしながらこのような小さな決断を記録するという手法は、正当に評価されているとは言えません。この点については、以前の記事で説明しました。読み進めればおわかりになるでしょうが、小さな決断による影響について検討することで、ソフトウェアをさらに便利なものにするための新たな方法を見つけやすくなります。

小さなユーティリティを作るメリットの1つは、問題の領域に焦点が絞り込まれることです。しかし、設計の問題が紛れ込むことがそれによって防止されるわけではありません。まずは、この問題から取り上げることにします。

 

設計

ここでの目的は、簡単なコマンドライン・ユーティリティを作ることです。このユーティリティでは、1つまたは複数のディレクトリを指定することにより、そこに含まれるすべての重複ファイルをグループ化したリストを生成させることができます。

現時点でのコマンドラインは、次のようになります。

java –jar jar-name directory1 [directory2...directoryn]

とても便利な追加機能として、サブディレクトリを検索するかどうかをプログラムに伝える機能が考えられます。ここでは、サブディレクトリをスキャンすることをデフォルトの動作とします。そうすれば、トップレベルの音楽ディレクトリを指定することで、その下位にあるすべての曲を処理させることができます。つまり、コマンドライン・スイッチはこの機能を有効にするのではなく、無効にするオプションということになります。ここでは、–nosubdirsを使うことにします。

最後のオプションは、–hまたは–helpです。時間がたって使い方を忘れてしまったときに、説明を表示する機能です。このような小さな仕様でも、いくつかの暗黙的な選択を行いました。たとえば、ヘルプ引数にハイフン2つを使うGNUスタイルのコマンド・オプション(--help)は使用しませんでした(これはささいなことのように思えるかもしれませんが、広く使ってもらうためにこのツールを作るとしたら、ハイフン2つの形式もおそらく含めるでしょう)。

次に、出力について考えます。情報を単純に表示するだけにしたいため、データはstdoutに書き出すことにしました。この出力は、キャプチャしてテキスト・ファイルに格納する必要があります。この選択でも、コマンドライン・オプションがもう1つ省かれています。それは出力ファイルを指定する機能で、高度なバージョンには搭載されているでしょう。この機能は、–oコマンドライン・オプションで表現するのが一般的です。

現時点で、重複ファイルが見つかった場合のサンプル出力は、次のようになります。

These files are the same:
  D:\GoogleDrive\misc\NotesOnReed.txt
  D:\GoogleDrive\misc\NotesOnReed2.txt

These files are the same:
  D:\GoogleDrive\misc\Chad-smiling.jpg
  D:\GoogleDrive\misc\Chad-1988-atCamp.jpg

重複ファイルがない場合、プログラムで何も出力しないのではなく、そのことを示す1行を出力する必要があります。

ここまでは、ユーザーからの視点による基本設計のあらましを述べました。このような単純な決断により、コーディング時に機能を決める必要をなくすことができます。そういった決断はまた、YAGNI(「You ain't gonna need it」を縮めたもので、今後必要になるかもしれないがすぐには必要ない機能を作ってはいけないという意味)をどの程度認めるかを判断する際にも役立ちます。

実装を始める前に、目指すべき堅牢さのレベルを決めておく必要があります。筆者にとって、堅牢さの基本的な基準は2つあります。1つはキャッチされない例外をスローしないことです。もう1つは、何も出力されないケースがあってはならないことです。これらの決断は最低限の内容に見えますが、それによって以下に示す一連の要件が加わります。

  • 存在しないディレクトリを指定した場合、エラー・メッセージを生成する必要がある
  • 空のディレクトリを指定した場合、警告メッセージを生成する必要がある(ただし、空のサブディレクトリについては警告しない)
  • すべてのI/O例外をキャッチする必要がある(ユーザーへの報告も行う必要がある)

かなり単純に思えますが、それは一部の厄介な問題に対処しないようにしているからです。たとえば、ユーティリティの実行中にファイルが追加または削除されたディレクトリは、どのように扱うべきでしょうか。つまり、重複ファイルを重複リストに含める前に、そのファイルがまだ存在していることを確認する必要があるでしょうか。隠しファイルや、他のファイルへのシンボリック・リンクはどう扱えばよいでしょうか。ひとまずは、変更のないディレクトリのみを扱い、シンボリック・リンクはたどらないことにします。

前もってこのような決断をしておくことで、コードを書くときに余計なことに惑わされることがなくなります。

 

実装

ここで提示する設計には、主要なアクションが5つあります。コマンドライン処理、指定したディレクトリのファイル一覧の作成、ファイルのフィンガープリントの取得、重複チェックのためのフィンガープリント比較、そして出力の生成です。それぞれについて考えてみます。

ここで示すコードは、すべてJava 8をベースとしています。この選択に大きな意図があるわけではなく、それより後のJavaリリースに含まれる機能はこのプロジェクトに必要ないというだけです。コードは、FileDedupeプロジェクトのリリース1.0としてGitHubで公開しています。

コマンドライン処理:先ほど説明したコマンドラインはとてもシンプルであるため、コマンドライン・オプションを扱う無数のライブラリのいずれかを選んで使う必要はありません。ここでは、渡された引数を1つずつ調べることにします。引数は、ハイフンで始まるオプションが見つかるか、リストの最後に到達するまでは、すべてディレクトリとして扱います。このコードに、特筆すべきことはありません。

しかし、このアプローチから、ファイルとディレクトリに関連する多くのコマンドライン処理で対処されていない問題が浮かび上がります。たとえば、.と..は有効なディレクトリとして扱われるようにすべきでしょうか。そうすれば、フルパスを使わずにディレクトリを指定できることになります。これは、名前がハイフンで始まるディレクトリがなければ、うまく動作します。ハイフンで始まっていれば、ディレクトリではなく、オプションとして扱うでしょう。筆者の場合、そのようなディレクトリはないと認識しているため(少なくとも、「ない」と思っています)、この問題は無視することにします。ただし、その場合、ハイフンで始まるディレクトリはフルパスを使用して指定する必要があることをヘルプ情報に記しておくべきでしょうか。エッジ・ケースはソフトウェア開発を急ぐ開発者にとって強敵です。課題が概念的にはシンプルに見えるからです。エッジ・ケースに対処すれば、ユーティリティの信頼性が向上します。

ディレクトリのファイル一覧:ディレクトリ構造をたどり、そこに含まれる(場合によっては、そのサブディレクトリに含まれる)ファイルの一覧を取得するというのは、とてもありふれた操作です。そのため、この操作を行うJavaコードはほぼ決まっています。java.nio.fileパッケージのFiles APIには、ディレクトリをクロールするwalk()メソッドがあります。このメソッドでは、Pathエントリのストリームを返します。次のコードでは、このAPIを使って、ファイル名のストリームをArrayListに変換しています。

Files.walk( dir, skipSubDirs? 1 : Integer.MAX_VALUE )
        .filter( p -> p.toFile().isFile() )
        .peek( System.out::println )
        .collect( Collectors.toCollection( ArrayList::new ));

Files.walkにはいくつかの亜種があります。ここで使っているのは、検索するサブディレクトリの深さを整数で指定できるものです。.filterは、ファイルのみが返されるようにするために使っています。このコードでは、ファイル名の出力も行っています。このユーティリティの高度なバージョンでは、最後の機能はコマンドラインの–verboseオプションで制御することになるでしょう。

この処理で発生した例外はすべて捕捉します。例外が発生した場合は、nullではなく空のArrayListを返します。nullポインタ例外を避けるために、nullではなく空のコレクションを返すのは良いことです。しかし、これには言外の意味があります。具体的に言えば、大きなディレクトリを処理している途中で例外が発生した場合、ディレクトリにファイルがなかったとプログラムが勘違いしてしまうのです。この点については、さまざまな選択肢が考えられますが、ユーザーにエラーを通知することにしたいと思います。どのトップレベル・ディレクトリでエラーが起きたかを明示し、重複リストは返さないものとします。I/Oに問題があるディレクトリでは、後でファイルを削除したくはありません。

この選択には大きな制限が伴います。先ほどの要件に基づけば、ディレクトリにファイルがない場合はユーザーに通知します。しかし、前述のエラーによって空のArrayListが返されるため、そのメッセージが表示されてしまいます。つまり、ユーザーにはまずエラーが起きてディレクトリがスキップされることが表示され、次にディレクトリにファイルがなかったと表示されます。後ほどこれを改善したいと思った場合の適切な解決策は、Optionalを返すことです。そうすることで、呼び出す側のメソッドがエラーと有効な空のリストを区別できます。

以上でファイル一覧を取得したため、次は重複を検知する方法について考えてみます。

 

ファイルの内容のフィンガープリントを取得する

ここでの目的は、それぞれのファイルの内容を一意に識別する方法を見つけ出すことです。暗号ハッシュはファイルに対して一意な値を生成しますが、機密要件を満たすために大量の計算が必要になるため、今回のニーズの解決策としては重すぎます。たとえば、暗号ハッシュでは、1バイトや2バイトしか違わない2つのファイルからまったく異なるハッシュが生成される必要があります。今回は、ファイルが一意であれば、似ているかどうかは関係ありません。そのため、いかなる暗号計算でも、このユーティリティにメリットをもたらすことはありません。

ここで必要なものは、どんなファイルの内容からも一意な値が生成されると保証されているチェックサム生成ツールだけです。つまり、2つのファイルから同じ値が生成されれば、確実に同じ内容であることがわかればよいのです。そのようなチェックサムで特に有名なのがCRC-32です。ありがたいことに、標準Javaライブラリのjava.util.zipパッケージにはCRC-32チェックサム・ルーチンが含まれています。チェックサム生成ツールでは、このチェックサム・ルーチンを次のコードで使用しています。

CheckedInputStream check = new CheckedInputStream( file, new CRC32() );
BufferedInputStream in = new BufferedInputStream( check );

try {
    while( in.read() != -1 ) {
        // ファイルをすべて読み取る
    }
    in.close();
} catch( IOException e ) {
    System.err.println( "Error reading file: " + filename );
    throw( new IOException( e.toString() ));
}

return( check.getChecksum().getValue() );

このAPIのコードは通常とは異なります。まず、このコードの1行目で行っているように、それぞれのファイルについてCheckedInputStreamを作成し、それをJavaライブラリのCRC-32ルーチンに向ける必要があります。次に、空のループでファイルの内容をすべて読み取り、最後にCheckedInputStreamに戻ってチェックサムの値を取得しています。

Javaで提供されている選択肢は、CRC-32だけではありません。Adler-32アルゴリズムを使うこともできます。こちらの方が高速ですが、小さなファイルのチェックサムを計算する場合の信頼性は低下します。このJava APIでは他のチェックサム・アルゴリズムを追加することもできますが、このプロジェクトの場合はCRC-32でまったく問題ありません。

ここまでで、すべてのファイルのチェックサムを取得しました。他に必要なのは、そこから重複したファイルを見つけ出す方法だけです。

 

重複ファイルの検索

重複チェックにはいくつかの方法があります。1つの方法は、大きなArrayListを作成し、ファイル名とそれに対応するチェックサムからなるエントリを格納することでしょう。次に、チェックサムでソートし、ソート済みのリストをたどって2回以上出現するチェックサムを探し、それを出力します。ソートされているため、重複があれば連続して出現することになります。

ここでは、ソート処理を省いた、別のアプローチを選択しました。具体的には、チェックサム(long型)をキーとし、それに対応するファイル名のArrayListを値とするHashMapを作成します。HashMapへのエントリの追加は、チェックサムが表内にすでに存在するかどうかをチェックしながら行います。チェックサムが存在する場合は、そのチェックサムに対応するArrayListにファイル名を追加します。チェックサムが存在しない場合は、そのチェックサムと、現時点ではそれに対応するファイル名1つだけが含まれるArrayListを使って、新しいエントリを表内に作成します。次に示すように、コードは簡単です。

ArrayList tableEntry = dupesTable.get( checksum );
if( tableEntry == null ) {    // 表内でエントリがまだ見つからない場合
    ArrayList<String> entry = new ArrayList<>();
    entry.add( filename );
    dupesTable.put( checksum, entry );
}
else {
    tableEntry.add( filename ); // チェックサムが表内にすでに存在する場合
}

最初の行では、チェックサムを使ってHashMap(dupesTableという名前です)のエントリをチェックしています。nullが返された場合、そのチェックサムに対応するエントリがないことを意味します。その場合は、新しいArrayListを作成し、そこにファイル名を1つ追加してから、チェックサムとともにHashMapに追加しています。結果がnullでない場合、そのチェックサムは表内にすでに存在し、ArrayListに1つまたは複数のファイル名が格納されています。最初のget()関数で返されるのがそのArrayListであり、今度はそこに新しいファイル名を追加しています。

すべてのファイル・エントリをロードした後は、HashMapを順番にたどります。対応するファイル名のArrayListに2つ以上のエントリがあるチェックサムを探し、そのファイル名をすべてstdoutに出力します。HashMap全体をたどり終われば、それで終了です。

この設計と、大きな配列のエントリをソートするという先ほどの設計には大きなメリットがあり、それが役立つことがあるかもしれません。具体的に言えば、今後のバージョンで、重複のないファイルのみを出力するコマンドライン・オプションを追加することもできます。この機能は、バックアップ・ディレクトリがあり、オリジナルとバックアップの同期がとれているかどうかがわからない場合に便利です。その場合、重複していないファイルがあれば、そのファイルのバックアップが適切に行われなかったことを示しています。もちろん、この機能を実現する場合は、対応するArrayListに含まれるファイル名がただ1つであるチェックサムのみを出力するでしょう。

設計段階から現在まで、この機能について特に考えてはきませんでした。しかし、この機能も実現可能な実装になっているとわかるのはありがたいと言えるでしょう。

 

テスト

ここまでで説明したFileDedupeユーティリティは、それなりの規模で大変良好に動作します。60万個を超えるファイルが存在するディスク全体を対象にしても、問題なく実行されました。このような大きな規模で実行する場合、問題となるのは、不具合によって見落とされている重複があるかどうかを確実に知ることができない点です。この点から、テストに関する問題が浮かび上がってきます。

現在の多くの開発者と同じように、筆者もコーディングをしながら単体テストを記述しています。しかし、単体テストでは、ここで知る必要があることがすべてわかるわけではありません。ユーザー受入テスト(UAT)も実行する必要があります。このテストで多数のファイルを含む大きなディレクトリを作り、既知の重複ファイルを混ぜておきます。その後、すべての重複ファイルがリストに出力されることを確認する必要があります。

これを適切に行うためには、さらにコードを書く必要があります。この作業は、本プロジェクトの記事のパート2(近日公開予定)で取り上げます。筆者がその作業を終えるころ、皆さんはFileDedupeに対して十分なテストを確実に実行できると安心しているでしょう。

 

まとめ

FileDedupeのパフォーマンスは十分で、筆者のニーズにおいてはまったく問題ありません。頻繁な実行を想定したユーティリティではないため、この点はさほど心配していません。しかし、不安がないというわけではありません。FileDedupeは、友人や同僚と共有できるようにしたいと考えています。中には、かなり大量の写真や曲のコレクションを抱えている人もいるかもしれません。その場合、このユーティリティが想像よりも遅ければ、多少の感謝はしてもらえるかもしれませんが、大喜びとはいかないのではないかと心配しています。

筆者は自分が書いたソフトウェアに多少の自負を持っているため、できる限り高速に実行させたいと考えています。今は、問題なく動作することがわかり、先ほど触れたテストをすべて終えたところであるため、このソフトウェアの最適化を行うことができます。

処理に時間がかかるのは、すべてのファイルにおいてすべてのバイトを読み取ってCRC-32チェックサムを計算する部分です。もっと高速なアルゴリズムを使うこともできますが、次回記事では、興味深い最適化について説明したいと思います。通常、この方法を使えば、チェックサムを計算するのは、ファイルの一部だけで済むようになります。FileDedupeの処理速度は、CPUの速度というよりはI/Oの速度によって決まるため、この点は重要です(ただし、古いマシンやVMでは、CPUによって決まる可能性もあります)。そのため、I/Oを減らすためにできることを行えば、すべてパフォーマンスの向上に直結します。皆さんは、すべてのファイルのチェックサムを計算することなく、内容が重複しないファイルを特定する方法を思いつくことができるでしょうか。次の記事が出るまでの間、じっくりと考えてみてください。

このユーティリティのコードに外部依存性はなく、多数のコメントを含むいくつかのファイルで構成されています。コードはGitHubで公開しており、簡単にビルドできるようにMavenファイルも含めています。本記事のように、小さなプロジェクトに特化し、実用的で実践を重視した記事が好きだという方は、ぜひお知らせください。

 


Andrew Binstock

Andrew Binstock(@platypusguy):Java Magazineの前編集長。Dr.Dobb's Journalの元編集長。オープンソースのiText PDFライブラリを扱う会社(2015年に他社によって買収)の共同創業者。16刷を経て、現在もロング・テールとして扱われている、Cでのアルゴリズム実装についての書籍を執筆。以前はUNIX Reviewで編集長を務め、その前にはC Gazetteを創刊し編集長を務めた。妻とともにシリコン・バレーに住んでおり、コーディングや編集をしていないときは、ピアノを学んでいる。

Be the first to comment

Comments ( 0 )
Please enter your name.Please provide a valid email address.Please enter a comment.CAPTCHA challenge response provided was incorrect. Please try again.