こんにちは、 @kz_morita です。 今回は、タイトルの通り 『検索システム ― 実務者のための開発改善ガイドブック』 を読んだので感想とか書いていきます。 読もうとしたきっかけ 普段、検索エンジンにデータをインデックスするためのシステムの開発をしているが、検索エンジンそのものや検索についてもっと詳しくなりたいという気持ちがあるため、今回読んで見ようと思い購入しました。 目次 目次についてどんな章があったのか HP から引用します。 https://www.lambdanote.com/collections/ir-system/products/ir-system 本書について 第1章 イントロダクション 第I部 検索エンジンの基礎 第2章 検索エンジンのしくみ 第3章 テキスト解析 第4章 ポスティングリストの走査とランキングのアルゴリズム 第5章 検索エンジンへのデータ登録 第6章 検索インターフェースと検索クエリの処理 第II部 より高度な検索システムにむけて 第7章 よい検索とは 第8章 検索システムプロジェクトの始め方 第9章 検索システムの評価と課題の発見 第10章 クエリ提案とドメイン理解の支援 第11章 検索を成功させるための支援 第12章 検索結果のランキング さらに先に進むために 参考文献 索引 大まかに、二部構成になっていて、基礎編と応用編のような形でした。 基礎編は検索エンジンにおける基礎的な転置インデックスについてや、indexer、ランキングについてなどについて紹介されてました。 第二部としては、検索システムをプロジェクトとしてどう始めるのかといったところから、良い検索のためのクエリ提案やクエリの解釈、拡張などについて書かれてました。 読んだ感想など 第一部は、検索エンジンの基本的な内容が詳しく書かれていたため検索システムの開発に普段から携わってない自分には非常にわかりやすくてよかったです。 『情報検索の基礎』を以前よんでたこともあって、ポスティングリスト周りの話は非常にわかりやすかったです。 第二部のより高度な検索システムにむけてに関しては、より本格的な良い検索のための実装や研究などが紹介されてました。 特に 第11章、第12章はいろいろな手法が紹介されていました。 第11章は、クエリをどのように理解するかやクエリの書き換えなどの手法について工夫が書かれていて、第12章は検索結果のランキングについて書かれていました。 特にこの2章に関しては、正直難しい内容で内容を理解できたとはいえないですが、さまざまな手法や研究が紹介されているのと参考文献もとても多く記載されていたのでこれから学んでいくにとても役立ちそうだと感じました。 この一冊を読んだだけでも、検索システムについて考えなければいけないことや研究されていることが大量にあり難しく面白い分野だなと思えたのがよかったです。 今後の学習の良いきっかけになったと思います。

この記事は、 株式会社スタンバイアドベントカレンダー の 22 日目の記事です。 昨日は、 @jsoizo さんの Scala + GraalVM AOTコンパイル + AWS Lambdaでwebアプリを動かしたい でした。 はじめに こんにちは、 @kz_morita です。 今年の 9 月に転職をして求人検索エンジンを開発している 株式会社スタンバイに入社しました。 検索エンジンを開発している会社に入社したので、OSS の検索エンジンである Lucene について理解を深めるため、Lucene を簡単に動かしてみて実際にどのように検索エンジンが動いているのか見ていきます。 Lucene について Lucene は、OSS の検索エンジンのライブラリです。 検索エンジンのサーバーである Solr や、Elasticsearch 内で使用されています。 https://lucene.apache.org/ 以降の本文中で、 https://github.com/apache/lucene からソースコードを一部引用しながら Lucene がどのように Index を行っているかを探っていきます。 まずは使ってみる Lucene 公式の Lucene in 5 minutes を Scala でやってみます。 https://www.lucenetutorial.com/lucene-in-5-minutes.html バージョンは 8.10.1 を使用していきます。 まずは、build.sbt から。 name := "LuceneSample" version := "0.

こんにちは、 @kz_morita です。 今回は，検索エンジンなどの，クエリと文書のマッチ度に使われる BM25 の式を読み解いていきます． BM25 とは BM25 は，検索システムにおいて，クエリが文書とどれだけマッチしているかについてを計算するための手法になります． 式で表すと以下になります． $$ score(D, Q) = \sum^{n}_{i=1} IDF (q_i) \cdot \frac{f(q_i, D) \cdot (k_1 + 1)} {f(q_i, D) + k_1 \cdot (1 - b + b \cdot \frac{|D|}{avgdl})} $$ これらの式の意味を一つずつ見ていきます． 各種変数の意味 上記の式の score 関数に登場する各種変数について見ていきます． D 検索対象の特定の文書の文字列集合 |D| 検索対象の特定の文書の文字列集合の大きさ (どれくらいの単語量 ≒ 文書量) なのか avgdl 全文書の文字列集合の大きさの平均 Q 検索クエリの文字列集合 q 検索クエリの１つの単語 IDF関数 Inverse Document Frequency の略．いろんな文書に登場する一般的な単語だと値が小さく，レアな単語だと値が大きい f 関数 検索クエリの単語が対象の文書の中でどのくらい現れるかの指標．tf (Term Frequency) であったり，純粋な数のカウントだったりする．tf の場合は，以下のような式になる $$ tf = \frac{ある単語の出現回数}{全単語の合計数} $$

こんにちは、 @kz_morita です。 今回は，情報検索システムのクエリのスペルミスの修正について概要をまとめます． スペルミス修正とは Webの検索システムにおいて，ユーザーが入力したクエリがスペルミスしている可能性もあり，スペルミスの修正を行う場合もあります． Google 検索などでも，「もしかして○○」といったものが表示され，スペルミスを検知していることがわかります． 編集距離 スペル修正を行う場合以下のような実装を行う必要があるかと思います． １. 誤ったスペルのクエリに対して，もっとも近いものを選択する ２. 正しいスペルのクエリが複数ある場合には，より一般的なものを選択する ここで，もっとも近い というワードが出てきましたが，検索クエリと辞書内にある用語の距離を図る必要があります．つまり文字列と文字列の距離を判定するロジックが必要になります． そこで 編集距離 (レーベンシュタイン距離) という考え方があります． 文字列 s1 から s2 に変換するために以下のような編集走査を何回行う必要があるか？その最小値を編集距離と呼びます． 文字列に文字を挿入する 文字列から文字を削除する 文字列の文字を別の文字に置き換える 具体的に例えば，s1 = cat , s2 = dog といったケースを考えます． cat を dog に変換するためには， c -> d , a -> o , t -> g といった操作を行えば良いことから，cat と dog の編集力は 3 ということが出来ます． 一番ちかいクエリが複数あるケース たとえば，入力されたクエリが grnt だとした場合に，以下のような用語が修正先の候補として考えられます． grant grunt これらはどちらも，編集距離でいうと 1 になるため，どちらを候補として返せばよいかを決める必要があります．

こんにちは、 @kz_morita です。 情報検索のシステムについて勉強中で，以下のような記事をこれまでにまとめました． 情報検索の概要について 情報検索と転置インデックスについて 検索システムと辞書・用語 今回はワイルドカードのクエリについてまとめます． ワイルドカードクエリとは ワイルドカードクエリとは，以下のようなクエリのことを指します． pro*ing このようなクエリに対して，programming や，processing などといったワードで検索したような文書を返すことを目的にしたものです． このような検索を実現するための手法について見ていきます． 辞書とデータ構造 その前に，検索システムにおける語彙とそれを扱うデータ構造についてまとめます． 検索システムでは，検索されたワードに対して一定の正規化などを行った後にそのワードを辞書から見つけ出す必要があります．辞書から見つければその後は，ポスティングリストを参照し文書IDを得るといった流れになります． 辞書から見つけるのには，通常の全探索だと語彙数を N としたときに O(N) の計算量となります． 効率よく探すために以下のようなデータ構造が用いられます． ハッシュ 探索木 ハッシュ ハッシュは，用語を特定のハッシュ関数でハッシュ化して格納するもので，計算量は (ハッシュ計算する時間を除いて) O(1) になり高速です． ただし，デメリットもあります． まず，ハッシュの衝突です．ハッシュの計算結果は十分大きい数の数値のため通常は衝突を気にするケースはあまりありませんが，Web 検索システムなど扱う語彙の数が膨大なシステムnの場合は，本当に衝突を気にする必要がないかどうかをよく検討する必要がありそうです． ２つめに，似ている語彙を探すことが困難なことがあります．語彙がすこしでも違えば，まったく別のハッシュ値になることも普通にありえるので柔軟的に扱うのは難しいです． 探索木 探索木は，データを木構造で扱うことで O(logN) の計算量で探索できるようにしたものです． 以下のようなものが代表的です． 二分木 (binary-tree) B 木 (B-tree) 詳細はここでは扱いませんが，検索システムでは，B-tree が用いられることが多いそうです． B-tree については，下記のサイトなどがわかりやすかったです． RDBMSで使われるB木を学ぼう （1/3）－ ＠IT ワイルドカードクエリの実現方法 後方一致 まずは，以下のような後方一致のワイルドカードクエリについて考えます． prog* 後方一致のクエリに関しては，以下の図のように 探索木を辿っていって prog までたどれたらその子供の木でアクセスできる用語すべてのリストが用語リストになります． この用語のリストの論理積のクエリととらえて，あとは転置インデックスから文書IDを取得すれば prog* の検索を実現できます．

こんにちは、 @kz_morita です。 今回は，検索システムにおいてインデックスを構築する際の辞書と用語についてまとめます． 辞書と用語 検索システムは，検索クエリに合致する文書を探すことが目的のシステムです． 効率的に探すために，インデックスを事前に構築します． 情報検索と転置インデックス 上記の以前書いた記事にもありますが，インデックスには用語集である辞書と，その用語が出現する文書IDを記した，ポスティングリストがあります． 文書の取得からこの辞書を構築するまでについて手順を説明します． 辞書作成の手順 辞書を作成するには，おおまかに以下のような手順が必要になります． 文字列の取得 語彙の決定 語彙の正規化 これらについてまとめます． 文字列の取得 検索システムの検索対象である文書ですが，データある以上もとのデータは byte 列になります． これを文字列として認識するためにはいくつかの懸念点があります． 文字コード byte 列を文字列として認識するためにはその文書がどの文字コードで書かれているかということを知る必要があります． 文字コード判別の手段として以下のようなものがあります． 機械学習分類 ヒューリスティック ユーザー選択 文書メタデータ 多くは，下３つが使われているようです． ちなみに文書メタデータは，HTML の meta 属性のようなものと考えると良さそうです． ファイルタイプ ファイルのタイプにより特別な復号化が必要な場合があります． zip docx xml PDF たとえば，zip であれば解凍する必要がありますし，xml などでも，& など特別なエンコードをもとに戻したりする必要があります． 言語 アラビア語など文書の読む方向が違うような言語についても，必要があれば考慮する必要があります． 語彙の決定 文字列が取得できたら，そこから語彙を決定します．語彙を決定するために文字列から Token 列を得る必要があります． Token 化は文書の言語に依存するため，分類器などを用いて言語を推定します． たとえば，英語などは単語がスペースで区切られているため分割は比較的簡単ですが，日本語などでは区切られてないため形態素解析などで語分割を行います． とはいえ，英語などでも，アポストロフィの扱いなど考えなければならない点があります． Token 列が取得できたら，語彙として使用しないワードをストップワードとして登録して辞書から除外することがあります． たとえば，日本語の助詞などをストップワードに登録することが多いです． ストップワードをつくることのメリットしては，助詞などはとても頻度が多いため辞書とポスティングりすとの個数を大幅に減らせることにあります． ただし，歌のタイトルや，格言など，ストップワードが大きく影響をうけるような分野もあるため，Web検索などでは使用されない傾向にあるそうです． その代わりとして，言語統計などを用いて，頻出語をどのように扱い削減するかに焦点が当てられています． 語彙の正規化 語彙が決定したら，正規化を行います． 表記が異なっていても，等価として扱いたいものを一つに正規化をします． たとえば，USA と U.

こんにちは、 @kz_morita です。 今回は，検索に使われる転置インデックスについてまとめます． 検索におけるインデックスとは 情報検索システムの目的は，ユーザーが入力したクエリに関連する文書を見つけることにありますが，文書が大量にある場合は全文検索では到底探しきれないためインデックス付けを行います． インデックスをつける際は，どのような用語がどの文書に現れるかを知る必要があります． そこで，文書と用語を行列で表す方法があります．具体的には以下のようなものになります． 文書を以下のようなものだと仮定します． 文書1: I have a pen. 文書2: This is a pen. 文書3: I am grad to see you. すると，出てくる単語は，I, have, a, pen, This, is, am, grad, to, see, you となります．これらの対応表を書くと以下のとおりです． (現れるところは 1 それ以外は 0) I have a pen This is am grad to see you 文書1 1 1 1 1 0 0 0 0 0 0 0 文書2 0 0 1 1 1 1 0 0 0 0 0 文書3 1 0 0 0 0 0 1 1 1 1 1 上記を結合行列といいます．

こんにちは、 @kz_morita です。 情報検索の概要について学んだことをまとめます． 情報検索とは 情報検索の目的は，大規模なコレクションのなかから必要な情報を含むデータや文書を見つけることです． 見つけたいデータは，テキストや画像，音声など様々あります．（主にテキストの検索について語られれていることが多いと思います) テキストなどのように探したいデータは非構造的なものが多いため，どのように効率的に探すのかといったことが重要です． 情報検索の規模も，個人的な PC 内の検索といった比較的小さいものから，Web 検索といった膨大な量の文書の中から必要なデータを探すといったものがあり，その中間に各ドメインごとの検索といったものもあります． adhoc 検索 1回のクエリでユーザーがほしい文書，情報を検索して取得するものを adhoc 検索と呼びます． ユーザーがクエリとして入力していないもので，それがユーザーに対して価値がある欲しい情報であれば，関連している文書として返すことも重要になっています． 論理検索モデル Google 検索などでも採用されていると思いますが，検索したい用語を AND や OR や NOT で結合して検索できるものが 論理検索モデルです． dog AND cat などと検索して，犬と猫が同時に現れる文書を検索するようなモデルになります． 検索の方法 検索の方法は様々ありますが，まず一番シンプルなのは線形に全探索することだと思います．いわゆる grep です． こちらは，シンプルである程度の規模の文書のコレクションであれば効果的ですが以下のようなことは難しいです． 大規模のコレクションを高速に処理する より柔軟な検索クエリに対応する (たとえば，NEAR 検索 dog の近くに cat と書かれている文書 etc) 検索結果をランク付けする これらを解決するために，文書をあらかじめインデックス付けをすることが重要です． 検索システムの評価 検索システムは，どれだけユーザーの要求する結果を返せるのかというところが評価対象になります． 評価指標としては以下の２つなどがあげられます． 適合率 (precision) : 返した文書のうちに価値あるものの割合 再現率 (recall) : 関連する全文書のうち検索システムが返した文書の割合 まとめ 情報検索の概要についてざっくりまとめました．次はインデックス周りについてまとめていきたいと思います． 参考 情報検索の基礎