Detaillierte Erläuterung der Verwendung des Javascript-Trie-Präfixbaums

Dieses Mal werde ich Ihnen eine detaillierte Erklärung der Verwendung von JavascriptTrie-Präfixbaum geben. Was sind die Vorsichtsmaßnahmen für die Verwendung von JavascriptTrie-Präfixbaum? Das Folgende ist ein praktischer Fall.

Einführung

Der Trie-Baum (aus dem Wort „Retrieval“), auch Präfixwort, Wortsuchbaum, Wörterbuchbaum genannt, ist ein Baum Shape Structure, eine Variante des Hash-Baums, ist eine Mehrbaumstruktur, die zum schnellen Abrufen verwendet wird.

Seine Vorteile sind: Minimierung unnötiger Zeichenfolgenvergleiche und die Abfrageeffizienz ist höher als die von Hash-Tabellen.

Die Kernidee von Trie ist der Austausch von Raum gegen Zeit. Verwenden Sie das gemeinsame Präfix von Zeichenfolgen, um den Zeitaufwand für Abfragen zu reduzieren und die Effizienz zu verbessern.

Der Trie-Baum hat auch seine Mängel. Unter der Annahme, dass wir nur Buchstaben und Zahlen verarbeiten, hat jeder Knoten mindestens 52 + 10 untergeordnete Knoten. Um Speicherplatz zu sparen, können wir verknüpfte Listen oder Arrays verwenden. In JS verwenden wir Arrays direkt, da JS-Arrays dynamisch sind und über eine integrierte Optimierung verfügen.

Grundlegende Eigenschaften

1. Der Wurzelknoten enthält keine Zeichen, außer für den Wurzelknoten Jeder untergeordnete Knoten von enthält ein Zeichen

2. vom Wurzelknoten zu einem bestimmten Knoten. Die auf dem Pfad übergebenen Zeichen sind verbunden, was die Zeichenfolge ist, die dem Knoten entspricht

3. Alle Unterknoten jedes Knotens enthalten unterschiedliche Zeichen

Programmimplementierung

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

Konzentrieren wir uns auf die Einfügemethode von TrieNode und Trie. Da der Wörterbuchbaum hauptsächlich für die Worthäufigkeitsstatistik verwendet wird, verfügt er über viele Knotenattribute, einschließlich numPass und numEnd, aber sehr wichtige Attribute. Die

Einfügemethode wird verwendet, um schwere Wörter einzufügen. Bevor wir beginnen, müssen wir feststellen, ob das Wort zulässig ist. Sonderzeichen und Leerzeichen dürfen nicht vorkommen. Beim Einfügen werden Zeichen aufgebrochen und in jedem Knoten platziert. numPass muss jedes Mal geändert werden, wenn ein Knoten passiert wird.

Optimierung

Jetzt gibt es in jeder unserer Methoden eine Operation von c=-48. Tatsächlich gibt es andere Zeichen zwischen Zahlen, Großbuchstaben und Kleinbuchstaben. Ja, dies führt zu unnötiger Platzverschwendung

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

Dann besteht die relevante Methode darin, c-= 48 in c = this.getIndex(c)

zu ändern Test

var trie = new Trie(); 
  trie.insert("I"); 
  trie.insert("Love"); 
  trie.insert("China"); 
  trie.insert("China"); 
  trie.insert("China"); 
  trie.insert("China"); 
  trie.insert("China"); 
  trie.insert("xiaoliang"); 
  trie.insert("xiaoliang"); 
  trie.insert("man"); 
  trie.insert("handsome"); 
  trie.insert("love"); 
  trie.insert("Chinaha"); 
  trie.insert("her"); 
  trie.insert("know"); 
  var map = {}
  trie.preTraversal(function(node, str){
    if(node.isEnd){
     map[str] = node.numEnd
    }
  })
  for(var i in map){
    console.log(i+" 出现了"+ map[i]+" 次")
  }
  console.log("包含Chin（包括本身）前缀的单词及出现次数："); 
  //console.log("China")
  var map = {}
  trie.preTraversal(function(node, str){
    if(str.indexOf("Chin") === 0 && node.isEnd){
      map[str] = node.numEnd
    }
   })
  for(var i in map){
    console.log(i+" 出现了"+ map[i]+" 次")
  }

Vergleich von Trie-Baum und anderen Datenstrukturen

Trie-Bäume und binäre Suchbäume

Binäre Suchbäume sollten die frühesten Baumstrukturen sein, mit denen wir in Kontakt kommen. Wir wissen, dass bei einer Datengröße von n die Zeit zum Einfügen, Suchen und Löschen ansteigt Operationen in einem binären Suchbaum Die Komplexität beträgt normalerweise nur O (log n). Im schlimmsten Fall haben alle Knoten im gesamten Baum nur einen untergeordneten Knoten, der zu einer linearen Liste degeneriert , Such- und Löschvorgänge sind O(n).

Normalerweise ist die Höhe n des Trie-Baums viel größer als die Länge m der Suchzeichenfolge, sodass die zeitliche Komplexität des Suchvorgangs normalerweise O (m) und im schlimmsten Fall die zeitliche Komplexität beträgt ist O(n). Es ist leicht zu erkennen, dass die Worst-Case-Suche in einem Trie-Baum schneller ist als ein binärer Suchbaum.

Der Trie-Baum in diesem Artikel verwendet Zeichenfolgen als Beispiele. Tatsächlich gelten strenge Anforderungen an die Eignung des Schlüssels. Wenn der Schlüssel eine Gleitkommazahl ist, kann dies dazu führen, dass der gesamte Trie-Baum extrem ist Die Lesbarkeit ist ebenfalls sehr schlecht. In diesem Fall ist die Verwendung des Trie-Baums zum Speichern von Daten nicht geeignet.

Trie-Baum und Hash-Tabelle

Bedenken Sie das Problem des Hash-Konflikts. Wir sagen normalerweise, dass die Komplexität einer Hash-Tabelle O(1) ist. Genau genommen ist dies die Komplexität einer Hash-Tabelle, die nahezu perfekt ist. Darüber hinaus müssen wir auch berücksichtigen, dass die Hash-Funktion selbst benötigt wird um die Suchzeichenfolge zu durchlaufen, und die Komplexität beträgt O(m). Wenn unterschiedliche Schlüssel der „gleichen Position“ zugeordnet werden (unter Berücksichtigung des geschlossenen Hashings kann diese „gleiche Position“ durch eine gewöhnliche verknüpfte Liste ersetzt werden), hängt die Komplexität der Suche von der Anzahl der Knoten unter der Nummer „gleiche Position“ ab. Daher kann die Hash-Tabelle im schlimmsten Fall auch zu einer einseitig verknüpften Liste werden.

Trie-Bäume können einfacher nach der alphabetischen Reihenfolge der Schlüssel sortiert werden (der gesamte Baum wird einmal der Reihe nach durchlaufen), was sich von den meisten Hash-Tabellen unterscheidet (Hash-Tabellen haben im Allgemeinen unterschiedliche Schlüssel für unterschiedliche Schlüssel). ist ungeordnet).

Unter idealen Umständen kann die Hash-Tabelle das Ziel schnell mit O(1)-Geschwindigkeit erreichen. Wenn diese Tabelle sehr groß ist und auf der Festplatte platziert werden muss, ist der Suchzugriff der Hash-Tabelle schneller Im Idealfall muss dies nur einmal erfolgen; die Anzahl der Festplattenzugriffe durch den Trie-Baum muss jedoch der Knotentiefe entsprechen.

Oft benötigt ein Trie-Baum mehr Platz als eine Hash-Tabelle. Wenn wir die Situation betrachten, in der ein Knoten ein Zeichen speichert, gibt es beim Speichern einer Zeichenfolge keine Möglichkeit, es als separaten Block zu speichern. Durch die Knotenkomprimierung des Trie-Baums kann dieses Problem erheblich gemildert werden, worauf später noch eingegangen wird.

Verbesserung des Trie-Baums

Bitwise Trie (Bitwise Trie)

Im Prinzip ist es so ähnelt einem gewöhnlichen Trie-Baum, außer dass die kleinste in einem gewöhnlichen Trie-Baum gespeicherte Einheit ein Zeichen ist, aber ein bitweiser Trie speichert nur Bits. Der Zugriff auf Bitdaten wird einmalig direkt durch den CPU-Befehl implementiert. Bei Binärdaten ist dies theoretisch schneller als beim gewöhnlichen Trie-Baum.

Knotenkomprimierung.

Zweigkomprimierung: Bei stabilen Trie-Bäumen handelt es sich im Wesentlichen um Such- und Lesevorgänge, und einige Zweige können komprimiert werden. Beispielsweise kann das Inn des Zweigs ganz rechts in der vorherigen Abbildung direkt in einen Knoten „inn“ komprimiert werden, ohne als regulärer Teilbaum zu existieren. Der Radix-Baum basiert auf diesem Prinzip, um das Problem zu lösen, dass der Trie-Baum zu tief ist.

Knotenzuordnungstabelle: Diese Methode wird auch verwendet, wenn die Knoten des Trie-Baums möglicherweise fast vollständig für jeden Zustand des Knotens im Trie-Baum bestimmt wurden, wenn die Gesamtzahl der Zustände viele Male wiederholt wird Durch ein Element, das als digitales mehrdimensionales Array dargestellt wird (z. B. Triple Array Trie), wird der Platzaufwand für die Speicherung des Trie-Baums selbst geringer, obwohl eine zusätzliche Zuordnungstabelle eingeführt wird.

Anwendung des Präfixbaums

Der Präfixbaum ist immer noch leicht zu verstehen und seine Anwendung ist auch sehr breit.

(1) Schnelles Abrufen von Zeichenfolgen

Die Abfragezeitkomplexität des Wörterbuchbaums beträgt O(logL), wobei L die Länge der Zeichenfolge ist. Der Wirkungsgrad ist also immer noch relativ hoch. Wörterbuchbäume sind effizienter als Hashtabellen.

(2) String-Sortierung

Aus der obigen Abbildung können wir leicht erkennen, dass die Wörter sortiert sind und zuerst die alphabetische Reihenfolge durchlaufen wird. Reduzieren Sie unnötige gemeinsame Teilzeichenfolgen.

(3) Das längste gemeinsame Präfix

Das längste gemeinsame Präfix von inn und int ist in. Beim Durchlaufen des Wörterbuchbaums zum Buchstaben n ist das gemeinsame Präfix dieser Wörter in.

(4) Präfixe automatisch abgleichen und Suffixe anzeigen

Wenn wir ein Wörterbuch oder eine Suchmaschine verwenden, geben Sie appl ein, und eine Menge Dinge mit dem Präfix appl werden automatisch angezeigt. Dann kann dies über einen Wörterbuchbaum erreicht werden. Wie bereits erwähnt, müssen wir nur die verbleibenden Suffixe durchqueren und anzeigen.

Das Obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, dass er für das Lernen aller hilfreich sein wird. Ich hoffe auch, dass jeder Script Home unterstützt.

Ich glaube, dass Sie die Methode beherrschen, nachdem Sie den Fall in diesem Artikel gelesen haben. Weitere spannende Informationen finden Sie in anderen verwandten Artikeln auf der chinesischen PHP-Website.

Empfohlene Lektüre:

Angular2-Kommunikationsmethode für Eltern-Kind-Komponenten

Eine Zusammenfassung der Methoden zur Optimierung des jQuery-Codes

So gehen Sie mit unvollständiger Seitenanzeige im 360-Browser-Kompatibilitätsmodus um

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Verwendung des Javascript-Trie-Präfixbaums. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!