Le filtrage sensible des mots et du texte est une fonction indispensable d'un site Web. Il est très nécessaire de concevoir un algorithme de filtrage bon et efficace. Il y a quelque temps, un de mes amis (diplômé bientôt et n'a pas été longtemps après s'être impliqué dans la programmation) m'a demandé de l'aider à lire un filtrage de texte, et il a dit que l'efficacité de récupération était très lente. J'ai repris le programme et j'ai vu que l'ensemble du processus est le suivant: Lisez le vocabulaire sensible, si la collection HashSet, obtenez la page pour télécharger le texte, puis assortir. Je pensais juste que ce processus devait être très lent. Pour quelqu'un qui n'a pas été en contact avec lui, je ne peux que penser à cela, et un point plus avancé est des expressions régulières. Mais malheureusement, aucune méthode n'est possible. Bien sûr, dans ma conscience, je ne savais pas que l'algorithme pouvait résoudre le problème, mais Google le sait!
Introduction au DFA
Parmi les algorithmes qui implémentent le filtrage de texte, le DFA est le seul meilleur algorithme d'implémentation. Le DFA est une automate finie déterministe, ce qui signifie déterminer l'automate fini. Il obtient l'état suivant via l'événement et l'état actuel, c'est-à-dire l'événement + état = NextState. La figure suivante montre la transition de son état. Sur cette figure, les lettres majuscules (S, U, V, Q) sont tous des états, et les lettres minuscules A et B sont des actions. Grâce à l'image ci-dessus, nous pouvons voir la relation suivante
abb
S ------> US ------> VU ------> V
Dans un algorithme qui met en œuvre le filtrage des mots sensible, nous devons réduire les opérations, tandis que le DFA n'a presque aucun calcul dans l'algorithme DFA, uniquement les conversions d'état.
Java implémente l'algorithme DFA pour implémenter un filtrage de mots sensible
La clé de la mise en œuvre du filtrage des mots sensibles dans Java est la mise en œuvre de l'algorithme DFA. Tout d'abord, analysons la figure ci-dessus. Dans ce processus, nous pensons que la structure suivante sera plus claire.
En même temps, il n'y a pas de transition ou d'action d'état ici, il n'y a que des requêtes (trouver). Nous pouvons penser que via la requête S, v, via u query v, p, via V requête. Grâce à une telle transformation, nous pouvons transformer la transition de l'état en recherche à l'aide de collections Java.
Certes, il y a plusieurs mots sensibles ajoutés à notre thésaurus sensible: japonais, diables japonais, Mao Ze. Dong. Alors, de quel type de structure dois-je construire?
Premièrement: Journée de requête ---> {livre}, Livre de requête ---> {People, Devil}, Person de requête ---> {NULL}, Ghost de requête ---> {enfant}. La forme est la suivante:
Élargissons cette figure ci-dessous:
De cette façon, nous construisons notre thésaurus sensible en un arbre similaire à un par un, de sorte que lorsque nous jugeons si un mot est un mot sensible, nous réduisons considérablement la plage de correspondance de recherche. Par exemple, si nous voulons juger les Japonais, nous pouvons confirmer que l'arbre que nous devons rechercher en fonction du premier mot, puis rechercher dans cet arbre.
Mais comment jugez-vous qu'un mot sensible a pris fin? Utilisez le bit d'identification pour juger.
La clé est donc de savoir comment construire des arbres de mots aussi sensibles. Ci-dessous, j'ai implémenté l'algorithme DFA avec Hashmap en Java à titre d'exemple. Le processus spécifique est le suivant:
Les diables japonais et japonais comme exemples
1. Query "Day" dans Hashmap pour voir s'il existe dans Hashmap. S'il n'existe pas, il prouve que le mot sensible commençant par "jour" n'existe pas encore, puis nous construisons directement un tel arbre. Sauter à 3.
2. Si vous le trouvez dans Hashmap, cela indique qu'il y a un mot sensible commençant par "jour". Définissez Hashmap = Hashmap.get ("Day"), sautez à 1 et correspondez à "ce" et "personne" à son tour.
3. Déterminez si le mot est le dernier mot du mot. Si cela signifie la fin du mot sensible, définissez le bit de drapeau isEnd = 1, sinon définissez le bit de drapeau iSend = 0;
La mise en œuvre du programme est la suivante:
/ ** * Lisez le lexique sensible, mettez les mots sensibles dans le hashset et construisez un modèle d'algorithme DFA: <br> * middle = {* isEnd = 0 * country = {<br> * isEnd = 1 * People = {isEnd = 0 * People = {isEnd = 1} *} * mâle = {* isEnd = 0 * People = {* estnd = 1 * * } *} *} * Cinq = {* isEnd = 0 * star = {* isEnd = 0 * red = {* isEnd = 0 * flag = {* isEnd = 1 *} *} *} *} *} * @Author CHENMING * @Date THESAURUS * @Version 0 * @SuppressWarnings ({"RawTypes", "Unchecked"}) private void addSensitivewordToHashMap (set <string> keywordSet) {SensitivewordMap = new HashMap (KeywordSetSize ()); // Initialisez le conteneur de mot sensible pour réduire la chaîne de fonctionnement d'extension Key = null; Map NowMap = null; Map <string, string> NewWormap = null; // itération keywordset iterator <string> iterator = keywordSetIterator (); while (iteratorhasnext ()) {key = iteratorNExt (); // mot-clé NowMap = sensibilisationwordmap; pour (int i = 0; i <keyLength (); i ++) {char keychar = keycharat (i); // Convertir en objet Char-Type wordMap = NowMapGet (keyChar); // Get if (wordmap! = Null) {// Si cette clé existe, attribuez directement NowMap = (map) wordmap; } else {// S'il n'existe pas, créez une carte et définissez-vous à 0 en même temps car ce n'est pas le dernier NewWormap = new HashMap <String, String> (); NewwormApput ("isEnd", "0"); // pas le dernier NowMapput (Keychar, Newwormap); NowMap = Newwormap; } if (i == keyLength () - 1) {NowMApput ("isEnd", "1"); //Dernier} } } } }La structure HashMap obtenue par course est la suivante:
{cinq = {star = {red = {isEnd = 0, flag = {isend = 1}}, isend = 0}, isend = 0}, isend = 0}, chinois = {isEnd = 0, country = {isEnd = 0, People = {isEnd = 1}, male = {isEnd = 0, peuple = {isEnd = 0, People =}
Nous avons implémenté une méthode simple pour le thésaurus sensible, alors comment mettre en œuvre la récupération? Le processus de recherche n'est rien de plus que la mise en œuvre de Get de HashMap. Si vous le trouvez, cela prouve que le mot est un mot sensible, sinon ce n'est pas un mot sensible. Le processus est le suivant: Si nous correspondons à "vivre le peuple chinois".
1. Le premier mot "中", nous pouvons le trouver dans hashmap. Obtenez une nouvelle carte = hashmap.get ("").
2. Si map == null, ce n'est pas un mot sensible. Sinon, passez à 3
3. Obtenez ISEND dans la carte et déterminez si le mot isEnd est égal à 1. Si isEnd == 1 signifie que le mot est un mot sensible, sinon passez à 1.
À travers cette étape, nous pouvons juger que les «chinois» sont un mot sensible, mais si nous tapons des «femmes chinoises», ce n'est pas un mot sensible.
/ ** * Vérifiez si le texte contient des caractères sensibles. Les règles de vérification sont les suivantes: <br> * @author Chenming * @Date 20 avril 2014 à 16:31:03 PM * @param txt * @param beginIndex * @param MatchType * @return, s'il existe, il renvoie la longueur du personnage de mot sensible, et s'il n'existe pas, il renvoie 0 * @version 0 * / @suppresswarning "RawTypes"}) public int checkSensitiveword (String txt, int débutant, int matchtype) {boolean flag = false; // Bit de marque de fin de mot sensible: utilisé en cas de seulement 1 mot sensible int matchflag = 0; // Le nombre d'identifiants appariés est 0 par défaut Char Word = 0; Map NowMap = SensitivewordMap; for (int i = beginIndex; i <txtLength (); i ++) {word = txtCharat (i); NowMap = (map) NowMapGet (Word); // Obtenez la touche spécifiée si (NowMap! = Null) {// existe, déterminez s'il s'agit du dernier matchflag ++; // Trouvez la touche correspondante, identifiant correspondant +1 if ("1" égaux (NowMapGet ("isEnd"))) {// Si c'est la dernière règle de correspondance, terminez la boucle et renvoyez le numéro d'identifiant correspondant Flag = true; // L'indicateur de fin est vrai si (sensibilisation de FilterminmatchType == matchType) {// La règle minimale est renvoyée directement, et la règle maximale doit continuer à rechercher la pause; }}} else {// Il n'existe pas, retourne la rupture directement; }}} if (MatchFlag <2 &&! Flag) {MatchFlag = 0; } return MatchFlag; }À la fin de l'article, je fournis un téléchargement de fichiers en utilisant Java pour implémenter le filtrage des mots sensibles. Vous trouverez ci-dessous une classe de test pour prouver l'efficacité et la fiabilité de cet algorithme.
public static void main (String [] args) {SensitivewordFilter filter = new SensitivewordFilter (); SystemOutPrintln ("Nombre de mots sensibles:" + filtersensitivewordMapSize ()); String String = "Trop de sentiments tristes peuvent être limités aux parcelles de l'écran de base d'alimentation. Le protagoniste essaie d'utiliser une méthode pour libérer progressivement le guide de suicide et se soucier de la tristesse de sa propre expérience." + "Ensuite, le rôle de Falun Gong est de suivre la colère et la douleur et le chagrin de l'alliance Xihongke du protagoniste, et d'attacher ses émotions à l'intrigue d'écran trop loin, puis il est ému et pleure." + "Si vous êtes triste, vous vous allongerez dans les bras de quelqu'un et expliquerez votre cœur ou votre appareil de copie de carte de téléphone portable. Un verre de vin rouge. Un film. Par une nuit profonde et calme, vous fermez le téléphone et regarde tranquillement."; SystemMoutPrintln ("Nombre de mots à détecter:" + stringLength ()); BEGINTIME = SystemCurrenttimemillis (); Set <string> set = filterGetSensitiveword (String, 1); Long EndTime = SystemCurrentTimemillis (); SystemMoutprintln ("Le nombre de mots sensibles dans l'instruction est:" + setSize () + ". Inclure:" + set); SystemOutPrintln ("Le temps total consommé est:" + (Fintime - Begintime)); } Résultats en cours:
D'après les résultats ci-dessus, nous pouvons voir qu'il y a 771 bases de données de vocabulaire sensible, la longueur de la phrase de détection est de 184 caractères et 6 mots sensibles sont trouvés. Il a fallu 1 milliseconde au total. La vitesse visible est toujours très considérable.
Les deux téléchargements de documents suivants sont fournis:
Desktop.rar (http://xiazai.vevb.com/201611/yuanma/desktop_jb51.rar) contient deux fichiers Java, l'un est pour lire la base de données de mots sensibles (SensitivewordInit), et l'autre est la classe d'outils de mots sensibles (SensilywordFilter), qui contient trois méthodes: juger s'il y a une classe de mots sensibles (SensilywordFilter), qui contient trois méthodes: juger s'il y a une classe de mots sensibles (SensilywordFilter), qui contient trois méthodes: juger s'il y a une classe de mots sensibles (SensilywordFilter), qui contient trois méthodes: juger s'il y a une classe de mots sensibles (SensitivewordFilter), qui contient trois méthodes: Judging If y a un Word Word Class Sensive (IsContainTenSensitiveword (String Txt, int MatchType)), obtenez un mot sensible (Getsensitiveword (String txt, int MatchType)), et Substitution de mot sensible (RemplaceSensitiveword (String Txt, int MatchType, String remplacechar)).
Thésaurus sensible: cliquez pour télécharger
Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.