Ich habe ein Programm geschrieben, das alle Instanzen einer gewünschten Wortklasse in einem Text anzeigt. So mache ich es:
Erstellt ein Array von Wörtern aus dem gesamten Text
Iterate dieses Array. Suche für jedes Wort, was sein erster Buchstabe ist.
Nachdem alle Wörter markiert sind, wiederhole das Array der Übereinstimmungen und markiere jedes einzelne im Text.
Ein Text, der aus 240000 Wörtern besteht, wird in 100 Sekunden in Bezug auf Substantive und ungefähr 4,5 Sekunden in Bezug auf Präpositionen auf meiner Maschine verarbeitet.
Ich suche nach einer Möglichkeit, die Leistung zu verbessern, und das sind die Ideen, die ich mir vorstellen konnte:
Sind das solide Ideen und gibt es noch weitere Ideen oder bewährte Techniken, um diese Art der Verarbeitung zu verbessern?
Nutzen Sie die Kraft von Javascript.
Es manipuliert Wörterbücher mit String-Schlüsseln als grundlegende Operation. Erstellen Sie für jede Wortklasse ein Objekt, wobei jedes mögliche Wort ein Schlüssel und ein einfacher Wert wie true oder 1 ist. Dann wird jedes Wort einfach überprüft typeof(wordClass[word]) !== "undefined" . Ich erwarte, dass das viel schneller geht.
Reguläre Ausdrücke sind ein weiterer stark optimierter Bereich von Javascript. Sie können das Ganze wahrscheinlich als einen massiven regulären Ausdruck für jede Wortklasse verwenden. Wenn Ihre Hervorhebung in HTML ist, können Sie auch einfach eine Ersetzung im RE verwenden, um das Ergebnis zu erhalten. Diese Arbeit hängt wahrscheinlich davon ab, wie groß Ihre Wortsätze sind.
Die von mir vorgeschlagene Lösung ist die Implementierung einer trie Datenstruktur. Es erfordert mehr Aufwand zu implementieren, hat aber mehrere Vorteile gegenüber einer Hash-Tabelle (Wörterbuch).
Nachschlagen von Daten in einem Trie dauert höchstens 0 ( k ) Zeit, wobei k die Länge der Suchzeichenfolge ist. Mit einer Hash-Tabelle könnte das Speichern jedes Wortes als Schlüssel funktionieren, aber was speichern Sie als Wert für diesen Schlüssel in der Tabelle? Hashtabellen scheinen mir für dieses Problem nicht sehr effizient zu sein.
Darüber hinaus kann ein Trie alphabetisch Ihre Schlüsseleinträge nativ über Vorbestellungs-Traversal bereitstellen. Eine Hash-Tabelle kann nicht. Um seine Schlüssel zu sortieren, müssten Sie selbst eine Sortierfunktion implementieren, die nur mehr Zeit und Platz hinzufügt.
Wenn Sie weiter in Versuche lesen, werden Sie Suffixbäume und Radix-Bäume , die genau auf das Problem ansprechen, das Sie lösen möchten. In gewisser Weise erfindest du das Rad neu, aber ich behaupte nicht, dass das eine schlechte Sache ist. Das Lernen dieses Materials macht dich zu einem besseren Programmierer.
Wir können einen einfachen Trie als eine Menge verbundener Knoten implementieren, die drei Informationen speichern: 1) ein Symbol (Zeichen), 2) einen Zeiger auf das erste Kind dieses Knotens und 3) einen Zeiger auf den Elternknoten das nächste Kind des Knotens.
%Vor%Sie können dann ein Netz von Wörtern aufbauen, die durch jeden Buchstaben im Wort miteinander verbunden sind. Wörter, die das gleiche Präfix haben, werden nativ über den Kind- und den nächsten Zeiger miteinander verknüpft, so dass die Suche ziemlich schnell ist. Ich ermutige Sie, weiter in Versuche zu schauen. Sie sind ordentlich Datenstrukturen und ich denke, dass es am besten zu Ihrem Problem passt.
Ich denke, die Schritte, die eine hohe Rechenzeit kosten, wären:
Somit würde ich eine effizientere Datenstruktur vorschlagen, um Ihren Wortklassencontainer und die Übereinstimmungen Liste zu speichern. So läuft die Suche und Suche schneller.
Wenn ich Ihr Problem richtig verstanden habe, möchten Sie nur die Wörter hervorheben, die in der Weltklassenliste enthalten sind . Also würde ich Bloom Filter vorschlagen, der diesen Job sehr hervorragend macht.
Bloom Filter ist ein Set-Container, in dem Sie beliebige Elemente (Wörter) ablegen und prüfen können, ob bereits ein neues Wort in diesem Set enthalten ist. Die Geschwindigkeit ist rasend schnell und eignet sich gut für die Verarbeitung großer Datenmengen.
Die Anwendungsfälle wären:
2,40,000 Wörter sind in der Tat eine große Datenmenge, die auf der Client-Seite verarbeitet werden muss, dies wird Performance-Probleme in Javascript sowie DOM-Manipulation verursachen, wenn Sie den Text markieren. Sie sollten versuchen, einen kleineren Satz zu verarbeiten, wie Seiten, Absätze oder Abschnitte.
Wenn Sie Ihre aktiven Wörter reduzieren können oder nicht, hier sind einige Optimierungen, die Sie für Ihre Textverarbeitung ausprobieren können:
Speichern des Textes in DOM
Sie können hier zwei Ansätze ausprobieren:
Sie müssen Tools wie jsPerf verwenden, um zu sehen, wie schnell innerHTML-Änderungen in beiden Ansätzen sind, dh ein großes ersetzen innerHTML oder Text in einem einzelnen DOM-Element gegenüber dem Ersetzen mehrerer innerHTMLs übereinstimmender DOM-Elemente.
Übereinstimmende Wörter werden hervorgehoben, wenn sie vollständig eingegeben wurden
Sie möchten beispielsweise "Javascript" und "Text" in Ihrem Text markieren, nachdem sie vollständig eingegeben wurden. In diesem Fall, wie @DrC erwähnt, wäre die Vorverarbeitung Ihres Textes zum Speichern von Schlüssel vs Daten eine gute Sache. Generieren Sie einen Schlüssel für das Wort (Sie können den Schlüssel normalisieren, falls Sie die Groß- / Kleinschreibung nicht berücksichtigen oder Sonderzeichen usw. ignorieren möchten, dh 'nosql' ist der Schlüssel für 'NoSQL' oder 'NOSQL' oder 'No-SQL ". Ihr Nachschlageobjekt wird dann wie folgt aussehen:
%Vor%Wenn ein Wort durchsucht wird, generieren Sie den Schlüssel zum Suchen von Indizes aller Übereinstimmungen und markieren den Text.
Übereinstimmende Wörter werden hervorgehoben, während sie eingegeben werden
Für diesen Ansatz benötigen Sie eine trie basierte Struktur, die im JavaScript-Objekt erstellt wurde.
Ein anderer Ansatz wäre das Erzeugen und Kompilieren von Regex basierend auf
aktuelle typisierte Zeichenfolge, z. B. wenn der Benutzer 'jav' eingegeben hat, wäre die Regex
\jav\gi und führt eine Regex-Übereinstimmung für den gesamten Text aus.
Beide Ansätze würden einen Leistungsvergleich benötigen
Tags und Links javascript performance process text