SpringBoot从零开始的问答社区 (4)文本过滤-字典树

SpringBoot从零开始的问答社区 (4)文本过滤-字典树

在上一篇中，完成了首页的“问题列表”，经过测试，数据和页面都没有问题。然而这里有一个不容忽视的问题，那就是实际生产环境中“问题”将是由用户发出来的，UGC 可不会按照规矩来，这些文本中的坑，懂的都懂……最经典的问题就是 HTML 注入和敏感词，两者都会使社区的用户体验大大降低，前者还可能会造成数据安全问题，后者则可能涉及到法律问题，因此文本过滤是无论如何都非常有必要做的。

敏感词过滤

思考一下，需要被过滤的关键词数量是比较多的，而且其中的一些关键词比较相似。如果要到目标文本中一个个找关键词，必然需要多次遍历长文本，效率非常低，因此比较理想的做法是把关键词构建成一个树，只遍历文本一次就完成查找的任务。

字典树又称为单词查找树、前缀树，典型应用于统计、排序和保存大量的字符串，但不仅限于字符串，所以经常被搜索引擎系统用于文本词频统计。它的优点在于，利用字符串的公共前缀来减少查询时间，最大程度减少无谓的字符串比较，查询效率比哈希树高。看完这段百度百科对字典树的介绍，不难发现它是比较适合用于本场景下的敏感词检索的。

字典树

字典树是一种树形结构，它的基本性质为：

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
• 每个节点的所有子节点包含的字符都不相同。

其基本 *** 作有：查找、插入和删除，这里我们需要的 *** 作只有插入和查找，接下来就是代码实现。

字典树节点

在项目里创建一个 util 包，新建 FilterUtil 类。

首先定义一个 TrieNode 内部类，TrieNode 即字典树节点，是构建字典树的基本单位。

private static class TrieNode {
        
        boolean end = false;

        
        final Map subNode = new HashMap<>();

        void addSubNode(Character key, TrieNode node) {
            subNode.put(key, node);
        }

        TrieNode getSubNode(Character key) {
            return subNode.get(key);
        }

        boolean isEnd() {
            return end;
        }

        void setEnd() {
            this.end = true;
        }
    }

定义 TrieNode 类之后，就可以定义字典树的根节点：

private final TrieNode rootNode = new TrieNode();

插入 *** 作

将字符（串）插入字典树的方法：

private void insert(String lineText) {
        TrieNode temp = rootNode;

        for (int i = 0; i < lineText.length(); ++i) {
            Character c = lineText.charAt(i);
            TrieNode subNode = temp.getSubNode(c);
            if (subNode == null) {
                subNode = new TrieNode();
                temp.addSubNode(c, subNode);
            }
            temp = subNode;
        }

        temp.setEnd();
    }

构建字典树

在 FilterUtil 类添加 @Component 注解，让 FilterUtil 类继承 InitializingBean 接口，重写 afterPropertiesSet() 方法，该方法会在初始化对应 Bean 时自动被调用，我们把构建字典树的部分写在这个方法中，这样在项目启动时就会自动完成字典树构建的工作。

@Override
    public void afterPropertiesSet() throws Exception {
        try {
            InputStream is = Thread.currentThread().getContextClassLoader()
                    .getResourceAsStream("SensitiveWords.txt");
            if (is == null) {
                throw new Exception("打开敏感词文件错误");
            }
            InputStreamReader reader = new InputStreamReader(is);
            BufferedReader bufferedReader = new BufferedReader(reader);
            String lineText;
            while ((lineText=bufferedReader.readLine()) != null) {
                insert(lineText.trim());        // 删除字符串两端的空白
            }
            reader.close();
        } catch (Exception e) {
            logger.error("构建字典树失败 " + e.getMessage());
        }
    }

查找+过滤

字典树构建完成后，就可以对文本进行关键词查找和过滤了。

public String filter(String text) {
    if (StringUtils.isBlank(text)) {
        return text;
    }

    StringBuilder result = new StringBuilder();
    String replacement = "*";
    TrieNode temp = rootNode;
    int begin = 0;      //词语的开头
    int position = 0;       //当前比较的字符

    while (position < text.length()) {
        char c = text.charAt(position);

        if (isSymbol(c)) {      //跳过空格等
            if (temp == rootNode) {
                result.append(c);
                ++begin;
            }
            ++position;
            continue;
        }

        temp = temp.getSubNode(c);
        if (temp == null) {
            result.append(text.charAt(begin));
            position = ++begin;
            temp = rootNode;
        } else if (temp.isEnd()) {
            result.append(replacement.repeat(position - begin + 1));
            begin = ++position;
        } else {
            ++position;
        }
    }
    result.append(text.substring(begin));

    return result.toString();
}


public boolean isSymbol(char c) {
    return !CharUtils.isAsciiAlphanumeric(c) && ((int) c < 0x2E80 || (int) c > 0x9FFF);
}

HTML过滤

直接使用 spring 内置的 HTML 过滤方法，非常方便。

import org.springframework.web.util.HtmlUtils;

HtmlUtils.htmlEscape(input) 方法返回过滤后的字符串，HTML 标签会被转义。