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

 (alexmolas.com)
6 ポイント 投稿者 GN⁺ 2024-02-08 | 1件のコメント | WhatsAppで共有

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

  • 昨年9月にWallapopの検索データサイエンティストとして加わり、Solrというオープンソースの検索エンジンを扱う仕事をしている。
  • 検索エンジンの基本原理を理解するため、Pythonを使ってゼロから検索エンジンを作ることにした。
  • 目標は「小規模ウェブサイトの発見可能性の危機」を解決することで、Googleのような検索エンジンでは見つけられない小さなウェブサイトを再び素晴らしいものにすることだ。
  • この記事では、Pythonを使って検索エンジンを作る過程を案内し、書いたすべてのコードはGitHubのmicrosearchリポジトリで確認できる。
  • 実装された検索エンジンは本番運用に対応した検索エンジンではなく、検索エンジンが内部でどのように動作するのかを示す実用的なおもちゃの例である。

microsearch

  • microsearchを構成する要素を見ていき、それぞれをどのように作ったかを探る: (1) クローラー、(2) 転置インデックス、(3) ランキング、(4) インターフェース。

クローラー

  • 検索エンジンを作るための最初のステップは、検索対象となるデータを確保することだ。
  • 「ローカルGoogle」を作るつもりで、フォローしているブログのデータを使って検索エンジンを構築した。
  • クローリングには、特定のブログ一覧にあるすべての投稿をダウンロードして整理する作業が含まれる。
  • より高速にするため、asyncio Pythonライブラリを使ってクローリング時間を20分から20秒に短縮した。
  • 642個のRSSフィードを使い、そのうち約100個は普段よく読むブログ、残り500個はsurprisetalkブログプロジェクトから取得した。

転置インデックス

  • 転置インデックスは、キーワードを文書に対応付けるデータ構造で、特定の単語が現れる文書を簡単に見つけられるようにする。
  • ユーザーがクエリを検索するとき、転置インデックスを使ってクエリのキーワードに一致するすべての文書を検索する。
  • 転置インデックスのロジックはSearchEngineというクラス内に定義されており、2つの辞書を初期化することで実装している。

ランキング

  • あるクエリに対して一致する文書集合が得られたら、それを並べ替える方法が必要になる。
  • 最も有名なランキング手法はGoogleのPageRankだが、BM25のように内容ベースで文書をランキングする別の選択肢もある。
  • BM25スコアの計算方法を含め、SearchEngineクラスの不足している部分を実装した。

インターフェース

  • 検索エンジンを構築した後は、何らかの形でそれを公開したい。
  • FastAPIアプリを構築して検索エンジンを公開するエンドポイントを提供し、検索を実行できるシンプルなウェブページをレンダリングする。
  • 出力を読みやすくするため、上位N個のURLだけを選ぶことにした。

足りない機能

  • 検索エンジンを日頃よく扱う読者なら、実装に多くの機能が欠けていることに気づくだろう。
  • クエリ演算子、n-gramインデキシング、クエリまたは文書の拡張、クローリングとインデキシングを同時に行う機能などが欠けている。

結論

  • このプロジェクトを進める中で、Solrの内部動作についてより深く理解でき、非同期コードを書くことの驚きも学んだ。
  • 個人向け検索エンジンを作る次のステップとして、検索エンジンにセマンティック検索機能を実装する予定だ。

GN⁺の意見

  • この記事で最も重要なのは、小規模ウェブサイトの発見可能性を改善するために、個人が自分で検索エンジンを作れるという点だ。
  • Pythonとオープンソースライブラリを活用し、複雑な機能を持つ検索エンジンを単純化して実装した経験は、初級ソフトウェアエンジニアにとっても刺激になる。
  • 非同期プログラミングの効率とデータ構造の重要性を実例で示すことで、この記事は技術的な洞察と実践的な学習機会を提供している。

関連記事

1件のコメント

 
GN⁺ 2024-02-08
Hacker Newsの意見

  • Pandasを使ったBM25検索エンジンの開発

    • 開発者はPandas上で動作する高速なBM25検索エンジンを開発中。
    • Pandasを使う理由は、BM25アルゴリズム以外にも新しさや人気度など、他の要素を簡単に組み合わせられるため。
    • フレーズマッチには多くの例外ケースがあり、できるだけ少ないメモリで位置情報を圧縮することが重要。

  • コードレビュー: SearchEngine クラス

    • k1 と b というパラメータの意味が分からず、コードにはコメントがまったくない。
    • _documents はURLをキーに、そのURLの内容を値として持つものと推測される。
    • コードのドキュメントが十分でないのが惜しい。きちんと文書化されていれば、検索エンジン構築の学習資料として有用だったはず。

  • 検索エンジンの複雑さ

    • 検索エンジンの主な難しさは、データ量を扱うことにある。
    • ロジック自体は意外と単純で、このプロジェクトは不要な部分をほとんど取り除いていて成功している。
    • 検索エンジンを大きくするのではなく、データをより小さくするか、信号対雑音比を高めるアプローチが重要。

  • コード行数についての意見

    • 外部依存を使っている状況で、コード行数を誇ることの意味に疑問を呈している。
    • コードベースに対するSI単位はないが、認知負荷を何らかの形で測る必要があるという意見。

  • コード内の表現に関するジョーク

    • コード中の chunk for chunk in chunks if chunk という表現を見て、木こりに関するジョークを思い出した。

  • 推薦エンジンのコード例

    • 検索エンジンと一緒に使える、Pythonで書かれた20行未満の推薦エンジンのコードを提示。
    • セッションログでクリックされたURLを基に推薦を生成する。
    • ログに入力されたクエリとクリックされたURLを混ぜて使えば、スペルチェックの候補も得られる。

  • パースライブラリの性能比較

    • lxml.html と lxml.html.clean は BeautifulSoup よりはるかに高速な場合があると述べている。

  • キーワード利用に関する助言

    • 英語検索結果の品質を高めるため、1-gramの代わりに2-gramと3-gramを使うことを勧めている。
    • n-gramは文脈を保つのに役立つ。

  • 教育的なプロジェクトに対する意見

    • プロジェクトは非常にすばらしく教育的だが、実運用には出さないほうがよいと勧めている。
    • 数万件の文書を扱う、より大規模なプロジェクトにはSQLiteのFTS5を使うのが答えだとしている。

  • Pythonによる大規模データ処理への疑問

    • 大規模データを高速に処理しなければならない作業に、Python（遅い言語）を使うのが本当に良い考えなのか疑問を呈している.