编码母题 / P2 / 检索与 Agent 协议 / 01

关键词与向量结果的混合检索融合

先读清题意与边界，独立尝试，再展开思路并对照可运行的参考代码。

重要程度岗位专项难度中等预计完成35–45 分钟

难度按 LeetCode 简单／中等／困难三档估计；工程题并非 LeetCode 官方题目。用时指独立编码并检查主要边界的参考时间，因经验而异。

题目是什么

关键词与向量检索各返回排序列表。先做权限过滤，再用 RRF 按文档 id 去重并融合排名，输出前 k 项及来源排名。

输入输出示例

未授权文档排在某列表首位时，它不能占用候选名额，也不能改变授权结果的融合排名。

练习起手式与验证

复制代码后补全空方法，再运行下方三组验证；复杂题所需的辅助类型与输入准备一并放在代码块中。

/*
 * 题目：关键词与向量结果的混合检索融合
 * 要求：关键词与向量检索各返回排序列表。先做权限过滤，再用 RRF 按文档 id 去重并融合排名，
 * 输出前 k 项及来源排名。
 * 示例：未授权文档排在某列表首位时，它不能占用候选名额，也不能改变授权结果的融合排名。
 */
function reciprocalRankFusion(resultLists, { k, constant = 60, allow = () => true } = {}) {}

const keyword = [
  { id: "a", tenant: 1 },
  { id: "b", tenant: 1 },
  { id: "secret", tenant: 2 },
];
const vector = [
  { id: "b", tenant: 1 },
  { id: "c", tenant: 1 },
  { id: "a", tenant: 1 },
];
const result = reciprocalRankFusion([keyword, vector], {
  k: 3,
  constant: 60,
  allow: (doc) => doc.tenant === 1,
});
console.log(result.map((x) => x.document.id)); // 预期：["b", "a", "c"]
console.log(result.some((x) => x.document.id === "secret")); // 预期：false
console.log(result[0].sources.length); // 预期：2

解题思路

展开思路、不变量与常见边界

关键切入点：每个检索源的授权后名次贡献 1/(constant+rank)，按 id 累加再排序。

不变量：每个文档最多一项；分数等于它在全部结果列表中的排名贡献和；输出按分数降序并以 id 稳定破同分。时间 O(totalResults + m log m)，空间 O(m)。生产系统还需 Query Rewrite、rerank、引用片段、索引版本和离线召回评测。

参考代码与验证

“关键机制”注释用于解释实现，下载链接提供未经页面注释修改的原始 JS 文件。

// 关键机制：每个检索源的授权后名次贡献 1/(constant+rank)，按 id 累加再排序。
function reciprocalRankFusion(
  resultLists,
  { k, constant = 60, allow = () => true } = {},
) {
  if (!Number.isInteger(k) || k < 0 || !(constant > 0))
    throw new RangeError("invalid options");
  const fused = new Map();
  resultLists.forEach((list, sourceIndex) => {
    let authorizedRank = 0;
    for (const document of list) {
      if (!document || document.id === undefined || !allow(document)) continue;
      authorizedRank += 1;
      const current = fused.get(document.id) || {
        document,
        score: 0,
        sources: [],
      };
      current.score += 1 / (constant + authorizedRank);
      current.sources.push({ sourceIndex, rank: authorizedRank });
      fused.set(document.id, current);
    }
  });
  return [...fused.values()]
    .sort(
      (a, b) =>
        b.score - a.score ||
        String(a.document.id).localeCompare(String(b.document.id)),
    )
    .slice(0, k);
}

// 三组以上可直接运行的验证。
const keyword = [
  { id: "a", tenant: 1 },
  { id: "b", tenant: 1 },
  { id: "secret", tenant: 2 },
];
const vector = [
  { id: "b", tenant: 1 },
  { id: "c", tenant: 1 },
  { id: "a", tenant: 1 },
];
const result = reciprocalRankFusion([keyword, vector], {
  k: 3,
  constant: 60,
  allow: (doc) => doc.tenant === 1,
});
console.log(result.map((x) => x.document.id)); // 预期：["b", "a", "c"]
console.log(result.some((x) => x.document.id === "secret")); // 预期：false
console.log(result[0].sources.length); // 预期：2

复杂度分析

时间复杂度：O(N + m log m)。扫描 N 条检索结果融合去重，再排序 m 个授权文档。

空间复杂度：O(m+N_s)。融合表保存 m 个文档及其 N_s 条来源记录。

下载原始 JS 文件