如何用NodeJs实现简易搜索引擎？解析面试题核心需求

一、核心需求拆解 #

需求1：动态添加可立即查询的单词 #

指接收用户传入的单词x后，无需重新加载原始TXT文件，直接将x纳入搜索语料库，后续用户搜索x或相关匹配规则（比如前缀）时，能立刻返回结果。本质是实现语料库的实时增量更新。

需求2：移除与指定单词最相似的条目 #

这里的“最相似”通常指编辑距离最小（即Levenshtein距离，两个单词间最少需要多少次增删改操作才能完全一致）。需要遍历语料库找到与y编辑距离最小的单词，将其从语料库中彻底删除，后续搜索不再出现该单词。若存在多个距离相同的单词，一般默认选择第一个匹配项（可根据需求调整规则）。

二、具体实现方案 #

1. 核心数据结构选型 #

使用Set存储语料库（保证O(1)级别的增删查效率），同时维护一个Array用于遍历计算单词相似度，兼顾性能和遍历需求。

2. 代码实现 #

初始化：加载TXT数据源

const fs = require('fs').promises;
const path = require('path');

// 核心语料库：Set用于快速去重与查询，Array用于遍历计算相似度
let corpusSet = new Set();
let corpusArray = [];

// 从TXT文件加载初始语料
async function initCorpus(txtFilePath) {
  try {
    const content = await fs.readFile(txtFilePath, 'utf8');
    // 提取所有单词，转小写、去重、过滤空字符串
    const rawWords = content.toLowerCase().split(/[^a-zA-Z]+/);
    const validWords = rawWords.filter(word => word.length > 0);
    
    validWords.forEach(word => corpusSet.add(word));
    corpusArray = Array.from(corpusSet);
    console.log(`语料库初始化完成，共加载 ${corpusArray.length} 个单词`);
  } catch (error) {
    console.error('加载语料库失败:', error);
  }
}

基础搜索功能

先实现精确匹配，若需要前缀/模糊匹配可扩展：

// 精确搜索：返回匹配的单词数组
function searchExact(word) {
  const target = word.toLowerCase();
  return corpusSet.has(target) ? [target] : [];
}

// 可选：前缀搜索，返回所有以输入前缀开头的单词
function searchPrefix(prefix) {
  const targetPrefix = prefix.toLowerCase();
  return corpusArray.filter(word => word.startsWith(targetPrefix));
}

动态添加单词

// 向语料库添加单词，立即生效
function addWord(x) {
  const lowerX = x.toLowerCase();
  if (!corpusSet.has(lowerX)) {
    corpusSet.add(lowerX);
    corpusArray.push(lowerX);
    return true; // 添加成功
  }
  return false; // 单词已存在，无需重复添加
}

移除最相似单词（基于Levenshtein距离）

// 计算两个单词的Levenshtein编辑距离
function calculateEditDistance(a, b) {
  // 创建二维矩阵存储编辑距离
  const distanceMatrix = Array.from({ length: a.length + 1 }, () => 
    Array(b.length + 1).fill(0)
  );

  // 初始化边界：空字符串到目标字符串的距离
  for (let i = 0; i <= a.length; i++) distanceMatrix[i][0] = i;
  for (let j = 0; j <= b.length; j++) distanceMatrix[0][j] = j;

  // 填充矩阵计算距离
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      const cost = a[i-1] === b[j-1] ? 0 : 1;
      distanceMatrix[i][j] = Math.min(
        distanceMatrix[i-1][j] + 1,   // 删除操作
        distanceMatrix[i][j-1] + 1,   // 插入操作
        distanceMatrix[i-1][j-1] + cost // 替换操作
      );
    }
  }

  return distanceMatrix[a.length][b.length];
}

// 找到并移除与y最相似的单词
function removeMostSimilar(y) {
  const lowerY = y.toLowerCase();
  if (corpusArray.length === 0) return null;

  let minDistance = Infinity;
  let targetWord = null;

  // 遍历语料库找最小距离的单词
  for (const word of corpusArray) {
    const currentDistance = calculateEditDistance(lowerY, word);
    if (currentDistance < minDistance) {
      minDistance = currentDistance;
      targetWord = word;
    }
  }

  // 从语料库中删除目标单词
  if (targetWord) {
    corpusSet.delete(targetWord);
    corpusArray = corpusArray.filter(word => word !== targetWord);
    return targetWord; // 返回被删除的单词
  }
  return null;
}

测试示例

// 测试流程
async function testEngine() {
  await initCorpus(path.join(__dirname, 'your_corpus.txt'));
  
  // 测试精确搜索
  console.log('搜索"apple":', searchExact('apple'));
  
  // 测试添加单词
  addWord('blueberry');
  console.log('添加后搜索"blueberry":', searchExact('blueberry'));
  
  // 测试移除最相似单词（比如输入"appel"匹配"apple"）
  console.log('移除的单词:', removeMostSimilar('appel'));
  console.log('再次搜索"apple":', searchExact('apple'));
}

testEngine();

3. 可选优化点 #

• 持久化：若需要重启服务后保留修改，可将语料库的增量修改（添加/删除）写入额外的JSON文件，初始化时同时加载原始TXT和增量文件；
• 性能优化：针对大规模语料库，可提前建立n-gram索引，减少相似性计算的遍历次数；
• 相似规则扩展：可替换编辑距离算法为词干匹配，或前缀/后缀匹配，根据需求调整。

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