字符串相似度匹配算法_java逻辑表达式解析

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

阅读博客的朋友可以参看视频：
如何进入google,算法面试技能全面提升指南

什么叫有限状态自动机

先看一个图：

上面这个图描述的就叫一个有限状态自动机，图中两个圆圈，也叫节点，用于表示状态，从图中可以看成，它有两个状态，分别叫0和1. 从每个节点出发，都会有若干条边，当处于某个状态时，如果输入的字符跟该节点出发的某条边的内容一样，那么就会引起状态的转换。例如，如果当前状态处于0，输入是字符a,那么状态机就会从状态0进入状态1.如果当前状态是1，输入字符是b或a,那么，状态机就会从状态1进入状态0.如果当前所处的状态，没有出去的边可以应对输入的字符，那么状态机便会进入到错误状态。例如，如果当前处于状态0，输入字符是c,那么状态机就会出错，因为从状态0开始，没有哪条边对应的字符是c.

状态机会有一个初始节点，和一个接收节点，以上图为例，我们可以设置初始节点为0，接收节点为1，当进行一系列的输入，使得状态机的状态不断变化，只要最后一个输入使得状态机处于接收节点，那么就表明当前输入可以被状态机接收。例如对应字符串”abaaa”, 从初始节点0开始，状态机根据该字符串的输入所形成的状态变化序列为：{0，1，0，1，0，1}。由于最后状态机处于状态1，所以该字符串可以被状态机接收。如果输入的字符串是:abbaa, 那么状态机的变化序列为：{0，1，0，0，1，0}， 由于最后状态机处于非接收状态，因此这个字符串被状态机拒绝。

在程序中，我们一般使用二维表来表示一个状态机，例如上面的状态机用二维表来表示如下：

通过查表，我们便可知道状态机的转换，例如处于状态0，输入字符是a时，我们从表中得到的数值是1，也就是说处于状态0，输入是字符a,那么状态机将转入状态节点1.

一个文本匹配流程的描述

接下来我们看看一个文本的匹配流程，假定要查找的字符串为P=”ababaca”, 被查找的文本为T=”abababacaba”. 一次读入T的一个字符，用S表示当前读入的T的字符，一开始读入一个字符，于是S=a.然后看看，从P开始，连续几个字符所构成的字符串可以成为S的后缀，由于当前S只有一个字符a,于是从P开始，连续1个字符所形成的字符串”a”,可以作为S的后缀。把这个字符串的长度记为k,于是此时k 等于1. 继续从T中读入字符，于是S=”ab”, 此时，从P开始，连续两个字符所构成的字符串”ab”可以作为S的后缀，于是k = 2.反复这么操作，于是便有以下序列：

1. S=a, k = 1, P[1] 是S的后缀
2. S=ab, k = 2, P[1,2] 是S的后缀
3. S=aba, k = 3, P[1,2,3]是S的后缀
4. S=abab, k= 4, P[1,2,3,4]是S的后缀
5. S=ababa, k = 5, P[1,2,3,4,5]是S的后缀
6. S=ababab, k = 4, P[1,2,3,4]是S的后缀
7. S=abababa, k = 5, P[1,2,3,4,5]是S的后缀
8. S=abababac, k = 6, P[1,2,3,4,5,6]是S的后缀
9. S=abababaca, k = 7, P[1,2,3,4,5,6,7]是S的后缀
10. S=abababacab, k =2, P[1,2] 是S的后缀
11. S=abababacaba, k = 3, P[1,2,3] 是S的后缀。

注意看第9步，P的长度是7，整个字符串P成为了字符串S的后缀，而此时的S是文本T的前缀，这不就表明文本T含有字符串P了吗。在每一个步骤中，我们都需要从P的第一个字符开始，看看最多能连续读取几个字符，使得他们能成为S的后缀，假设P的字符个数为m, 那么这个读取过程最多需要读取m个字符，于是复杂度为O(m). 如果有某种办法，使得我们一次就可以知道从P开始，连续读取几个字符就可以构成S 的后缀，假设文本T含有n个字符，那么我们就可以在O(n)的时间内判断，T是否含有字符串P.因为上面的步骤最多可以执行n次。

于是当前问题变成，构造一个方法，使得一次运行便能知道从P开始，连续读取几个字符能使，得这几个字符构成的字符串是S的后缀。这个方法，就需要上面我们提到的有限状态自动机。

用于字符串匹配的自动机

假定字符串P和文本T只由a,b两个字符组成，也就是字符集为$\sum$={a,b,c}, P含有m个字母，于是，我们要构造的自动机就含有m个状态节点。假设我们当前处于状态节点q, 那么当下一个输入字符是a和b时，从当前节点q该跳转到哪一个节点呢？ 如果用$P_q$来表示长度为q的P的前缀，以q=4, p=”ababaca”, $P_q$=”abab”, 那么当处于状态4, 当输入为a时，我们构造字符串 S = $P_q$ + ‘a’ = “ababa”, 然后看看字符串P从第一个字符开始，连续几个字符所构成的字符串可以成为S的后缀，就当前S为例，从第一个字符开始，连续5个字符，也就是P[1,2,3,4,5]可以作为S的后缀，于是，我们就有，当状态机处于节点4，输入为a时，跳转的下个状态就是5. 同理，当处于状态q=4,输入为字符b时，S = $P_q$ + ‘b’ = “ababb”,此时从P开始，连续读取0个字符才能形成S的后缀，于是当状态机处于状态4，如果读入字符是b, 那么跳转的下一个状态是0，同理，如果输入字符是c, 那么S = $P_q$ + ‘c’ = “ababc”, 此时从P开始，连续读取0个字符所形成的空字符串才能作为S的后缀，于是当状态机处于状态节点4，输入字符为c时，跳转到节点0. 如果q从0开始，一直到m,反复运用刚才提到的步骤，便会产生下面这个跳转表：

利用上面的状态机，依次读入T的字符，如果状态机跳转到状态q,那就表明从P的第一个字符开始，连续读取q个字符，所形成的字符串可以构成是S的后缀，也就是说，当我们的状态机跳转到状态7时，我们就可以得知文本T,包含字符串P.

我们走一遍这个过程，首先状态机处于状态0，读入T[0]=a, S= a, 查表可知进入状态1，读入T[1]=b, S=ab, 查表可知，进入状态2，读入T[2]=a,查表可知进入状态3，读入T[3]=b, S=abab,查表可知进入状态4，读入T[4]=a,S=ababa,查表可知进入状态5，读入T[5]=b,S=ababab,查表可知进入状态4，读入T[6]=a, S=abababa,查表可知进入状态5，读入T[7]=c,S=abababac,查表可知进入状态6，读入T[8]=a,S=abababaca,查表可知进入状态7，此时，我们可以得出结论，文本T包含有字符串P.

代码实现

import java.util.HashMap;


public class StringAutomaton { 
   
   private HashMap<Integer, HashMap<Character, Integer>> jumpTable = new HashMap<Integer, HashMap<Character, Integer>>();
   String P = "";
   private final int alphaSize = 3;
   public StringAutomaton(String p) {
       this.P = p;
       makeJumpTable();
   }

   private void makeJumpTable() {
       int m = P.length();
       for (int q = 0; q <= m; q++) {
           for (int k = 0; k < alphaSize; k++) {

               char c = (char)('a' + k);
               String Pq = P.substring(0, q) + c;


               int nextState = findSuffix(Pq);
               System.out.println("from state " + q + " receive input char " + c + " jump to state " + nextState);
               HashMap<Character, Integer> map = jumpTable.get(q);
               if (map == null) {
                   map = new HashMap<Character, Integer>();
               }

               map.put(c, nextState);
               jumpTable.put(q, map);
           }
       }
   }

   private int findSuffix(String Pq) {
       int suffixLen = 0;
       int k = 0;

       while(k < Pq.length() && k < P.length()) {
           int i = 0;
           for (i = 0; i <= k; i++) {
               if (Pq.charAt(Pq.length() - 1 - k + i) != P.charAt(i)) {
                   break;
               }
           }

           if (i - 1 == k) {
              suffixLen = k+1;
           } 

           k++;
       }

       return suffixLen;
   }

   public int match(String T) {
       Integer q = 0;
       System.out.println("Begin matching...");

       for (int n = 0; n <= T.length(); n++) {
           HashMap<Character, Integer> map = jumpTable.get(q);
           int oldState = q;
           q = map.get(T.charAt(n));
           if (q == null) {
               return -1;
           }

           System.out.println("In state " + oldState + " receive input " + T.charAt(n) + " jump to state " + q);

           if (q == P.length()) {
               return q;
           }
       }

       return -1;
   }
}

代码中，makeJumpTable调用用来构建跳转表，findSuffix用来查找最大的数值K, 使得P[1…k] 是字符串$P_q$的后缀，该调用有两层循环，所以复杂度是O($m^2$), makeJumpTable有两层循环，循环次数为O(m*|$\sum$|), 所以makeJumpTable总的时间复杂度为O($m^3$|$\sum$|), 也就是说，构建跳转表的复杂度是：O($m^3$|$\sum$|)。

match依靠跳转表来判断，输入的字符串T是否包含字符串P,如果T的最后一个字符输入状态机后，从跳转表得到的状态的值等于P的长度m,那么表明T包含字符串P.具体的程序调试过程请参看视频。

我们只给出了算法的实现流程，算法的数学原理比较复杂，我们将在下一节详解。