JavaScript의 트라이 접두사 트리에 대한 자세한 해석

이 글은 주로 javascript trie 단어 검색 트리의 예를 소개하며, trie의 개념과 구현에 대해 자세히 소개합니다. 관심 있는 친구들은 참고할 수 있습니다.

Introduction

Trie Tree (from 단어 검색)은 접두어, 단어 검색 트리, 사전 트리라고도 알려져 있으며 빠른 검색에 사용되는 트리 구조, 해시 트리의 변형 및 다중 포크 트리 구조입니다.

장점은 불필요한 문자열 비교를 최소화하고 해시 테이블보다 쿼리 효율성이 높다는 것입니다.

Trie의 핵심 아이디어는 공간과 시간을 교환하는 것입니다. 문자열의 공통 접두사를 사용하면 쿼리 시간 오버헤드를 줄여 효율성을 높일 수 있습니다.

Trie 트리에도 단점이 있습니다. 문자와 숫자만 처리한다고 가정하면 각 노드에는 최소 52+10개의 하위 노드가 있습니다. 메모리를 절약하기 위해 연결 목록이나 배열을 사용할 수 있습니다. JS 배열은 동적이며 최적화 기능이 내장되어 있으므로 JS에서는 배열을 직접 사용합니다.

기본 속성

1. 루트 노드는 문자를 포함하지 않으며, 루트 노드를 제외한 모든 하위 노드는 하나의 문자를 포함합니다

2. 루트 노드에서 특정 노드까지. 경로를 통과하는 문자는 노드에 해당하는 문자열로 연결됩니다. 각 노드의 모든 하위 노드에는 Trie의 삽입 방법이 포함됩니다. 사전 트리는 주로 단어 빈도 통계에 사용되므로 numPass, numEnd를 포함한 많은 노드 속성을 갖지만 매우 중요한 속성을 갖습니다.

insert 메소드는 무거운 단어를 삽입하는 데 사용됩니다. 시작하기 전에 해당 단어가 적합한지, 특수 문자와 공백이 나타날 수 없는지 확인해야 합니다. 삽입 시 캐릭터가 분할되어 각 노드에 배치됩니다. numPass는 노드가 전달될 때마다 수정되어야 합니다.

3. Optimization

이제 각 메소드에는 c=-48 연산이 있습니다. 사실 숫자, 대문자, 소문자 사이에 다른 문자가 있어서 불필요한 공간 낭비가 발생합니다

// by 司徒正美
class Trie {
 constructor() {
  this.root = new TrieNode();
 }
 isValid(str) {
  return /^[a-z1-9]+$/i.test(str);
 }
 insert(word) {
  // addWord
  if (this.isValid(word)) {
   var cur = this.root;
   for (var i = 0; i < word.length; i++) {
    var c = word.charCodeAt(i);
    c -= 48; //减少”0“的charCode
    var node = cur.son[c];
    if (node == null) {
     var node = (cur.son[c] = new TrieNode());
     node.value = word.charAt(i);
     node.numPass = 1; //有N个字符串经过它
    } else {
     node.numPass++;
    }
    cur = node;
   }
   cur.isEnd = true; //樯记有字符串到此节点已经结束
   cur.numEnd++; //这个字符串重复次数

   return true;
  } else {
   return false;
  }
 }
 remove(word){
   if (this.isValid(word)) {
     var cur = this.root;
     var array = [], n = word.length
     for (var i = 0; i < n; i++) {
       var c = word.charCodeAt(i);
       c = this.getIndex(c)
       var node = cur.son[c];
       if(node){
         array.push(node)
         cur = node
       }else{
         return false
       }
 
     }
     if(array.length === n){
       array.forEach(function(){
         el.numPass--
       })
       cur.numEnd --
       if( cur.numEnd == 0){
         cur.isEnd = false
       } 
     }
   }else{
     return false
   }
 }
 preTraversal(cb){//先序遍历
    function preTraversalImpl(root, str, cb){ 
      cb(root, str);
      for(let i = 0,n = root.son.length; i < n; i ++){
        let node = root.son[i];
        if(node){
          preTraversalImpl(node, str + node.value, cb);
        }
      }
    } 
    preTraversalImpl(this.root, "", cb);
  }
 // 在字典树中查找是否存在某字符串为前缀开头的字符串(包括前缀字符串本身)
 isContainPrefix(word) {
  if (this.isValid(word)) {
   var cur = this.root;
   for (var i = 0; i < word.length; i++) {
    var c = word.charCodeAt(i);
    c -= 48; //减少”0“的charCode
    if (cur.son[c]) {
     cur = cur.son[c];
    } else {
     return false;
    }
   }
   return true;
  } else {
   return false;
  }
 }
 isContainWord(str) {
  // 在字典树中查找是否存在某字符串(不为前缀)
  if (this.isValid(word)) {
   var cur = this.root;
   for (var i = 0; i < word.length; i++) {
    var c = word.charCodeAt(i);
    c -= 48; //减少”0“的charCode
    if (cur.son[c]) {
     cur = cur.son[c];
    } else {
     return false;
    }
   }
   return cur.isEnd;
  } else {
   return false;
  }
 }
 countPrefix(word) {
  // 统计以指定字符串为前缀的字符串数量
  if (this.isValid(word)) {
   var cur = this.root;
   for (var i = 0; i < word.length; i++) {
    var c = word.charCodeAt(i);
    c -= 48; //减少”0“的charCode
    if (cur.son[c]) {
     cur = cur.son[c];
    } else {
     return 0;
    }
   }
   return cur.numPass;
  } else {
   return 0;
  }
 }
 countWord(word) {
  // 统计某字符串出现的次数方法
  if (this.isValid(word)) {
   var cur = this.root;
   for (var i = 0; i < word.length; i++) {
    var c = word.charCodeAt(i);
    c -= 48; //减少”0“的charCode
    if (cur.son[c]) {
     cur = cur.son[c];
    } else {
     return 0;
    }
   }
   return cur.numEnd;
  } else {
   return 0;
  }
 }
}

class TrieNode {
 constructor() {
  this.numPass = 0;//有多少个单词经过这节点
  this.numEnd = 0; //有多少个单词就此结束
  this.son = [];
  this.value = ""; //value为单个字符
  this.isEnd = false;
 }
}

그런 다음 관련 방법은 c-= 48을 c = this.getIndex(c)

Test

// by 司徒正美
getIndex(c){
   if(c < 58){//48-57
     return c - 48
   }else if(c < 91){//65-90
     return c - 65 + 11
   }else {//> 97 
     return c - 97 + 26+ 11
   }
 }

Trie 트리와 기타 데이터 구조의 비교

Trie 트리와 Binary로 변경하는 것입니다. 검색 트리

이진 검색 트리는 우리가 접하게 되는 가장 초기의 트리 구조여야 합니다. 데이터 크기가 n일 때 이진 검색 트리 삽입, 검색 및 삭제 작업의 시간 복잡도는 일반적으로 O(log)에 불과합니다. n), 최악의 경우 전체 트리의 모든 노드는 하나의 자식 노드만 가지며 선형 리스트로 변질됩니다. 이때 삽입, 검색, 삭제 작업의 시간 복잡도는 O(n)입니다.

일반적으로 Trie 트리의 높이 n은 검색 문자열의 길이 m보다 훨씬 크기 때문에 검색 연산의 시간 복잡도는 대개 O(m)이고, 최악의 경우 시간 복잡도는 O(n)입니다. ). Trie 트리의 최악의 경우 검색이 이진 검색 트리보다 빠르다는 것을 쉽게 알 수 있습니다.

이 문서의 Trie 트리는 문자열을 예로 사용합니다. 실제로 키의 적합성에 대한 엄격한 요구 사항이 있습니다. 키가 부동 소수점 숫자인 경우 전체 Trie 트리가 매우 길어지고 노드가 늘어날 수 있습니다. 읽기가 매우 어렵습니다. 이 경우 Trie 트리를 사용하여 데이터를 저장하는 것은 적합하지 않습니다. 이 문제는 이진 검색 트리에는 존재하지 않습니다. 트리 트리와 해시 테이블

해시 충돌 문제를 고려해보세요. 우리는 일반적으로 해시 테이블의 복잡도를 O(1)이라고 말합니다. 사실 엄밀히 말하면 이는 완벽에 가까운 해시 테이블의 복잡도입니다. 또한, 해시 함수 자체가 필요로 하는 부분도 고려해야 합니다. 검색 문자열을 순회하는 경우 복잡도는 O(m)입니다. 서로 다른 키가 "동일 위치"에 매핑되면(폐쇄 해싱을 고려하면 이 "동일 위치"는 일반 연결 목록으로 대체될 수 있음) 검색의 복잡성은 "동일 위치" 숫자 아래의 노드 수에 따라 달라집니다. 따라서 최악의 경우 해시 테이블은 단방향 연결 목록이 될 수도 있습니다. Trie 트리는 키의 알파벳 순서에 따라 더 쉽게 정렬할 수 있습니다(전체 트리는 순서대로 한 번 탐색됩니다). 이는 대부분의 해시 테이블(해시 테이블에는 일반적으로 다른 키에 대한 기능이 없습니다) 순서와 다릅니다.

이상적인 상황에서 해시 테이블은 O(1) 속도로 빠르게 목표에 도달할 수 있습니다. 테이블이 매우 커서 디스크에 배치해야 하는 경우 해시 테이블의 검색 액세스는 아래에서 한 번만 수행하면 됩니다. 이상적인 상황입니다. 그러나 Trie 트리에서 액세스하는 디스크 수는 노드 깊이와 동일해야 합니다.

Trie 트리는 해시 테이블보다 더 많은 공간을 필요로 하는 경우가 많습니다. 하나의 노드가 하나의 문자를 저장하는 상황을 고려하면 문자열을 저장할 때 이를 별도의 블록으로 저장할 방법이 없습니다. Trie 트리의 노드 압축은 이 문제를 크게 완화할 수 있으며 이에 대해서는 나중에 설명하겠습니다.

트리 트리 개선

Bitwise Trie(Bitwise Trie)

일반 Trie 트리에 저장되는 가장 작은 단위가 문자라는 점만 빼면 원리는 일반 Trie 트리와 비슷하지만 Bitwise Trie는 비트만 저장합니다. 비트 데이터에 대한 액세스는 CPU 명령에 의해 한 번 직접 구현됩니다. 바이너리 데이터의 경우 이론적으로 일반 Trie 트리보다 빠릅니다.

노드 압축.

분기 압축: 안정적인 Trie 트리를 위해 기본적으로 검색 및 읽기 작업을 수행하며 일부 분기는 압축될 수 있습니다. 예를 들어 이전 그림에서 가장 오른쪽 가지의 inn은 일반 하위 트리로 존재하지 않고 노드 "inn"으로 직접 압축될 수 있습니다. Radix 트리는 Trie 트리가 너무 깊어지는 문제를 해결하기 위해 이 원리를 기반으로 합니다.

노드 매핑 테이블: 이 방법은 Trie 트리의 노드가 거의 완전히 결정되었을 때에도 사용됩니다. 요소가 숫자인 차원 다차원 배열 배열(예: Triple Array Trie)로 표현되며, 추가 매핑 테이블이 도입되더라도 Trie 트리 자체를 저장하는 공간 오버헤드는 더 작아집니다.

접두사 트리의 적용

접두사 트리는 여전히 이해하기 쉽고 적용 범위도 매우 넓습니다.

(1) 문자열의 빠른 검색

사전 트리의 쿼리 시간 복잡도는 O(logL)이고 L은 문자열의 길이입니다. 따라서 효율성은 여전히 ​​​​상대적으로 높습니다. 딕셔너리 트리는 해시 테이블보다 더 효율적입니다.

(2) 문자열 정렬

위 그림을 보면 단어가 정렬되어 있고, 알파벳 순서가 먼저 순회되는 것을 쉽게 알 수 있습니다. 불필요한 공통 부분 문자열을 줄입니다.

(3) 가장 긴 공통 접두사

inn과 int의 가장 긴 공통 접두사는 in입니다. 사전 트리를 문자 n으로 순회하면 이 단어의 공통 접두사는 이때 in입니다.

(4) 자동으로 접두사 일치 및 접미사 표시

사전이나 검색 엔진을 사용할 때 appl을 입력하면 접두사가 appl인 항목이 자동으로 표시됩니다. 그런 다음 사전 트리를 통해 얻을 수 있습니다. 앞서 언급한 것처럼 사전 트리는 나머지 접미사를 탐색하고 표시하기만 하면 됩니다.

위 내용은 제가 여러분을 위해 정리한 내용입니다. 앞으로 도움이 되길 바랍니다.

관련 기사:

Vue에서 간소화된 스타일을 구현하는 방법(자세한 튜토리얼)

Vue에서 사용자 정의 전역 구성 요소를 수행하는 방법은 무엇입니까?

vue2.0에서 다중 페이지 개발을 구현하는 방법

위 내용은 JavaScript의 트라이 접두사 트리에 대한 자세한 해석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!