導讀
本文主要介紹了一些主流的解析器是怎麼實作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的值。
狀态模式
狀态模式通常是表達實作狀态不多、狀态轉移簡單，但是事件觸發動作所包含的業務邏輯比較複雜的狀态機。将不同狀态下事件所觸發的狀态轉移和動作執行，拆分到不同的狀态類中，來避免分支判斷邏輯。
和查表法相比，當狀态模式會引入較多的狀态類，對于狀态比較多的推薦使用查表法；而對于狀态比較少，但是動作複雜的，狀态模式更加适合。
那麼like的實作基于狀态模式的方式會更友善。動手前我們需要做個簡單的分析。假如測試的語句是 'CBEED' like '%B%E%D%'，顯而易見這個結果肯定是為true的，那麼我們怎麼實作這麼個狀态機呢？
具體的拆解可以分為兩個部分，狀态機的建構和運作比對。
public void compile(final String pattern) {
...
LikeStateMachine machine = LikeStateMachine.build(pattern);
...
} 建構的過程就是我們把pattern解析加載的過程，我采用的方式是建構連結清單的方式。實作就是周遊建構的過程，compile時間複雜度O(n)
接下來就是match字元串'CBEED'過程了，代碼的實作就是周遊比對過程，match時間複雜度O(n*m))
那麼最終的比對結果可以是圖1，也可以是圖2，這取決于比對的邏輯是倒序優先的還是正序優先的
圖1
圖2
這裡的難度的在于比對的可能性不是唯一的，同時并不是每個百分号符号對應的字元是同一個。比如下面這個case
是以我在做matcher狀态設計的時候就定義了5種狀态類型，最終幫助我實作了整體的邏輯。上面這種方式在實作的時候也需要考慮到回溯的情況，JUMP就是專門為回溯設計的。
是以整體下來由狀态機相關的類一共需要定義5個，足以完成我們的功能以及足夠的擴充性。
（LikeStateMachine）---狀态機
（LikeStateMatcher）---狀态機比對器 （LikeState）---狀态機節點
（LikeStateStatus）---狀态機節點狀态 （LikeStateWord）---狀态機比對詞
回溯場景優化
我在想怎麼能夠優化掉這種可逆的場景，因為回溯的存在讓整個邏輯變得複雜，是以我的目标就是讓複雜的邏輯表達更簡單一點，我嘗試在編譯的階段處理更多的事情，以便于比對的時候能擷取更好的性能。相比之前的case，我對pattern資料進行了類似split的操作，将非百分号的部分用字元串的形式進行了表達，效果出乎意料的好。舉個例子，'%BF%EA%D'，下面是它的優化過程。
我對幾種場景進行了場景類型定義：%a = TYPE:LEFT a% = TYPE:RIGHT %a% = TYPE:SURROUND
任何帶有'%'的pattern都可以被解析成這三種類型，同時我們的狀态機節點個數被優化掉了不少。基于這樣的實作方式後，回溯邏輯就變得不複存在了，通過目前節點和下個節點的聯合校驗就能識别，最終能做到O(n) ，同時對于一些場景，可以通過類型+長度判斷就能識别，無需繼續周遊。讓我們在看下之前回溯的case，pattern = "a%bcd" 同時比對 abcde和 abcdbcdbcd，對于這種RIGHT+LEFT的場景做下特殊處理就行。
常用場景優化
到目前為止那麼是不是還能做進一步的優化呢？其實還可以基于常用的場景再次進一步的優化，我嘗試把這些場景羅列出來，
'ab' like 'abc','ab' like 'abc%','ab' like '%abc','ab' like '%abc%'
可能超過80%的使用場景莫過于上面這些正常運用了，這個時候我想又可以在編譯的時候識别到這樣的場景了并且做進一步的優化了。
'ab' like 'abc' ----> equals("abc")
'ab' like 'abc%' (或者類似'abc%%','abc%%%' 以n個'%'結尾)----> startsWith("abc")
'ab' like '%abc' (或者類似'%%abc','%%%abc' 以n個'%'開始)----> endsWith("abc")
'ab' like '%abc%'(或者類似'%%abc%%', 被n個'%'圍繞前後)----> contains("abc")
'ab' like '%'(或者類似'%%', n個'%')----> true
盡量使用jdk底層的能力去做這樣的事，在長度檢驗等判斷上就可能不需要再周遊了。
public LikeParserResult compile(final String pattern) {
return parseLikeExpress(pattern);
}
....
public boolean match(final String dest, LikeParserResult likeParserResult) {
switch (likeParserResult.getMatchResult()) {
case LikeMatchResult.TYPE.ALLMATCH:
return true;
case LikeMatchResult.TYPE.EQUALS:
return doEquals(dest, likeParserResult.getFinalPattern());
case LikeMatchResult.TYPE.STARTSWITH:
return doStartsWith(dest, likeParserResult.getFinalPattern());
case LikeMatchResult.TYPE.ENDSWITH:
return doEndsWith(dest, likeParserResult.getFinalPattern());
case LikeMatchResult.TYPE.CONTAINS:
return doContain(dest, likeParserResult.getFinalPattern());
default:
//或者别的實作
return likeParserResult.getLikeStateMachine().match(dest);
}
} 上面給出的代碼是為了清楚的看到裡面運作，最終根據自己擅長的代碼風格（函數式Function，接口等），還可以進一步優化和精簡。
...
public LikeParserResult compile(final String pattern) {
return parseLikeExpress(pattern);
}
public boolean match(final String dest, LikeParserResult likeParserResult) {
return likeParserResult.getMatcher().match(dest);
}
...
public class StartsWithMatcher implements Matcher {
...
@Override
public Boolean match(String dest) {
return dest.startsWith(this.pattern);
}
}
... 壓測資料對比
| 算法/運作1億次avgms/業務場景 | 短-精确比對 pattern = "halo", dest = "halo"; | 短-隻存在百分号 pattern = "%", dest = "hello"; | 短-右比對 pattern = "he%", dest = "hello!"; | 短-左比對pattern = "%go", dest ="let's go"; | 短-雙向比對pattern = "%wo%", dest ="world"; | 短-右左比對 pattern = "he%lo", dest ="hello"; | 短-雙左比對 pattern = "%he%lo", dest ="hello"; |
| 狀态機(提前編譯) | 11 | 7 | 181 | 321 | 492 | 1198 | 1477 |
| 雙指針算法 | 740 | 780 | 1277 | 1710 | 1133 | 1768 | 2152 |
| 長-精确比對 pattern ="this is hello world! let's go!", dest = "this is hello world! let's go!"; | 長-隻存在百分号 pattern = "%%%%%", dest = "this is hello world! let's go!"; | 長-右比對pattern = "hello%", dest = "hello world! let's to!"; | 長-左比對pattern = "%go", dest ="this is hello world! let's go"; | 長-雙向比對pattern = "%wo%", dest ="hello world! let's go!"; | 長-右左比對 pattern = "he%go", dest ="hello world, let's go"; | 長-雙左比對pattern = "%lo%go", dest ="hello world, let's go"; | |
| 狀态機(提前編譯) | 10 | 5 | 228 | 356 | 524 | 1182 | 1966 |
| 雙指針算法 | 2063 | 1984 | 2433 | 3775 | 3073 | 3294 | 4569 |
| 短-右雙比對 pattern = "he%lo%", dest ="hello!"; | 長-右雙比對pattern = "he%ld%", dest ="hello world, let's go"; | 短-多雙向比對 pattern = "%wo%ld%",dest ="world"; | 長-多雙向比對 pattern = "%wo%et%", dest ="this is hello world! let's go!"; | 短-回溯 pattern = "%he%rld", dest ="helloworld world"; | 長-回溯 pattern = "%he%rld", dest ="this is hello world world world"; | ||
| 狀态機(提前編譯) | 1366 | 1382 | 1345 | 3433 | 1749 | 2063 | |
| 雙指針算法 | 2187 | 4402 | 2072 | 4755 | 4986 | 8650 |
上面是根據典型的場景設計的測試用例，大體上的資料結論來看是字元串越長于通用算法來說就會是越來越慢的，狀态機在絕大多數情況下的表現會優于通用算法，相當少數情況性能差不多。
最後
按照多個優缺點綜合評估的話，個人感覺狀态機實作 > 直接實作 > 正規表達式實作，狀态機和正則的編譯過程可以放到代碼編譯階段或者初始化的時候去做，能夠避免頻繁的性能損耗，對于擴充性和可維護性上來看，更傾向于基于狀态機來實作like的文法。
作者:陶侃(靈葙)
來源:微信公衆号:阿裡開發者
出處:https://mp.weixin.qq.com/s/jOyj71wWfukcObTYw_gdPg