js реализует алгоритм фильтрации чувствительных слов

Java внешний интерфейс алгоритм JavaScript
js реализует алгоритм фильтрации чувствительных слов

Я не обновлялся больше полумесяца, потому что был немного занят в последнее время (на самом деле ленивый)

Недавно была создана функция для пользователей, чтобы оставлять комментарии.Пользователи загружают комментарии, а затем они могут видеть свои комментарии под статьей.Однако, как преемники социализма, мы практикуем основные ценности социализма, поэтому функция без фильтрации деликатных слов в комментариях не обойтись.Поискав информацию в интернете, я обнаружил, что уже есть очень зрелые решения. Обычно используемые схемы используют такие два

  1. Полнотекстовый поиск, матч за матчем. Это звучит недостаточно высоко. В случае большого количества данных будут проблемы с эффективностью. В конце статьи есть сравнение.
  2. Алгоритм DFA — определение автоматов с конечным состоянием Прикрепить ссылку на энциклопедиюДетерминированные автоматы с конечным состоянием

Введение в алгоритм DFA

DFA — это вычислительная модель, источник данных — конечное множество, а следующее состояние определяется текущим состоянием и событиями, то есть   состояние + событие = следующее состояние, таким образом постепенно строится ориентированный граф, где узлы — состояния, Следовательно, в алгоритме DFA есть только поиск и оценка, а сложных вычислений нет, что повышает эффективность алгоритма.

Справочная статья Java реализует фильтрацию чувствительных слов

реализовать логику

построить структуру данных

Преобразуйте чувствительные слова в древовидную структуру, например, так много чувствительных слов['日本鬼子','日本人','日本男人'], то структура данных выглядит следующим образом (справочная статья с изображением)

数据结构

Каждый текст является узлом, а последовательные узлы образуют слово.日本人В соответствии с цепочкой в ​​середине мы можем использовать объекты или карты для построения дерева, каштан здесь используетmapСоздайте узел. У каждого узла есть флаг состояния, чтобы указать, является ли текущий узел последним. Каждая ссылка должна иметь конечный узел. Давайте сначала посмотрим на блок-схему построения узла.

流程图

Логика суждения

Начните проверку с первого слова текста, например.你我是日本鬼子, первое слово你, узел не может быть найден на первом уровне дерева, то продолжаем искать второе слово, приходим日Когда узел первого слоя найден, выполняется поиск узла следующего слоя.本, и оцените, является ли этот узел конечным узлом, если это конечный узел, сопоставление успешно, в противном случае продолжайте сопоставление

Код

####Построение структуры данных

/**
* @description
* 构造敏感词map
* @private
* @returns
*/
private makeSensitiveMap(sensitiveWordList) {
    // 构造根节点
    const result = new Map();
    for (const word of sensitiveWordList) {
        let map = result;
        for (let i = 0; i < word.length; i++) {
            // 依次获取字
            const char = word.charAt(i);
            // 判断是否存在
            if (map.get(char)) {
                // 获取下一层节点
                map = map.get(char);
            } else {
                // 将当前节点设置为非结尾节点
                if (map.get('laster') === true) {
                    map.set('laster', false);
                }
                const item = new Map();
                // 新增节点默认为结尾节点
                item.set('laster', true);
                map.set(char, item);
                map = map.get(char);
            }
        }

    }
    return result;
}

Окончательная структура карты выглядит следующим образом

结构

Найдите деликатные слова

/**
* @description
* 检查敏感词是否存在
* @private
* @param {any} txt
* @param {any} index
* @returns
*/
private checkSensitiveWord(sensitiveMap, txt, index) {
    let currentMap = sensitiveMap;
    let flag = false;
    let wordNum = 0;//记录过滤
    let sensitiveWord = ''; //记录过滤出来的敏感词
    for (let i = index; i < txt.length; i++) {
        const word = txt.charAt(i);
        currentMap = currentMap.get(word);
        if (currentMap) {
            wordNum++;
            sensitiveWord += word;
            if (currentMap.get('laster') === true) {
                // 表示已到词的结尾
                flag = true;
                break;
            }
        } else {
            break;
        }
    }
    // 两字成词
    if (wordNum < 2) {
        flag = false;
    }
    return { flag, sensitiveWord };
}
/**
* @description
* 判断文本中是否存在敏感词
* @param {any} txt
* @returns
*/
public filterSensitiveWord(txt, sensitiveMap) {
    let matchResult = { flag: false, sensitiveWord: '' };
    // 过滤掉除了中文、英文、数字之外的
    const txtTrim = txt.replace(/[^\u4e00-\u9fa5\u0030-\u0039\u0061-\u007a\u0041-\u005a]+/g, '');
    for (let i = 0; i < txtTrim.length; i++) {
        matchResult = checkSensitiveWord(sensitiveMap, txtTrim, i);
        if (matchResult.flag) {
            console.log(`sensitiveWord:${matchResult.sensitiveWord}`);
            break;
        }
    }
    return matchResult;
}

эффективность

Чтобы увидеть эффективность DFA, я провел простой тест. Длина тестового текста составляет 5095 китайских иероглифов, а в тезаурусе чувствительных слов 2000 слов. Алгоритмы сравнения обеспечиваются алгоритмом DFA и String. родной объект.indexOfСравнение API

// 简单的字符串匹配-indexOf
ensitiveWords.forEach((word) => {
    if (ss.indexOf(word) !== -1) {
        console.log(word)
    }
})

Два алгоритма выполняются 100 раз соответственно, и получаются следующие результаты.

比较结果

Хорошо видно, чтоDFAСреднее время около 1мс, максимальное 5мс;indexOfСредняя трудоемкость метода составляет около 9 мс, а максимальная — 14 мс, поэтому эффективность DFA по-прежнему весьма очевидна.

Категории