如何在MongoDB中基于Hash的编辑距离查询相似对象？

MongoDB本身没有内置的编辑距离（Levenshtein Distance）或汉明距离（Hamming Distance）函数，但可以通过**聚合框架的$function**自定义计算逻辑，实现基于编辑距离阈值筛选相似Hash的需求。以下是具体实现方式：

一、基于编辑距离（Levenshtein）的查询实现 #

通过在聚合管道的$match阶段中，用$function定义编辑距离计算逻辑，将文档的hash字段与目标Hash对比，筛选出编辑距离≤阈值的文档。

查询示例代码 #

db.your_collection_name.aggregate([
  {
    $match: {
      $expr: {
        $lte: [
          {
            $function: {
              body: function(targetHash, docHash) {
                // 实现Levenshtein编辑距离算法
                if (targetHash.length === 0) return docHash.length;
                if (docHash.length === 0) return targetHash.length;
                
                // 初始化距离矩阵
                const matrix = Array(docHash.length + 1)
                  .fill(null)
                  .map(() => Array(targetHash.length + 1).fill(null));
                
                // 填充矩阵边界
                for (let i = 0; i <= targetHash.length; i++) matrix[0][i] = i;
                for (let j = 0; j <= docHash.length; j++) matrix[j][0] = j;
                
                // 计算编辑距离
                for (let j = 1; j <= docHash.length; j++) {
                  for (let i = 1; i <= targetHash.length; i++) {
                    const cost = targetHash[i-1] === docHash[j-1] ? 0 : 1;
                    matrix[j][i] = Math.min(
                      matrix[j-1][i] + 1,  // 删除操作
                      matrix[j][i-1] + 1,  // 插入操作
                      matrix[j-1][i-1] + cost // 替换操作
                    );
                  }
                }
                return matrix[docHash.length][targetHash.length];
              },
              args: ["hum024", "$hash"], // 目标Hash、文档的hash字段
              lang: "js"
            }
          },
          2 // 最大允许的编辑距离阈值
        ]
      }
    }
  }
])

逻辑说明 #

1. 自定义的JavaScript函数实现了标准的Levenshtein编辑距离计算逻辑，对比目标Hash（hum024）与每个文档的hash字段。
2. 通过$lte判断计算出的编辑距离是否≤设定的阈值（2），满足条件的文档会被保留。
3. 运行该查询后，会返回hash为hum123和humX124的文档，与预期结果一致。

二、基于汉明距离（Hamming）的查询实现 #

如果你的Hash长度固定，汉明距离（仅统计相同长度字符串的不同字符数）是更轻量的选择，可简化计算逻辑：

修改后的$function代码 #

body: function(targetHash, docHash) {
  // 长度不同的字符串直接返回无穷大，不纳入结果
  if (targetHash.length !== docHash.length) return Infinity;
  
  let distance = 0;
  for (let i = 0; i < targetHash.length; i++) {
    if (targetHash[i] !== docHash[i]) distance++;
  }
  return distance;
}

注意事项 #

• 性能问题：该实现需要遍历集合中所有文档并逐一计算距离，无法利用索引加速，数据量较大时查询会非常慢，仅适合小数据集或测试场景。
• 函数兼容性：$function从MongoDB 4.4版本开始支持，若使用更早版本，可考虑用mapReduce实现类似逻辑，但性能同样受限。

内容的提问来源于stack exchange，提问作者Dawit