数万個のファイルの重複チェックを行うプログラムをC#でささっと作る

# はじめに

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

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

さて，そのような重複するデータをチェックしてストレージの中を掃除をしたいのだが，ファイルの総数を $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` を用意したのはハッシュ値が衝突する危険性があるからだ。つまり，最終判断を人間が行うためのものだ。

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

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

# MD5 によるハッシュ値

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

```c#: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
```

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

# コード解説

## ファイル一覧の作成

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

```c#:ファイル一覧の作成
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();
```

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

```c#:大文字・小文字を区別しない比較クラス
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` として作成する。

```c#: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` が有効になると単なる文字列比較（大文字・小文字を区別しない）でソートする。

```c#:ハッシュ値に従ってインデクスをソートする
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** を呼び出して使う。

```c#: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` が有効になる。

```c#:ハッシュ値の重複するファイルを削除する
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];
}
```

# 実装コード

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

<details><summary><b>実装コードはコチラ（VBLIB.CS，UNIQFILE.CS）</b></summary>

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

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

本体を以下に示す。

```c#: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;
	}
}
```

</details>

# ビルド

筆者は基本的に **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{まあ，そりゃそうだよね}}$

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

# 参考文献

- [【MD5って何？】なんでもう使われていないのかまとめてみた！ - Qiita](https://qiita.com/SDTakeuchi/items/821a32501312d5d0b13e)

- [ハッシュ関数とハッシュ値 - Qiita](https://qiita.com/j_uehara/items/631531c17f93cecb30c2)

- [一方向ハッシュ関数についてまとめてみた。- Qiita](https://qiita.com/jackpod/items/84cf1b741c4975bbedca)

- [C#の配列の重複要素を削除する（LINQ Distinct）- Ararami Studio](https://araramistudio.jimdofree.com/2020/01/21/c-の配列の重複要素を削除する-linq-distinct/)

- [【備忘録】byte配列⇒16進数文字列へ変換 - Qiita](https://qiita.com/shusakuorz/items/f90aa57b4ddc2d01e3ea)

- [【C#】知られざる比較の高速化戦略 - Qiita](https://qiita.com/Kujiro/items/e687b089a0348d989f1b)