A filtragem sensível de palavras e texto é uma função indispensável de um site. É muito necessário projetar um algoritmo de filtragem bom e eficiente. Algum tempo atrás, um amigo meu (se formou em breve e não demorou muito depois de me envolver na programação) me pediu para ajudá -lo a ler uma coisa de filtragem de texto, e dizia que a eficiência da recuperação era muito lenta. Aceitei o programa e vi que todo o processo é o seguinte: Leia o vocabulário sensível, se a coleção de hashset, pegue a página para fazer o upload do texto e depois combiná -lo. Eu apenas pensei que esse processo deveria ser muito lento. Para alguém que não entrou em contato com ele, só consigo pensar nisso, e um ponto mais avançado são expressões regulares. Infelizmente, porém, nenhum método é viável. É claro que, na minha consciência, eu não percebi que o algoritmo poderia resolver o problema, mas o Google sabe disso!
Introdução ao DFA
Entre os algoritmos que implementam a filtragem de texto, o DFA é o único algoritmo de implementação melhor. O DFA é um autômato finito determinístico, o que significa determinar o autômato finito. Ele obtém o próximo estado através do evento e do estado atual, ou seja, evento+estado = nextState. A figura a seguir mostra a transição de seu estado. Nesta figura, as letras maiúsculas (s, u, v, q) são todos estados, e as letras minúsculas A e B são ações. Através da imagem acima, podemos ver o seguinte relacionamento
ABB
S ------> nós ------> vu ------> v
Em um algoritmo que implementa filtragem sensível de palavras, devemos reduzir as operações, enquanto o DFA quase não possui cálculos no algoritmo DFA, apenas conversões estaduais.
Java implementa o algoritmo DFA para implementar filtragem de palavras sensíveis
A chave para implementar a filtragem de palavras sensíveis em Java é a implementação do algoritmo DFA. Primeiro, vamos analisar a figura acima. Nesse processo, achamos que a seguinte estrutura será mais clara.
Ao mesmo tempo, não há transição ou ação de estado aqui, há apenas consulta (encontre). Podemos pensar que, através de S Query U, V, através de U Query V, P, através da consulta V. Por meio dessa transformação, podemos transformar a transição do estado em pesquisa usando coleções Java.
É certo que existem várias palavras sensíveis adicionadas ao nosso sinônimo sensível: japonês, demônios japoneses, Mao Ze. Dong. Então, que tipo de estrutura eu preciso construir?
Primeiro: Query Day ---> {Book}, Query Book ---> {People, Diabo}, Pergunta Pessoa ---> {null}, Query Ghost ---> {Child}. A forma é a seguinte:
Vamos expandir esta figura abaixo:
Dessa forma, construímos nosso sinônimo sensível em uma árvore semelhante a uma a uma, de modo que, quando julgamos se uma palavra é uma palavra sensível, reduzimos bastante a faixa de correspondência de pesquisa. Por exemplo, se queremos julgar os japoneses, podemos confirmar que a árvore que precisamos pesquisar com base na primeira palavra e depois pesquisar nesta árvore.
Mas como você julga que uma palavra sensível terminou? Use o bit de identificação para julgar.
Portanto, a chave para isso é como construir árvores de palavras tão sensíveis. Abaixo, implementei o algoritmo DFA com hashmap em Java como exemplo. O processo específico é o seguinte:
Japonês, demônios japoneses como exemplos
1. Query "dia" no hashmap para ver se existe no hashmap. Se não existir, isso prova que a palavra sensível começando com "dia" ainda não existe e, em seguida, construímos diretamente uma árvore. Salte para 3.
2. Se você o encontrar no hashmap, indica que há uma palavra sensível começando com "dia". Definir hashmap = hashmap.get ("dia"), pule para 1 e combine "this" e "pessoa" por sua vez.
3. Determine se a palavra é a última palavra na palavra. Se isso significa o final da palavra sensível, defina o bit sinalizador isend = 1, caso contrário, defina o bit sinalizador isend = 0;
A implementação do programa é a seguinte:
/** * Leia o léxico sensível, coloque as palavras sensíveis no hashset e construa um modelo de algoritmo DFA: <br> * middle = { * isend = 0 * country = {<br> * isend = 1 * pessoas = {isend = 0 * pessoas = {isend = 1} *} »= { * isend = 0. } *} *} * Cinco = { * isend = 0 * star = { * isend = 0 * vermelho = { * isend = 0 * flag = { * isend = 1 *} *} *} *} *} * @author chenming * @date 20 de abril, 2014 às 3:04:20 * * @autam chenming * @date 20, 2014 às 3:04:20 * * @Suppresswarnings ({"RawTypes", "desmarcado"}) private void addSensitivewordToHashMap (set <string> keywordSet) {sensívelwordMap = new hashmap (KeywordSetSetSize ()); // Inicialize o contêiner de palavras sensíveis para reduzir a operação de expansão Tecla de sequência = null; Mapa NowMap = null; Mapa <string, string> newwormap = null; // iteração do iterador de palavras -chave iteração <tring> iterator = keywordSetIterator (); while (iteratorHasNext ()) {key = iterArorNext (); // palavra -chave nowmap = sensívelwordmap; for (int i = 0; i <keyLength (); i ++) {char keychar = keycharat (i); // converter para o objeto de char wordmap = nowmapget (keychar); // get if (wordmap! = Null) {// Se houver essa tecla, atribua diretamente nowmap = (map) wordmap; } else {// Se não existir, crie um mapa e defina o ISEND para 0 ao mesmo tempo, porque não é o último newwormap = new hashmap <string, string> (); newwormapput ("isend", "0"); // não o último NowMapput (Keychar, Newwormap); agoraMap = newwormap; } if (i == keyLength () - 1) {NowMapput ("isend", "1"); //Durar} } } } }A estrutura de hashmap obtida pela corrida é a seguinte:
{cinco = {star = {Red = {isend = 0, flag = {isend = 1}}, isend = 0}, isend = 0}, isend = 0}, chinês = {isend = 0, country = {iSend = 0, pessoas = {isend = 1}, mass = {isend = 0, {pessoas 0, {ISEND = 0, ISend = {isend = 1}, mass = {isend = 0, 0, {{
Implementamos um método simples para sinário sensível, então como implementar a recuperação? O processo de pesquisa nada mais é do que a implementação do hashmap. Se você o encontrar, prova que a palavra é uma palavra sensível, caso contrário, não é uma palavra sensível. O processo é o seguinte: se combinarmos "viva o povo chinês".
1. A primeira palavra "中", podemos encontrá -la no hashmap. Obtenha um novo mapa = hashmap.get ("").
2. Se mapa == NULL, não é uma palavra sensível. Caso contrário, pule para 3
3. Obtenha o isend no mapa e determine se a palavra isend é igual a 1. Se isend == 1 significa que a palavra é uma palavra sensível, de outra forma, pule para 1.
Através desta etapa, podemos julgar que o "povo chinês" é uma palavra sensível, mas se digitarmos "mulheres chinesas", não é uma palavra sensível.
/*** Verifique se o texto contém caracteres sensíveis. As regras de verificação são as seguintes: <br> * @author chenming * @date 20 de abril de 2014 às 16:31:03 * @param txt * @param BeginIndex * @param matchType * @return, se existe, ele existe, retorna o comprimento do caractere sensível/ não existe, retorna 0 * "RawTypes"}) public int checkSensitiveword (string txt, int BeginIndex, int matchType) {sinalizador booleano = false; // Bit de ponta final de palavra sensível: usado em caso de apenas 1 palavra sensível int matchflag = 0; // O número de identificadores correspondentes é 0 por padrão char word = 0; Mapa NowMap = SensívelWordMap; for (int i = BEGNIDEX; i <txtLength (); i ++) {word = txtcharat (i); NowMap = (map) NowMapget (Word); // Obtenha a tecla especificada se (NowMap! = Null) {// Existir, determine se é o último matchflag ++; // Encontre a chave correspondente, identificador correspondente +1 se ("1" é igual (NowMapget ("isend"))) {// Se for a última regra de correspondência, encerre o loop e retorne o sinalizador de número do identificador correspondente = true; // O sinalizador final é verdadeiro se (SensívelwordFilterMinMatchType == MatchType) {// A regra mínima é retornada diretamente e a regra máxima precisa continuar procurando quebra; }}} else {// não existe, retorne a quebra diretamente; }}} if (matchflag <2 &&! Flag) {matchflag = 0; } retornar matchflag; }No final do artigo, forneço um download de arquivo usando Java para implementar filtragem de palavras sensíveis. Abaixo está uma classe de teste para provar a eficiência e a confiabilidade desse algoritmo.
public static void main (string [] args) {sensívelwordFilter filter = new SensívelWordFilter (); SystemOutPrintln ("Número de palavras sensíveis:" + filterSensitivewordMapsize ()); String string = "Muitos sentimentos tristes podem ser limitados às parcelas na tela base de alimentação. O protagonista tenta usar algum método para liberar gradualmente o guia suicida e se preocupar com a tristeza de sua própria experiência". + "Então, o papel do gong Falun é seguir a raiva, a tristeza e a tristeza da Aliança Xihongke do protagonista, e anexar suas emoções à trama da tela muito longe, e então ele é movido e chorando". + "Se você estiver triste, você deitará nos braços de alguém e explicará seu coração ou seu dispositivo de cópia de cartão de celular. Um copo de vinho tinto. Um filme. Em uma noite profunda e tranquila, você fecha o telefone e olha em silêncio."; SystemMoutPrintln ("Número de palavras a serem detectadas:" + stringLength ()); long begintime = SystemCurrentTimemillis (); Set <string> set = filtergetSensitiveword (string, 1); Long Endtime = SystemCurrentTimemillis (); SystemMoutPrintln ("O número de palavras sensíveis na declaração é:" + setSize () + ". Inclua:" + set); SystemOutPrintln ("O tempo total consumido é:" + (EndTime - BeginTime)); } Resultados em execução:
A partir dos resultados acima, podemos ver que existem 771 bancos de dados de vocabulário sensíveis, o comprimento da sentença de detecção é de 184 caracteres e 6 palavras sensíveis são encontradas. Demorou 1 milissegundo no total. A velocidade visível ainda é muito considerável.
Os dois downloads de documentos a seguir são fornecidos:
Desktop.rar (http://xiazai.VeVB.COM/201611/yuanma/Desktop_jb51.rar) contains two Java files, one is to read sensitive word database (SensitiveWordInit), and the other is the sensitive word tool class (SensitivewordFilter), which contains three methods: judging whether there is a sensitive word (ISContaintSensitiveword (String txt, int matchType)), obtenha palavra sensível (GetSensitiveword (String txt, int matchType)) e substituição de palavras sensíveis (substitua as palavras -palavras (String txt, int matchType, string replacechar)).
Thesaurus sensível: clique para baixar
O exposto acima é todo o conteúdo deste artigo. Espero que seja útil para o aprendizado de todos e espero que todos apoiem mais o wulin.com.