Yahoo 楽天 NTT-X Store全文検索用のインディックスの部分を作成しています。 ハッシュは使わないことにしましたが。 すこしだけハッシュについてまとめます (keyword : n-Gram ハッシュ インデックス)
○全文検索とインディックス ○インディックスについて ○メモリーにのるけど重いインディックスについて、 ○インデッイクスの圧縮の問題点 ○ハッシュの意義という選択 ○採用した方法について ○おわりに
まず全文検索とはなにかというと、たくさんテキストの 中から特定の単語を含むテキストを見つけるこ とです。 もしも、検索したい単語とテキストが与えれたので あれば べての文から単語を探す方法として、入力さ れた単語をテキストが含むかどうかを 一文字一文字比較していく方法が考えられます。 もしも、１０００文字のテキストがあるとして ３文字の単語が与えられたのであれば、１０００ 文字のテキストを３文字ずつ切り取って比較して いきます。これを９９７回続けるとテキストに 与えられた単語が存在するかが判ります。 以上の方法はとても簡単な方法ですが、以上の方法を ４０００件のテキストを相手に行うと、単語が含まれ ているかどうかを確認するのに。 Σ テキストの数×単語の数−キーワードの大きさ だけ比較しなくてはなりません。 昨今のコンピューターの性能が向上しているとは いえ、時間がかかります。 そこで、 与えられた テキストと単語という情報に 前処理 という情報をプラスします。 前処理情報という情報に全文検索を行う上で時間のか かる処理の結果を保持しておきます。 前処理情報は特定の単語がどの文に含まれるのかの情報 をもっています。 このようにすると、特定の単語が 含まれるかどうかを確認する方法は前処理情報にアクセス することになります。 もちろん、インディックスは保持するテキストよりも 大きくなる場合があります。ほとんどの場合、テキスト よりも大きくなるのではないでしょうか。 インディックスとはテキストがどの単語を含んでいるか を保持しているデーターの集まりだよという話でした。
優れたインディックスはとは何かというと ○多くのテキストを小さなデータにインディックスにまと めることが出来ること。 ○そして、より高速にインディクスからテキストを探し当 てること ○出来る限り多くの単語をサポートすること です。 ○新たにテキストを追加または削除した時のコストが低いこと インディックスについて-1 まずは単語と容量の関係にについて言及しておきま しょう。 検索するときには特定のテキストの中から単語が含まれ ているのかを検索するのですが単語というのが厄介です。 意味の無い文字列も単語として捉えることが出来ます。 意味が無いので検索に用いられることは無いでしょう から。割合してもよいでしょう。しかし、新たらしい 言葉が生まれることがあります。 または単語と単語 がつながって新たな単語が生まれたりします。 これらの多くの単語想定する場合、単語はテキストの 中に含まれる文字列として考えられます。 このような文字列を用いる方法をｎ-Gram 特定の辞書を持ついる方法ほ形態素解析といいます (たぶん)。
ｎ−Gramを用いて発見した単語のインディックスを作成すると非常重いデータになります。 つまり、インディックスの中のデータを探すのにも時間を要するわうになります。 単純に配列のように順番に"単語と参照先のデータ"が並ぶ場合を考えて見ましょう ｎ文字でテキストから単語をキリだすと n Σt×(テキスト−ｎ)の単語を作成します。 0
ハッシュが解決した問題 ハッシュの何が優れているのか
PC用眼鏡【管理人も使ってますがマジで疲れません】 解約手数料０円【あしたでんき】 Yahoo 楽天 NTT-X Store