検索
検索(けんさく。サーチ、ときに探索とも)とは、データの集合の中から目的とするデータを探し出すこと。コンピュータによる事務データ処理において、「ソート（整列）、マージ（併合）、サーチ（検索）」の三つは初歩であり基礎であるといわれる。
概要[編集]
多くの手法があるが、最も基本的なものは「線形探索（リニアサーチ。「馬鹿探索」とも）」である。要するに頭から順々に見ていってキーが一致するものを検出すること。いちばん単純でいちばん遅いので、「線形探索よりもどれだけ速いか？」が実行効率の目安となる。
他に「バイナリー・サーチ」「ハッシュ法」「ｎ分木探索」などがある。
1 バイトは 8 ビットなので 0 ～ 255 が表されるので 256分木探索がいちばん速い。たとえば「バイト文字列の中から意味のある文字列並び（部分持ち列）をすべて検出する[1]」などするには有効そうに思える。ところが、実メモリ空間に展開するには 256分木のデータ構造はいかにもデカすぎて実メモリの容量が足りなくなりそうである。そこで二次記憶を用いようとすると、物理的なアクセスが負担になって処理が返ってこなくなる。さあ、どうするか。
たとえば「hakusaiyadaikonnadonoyasaiga」を「白菜や大根などの野菜が」と一発変換しようと思うと「白砂厭だこんなどの野菜が」が出てしまうとか、「ん」は「n」ではなく「nn」と入力しろとか「ぁ」は「xa」か「lxa」かとか、いろいろ面倒臭い話があるのである。辞書登録語彙が増える。
そのため検索エンジンの構築には膨大なマシンパワーが必要であってどこかの秘密基地みたいなところにサーバーが何十台と並んでいる写真がネット検索でヒットしたりするが、あれはこけおどしとかハッタリというか嘘の皮である。ぶっちゃけパソコンのメモリの隅っこに 128 Mb くらいあったら余裕で楽勝である。
まぁ、連続した実メモリを 128 M とかいったら相当にデカいっちゃあデカいのだが、ある一定以上の長さの文字列は数が減ってゆく。「じゅげむじ」までヒットしたらその時点で「じゅげむじゅげむごごうのすりきれかいじゃるすいぎょのうんらいまつくうらいまつ ……」と見做して「寿限無」「寿限無寿限無」「寿限無寿限無五恒の擦り切れ …… 」まで出てくれば誰も文句は言わない。つまり「出現頻度の高いコアな一万五千語くらいの辞書」があって、そこから RDBMS サーバーに紐づけられていたら仮想記憶かなんかでミリ秒単位のターンアラウンドでワードが引っ掛かってくる。あとは人間様が反応するのが 三百ミリ秒程度だから、余裕で処理できる。
これを実装する方法が「トリプル配列法」である。
トリプル配列法[編集]
トリプル配列法は生きた化石である。まだメモリサイズが数メガだった時代に、トリプル配列法を改良したダブル配列法が考案され、そちらがかれこれ三十年以上も使われていたために「原始的」なトリプル配列法は使われなくなった。じっさい、トリプル配列法にかんする正式な論文などは見たことがない。トリプル配列法は、ダブル配列法の論文から「掘り出された」ものである。
トリプル配列法のデータ構造は単純である。三要素の構造体の配列だからだ。本当は四要素だが、そこは適宜都合してくれ。
- 根を示すポインタ
- 次の節点のポインタ
- データポインタ
Java には unsigned のポインタがないので Java で説明するとややこしくなる。C 言語かなんかで考えてくれ[2]。
で、この配列要素が櫛の歯が抜けた感じのセットになっていて、ある櫛のあるところを避けて別の櫛を置くということをする。
最初の櫛はヌル文字列だが、これは別扱いするのがいいだろう。
つぎに 1 バイトである。ここが 0 要素だとしよう。そして次の文字のうち辞書に入っている文字があったら(0～255)、元の参照点にあたる要素の「根を示すポインタ」に参照点のアドレスを入れる。で、そこに参照すべきデータがあったらデータポインタにアドレスをセットする。で、辞書に続きがあったらその「次の節点のポインタ」を辿って同じことをする。これだけである。
これが簡単なようで、「次のデータをどこに置くか？」のやりくりが面倒臭いのでセッティングが面倒臭い。そんなわけで実データをあらかじめ作っておいてブートするときに実メモリ領域にそいつをガバッとコピーするのである。このとき辞書データが大雑把だと、「辞書に単語を登録しようとおもったらその場所が塞がっていて引っ越し」という恥ずかしいことになる。データの削除は簡単だ。「ここは使ってないよ」という不使用フラグを要素のどっかに立てておけばいい。そんでもってシャットダウンするときに整理して捨てちゃうなりなんなりすればいい。
ここで面倒臭いのは、「辞書引きをするまでもない形態素はハッシュテーブルかなんかに格納してアクセス速度を上げる」「使用頻度の高いコアな部分の辞書を固める」「滅多に出てこない辞書は、元の辞書の管理の都合があるから複数の辞書に分けておく」などという工夫がいることだ。
人間生活との関わり・利用[編集]
このシステムを商用化するためには結構なヒト・モノ・カネがいるので、あまり利用はされなかった。なにしろバブル景気崩壊後の「失われた二十年」のせいで開発母体がコケたからである。ただし、同人ゲーム開発程度の頭数が揃えば、三ヶ月くらいでそこそこ動くものはできるハズである。その時点の辞書語彙数はせいぜい五千語で、そのあとの課題は読みを振る部分と品詞の分類をどうするかと、辞書の項目別の管理をネット上に構築するとかいった力仕事になる。