In Szenarien wie Foren und Chatrooms müssen wir häufig viele schlechte Worte blockieren. Bei der Suche nach einzelnen Keywords ist es natürlich effizienter in den Index- und regulären Methoden. Wenn es jedoch viele Schlüsselwörter gibt, wenn Sie wiederholt Indexof oder reguläre Wörter aufrufen, um den vollständigen Text zu entsprechen, ist der Leistungsverbrauch sehr hoch. Da die Zielzeichenfolge normalerweise groß ist, muss sichergestellt werden, dass das Ergebnis in einer Durchführung erzielt wird. Basierend auf solchen Bedürfnissen ist es leicht, sich nachdenken, um jeden Charakter im gesamten Text nacheinander abzustimmen. Zum Beispiel für diesen Text: "Mike Jordan hatte" einfach mach es "gesagt, also war Mark ein Coder." Wenn unser Schlüsselwort "Mike" und "Mark" ist, können Sie den gesamten Satz durchqueren. Wenn Sie "M" finden, sehen Sie, ob Sie mit "I" oder "A" übereinstimmen können. Wenn Sie bis zum Ende übereinstimmen können, finden Sie erfolgreich ein Keyword, andernfalls werden Sie weiterhin durchqueren. Dann sollte die Struktur der Schlüsselwörter wie folgt sein:
var keywords = {m: {i: {k: {e: {end: true}}}}, a: {r: {k: {end: true}}}}}Aus dem obigen Punkt können wir feststellen, dass diese Daten eine Baumstruktur sind und noch zeitaufwändig ist, eine Baumstruktur zu erstellen, die auf der Schlüsselwortgruppe basiert, während die Schlüsselwörter bereits angegeben sind, sodass Sie vor dem Anpassen eine solche Datenstruktur im Voraus erstellen können. Der Code ist wie folgt:
Funktion Buildtree (Schlüsselwörter) {var tBlcur = {}, key, str_key, Länge, j, i; var tblroot = tblcur; für (j = keywords.length - 1; j> = 0; j - = 1) {str_key = keywords [j]; Länge = str_key.length; für (i = 0; i <Länge; i += 1) {key = str_key.charat (i); if (tblcur.hasownProperty (Schlüssel)) {tblcur = tBlcur [Schlüssel]; } else {tblcur = tBlcur [key] = {}; }} tblcur.end = true; // das letzte Schlüsselwort tblcur = tblroot; } return tblroot;}Dieser Code verwendet eine kontinuierliche Anweisung: tBlcur = tBlcur [Schlüssel] = {}. Die Ausführungsreihenfolge hier ist die Ausführungsreihenfolge der Aussagen. Da der Betriebsniveau von [] höher als = ist, ist das erste, was im TBLCUR -Objekt ein Schlüsselattribut erstellt. In Kombination mit Tblroot = Tblcur = {} ist die Ausführungsreihenfolge:
var tblroot = tBlcur = {}; tblroot = tBlcur; tBlcur ['key'] = undefiniert; // jetzt tblroot = {key: undefined} tBlcur ['key'] = {}; tBlcur = tBlcur ['key'];Über den obigen Code werden die erforderlichen Abfragedaten erstellt. Schauen wir uns die Schreibmethode der Abfrageschnittstelle an.
Für jedes Wort der Zielzeichenfolge beginnen wir ganz oben in diesen Schlüsselwörtern. Erstens Schlüsselwörter [a]. Wenn ja, schauen Sie sich das Schlüsselwort [a] [b] an. Wenn das letzte Schlüsselwort [a] [b]… [x] = true bedeutet, dass die Übereinstimmung erfolgreich ist. Wenn das Schlüsselwort [a] [b]… [x] = undefiniert ist, wird die Übereinstimmung von der nächsten Position neu gestartet.
Funktionssuche (Inhalt) {var tBlcur, p_star = 0, n = content.length, p_end, match, //, ob ein match_key, match_str, arrmatch = [], // Speichern Sie das Ergebnis arrLength = 0; // Der Längenindex von Arrmatch while (p_star <n) {tblcur = tblroot; // Rückverfolgung zum root p_end = p_star; match_str = ""; Match = false; do {match_key = content.charat (p_end); if (! (tblcur = tBlcur [match_key])) {// Das Ende dieses Match P_star += 1; brechen; } else {match_str += match_key; } p_end += 1; if (tBlcur.end) //, ob mit dem Schwanz übereinstimmt {match = true; }} while (true); if (match) {// maximale Übereinstimmung arrmatch [arrlenength] = {key: match_str, begin: p_star - 1, ende: p_end}; Arrlength += 1; p_star = p_end; }} return arrmatch;}Das obige ist der Kern des gesamten Keyword -Matching -Systems. Hier verwenden wir die Sprachmerkmale von JS sehr gut und die Effizienz ist sehr hoch. Ich habe ein 500.000-Wort "Soushen Ji" verwendet, um es zu testen, und fand die angegebenen 300 Redewendungen. Der passende Effekt beträgt etwa 1 Sekunde. Da der Zieltext gleichzeitig durchquert wird, hat die Länge des Zieltextes nur geringe Auswirkungen auf die Abfragezeit. Die Anzahl der Schlüsselwörter, die einen größeren Einfluss auf die Abfragezeit haben, ist die Anzahl der Schlüsselwörter. Jedes Wort im Zieltext durchquert die Schlüsselwörter, sodass es einen gewissen Einfluss auf die Abfrage hat.
Einfache Analyse
Ich denke, Sie fragen sich, wenn Sie den obigen Artikel lesen. Sie können alle Schlüsselwörter für jedes Wort durchqueren. Auch wenn einige Schlüsselwörter teilweise gleich sind, ist es ziemlich zeitaufwändig, sie vollständig zu durchqueren. Die Eigenschaften von Objekten in JS werden jedoch unter Verwendung einer Hash -Tabelle konstruiert. Die Daten dieser Struktur unterscheiden sich stark von der einfachen Array-Traversal, und die Effizienz ist viel höher als die der ordnungsbasierten Array-Durchfahrten. Einige Schüler sind möglicherweise nicht mit Datenstrukturen vertraut, daher werde ich kurz über den relevanten Inhalt der Hash -Tabelle sprechen.
Schauen wir uns zunächst die Speicherung von Daten an.
Die Speicherung von Daten im Speicher besteht aus zwei Teilen, einer ist der Wert und der andere die Adresse. Stellen Sie sich das Gedächtnis als ein Xinhua -Wörterbuch vor, die Erklärung des Wortes ist der Wert und das Verzeichnis ist die Adresse. Das Wörterbuch wird von Pinyin sortiert, zum Beispiel "Ni" mit derselben Aussprache ist im selben Stück angeordnet, dh das Array ist ordentlich in einem Speicherbereich angeordnet. Diese Struktur ist ein Array. Sie können "Ni" Nummer 1 und 10 angeben, um darauf zuzugreifen. Das Strukturdiagramm lautet wie folgt:
Der Vorteil von Arrays besteht darin, dass sie einfach zu durchlaufen sind und über Einweisungen direkt auf die entsprechenden Daten zugreifen können. Es ist jedoch sehr schwierig, ein bestimmtes Element hinzuzufügen oder zu löschen. Wenn Sie beispielsweise Element 6 löschen möchten, müssen die Daten nach Punkt 5 von einer Position vorangetrieben werden. Wenn Sie das erste Bit löschen möchten, muss das gesamte Array bewegt werden, was viel verbraucht.
Um das Problem der Array -Addition und -Löhe zu lösen, werden verknüpfte Listen angezeigt. Wenn wir den Wert in zwei Teile unterteilen, wird ein Teil verwendet, um den ursprünglichen Wert zu speichern, und der andere Teil wird verwendet, um eine Adresse zu speichern, die auf eine andere gleiche Struktur usw. zeigt, eine verknüpfte Liste zu bilden. Die Struktur ist wie folgt:
Aus der obigen Abbildung ist deutlich zu erkennen, dass das Hinzufügen und Löschen der verknüpften Liste sehr einfach ist. Schreiben Sie einfach das Zielelement und das nächste Element des vorherigen Elements neu und es wird abgeschlossen. Es ist jedoch sehr schwierig, den Wert eines Artikels abzufragen. Sie müssen es wiederum durchqueren, um auf den Zielort zuzugreifen.
Um die Vorteile dieser beiden Strukturen zu integrieren, müssen Sie an die folgende Struktur nachdenken.
Diese Datenstruktur ist eine Hash -Tabellenstruktur. Die Header-Adresse der verknüpften Liste wird im Array gespeichert, und es kann eine zweidimensionale Datentabelle gebildet werden. Was die Verteilung von Daten betrifft, ist dies ein Hashing -Algorithmus, und eine regelmäßige Übersetzung sollte ein Hashing -Algorithmus sein. Obwohl es viele Arten von Algorithmen gibt, lösen sie im Prinzip den Schlüssel durch eine Funktion und platzieren dann die Daten gemäß den Ergebnissen der Lösung. Mit anderen Worten, zwischen dem Schlüssel und der tatsächlichen Adresse wird eine Zuordnung gebildet, sodass wir zu diesem Zeitpunkt nicht mehr auf das Array zugreifen, indem wir das Array abonnieren oder einfach nur durchqueren, sondern die Daten nach der inversen Funktion der Hash -Funktion lokalisieren. Das Objekt in JS ist eine Hash -Struktur. Zum Beispiel definieren wir einen OBJ. Obj.name durch Hashing, und seine Position im Gedächtnis kann in der obigen Abbildung 90 sein. Wenn wir Obj.name bedienen möchten, hilft uns die zugrunde liegende Ebene automatisch bei der Position von 90 über den Hash -Algorithmus, was bedeutet, dass wir die verknüpfte Liste direkt aus den 12 Elementen des Arrays nachschlagen, anstatt den gesamten Speicherblock von 0 zu durchqueren.
Definieren Sie ein Objekt obj {Schlüssel: Wert} in js. Der Schlüssel wird in eine Zeichenfolge konvertiert und dann gehasht, um eine Speicheradresse zu erhalten, und dann den Wert in ihn einfügen. Auf diese Weise können wir verstehen, warum wir Attribute nach Belieben hinzufügen und löschen können und warum wir Arrays in JS auch Attribute zuweisen können, und es gibt kein sogenanntes grenzüberschreitendes Array.
In Situationen, in denen das Datenvolumen groß ist, hat die Hash -Tabelle einen sehr offensichtlichen Vorteil, da sie durch den Hash -Algorithmus viele unnötige Berechnungen reduziert. Die sogenannte Leistungsoptimierung besteht darin, Computer weniger Computer zu machen. Die größte Optimierung besteht darin, nicht zu berechnen!
Optimierung von Algorithmen
Nachdem Sie die zugrunde liegende Implementierung des Algorithmus verstehen, können Sie den Algorithmus im Nachhinein optimieren. Vor der Optimierung sollten Sie jedoch eine Sache betonen: Verfolgen Sie nicht blind die Leistung! In diesem Fall können wir beispielsweise höchstens bis zu 5.000 Wörtern übereinstimmen, sodass der vorhandene Algorithmus ausreicht und alle Optimierungen nicht erforderlich sind. Der Grund, warum ich immer noch über Optimierung spreche, ist, mein Verständnis des Algorithmus und des Programms zu verbessern, anstatt die 1MS -Optimierung wirklich durchzuführen.
Wir haben festgestellt, dass keiner unserer Schlüsselwörter ein einzelnes Wort hat, daher wäre es für uns eine Verschwendung, Schlüsselwörter entsprechend der Einheit eines Wortes zu durchqueren. Die Optimierung hier besteht darin, die maximale und minimale Länge des Keywords vorzustatistisch und in Einheiten der minimalen Länge jedes Mal zu suchen. Zum Beispiel ist das Schlüsselwort in meinem Testfall eine Idiom, und das kürzeste ist 4 Zeichen. Jedes Mal, wenn ich übereinstimme, stimme ich mit 4 Zeichen zusammen. Wenn ich drücke, suchen Sie weiterhin Tiefe, um die maximale Länge zu finden. Mit anderen Worten, wenn wir den Baum zum ersten Mal konstruieren, wird er zuerst mit der Mindestlänge gebaut und dann wörtlich hinzugefügt.
Eine einfache Berechnung wird durchgeführt. Laut unserem Testfall müssen wir für 300 Redewendungen nur einmal ein Wort vergleichen, und für eine Ein-Wort-Abfrage müssen wir viermal vergleichen, und bei jedem Vergleich müssen wir auf unsere Baumstruktur zugreifen, was der vermeidbare Leistungsverbrauch ist. Noch wichtiger ist, dass der Vergleich hier kein String -Vergleich ist. Unsere Schlüsselwörter hier existieren alle als Schlüssel, und der Effekt ist der gleiche wie der Schlüssel in OBJ, was den Schlüssel gehasht und dann auf die entsprechende Adresse zugreift! Machen Sie sich also keine Sorgen über den Unterschied zwischen dem Vergleichen eines Wortes und dem Vergleichen von vier Wörtern. Wir haben keine Saiten verglichen!
Hier geht es darum, mehrere Keywords abzustimmen. Ich werde die optimierte Version des Codes nicht veröffentlichen, da er im Allgemeinen nicht verfügbar ist.