문자열 검색에 대해 알고 있는 모든 것을 잊어버리십시오 - 시도는 당신의 마음을 사로잡을 것입니다!

Trie 데이터 구조 소개

접두사 트리라고도 알려진 트리는 문자열을 저장하고 검색하는 데 사용되는 효율적인 트리형 데이터 구조입니다. 문자열 검색, 접두사 일치, 자동 완성 기능과 관련된 작업에 특히 유용합니다.

발음:

• 단음절 단어입니다
• 끝의 "ie"는 "see" 또는 "tree"와 유사한 긴 "e" 소리로 발음됩니다.
• '파이'나 '다이'와 운율이 맞지 않습니다. 이 발음은 유사해 보이는 다른 단어와 구별하는 데 도움이 되며 데이터 검색 작업과의 연관성을 강조합니다.

트라이를 사용해야 하는 경우

시도는 다음과 같은 상황에서 이상적입니다.

1. 접두사 기반 검색을 빠르게 수행
2. 자동완성 기능 구현
3. 맞춤법 검사를 위한 단어 사전 저장
4. 공통 접두사가 있는 문자열을 효율적으로 저장하고 검색합니다. ## 트라이 시각화

"cat", "car", "dog"라는 단어가 포함된 트리를 시각화해 보겠습니다.

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

각 노드는 문자를 나타내며, 루트에서 리프 노드까지의 경로는 완전한 단어를 구성합니다.

JavaScript에서 Trie 구현하기

JavaScript에서 기본 트라이 구조를 구현해 보겠습니다.

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: 트리의 노드를 나타냅니다. 각 노드에는 다음이 포함됩니다.: 하위 노드를 저장하는 개체: 단어 끝을 표시하는 부울 플래그
2. 클래스 Trie: 메소드가 포함된 주요 Trie 구조:
   • 삽입: 트라이에 단어를 추가합니다
   • 검색: 트라이에 단어가 있는지 확인
   • startsWith: 트리에 있는 단어 중 주어진 접두어로 시작하는 단어가 있는지 확인
3. 이 메서드는 트라이를 순회하여 존재하지 않는 문자에 대해 새 노드를 만들고 마지막 노드를 단어의 끝으로 표시합니다.
4. 이 메소드는 주어진 단어의 경로를 따라 트라이를 순회하며, 전체 단어가 발견되어 완전한 단어로 표시되면 반환됩니다.
5. 이 방법은 와 유사하지만 완전한 단어인지 여부에 관계없이 주어진 접두사가 트라이에 존재하는지 확인합니다.

시간과 공간의 복잡성

• 시간 복잡성:
  • 삽입: O(m), 여기서 m은 단어의 길이입니다
  • 검색: O(m), 여기서 m은 단어의 길이
  • 시작: O(m), 여기서 m은 접두사의 길이입니다
• 공간 복잡도:O(n * m), 여기서 n은 단어 수이고 m은 단어의 평균 길이

Tries는 특히 공통 접두사가 있는 대규모 단어 집합을 처리할 때 문자열 관련 작업에 탁월한 성능을 제공합니다. 빠른 조회와 접두사 일치 기능을 제공하므로 자동 완성 시스템, IP 라우팅 테이블, 사전 구현과 같은 다양한 애플리케이션에서 매우 유용합니다.

이 튜토리얼이 마음에 드셨다면 여기와 X/Twitter(@turckalicious)에서 저를 팔로우하세요. 이 기사는 더 빠르게 조사하고, 작성하고, 반복하는 데 도움이 되는 AI 기반 대화형 문서 편집기인 Wonderfall(https://wonderfall.xyz)의 도움으로 작성되었습니다.

위 내용은 문자열 검색에 대해 알고 있는 모든 것을 잊어버리십시오 - 시도는 당신의 마음을 사로잡을 것입니다!의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!