Redisのソート済みセットで実現する、ユーザー行動から学ぶスマートオートコンプリート

検索ボックスに文字を入力すると候補が次々と表示される——この体験は誰もが日常的に目にしているはずです。しかし、その多くの候補は単純にアルファベット順に並んでいるだけで、必ずしも役立つとは限りません。

もし検索ボックスが使われるほど「賢く」なっていったらどうでしょうか?

ユーザーが実際にクリックした結果から学び、人気の高い候補を優先的に表示する——そんな仕組みです。

本記事で構築するのはまさにこれです:

Redisのソート済みセット(Sorted Set)を活用し、ユーザーの行動から学習しながら精度を高めていく(人気の結果を上位に表示する)インテリジェントなオートコンプリートシステムの作り方を解説します。

スマートオートコンプリートの基本アイデア

基本的な検索ボックスは「前方一致(プレフィックスマッチング)」という手法で表示順序を決めています。

入力するたびに、マッチした結果がA〜Zの順番で表示されるだけ。ユーザーが実際にどの結果をよくクリックしているかは考慮されません。

今回はここを賢くしていきます。私たちの検索ボックスはユーザーの選択から学習します。ある検索結果がクリックされたら、次回からその結果を上位に表示するのです。

こうすることで、人気の結果が自動的に上位に並び、検索は使うほど便利になっていきます。

検索アプリケーションにおいて重要な理由

映画検索アプリを例に考えてみましょう。ユーザーが「int」と入力したとき、次のような候補が表示されるかもしれません。

• 「Interceptor」
• 「Interstate 60」
• 「Interstellar」

従来型のシステムでは、これらはアルファベット順に表示されます。しかし、ユーザーが一貫して「Interstellar」をクリックしているのであれば、それをオートコンプリート候補の最上部へ引き上げたいところです。

このようなスマートなランキングシステムが特に効果を発揮するのは、以下のようなケースです。

• 動画配信サービス(NetflixやYouTubeなど):よく視聴されている作品を優先表示
• オンラインストア:検索時に人気商品を先に表示
• ヘルプセンター:よく問い合わせされる質問を上位に表示
• 検索機能を持つあらゆるサイト:多くの人がクリックするコンテンツを優先表示

Redisソート済みセットの理解

なぜRedisのソート済みセットがオートコンプリートシステムの構築に適しているのか、その理由を見ていきましょう。

Redisのソート済みセットは、次のような特徴を持つ「賢いリスト」です。

• 各要素は一意である(セットと同様)
• 各要素にスコアが付与される(並び替えに使用)
• スコアに基づいて高速にソートできる

今回のオートコンプリートシステムでは、2つのソート済みセットを使用します。

1. テキストの前方一致用(例:「int」が「interstellar」にマッチ)
2. 各候補の人気度を追跡する用

この2つのセットが連携することで、ユーザーの入力に応じて最も関連性の高い結果を提案できます。

基盤となる辞書順ソート

Redisのソート済みセットは、すべてのメンバーが同じスコアを持つ場合、辞書順(アルファベット順)に並びます。これは検索候補の実装に理想的で、次のことが可能になります。

1. 検索対象語のすべてのプレフィックスを単一のデータ構造に格納できる
2. ZRANKを使い、任意のプレフィックスの開始位置をO(log N)で特定できる
3. ZSCANを使い、その位置以降のマッチを効率的に取得できる
4. ZMSCOREで各マッチの人気スコアを一括取得できる
5. ZINCRBYで各マッチの人気スコアを増加できる

簡単な例を見てみましょう。映画「INTERSTELLAR」を検索システムに登録すると、次のように分解されます。

• スコア:0、メンバー:"I"
• スコア:0、メンバー:"IN"
• スコア:0、メンバー:"INT"
• スコア:0、メンバー:"INTE"
• スコア:0、メンバー:"INTER"
• スコア:0、メンバー:"INTERSTELLAR$Interstellar"(表示形式を含む完全エントリ)

「$」記号で検索用バージョンと表示用バージョンを区切っている点に注目してください。これにより、ユーザーは大文字・小文字を気にせず検索できながら、画面には正しい形式の映画タイトルを表示できます。

データの保存方法

オートコンプリートを実現するために、2つのRedisソート済みセットを使用します。

1. 映画タイトルリスト

moviesという名前のソート済みセットでタイトルを管理します。これは素早く映画を見つけるための辞書のようなもので、「int」と入力された瞬間に、その文字で始まるすべての映画を即座に見つけられます。

最初に出現する「int」の位置をZRANKで特定し、その位置からワイルドカードINT*$*を使って完全な映画名を取得します。

2. 人気映画リスト

もう一方のmovie-popularityというソート済みセットは、いわば「トレンド映画ランキング」です。

ユーザーが検索結果の映画をクリックするたびに、ZINCRBYでスコアを増加させ、その映画の人気度が上がります。クリック数の多い映画ほど、今後の検索で上位に表示されます。

Netflixがトレンド作品を表示するのと同じ仕組みです。視聴されるほど、おすすめの上位に現れます。

今回のケースでは、INT*$*に一致する候補を特定した後、movie-popularityでそれぞれのスコアを確認し、最も人気の高いものを返します。

アルゴリズムの流れ

graph TD
 A[User types 'int'] --> B[ZRANK: Find lexicographic position of 'INT']
 B --> C[ZSCAN: Retrieve matches starting from position (movies set)]
 C --> D[Filter: Extract complete terms containing '$']
 D --> E[ZMSCORE: Get popularity scores for all matches (movie-popularity set)]
 E --> F[Rank: Return highest-scored suggestion]
 G[User selects suggestion] --> H[ZINCRBY: Increment popularity score]
 H --> I[Future searches: Higher scored items rank first]
 I --> A

ユーザーが検索して候補をクリックするたびに、システムは学習し、改善されていきます。利用者が増えるほど、最も関連性の高い候補を上位に表示する能力が向上するのです。

オートコンプリートシステムを構築しよう

ここからは、このオートコンプリートシステムをステップごとに構築していきます。できるだけシンプルに保ちます!

ステップ1:映画タイトルをRedisに追加する

まず、後で検索できるよう映画タイトルをRedisに登録します。データベースやテキストファイルなど、どこかにあるシンプルな映画リストから始めればOKです。追加方法は以下の通りです。

import { Redis } from "@upstash/redis";
 
const redis = new Redis({
 url: process.env.UPSTASH_REDIS_URL!,
 token: process.env.UPSTASH_REDIS_TOKEN!,
});
 
// 例:タイトルのリスト
const titles = [
 "Interceptor",
 "Interstate 60",
 "Interstellar",
 // ...その他のタイトル
];
 
async function populateAutocomplete() {
 // プレフィックスと完全なタイトルを 'movies' ソート済みセットに挿入
 for (const title of titles) {
 let term = title.toUpperCase();
 let terms = [];
 for (let i = 1; i < term.length; i++) {
 terms.push({ score: 0, member: term.substring(0, i) });
 }
 terms.push({ score: 0, member: term });
 terms.push({ score: 0, member: term + "$" + title });
 await redis.zadd("movies", ...terms);
 }
 
 // 人気度トラッキングのため、全タイトルを 'movie-popularity' ソート済みセットに挿入
 await redis.zadd(
 "movie-popularity",
 ...titles.map((title) => ({
 score: 0,
 member: title.toUpperCase(),
 })),
 );
}
 
populateAutocomplete();

上記のコードの処理内容を分解してみましょう。

1. 各映画タイトルについて、次の3種類を保存します。

   • 考えられるすべての部分一致("Interstellar"なら「INT」「INTE」「INTER」など)
   • 完全なタイトル自体
   • 表示用に整形されたバージョン

2. 同時に、各映画の人気度を追跡する別のリストも作成します。初期値はゼロです。

これで、ユーザーの入力に応じてスマートな候補を表示し、クリックから学習するための準備が整いました。

ステップ2:最適なマッチを見つける

次に、これらの映画タイトルからマッチを検索する方法を見ていきます。matchQuery関数がすべての重い処理を担います。

export const matchQuery = async (query: string): Promise<string | null> => {
 const upperQuery = query.toUpperCase();
 
 // ステップ1: 辞書順ソートを利用して開始位置を特定
 let rank = await redis.zrank("movies", upperQuery);
 if (rank === null) return null;
 
 // ステップ2: その位置から効率的にマッチをスキャン
 const scanResult = await redis.zscan("movies", rank, {
 match: `${upperQuery}*$*`,
 count: 1000,
 });
 
 // ステップ3: 完全なエントリを抽出し、人気スコアを取得
 const completeTitles = scanResult[1].filter(
 (el, idx) => idx % 2 === 0 && el.includes("$"),
 );
 
 const baseNames = completeTitles.map((title) => title.split("$")[0]);
 const scores = await redis.zmscore("movie-popularity", baseNames);
 
 // ステップ4: 最もスコアの高い(人気の)マッチを返す
 const maxScore = Math.max(...scores);
 const bestMatchIndex = scores.indexOf(maxScore);
 return completeTitles[bestMatchIndex].split("$")[1];
};

ユーザーの選択から学ぶ

ユーザーが映画タイトルを選択したら、そのスコアに1ポイント加算します。ポイントの多い映画ほど、候補リストの上位に表示される仕組みです。非常にシンプルですね!

ユーザーが実際に何を選んだかを記録し続けることで、システムは時間とともに賢くなっていきます。

const onSubmit = async (title: string) => {
 // 送信時のロジックをここに記述
 await redis.zincrby("movie-popularity", 1, title.toUpperCase());
};

パフォーマンスはどれくらい?

各操作にかかる時間を分解して、このソリューションの速度を確認しましょう。

• ZRANK: O(log N) — 対数時間でのルックアップ
• ZSCAN: O(log N + M) — Mは返却される要素数
• ZMSCORE: O(N) — Nはマッチした結果の数であり、データセット全体のサイズではない
• ZINCRBY: O(log N) — 対数計算量でのアトミックな増分処理

映画タイトルをいくら追加しても、パフォーマンスは安定して維持されます。

まとめ:私たちが構築したもの

AIを使わずに、時間とともに賢くなるスマートな検索ボックスの作り方を学びました。

今回のオートコンプリートは、ユーザーの選択から学習し、その情報をもっと良い候補表示に活かします。

高速でシンプル、そして使われるほど便利になっていく——そんな仕組みです。

Redisの最適化戦略について語り合いたい方、自身の実装を共有したい方は、ぜひDiscordにご参加ください!