Googleはなぜ的確に探せるのか？ ― 第4回

悟空、キーワードを瞬時に見つける

2008年12月26日 08時00分更新

文● 清田陽司／東京大学情報基盤センター図書館電子化研究部門助教

キーワードを素早く探し出す方法その2　～ハッシュ表～

　人からもらった名刺を整理するとき、みなさんはどんな方法を使っていますか？　几帳面な方は、1枚ずつ名刺ホルダーに入れて整理しているかもしれません。

　しかし、新しい名刺をもらうたびに1枚ずつずらしていては大変ですから、完全に名前の五十音順に並べている方はいないでしょう。「ア行」「カ行」「サ行」と区分けしたページを作って、それぞれの末尾に空いたスペースに名刺を追加するやり方が普通だと思います。

　名刺が増えて何千枚にもなってくると、だんだん探すのが大変になってきます。「ア行」だけでも何百枚にもなってしまうことでしょう。それぞれのページの中ではバラバラに並んでいるので、けっこう時間がかかってしまいそうです。

　そこで、「ア行」を「ア」「イ」「ウ」「エ」「オ」、「カ行」を「カ」「キ」「ク」「ケ」「コ」と区分けして整理し直します。「ア行」全部よりも「ア」だけの方が名刺の枚数が減るので、ずいぶん探しやすくなりました。

　でも、さらに枚数が増えてくると別の問題が起こります。「ア」で始まる名前は、「相川」「藍田」「赤坂」「秋田」「浅原」のようにたくさんありますが、「ル」で始まる名前は日本人には大変少ないのです（タレントのルー大柴さんは「ル」で始まりますが……）。名刺ホルダーの中に無駄なスペースがたくさんできてしまう一方で、「ア」で始まる名前を探すときにはやはり時間がかかってしまいます。「ア」をさらに「アイ」「アカ」「アキ」「アサ」と区分けすることにすると、ますますページ数が増えてさらに無駄が生じてしまいます。

　名前の五十音分布が偏っているのが原因じゃない？　もし「ア」から「ワ」まで名刺の数がほぼ同じならいいのに……」―――名前に限らず、あらゆる言葉に使われる文字は、もともと非常に偏ったものなのです。英語でも、「e」や「t」はとても頻繁に使われますが、「z」はほとんど使われません。「e」はなんと「z」の何十倍も使われているそうです。

　ためしに、英単語の頭文字がどれだけ偏っているかを調べてみましょう。下の図を見てください。「s」で始まる単語は8200個以上もありますが、「q」で始まる単語は300個ほどしかありません。「x」にいたってはたったの31個です。「s」と「x」の間にはなんと267倍もの偏りがあるのです。


英単語の頭文字の分布（GNU/Linuxのスペルチェック用辞書ファイル “/usr/share/dict/american-english” より）

　名刺ホルダーの偏りをなくして均等に区分けするにはどうしたらいいのでしょうか？

　ハッシュ表は、偏ったデータを均等に分割して素早く検索するための「魔法のアルゴリズム」です。「英語のキーワード列を『a』から『z』のいずれかの箱にできるだけ偏らないように区分けする」という問題を例にとって説明します。「ascii」というキーワードは、さてどの箱に入れることになるでしょうか？

　ハッシュ表でどの箱にデータを入れるかを決めるにはいろいろなアルゴリズムがあるのですが、その一つを図に示します（「アルゴリズムZ」と呼ぶことにしましょう）。

　まず、「ascii」を構成するそれぞれの文字(アルファベット)を、左の対応表を使って数字に置き換えます。すると、「0　18　2　8　8」という数字列になります。次に、隣り合う数字どうしを「左から右に引き算」して、新しい数字の列を作ります。「0－18＝－18」、「18－2＝16」、「2－8＝－6」という計算を繰り返すことで、「－18　16　－6　0」という数字列になります。今度はこの数字列を、左の対応表を使ってアルファベットに戻します（マイナスの数字は水色の部分を参照して戻していることに注意してください）。その結果、「iqua」という文字列が得られます。この操作を繰り返していくことで、最後には「u」という1文字が得られます。すなわち、「ascii」は「u」の箱に区分けされます。

　「どの箱に入れるかを決める値」のことをハッシュインデックスと呼んでいます。いろんなキーワードにアルゴリズムZを適用した結果が以下の図です。それぞれの箱に、比較的均等に区分けされていることが分かりますか？


アルゴリズムZによりハッシュインデックスを作ると、偏りが減る

　参考までに、Javaというプログラミング言語で書いたアルゴリズムZのプログラムと、その実行結果を下に示します。プログラムの意味は理解できなくてもかまわないので安心してください。プログラミング言語についてある程度勉強すれば、誰でも同じようなプログラムを書くことができます。前回の連載で述べた「明確な手順が与えられている」というアルゴリズムの性質を、アルゴリズムZが満たしているということが理解できていれば十分です。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class HashTable {
    static boolean DEBUG = true;
    public static void main(String[] args) {
        
        BufferedReader myReader = new BufferedReader(new InputStreamReader(
                System.in), 1);
        String input;
        try {
            while ((input = myReader.readLine()) != null) {
                char[] keyArray = input.toCharArray();
                HashTable hash = new HashTable();
                char result = hash.getHashIndex(keyArray);
                System.out.print(result);
                System.out.println(" " + input);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
        
        
    char getHashIndex(char[] hashKey) {
        if (hashKey.length == 1) { // 最終的なハッシュインデックス
            return hashKey[0];
        }
        // 現在の文字列を表示
        if (DEBUG) {
            for (int i = 0; i < hashKey.length; i++) {
                System.out.printf("%c(%d) ", hashKey[i], hashKey[i] - 'a');
            }
            System.out.println();
        }
        // 1文字短縮した文字列(newHashKey)を求める
        char[] newHashKey = new char[hashKey.length - 1];
        for (int i = 0; i < hashKey.length - 1; i++) {
            int x = hashKey[i] - hashKey[i + 1];
            newHashKey[i] = diff2char(x);
            if (DEBUG)
                System.out.printf("%d(%c) ", x, newHashKey[i]);
        }
        if (DEBUG)
            System.out.println("\n----");
        return getHashIndex(newHashKey);
    }
    char diff2char(int x) {
        if (x >= 0) {
            return (char) ('a' + x);
        } else {
            return (char) ('z' + 1 + x);
        }
    }
}