【アルゴリズム】検索エンジンで重要なトップnソートについてまとめておく

検索エンジンやレコメンドエンジンを昔実装していた先輩から、飲み会で

レコメンドエンジンって、要するに検索エンジンの特殊なもの
検索エンジンに重要なアルゴリズムはトップnソート
実際に利用した性能評価も重要

という話を聞きました。

ところが、私は低レイヤーの言語（CやC++）から逃げてPythonを始めたような人間なので、残念ながら「アルゴリズムとデータ構造」と呼ばれるような分野は全く詳しくありません。

しかし、社内には既に数学や機械学習・数理計画法の知識では敵わない人がいるため、私は生き延びるためには実装やアーキテクチャ（要するに数理モデルを「検索エンジン」として使えるようにする技術）を勉強しなければいけないと思っています。

という話はさておき、今後これらの分野を勉強するときのために、「トップnソート」関連の記事についてポインタを残しておこうと思います。

まずはこちらの記事。"top n sort"ではなく"top k-selection"と呼んでいますが、同じアルゴリズムだと思います。

プログラムを書くお仕事をしていると、いろんな場面で top-k selection をしなきゃいけない状況にちょくちょく出くわすことがあるかと思います。もちろん RDBMS を使っていれば、ORDER BY sort_column LIMIT k とすることでさくっと top-k selection が実現できるわけですが、RDBMS の外で top-k selection をしなきゃいけない状況だって (年に 2〜3 回もあるかは個人差がありますが)、人生の中で 1〜2 回は遭遇するんじゃないかと思います。

非常にわかります。私の場合、今のところ運良く「nが小さく、全部ソートしてしまっても遅くなかったケース」「一番大きなものだけ選ぶケース」にしか当たっていないので実装せずに済んでいるのですが。

こちらの記事のコメントで、言われている「mikioさんのページ」は、

本当は、mikioさんがかなり色々と実験をされていたので、そこにリンクが張れるとよかったんですが、ページが消えてるみたいで、見つかりませんでした……。

別の記事でも言及があったため、そのURLをインターネットアーカイブを探ると見つかりました。

開発メモ: トップNソートの検討

データベースに対して、ある順序でソートした時の最初の何件かが欲しいというクエリを投げることはよくあるだろう。SNSで言えば、誰かのコンテンツの最新10件を表示するとかいう場合だ。SQLだと　"ORDER BY timestamp DESC LIMIT 10" とかいう感じ。同じような操作は全文検索システムのスコアリングでも定番である。俺もよく自分で実装するわけだが、その度に適当な試行錯誤をして時間がもったいないので、今回は入念に調べて決定版を出そうじゃないか。

こちらの記事では、実際にC++でヒープソート、クイックソートを改造して実装しています。

なお、「レコメンドエンジンって、要するに検索エンジンの特殊なもの」ということは、以下の本の「Solrをレコメンドエンジンとして使う」という章でも書かれていました。検索エンジンの性能評価についても書かれていたのできちんとやればかなり勉強になりそうです。