Googleはなぜ的確に探せるのか？ ― 第6回
悟空、単語辞書を手に入れる
2009年07月03日 12時46分更新
秘密兵器「最短経路探索アルゴリズム」の登場
「京都・東京都問題」と「西日・西日本問題」の両方をうまく解決するには、「品詞どうしの結びつきの強弱関係」と「単語の使われやすさ」を同時に扱う必要があることが分かりました。いったいどうやって実現すればよいのでしょうか？
この難しい問題を一挙に解決できる素晴らしい方法があります。それが「最短経路探索アルゴリズム」です。実は、私たちは日常生活で無意識のうちにこのアルゴリズムのお世話になっています。出張や営業回りのときに交通経路案内サイトを使っている方は多いことでしょう。「新宿から難波（大阪）まで」と入力すると、下のような検索結果が得られます。このとき、最も早いルートを素早く探せるのは、最短経路探索アルゴリズムのおかげなのです。
 |
|---|
| 画面は乗換案内（ジョルダン）における検索結果の例 |
「交通経路検索と単語の分かち書きって全然違う問題じゃないの？」――実は、単語の分かち書き問題は、「品詞どうしの結びつきの強弱関係」を「駅の乗り換え所要時間」、「単語の使われやすさ」を「駅間の乗車時間」に置き換えることでうまく解決できるのです。交通経路問題と単語の分かち書き問題を、次のように対応づけてみましょう。
| 交通経路 | 単語の分かち書き |
|---|---|
| 交通手段 | 品詞 |
| 地下鉄 | 一般名詞 |
| 路面電車 | 地名 |
| バス | 接尾辞 |
| 駅の乗り換え所要時間 | 品詞どうしの結びつき |
|
路面電車→バス 1分（乗り換えやすい） |
地名→接尾辞 （結びつきの確率が大きい） |
|
地下鉄→路面電車 5分（乗り換えにくい） |
一般名詞→地名 （結びつきの確率が小さい） |
|
地下鉄→地下鉄 5分（乗り換えにくい） |
一般名詞→一般名詞 |
| 駅間の乗車時間 | 単語の使われやすさ |
| 乗車時間が短い | 単語が使われやすい（確率が大きい） |
| 乗車時間が長い | 単語が使われにくい（確率が小さい） |
それでは、「京都・東京都問題」「西日・西日本問題」を解いてみましょう。
 |
|---|
どちらも、スタート地点から地下鉄・路面電車・バスを乗り継いでゴール地点までたどり着く問題になっています。それぞれ所要時間が最も短いルートは、簡単な計算で求められます。「東京都」は「東京|都」、「西日本」は「西|日本」に正しく分かち書きされることが分かります。
「品詞どうしの結びつきの強弱」「単語の使われやすさ」などの「人間の都合」を 「所要時間」というパソコンが簡単に扱える数字に置き換えることで、難関だった「京都・東京都問題」「西日・西日本問題」をやっと解くことができました。ここで説明した方法は「コスト最小法」と呼ばれていて、実用的な単語分かち書きツールで広く一般に使われている方法です。うまいこと考えた人がいるものですね。
コスト最小法では、交通経路での「所要時間」にあたる「コスト」という数字を人手で割り振ることで、もっともらしい分かち書きの結果を出すことができます。しかし、適切な「コスト」をたくさんのルールに対して割り当てるのは簡単ではありません。そこで、最近では大量の分かち書きされたデータから、品詞どうしの結びつきの強弱や単語の使われやすさを「確率」として計算しておき、「コスト」の代わりに使うという方法が使われるようになっています。
さて、ここまで説明した方法で、だいぶ高い精度で単語の分かち書きができるようになりました。ではこれでもう問題はないのでしょうか？ 次回は、これまでに紹介した方法ではまだ解決できない、ことばの性質に迫ります。
この連載の記事
- 第5回 悟空、秘技「分かち書き」を習う
- 第4回 悟空、キーワードを瞬時に見つける
- 第3回 悟空、キーワードを電光石火で切り出す
- 第2回 悟空、秘剣「転置インデックス」を手に入れる
- 第1回 悟空、村の中で文書を探す
- この連載の一覧へ
