JavaScript使用前綴樹(trie樹)實現(xiàn)文本高亮

更新時間：2024年04月25日 10:43:57 作者：weixin_47806733

這篇文章主要為大家詳細介紹了JavaScript如何使用前綴樹(trie樹)實現(xiàn)文本高亮效果,文中的示例代碼講解詳細,有需要的小伙伴可以參考下

如何使用前綴樹（也稱為Trie樹）來實現(xiàn)文本高亮

前綴樹類似字典樹，二者是相似的數(shù)據(jù)結(jié)構(gòu)。它們的名稱不同，但指的是相同的概念。字典樹是用來存儲和處理字符串集合的樹狀數(shù)據(jù)結(jié)構(gòu)，它在某些情況下也被稱為前綴樹。

異同點：

命名差異：字典樹和前綴樹是同一種數(shù)據(jù)結(jié)構(gòu)，只是不同的命名方式而已。

數(shù)據(jù)結(jié)構(gòu)：字典樹/前綴樹是一個多叉樹，其中每個節(jié)點代表一個字符，從根節(jié)點到葉子節(jié)點的路徑表示一個完整的字符串。

字符串存儲：字典樹/前綴樹適用于存儲大量字符串，并能高效地進行插入、刪除、搜索等操作。

前綴匹配：字典樹/前綴樹的主要優(yōu)勢在于支持按前綴搜索，能夠快速找到所有以某個前綴開頭的字符串。

總結(jié)來說，字典樹和前綴樹并沒有本質(zhì)上的區(qū)別，只是在命名上有所差異。它們都是一種用于高效存儲和處理字符串集合的數(shù)據(jù)結(jié)構(gòu)，特別適用于前綴搜索等操作。

使用前綴樹（也稱為Trie樹）來實現(xiàn)文本高亮有以下幾個步驟：

構(gòu)建前綴樹：將需要高亮的關(guān)鍵詞構(gòu)建成前綴樹。每個節(jié)點代表一個字符，從根節(jié)點開始，通過邊連接到下一個字符節(jié)點。葉子節(jié)點表示一個完整的關(guān)鍵詞。

遍歷文本：遍歷待高亮的文本，逐個字符進行匹配。

匹配過程：從根節(jié)點開始，逐個字符匹配。如果當前字符在前綴樹中有對應(yīng)的子節(jié)點，則繼續(xù)向下匹配；如果沒有匹配到子節(jié)點，說明不是關(guān)鍵詞的一部分，跳到下一個字符

高亮處理：當匹配到某個關(guān)鍵詞的葉子節(jié)點時，記錄該位置并標記為需要高亮。繼續(xù)匹配下一個字符，直到文本遍歷完成。

高亮展示：根據(jù)標記的位置信息，在文本中添加相應(yīng)的HTML標簽或CSS樣式來實現(xiàn)高亮效果。

下面是一個簡單的示例代碼，用于演示使用前綴樹實現(xiàn)文本高亮：

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;
}

// 調(diào)用示例
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 類，用于構(gòu)建前綴樹，并提供了 insert 和 search 方法。然后，highlightText 函數(shù)接受文本和關(guān)鍵詞作為輸入，使用前綴樹來實現(xiàn)文本高亮。最后，將高亮文本作為結(jié)果返回。

方法補充

除了上文的方法，小編還為大家整理了使用前綴樹/字典樹/trie樹實現(xiàn)文本高亮的方法，需要的可以參考下

示例代碼

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('');
  }
}


// 調(diào)用示例
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));

到此這篇關(guān)于JavaScript使用前綴樹(trie樹)實現(xiàn)文本高亮的文章就介紹到這了,更多相關(guān)JavaScript文本高亮內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: