本文主要介绍了一些主流的解析器是怎么实现like的语法逻辑，接着作者分析了几种实现方式的优劣，最终采用状态机的方式，针对场景一步一步进行性能优化。

作者 | 陶侃(灵葙)

来源 | 阿里开发者公众号

提及

最近在优化项目的like语法，那既然谈到了SQL，我们不妨来看看一些主流的解析器是怎么实现like的语法逻辑。这里需要提一下主流的两种SQL解析器，它们分别是ANTLR和Calcite。

ANTLR是一款功能强大的语法分析器生成器，可以用来读取、处理、执行和转换结构化文本或者二进制文件。在大数据的一些SQL框架里面有广泛的应用，比如Hive的词法文件是ANTLR3写的，Presto词法文件也是ANTLR4实现的。但是ANTLR并不会直接实现具体的语法，因此没办法找到实现语句。

Calcite简化了ANTLR生成代码的过程，它提供了标准的 SQL 语言、多种查询优化和连接各种数据源的能力，同时Calcite 有着良好的可插拔的架构设计，可以让用户很方便的给自己的系统套上一个SQL的外壳，并且提供足够高效的查询性能优化，因此也获得了不少开发者的青睐。这里附上找到的Calcite对于like逻辑匹配的实现。

/** SQL {@code LIKE} function. */
public static boolean like(String s,String pattern){
    final String regex = Like.sqlToRegexLike(pattern, null);
   return Pattern.matches(regex, s);
}

/** Translates a SQL LIKE pattern to Java regex pattern.*/
static String sqlToRegexLike(String sqlPattern,char escapeChar) {
    int i;
    final int len = sqlPattern.length();
    final StringBuilder javaPattern = new StringBuilder(len + len);
    for (i = 0; i < len; i++) {
      char c = sqlPattern.charAt(i);
      if (JAVA_REGEX_SPECIALS.indexOf(c) >= 0) {
        javaPattern.append('\\');
      }
      if (c == escapeChar) {
        if (i == (sqlPattern.length() - 1)) {
          throw invalidEscapeSequence(sqlPattern, i);
        }
        char nextChar = sqlPattern.charAt(i + 1);
        if ((nextChar == '_')
            || (nextChar == '%')
            || (nextChar == escapeChar)) {
          javaPattern.append(nextChar);
          i++;
        } else {
          throw invalidEscapeSequence(sqlPattern, i);
        }
      } else if (c == '_') {
        javaPattern.append('.');
      } else if (c == '%') {
        javaPattern.append("(?s:.*)");
      } else {
        javaPattern.append(c);
      }
    }
    return javaPattern.toString();
}

还有一些别的编译器或者中间件，比如TDDL，附上我找到的实现方式，我们简单看下其实现方式，整体差不多，就是buildPattern的逻辑不太相同。

...
try {
    Pattern pattern = patterns.get(buildKey(right, escTmp), new Callable<Pattern>() {
        @Override
        public Pattern call() throws Exception {
            return Pattern.compile(buildPattern(right, escTmp), Pattern.CASE_INSENSITIVE);
        }
    });
    Matcher m = pattern.matcher(left);
    return m.matches() ? 1l : 0l;
} catch (ExecutionException e) {
    throw new FunctionException(e.getCause());
}
...

到此，综上来看，不少项目是基于正则表达式来完成的，接下来我整理了下我最近实现的几种方式：

正则表达式实现

Java的正则表达式与SQL的"like"具有不同的语法。最重要的就是必须转义Java视为特殊字符的任何字符，简单处理了下regexParse函数里面就是对于特殊符号的遍历替换操作([](){}.*+?$^|#\)等。

public static boolean like(final String dest, final String pattern) {
    String regex = regexParse(pattern);
    regex = regex.replace("_",".").replace("%",".*?");
    Pattern p = Pattern.compile(regex,Pattern.CASE_INSENSITIVE | Pattern.DOTALL);
    return p.matcher(dest).matches();
}

这种方式在代码层面简单明了，但是性能非常差，多次replace的使用就已经进行了多次遍历，这里有个可以优化的点，对于单个字符做替换可以选择用replaceChars(str, searchChar, replaceChar)这个方案。

Java 语言使用的正则表达式执行引擎是 NFA (Non-deterministic finite automaton) 非确定型有穷自动机，这种引擎的特点是：功能很强大，但存在回溯机制导致执行效率慢（回溯严重时可以导致机器 CPU 使用率 100%，直接卡死机器），正则里对于Pattern的处理相关的优化也是可以做的，将编译后的Pattern对象缓存下来，避免反复编译Pattern（对于每一个pattern-exprstr需要缓存一个Pattern），尽量选择懒惰模式和独占模式，避免使用贪婪模式（默认）。

这里说的三种模式分别是：贪婪模式、懒惰模式、独占模式

贪婪模式

数量表示符默认采用贪婪模式，除非另有表示。贪婪模式的表达式会一直匹配下去，直到无法匹配为止。如果发现表达式匹配的结果与预期的不符合，很有可能是因为咱们以为表达式只会匹配前面几个字符，实际确会不停匹配。

懒惰模式

与贪婪模式相反，懒惰模式会尽量匹配更少的内容，如上面对于百分号的处理。

独占模式

独占模式应该算是贪婪模式的一种变种，它同样会尽量匹配更多的内容，区别在于在匹配失败的情况下不会触发回溯机制，而是继续向后判断，所以该模式效率最佳。

简单算法实现

有什么比裸写一个定制版的like更好呢，简单易用，对于内存和性能几乎到了最优的地步，最复杂的情况是O(n*m)，有点类似于做一道算法题一样，纯一个match过程，不需要前置的缓存处理，下面用的双指针的方法实现，也可以考虑动态规划去做。(一部分的代码隐藏了)。

public static boolean like(final String dest, final String pattern) {
    int destPointer = 0, patternPointer = 0;
    int destRecall = -1, patternRecall = -1;
    final int patternLen = pattern.length();
    final int destLen = dest.length();
    while( destPointer < destLen) {
        ......
        ......
    }
    while(patternPointer < patternLen && pattern.chatAt(patternPointer) == '%') {
        patternPointer++;
    }
    return patternPointer == patternLen;
}

有个场景我们不得不去考虑，那就是回溯的情况，举个例子

对于pattern = "a%bcd" 同时匹配 abcde和 abcdbcdbcd这两种情况是无法一样的，用这种方式就需要记录回溯标记（后面我会讲一种方法不需要用到回溯）

如果说这是最省内存的方法的话，确实只用到了内部的几个变量就完成了全部的工作，硬要说缺点的话，就是可维护性太差了，逻辑处理之间藕断丝连，将来如果针对语法做一些扩展，那将会是一个比较棘手的改动。

有限状态机实现

状态机有 3 个组成部分：状态、事件、动作。

状态：所有可能存在的状态。包括当前状态和条件满足后要迁移的状态。

事件：也称为转移条件，当一个条件被满足，将会触发一个动作，或者执行一次状态的迁移。

动作：条件满足后执行的动作。动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状态。动作不是必需的，当条件满足后，也可以不执行任何动作，直接迁移到新状态。

一般使用涉及到穷举法、查表法、状态模式

穷举法

状态机最简单的实现方式，利用if-else或者switch-case，参照状态转移图，将每一种状态转移直接翻译成代码。对于简单的状态机，分支逻辑法的实现方式可以接受。对于复杂的状态机，缺点是容易漏写、错写某些状态转移。除此之外，代码中充斥着大量的if-else，可读性、可维护性都很差。

查表法

查表法适用于实现状态、事件类型很多、状态转移比较复杂的状态机，利用二维数组表示状态转移表，能极大的提高代码的可读性和可维护性。在二维数组的表示形式中，用数组transitionTable和actionTable分别表示状态转移和动作执行。在这两个数组中，横坐标都表示当前状态，纵坐标都表示发生的事件，值则分别表示转移后的新状态和需要执行的动作。

查表法这里引用一个入门举例

比如有个pattern为"SCSAS"的字符串，那我们尝试梳理一下这个字符串对应的状态转移表,"!"表示与"S","C","A"无关的字符，下面为有限状态机状态转换表

下图为pattern为 "SCSAS" 的有限状态机状态转换图

接下来就是match的过程，拿到dest字符串，按照表中的状态数据依次匹配字符就好了，直到找到State = 5的值。

状态模式

状态模式通常是表达实现状态不多、状态转移简单，但是事件触发动作所包含的业务逻辑比较复杂的状态机。将不同状态下事件所触发的状态转移和动作执行，拆分到不同的状态类中，来避免分支判断逻辑。

剩余60%，完整内容请点击下方链接查看：

https://mp.weixin.qq.com/s?__biz=MzIzOTU0NTQ0MA==&mid=2247532574&idx=1&sn=3416f2e7aae20bc4bf864916847828f9&chksm=e92a7d11de5df40710c22fbc984e15c242ad2f102e8a815239407afec6cdd65029cec73cd27e&token=1900710254&lang=zh_CN#rd

版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。