Node.js猜词机器人开发：变形字符匹配与存储优化需求

一、存储格式选择 #

• JSON格式：适合存储结构化数据（字符映射表、词汇集合），读写便捷，Node.js原生支持，完全适配1000+词汇量的场景。
• SQLite（可选）：如果未来词汇量会增长至上万级，用轻量数据库存储，支持快速查询和索引优化。

示例JSON存储结构：

{
  "charMap": {
    "a": ["@", "ª", "₳"],
    "b": ["₿", "฿"],
    "c": ["₵", "₡", "¢"],
    "e": ["£", "€", "ɛ"],
    "s": ["$", "&", "ʂ", "₰", "₷"],
    "l": ["|", "ł", "ʟ"],
    "p": ["℗", "‽", "⁋", "₽", "₱", "Þ", "þ"]
  },
  "vocab": ["sleep", "as", "cat", "dog"]
}

二、猜词逻辑优化：前缀树（Trie）+ 字符映射 + 容错处理 #

针对现有方案的问题，推荐基于前缀树改造，同时解决键重复、缺失字母识别问题，并兼顾匹配效率：

1. 核心思路 #

• 前缀树存储标准词汇，每个节点关联对应字符的所有变形体，遍历输入时直接匹配变形字符，无需先全量转译输入。
• 递归遍历前缀树时增加容错分支，允许最多跳过一个输入字符（可调整容错次数），实现缺失字母的识别。

完整实现代码 #

// 模拟从JSON文件加载字符映射和词汇库
const { charMap, vocab } = {
  "charMap": {
    "a": ["@", "ª", "₳"],
    "b": ["₿", "฿"],
    "c": ["₵", "₡", "¢"],
    "e": ["£", "€", "ɛ"],
    "s": ["$", "&", "ʂ", "₰", "₷"],
    "l": ["|", "ł", "ʟ"],
    "p": ["℗", "‽", "⁋", "₽", "₱", "Þ", "þ"],
    "d": ["d"],
    "o": ["0", "o"],
    "g": ["G", "g"]
  },
  "vocab": ["sleep", "as", "cat", "dog"]
};

// 构建前缀树
function buildTrie() {
  const root = {};
  vocab.forEach(word => {
    let node = root;
    for (const char of word) {
      // 将标准字符及所有变形字符关联到同一节点
      const allRelatedChars = [char, ...(charMap[char] || [])];
      allRelatedChars.forEach(c => {
        if (!node[c]) node[c] = {};
      });
      // 以标准字符作为节点主标识，用于拼接结果词
      node = node[char];
    }
    node.isEnd = true;
    node.word = word;
  });
  return root;
}

// 带单字符缺失容错的猜词函数
function guessWord(input, trie) {
  const matchedWords = [];
  const inputChars = input.split('');

  function traverse(node, inputIndex, missedCount, currentWord) {
    // 遍历完所有输入字符，检查是否匹配到完整词汇
    if (inputIndex === inputChars.length) {
      if (node.isEnd) matchedWords.push(node.word);
      // 允许跳过一个字符，匹配比输入长一位的词汇
      if (missedCount < 1) {
        Object.keys(node).forEach(key => {
          if (key !== 'isEnd' && key !== 'word') {
            traverse(node[key], inputIndex, missedCount + 1, currentWord + key);
          }
        });
      }
      return;
    }

    const currentInputChar = inputChars[inputIndex];
    // 遍历当前节点的所有子节点，匹配变形字符
    Object.keys(node).forEach(key => {
      if (key === 'isEnd' || key === 'word') return;
      const matchableChars = [key, ...(charMap[key] || [])];
      if (matchableChars.includes(currentInputChar)) {
        // 字符匹配成功，继续遍历下一位
        traverse(node[key], inputIndex + 1, missedCount, currentWord + key);
      } else if (missedCount < 1) {
        // 字符不匹配，尝试跳过当前输入字符（容错）
        traverse(node[key], inputIndex, missedCount + 1, currentWord + key);
      }
    });

    // 尝试跳过当前输入字符，继续遍历当前节点（匹配比输入短一位的词汇）
    if (missedCount < 1) {
      traverse(node, inputIndex + 1, missedCount + 1, currentWord);
    }
  }

  traverse(trie, 0, 0, '');
  return matchedWords;
}

// 测试用例
const trie = buildTrie();
console.log(guessWord("₰ʟ£ɛ‽", trie)); // 输出 ["sleep"]
console.log(guessWord("@s", trie)); // 输出 ["as"]
console.log(guessWord("d0G", trie)); // 输出 ["dog"]
console.log(guessWord("₰ʟ£‽", trie)); // 缺失一个e，输出 ["sleep"]
console.log(guessWord("C@R", trie)); // 无匹配，输出 []

三、方案优势 #

• 解决键重复问题：字符映射与前缀树分离，同一标准字符的所有变形体共享同一树节点，无需重复定义。
• 支持单字符缺失：通过容错分支实现最多一个字符的缺失匹配，可按需调整容错次数。
• 效率提升：遍历过程中直接匹配变形字符，不匹配时提前终止分支，比先转译再查集合的方式更高效。

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