リンクサジェスト/横断曖昧検索の仕組み
リンクサジェスト/横断曖昧検索とは
最近作ったプロトタイプの仮の名前
「キーフレーズ抽出」のプロジェクトから派生したが、この名前とイメージがマッチしてない
レコメンドと検索のあいのこのような振る舞いをする
リンクサジェスト
レコメンド的な側面
ここでいう「リンク」とは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くらい
Related Pages
- →連想×リンク×過去の連想の再利用×リンクサジェスト×あいまい検索×原始的連想×オーガニック連想×手繰る×xy問題×メタノート×赤リンク×有用な概念の当たり判定を拡大する×長いタイトルを刻む×長いタイトルを刻むページ→
- →word2vecによる自然言語処理×距離×三角不等式×ベクトルの類似度×軸を潰す×潰す×無視×次元削減は抽象化×抽象化×特徴量の無視×違いを無視×word2vec×deep_learning×dropout×ニューロン×汎化性能×概念×類似度×単語の意味×意味の類似度×話が飛躍する人=ベクトル検索エンジンか？×連想×次元削減してから類似度検索→
- →拡散モデル×denoising_diffusion_probabilistic_models×ddpm×high-resolution_image_synthesis_with_latent_diffusion_models×latent_diffusion_model×vae×stable_diffusion_latent_space_visualization×denoising_diffusion_implicit_models×ddim×stable_diffusionのpromptは77×768次元のテンソルになる×positional_encoding×clip×clip-vit-l-14×注意機構×u-net×オートエンコーダ×stable_diffusionのシードとプロンプトの関係×stable_diffusion埋め込みテンソル編集×stable_diffusion_inpaintの仕組み×mask_again_after_inpaint×img2prompt×clip_interrogator×blip×画家の発見×高次元においてコサイン類似度0.2は激レア×textual_inversionを試してみる×dreambooth×stablediffusion×バタフライ効果×word2vec→
- →思考の結節点2019-10-14×知識の保存形式×知識の表現形式がアップデートされなければならない×知識の表現形式のアップデート×連想のストック×連想装置×レコメンド×検索×2-hop_link×連想×知識を編むプログラム×リンクサジェスト×過去の自分の書き物と今の思考の結合支援×類似文書検索×word2vec×gyazz×転置インデックスと指差し×文書は場所×指差し×文書が階層的×長さをパラメータにしたdf×接尾辞配列×scrapboxの良さ(その2)×抽象概念×メタファー×知性を高めるシステム×アイデアの干渉効果×類似度ベースではないレコメンド×レコメンドとscrapbox×明示的なブラケティング→
- →キーフレーズ抽出×名詞句アプローチ×動詞を許容するキーフレーズ×動詞を積極的にブラケティング×「情報の共有」を「情報共有」と関連づけたい×文中に出現しないキーフレーズ×単語出現頻度×ストップワード×共起×出現集中×tf-idf×idf×rake×textrank→
- →キーフレーズ抽出×kytea×極大部分文字列×sentencepiece×textrank×フレーズベースtf-idf×liblinear×active_learning×ページ単位df×PositionRank×scrapbox統計2019-2×フレーズベースTF-IDF: 名詞句解析の応用×大きすぎるリンクの問題×参加者の多いリンクに参加するのは有益ではない×遠くとつながるリンク×自動ブラケティング×文書が階層的×bitapアルゴリズム→
- →フレーズベースtf-idf×名詞句解析×tf-idf×キーフレーズ抽出×村脇_有吾×Conundrums in Unsupervised Keyphrase Extraction×textrank×単語ベースtf-idf×文法性→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]