重複ファイル発見ツール

このページでは、私のプログラミングしたツールを公開します。おそらくは、Javaのソースファイルが多くなるでしょう。 Javaのソースファイルで公開しているツールを利用するには、 Javaのコンパイル・実行環境が必要です。つまり、 Javaプログラムのコンパイル・実行ができる人を対象と考えています。

ここで公開するツールのライセンスは以下のとおりです。

基本的に利用・改変・再配布は御自由にどうぞ。
オリジナルの著作権 (Copyright) は高木祐介が保持します。改変版の著作権は常識で判断して下さい。十分に改変されたソフトウェアに対して私の著作権表示を含める必要はありません。
ただし、公開ツールをまるごとパクッてソフトに組み込んだ上に、なおかつ私がソースをコピーしたと称して不当に金銭や公開ツールの削除を要求するなどのような、ヒトとしてありえない真似はしないで下さい。そんな人はいないと思いますが。
公開ツールを利用することによってどのような被害を負ったとしても、私は責任をとれません。自己責任で御利用下さい。
上記の条項に違反しない限り、商用ソフトに組み込んだり、あまつさえコピーをそのまま売り付けることも構いません。しかし、私はツールの公開を止めようとはしないでしょうから、それだけでビジネスが成り立つとは思えません。
このライセンスが予告なく変更されることはありません。万一あったとしたら、私が何らかの圧力に屈したことが考えられます。そのような場合は、奴らを疑え！（って誰？）
公開ツールを改良してすばらしいツールができたら、ぜひ私にも使わせて下さい。

参考文献

Java 2 SDK, Standard Edition ドキュメント V1.4.0
プロフェッショナル Java 上, インプレス

重複ファイルを発見する

ネットワークからさまざまなファイルをゲットしてローカルディスクに保存しておくと、同じ内容のファイルが重複することがあります。例えば、次のような状況でファイルの重複が起こります。

Java SDK をダウンロードしてインストールした後、 OS を再インストールする場合に備えてダウンロードファイルをとっておいた。そのことを忘れて、OS を再インストールした時、同じ Java SDK をダウンロードした。
お気に入りの絵を絵描きさん本人のホームページからも別のホームページからもダウンロードして別々の場所に保存している。仲の良い絵描きさんたちは「年賀状」や「暑中見舞」を送り合い、受け取った絵を自分のホームページに掲載する習慣があります。人に送った絵をそのままご自分のホームページにも掲載する絵描きさんの絵は、複数箇所から重複してダウンロードしていることも多くなります。

このため、ローカルディスク内の重複ファイルを発見するツールを作りました。とりあえず重複が判明すれば、いずれかを消すなり、バックアップとして両方残すなりの対策をとることができます。

今後の希望

GUIのディレクトリ選択ダイアログを付けてみたいです。そうするとプロセス構造が全く変わるでしょうが。

使用法（バージョン3.6以降）

Javaソースをコンパイルする
javac *.java
同一内容のファイルをリストアップする。
java UniqueFiles -reverse -o uniquefiles.txt ＜重複検査をしたいファイルやフォルダ＞
uniquefiles.txtに重複ファイルのリストが出力される。

テスト環境

バージョン3.5以降は下記の環境で動作を確認しています。

CPU: Intel Celeron 2.4GHz
メモリ：512MB
OS: Windows 2000 Professional
Java SDK: J2SDK 1.4.2_04 Windows版

バージョン2から3.4までは下記の環境で動作を確認しました。

CPU: Intel Pentium III 800MHz
メモリ；256MB
OS: Debian GNU/Linux 3.0 (Woody)
Java SDK: J2SDK 1.4.2_02 Linux版

OS: Windows 2000 Professional
Java SDK: J2SDK 1.4.2_02 Windows版

バージョン3.7

2007年5月27日

バージョン3.6からの変更点は次のとおりです。

FindUniqProperties.javaとFindUniq.propertiesはバージョン3.5のものと同じです。
ファイルの先頭1ブロックだけを読み込み、簡易ハッシュ値を計算し、ハッシュ値の異なるファイルを比較しないようにしました。ファイルの先頭1ブロックのサイズは FindUniq.propertiesのinput.buffer.byte.countに設定してあります。（8192バイトとしてあります。） input.buffer.byte.countは入力バッファサイズにも使っています。あまり小さくするとハッシュ値が重複しやすくなり、バッファの効果も弱くなります。大きくしすぎるとハッシュ値の計算に時間がかかります。
バージョン3.6のファイル比較にバグがあり、入力バッファのクリアを行っていなかったため、同一内容のファイルが見逃されることがありました。バージョン3.7ではバッファの内容を1バイトずつ比較するようにしました。

バージョン3.6

2007年5月27日
バージョン3.6はファイル比較にバグがあり、入力バッファのクリアを行っていなかったため、同一内容のファイルが見逃されることがありました。バージョン3.7はこのバグが修正済みです。

2004年6月18日

バージョン3.5からの変更点は次のとおりです。

FindUniqProperties.javaとFindUniq.propertiesはバージョン3.5のものと同じです。
バージョン3.5で高速化できたので、1プロセス構成に戻しました。 UniqueFilesだけを実行すれば完了です。 FindFilesの -reverse オプションはUniqueFilesに統合して残してあります。
利点としては、中間ファイルを作らなくなり、多少速くなったようです。また、文字列で表されない変な名前のファイルにも対応しました。 Windowsで日本語名のファイルを作り、Linuxでcodepage=932を指定せずに vfatをマウントしてそのファイルをコピーした結果、私の環境にはそのような名前のファイルができており、バージョン3.5のUniqueFilesではFileNotFoundExceptionが出ていたのですが、出なくなりました。
欠点としては、CPU使用率が（また）増えてしまいました。実行中ずっとではなく上下しますが、一瞬CPU使用率100％と出ます。

バージョン3.5

2004年6月15日

バージョン3.4からの変更点は次のとおりです。

高速化。これまで遅い遅いと思っていましたが、1バイト単位でファイルを比較していたせいでした。 Windowsのタスクマネージャを見ているとCPU使用率が100％で横一直線でしたが、これはファイル読み込みを含んでいたのですね。 BufferedInputStreamを噛ませてあったのだから、1バイト単位でファイルを比較してもファイル読み込みはバッファ単位で行われるものだと思い込んでいましたが、 BufferedInputStream#read()は1バイト単位でファイルを読み込んでいたみたい。明示的にバッファへ読み込みを行うようにした結果、タスクマネージャのCPU使用率は20％を超えないようになりました。
エンコーディング、バッファサイズ、日時のフォーマットをプロパティファイルから読み込むようにしました。とは言ってもPropertiesではなくResourceBundleを使っているのですが、この2つのクラスの使い分けがまだつかめていません。 ResourceBundleを使っているため、FindUniq.properties はクラスパスの通ったディレクトリに置いておく必要があります。
InputStream/OutputStreamの代わりにReader/Writerを使うようにしました。
バージョン2.1で少しでも使用メモリを節約しようとして、全てのメソッドをstaticとしていましたが、高速化に伴い、staticを外して普通にインスタンスを生成するようにしました。やはりJavaのstaticは純粋なオブジェクト指向の観点から見ると邪道で、むやみに継承の可能性を狭めますから。

バージョン3.4

2004年4月25日

バージョン3.3からの変更点は次のとおりです。

FindFilesに -reverse オプションを追加しました。このオプションを指定すると、ファイルリストがファイルサイズの昇順ではなく降順に出力されます。
FindFilesの出力にヘッダ行を追加して、いつどんなオプションで実行したのか分かるようにしました。
UniqueFilesの出力にFindFilesからの出力のヘッダ行をコピーするようにしました。 FindFilesとUniqueFilesの実行に時間差があっても、いつ時点のファイルリストを元に実行したか分かります。
バージョン3.3では FindFiles, UniqueFiles 共に、 -o オプションを使用して標準出力でなくファイルに出力する場合にストリームをフラッシュして閉じていませんでした。このため、出力ファイルが途切れることがありました。バージョン3.4では出力ファイルストリームをフラッシュして閉じるように修正しました。

バージョン3.3

2004年4月25日
バージョン3.3は -o オプションを指定したときに、出力ファイルストリームをフラッシュして閉じていないバグがありました。バージョン3.4はこのバグが修正済みです。

2004年2月11日

バージョン3.2からの変更点は次のとおりです。

UniqueFilesの出力にファイルの最終更新時刻を追加しました。
-o パラメータで出力ファイル名を指定できるようにしました。 UniqueFilesのパラメータは入力のエンコーディング名ではなく入力ファイル名として扱うようにしました。
開発環境をEmacsからEclipseに移行しました。これまでEmacsで1段インデントはスペース4文字、2段インデントはタブ1文字となっていたため、タブストップが8文字以外の環境ではまともにソースを読めませんでしたが、タブを使わないようにしました。
Javaのプログラミングスタイルをチェックしてくれるcheckstyleというツールの Eclipseへのプラグインを2つ使ってみました。
1つ目のcheckstyleというツールと同名のプラグインは、 checkstyle-2.2というツールの古いバージョンに対応しているようです。こちらを使うと、全てのメソッドのパラメータをfinal宣言しろと警告されます。全てのメソッドのパラメータをfinalにするというのはSun推奨のJavaコーディングスタイルだそうですが、このスタイルに従うことのメリットはあまり感じられません。
2つ目のcheckclipseというプラグインは、checkstyle-3.0に対応しており、パラメータをfinalにしろとは言いません。やはりパラメータをfinal宣言することのメリットはcheckstyleツール作者にも感じられなかったのでしょうか。

バージョン3.2

2003年9月10日

バージョン3.1からの変更点は次のとおりです。

FindFiles はバージョン3.1から変わっていません。
UniqueFiles の出力が見づらかったので、 FindFiles の出力と同じ形式に変えました。
UniqueFiles の実行時間の表示がおかしかったので直しました。実行前と実行後の時刻を日付までしか表示していなかったので、時分秒まで出すようにしました。また、経過時間の年月日表示は意味不明だったので表示しないようにしました。

バージョン3.1

2003年6月28日

バージョン3からの変更は次のとおりです。

FindFiles の出力をファイルサイズ順に変更しました。バージョン3の FindFiles を実行しても、 1、2分程度で実行終了してしまうので、見やすさを優先しました。ファイルのリストを HashMap から TreeMap に変更しただけです。
空っぽの /lost+found のようなディレクトリに対して File#listFiles() が null を返すので、null チェックを加えました。 Java API ドキュメントを読む限りは、 File#isDirectory() が true であるようなファイルに対して File#listFiles() は長さ 0 の配列を返すはずですが。
UniqueFiles の実行時間を表示するようにしました。 DateFormat で遊んでみました。

バージョン3

2003年6月22日
実行時間がほぼ最適になったと思われるバージョン2.1ですが、まだ強制的に kill されないかと不安を感じさせる部分があります。そこで、バージョン3は古き良きバージョン1にならってプロセスを分割しました。

FindFiles.java ディレクトリツリー内のファイルをファイルサイズでハッシュして列挙します。
UniqueFiles.java 列挙されたファイルのリストを同サイズのファイルのグループごとに比較し、重複ファイルのグループを列挙します。

プロセスを分割したため、FindFiles の実行時間と UniqueFiles のメモリ使用量がともに10％以下になっています。つまりメモリ使用量に関しては FindFiles、実行時間に関しては UniqueFiles が多く食っていることになります。

ファイル総数3万個、重複ファイル（ペア）数1千個程度のディレクトリに対して実行してみました。 2つのプロセスをパイプでつながずに中間ファイルに落としてみたところ、 FindFiles の出力（中間ファイル）は1.5メガバイトありました。ファイル1個につき50バイト程度。ファイルパスの長さとして妥当なところでしょう。

1プロセスのバージョンでは、UniqueFiles 相当部分の実行中にも少なくとも1.5メガバイトの Map がメモリに居座っていたことになります。しかし、バージョン3の UniqueFiles の使用メモリ量（ワークセット）は同サイズのファイルグループの量と比較中の2ファイル入力分だけです。

FindFiles のメモリ使用量はファイル総数と重複ファイル数のオーダですが、バージョン1でもリスト並べ替えのためにファイル総数のオーダが必要でした。これ以上メモリ使用量を減らすためにはディスクソートやデータベースの使用などツールのレベルを越え、ビジネスソフトウェアレベル（この言い方が気に入らないなら GNUレベル）のプログラミングになります。現状で問題なく動いているので、そこまで労力を費やす気はありません。このツールは重複ファイルの個数とサイズが大きいほど時間とメモリを食うので、最終目標のディレクトリ全体を対象とする前に適当なサブディレクトリから少しずつ重複ファイルを削除していき、最終目標を対象とする時にはほとんど重複ファイルがない状態にしておくのが賢い使い方です。

バージョン2.1

2003年6月22日
バージョン2を再構成してみました。主な変更点はハッシュの計算方法です。ファイルサイズが比較的良いハッシュ値となっており、しかもファイルの内容を全く読む必要がないことに今更気づきました。また、ファイルの読み込みに BufferedInputStream を使ってみましたが、差は実感できません。

UniqueFiles.java ハッシュ計算にファイルの内容を読む必要がなくなったので、考えてみれば無駄にメモリを食っていた FileContent, FileTree をなくしました。また、この際全てのメソッドを static にして、インスタンスを不要にしました。

ファイル総数3万個、重複ファイル数（＝重複しているペア数）1千個程度のディレクトリに対して実行したところ、メモリ使用量は10メガバイトくらい、 CPUがIntel Pentium III 800EB、メモリが256メガバイトの機械で1時間くらいかかりました。バージョン2で概算したメモリ使用量1メガバイトって 10倍も違ってました。てへっ。忘れがちなファイル名の文字列が意外にメモリを食っているようです。

無駄なインスタンスを不要としたため、メモリ使用量はこのアルゴリズムの範囲ではほぼ最適になったと思います。また、実行時間に関しても、最も時間を食っていたと思われるハッシュ計算を最適化したため、ファイル総数、重複ファイル数、重複ファイルサイズのオーダとなっており、最適に近いと思います。

バージョン2：Java版

2003年6月21日

バージョン2はバージョン1の欠点を補うために作ってみました。 JavaコードならOSに依存せずに動作します。

FileComparer.java 手始めに2つのファイルの内容を比較するコマンドを作りました。 Unixのcmpコマンドのように使えます。
FileContent.java 次に、ファイルをサイズ順に並べるのではなく、ハッシュすることによって比較回数を減らすことを思いつきました。ファイル内容からハッシュ値を計算する関数は、似た内容のファイルが異なる値になるように適当に調整したものです。 FileContent.java と FileContent.java~ が異なる値になることを確認しました。また、hashCode だけでなく equals メソッドがあることを思い出して、 FileComparer.areDifferentFiles の内部の処理を FileContent.equals に移動しました。
FileTree.java 指定されたディレクトリ以下のすべてのファイルを出力するコマンドです。 find $DIR -type f に相当します。
UniqueFiles.java 本命の重複ファイルを発見するコマンドです。全リスト内のファイルをハッシュし、ハッシュ値の等しいファイルをリストに繋げておきます。新たにハッシュ値の等しいファイルが見つかるたびに、同ハッシュ値のリスト内の全てのファイルと比較して、同一内容なら重複リストに加え、異なるなら同ハッシュ値のリストに加えます。全リストの処理を終えたら、重複リストを出力します。

UniqueFilesをUniqueFiles自身のソースディレクトリに対して使ってみると、結構時間がかかってから重複のないことがわかりました。バイナリファイル総数40個くらいのディレクトリに対して使ってみると 5分ほどかかり、重複のないこととハッシュ値が良く分散していることが分かりました。最終目的であるファイル数3万個のディレクトリに対して使ってみると、めちゃめちゃ時間がかかり、なおかつ途中でシステムに kill されました。

システムに kill されるということは、メモリの使いすぎのように思えるので、ヒープ使用量を概算してみましょう。

FileComparer 使用しないので0バイト。
FileContent メンバはFileが1個。1インスタンス20バイトとしてみる。
FileTree メンバはFileが1個。1インスタンス20バイト。
UniqueFiles メンバはFileのListが1個＝10バイト×3万ファイル。中間結果であるFileContentのListのHashMapが2個＝20バイト×3万ファイル。合計で90万バイト。1メガバイトやそこらでkillされるものかなぁ？

1プロセスの利用可能メモリ制限が厳しいことを考えて、次のバージョンではバージョン1でやっていたようにプロセスを分けることにします。 UniqueFiles を300キロバイトと600キロバイトのプロセスに分割すれば、 1プロセスのメモリ使用量が3分の2に減りそうです。

ここで、kill された原因がサイズではなく時間の制限である可能性も考慮してアルゴリズムを再検討してみます。

まず、3万個のファイルをリストにする。3万ステップ。
リストからファイルを取り出し、その内容を全て読み込んでハッシュ値を計算する。ファイルサイズの最大は数メガバイト単位。平均は数百キロバイト。 BufferedInputStreamをかぶせずに FileInputStreamで1バイトずつ読み込んでいる。数百キロステップ×3万ファイル
同じハッシュ値のファイルが登録されていたら、そのファイルと比較する。ハッシュ値は良く分散されているので比較先のファイルは平均1個。数百キロステップ×重複ファイル数

合計すると数百キロステップ×3万ファイルで、ハッシュ計算に最大の時間がかかっています。重複があった場合、その2つのファイルはハッシュ計算と比較のために 2度ずつ読み込まれることになり、サイズが大きいほど無駄があります。

実行時間を縮める方法としては、ハッシュ値の計算のためにファイルの内容を全て読み込むのではなく、特定サイズだけ読み込むことが考えられます。ただし、そのためにハッシュ値の分散が悪くなっては、逆に比較回数が多くなるので、ハッシュ値の計算式や読み込むバイトの選択を工夫する必要があります。

単に実装方法の選択として、BufferedInputStream を使うだけで数百キロステップが10分の1になる可能性もあります。次のバージョンでは BufferedInputStream を使ってみることにします。

バージョン1：Unix (GNU) コマンドの組合せ

このバージョンは Linux を再インストールした時に消失してしまいました。アルゴリズムは次のとおりですが、記憶のみに頼っているのでオプションなどの正確さは怪しいです。

find $DIR -type f -print "%p" で特定のディレクトリ以下のファイルをすべてリスト出力する。
xargs ls -srt でパイプから入力されたファイルのリストをサイズ順に並べ替える。
while ["$2"]; do cmp "$1" "$2"; shift; done （シェルスクリプト）でファイルリストを引数として受け取り、前から順に隣り合った2つのファイルを比較する。

バージョン1の欠点は、同一内容のファイル A, B と同サイズで内容の異なるファイル C があり、ファイルリストに A, C, B と並んでしまった場合に重複を発見できないことです。ファイルリストで隣り合ったファイルだけでなく、同サイズのファイルすべてを比較する必要があります。また、Linuxを使っている時は良いのですが、たまにWindowsを使う時にこれらのコマンドがなくて不便です。