如何基于Trie前缀树实现子串包含、乱序匹配的单词查询功能

以下是一款可适配任意语言字母/文字系统的Trie实现：

class TrieNode {
  constructor(key) {
    // 节点存储的当前序列字符
    this.key = key;
    // 父节点引用
    this.parent = null;
    // 子节点哈希表
    this.children = {};
    // 标记当前节点是否为单词终点
    this.end = false;
  }

  getWord() {
    let output = [];
    let node = this;

    while (node !== null) {
      output.unshift(node.key)
      node = node.parent
    }

    return output.join('')
  }
}

class Trie {
  constructor() {
    this.base = new TrieNode(null)
  }

  insert(word) {
    let node = this.base

    const points = Array.from(word)

    for (const i in points) {
      const point = points[i]
      if (!node.children[point]) {
        const child = node.children[point] = new TrieNode(point)
        child.parent = node
      }

      node = node.children[point]

      if (i == word.length - 1) {
        node.end = true
      }
    }
  }

  contains(word) {
    let node = this.base

    const points = Array.from(word)

    for (const i in points) {
      const point = points[i]

      if (node.children[point]) {
        node = node.children[point]
      } else {
        return false
      }
    }

    return node.end;
  }

  find(prefix) {
    let node = this.base
    let output = []

    const points = Array.from(prefix)

    for (const i in points) {
      const point = points[i]

      // 校验前缀是否存在对应词条
      if (node.children[point]) {
        node = node.children[point]
      } else {
        // 无匹配直接返回空结果
        return output
      }
    }

    const stack = [node]
    while (stack.length) {
      node = stack.shift()
      // 遍历到单词终点，加入结果集
      if (node.end) {
        output.unshift(node.getWord())
      }

      // 遍历所有子节点递归收集词条
      for (var child in node.children) {
        stack.push(node.children[child])
      }
    }

    return output
  }
}

目前这套Trie结构已经可以高效实现前缀（开头位置）匹配，基于Scrabble词表的测试代码与运行效果如下：

const fs = require('fs')
const Trie = require('./Trie')

// 读取词表文件
const words = fs.readFileSync('tmp/scrabble.csv', 'utf-8')
  .trim()
  .split(/\n+/)
  .map(x => x.trim())

const trie = new Trie()
// 所有词条插入Trie
words.forEach(word => trie.insert(word))

// 查询前缀为"zy"的所有单词
console.log(trie.find('zy'))
// 返回结果：
[
  'zygodactylous', 'zygomorphies', 'zygapophysis',
  'zygapophyses',  'zygomorphic',  'zymologies',
  'zygospores',    'zygosities',   'zygomorphy',
  'zygodactyl',    'zymurgies',    'zymograms',
  'zymogenes',     'zygotenes',    'zygospore',
  'zygomatic',     'zyzzyvas',     'zymosans',
  'zymology',      'zymogram',     'zymogens',
  'zymogene',      'zygotene',     'zygosity',
  'zygomata',      'zyzzyva',      'zymurgy',
  'zymotic',       'zymosis',      'zymoses',
  'zymosan',       'zymogen',      'zymases',
  'zygotic',       'zygotes',      'zygosis',
  'zygoses',       'zygomas',      'zydecos',
  'zymase',        'zygote',       'zygose',
  'zygoma',        'zygoid',       'zydeco',
  'zymes',         'zyme'
]

测试使用的scrabble.csv为公开可用的官方拼字游戏词典。

标准前缀Trie仅对前缀匹配有最优性能，针对「任意位置子串匹配」「乱序字母组词」两类需求，可以基于Trie做改造实现，但存在明确的效率瓶颈，也有更适配场景的替代方案，具体说明如下： #

一、包含指定子串匹配 #

最初设想的「枚举所有可能子串构建Trie」方案逻辑可行，但内存开销为O(n²)量级：对平均长度为5的100万单词，总子串数量可达1500万条，内存压力极大，不适合生产环境大规模使用。

基于Trie的实现思路 #

可以将全子串Trie优化为后缀Trie（后缀树）：插入单词时，仅将单词的所有后缀插入Trie，每个节点额外挂载该后缀对应的原单词ID列表。查询时从根节点逐字符遍历输入子串，走到对应节点后，直接取出节点上挂载的所有原单词即可。该方案内存开销比全子串Trie低一个量级，但仍远高于纯前缀Trie，仅适合10万词条以下的中小规模词表。

效率瓶颈与替代方案 #

后缀Trie的内存开销会随单词平均长度增长快速升高，且构建速度慢。如果追求百万级词条下的高性能查询，更适配的方案为：

• 后缀数组+二分查找：将所有单词的所有后缀排序构建数组，查询子串时通过二分定位匹配区间，内存占用仅为后缀Trie的1/5~1/3，查询速度可达毫秒级
• Aho-Corasick自动机：适合批量多模式子串匹配场景，一次扫描即可返回所有命中的子串结果

二、乱序字母组词匹配 #

之前尝试的「单词字母排序后存入Trie，查询时排序输入串做包含匹配」的方案存在逻辑漏洞是必然的：排序后的字符串做子串匹配只能覆盖排序后字符连续的场景，无法支持字母重复、子集选取的匹配规则，比如输入caldku匹配duck的场景就无法覆盖。

基于Trie的实现思路 #

可以构建定序无重复Trie实现该需求：

• 插入阶段：先将单词按固定规则（如英文字母a-z顺序）排序，插入Trie时要求子节点字符顺序必须大于等于父节点，避免重复路径，每个终止节点挂载对应的原单词
• 查询阶段：将输入串按相同规则排序，在Trie上做回溯遍历，遍历过程中统计已选字符的计数，只要不超过输入串对应字符的总计数就可以继续深入，每遇到终止节点就将对应单词加入结果集
  该方案逻辑可行，但查询过程需要回溯，性能和输入串长度强相关，输入串长度超过10时性能会明显下降。

效率瓶颈与替代方案 #

Trie的有序前缀遍历特性本质上和乱序匹配的需求不匹配，回溯遍历的开销很高。更适配的方案为字母计数签名哈希索引：

• 预处理阶段：为每个单词生成固定长度的计数签名，比如英文场景下生成长度为26的数组，每个位置存储对应字母在单词中的出现次数，将签名序列化为字符串作为哈希表的Key，Value为对应签名的所有单词列表；额外按单词长度、是否包含高频字母等维度做分桶索引，减少查询时的比对量
• 查询阶段：先统计输入串的各字母计数，遍历所有长度不超过输入串的分桶，比对桶内单词的签名，只要单词每个字母的计数都小于等于输入串对应字母的计数，就将该单词加入结果集
  该方案在百万级词表下的查询速度比改造Trie快一个量级以上，内存开销也更低，是目前拼字游戏、乱序组词类场景的主流实现方案。

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