Python 80行で作った検索エンジン

 (alexmolas.com)
6 ポイント 投稿者 GN⁺ 2024-02-08 | 1件のコメント | WhatsAppで共有
  • microsearchは検索エンジンの内部を自分で理解するためのおもちゃ実装で、コアの検索エンジンクラスは80行未満だが、クローラ・API・HTMLテンプレートまで含めるとプロジェクト全体はより大きい
  • 小規模なWebサイトやブログが大手検索エンジンでは見つかりにくいという問題を背景に、642件のRSSフィードから記事を収集して検索データを作成
  • asyncioベースの非同期クローリングにより収集時間は20分から20秒に短縮され、整形済み本文はParquetデータとして保存される
  • 検索は、単語をURLごとの出現回数に結びつける転置インデックスの上で動作し、結果の並び替えにはリンクベースのPageRankではなくコンテンツベースのBM25を使用
  • FastAPI UIで検索ボックスと結果ページを提供するが、クエリ演算子・n-gramインデックス・クエリ/文書拡張・クローリング中のインデックス化といった機能はまだない

microsearchの目標と範囲

  • microsearchはGitHubリポジトリで公開されているPython製検索エンジン実装
  • 目的は本番用の検索エンジンではなく、検索エンジンが内部でどのように動くかを示す使えるおもちゃの例を作ること
  • 検索対象は、Google SEO競争では見つかりにくい小規模なWebサイトやブログに近い
  • コアとなる検索エンジン実装は80行未満だが、データクローラ・API・HTMLテンプレートのような補助コードを含めるとプロジェクト全体はより大きい
  • 実装は、SolrとLuceneを扱いながら検索エンジンの動作をより深く理解しようとする過程で作られた

RSSベースのクローラ

  • 検索対象データを作るためにブログのRSSフィードをクローリングする
  • 使用したフィードは合計642件のRSSフィード
  • クローリングは、各RSSフィードから記事URLを抽出し、記事HTMLをダウンロードした後、本文テキストを整形する流れ
  • HTML整形ではBeautifulSoupでscriptとstyleを除去し、改行と空白を整えてテキストに変換する
  • aiohttpとasyncioを使った非同期クローリングにより実行時間は20分から20秒に短縮
  • 結果はURLと整形済み本文を含むDataFrameを作成し、output.parquetに保存する

転置インデックス構造

  • 検索エンジンの最初の中核データ構造は転置インデックス
  • 転置インデックスはキーワードを文書にマッピングし、特定の単語がどの文書に現れるかを高速に見つけられるようにする
  • 実装ではdict[str, dict[str, int]]形式のdefaultdictを使う
    • 外側のキーは単語
    • 内側のキーはURL
    • 内側の値は、その単語がそのURLの文書に現れた回数
  • SearchEngineクラスは2つの内部ディクショナリを持つ
    • _index: 単語ごとのURL出現回数を保存
    • _documents: URLごとの元のコンテンツを保存
  • index(url, content)はコンテンツを正規化した後、空白で分割し、各単語のURLごとの出現回数を増やす
  • bulk_index()はURLとコンテンツの一覧を受け取り、複数文書をまとめてインデックス化する
  • get_urls(keyword)はキーワードを正規化した後、その単語を含むURLと出現回数を返す

文字列正規化と基本検索

  • 文字列正規化では句読点を空白に置き換え、重複する空白を整理した後、小文字に変換する
  • 大文字小文字の差を減らすため、Fooとfooは同じキーワードとして扱われる
  • 例として2つの文書をインデックス化すると、fooの検索結果は両方の文書を返す
    • Foo: Hello, World! My name is Foo!
    • Bar: Hello, World! My name is Bar, I'm not Foo!
  • この段階では、文書が検索語を含むかどうかと何回含むかしか分からないため、結果の順序を決めるには別途ランキングが必要

BM25ランカー

  • 検索結果の並び替えにはBM25を使う
  • PageRankはリンクを基に文書をランキングするが、BM25は文書コンテンツを基にスコアを計算する
  • SearchEngineはBM25計算のためのデフォルトパラメータk1=1.5, b=0.75を持つ
  • クラスはランキング計算に必要な属性を提供する
    • posts: インデックス化されたURL一覧
    • number_of_documents: 文書総数
    • avdl: 平均文書長
  • idf(kw)は特定キーワードの逆文書頻度を計算する
    • 文書総数 N
    • そのキーワードを含む文書数 n_kw
    • log((N - n_kw + 0.5) / (n_kw + 0.5) + 1) の式を使う
  • bm25(kw)は、そのキーワードを含む各URLについてBM25スコアを計算する
  • search(query)はクエリを正規化して単語に分割した後、各単語のBM25スコアをURLごとに合算して返す
  • 例ではfooだけを検索するとFoo文書のスコアがBarより高くなり、foo barを検索するとBar文書のスコアがより高くなる

FastAPIインターフェース

  • 検索エンジンは小さなFastAPIアプリとして公開される
  • アプリはSearchEngineインスタンスを作成し、起動時にParquetデータからURLとコンテンツを読み込んでbulk_index()でインデックス化する
  • 主なルートは3つ
    • /: 検索ページをレンダリングし、インデックス化された記事一覧を渡す
    • /results/{query}: クエリを検索し、上位5件のURLを結果ページに表示する
    • /about: 紹介ページをレンダリングする
  • 結果はスコアの降順で並べた後、top-N URLだけを選択する
  • UIとUXには大きな改善余地があるが、検索は高速に動作し、結果も悪くない

欠けている機能と限界

  • 実装には、実際の検索エンジンで期待されるいくつかの機能が欠けている
  • クエリ演算子がない
    • たとえばGoogleのhow to build a search engine -solrのように特定の単語を除外する検索はサポートしていない
  • n-gramインデックスがない
    • "search engine"のように2語が特定の順序で現れる文書だけを探す方式はサポートされていない
  • クエリまたは文書拡張がない
    • engineを検索しても、enginesを含む文書は自動では検索されない
  • クローリングとインデックス化が分離されている
    • 文書を受け取ったら即座にインデックス化する形で統合でき、この過程も非同期化できる

次のステップ

  • このプロジェクトを通じて、Solrが内部でどのように動作するかについての直感がさらに得られた
  • IO中心の作業では非同期コードが大きな効果を発揮することも確認できた
  • 次のステップは、検索エンジンにセマンティック検索機能を追加すること
  • 埋め込みモデルとANNを実験してきており、その機能をmicrosearchに組み込むのが次の作業

関連記事

1件のコメント

 
GN⁺ 2024-02-08
Hacker News のコメント

  • これは本当にすばらしい。ローカルテスト用にかなり速い BM25 検索エンジンを Pandas で作っているところ: https://github.com/softwaredoug/searcharray
    Pandas を使う理由は、BM25 だけでは足りず、新しさ・人気度のような他の要素を pandas/numpy で簡単に計算して組み合わせたいから
    ちなみに フレーズ検索が難しい部分。フレーズマッチングには境界ケースが多く、slop のようなものも考慮する必要がある。位置情報もできるだけ少ないメモリに圧縮しなければならない: https://github.com/softwaredoug/searcharray/blob/main/searcharray/utils/roaringish.py

    • おもちゃプロジェクトで フレーズマッチングを扱ってみた: https://github.com/vasilionjea/lofi-dx/blob/main/test/search/inverted-search.test.ts#L140
      かなり徹底的にテストしたつもりだが、フィードバックをもらえるとうれしい。位置情報はデルタエンコードして base36 でエンコードした
    • センチメント分析を入れたことがフレーズ処理に役立ったのか、それともむしろ害になったのか気になる。フレーズは扱いが難しく、性能を改善するには何ができるか考えている
    • この記事をこんなに早く見つけてコメントしたのが気になる。関心キーワードを探すためにトップページを巡回する 検索監視ツールのようなものを使っているのか、それとも偶然なのか知りたい

  • その通り。検索で難しい部分の大半は データ規模を扱うところにある。ロジック自体は驚くほど簡単だったり、簡単に作れたりする
    もちろん際限なく複雑にもできるが、このプロジェクトは不要な部分をうまく削ぎ落としている。検索エンジンをより大きくする問題ではなく、データを物理的により小さくする、あるいは S/N 比を高める問題として捉えれば、かなり遠くまで行ける

  • src/microsearch/engine.pyを見ると SearchEngine.__init__(self, k1: float = 1.5, b: float = 0.75) のようなコードがあるが、k1 や b が何なのかまったく分からず、ファイル全体にコメントが一つもない
    最近は コメントは流行りではないのだろうか？ _documents はキーが URL で値がその URL の内容のように思えるが、違うかもしれない。検索エンジンの作り方を学び、拡張できる資料になり得たはずなのに、ドキュメント化されていないせいでコード品質が惜しい

    • その部分は記事で説明されていて、記事自体がコードの ドキュメントの役割を果たしている。BM25 のリンクは数学的背景につながっており、BM25 のパラメータを少し調べれば、どう選ぶかを扱った関連記事も出てくる
    • 記事タイトルを目を引くものにするには、コード行数をできるだけ減らす必要があった ;)
      冗談はさておき、普通はドキュメントとコードが一緒にある方がよいという点には同意する。ただ、この場合は教育用プロジェクトなのでコードとドキュメントを分け、ブログ記事でコードをドキュメント化することにした
    • モバイルなので詳しくは見られないが、k1 と b は TF-IDF や BM25 で使われる標準的な 重み値で、ここでは BM25 側のもの
      コメントがあれば便利だが、この問題に慣れている人にはすぐ分かる名前でもある
    • k1 と b は BM25 ランキング関数の調整パラメータ。原著者が新しく作った名前ではなく、ほぼすべての実装と教科書でこの変数名が使われている
      情報検索分野を知る人が理解するには、むしろ k1 と b と名付けるのが正しい: https://en.wikipedia.org/wiki/Okapi_BM25
    • a: float のような流れを見ると、Rich Hickey の「必要なのは型ではなく、適切な名前だ」という講演をいつも思い出す
      Go から来たように感じる、説明のない一文字変数名を使い、型システムを名前の補助ツールのように濫用する傾向が本当に嫌いだ。名前はプログラムが何をするかについての 意味情報を伝えられるのだから、きちんと使うべき

  • 外部依存を使っておきながら、全体の \r\n の数ではなく コード行数を自慢することに何の意味があるのか分からない
    コードベースを測る SI 単位はないが、認知負荷は何らかの形で測るべきだと思う

    • 公式な基準ではないが、私たちのチームでは時々 https://grugbrain.dev になぞらえて「このコードは grug ではない」とか「このコードはかなり grug だ」と言う
    • 80行の検索エンジン自体は外部依存を使っていない。collections、math、string だけをインポートしていて、すべて標準ライブラリ
      ただ、より正確には「検索エンジンエンジン」と呼ぶのが正しいかもしれない。クローラーとインターフェースはその80行には含まれていないが、何らかの形で必要で、提示された実装は行数とライブラリをかなり増やしている。それでも、それらのライブラリは検索エンジン自体に関係するものではない。pandas や fastapi のような一般的な依存まで数え始めるなら、OS の何百万行やネットワークカードのファームウェア、ハードウェアの複雑さまで数えなければならないかもしれない
    • こういうものを 80行で作れるようになった産業の成果を祝ってはいけない理由があるのか？
    • ここでは意味がある。「Python 4000行で作った検索エンジン」だったら大半の人は素通りしただろうが、80行なら一度見てみるだけの短さだから
    • 昔ながらの方法としては 循環的複雑度 がある

  • 気に入った。検索エンジンと一緒に使える 20行未満のレコメンドエンジンも可能。クリックした URL のセッションログを保存しているなら、各セッションで現在の URL の後ろにあるスライディングウィンドウを見て、近いリンクほど高い重みを与えて推薦リストを作れる
    推薦結果を並べ替えて上位 N 件だけ残せば、特定の URL に対する推薦 URL リストが得られる。少し手を入れれば、入力した検索語とクリックした URL をログに混ぜて スペル候補も抽出できる

  • とても素晴らしく、教育的。ただしデプロイはしないこと :-)
    以前、似たようなものが必要になったことがあるが、規模が少し大きく、文書が数万件ほどあり、答えはいつものように sqlite だった。構造的にはここにあるものと同じだが、転置インデックスの永続化層を他の人が代わりに書いてくれた形。

    • SQLite FTS はほぼあらゆるところで使っているが、一度も期待を裏切られたことがない
    • 実際、同じ数式まで入っている。このコメントのおかげで「理解の震え」のようなものが来た

  • Google は "search engine" のようにダブルクォートで検索すると、2つの単語がその順序で出現する結果だけを表示する
    少なくとも一部の場合はそうだが、残念ながら常にそうとは限らない。上級ユーザーが求めているのは「Web 向け grep」であって、「Google が見せたいものを教えてくれるもの」ではない。

    • 「Web 向け grep」を本当に欲しがっている人はほとんどいないと断言できる。ごくわずかなクエリ拡張だけを行う検索エンジンと比べても、Web 向け grep は明らかに劣る。
      Google がクエリを解釈するときに自由にやりすぎているのは確かだが、どんな検索エンジンであれ、やらないよりは明らかに良い処理は多い。現在の Google 検索の問題は、なぜその結果が出るのか推論しにくい点にあり、文字列比較で埋め込みに過度に依存しているからのように見える。"cat food" が "dog restaurant" とマッチする、といった具合に、埋め込み空間では意味的に近いが人間の推論とは合わない結果が出るといらだたしい。

  • 外部ライブラリである feedparser、bs4 などを使いながら80行のコードと言うのは公平ではないと思う

    • elasticsearch の上に作ったものなら同意するが、実際の検索エンジン部分がその80行で実装されているなら公平だと思う。取り込んでいるライブラリは、自前で実装しないほうが正しい種類のものだ。
      ときどき「自分だけの検索エンジンを作る」という記事が、実際には searxng や yacy のインストールガイドである場合があるが、これはそういうケースとは違う。
    • その依存関係が非常に一般的で主流なら問題ないと思う

  • 良い。ここにファジー検索機能を追加するのも、それほど難しくはなさそう。たとえば "hackrnew" の検索が "hackernews" にマッチするように、接頭編集距離があるしきい値以下の結果を探す方式だ。
    基本的なアイデアは、追加の転置インデックスをもう1つ用意し、キーを文書コレクション内の単語の n-gram（通常は 3-gram）にし、ポスティングをその n-gram が出現する単語または単語 ID にするというもの。PED(x, y) <= delta なら |N(x) ∩ N(y)| >= |N(x)| - n ∙ delta という補題を利用できる。入力 x の n-gram を計算して各 n-gram のポスティングを取得し、重複をまとめると、各候補単語 y と共有する n-gram の数が得られる。この数が基準より大きい場合にだけ実際の PED を計算し、小さい場合はスキップすることで、高コストな計算を大幅に減らせる。
    こうして得た単語リストを既存のインデックスに問い合わせればよい。以前 https://dont.watch/ でクライアント側 JS のファジー検索エンジンを作ったとき、このアプローチを使った。JS コードの中を見ると、転置インデックスと圧縮された n-gram インデックスを JS ファイルとしてそのまま渡しているのが分かる。実際の検索エンジンは外部依存なしで約300行の JS で、検索結果改善のためのごく基本的なヒューリスティックだけが入っている。

    • その方式だとインデックスサイズはどのくらい増えるの？