リンクサジェスト/横断曖昧検索の仕組み

リンクサジェスト/横断曖昧検索の仕組み 2020-10-02

リンクサジェスト/横断曖昧検索とは

• 最近作ったプロトタイプの仮の名前
• 「キーフレーズ抽出」のプロジェクトから派生したが、この名前とイメージがマッチしてない
• レコメンドと検索のあいのこのような振る舞いをする

リンクサジェスト

• レコメンド的な側面

• ここでいう「リンク」とはHTMLのaタグ的なものではない

  • Scrapbox的なリンク
  • 

• 単なるレコメンドとどう違うか

  • レコメンドの理由がわかる
  • 「関係ありそうな文書」のレコメンドと、「共通のキーフレーズが出現する文書」へのリンクのサジェストの違い
  • 
  • 例えばDXに関する記事に対して一見関係なさそうな統計学の記事がレコメンドされたとする(実話)
    • 理由の表示されないレコメンドでは「なんでこの記事が関係するのかな？」と頭をひねる
    • 人間、理解できないものに対して不愉快に感じがち
    • リンクサジェストでは「キーワード”dx”が共通です！」と表示されるので、人間は「いやそのdxは積分の一部だから！」と笑ってスルーできる。

横断曖昧検索

• 検索的な側面
• 作ってみたら予想以上に高速に動作した
• 人間の入力に対して即座に結果を返せる
  • →検索っぽい
• 検索として捉えると「たくさんの文書を横断して、曖昧検索をできるシステム」となる
• 例えば電子化した書籍をたくさん持っている人は、横断検索をすると「どこかで読んだんだけどな」の出典を探すのが楽だし、複数の書籍の予期しないつながりを発見できたりもする
  • これを今までの僕はPDFのテキスト化をしておいてagで検索してたのだが、これは文字列完全一致なので取りこぼしやすかったり、逆に大量に出力されてしまったりする
  • 今回のプロトタイプでは長めのクエリを入れて最長一致を探す
  • キーワードを入れて検索するというより、今書きかけの文書断片を入れて関連図書を探すイメージ
• 

仕組み

• 接尾辞配列

  • 入力文字列
    • seq = "abc-abc$" : | i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | — | — | — | — | — | — | — | — | — | | seq | a | b | c | - | a | b | c | $ |
    • 1億文字
  • 出力
  • 「seqのi文字目以降の文字列」すべてを辞書順にソートしたもの sa | i | sa | | — | — | — | — | — | — | — | — | — | — | | 0 | 7 | $||1|3|-|a|b|c|$ | | 2 | 4 | a | b | c | $||3|0|a|b|c|-|a|b|c|$ | | 4 | 5 | b | c | $||5|1|b|c|-|a|b|c|$ | | 6 | 6 | c | $||7|2|c|-|a|b|c|$ |

• 文字と単語

  • 文字であることは必要条件ではない
  • 大小比較のできる値の列なら何でも良い
  • 単語に刻んでから単語IDを振れば単語列に対しても同様に使える

• 接尾辞配列の構築コスト

  • 素朴にソートをするとO(N log N)
  • SA-IS法を使うと接尾辞配列をO(N)で構築できる
  • SA-IS法を説明するとそれだけで1〜2時間掛かりそう

• LCP配列

  • longest common prefix : | i | sa | lcp | | — | — | — | — | — | — | — | — | — | — | — | | 2 | 4 | 3 | a | b | c | $||3|0||a|b|c|-|a|b|c|$ |
  • 例えばこの部分なら3文字が共通
    • longest common prefixが3文字
  • 素朴にやると最悪計算量O(N^2)だが、O(N)にできる(Kasai法)

• 検索の仕組み: 配列の二分探索でO(M log N)

  • Mはクエリ長さ sa | i | sa | | — | — | — | — | — | — | — | — | — | — | — | | 0 | 7 | $||1|3|-|a|b|c|$ | | 2 | 4 | a | b | c | $||3|0|a|b|c|-|a|b|c|$ | | 4 | 5 | b | c | $||5|1|b|c|-|a|b|c|$ | | | | b | c | d | e | | | | | query | | 6 | 6 | c | $||7|2|c|-|a|b|c|$ |
  • 例えば”bcde”で検索したら、まず真ん中あたりの3番を見て、それよりは大きいので次は5番を見て、それより大きいので6番を見て、それより小さいので5と6の間に入ることがわかる
  • Nが8なので${\log }_{2}8=3$回で最も長くマッチする位置を発見できる
    • →発展的話題: LCP配列を使うことでO(M+log N)にすることも可能

• リンクサジェストの仕組み

  • 長文クエリのすべての開始位置から二分探索をかける
    • bcde → bcde cde ed e
    • すべての部分単語列での検索を行うことに相当する
  • 十分速い
    • クエリが1万文字ぐらいで検索に1秒程度
    • 普通の使い方なら数十ミリ秒くらい

• 文書ごとの出現回数の取得

  • 二分探索の後で前後と比較することでクエリとのLCPが求まる
    • つまりこれは「クエリと検索対象文書の間のなるべく長い共通文字列」
    • 
  • LCP配列をあらかじめ作っておくことで、その共通文字列が出現する個数を数えられる
  • 接尾辞配列を使うことでその共通文字列の出現位置を知ることができる
  • あらかじめ文書の区切り位置の配列を用意しておけばこれに対する二分探索でそれぞれの出現がどの文書の中なのかをO(log D)で求められる。Dは文書数。
  • →発展的話題、LCP配列を使うことで文書全体に対して統計値を効率的に計算できるアルゴリズムがある。検討したが今回はマッチしたものに対してだけ計算している。マッチ後の計算コストより、前計算の結果をメモリにロードすることの方が高く気配。

• 検索結果の取捨選択

  • ヒットしたものを全て出すと情報過多になる
  • 適当なルールやスコア付けをして取捨選択をする必要がある

• 曖昧検索の仕組み

  • 単語分割のタイミングで単語の見た目とダイジェスト値のペアに変換、単語の同一性判定はダイジェスト値に対して行う
  • 例えばダイジェスト時に動詞の活用形を原型にしておけば、活用を無視してマッチする
  • 「の」などの助詞をスキップしておけば「情報共有」「情報の共有」「情報を共有」などもマッチする
  • 今はやっていないが、例えば同義語や類義語を同じダイジェスト値にまとめればその揺れも吸収できる
    • word2vec的な方法でベクトルにしてからk平均法を使うことで機械的にも実現できるけど、あんまりやると「レコメンドの理由がわかる」って長所が失われる

• 実験

  • 書籍834冊分のPDFから接尾辞配列を作成
  • 構築時間1秒あたり18万文字で線形 : | books | docs | chars | load | translate | construct | chars / construct | | — | — | — | — | — | — | — | | 10 | 3028 | 1567704 | 0.06 | 5.92 | 8.34 | 187974 | | 100 | 30799 | 19774115 | 0.39 | 84.9 | 125.86 | 157111 | | 834 | 264166 | 177638808 | 3.69 | 729.6 | 1130.48 | 157135 |
  • translateは形態素解析してダイジェストし単語IDの列にする過程
  • 834冊から1Tweet140文字くらいの文書で横断検索して250msくらい