如何用JavaScript正确实现自动补全功能？

针对7000个词汇的自动补全需求，以下几种方案都能高效实现，无需依赖内置Trie结构：

1. 手动实现Trie树 #

这是前缀匹配的经典方案，适合频繁查询的场景，查询时间复杂度为O(k)（k为输入前缀的长度）。

实现思路： #

• 定义Trie节点，包含子节点映射、单词结尾标记，同时存储完整单词方便直接返回结果。
• 先将所有词汇插入Trie树，用户输入字符后，沿着Trie树的前缀路径遍历，收集所有匹配的词汇。

代码示例： #

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
    this.word = ''; // 存储完整单词，避免后续拼接
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }
    node.isEnd = true;
    node.word = word;
  }

  getPrefixMatches(prefix) {
    let node = this.root;
    const matches = [];
    // 定位到前缀的最后一个节点
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return matches; // 无匹配前缀，直接返回空数组
      }
      node = node.children.get(char);
    }
    // 递归收集所有子节点中的完整单词
    this.collectWords(node, matches);
    return matches;
  }

  collectWords(node, matches) {
    if (node.isEnd) {
      matches.push(node.word);
    }
    for (const child of node.children.values()) {
      this.collectWords(child, matches);
    }
  }
}

// 使用示例
const vocab = ['apple', 'app', 'application', 'banana', 'berry'];
const trie = new Trie();
vocab.forEach(word => trie.insert(word));
console.log(trie.getPrefixMatches('app')); // 输出 ["app", "apple", "application"]

2. 前缀哈希表预处理 #

如果不想实现复杂的Trie，可以预先构建前缀到词汇列表的哈希表，查询时直接通过前缀取结果，时间复杂度O(1)。

实现思路： #

• 遍历所有词汇，生成该词汇的所有可能前缀（比如"apple"的前缀包括"a", "ap", "app", "appl", "apple"）。
• 将每个前缀作为键，对应的词汇添加到哈希表的值数组中（注意去重，避免同一词汇被多次添加）。
• 用户输入前缀后，直接从哈希表中取出对应的词汇列表即可。

代码示例： #

function buildPrefixMap(vocab) {
  const prefixMap = new Map();
  vocab.forEach(word => {
    // 生成所有前缀
    for (let i = 1; i <= word.length; i++) {
      const prefix = word.slice(0, i);
      if (!prefixMap.has(prefix)) {
        prefixMap.set(prefix, []);
      }
      // 避免重复添加同一单词
      if (!prefixMap.get(prefix).includes(word)) {
        prefixMap.get(prefix).push(word);
      }
    }
  });
  return prefixMap;
}

// 使用示例
const vocab = ['apple', 'app', 'application', 'banana', 'berry'];
const prefixMap = buildPrefixMap(vocab);
console.log(prefixMap.get('app')); // 输出 ["app", "apple", "application"]

优缺点： #

• 优点：查询速度极快，实现简单。
• 缺点：预处理时会占用更多内存（7000个词汇的总前缀数约几万级别，完全可接受）。

3. 直接使用数组filter（备选方案） #

虽然理论时间复杂度是O(n)，但7000个元素在JavaScript中处理速度非常快，实际体验可能和Trie相差无几，适合快速实现的场景。

代码示例： #

const vocab = ['apple', 'app', 'application', 'banana', 'berry'];

function getAutocompleteSuggestions(prefix) {
  return vocab.filter(word => word.startsWith(prefix));
}

console.log(getAutocompleteSuggestions('app')); // 输出 ["app", "apple", "application"]

适用场景： #

• 词汇量增长不太快，或者对实现复杂度要求极低的情况。

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