El filtrado confidencial de palabras y texto es una función indispensable de un sitio web. Es muy necesario diseñar un algoritmo de filtrado bueno y eficiente. Hace algún tiempo, un amigo mío (se graduó pronto y no pasó mucho tiempo después de involucrarme en la programación) me pidió que lo ayudara a leer una cosa de filtrado de texto, y dijo que la eficiencia de recuperación era muy lenta. Tomé el programa y vi que todo el proceso es el siguiente: lea el vocabulario confidencial, si la colección hashset, obtiene la página para cargar el texto y luego coincidir con él. Pensé que este proceso debe ser muy lento. Para alguien que no ha estado en contacto con él, solo puedo pensar en esto, y un punto más avanzado son las expresiones regulares. Pero desafortunadamente, ninguno de los métodos es factible. Por supuesto, en mi conciencia, no me di cuenta de que el algoritmo podría resolver el problema, ¡pero Google lo sabe!
Introducción a DFA
Entre los algoritmos que implementan el filtrado de texto, DFA es el único algoritmo de implementación mejor. DFA es autómata finito determinista, lo que significa determinar el autómata finito. Obtiene el siguiente estado a través del evento y el estado actual, es decir, event+state = nextState. La siguiente figura muestra la transición de su estado. En esta figura, las letras mayúsculas (S, U, V, Q) son todos estados, y las letras minúsculas A y B son acciones. A través de la imagen de arriba podemos ver la siguiente relación
tejido
S ------> US ------> Vu ------> V
En un algoritmo que implementa un filtrado de palabras sensible, debemos reducir las operaciones, mientras que DFA casi no tiene cálculos en el algoritmo DFA, solo las conversiones de estado.
Java implementa el algoritmo DFA para implementar un filtrado de palabras confidencial
La clave para implementar el filtrado de palabras confidencial en Java es la implementación del algoritmo DFA. Primero, analicemos la figura anterior. En este proceso, creemos que la siguiente estructura será más clara.
Al mismo tiempo, no hay transición o acción estatal aquí, solo hay consulta (encontrar). Podemos pensar que a través de S Query U, V, a través de la consulta V, P, a través de la consulta. A través de tal transformación, podemos transformar la transición del estado en búsqueda utilizando colecciones Java.
Es cierto que hay varias palabras sensibles agregadas a nuestro tesauro sensible: demonios japoneses, japoneses, Mao Ze. Polla. Entonces, ¿qué tipo de estructura necesito construir?
Primero: día de consulta ---> {libro}, libro de consultas ---> {personas, diablo}, persona de consulta ---> {null}, consulta fantasma ---> {niño}. La forma es la siguiente:
Expandamos esta figura a continuación:
De esta manera, construimos nuestro tesauro sensible en un árbol similar a uno por uno, de modo que cuando juzgamos si una palabra es una palabra sensible, reducimos en gran medida el rango de coincidencia de búsqueda. Por ejemplo, si queremos juzgar a los japoneses, podemos confirmar que el árbol que necesitamos buscar en función de la primera palabra y luego buscar en este árbol.
Pero, ¿cómo juzgas que una palabra sensible ha terminado? Use el bit de identificación para juzgar.
Entonces, la clave para esto es cómo construir árboles de palabras tan sensibles. A continuación, he implementado el algoritmo DFA con HashMap en Java como ejemplo. El proceso específico es el siguiente:
Devils japoneses, japoneses como ejemplos
1. Consulta "Día" en Hashmap para ver si existe en Hashmap. Si no existe, demuestra que la palabra sensible que comienza con el "día" aún no existe, y luego construimos directamente dicho árbol. Salta a 3.
2. Si lo encuentra en hashmap, indica que hay una palabra sensible que comienza con "día". Establezca hashmap = hashmap.get ("día"), salta a 1 y coincide con "esto" y "persona" a su vez.
3. Determine si la palabra es la última palabra en la palabra. Si significa el final de la palabra sensible, configure el bit de indicador isend = 1, de lo contrario, configure el bit de indicador isend = 0;
La implementación del programa es la siguiente:
/** * Lea el léxico sensible, coloque las palabras confidenciales en el hashset y construya un modelo de algoritmo DFA: <br> * middle = { * isend = 0 * país = {<br> * isend = 1 * People = {isend = 0 * People = {isend = 1} *} * masculino = { * * ISEND = 0 * People = {{iSend = 1 *}} } *} *} * Cinco = { * isend = 0 * star = { * isend = 0 * rojo = { * isend = 0 * flag = { * isend = 1 *} *} *} *} *} * @author chenming * @date el 20 de abril de 2014 a las 3:04:20 pm * @param Key Wordset Sensitive Thesurus * @version 0 */ @SupessWarnings ({"RawTypes", "sin control"}) Void privado addSensitiveWordToHashMap (set <string> KeywordSet) {SensitiveWordMap = new HashMap (KeywordSetSetSize ()); // Inicializar el contenedor de palabras sensible para reducir la operación de expansión String Key = NULL; Map nowmap = null; Map <string, string> newWormap = null; // iteration KeywordSet Iterator <String> iterator = keywordSetIterator (); while (iteratorHasNext ()) {key = iteratornext (); // Palabra clave NowMap = SensitiveWordMap; for (int i = 0; i <keyLength (); i ++) {char keychar = keyCharat (i); // Convertir al objeto Char-Type WordMap = NowMapget (KeyChar); // get if (wordmap! = Null) {// Si esta clave existe, asigne directamente nowmap = (map) wordmap; } else {// Si no existe, luego construya un mapa y configure a 0 al mismo tiempo porque no es el último newWormap = new HashMap <String, String> (); NewWormApput ("isend", "0"); // no es el último NowMapput (KeyChar, NewWormap); NowMap = NewWormap; } if (i == keylength () - 1) {nowMapput ("isend", "1"); //Último} } } } }La estructura hashmap obtenida por ejecutar es la siguiente:
{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}}}}}
Hemos implementado un método simple para el tesauro sensible, entonces, ¿cómo implementar la recuperación? El proceso de búsqueda no es más que la implementación de HASHMAP. Si lo encuentra, demuestra que la palabra es una palabra sensible, de lo contrario no es una palabra sensible. El proceso es el siguiente: si coincidimos con "Long Long Live the Chinese People".
1. La primera palabra "中", podemos encontrarla en hashmap. Obtenga un nuevo mapa = hashmap.get ("").
2. Si map == nulo, no es una palabra sensible. De lo contrario, salte a 3
3. Obtenga arrebato en el mapa y determine si la palabra es igual a 1. Si isend == 1 significa que la palabra es una palabra sensible, de lo contrario saltear a 1.
A través de este paso, podemos juzgar que el "pueblo chino" es una palabra sensible, pero si escribimos "mujeres chinas", no es una palabra sensible.
/*** Verifique si el texto contiene caracteres sensibles. 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 checkSensitiveWord (string txt, int beginIndex, int matchType) {boolean flag = false; // bit de marca de finalización sensible: se usa en el caso de que solo hay 1 bit de una palabra sensible int coinclag = 0; // El número de identificadores coincidentes es 0 por defecto Char Word = 0; Map nowMap = SensitiveWordMap; for (int i = beginIndex; i <txtLength (); i ++) {word = txtcharat (i); NowMap = (map) NowMapget (palabra); // Obtenga la clave especificada if (NowMap! = NULL) {// Exist, determine si es el último MatchFlag ++; // Encuentre la clave correspondiente, identificador coincidente +1 if ("1" es igual (nowMapget ("isend"))) {// Si es la última regla de coincidencia, finalice el bucle y devuelva el número de identificador de coincidencia flag = true; // El indicador final es verdadero if (SensitiveWordFilMinMatchType == MatchType) {// La regla mínima se devuelve directamente, y la regla máxima debe continuar buscando el descanso; }}} else {// No existe, return rupe directamente; }}} if (matchFlag <2 &&! flag) {matchFlag = 0; } return MatchFlag; }Al final del artículo, proporciono una descarga de archivos usando Java para implementar un filtrado de palabras confidencial. A continuación se muestra una clase de prueba para demostrar la eficiencia y la confiabilidad de este algoritmo.
public static void main (string [] args) {SensitiveWordFilter Filter = new SensitiveWordFilter (); SystemOutPrintln ("Número de palabras confidenciales:" + FilterSensitiveWordMapsize ()); String String = "Demasiados sentimientos tristes pueden limitarse a las tramas en la pantalla base de alimentación. El protagonista intenta usar algún método para liberar gradualmente la guía de suicidio y se preocupa por la tristeza de su propia experiencia". + "Entonces el papel de Falun Gong es seguir la ira, el dolor y el dolor de la alianza Xihongke del protagonista, y adjuntar sus emociones a la trama de la pantalla demasiado lejos, y luego se muda y llora". + "Si estás triste, te acostarás en los brazos de alguien y explicarás tu corazón o el dispositivo de copia de tu tarjeta de teléfono móvil. Una copa de vino tinto. Una película. En una noche profunda y tranquila, cierras el teléfono y miras en silencio"; SystemOutPrintln ("Número de palabras a detectar:" + StringLength ()); largo BegiNtime = SystemCurrentTimemillis (); Set <String> set = filtergetSensitiveWord (string, 1); Long Time = SystemCurrentTimemillis (); SystemOutPrintln ("El número de palabras sensibles en la declaración es:" + setSize () + ". Incluye:" + set); SystemOutPrintln ("El tiempo total consumido es:" + (EndTime - BegIntime)); } Resultados de ejecución:
De los resultados anteriores, podemos ver que hay 771 bases de datos de vocabulario sensibles, la longitud de la oración de detección es de 184 caracteres y se encuentran 6 palabras sensibles. Tomó 1 milisegundo en total. La velocidad visible sigue siendo muy considerable.
Se proporcionan las siguientes dos descargas de documentos:
Desktop.rar (http://xiazai.vevb.com/201611/yuanma/desktop_jb51.rar) contiene dos archivos Java, uno es leer la base de datos de palabras confidenciales (Sensitive Wordinit), y el otro es la clase de herramienta de palabra sensible (Sensitivewordfilter), que contiene tres métodos: si hay una palabra sensible), y el otro es la clase sensible de la herramienta (SensitiveWordFilter), que contiene tres métodos: si hay una palabra sensible), y el otro es la clase sensible de la herramienta de palabras (sensible (ISCONTAINTSENSIPTYWORD (String TXT, int matchType), obteniendo palabras sensibles (GetSenSitiveWord (String txt, int matchType)) y reemplazo de palabras sensibles (reemplazaSensitiveWord (string txt, int matchtype, string replaceChar)).
Tesauro sensible: haga clic para descargar
Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.