侧边栏壁纸
博主头像
zzzgd博主等级

一忘皆空!

  • 累计撰写 22 篇文章
  • 累计创建 15 个标签
  • 累计收到 25 条评论

目 录CONTENT

文章目录

使用字典树TireTree和AOP注解SpringEL表达式过滤敏感词

zzzgd
2021-09-09 / 0 评论 / 0 点赞 / 315 阅读 / 10,310 字
温馨提示:
本文最后更新于 2021-12-21,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

@TOC

字典树

字典树的概念这里不多说, 一般我们如果需要判断一串字符串中某个词语在不在, 都是直接用contain方法或者indexOf方法. 但是这样的话, 如果需要判断的词语很多, 效率就很低了. 如果字符串的长度是n, 词语有m个, 平均长度是l, 那这样需要调用m次indexOf方法或者contains方法, 而indexOf方法或contain方法的本质也是要遍历原字符串. 因此词语越多, 效率越低.

而字典树的特性, 将很多个词语, 构建成一个树, 树的高度和最长的词语相同. 如果词语大致长度一样, 那么树的高度也就一定, 也就是说不会因为词语越多而导致效率降低. 只取决于原字符串的长度.

字典树可以用数组, list, map等来实现. 如果词语是有限的, 比如都是英文, 26个字母, 那么可以用大小为26的数组来表示, 如果包括中文, 因为涵盖范围太大, 导致每个节点都会占用很大的空间, 不如用map.

代码

package com.zgd.common.util.word;

import cn.hutool.core.util.PrimitiveArrayUtil;
import lombok.extern.slf4j.Slf4j;

import java.util.*;


@Slf4j
public class TrieTree {

  TrieTree() {
  }

  private char[] ignoreChar;

  public void setIgnoreChar(char[] ignoreChar) {
    this.ignoreChar = ignoreChar;
  }

  /**
   * 内部节点类
   *
   * @author "zhshl"
   * @date 2014-10-14
   */
  private static class Node {
    //该字串的重复数目,  该属性统计重复次数的时候有用,取值为0、1、2、3、4、5……
    private int dumpli_num;
    //以该字串为前缀的字串数, 应该包括该字串本身!!!!!
    private int prefix_num;
    //此处用数组实现,当然也可以map或list实现以节省空间
    private Map<Character, Node> childs;
    private Node parent;
    //是否为单词节点
    private boolean isLeaf;

    public Node() {
      dumpli_num = 0;
      prefix_num = 0;
      isLeaf = false;
      childs = new HashMap<>();
    }
  }

  private static final Node root = new Node();


  /**
   * 插入字串,用循环代替迭代实现
   *
   * @param words
   */
  public void add(String words) {
    add(root, words);
  }

  /**
   * 插入字串,用循环代替迭代实现
   *
   * @param root
   * @param words
   */
  private void add(Node root, String words) {
    words = words.toLowerCase();
    //转化为小写
    char[] chrs = words.toCharArray();

    for (int i = 0, length = chrs.length; i < length; i++) {
      ///用相对于a字母的值作为下标索引,也隐式地记录了该字母的值
      char index = chrs[i];
      if (root.childs.get(index) != null) {
        //已经存在了,该子节点prefix_num++
        root.childs.get(index).prefix_num++;
      } else {
        ///如果不存在
        root.childs.put(index, new Node());
        root.childs.get(index).prefix_num++;
        root.childs.get(index).parent = root;
      }

      ///如果到了字串结尾,则做标记
      if (i == length - 1) {
        root.childs.get(index).isLeaf = true;
        root.childs.get(index).dumpli_num++;
      }
      ///root指向子节点,继续处理
      root = root.childs.get(index);
    }
  }

  public boolean removePrefix(String prefix) {
    prefix = prefix.toLowerCase();
    Node node = getNode(root, prefix, false);
    if (node == null) {
      return false;
    }
    node.parent.childs.remove(prefix.charAt(prefix.length() - 1));
    return true;
  }

  public boolean remove(String word) {
    return remove(root, word);
  }

  private boolean remove(Node root, String word) {
    word = word.toLowerCase();
    Node node = getNode(root, word, false);
    if (node == null) {
      return false;
    }

    for (int lastOne = word.length() - 1, i = lastOne; i >= 0; i--) {
      if (node.childs.isEmpty() && (i == lastOne || !node.isLeaf)) {
        //可删除
        node.parent.childs.remove(word.charAt(i));
      } else {
        if (i == word.length() - 1) {
          node.dumpli_num--;
          node.isLeaf = false;
        }
        node.prefix_num--;
      }
      node = node.parent;
    }
    return true;
  }

  public List<String> getAllWords() {
    Map<String, Integer> map = getAllWordsCountMap();
    return new ArrayList<>(map.keySet());
  }

  /**
   * 遍历Trie树,查找所有的words以及出现次数
   *
   * @return HashMap<String, Integer> map
   */
  public Map<String, Integer> getAllWordsCountMap() {
    return getAllWordsCountMap(root, "");
  }

  /**
   * 得到以某字串为前缀的字串集,包括字串本身! 类似单词输入法的联想功能
   *
   * @param prefix 字串前缀
   * @return 字串集以及出现次数,如果不存在则返回null
   */
  private Map<String, Integer> getWordsCountMapForPrefix(String prefix) {
    return getWordsCountMapForPrefix(root, prefix);
  }

  /**
   * 前序遍历。。。
   *
   * @param root    子树根节点
   * @param prefixs 查询到该节点前所遍历过的前缀
   * @return
   */
  private Map<String, Integer> getAllWordsCountMap(Node root, String prefixs) {
    Map<String, Integer> map = new LinkedHashMap<>();
    if (root != null) {
      if (root.isLeaf) {
        //当前即为一个单词
        map.put(prefixs, root.dumpli_num);
      }
      for (Map.Entry<Character, Node> en : root.childs.entrySet()) {
        char ch = en.getKey();
        //递归调用前序遍历
        String tempStr = prefixs + ch;
        map.putAll(getAllWordsCountMap(en.getValue(), tempStr));
      }
    }
    return map;
  }


  /**
   * 判断某字串是否在字典树中
   *
   * @param word
   * @return true if exists ,otherwise  false
   */
  public boolean isExist(String word, boolean ignore) {
    return getNode(root, word, ignore) != null;
  }


  public List<String> getWordsForPrefix(String prefix) {
    return new ArrayList<>(getWordsCountMapForPrefix(root, prefix).keySet());
  }

  /**
   * 得到以某字串为前缀的字串集,包括字串本身!
   *
   * @param root
   * @param prefix
   * @return 字串集以及出现次数
   */
  private Map<String, Integer> getWordsCountMapForPrefix(Node root, String prefix) {
    char[] chs = prefix.toLowerCase().toCharArray();
    for (int i = 0, length = chs.length; i < length; i++) {
      char index = chs[i];
      if (root.childs.get(index) == null) {
        return new HashMap<>();
      }
      root = root.childs.get(index);
    }
    ///结果包括该前缀本身
    ///此处利用之前的前序搜索方法进行搜索
    return getAllWordsCountMap(root, prefix);
  }


  private Node getNode(Node node, String word, boolean ignore) {
    char[] chs = word.toLowerCase().toCharArray();
    for (int i = 0, length = chs.length; i < length; i++) {
      char index = chs[i];
      if (ignore && i < length - 1 && ignoreChar != null && PrimitiveArrayUtil.contains(ignoreChar, index)) {
        continue;
      }
      if (node.childs.get(index) == null) {
        return null;
      }
      node = node.childs.get(index);
    }
    return node;
  }

  public Map<Integer, String> match(String str, boolean ignore) {
    return match(root, str, ignore);
  }

  /**
   * 返回一串字符串中, 符合词库的首次出现的索引
   */
  private Map<Integer, String> match(Node node, String str, boolean ignore) {
    char[] chs = str.toLowerCase().toCharArray();
    Map<Integer, String> map = new HashMap<>();
    out:
    for (int i = 0, length = chs.length; i < length; i++) {
      StringBuilder name = new StringBuilder();
      Node currentNodes = node;
      for (int j = i; j < length; j++) {
        char index = chs[j];
        if (ignore && j < length - 1 && ignoreChar != null && PrimitiveArrayUtil.contains(ignoreChar, index)) {
          //跳过忽略字符
          continue;
        }
        if (currentNodes.childs.get(index) == null) {
          continue out;
        }
        name.append(index);
        currentNodes = currentNodes.childs.get(index);
        if (currentNodes.isLeaf) {
          //匹配到则跳出循环
          map.put(i, name.toString());
          continue out;
        }
      }
    }
    return map;
  }


  public boolean isMatch(String str, boolean ignore) {
    return isMatch(root, str, ignore);
  }

  private boolean isMatch(Node node, String str, boolean ignore) {
    char[] chs = str.toLowerCase().toCharArray();
    out:
    for (int i = 0, length = chs.length; i < length; i++) {
      Node currentNodes = node;
      for (int j = i; j < length; j++) {
        char index = chs[j];
        if (ignore && j < length - 1 && ignoreChar != null && PrimitiveArrayUtil.contains(ignoreChar, index)) {
          //跳过忽略字符
          continue;
        }
        if (currentNodes.childs.get(index) == null) {
          continue out;
        }
        currentNodes = currentNodes.childs.get(index);
        if (currentNodes.isLeaf) {
          //匹配到则跳出循环
//          log.debug("匹配到关键词");
          return true;
        }
      }
    }
    return false;
  }
}

单例工厂类

package com.zgd.common.util.word;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.function.Supplier;

/**
 * TreeManager
 *
 * @author zgd
 * @date 2021/9/9 14:58
 */
@Slf4j
public class TreeManager {

  private static TrieTree trieTree;

  public static TrieTree get() {
    if (trieTree == null) {
      synchronized (String.class) {
        if (trieTree == null) {
          trieTree = new TrieTree();
        }
      }
    }
    return trieTree;
  }

  public static synchronized TrieTree init(Collection<String> words, char... ignore) {
    return init(() -> words, ignore);
  }

  public static synchronized TrieTree init(Supplier<Collection<String>> words, char... ignore) {
    get();
    log.debug("初始化...");
    for (String s : words.get()) {
      TreeManager.trieTree.add(s);
    }
    trieTree.setIgnoreChar(ignore);
    return trieTree;
  }


  public static void main(String[] args) {
    List<String> objects = new ArrayList<>();
    objects.add("abc");
    objects.add("abcd");
    objects.add("abadfc");
    objects.add("aabc");
    objects.add("大法师bc");
    objects.add("啥时给bc");
    objects.add("大a");
    objects.add("大a");
    objects.add("大a");
    objects.add("大a");
    objects.add("大ab");
    objects.add("大abc");
    objects.add("大abc");
    objects.add("大abc");
    objects.add("大abcd");
    objects.add("大abcde");
    init(() -> objects, '&', '!', '$');

    System.out.println(get().isExist("大abc", true));
    System.out.println(get().isExist("大a1bc", true));
    System.out.println(get().isExist("大ab&c", true));
    System.out.println(get().isExist("大ab&c", false));

    System.out.println(get().match("阿嘎发大a顺丰噶大法&!!!!!!!师bc那啥吗司法所大ab", true));

    System.out.println(get().getWordsForPrefix("大"));

  }
}

使用service类

@Component
public class BannedWordFilter {

  private TrieTree trieTree;

  @Autowired
  private IBannedWordService bannedWordService;

	//指定需要跳过哪些无用的字符
  private static final String IGNORE_CHAR = ",./'\"\\~!@#$%^&*()_+<>?;:[]{}-=~`¥…()—【】‘;:”“’。,_·、? ";

  @PostConstruct
  public void init() {
    List<String> words = bannedWordService.lambdaQuery().select(BannedWord::getName).list().stream().map(BannedWord::getName).collect(Collectors.toList());
    trieTree = TreeManager.init(words, IGNORE_CHAR.toCharArray());
  }


  public boolean checkExist(String str) {
    return trieTree.isMatch(str, true);
  }

}

Aop切面检查参数, 配合SpringEL表达式处理

使用注解+aop来实现对参数的校验.

SpringEL表达式的话, 方便我们灵活的指定需要检查哪个参数的哪个字段. 具体用法的话就是用#作为前缀+变量名, 然后在解析表达式的时候, 把同名的变量绑定进去就可以了.

代码

注解

这个注解我们只要放在需要检查的参数上就可以了


import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

@Target({ ElementType.METHOD})
@Retention(RetentionPolicy.RUNTIME)
public @interface CheckBannedWord {

  /**
   * 需要检查的字段, 格式是El表达式. #{}包裹(可不写), 引用变量前加#. 比如 #user.id
   */
  String[] value() default {};

  /**需要检查的字段, 格式是El表达式. #{}包裹(可不写), 引用变量前加#. 比如 #user.id
   */
  String[] filedName() default {} ;





}

切面(解析EL表达式)

这里用到SpelExpressionParser来解析注解中的表达式


@Component
@Aspect
@Slf4j
public class CheckBannedWordAspect {

  @Autowired
  private BannedWordFilter bannedWordFilter;

  @Pointcut("@within(com.zgd.common.valid.CheckBannedWord)" +
          "|| @annotation(com.zgd.common.valid.CheckBannedWord)")
  public void pointcutException() {
    //
  }


  @Before("pointcutException()")
  public void doBefore(JoinPoint joinPoint) {
    MethodSignature methodSignature = (MethodSignature) joinPoint.getSignature();
    Method method = methodSignature.getMethod();
    if (!method.isAnnotationPresent(CheckBannedWord.class)){
      return;
    }
    CheckBannedWord annotation = method.getAnnotation(CheckBannedWord.class);
    String[] fields = annotation.value();
    if (fields ==null){
      fields = annotation.filedName();
    }
    if (fields ==null || fields.length==0){
      return;
    }
    //通过evaluationContext.setVariable可以在上下文中设定变量。
    EvaluationContext context = new StandardEvaluationContext();
    ExpressionParser paser = new SpelExpressionParser();//创建表达式解析器

    Object[] args = joinPoint.getArgs();
    Parameter[] params = ((MethodSignature) joinPoint.getSignature()).getMethod().getParameters();
    for (int i = 0; i < params.length; i++) {
      context.setVariable(params[i].getName(), args[i]);
    }
    for (String field : fields) {
      Expression expression = paser.parseExpression(field);
      String value = (String) expression.getValue(context);
      if (value !=null){
//        检查, 抛出异常,交给统一异常类处理
        Assert.required(!bannedWordFilter.checkExist(value), REQUEST_STR_HAS_BANNED_WORD_ERROR);
      }
    }


  }

}

示例Controller

  @PostMapping("/save")
  @ApiOperation("发布动态的评论")
  @CheckBannedWord("#req.message")
  public Response savePostReply(@Valid @RequestBody  PostReplySaveReq req) {
  // todo 业务代码
    }
0

评论区