タグ付けという考え方

以前はハッシュの本質は「分割して検索範囲を減らす」ことにあると思っていた。これはその通りであると思うが、別の見方をしてみると、「タグ付け」がハッシュ(というデータ構造)のアルゴリズムの本質であると思う。

タグ付けとは、すなわち、ある複数のオブジェクトがあったときに、1つ1つのオブジェクトにひもづけされたもう一つのデータを考えることである。ハッシュ(辞書)で言えば、オブジェクトValueがあったときに、Keyがタグである。そして、そのタグに対して、ソートしたりグループ化したりする。ハッシュの場合は、Keyにハッシュ関数を適用して出てきた値がダブった場合はグループ化して単に並べている。

この考え方はアルゴリズムの色々なところに応用されており、DSU(Decorate-Sort-Undecorate)もそうであるし、「珠玉のプログラミング」に載っていた以下の問題でもそうである。

「英語の辞書が与えられたときに、すべてのアナグラムを見つけよ」

これは、例えば、pans、pots、opt、snap、stop、topsという単語が与えられたら、まずタグをつける。つまり、

(anps pans)
(opst pots)
(opt  opt)
(anps snap)
(opst stop)
(opst tops)

というように、単語の文字列をソートした文字列でタグを付ける。次にタグをソートする。

(anps pans)
(anps snap)
(opt  opt)
(opst pots)
(opst stop)
(opst tops)

あとは、同じタグを順に取り出せばアナグラムが見つかるという訳である。タグ付けを応用したアルゴリズムはかなり便利である。今後は意識的に見てもう少し研究するつもり。