はじめに

ハードディスクの中にインターネットからダウンロードしたり，キャプチャしたファイルが（推定）数万個ある。このうち全く同一内容のファイルが数百個はあり，ストレージの無駄遣いなので削除してしまいたい。

おそらく自分に限らないだろうが，長年 PC を利用しているうちに新旧データが入り混じってきて PC のストレージは徐々に混沌カオスな状況になっていき，まったく同じデータを重複してダブッて持っていることに気づかない。そのときそのときの気分（当時のマイブーム的な感じ）でファイル名を付けているため，全く同一のデータであってもファイル名まで同じとは限らないのだ。

さて，そのような重複するデータをチェックしてストレージの中を掃除をしたいのだが，ファイルの総数を $n$ 個として単純にファイル同士のバイナリ比較を行うと $n(n - 1) / 2$ 回の比較を行わなくてはならない。さすがにこれはちょっとあり得ない。

アルゴリズムを考える

三日ほど悩んで下記のアルゴリズムに辿り着いた。

ファイルを読み込んでハッシュ値を作る。ファイルの内容が異なれば滅多に衝突しないもの，ハッシュ値の計算が軽く，標準ライブラリなどに搭載されているものが良い。ということで MD5（Message-Digest Algorithm 5）を使うことにした。

次にハッシュ値のリストをソートしてやり，隣接するリストのハッシュ値が同一の場合，ファイルの内容は同一であるとみなす。

これなら計算量 $O(n\log{n})$ でいけるはずだ。

お品書き（仕様案）

.NET Framework の頃から MD5 がサポートされているということで開発言語を C# とする。
コマンドラインから実行するコンソールプログラムとする。
重複チェックを行うファイル名を複数指定できる。ファイル名の指定にはワイルドカードが使える。
重複したファイルを削除するとき，ファイル名を昇順ソートして最上位のファイルのみ残す。
ファイル名を昇順ソートするときは，Explorer 互換アルゴリズムも選択できる。
オプション /S Sub-directory を指定するとサブディレクトリ以下を検索できる。
オプション /T to Trashbox を指定すると重複するファイルをゴミ箱に送る。
オプション /V View only を指定すると重複するファイル名を表示するだけで削除しない。ちなみにオプション /T と /V を同時指定した場合は /V が優先されることにする。

オプション /T と /V を用意したのはハッシュ値が衝突する危険性があるからだ。つまり，最終判断を人間が行うためのものだ。

注意事項
コマンドラインからファイル名（検索パターン）を複数指定できるようにしたが，うっかり同じファイルを複数回指定してしまうと（当たり前だが）内容は完全一致するので削除されてしまう。

これを防ぐためには，まず対象となるファイル名をフルパスに変換してやり，名前が重複するものはリストから削除してやらなくてはならない。Windows のファイルシステムの都合上，ファイル名の大文字・小文字は区別しないモードで名前の重複チェックを行う必要がある。

MD5 によるハッシュ値

MD5 を扱うのは初めてなのでテストプログラムを作成した。

MD5HASH.CS

using System;
using System.IO;
using System.Text;
using System.Reflection;
using System.Security.Cryptography;
using System.Runtime.InteropServices;
class MD5HASH {
	static	int	Main(string[] args) {
		if(args.Length < 1) {
			Console.Error.WriteLine("ファイルの MD5 ハッシュ値を求めます。");
			Console.Error.WriteLine("");
			Console.Error.WriteLine("MD5HASH(.EXE) [ファイル名]");
			return -1;
		}
		if(!File.Exists(args[0])) {
			Console.Error.WriteLine("ファイル {0} が存在しません!!", args[0]);
			return -1;
		}
		var	bytes = File.ReadAllBytes(args[0]);
		var	md5 = MD5.Create();
		var	hash = md5.ComputeHash(bytes);
		var	s = BitConverter.ToString(hash);
		Console.WriteLine(s);
		return 0;
	}
}

テスト用コードの実行例を以下に示す。MD5 は 16 bytes（128bits）のハッシュ値を出力するが，これを BitConverter.ToString() を用いて文字列に変換すると16進数の英字は大文字になり，1 byte 毎にハイフン - が入る。

実験用コードの実行例

c:\qiita>md5hash md5hash.exe
D0-45-F1-14-2A-FC-C3-A2-44-A9-80-78-2D-FB-67-89

ハイフンが入ると余分にメモリを消費するし，比較時間も余計にかかるので後で削除したい。なお .NET 5 以降であれば Convert.ToHexString() により，ハイフン無しの16進数文字列を得られる。

コード解説

ファイル一覧の作成

List<string> list はコマンドラインから与えられたファイル名のリストが格納されている。ファイル名にはワイルドカードが含まれている場合があり，ファイル名をディレクトリ名とそれ以外に分離して検索する。オプション /S が指定されていると recursiveSearch が有効になり，サブディレクトリ以下を検索する。検索した結果であるファイル名一覧はリスト files に登録され，最後に Distinct メソッドを用いて重複要素を削除する。

ファイル一覧の作成

var	files = new List<string>();
var	opt = recursiveSearch
		? SearchOption.AllDirectories
		: SearchOption.TopDirectoryOnly;
for(int i = 0; i < list.Count; i++) {
	var	s = list[i];
	var	path = Path.GetDirectoryName(s);
	var	file = Path.GetFileName(s);
	if(path == "") {
		path = ".";
	} else if(!Directory.Exists(path)) {
		Console.Error.WriteLine("ディレクトリ {0} は存在しません!!", path);
		return -1;
	}
	path = Path.GetFullPath(path);
	files.AddRange(Directory.GetFiles(path, file, opt));
}
files = files.Distinct(new IgnoreCaseComparer()).ToList();

大文字・小文字を区別しない比較クラスは下記の通り。

大文字・小文字を区別しない比較クラス

class IgnoreCaseComparer : IEqualityComparer<string> {
	public	bool	Equals(string s1, string s2) {
		return string.Equals(s1, s2, StringComparison.OrdinalIgnoreCase);
	}
	public	int	GetHashCode(string s) {
		return s.ToUpper().GetHashCode();
	}
}

MD5 によるハッシュ作成

MD5 によるハッシュ値を計算する。すでに述べたように16進数文字列にはハイフン - が含まれるので，これを除去したものを新たにハッシュリスト hash として作成する。

MD5によるハッシュ作成

var	hash = new List<string>();
var	md5 = MD5.Create();
for(int i = 0; i < files.Count; i++) {
	if(!File.Exists(files[i])) {
		Console.Error.WriteLine("ファイル {0} が存在しません!!", files[i]);
		return -1;
	}
	var	bytes = File.ReadAllBytes(files[i]);
	var	a = md5.ComputeHash(bytes);
	var	s = BitConverter.ToString(a).Replace("-", "");
	hash.Add(s);
}

ハッシュ値のソート

ハッシュリスト hash を直接ソートしないでインデクス配列 index をソートするようにした。これはファイル名リスト files も参照する必要があるからだ。なお，ハッシュ値が同値の場合，ファイル名で比較する。デフォルトでは Explorer 互換アルゴリズムでソートするが，オプション指定により classicCompare が有効になると単なる文字列比較（大文字・小文字を区別しない）でソートする。

ハッシュ値に従ってインデクスをソートする

var	index = new int[files.Count];
for(int i = 0; i < index.Length; i++) index[i] = i;
Comparison<int>	compare = delegate(int a, int b) {
	int	ret = string.Compare(hash[a], hash[b]);
	if(ret != 0)
		return ret;
	else if(classicCompare)
		return string.Compare(files[a], files[b], StringComparison.OrdinalIgnoreCase);
	else
		return LogicalStringComparer.Compare(files[a], files[b]);
};
Array.Sort(index, compare);

Explorer 互換ソートクラスである。Win32 API を呼び出して使う。

Explorer 互換ソートクラス

class LogicalStringComparer {
	[DllImport("shlwapi.dll", CharSet = CharSet.Unicode)]
	extern	static	int	StrCmpLogicalW(string s1, string s2);
	public	static	int	Compare(string s1, string s2) {
		return StrCmpLogicalW(s1, s2);
	}
}

ハッシュ値の重複するファイルを削除する

ハッシュ値をソートしたので，前回値 prev と同じであれば削除する。なお，オプション /V が指定されると viewOnlyMode が有効になり，オプション /T が指定されると trashBoxMode が有効になる。

ハッシュ値の重複するファイルを削除する

var	prev = "";
for(int i = 0; i < index.Length; i++) {
	int	n = index[i];
	var	name = Path.GetFileName(files[n]);
	Console.Out.Write("{0} {1}", name, hash[n]);
	var	s = "";
	if(prev == hash[n]) {
		if(viewOnlyMode) {
			s = " ... (*)";		/* 何もしない */
		} else if(trashBoxMode) {
			s = " ... (TRASH)";	VBLIB.RemoveFile(files[n]);
		} else {
			s = " ... DELETED";	File.Delete(files[n]);
		}
	}
	Console.Out.WriteLine(s);
	prev = hash[n];
}

実装コード

実装コードを以下に示す。

実装コードはコチラ（VBLIB.CS，UNIQFILE.CS）

ゴミ箱に移動する VisualBasic のライブラリである。筆者は基本的に公開用の小さなプログラムはできるだけ単一のファイルに収めるように心掛けている（One Filer）が，残念ながら System.IO と Microsoft.VisualBasic.FileIO で名前空間の一部衝突が起こってしまうので分離せざるを得なかった。

VBLIB.CS

using Microsoft.VisualBasic.FileIO;
//------------------------------------------------------------------------------
// VisualBasic ライブラリクラス
//------------------------------------------------------------------------------
class VBLIB {
	//--------------------------------------------------------------------------
	// ファイルをゴミ箱へ移動する
	//--------------------------------------------------------------------------
	public	static	void	RemoveFile(string path) {
		FileSystem.DeleteFile(path, UIOption.OnlyErrorDialogs, RecycleOption.SendToRecycleBin);
	}
}

本体を以下に示す。

UNIQFILE.CS

using System;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Collections.Generic;
using System.Security.Cryptography;
using System.Runtime.InteropServices;
//------------------------------------------------------------------------------
// Explorer 互換ソートクラス
//------------------------------------------------------------------------------
class LogicalStringComparer {
	[DllImport("shlwapi.dll", CharSet = CharSet.Unicode)]
	extern	static	int	StrCmpLogicalW(string s1, string s2);
	public	static	int	Compare(string s1, string s2) {
		return StrCmpLogicalW(s1, s2);
	}
}
//------------------------------------------------------------------------------
// 大文字・小文字を区別しない比較クラス
//------------------------------------------------------------------------------
class IgnoreCaseComparer : IEqualityComparer<string> {
	public	bool	Equals(string s1, string s2) {
		return string.Equals(s1, s2, StringComparison.OrdinalIgnoreCase);
	}
	public	int	GetHashCode(string s) {
		return s.ToUpper().GetHashCode();
	}
}
//------------------------------------------------------------------------------
// エントリポイントを持つクラス
//------------------------------------------------------------------------------
class UNIQFILE {
	//--------------------------------------------------------------------------
	// メイン関数
	//--------------------------------------------------------------------------
	static	int	Main(string[] args) {
		var	classicCompare  = false;	// ファイル名のソートを単純な文字列比較で行います。
		var	recursiveSearch = false;	// ファイルを再帰的に検索します。
		var	trashBoxMode    = false;	// ファイルをゴミ箱に移動します。
		var	viewOnlyMode    = false;	// ファイルを削除しません。
		//----------------------------------------------------------------------
		// ヘルプメッセージ
		//----------------------------------------------------------------------
		if(args.Length < 1) {
			Console.Error.WriteLine("重複するファイルを削除します。");
			Console.Error.WriteLine("");
			Console.Error.WriteLine("UNIQFILE(.EXE) (オプション) [ファイル名] ...");
			Console.Error.WriteLine("");
			Console.Error.WriteLine("＜オプション＞");
			Console.Error.WriteLine("/C　ファイル名のソートを単純な文字列比較で行います。");
			Console.Error.WriteLine("　　デフォルトは Explorer 互換アルゴリズムで比較します。");
			Console.Error.WriteLine("/S　ファイルを再帰的に検索します。");
			Console.Error.WriteLine("/T　ファイルをゴミ箱に移動します。");
			Console.Error.WriteLine("/V　ファイルを削除しません。");
			Console.Error.WriteLine("");
			Console.Error.WriteLine("＜注意事項＞");
			Console.Error.WriteLine("・ファイルの内容が重複する場合，ファイル名を昇順にソートして");
			Console.Error.WriteLine("　先頭のファイルのみ残し，残りのファイルは削除します。");
			Console.Error.WriteLine("・複数のファイル名を指定できます。");
			Console.Error.WriteLine("・ファイル名の指定にはワイルドカードを使用できます。");
			return -1;
		}
		//----------------------------------------------------------------------
		// オプション解析
		//----------------------------------------------------------------------
		var	list = new List<string>();	// ファイル名（ワイルドカード可）
		for(int i = 0; i < args.Length; i++) {
			var	s = args[i];
			if(s[0] == '/' || s[0] == '-') {
				switch(s[1]) {
				  case 'C': case 'c':	classicCompare  = true;	break;
				  case 'S': case 's':	recursiveSearch = true;	break;
				  case 'T': case 't':	trashBoxMode    = true;	break;
				  case 'V': case 'v':	viewOnlyMode    = true;	break;
				  default:
					Console.Error.WriteLine("不正なオプション {0} を指定しました!!", s);
					return -1;
				}
			} else {
				list.Add(s);
			}
		}
		if(list.Count == 0) {
			Console.Error.WriteLine("ファイル名を指定して下さい!!");;
			return -1;
		}
		//----------------------------------------------------------------------
		// ファイル一覧の作成
		//----------------------------------------------------------------------
		var	files = new List<string>();
		var	opt = recursiveSearch
				? SearchOption.AllDirectories
				: SearchOption.TopDirectoryOnly;
		for(int i = 0; i < list.Count; i++) {
			var	s = list[i];
			var	path = Path.GetDirectoryName(s);
			var	file = Path.GetFileName(s);
			if(path == "") {
				path = ".";
			} else if(!Directory.Exists(path)) {
				Console.Error.WriteLine("ディレクトリ {0} は存在しません!!", path);
				return -1;
			}
			path = Path.GetFullPath(path);
			files.AddRange(Directory.GetFiles(path, file, opt));
		}
		files = files.Distinct(new IgnoreCaseComparer()).ToList();
		if(files.Count == 0) {
			Console.Error.WriteLine("ファイルが見つかりません!!");
			return -1;
		} else if(files.Count == 1) {
			Console.Error.WriteLine("ファイル数が不足しています!!");
			return -1;
		}
		//----------------------------------------------------------------------
		// MD5によるハッシュ値を生成する
		//----------------------------------------------------------------------
		var	hash = new List<string>();
		var	md5 = MD5.Create();
		for(int i = 0; i < files.Count; i++) {
			if(!File.Exists(files[i])) {
				Console.Error.WriteLine("ファイル {0} が存在しません!!", files[i]);
				return -1;
			}
			var	bytes = File.ReadAllBytes(files[i]);
			var	a = md5.ComputeHash(bytes);
			var	s = BitConverter.ToString(a).Replace("-", "");
			hash.Add(s);
		}
		//----------------------------------------------------------------------
		// ハッシュ値に従ってインデクスをソートする
		//----------------------------------------------------------------------
		var	index = new int[files.Count];
		for(int i = 0; i < index.Length; i++) index[i] = i;
		Comparison<int>	compare = delegate(int a, int b) {
			int	ret = string.Compare(hash[a], hash[b]);
			if(ret != 0)
				return ret;
			else if(classicCompare)
				return string.Compare(files[a], files[b], StringComparison.OrdinalIgnoreCase);
			else
				return LogicalStringComparer.Compare(files[a], files[b]);
		};
		Array.Sort(index, compare);
		//----------------------------------------------------------------------
		// ハッシュ値の重複するファイルを削除する
		//----------------------------------------------------------------------
		int	count = 0;
		var	prev = "";
 		for(int i = 0; i < index.Length; i++) {
			int	n = index[i];
			var	name = Path.GetFileName(files[n]);
			Console.Out.Write("{0} {1}", name, hash[n]);
			var	s = "";
			if(prev == hash[n]) {
				if(viewOnlyMode) {
					s = " ... (*)";		/* 何もしない */
				} else if(trashBoxMode) {
					s = " ... (TRASH)";	VBLIB.RemoveFile(files[n]);
				} else {
					s = " ... DELETED";	File.Delete(files[n]);
				}
				count++;
			}
			Console.Out.WriteLine(s);
			prev = hash[n];
		}
		var	fmt =   count == 0 ? "全ファイル {0} 個のうち，重複ファイルはありません。"
				: viewOnlyMode ? "全ファイル {0} 個のうち，重複ファイル {1} 個を削除できます。"
				: trashBoxMode ? "全ファイル {0} 個のうち，重複ファイル {1} 個をゴミ箱に送りました。"
				:                "全ファイル {0} 個のうち，重複ファイル {1} 個を削除しました。";
		Console.Out.WriteLine(fmt, index.Length, count);
		return 0;
	}
}

ビルド

筆者は基本的に Winows10 に備え付けの C# コンパイラでビルドできるように心掛けており，.NET Framework 世代の古い C# コンパイラでも無事ビルドが通る。

ビルド画面

c:\qiita>csc -o -w:4 UNIQFILE.CS VBLIB.CS -r:Microsoft.VisualBasic.DLL
Microsoft (R) Visual C# Compiler version 4.8.9232.0
for C# 5
Copyright (C) Microsoft Corporation. All rights reserved.

This compiler is provided as part of the Microsoft (R) .NET Framework,
but only supports language versions up to C# 5, which is no longer
the latest version. For compilers that support newer versions of the
C# programming language, see http://go.microsoft.com/fwlink/?LinkID=533240

結論というか感想

実際にこのプログラムを実行させると，それなりに時間がかかる。ハッシュ値を計算するために対象となるファイルを全部読み込んでいるからだ。

$\color{red}{\Huge\textsf{まあ，そりゃそうだよね}}$

今更だが，ファイルを全部読み込まなくとも，たとえばファイルサイズで予備チェックを行うなどすれば良かったと思う。

参考文献