辞書的検索
本ページにおける辞書的検索は、いわゆる検索とは異なるものであることに留意されたい。
いわゆる「検索」は、いわゆる「辞書」と呼ばれるデータ列があるとして、「与えられたデータ列が辞書データと一致するか」という問合せに応答することをいう。「二分法」「ハッシュ法」など多数のアルゴリズムが知られている。
ここでは、「あるバイト列が入力されたときに、そのうち『辞書に登録されたバイト列』が、入力バイト列に含まれていた場合に、『どの位置に、辞書に登録された、どのバイト列が含まれているか』」を効率的に検出する方法について述べる。
「全文検索」とも呼ばれ、いわゆる検索サイトで用いられるとされる。
概要[編集]
話としては簡単だが、実行効率と記憶容量のトレードオフが、辞書データ（辞書登録語彙）が大量である場合には問題になる。
いわゆるISAMではハッシュ法が多く用いられ、プログラミング言語の予約語の検出などには語彙が少ないため多く用いられるが、自然言語処理（とくに日本語処理）になると語彙数が数万語に及ぶため、いろいろと苦労がある。
辞書は「長さが不定であり、バイト列の順序以外に『長さ』についても検索の鍵語（キー）として考慮しなければならない」という制約がある。そのため、バイト列を 256 分木で表せば済むだけの話ではあるが、「主記憶領域は狭いし、二次記憶領域はアクセスが遅い」という問題があるため、「256分木」では場所を取りすぎて扱いに困るという難点がある。そこで開発された手法がトリプル配列法だが、「それでもメモリを喰う」というので生まれた手法がダブル配列法である。アルファベット（というか、ASCII）を使っているぶんにはまったく問題はなかったが、多言語対応によってマルチバイト文字の処理が一般化した現在では、ダブル配列法は役割を終えたと考える。