ahocorasick文本匹配算法

文本匹配算法

最近一直在搞数据血缘相关的功能，对于纯粹的sql的代码其实是不需要搞得这么麻烦。但是后面由于是需要拉通下游应用，包括下游的magicapi，和帆软报表标本之类的。但是下面这些的代码呢，是无法通过druid或者别的sql代码来进行解析的。因为这些脚本本身就不是正常sql代码。因此还是得回到文本匹配上面的。
当然传统的匹配算法可以简单的使用String.contains()算法，但是这个本质上就是简单的字符串暴力匹配，像我数据库底表本身有3000多张，如果每一个脚本都要这样进行循环匹配的话，时间效率将会非常低。
因此在这里我们引入了ahocorasick算法。

ahocorasick 算法

ahocorasick本质上是一种构建自动机的算法。具体可以参考这个文章https://developer.aliyun.com/article/1504093 但是今天其实并不像太多的讲述算法的底层原理。这里主要解释一下在java环境下具体要怎么用。

pom

ahocorasick本质是一种思想，因此没有一个很官方的方法。在这里引用这个包

    <dependency>
      <groupId>org.ahocorasick</groupId>
      <artifactId>ahocorasick</artifactId>
      <version>0.6.3</version>
    </dependency>

在正式代码为：

package org.example.utils;
import org.ahocorasick.trie.Trie;
import org.ahocorasick.trie.Emit;

import java.nio.file.*;
import java.util.*;

import static org.example.utils.RegexMapUtils.containsAnyWord;

public class ComplexStringMap {
    public static Set<String> getTableNames(String script,List<String> mapping) {
        Trie trie = Trie.builder().ignoreCase().addKeywords(mapping).build();

        Collection<Emit> emits = trie.parseText(script);
        Set<String> foundTables = new HashSet<>();
        for (Emit emit : emits) {
            foundTables.add(emit.getKeyword());
        }
        Set<String> resultSet=new HashSet<>();
        StringBuffer buffer=new StringBuffer();
        buffer.append("\\b(");
        for (String tableName : foundTables){
            buffer.append(tableName);
            buffer.append("|");
        }
        buffer.deleteCharAt(buffer.length()-1);
        buffer.append(")\\b");
        String pattern=buffer.toString();
        Set<String> tables=containsAnyWord(pattern,script);
        return tables;
    }

}

其中参数1是需要匹配文本，参数2是目标匹配文本。然后，文本中的foundTables就是匹配命中的字符串。我这边由于要继续其他操作，因此进行了其他的操作。
实际上测试，这个算法确实是非常快的。