実際に動くシンプルな検索エンジンを作る

 (karboosx.net)
9 ポイント 投稿者 GN⁺ 2025-11-18 | 1件のコメント | WhatsAppで共有
  • 既存のデータベースを活用して、外部サービスなしで動作する検索エンジン構造を実装し、トークン化・重み付け・スコアリングを中心に構成
  • 中核となるアイデアは、すべてのテキストをトークン化して保存し、検索時にも同じ方式でトークンをマッチさせて関連度を計算すること
  • Word、Prefix、N-Gram トークナイザーを組み合わせ、完全一致・部分一致・タイプミス対応をすべて処理し、各トークナイザーは固有の重みを持つ
  • 重み付けシステムと SQL ベースのスコアリングアルゴリズムによって、文書長、トークンの多様性、平均品質などを総合評価
  • 拡張性と透明性が高く、新しいトークナイザーや文書タイプの追加、重みの調整、スコアリングの修正を自由に行える構造

自前で検索エンジンを作る理由

  • Elasticsearch や Algolia のような外部サービスは強力だが、複雑な API の学習やインフラ運用の負担がある
  • 単に 既存のデータベースと統合して動作し、デバッグしやすい検索機能が必要な場合は、自前構築が有用
  • 目標は、外部依存なしで関連性の高い結果を返すシンプルな検索エンジン

中核概念: トークン化とマッチング

  • 基本原理は、すべてのテキストをトークン化（tokenize）して保存し、検索時にも同じ方法でトークンを生成してマッチさせること
  • インデックス作成段階でコンテンツをトークン単位に分割し、重みとともに保存
  • 検索段階ではクエリを同様にトークン化して一致するトークンを探し、スコアを計算
  • スコアリング段階では保存された重みを利用して関連度スコアを算出

データベーススキーマ設計

  • 2 つのテーブルを使用: index_tokens と index_entries
    • index_tokens: 一意のトークンとトークナイザーごとの重みを保存
    • index_entries: トークンと文書を結び付け、フィールド・文書・トークナイザーの重みを反映した最終スコアを保存
  • 最終重みの計算式:
    field_weight × tokenizer_weight × ceil(sqrt(token_length))
  • インデックスは文書参照、トークン参照、フィールド別クエリ、重みフィルタリングのために設定

トークン化システム

  • WordTokenizer: 単語単位で分割し、短い単語を除去、完全一致向け（重み 20）
  • PrefixTokenizer: 単語の接頭辞を生成し、自動補完や部分一致向け（重み 5）
  • NGramsTokenizer: 固定長の文字組み合わせを生成し、タイプミスや部分一致に対応（重み 1）
  • すべてのトークナイザーは共通して 小文字化、特殊文字の除去、空白の正規化 を実行

重み付けシステム

  • フィールド重み: タイトル・本文・キーワードなどの重要度を反映
  • トークナイザー重み: Word > Prefix > N-Gram の順
  • 文書重み: 上記 2 要素とトークン長を組み合わせて計算
  • ceil(sqrt()) 関数を使って長いトークンの影響を緩和し、必要に応じて対数関数や線形関数にも調整可能

インデックス作成サービス

  • IndexableDocumentInterface を実装した文書だけをインデックス化可能
  • 文書の作成・更新時にイベントリスナーやコマンド（app:index-document, app:reindex-documents）でインデックス作成を実行
  • 手順:
    • 既存インデックスを削除してから新しいトークンを生成
    • 各フィールドに対してすべてのトークナイザーを実行
    • トークンの存在有無を確認してから生成（findOrCreateToken）
    • 計算済みの重みで index_entries に バッチ挿入（batch insert）
  • 重複防止、性能向上、更新対応を意識した構造

検索サービス

  • クエリを同じトークナイザーで処理し、インデックス作成時と同一のトークンセットを取得
  • トークンの重複を除去した後、長さ順にソート（長いトークン優先）し、最大 300 個に制限
  • SQL クエリを通じてトークンと文書を結合し、関連度スコアを計算して並べ替え
  • 結果は SearchResult(documentId, score) 形式で返却

スコアリングアルゴリズム

  • 基本スコア: SUM(sd.weight)
  • トークン多様性補正: LOG(1 + COUNT(DISTINCT token_id))
  • 平均重み補正: LOG(1 + AVG(weight))
  • 文書長ペナルティ: 1 / (1 + LOG(1 + token_count))
  • 正規化（normalization）: 最大スコアで割って 0〜1 の範囲に調整
  • 最小トークン重みフィルタ（st2.weight >= ?）により、意味のない低重み一致を除去

結果処理

  • 検索結果は文書 ID とスコアで返され、リポジトリ（repository）を通じて実際の文書へ変換
  • FIELD() 関数を使い、検索結果の順序を維持したまま文書を取得

システム拡張性

  • 新しいトークナイザーは TokenizerInterface の実装で追加可能
  • 新しい文書タイプは IndexableDocumentInterface の実装で登録
  • 重みやスコアリングロジックは SQL を修正するだけで調整可能

結論

  • この構造は シンプルだが実際に動く検索エンジンであり、外部インフラなしでも十分な性能を提供
  • 明確なロジック、完全な制御、容易なデバッグ が利点
  • 複雑なシステムよりも、自分で理解し制御できるコードの方が価値があることを強調

関連記事

1件のコメント

 
GN⁺ 2025-11-18
Hacker Newsのコメント

  • 検索の基本的なアイデアはシンプルで、興味深い問題領域でもある
    ただし、本当に難しいのは大量のデータを扱うことと、曖昧なクエリを処理することだ
    DBMSベースのアプローチは小規模なWebサイト程度なら問題ないが、英語版Wikipediaの規模になるとすぐ限界に突き当たる
    入門用としては SeIRP e-book が良い無料資料だ

    • 大量データが難しいのは当然として、曖昧なクエリを扱うことは「最も関連性の高い結果をどう決めるか」という下位問題だと思う
      明確な正解がないことが特に厄介だ
      Googleは広告を「最も関連性の高い結果」として見せることもあるので、Marginalia Search は良い対照例だ
      もし TRECの論文群 を参照したことがあるか気になる
    • 最近はむしろ SEOスパムの回避 のほうが大きな問題だと思う
      検索エンジンは広告収益を狙う敵対的プレイヤーと絶えず戦わなければならない
      品質指標を継続的に変えて、彼らに悪用されないようにする終わりのないいたちごっこになる
    • SQLiteで単一サーバー（約1000ドル程度）上でテキスト中心のビジネスプロセスを回すなら、実際に扱えるドキュメントストアの規模がどの程度なのか気になる
      1クエリあたり5秒、1分あたり12クエリ程度を基準にすると、どれくらいのコーパスを検索できるのか知りたい
    • Marginalia Search が本当に好きだ
    • 検索の難しさは単なるデータ量だけでなく、どの結果を返すかを決める問題だと思う
      たとえば Gilligan’s Island のWiki記事とファンブログのどちらがより「良い」結果なのか判断するのは難しい
      さらに順位操作やキーワードスタッフィングまで加わると、スケーラビリティの問題よりはるかに複雑な課題になる

  • 検索は本当に難しい
    Apple、Microsoft、OpenAIのように資源も技術力も豊富な企業でさえ、検索機能の品質が低い
    これは単なる技術問題ではない

    • ほとんどの企業が検索をうまく実装できない理由は、企業文化と開発手法が検索開発と衝突するからだ
      検索品質を高めるにはランキングパラメータを細かく調整する必要があるが、こうした作業はスプリントやJiraのような管理体系では計画しにくい
      結局のところ、開発者に信頼と自律性が必要な領域だ
    • ただ、企業によっては単に検索が優先事項ではないから品質が低い場合もある
      AIモデルには何十億も投資するのに、Webアプリや検索は二の次なので、そういう結果になる

  • 10年ほど前に、検索エンジン設計で博士課程にいた同僚と一緒に働いたことがある
    彼は検索とデータベースの統合について非常に熱心に語っていて、そのおかげで多くを学べた
    いつかApache Solr と Lucene の内部を深く掘り下げてみたい

    • 私も自分の分野の話なら何時間でもできるくらい好きだが、大規模システムの細部実装に興味を持つ人は多くない

  • 昔はオープンソースの検索ソリューションがなかったので、自分で作るしかなかった
    その経験から得た教訓は、「検索エンジンを自作するな」ということだ
    長年にわたり多くの人員がこの問題に取り組んできたし、自作すると終わりのない保守地獄に陥る
    「誤字訂正機能を追加してほしい」「来年は分類体系も入れよう」といった要求が続くと終わりだ

  • 昔、Virginia University の David Evans 教授が行っていた検索エンジン構築の講義を本当に楽しんだ
    「古典的な検索エンジン」を自分で作ってみるのはとても楽しいプロジェクトだった
    講義リンク と YouTubeプレイリスト を参照できる

    • 私もその講義を受けたが、初心者プログラマーにとっても興味深く密度の高い授業だった

  • 私がよく使う検索エンジンが、2〜3文字の略語や単語を無視するのが不満だ
    「mp3」や「PHP」のような短い単語を検索するときに除外されると本当に不便だ

  • Toby Segaran の Programming Collective Intelligence を読んで、検索、推薦、分類器などさまざまなアイデアの着想を得た

    • 私もその本は好きだったが、著者が後にYouTubeで「もう古いので使わないほうがいい」と言っているのを見た
    • 本当に良い本だったので、2025年に相当する最新改訂版があるなら気になる

  • 興味深い記事だった
    人気の検索エンジンが使っているトークナイザー最適化の水準がどれほど高いのか気になる

  • このシステムがどれほどスケーラブルに動作するのか気になる
    Elasticsearchは推奨スケールを超えてもかなり印象的な性能を見せる

  • シンプルなテキスト検索エンジンを作ること自体は難しくない
    しかし、良い検索エンジンを作るのはまったく別の話だ
    単にBM25のようなアルゴリズムを実装するだけでは不十分だ
    私がコンサルティングした企業の大半は独自ソリューションを使っていたが、最終的には Elasticsearch や Opensearch に移行した
    独自実装は最初は単純でも、時間が経つとランキングの問題や性能低下で複雑になっていく
    「遅い」「的外れな結果が出る」といった症状が繰り返される
    Elasticsearchはすでに10年前からこうした問題を解決してきており、今ではさらに進化している
    「設定が難しい」とも言われるが、最近は大半が自動構成されるし、マネージドサービスも多い
    Postgresよりむしろ扱いやすい
    結局重要なのはインデックスマッピングの最適化だ
    「そんな高度な機能は必要ない」と言う人もいるが、実際には検索品質がビジネスの存続に直結する
    きちんとした検索を求めるなら、結局こうした複雑さを受け入れなければならない

    • 私もElasticsearchをデフォルトで使っている
      最近HNでよく言及される SeekStorm のような新興の代替も興味深く見えるが、実運用の事例はまだ見たことがない
    • 「不要な機能などない」という言葉には同感だ
      特に dynamic mapping を無効にし、不要なフィールドのインデックス作成を防ぐコツが有用だった
    • ManticoreSearch についてはどう思うのか気になる
      Luceneより古いプロジェクトだと認識している