Signature 方式について検討する

[s-yata]

概要

Signature 方式の全文検索について検討します． 基本的な構成を検討するとともに，どのような機能が提供できるのかも検討します．

基本的な構成は，トークンをビットに割り当てた Signature を使って対象を絞り込むというものです． 転置索引より単純であり，途中まで絞り込んだ状態からも使えるのが利点になると思います．

[daijiro]

• DBの文書量に更新時間が影響を受けない
• 検索結果の絞り込みの時にも高速化に寄与できる

などすぐれた特徴があります。

[s-yata]

トークナイズについて

文字列からトークンを取り出す方法については，転置索引と同じような課題があります．

• 1-gram
  • ひらがなやカタカナには使い勝手が悪そうです．
• 2-gram
  • 一文字クエリの扱いが課題になります．
• 形態素
  • 検索漏れが課題になります．
  • 形態素の切れ目を意識するのであれば，走査の途中で分かち書きが必要になります．

以上は日本語をイメージした課題ですが，英語などの言語では Stemming が課題となります． 基本的に，走査の段階では重い処理を入れたくないというのが本音です．

[s-yata]

走査について

単純な文字列照合（たとえば Boyer-Moore (BM) 法）を使うか，あるいはオートマトンを使うかの選択肢があると思います． オートマトンを使えば，より複雑なクエリを記述できますが，代わりに処理が重くなります． 単純な例としては，英字の大文字・小文字を同じように扱うことなどが挙げられます．

どのような機能をサポートするかが重要になりそうです．

[s-yata]

Signature の長さについて

固定長にすれば処理を単純化できます． その代わり，短い文字列に合わせれば長い文字列の扱いに問題があり，逆もまた然りです．

可変長にすると，文字列の長さや 1 の割合に合わせて調節できます． その代わり，操作は複雑になり，オーバーヘッドが大きくなります．

[s-yata]

Signature の配置について

文字列の本体に近接させれば， Signature で拾ったときにキャッシュミスを減らせそうです． 一方で， Signature で拾う割合が少なければ，キャッシュミスを増やしてしまうだけかもしれません．

データ構造の自由度を考慮に入れると，文字列と Signature は別々に配置した方が良さそうです．

[s-yata]

Signature の分割について

長い文字列に対する Signature を分割する案については，クエリを構成する文字列が離れて現れるのを許容するかどうかが鍵になります．

たとえば， A and B というクエリを与えられたとき， A と B が近くに現れたときだけを拾うのであれば， Signature を分割するのは良い案かもしれません． しかし，遠くに現れたときも拾いたいのであれば，分割した Signature をわざわざ重ねて照合することになり，分割が裏目に出ます．

[s-yata]

機能について

• 文字列照合
  • 指定された文字列を含むかどうかを条件として絞り込みます．
  • 表記の揺れみたいなのは無視して，単なるバイト列として照合します．
• 正規化
  • 全角を半角にしたり，大文字を小文字にしたり，ステミングしたり，その上で文字列照合をおこないます．
  • 正規化後にトークナイズして Signature を作成すると良さそうです．
• 正規表現
  • 正規表現に該当するかどうかを条件として絞り込みます．
  • Signature で補助できるパターンとできないパターンがありそうです．

[s-yata]

トークナイズおよび不要語の問題がうまく解決できそうにないため， Signature 方式は保留とします．