JavaScript 使用前缀树（Trie）实现文本高亮

前缀树实现文本高亮示例代码

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}

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

  insert(word) {
    let currentNode = this.root;

    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      if (!currentNode.children.has(char)) {
        currentNode.children.set(char, new TrieNode());
      }
      currentNode = currentNode.children.get(char);
    }

    currentNode.isEndOfWord = true;
  }

  search(word) {
    let currentNode = this.root;

    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      if (currentNode.children.has(char)) {
        currentNode = currentNode.children.get(char);
      } else {
        return false;
      }
    }

    return currentNode.isEndOfWord;
  }
}

function highlightText(text, keywords) {
  const trie = new Trie();
  for (const keyword of keywords) {
    trie.insert(keyword);
  }

  let highlightedText = "";
  let currentWord = "";

  for (let i = 0; i < text.length; i++) {
    const char = text[i];
    currentWord += char;

    if (trie.search(currentWord)) {
      highlightedText += `<span class="highlight">${currentWord}</span>`;
      currentWord = "";
    } else if (!trie.search(currentWord) && trie.search(currentWord.slice(0, currentWord.length - 1))) {
      highlightedText += currentWord.slice(0, currentWord.length - 1);
      currentWord = char;
    }
  }

  // 处理最后一个单词
  if (currentWord !== "") {
    highlightedText += currentWord;
  }

  return highlightedText;
}

// 调用示例
const text = "This is a sample text to highlight certain words.";
const keywords = ["sample", "highlight", "words"];
const highlightedText = highlightText(text, keywords);
console.log(highlightedText);

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}

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

  insert(word) {
    let currentNode = this.root;

    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      if (!currentNode.children.has(char)) {
        currentNode.children.set(char, new TrieNode());
      }
      currentNode = currentNode.children.get(char);
    }

    currentNode.isEndOfWord = true;
  }

  highlightText(text, highlightClass = 'highlight') {
    const result = [];
    let currentWord = '';
    let currentNode = this.root;

    for (const char of text) {
      currentWord += char;
      // console.log(currentWord, 'currentWord')
      if (currentNode.children.has(char)) {
        currentNode = currentNode.children.get(char);
        console.log(currentNode, 'currentNode')
        if (currentNode.isEndOfWord) {
          result.push(`<span class="${highlightClass}">${currentWord}</span>`);
          currentWord = '';
          currentNode = this.root;
        }
      } else {
        result.push(currentWord);
        currentWord = '';
        currentNode = this.root;
      }
    }
    if (currentWord) {
      result.push(currentWord);
    }
    return result.join('');
  }
}


// 调用示例
const text = "This is a sample text to highlight certain words.";
const keywords = "words";
let trie = new Trie();
trie.insert(keywords);
console.log(trie.root);
console.log(trie.highlightText(text));