首頁  >  文章  >  web前端  >  忘記您所知道的關於字符串搜索的一切 - 嘗試會讓您大吃一驚!

忘記您所知道的關於字符串搜索的一切 - 嘗試會讓您大吃一驚!

Linda Hamilton
Linda Hamilton原創
2024-09-21 06:24:321011瀏覽

Forget Everything You Know About String Searching - Tries Will Blow Your Mind!

Trie資料結構簡介

trie,也稱為前綴樹,是一種高效的樹狀資料結構,用於儲存和檢索字串。它對於涉及字串搜尋、前綴匹配和自動完成功能的任務特別有用。

發音:

  • 這是一個單音節字
  • 最後的「ie」發音為長「e」音,類似「see」或「tree」
  • 它與「pie」或「die」不押韻 這種發音有助於將其與其他外觀相似的單字區分開來,並強調其與資料檢索操作的聯繫。

何時使用 Trie

在您需要以下情況的情況下嘗試是理想的選擇:

  1. 快速執行基於前綴的搜尋
  2. 實現自動完成功能
  3. 儲存單字字典以進行拼字檢查
  4. 高效儲存和檢索具有公共前綴的字串 ## 可視化 Trie

讓我們想像一個包含單字「cat」、「car」和「dog」的特里樹:

       root
     /   |   \
    c    d    ...
   /     |
  a      o
 / \     |
t   r    g

每個節點代表一個字符,從根節點到葉節點的路徑組成完整的單字。

在 JavaScript 中實作 Trie

讓我們用 JavaScript 實作一個基本的 trie 結構:

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

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

  // Insert a word into the trie
  insert(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  // Search for a word in the trie
  search(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return node.isEndOfWord;
  }

  // Check if any word starts with the given prefix
  startsWith(prefix) {
    let node = this.root;
    for (let char of prefix) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return true;
  }
}

// Example usage
const trie = new Trie();

// Insert words
trie.insert("apple");
trie.insert("app");
trie.insert("banana");

console.log(trie.search("apple"));    // Output: true
console.log(trie.search("app"));      // Output: true
console.log(trie.search("appl"));     // Output: false
console.log(trie.startsWith("app"));  // Output: true
console.log(trie.startsWith("ban"));  // Output: true
console.log(trie.startsWith("cat"));  // Output: false

守則解釋

  1. class TrieNode:表示 trie 中的一個節點。每個節點都有:: 一個用於儲存子節點的物件: 一個布林標誌,用於標記單字的結尾
  2. class Trie:主要的 trie 結構及其方法:
    • 插入:在特里樹上加上一個單字
    • 搜尋:檢查單字是否存在於 trie
    • startsWith:檢查 trie 中是否有任何單字以給定前綴開頭
  3. 該方法遍歷 trie,為不存在的字元建立新節點,並將最後一個節點標記為單字的結尾。
  4. 該方法沿著給定單字的路徑遍歷 trie,如果找到整個單字並將其標記為完整單詞,則返回。
  5. 該方法類似,但只檢查給定的前綴是否存在於 trie 中,而不管它是否是一個完整的單字。

時間與空間複雜度

  • 時間複雜度:
    • 插入:O(m),其中 m 是單字的長度
    • 搜尋:O(m),其中 m 是單字的長度
    • StartsWith:O(m),其中 m 是前綴的長度
  • 空間複雜度:O(n * m),其中n是單字數,m是單字的平均長度

Tries 為字串相關操作提供了出色的效能,特別是在處理大量具有公共前綴的單字時。它們提供快速查找和前綴匹配,這使得它們在自動完成系統、IP 路由表和字典實現等各種應用中具有無價的價值。

如果您喜歡本教程,請在此處關注我,並在 X/Twitter 上關注我:@turckalicious。本文是在 Wonderfall (https://wonderfall.xyz) 的幫助下完成的,這是一款由人工智慧驅動的互動式文件編輯器,可幫助您更快地研究、寫作和迭代。

以上是忘記您所知道的關於字符串搜索的一切 - 嘗試會讓您大吃一驚!的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn