ファイルの重複検出ツールを作ろうぜ

1 ：07/10/18 〜 最終レス ：12/01/11

CD、DVD、HDDなどのファイルハッシュを計算しておきデータベースを作成して照合する
初めに64KB程度読み込んでハッシュを計算して、それが一致したら1MB程度ぶんずつ照合していく
ハッシュの計算方法は高速で、異なるファイルは異なる値を出すようにしたい
いちどブロックソーティングするといいとおもう

2 ：

前に自分で立てたスレがあったよ　すまん

3 ：

では、ここではブロックソーティング中心に研究します
解説サイトをあげておきます
http://www.geocities.jp/m_hiroi/light/pyalgo48.html
http://www.01-tec.com/document/basic_compression.html
http://ja.wikipedia.org/wiki/Burrows-Wheeler%E5%A4%89%E6%8F%9B
http://homepage3.nifty.com/DO/blocksorting.htm

4 ：

32KBから10MBまでのファイルをビット列と見なして、ブロックソーティングの符号化、復号化をなるべく高速に行うプログラムをつくろう

5 ：

ソートの仕方は、例えば2進数　1101が与えられたとき
この巡回データ　（1101　1011　0111　1110）をソートするわけですが、
これを10進に直すと　13　11　7　14　です
配列を16個用意して、13番目に1、11番目に2、7番目に3、14番目に4を代入してその他は0とします
先頭から1以上の数字を読み込むと、3　2　1　4になりこれでソートが完成します
初めに与えられた2進数の幅が大きい場合は、ランレングス圧縮 して登録するとよさそうな気がします

6 ：

ブロックソーディングがしにくいのは、00000000000000000000000000000000とか
10101010101010101010101010とかのデータが出てきた場合
どうすればいい?

7 ：

日本語テキスト、英語テキスト、exeなど別に辞書を作っておいて一度圧縮してからブロックソーディングいいかな?

8 ：

>>1
宿題スレにレス来ているよ。

9 ：

8ビットずつに区切って、ファイルごとに出現回数を求めて、類似するものを纏める
つぎに同分野ごとに出現回数からもっとも縮まる単語帳を作る

10 ：

>>1
>いちどブロックソーティングするといいとおもう
なぜブロックソーティングするのか理解不能。
何も考えずにmd5でも計算したほうがよっぽど速いだろ。
今使ってる重複検出ツールはまずファイルサイズで確認するよ。

11 ：

>>10
例えば、先頭1KだけでCRC計算するより、10Kを1Kに圧縮したものでCRCを計算した方がいいっていう発想
先頭が例えば空白ばかりのファイルが沢山あると区別がつかない

12 ：

単発作ろうスレ立てるな上げるなリアルで

13 ：

>>10
やっぱそのまま64Kとか100Kくらいをハッシュ関数にわたしたほうが良さそうだな

14 ：

重要なのは、合計のかかる時間なんだ
ファイルの読み込み、ハッシュの計算、比較の時間
どこにどの位時間をかけるかが重要だ
ファイルを沢山読めば、間違える確率は減るがそれだけ計算時間、読み込み時間がかかる
減らせば一致するファイルが多くなりこちらも比較に時間がかかる

15 ：

よしまずは、ファイルの先頭何バイト読み込めば異なるファイルだと判別できるか確かめよう

16 ：

先頭32Kでほぼ比較は出来るらしいことが判明した

17 ：

32Kを直接比較するのと、SHA512やMD5に変換して比較するのではどちらが速いのか?

18 ：

ハッシュですべき

19 ：

ファイルの先頭から32K程度だと、動画の場合でオープニングシーンがある場合は比較が難しい
(オープニング/タイトルシーンは同じ場合であることが多いから)
ある程度ファイルのオフセットを取ってから比較すると32Kも比較しなくていい場合もある
ここらへんは、1.まず最初にファイルサイズが一致したら、2.先頭32Kを比較しても一致したら、
3.オフセットを取って比較ぐらいにするといいかも

20 ：

同速度のHDD2つ、またはHDDとDVDを検索するとする
一つのファイルサイズは、2^32-1=約4Gバイト以下とする
ファイル総数は2^24=1600万以下とする
ファイルサイズと、CRC32を記録しようとすると一ファイルあたり8バイト必要
ファイル数は2^24個なので必要メモリは、最大128MB必要になる
これはスワップアウトを引き起こしてのろくなる原因になりうるが対処法はあるか?
ファイルの読み込みをドライブ別に読み込めば速度が出そう

21 ：

板違いｳｾﾞｰよ

22 ：

CRC16にしておけば、最大96MBで実用的か
あと肝心な事を忘れていた　ファイル名とそのパスを記録する必要がある　ここが一番メモリを消費する
ディレクトリ名は255文字位使えたような気がするのでメモリをくう
ハードディスクの格納方法を知ることが出来れば、文字列を全て記憶する必要はなさそうだが・・・　
あとあらかじめサイズなどで比較の必要がないものはCRCの記録までやらなければメモリは減らせるが・・・
しかし、ディスクのシーク時間を考えると、一度ファイル名やサイズを取得したら一緒に32Kくらい読み込んだ方がとくということもある
>>19
ファイルのオフセットとは何でしょうか?

23 ：

オフセットってのはファイル先頭からの距離の事

24 ：

MD5の値を使って、ファイルの重複をチェックしている。データベースには700万個の
ファイルが登録されている。
最近、複数マシンに渡ってファイルを比較する機能を追加した。

25 ：

>>1のプロファイル
・ヒキオタニート
・テラバイト級のストレージを持つ極度のny厨
・秘蔵のロリ画像・動画の収拾がつかなくなったから重複検出をせざるを得なくなった
挙句にム板でースレとかどうしようもないゴミだな。

26 ：

同一フォルダにおけるファイルとフォルダの合計数は、2^32-1個らしい　明確な記述は見つからなかったが・・
しかし、2^16個以上ある場合は無いだろうから、(a, b, c, ・・・)　abcは2バイトの数字でファイルの位置は表せるな
ツリー構造を表現できれば、親ディレクトリの情報は共有できる
>>23
>>19のいうオフセットの比較がわかりません

27 ：

ここいいよ
日本で現在最強の検索ツールundupの作者の開発ノートが置いてある
http://hp.vector.co.jp/authors/VA032597/Software/TechNote.txt
ファイルのパスだけど、一階層ずつ32ビット使ったとしてもある程度たまった時点でディスクに保存してしまえばメモリの消費から除外できるな
利用するのは最終的に重複ファイルが決まったときのみだからメモリにおいておく必要なし

28 ：

>>26
多分「オフセットを取って比較」ってのは「ファイルの先頭から一定の距離に位置するデータを比較」の意味でしょう。
「ファイルからオフセットを取得して比較」（？）じゃなくて。

29 ：

まずはドライブにあるファイルの、ファイルサイズと　先頭32KBのCRC16をメモリに格納する部分を作ろうぜ
ディレクトリ構造も保存しておいた方が良いけどコードがが煩雑になる　これも入れたやつで速度を測った方が正確か　
だれがもっとも速いアルゴリズムが作れるか競おう
CRCの計算方法はここにあるよ
http://laputa.cs.shinshu-u.ac.jp/~yizawa/logic2/chap9/index.html
http://www.geocities.co.jp/SiliconValley/4809/code/index.html
http://www.wdic.org/w/WDIC/CRC
>>28
意味理解しました　しかしずらして比較するくらいなら、一度の多くを読み込んだ方がシーク時間が短くなりそう

30 ：

>>27
そこのソフトの人の解説流し読みしたけど、かなり幼稚な印象だけど。
自画自賛？というか、もしかして1本人かな・・・
ファイルみたいな総数の判らん対象をオンメモリでソートなんて
やってる時点でソフト寿命はたかが知れてると思うよ。

31 ：

>>27>>30
他のソフトと比較した上で言ってるの？

32 ：

>>1とりあえず mail欄にsageっていれて投稿して
1,まず他のファイル重複検知ソフト(同業他社)が実装をどのようにしているのかのチェックを>>1はしたの？
2,ブロックソートとか行うと他のソフトとのハッシュ値の互換性がないけどどうするの？
　>>1が作成したアプリケーションでしか、ハッシュ値の計算ができなくなるけど…
3,代表的な使用用途・検索するファイルの数/ファイルサイズ・ハッシュ結果のバイト数をできれば教えてください。

33 ：

>>31>>32
日本一のファイル比較ツール作者のノートを読みましたよ 他のツールと比較しましたよ
>>32
ブロックソーティングはやめました
ハッシュ地に互換性は入りません　そもそもファイル全体のハッシュ値では無い為、他と一致するわけがありません
>>32
条件はこれにしましたよ
同速度のHDD2つ、またはHDDとDVDを検索するとする　一つのファイルサイズは、2^32-1=約4Gバイト以下とする
ファイル総数は2^24=1600万以下とする

34 ：

すみません　Janeでsageほ固定しました　以後気をつけます

35 ：

>>33
比較した他のツールってどれ？

36 ：

>>35
このへん　対抗馬ってなかなか無いよ　まともに動作しないのがほとんど　ここ一年程度のは調べていないが・・・
http://www.nifty.com/download/cgi-bin/vec_search.cgi?c_set=%83R%81%5B%83h&srch_max=30&key=%8Fd%95%A1&dir_path=%2Fwin%2Futil%2Ffile%2F
http://cowscorpion.com/Software/DuplicateFile.html

37 ：

最近のやつしらべたら良さそうなのがあった　上はUNDUPとそれほど変わらないかも
http://www.vector.co.jp/soft/win95/util/se257049.html
http://lucky.na.coocan.jp/ddchecker.html

38 ：

>>36
あとできればまともに動作しなかったのもおながい

39 ：

ほとんどのやつはいい加減か動作が鈍い　ファイルサイズしか調べなかったりする

40 ：

>>33
レスありがとう。Image Hash Search みたいなものを、作るのかなと思ってたんだけど。
そうではなくローカル環境で動作する重複ファイルの検知ソフトを作るということだよね？
あと>>1で書いている重複という言葉は「バイナリレベルでの完全一致」ということでいいの？
たとえば画像とかの場合はヘッダーだけ違って中身は同じというファイルも多々あるのだけど。
私の質問がわるくてごめん。>>32の3はソフト使用者がどういう用途で、
パソコンを使用しているのかを考慮して、重複検知ソフトを作っているのかという話だったりします。
変な例で悪いけど、P2P使用者とそうでない人ではHDD内にある主なファイル種類・サイズは違います。
よってソフトもそれを考慮して最適化する必要があります。

41 ：

『ほとんど』
って言葉できるだけつかわずに説明おねがい

42 ：

>>40
バイナリの完全一致ですよ　ファイルの種類での分類は考慮しない方向でいいと思います　
というのも異なる種類なら先頭の方で不一致するからです
>>41
ほとんど　＝　UNDUPや上に上げたソフト以外

43 ：

>>39
具体的に

44 ：

ｇｄｇｄ

45 ：

いい加減なツールは　>>36にある

46 ：

調べた時の条件は？

47 ：

>>1しか読んでないが、ファイルサイズとMD5を保存しておいて比較するだけでいいんじゃね？

48 ：

>>47
3GのMD5を計算するのにどれくらい時間がかかるんだろか? なるべく高速、低メモリが重要

49 ：

目的とか目標って何なの？
既に高速なツールはあるけどもっと高速なのを作りたいの？

50 ：

以前PerlとMySQLで、エロ画像の重複チェックしてたなぁ。
飽きて放置したまんまだけど。

51 ：

既に高速なツールあるとはどれですか?

52 ：

>>48
こういうのって重複したファイルを削除したいってのが目的だから、
サイズの小さいファイル(数百KBの画像とか)をターゲットにしているんじゃないの？
そこらへんが>>1に書いてないからよーわからん。

53 ：

>>52
サイズ小さくても、ディスク一杯に詰まっていたら、500G程度読み込んでMD5を計算することになるよ
なるべくディスクの読み込みを減らして比較できた方が良い

54 ：

1kb〜数gbのどんなサイズでも最高速に動くアルゴリズムなんて
30秒で思いつかなきゃ素質ないね。

55 ：

>>43
いい加減なソフトが多いのは事実だと思うよ。
・なにをもってファイル重複としているのか、マニュアルなどに書いていない。
・NTFSのリパースポイントをソフト側で考慮していない。
すぐにあげれる問題としてはこんなとこ。

56 ：

ルートディレクトリ(c:\)を入力したら、ファイル名とサイズと先頭32Kを読み込む
ファイルは読み込んだ順に連番をつける
ファイル名とその配置、ディレクトリ名はディスクに書き出し、ディレクトリ名とファイル番号とサイズとCRCはメモリに保持する　
ディレクトリがあれば最後に進める　いくつまで進めたかを記録しておく
調べるディレクトリがなければ上へ戻る

57 ：

もうｇｄｇｄって感じだな

58 ：

所詮割れ厨だしな

59 ：

>>56
最初からファイルの先頭読んでく必要ないでしょ。
同一サイズのファイルが出てきた時に初めてやればいい事だし。
つーかアルゴリズムもっと勉強しなさいよ。
辛いんだよこのスレ＞＜

60 ：

>>59
>>27をよんで下さい　
ディスクのシークにかかる時間を考慮すると、その位置にある時にまとめて同ディレクトリのファイル内容を
取得してしまった方が速いようです　
ここです
ソートを行って検索すべきファイルを減らした後で、今まではファイルサイズの順番に従って検索していたのを、
ディレクトリの並び順にCRCを計算していってメモリに記録し、後でファイルサイズ順にCRCを比較していく事にした。
テスト環境では従来の完全比較に比べ半分以下の時間ですみ、簡易検索の後に残った重複している可能性のある
ファイルを完全検索しても充分にお釣りがくる結果となった。
実際にはＭＯの様な極端にシークが遅いのでランダムアクセスが大きな負担にならない様なメディアや、
ほとんどが重複していて簡易検索では候補を絞れないためその後の完全検索で時間がかかり過ぎる場合など、
この新方式では高速化されないケースもある

61 ：

なるほど。
エントリ読みに行ったついでにクラスタサイズ程度読むのは有効かもな。

62 ：

基本はwindows APIを直接使う方がいいだろうな　速度的に　いま>>56を作っている

63 ：

普通に作ると一度実行するとファイルの中身がキャッシュされるので、メモリに収まるような少量のデータでテストすると１回目と２回目以降ではDISKアクセスに関してはまったく異なる挙動になります。
そこも考えてプログラムもテスト用データも作る必要がありますよ。

64 ：

とりあえず簡単の為にCreateFileで一度アクセス出来なかった物は存在しないものとしよう　
しばらくしたらアクセス出来る物もあるとは思うが・・・
CRCの計算、ファイルの読み込み、ファイル情報の書き出しを並列化できるとおもう
情報の書き出しはある程度サイズが貯まったらにして、CRCの計算はほとんどかからないだろうから
実質的には読み込み時間だけですむと思う

65 ：

あともっとも時間がかかるのは、サイズのでかいファイルが一致してしまう場合なんだよな
1Gのファイルが一致すれば、まともにやると2Gぶん最後まで比較しなければならなくなる
最大、比較サイズを決定してしまうという方法はある　たとえば全体の30％　OR 100M　一致すればあとは検査しないとか
あとは、1MずつにCRC計算しておいてデータベースに入れておけば半分ですむ
>>63
テストデータは作るの難しいと思うので直接CやDドライブを実験台にしようと思います

66 ：

わざわざBBSに独り言を書き込まずにはコーディングできないのかね

67 ：

1Kバイトのファイルが10万個とかある比較がと大変だな　同サイズのファイルはせいぜい1万個くらいな気はする
小さいファイルを沢山生成してテストするか　こうなると中身を読んだ方が断然いい

68 ：

頭大丈夫か

69 ：

unixのコマンドの組み合わせでできたような
http://en.wikipedia.org/wiki/Fdupes
winで動くのもあるね

70 ：

http://fx10.web.fc2.com/testdata.zip
テストデータを生成します　5分ほどかかるかと思います
現在最速ソフト
http://www.vector.co.jp/soft/win95/util/se257049.html
第二位
http://www.vector.co.jp/soft/win95/util/se257656.html

71 ：

ハードディスクの内蔵キャッシュは書き込み、読み込みなどを高速化するように並び替えするの?
それとも書き込む順番どおりなの?

72 ：

CRC32の計算方法とテーブルってわかる人いますか?

73 ：

http://kone.vis.ne.jp/diary/diaryb07.html
ここらへんにかいてあるが不明

74 ：

はやいコードをコピペすればいいか

75 ：

途中まで書いたが眠いので途中までしか無い
m ディレクトリの階層の深さ　
n 見つかったファイル総数
M 最大階層数
N 最大ファイル総数
dirname(i) 各階層のディレトリ名
dirban(i) 何番目に上のディレクトリが見つかるか
file(k) 現在調べているディレクトリでのファイル情報( 名前、サイズなと゛)
filesyori () {
path = dirname(0) +・・・+dirname(m)を開く
k=0;
if ( file(k)がファイル)

76 ：

さて、進んでいるかい？

77 ：

ファイル検索のDLLは作るから、GUI部分を作ってくれ。

78 ：

まかせろ

79 ：

誰もいなくなった？
UnDup にデータベース機能がついた様なソフトが
理想形となってるみたいですね。デスカ？

80 ：

俺が使ってるのは多分ファイルサイズくらいしか見てないと思うが、そんな死ぬほど遅いわけじゃないけどな
同サイズのファイルが大量にあると若干遅くなるけど

81 ：

>>79
それ考えたけど、データベース作成後に
ファイルが更新されているかどうかを調べるのが困難。
HDDだと書き換えられるから、全体を再チェックしなくてはいけなくなる。
それにデータベース作成時間程度かかる気がする。

82 ：

データベースをチェックしないままだと重複ではないものを、重複と間違えることが出てくるけどこれは大したことでは無い。
しかし、重複であるものを、重複とみなさないケースが出てきてこれを見つけるのが困難になる。
結局、全部検索することになりそう。　

83 ：

てか、そもそも何故DBを使うの？
重複検出を一回やるだけなら全部オンメモリで処理しても足りると思うんだけど。
後で別の重複検出をやるときにDBに入れたデータを再利用するってことなのかな？
そうそう再利用できるケースがあるとも思えないけど…そんな同じファイルを何回もHDD上に生成したりするものだろうか？
ファイルのハッシュ値と詳細を記録するとかだったらまだわかるんだが。

84 ：

DVDとCDは書き換え不能とし、それだけデータベース化するなら簡単だけどね。

85 ：

>>83
おもな利用方法はCD、DVDとの比較と思います。データベース導入ならHDDもしないと不自然だなと思うわけです。

86 ：

UNDUPを超えるソフト作ってシェアウェアにすると幾らくらい売れますか?
500円として100個は売れますか?

87 ：

UNDUPで十分なので売れません

88 ：

UNICODEや長いファイル名に対応していなくて、落ちやすいバグがありますよ
あとデータベース機能機能もつけて、UNDUPの速度を半分以下にしたら幾らくらいですか?

89 ：

シェアウェアにするなら最低でも1000円にしておけ。
500円でも1000円でも売り上げ本数は変わらんだろう。売れるかどうかは別問題だが。

90 ：

速度を半分以下にするのか。遅いな。

91 ：

シェアウェアで小ヒットするといくら位なんですか?　

92 ：

あー、昔作ったことあったわ

93 ：

シェアウェアにするほどの価値はあるのか？
どうでもいいのに金払うのが面倒だろ

94 ：

優秀な最大公約数的なソフトがフリーであるのに、
わざわざ得体の知れないシェアを使おうとは思わないな。
それに使うとしても月に一回ぐらいだろ?

95 ：

UNDUP　(600円)　に対抗して、使用制限無しで500円の販売したらいくつ位売れるのかと
思ったんです。大して売れなくても良いんですけど、
UNDUPを完全に上回ったとしたらどの位かなとおもったんです。

96 ：

自分でそういうソフトを選ぶ基準から考えてみろ。
UNDUPがあるんだし、他の、しかもシェアウェアを
わざわざ選ぶ理由なんてあるか？ゼロだろ。
買われるとしたら、検索もできないネット覚えたての
情報弱者がたまたま最初にみつけて、間違えて買うぐらいだな。
今時小学生でもありえないが。
UNDUP程度なら誰でも作れるんだし、ここでぐだぐだ
売れるかどうか、なんて書いてる奴のソフト、しかも
猿真似のシェアウェアが売れると思うか？
この程度のソフトなんて作っても金にならんぞ。
オクで転売でも始めた方が儲かるんじゃないか？

97 ：

完全フリーにして名前売った方が後々儲かるかも。

98 ：

空気読まずに書くよ
全ファイルのMD5とかSHAハッシュ取ってsortコマンド使えばええやん
殆ど重複はしないでしょ
でかいファイルは4MBくらいで読むの止めて、サイズ一緒に出力しておけばいいし

99 ：

>>98
小学生は大人になってから来てね

100read 1read

1read 100read

TOP カテ一覧 スレ一覧 削除依頼 ▲
・　次のスレ
[Tips]Borland C++Builder ちょいテク No.01
1000 1001 1110 1111 1001 1000 0110 0010
ゲームプログラムなら俺に聞け23
AndroidｱﾌﾟﾘとiPhoneｱﾌﾟﾘどっちがお勧め？ part2