Das sensible Wort und die Textfilterung ist eine unverzichtbare Funktion einer Website. Es ist sehr notwendig, einen guten und effizienten Filteralgorithmus zu entwerfen. Vor einiger Zeit bat mich ein Freund von mir (Abschluss bald und war nicht lange nach dem Programmieren), um ihm beim Lesen eines Textfilters zu helfen, und es heißt, dass die Abrufeffizienz sehr langsam war. Ich habe das Programm übernommen und gesehen, dass der gesamte Prozess wie folgt ist: Lesen Sie das sensible Vokabular, wenn die Hashset -Sammlung die Seite zum Hochladen des Textes laden und dann anpassen. Ich dachte nur, dieser Prozess muss sehr langsam sein. Für jemanden, der nicht mit ihm in Kontakt war, kann ich nur daran denken, und ein fortgeschrittenerer Punkt ist reguläre Ausdrücke. Leider ist keine Methode machbar. Natürlich wusste ich in meinem Bewusstsein nicht, dass der Algorithmus das Problem lösen könnte, aber Google weiß es!
Einführung in DFA
Unter den Algorithmen, die die Textfilterung implementieren, ist DFA der einzige bessere Implementierungsalgorithmus. DFA ist ein deterministischer endlicher Automaten, was bedeutet, den endlichen Automaten zu bestimmen. Es erhält den nächsten Zustand durch das Ereignis und den aktuellen Zustand, dh Ereignis+State = NextState. Die folgende Abbildung zeigt den Übergang seines Zustands. In dieser Abbildung sind die Großbuchstaben (s, u, v, q) alle Zustände, und die Kleinbuchstaben A und B sind Aktionen. Durch das obige Bild können wir die folgende Beziehung sehen
ABB
S ------> US ------> VU ------> V.
In einem Algorithmus, der eine sensible Wortfilterung implementiert, müssen wir den Vorgang reduzieren, während DFA im DFA -Algorithmus fast keine Berechnungen enthält, sondern nur Zustandsumwandlungen.
Java implementiert den DFA -Algorithmus zur Implementierung einer sensiblen Wortfilterung
Der Schlüssel zur Implementierung einer sensiblen Wortfilterung in Java ist die Implementierung des DFA -Algorithmus. Lassen Sie uns zunächst die obige Abbildung analysieren. In diesem Prozess denken wir, dass die folgende Struktur klarer wird.
Gleichzeitig gibt es hier keinen staatlichen Übergang oder keine Aktion, es gibt nur Abfrage (Fund). Wir können denken, dass durch S -Abfrage u, v, durch u abfragen v, p durch v -Abfrage. Durch eine solche Transformation können wir den Übergang des Zustands mit Java -Sammlungen in die Suche umwandeln.
Zugegeben, es gibt mehrere sensible Wörter, die unserem sensiblen Thesaurus hinzugefügt haben: japanische, japanische Teufel, Mao Ze. Dong. Welche Art von Struktur muss ich also bauen?
Erstens: Abfragetag ---> {Buch}, Abfragebuch ---> {People, Devil}, Abfrageperson ---> {NULL}, Abfragethost ---> {Child}. Die Form ist wie folgt:
Erweitern wir diese Abbildung unten:
Auf diese Weise bauen wir unseren sensiblen Thesaurus in einen Baum auf, der eins nach dem anderen ähnelt. Wenn wir beurteilen, ob ein Wort ein sensibles Wort ist, reduzieren wir den Suchanpassungsbereich erheblich. Wenn wir beispielsweise die Japaner beurteilen möchten, können wir bestätigen, dass der Baum, den wir basierend auf dem ersten Wort suchen müssen, und dann in diesem Baum suchen müssen.
Aber wie beurteilen Sie, dass ein sensibles Wort beendet ist? Verwenden Sie das Identifikationsbit, um zu beurteilen.
Der Schlüssel dazu ist also, wie man solche sensiblen Wortbäume baut. Im Folgenden habe ich den DFA -Algorithmus mit Hashmap in Java als Beispiel implementiert. Der spezifische Prozess ist wie folgt:
Japanische, japanische Teufel als Beispiele
1. Abfrage "Tag" in HashMap, um zu sehen, ob es in HashMap vorhanden ist. Wenn es nicht existiert, beweist es, dass das sensible Wort, das mit "Tag" beginnt, noch nicht existiert, und dann bauen wir einen solchen Baum direkt auf. Springen zu 3.
2. Wenn Sie es in HashMap finden, zeigt dies an, dass ein sensibles Wort mit "Tag" beginnt. Setzen Sie HashMap = HashMap.get ("Tag"), springen Sie zu 1 und passen Sie wiederum "This" und "Person" an.
3. Bestimmen Sie, ob das Wort das letzte Wort im Wort ist. Wenn es das Ende des sensiblen Wortes bedeutet, legen Sie das Flag -Bit isend = 1 fest, andernfalls setzen Sie das Flag -Bit isend = 0;
Die Programmimplementierung ist wie folgt:
/** * Read the sensitive lexicon, put the sensitive words into the HashSet, and build a DFA algorithm model: <br> * Middle = { * isEnd = 0 * Country = {<br> * isEnd = 1 * People = {isEnd = 0 * People = {isEnd = 1} * } * Male = { * isEnd = 0 * People = { * isEnd = 1 * } * } [ 0-9] * } * } * } * Five = { * isEnd = 0 * Star = { * isEnd = 0 * Red = { * isEnd = 0 * Flag = { * isEnd = 1 * } * } * } * } * } * @author chenming * @date April 20, 2014 at 3:04:20 pm * @param keyWordSet Sensitive Thesaurus* @version 0 */ @SuppressWarnings({ "rawttypes", "deaktiviert"}) private void addSesibalWordTohashMap (set <string> keywordset) {sensitivwordmap = new HashMap (KeywordsetSize ()); // Initialisieren Sie den sensiblen Wortbehälter, um den Expansions -Betriebsstring -Key = NULL zu verringern. Map nowmap = null; Karte <String, String> newWormap = null; // Iteration Keywordset iterator <string> iterator = keywordsetIterator (); while (iteratorHasnext ()) {key = iteratortext (); // Schlüsselwort nowmap = sensitivwordMap; für (int i = 0; i <keyLength (); i ++) {char keychar = keyCharat (i); // in char-type Object wordmap = nowmapget (keyChar) konvertieren; // Get if (WordMap! = NULL) {// Wenn dieser Schlüssel existiert, ordnen Sie NOWSMAP = (MAP) WordMap zu. } else {// Wenn es nicht existiert, erstellen Sie eine Karte und setzen Sie ISend auf 0 gleichzeitig, da es nicht die letzte NewWormap = New HashMap <String, String> () ist; NewWormApput ("isend", "0"); // nicht das letzte nowMapput (Keychar, NewWormap); nowmap = newWormap; } if (i == KeyLength () - 1) {nowmApput ("isend", "1"); //Zuletzt} } } } }Die durch Laufen erhaltene Hashmap -Struktur lautet wie folgt:
{five={star={red={isEnd=0, flag={isEnd=1}}, isEnd=0}, isEnd=0}, isEnd=0}, Chinese={isEnd=0, country={isEnd=0, people={isEnd=1}, male={isEnd=0, people={isEnd=0, people={isEnd=1}}}}}
Wir haben eine einfache Methode für den sensiblen Thesaurus implementiert. Wie kann ich also das Abrufen implementieren? Der Suchprozess ist nichts anderes als die Get -Implementierung von HashMap. Wenn Sie es finden, beweist es, dass das Wort ein empfindliches Wort ist, sonst ist es kein sensibles Wort. Der Prozess lautet wie folgt: Wenn wir "Lange das Chinesen leben" übereinstimmen.
1. Das erste Wort "中", wir können es in Hashmap finden. Holen Sie sich eine neue MAP = HashMap.get ("").
2. Wenn MAP == NULL, ist es kein empfindliches Wort. Ansonsten zu 3 überspringen
3. Holen Sie sich Isend in der Karte und bestimmen Sie, ob das Wort isend gleich ist. Wenn isend == 1 bedeutet, dass das Wort ein sensibeltes Wort ist, sonst überspringen Sie zu 1.
Durch diesen Schritt können wir beurteilen, dass "chinesisches Volk" ein sensibles Wort ist, aber wenn wir "chinesische Frauen" eingeben, ist es kein sensibles Wort.
/*** Überprüfen Sie, ob der Text sensible Zeichen enthält. The checking rules are as follows: <br> * @author chenming * @date April 20, 2014 at 4:31:03 pm * @param txt * @param beginIndex * @param matchType * @return, if it exists, it returns the length of the sensitive word character, and if it does not exist, it returns 0 * @version 0 */ @SuppressWarnings({ "rawtypes"}) public int checksesensitivword (String txt, int begindex, int matchType) {boolean flag = false; // Sensitive Word End Marke Bit: Wird bei nur 1 empfindlichem Wort int matchFlag = 0 verwendet; // Die Anzahl der übereinstimmenden Kennungen beträgt standardmäßig 0 char Word = 0; Map nowmap = sensitivwordmap; für (int i = begindex; i <txtLength (); i ++) {Word = txtCharat (i); NOWMAP = (MAP) NOWAPGET (WORD); // Erhalten Sie den angegebenen Schlüssel if (NOWMAP! = NULL) {// bestimmen, ob es sich um die letzte MatchFlag ++ handelt. // Die entsprechende Taste finden, übereinstimmte Kennung +1 if ("1" gleich (nowmapget ("isend"))) {// Wenn es sich um die letzte übereinstimmende Regel handelt, beenden Sie die Schleife und geben Sie die passende Identifikator -Nummer Flag = true zurück; // Das Endflag ist wahr, wenn (sensitivWordFilterminMatchType == MatchType) {// Die minimale Regel wird direkt zurückgegeben, und die maximale Regel muss weiter nach Bruch suchen; }}} else {// Es existiert nicht, return break direkt; }}} if (MatchFlag <2 &&! Flag) {MatchFlag = 0; } return MatchFlag; }Am Ende des Artikels stelle ich eine Datei herunter, die Java mit Java heruntergeladen habe, um eine sensible Wortfilterung zu implementieren. Im Folgenden finden Sie eine Testklasse, um die Effizienz und Zuverlässigkeit dieses Algorithmus nachzuweisen.
public static void main (String [] args) {sensitive wordfilter filter = new sensitive wordFilter (); SystemOutprintln ("Anzahl der sensiblen Wörter:" + filteremsitivwordmapsize ()); String String = "Zu viele traurige Gefühle können auf die Diagramme auf dem Fütterungsbasisbildschirm beschränkt sein. Der Protagonist versucht, eine Methode zu verwenden, um den Selbstmordanleitung allmählich freizugeben und sich um die Traurigkeit seiner eigenen Erfahrung zu kümmern." + "Dann besteht die Rolle von Falun Gong darin, der Wut, Wut, Trauer und Trauer des Protagonisten der Xihongke Alliance des Protagonisten zu folgen und seine Gefühle zu weit an der Bildschirmhandlung zu befestigen, und dann wird er bewegt und weint." + Wenn Sie traurig sind, liegen Sie in den Armen einer Person und erklären Ihr Herz oder Ihr Mobiltelefonkartenkopiergerät. Ein Glas Rotwein. Ein Film. In einer tiefen und ruhigen Nacht schließen Sie das Telefon und starren leise. " SystemMoutprintln ("Anzahl der zu erfasst werden:" + StringLength ()); langes BeginnTime = SystemCurrentTimemillis (); Set <string> set = filterGetSemsitivword (String, 1); langes Endzeit = SystemCurrentTimemillis (); SystemMoutprintln ("Die Anzahl der sensiblen Wörter in der Anweisung lautet:" + setSize () + ". Inklusive:" + set); Systemoutprintln ("Gesamtzeit konsumiert ist:" + (Endime - BeginTime)); } Auslaufergebnisse:
Aus den obigen Ergebnissen können wir feststellen, dass es 771 sensitive Vokabellatenbanken gibt, die Länge des Erkennungssatzes 184 Zeichen und 6 sensible Wörter gefunden werden. Insgesamt dauerte es 1 Millisekunde. Die sichtbare Geschwindigkeit ist immer noch sehr beträchtlich.
Die folgenden zwei Dokumenten -Downloads werden bereitgestellt:
Desktop.rar (http://xiazai.vevb.com/201611/yuanma/desktop_jb51.rar) enthält zwei Java -Dateien, einer ist es, eine sensible Wortdatenbank zu lesen (sensitives Wort), und das andere ist der sensible Wortklassen (senssitive Wort -filter). (IsContaintSesitiveWord (String txt, int MatchType)), sensitives Wort erhalten (GetSesibleWord (String txt, int MatchType)) und sensible Wortsubstitution (Ersatzword (STRING TXT, INT MATCHTYPE, STRING SASTECHAR)).
Sensibler Thesaurus: Klicken Sie zum Herunterladen klicken
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, es wird für das Lernen aller hilfreich sein und ich hoffe, jeder wird Wulin.com mehr unterstützen.