Чувствительная фильтрация слова и текстовая фильтрация является незаменимой функцией веб -сайта. Очень необходимо разработать хороший и эффективный алгоритм фильтрации. Некоторое время назад мой друг (скоро закончился и вскоре после участия в программировании) попросил меня помочь ему прочитать текстовую фильтрацию, и это сказало, что эффективность поиска была очень медленной. Я принял программу и увидел, что весь процесс выглядит следующим образом: прочитайте чувствительный словарь, если коллекция хэшсет, получите страницу для загрузки текста, а затем сопоставьте его. Я просто думал, что этот процесс должен быть очень медленным. Для того, кто не был с ним в контакте, я могу только думать об этом, и более продвинутый пункт - это регулярные выражения. Но, к сожалению, ни один метод не является возможным. Конечно, в моем сознании я не понимал, что алгоритм может решить проблему, но Google знает это!
Введение в DFA
Среди алгоритмов, которые реализуют текстовую фильтрацию, DFA является единственным лучшим алгоритмом реализации. DFA является детерминированным конечным автоматом, что означает определение конечного автомата. Он получает следующее состояние через событие и текущее состояние, то есть событие+состояние = NextState. На следующем рисунке показан переход его состояния. На этом рисунке прописные буквы (s, u, v, q) являются всеми состояниями, а строчные буквы A и B являются действиями. Через приведенную выше картинку мы можем увидеть следующие отношения
Абб
S ------> US ------> vu ------> v
В алгоритме, который реализует чувствительную фильтрацию слов, мы должны уменьшить операции, в то время как DFA почти не имеет расчетов в алгоритме DFA, только конверсии состояния.
Java реализует алгоритм DFA для реализации конфиденциальной фильтрации слов
Ключом к реализации конфиденциальной фильтрации слов в Java является реализация алгоритма DFA. Во -первых, давайте проанализируем вышеупомянутый рисунок. В этом процессе мы думаем, что следующая структура будет более ясной.
В то же время здесь нет государственного перехода или действия, есть только запрос (найти). Мы можем подумать, что через S Query u, v, через u Query v, p, через v Query Up. Благодаря такому преобразованию мы можем превратить переход состояния в поиск с использованием коллекций Java.
По общему признанию, к нашему чувствительному тезаурусу добавлено несколько чувствительных слов: японские, японские дьяволы, Мао Зе. Донг. Так какую структуру мне нужно построить?
Первый: День запроса ---> {книга}, книга запроса ---> {People, Devil}, Query Person ---> {null}, Query Ghost ---> {Child}. Форма следующая:
Давайте расширим этот рисунок ниже:
Таким образом, мы строим наш чувствительный тезаурус в дерево, похожее на одно за другим, так что когда мы судим, является ли слово чувствительным словом, мы значительно уменьшаем диапазон соответствия поиска. Например, если мы хотим судить о японцах, мы можем подтвердить, что дерево, которое нам нужно искать, на основе первого слова, а затем поиск в этом дереве.
Но как вы судите, что конфиденциальное слово закончилось? Используйте идентификационный бит, чтобы судить.
Таким образом, ключом к этому является то, как построить такие чувствительные деревья слов. Ниже я внедрил алгоритм DFA с HashMap в Java в качестве примера. Конкретный процесс заключается в следующем:
Японские японские дьяволы как примеры
1. Запрос «День» в HashMap, чтобы увидеть, существует ли он в Hashmap. Если его не существует, это доказывает, что чувствительного слова, начинающегося с «дня», еще не существует, а затем мы напрямую строим такое дерево. Прыгайте до 3.
2. Если вы найдете его в Hashmap, это указывает на то, что есть чувствительное слово, начинающееся с «дня». SET HASHMAP = hashmap.get ("Day"), прыгайте до 1 и сопоставьте "это" и "человек" по очереди.
3. Определите, является ли слово последним словом в слове. Если это означает конец конфиденциального слова, установите бит флага isEnd = 1, в противном случае установите бит флага Isend = 0;
Реализация программы выглядит следующим образом:
/** * Прочитайте чувствительный лексикон, поместите чувствительные слова в хэшсет и постройте модель алгоритма DFA: <br> * middle = { * isend = 0 * country = {<br> * isend = 1 * People = {isend = 0 * People = {Isend = 1} *} * male = { * isend = 0 * People = { * isEnd = 1 *} *} *} *} *} *} *} } *} *} * Five = { * isend = 0 * star = { * isend = 0 * red = { * isend = 0 * flag = { * isend = 1 *} *} *} *} *} * @author chenming * @date 20 апреля 2014 г. в 3:04:20 pm * @param. @Suppresswarnings ({"ravtypes", "unchecked"}) private void AddSensitywordTohashMap (set <sding> KeyWordSet) {SensitiveWordMap = new HashMap (KeyWordSetSitize ()); // Инициализируйте чувствительный контейнер для слова, чтобы уменьшить операцию расширения String Key = null; Карта nowmap = null; Карта <string, string> newwormap = null; // итерация ключевого слова итератор <string> iterator = KeyWordSetiterator (); while (iteratorhasnext ()) {key = iteratornext (); // ключевое слово nowmap = sensitivewordmap; for (int i = 0; i <keylength (); i ++) {char keyChar = keyCharat (i); // конвертируется в объект char-type oordmap = nowmapget (keyChar); // get if (wordmap! = Null) {// Если этот ключ существует, напрямую назначить nowmap = (map) wordmap; } else {// Если он не существует, то постройте карту и установите на 0 одновременно, потому что это не последний newwormap = new Hashmap <String, String> (); newwormapput ("isend", "0"); // не последний nowmapput (KeyChar, NewWormap); nowmap = newwormap; } if (i == keylength () - 1) {nowmapput ("isend", "1"); //Последний} } } } }Структура HashMap, полученная с помощью работы, выглядит следующим образом:
{five = {star = {red = {isend = 0, flag = {isend = 1}}, isend = 0}, isend = 0}, isend = 0}, китайский = {isend = 0, country = {isend = 0, people = {isend = 1}, male = {isend = 0, isend = 0, isend = 1} {ISEND = 1} {ISEND = 1} {ISEND = 1} {ISEND = 1}, {ISEND = 1}} {ISEND =}}} {ISEND = 1}} {ISEND =}}}} {ISEND = 1}, {ISEND = 1}, {ISEND = 1}, {ISEND = 1}.
Мы реализовали простой метод для чувствительного тезауруса, так как реализовать поиск? Процесс поиска - это не что иное, как реализация HashMap. Если вы найдете это, это доказывает, что слово является конфиденциальным словом, в противном случае это не конфиденциальное слово. Процесс заключается в следующем: если мы сопоставляем «долго живем китайцев».
1. Первое слово «中», мы можем найти его в Hashmap. Получите новую карту = hashmap.get ("" ").
2. Если map == null, это не чувствительное слово. В противном случае пропустите 3
3. Получите ISEND на карте и определите, равно ли слово ISEND равна 1. Если ISEND == 1 означает, что слово является конфиденциальным словом, в противном случае пропустите до 1.
Благодаря этому шагу мы можем судить, что «китайцы» - это чувствительное слово, но если мы напечатаем «китайских женщин», это не чувствительное слово.
/*** Проверьте, содержит ли текст чувствительные символы. Правила проверки следующие: <br> * @author chenming * @date 20 апреля 2014 года в 16:31:03 * @param txt * @param beginindex * @param matchtype * @return, если он существует, он возвращает длину чувствительного слова, и если оно не существует, он возвращает 0 * @version 0 * "rawtypes"}) public int checkEnsitiveword (String txt, int beginIndex, int matchtype) {boolean flag = false; // Чувствительный конец слова бит: используется только в случае 1 чувствительного слова int matchflag = 0; // количество соответствующих идентификаторов по умолчанию по умолчанию char word = 0; Карта nowmap = sensitywordmap; for (int i = beginindex; i <txtlength (); i ++) {word = txtcharat (i); nowmap = (map) nowmapget (word); // Получить указанный ключ if (nowmap! = Null) {// существует, определить, является ли это последним совпадением ++; // Найти соответствующий ключ, соответствующий идентификатор +1 if ("1" equals (nowmapget ("isend"))) {// Если это последнее правило совпадения, завершить цикл и вернуть соответствующий номер идентификатора flag = true; // Конечный флаг верно, если (SensitiveWordFilterminMintMatchType == MatchType) {// Минимальное правило возвращается напрямую, и максимальное правило должно продолжать искать перерыв; }}} else {// он не существует, вернуть перерыв напрямую; }}} if (matchflag <2 &&! flag) {matchflag = 0; } return matchflag; }В конце статьи я предоставляю загрузку файла с использованием Java для реализации конфиденциальной фильтрации слов. Ниже приведен тестовый класс, чтобы доказать эффективность и надежность этого алгоритма.
public static void main (string [] args) {sensitivewordfilter filter = new SensitiveWordFilter (); SystemOutPrintln («Количество чувствительных слов:» + FilterSitiveWordMapSize ()); String String = «Слишком много грустных чувств может быть ограничено участками на базовом экране кормления. Главный герой пытается использовать какой -то метод для постепенного освобождения Группа по самоубийству и заботиться о печали своего собственного опыта». + «Тогда роль Фалунь Гонга состоит в том, чтобы следовать за гневом и печалью Героя и печали главного героя, а также прикрепить его эмоции к сюжету, а затем он перемещается и плачет». + "Если вам грустно, вы будете лежать в чьей -то руках и объяснить свое сердце или копирование мобильного телефона. Стакан красно -вина. Фильм. В глубокой и тихой ночи вы закрываете телефон и тихо смотрите."; SystemMoutPrintln («Количество слов, которые необходимо обнаружить:" + stringlength ()); long bomintime = systemcurrenttimemillis (); SET <String> set = FilterGetSensityWord (String, 1); Long EndTime = SystemCurrentTimeMiLlis (); SystemMoutPrintln («Количество чувствительных слов в утверждении:« + setSize () + ». Включите:« + set); SystemOutPrintln («Общее время потребляется:» + (конечное время - начало)); } Результаты работы:
Из приведенных выше результатов мы видим, что существует 771 конфиденциальные словарные базы данных, длина предложения обнаружения составляет 184 символа, а 6 чувствительных слов найдено. Всего потребовалось 1 миллисекунд. Видимая скорость все еще очень значительна.
Следующие две загрузки документов представлены:
Desktop.rar (http://xiazai.vevb.com/201611/yuanma/desktop_jb51.rar) содержит два файла Java, один из которых состоит (IscontaintSensityword (String txt, int matchtype)), получение чувствительного слова (gestensityword (string txt, int matchtype)) и конфиденциальное замену слов (заменяет смысл (String txt, int matchtype, string replacechar)).
Чувствительный тезаурус: нажмите, чтобы загрузить
Выше всего содержание этой статьи. Я надеюсь, что это будет полезно для каждого обучения, и я надеюсь, что все будут поддерживать Wulin.com больше.