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

字符串相似度匹配算法_java逻辑表达式解析本章描述了如何构造一个用于字符串匹配的有限状态自动机,依赖该自动机,可以在O(n)的时间复杂度内,判断文本T是否包含字符串P

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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}, 由于最后状态机处于非接收状态,因此这个字符串被状态机拒绝。

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

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

输入 a b c
状态0 1 0 0
状态1 1 2 0
状态2 3 0 0
状态3 1 4 0
状态4 5 0 0
状态5 1 4 6
状态6 7 0 0
状态7 1 2 0

利用上面的状态机,依次读入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] 是字符串 Pq 的后缀,该调用有两层循环,所以复杂度是O( m2 ), makeJumpTable有两层循环,循环次数为O(m*| |), 所以makeJumpTable总的时间复杂度为O( m3 | |), 也就是说,构建跳转表的复杂度是:O( m3 | |)。

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

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/171700.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • pycharm怎么设置注释颜色_pycharm调颜色

    pycharm怎么设置注释颜色_pycharm调颜色”””代码块注释”””单行注释颜色设置Preferences–>Editor–>CorlorScheme–>Python–LineComment多行注释颜色设置: 1)修改函数内部代码块说明颜色Preferences–>Editor–>CorlorScheme–>Python–Docstring–>Text2)修改多行注释颜色Preferences–>…

  • 煤矿云计算大数据_构建物联网

    煤矿云计算大数据_构建物联网传统工业实时历史数据库与时序数据库的区别?本文介绍了实时数据库和时序数据库,并就其特点、应用场景、相关厂商、联系与区别做介绍。实时历史数据库![实时历史数据库架构.png](https://img-blog.csdnimg.cn/img_convert/ddd8d3b24107ac2ebf328f3fd390c603.png#clientId=ud49e0880-2e25-4&crop=0&crop=0&crop=1&crop=1&from=drop&i

  • 章节1:SQL语言简易入门

    章节1:SQL语言简易入门

  • Algorithms 普林斯顿算法课程笔记(一)

    Algorithms 普林斯顿算法课程笔记(一)本节将从动态连接性算法(并查集问题的模型)入手,引入算法分析和设计的整体思路和优化方法,为整个课程的引子部分。主要内容包括QuickFind和Quickunion算法,以及这些算法的改进。动态连接性对于连接做如下定义:自反:p连接于自身 对称:若p连接于q,则q连接于p 传递:若p连接q,q连接r那么p连接r我们的算法需要满足上述关于连接的定义。另外,引出了另一个概念…

  • python 之免费ip代理池[通俗易懂]

    python 之免费ip代理池[通俗易懂]基于proxy_pool,部署了一个开放的免费ip代理池,提供出来供大家使用。数据有效性每2分钟更新一次。地址:http://proxy.linuxdba.ltd/all/开源项目地址:https://github.com/jhao104/proxy_pool

  • Oracle监听器Server端与Client端配置实例

    Oracle监听器Server端与Client端配置实例

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号