増井ラボノート コロンブス日和

第14回 HashInfo

この記事を読むのに必要な時間:およそ 3 分

HashInfo

次のような作業をやりたいと思ったことはないでしょうか?

  • 同じファイルがあちこちにないかチェックしたい
  • 重要なファイルだけバックアップしたい
  • 自分のアイデアを日付つきで記録したい

実はこのような仕事は,1つの単純な方法を使って実行できます。

パソコンやWebには膨大なファイルがありますが,同じファイルがあちこちに冗長に置かれていることも多いでしょう。

私の場合,同じファイルを何度もダウンロードしてしまったり写真や動画をいろんな場所にコピーしてしまったりすることがよくありますし,バックアップのつもりでコピーしたデータをさらにバックアップ対象にしてしまった結果,バックアップのバックアップ(のバックアップの……以下同様)のような無駄なデータを作ってしまうことすらあります。

こういう問題を防ぐためには,同じファイルがすでに別のところに存在するか調べれば良いわけですが,すべてのファイルの中身を比較することは現実的ではありません。しかし,ファイルの「ハッシュ値」を利用すれば,あるファイルが独自の(ユニークな)ものなのかどうかを比較的簡単に判別できます。

ハッシュ関数とハッシュ値

デジタルデータを一定サイズの数値に変換する関数をハッシュ関数と呼び,計算された値をそのデータのハッシュ値と呼びます。

最近のプログラミング言語ではa['abc']のような連想配列が使えるのが普通ですが,これを通常の計算機上に実装する場合,"abc"のような文字列に対してハッシュ関数を計算し,その数値を添字として利用することによって通常の配列と同じように扱う手法がよく利用されています。

ハッシュ値のサイズが小さい場合は,異なるデータから同じハッシュ値が計算されてしまう(ハッシュ値が衝突する)ことがありますが,ある程度大きなハッシュ値を生成する適切なハッシュ関数を用意すれば,ハッシュ値が衝突する可能性はほぼゼロにできます。また,ハッシュ値からもとのデータを計算することもほぼ不可能にできます。

ハッシュ関数はさまざまなものが考えられますが,現在はMD5やsha1というハッシュ関数が広く利用されています。このようなハッシュ関数は次のような特徴を持つため,暗号化アルゴリズムなどで広く利用されています。

  • ハッシュ値からもとのデータを知ることはできない
  • 異なるデータのハッシュ値が同じ値になることはない

ファイルデータから計算されるハッシュ値の情報(HashInfo)をうまく利用することにより,最初に述べたようなさまざまな有用な機能を実現できます。

重複ファイルの視覚化

ハッシュ値の特徴を利用すれば,手持ちのすべてのファイルのハッシュ値をあらかじめ計算しておくことにより,あるファイルが別のところにすでに存在するかを調べることができます。たとえば,movies/abc.mp4という動画とbackup/xyz.mp4という動画のハッシュ値が同じであれば,abc.mp4xyz.mp4は同じファイルだということがわかるので,たとえば両方をバックアップする意味はないと判断できます。

図1は,手持ちのパソコンのすべてのファイルのハッシュ値を計算し,それをTreemapという手法で視覚化してみたものです。同じファイルが複数ある場合,そのファイルを赤く表示しています(研究室に所属していた池滝俊太氏の卒業論文による)。

図1 自分のパソコン内で重複しているものを赤く表示したもの

図1 自分のパソコン内で重複しているものを赤く表示したもの

池滝氏は整理が得意なのか,重複するファイルは多くはないようですが,それでもかなりの部分に色がついている(ファイルが重複している)ことがわかります。

ハッシュ情報を複数の人間で共有すれば,自分が持っているファイルを他の人も持っているかどうかがわかります。図2は,研究室の数人の学生に協力してもらって,他人のパソコンまで比較対象を広げて同じ計算をしてみたものです。多くの学生はMacを利用しており,Macのシステムファイルは全員に共通であるため,図1に比べると左下部分が赤くなっています。

図2 他人とのファイル共有の視覚化

図2 他人とのファイル共有の視覚化

このように,ハッシュ関数を利用すると自分が持っているファイルの素性がなんとなく見えてくると言えるでしょう。ファイルの中身をいくら調べてもこういうことはわからないわけですが,他のファイルや他人のファイルとの比較によりファイルの特徴が見えてくることになります。

著者プロフィール

増井俊之(ますいとしゆき)

1959年生まれ。慶應義塾大学環境情報学部教授。ユーザーインターフェースの研究者。東京大学大学院を修了後,富士通半導体事業部に入社。以後,シャープ,米カーネギーメロン大学,ソニーコンピュータサイエンス研究所,産業技術総合研究所,Appleなどで働く。2009年より現職。携帯電話に搭載される日本語予測変換システム『POBox』や,iPhoneの日本語入力システムの開発者として知られる。近著に『スマホに満足してますか? ユーザインターフェースの心理学』。

コメント

コメントの記入