本文介绍如何在 JavaScript 中利用前缀树（Trie 树）数据结构实现高效的文本关键词高亮功能。通过构建多叉树结构存储关键词，遍历文本进行字符匹配，并在匹配到完整关键词时记录位置，最终通过添加 HTML 标签实现高亮显示。
前缀树与字典树的概念辨析
介绍如何使用前缀树（即 Trie 树）来实现文本高亮功能
前缀树与字典树属于相似的数据结构，两者名称不同但指代相同的概念。字典树是一种用于存储和处理字符串集合的树状数据结构，在某些场景下也被称为前缀树。
分析两者的异同点：
命名差异：字典树与前缀树本质上是同一种数据结构，仅存在命名上的区别。
数据结构特征：字典树或前缀树是一种多叉树结构，其中每个节点代表一个字符。从根节点到叶子节点的路径构成一个完整的字符串。
字符串存储特性：该结构适用于存储大量字符串，并能高效执行插入、删除和搜索等操作。
前缀匹配优势：字典树/前缀树的核心优势在于支持按前缀进行搜索，能够快速检索出所有以特定前缀开头的字符串。
综上所述，字典树和前缀树没有本质区别，仅命名不同。它们均用于高效存储和处理字符串集合，特别适用于前缀搜索等应用场景。
JavaScript 实现文本高亮的步骤
使用前缀树（Trie 树）实现文本高亮的主要步骤如下：
构建前缀树：将需要高亮的关键词集合构建为前缀树。每个节点代表一个字符，从根节点开始，通过边连接至下一个字符节点。叶子节点标识一个完整的关键词。
遍历文本：对待高亮的文本进行遍历，逐个字符进行匹配操作。
匹配过程：从根节点开始，逐个字符进行匹配。若当前字符在前缀树中存在对应的子节点，则继续向下匹配；若未找到匹配的子节点，说明当前字符不属于任何关键词的一部分，此时跳过该字符并处理下一个字符。
高亮处理：当匹配过程到达某个关键词的叶子节点时，记录该位置并标记为需要高亮。随后继续匹配下一个字符，直至文本遍历结束。
高亮展示：根据记录的位置信息，在文本中插入相应的 HTML 标签或应用 CSS 样式，从而实现高亮效果。
以下提供一个简单的示例代码，演示如何使用前缀树实现文本高亮：
前缀树实现文本高亮示例代码
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);上述代码定义了 TrieNode 和 Trie 类，用于构建前缀树，并提供了 insert 和 search 方法。随后，highlightText 函数接收文本和关键词作为输入，利用前缀树实现高亮逻辑。最后，返回处理后的高亮文本结果。
方法补充说明
除上述方法外，还整理了其他使用前缀树、字典树或 Trie 树实现文本高亮的方案，供参考。
示例代码展示
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));本文关于 JavaScript 使用前缀树（Trie 树）实现文本高亮的介绍到此结束。如需了解更多 JavaScript 文本高亮相关内容，请搜索本站历史文章或浏览后续相关文章，感谢支持。