精华内容
下载资源
问答
  • DFA即Deterministic Finite Automaton,翻译过来就是确定性有限...时间复杂度为小于等于O(n),n是被检索文本的长度。 2. DFA关键词过滤,是精准过滤,无法实现模糊过滤,如我是*人,*匹配单个字符,%匹配多个字符。

    一、前言

    有一个关键词库,此时需要检索一段文本中是否出现词库中的关键词,该如何实现?

    小白回答:将所有的关键词放入一个set集合,然后遍历集合一个个匹配那段文本,存在的关键词放入另一个集合。实现代码如下:

    public class Test131 {
        public static void main(String[] args) {
            Set<String> wordSet = new HashSet<String>();
            wordSet.add("产品经理");
            wordSet.add("产品总监");
            wordSet.add("程序员");
            String content= "产品经理工作内容包含需求收集,需求分析,需求落地,项目跟踪,项目上线,数据跟踪以及对业务人员进行培训,协助运营、销售、客服等开展工作。";
            Set<String> haveWordSet = new HashSet<String>();
            for (String word : wordSet) {
                if (content.contains(word)) {
                    haveWordSet.add(word);
                }
            }
            System.out.println(haveWordSet);
        }
    }
    // [产品经理]
    

    思路很简单,也很容易理解,但是当关键词有几千、几万个时,性能会急剧下降。分析一下时间复杂度,遍历关键词是O(n),从文字段落检索的时间复杂度也是O(n),合起来就是O(n^2)。

    有没有其他更优的解决方案呢?有!就是DFA算法!

    二、何为DFA算法

    DFA即Deterministic Finite Automaton,翻译过来就是确定性有限自动机。简单原理就是:在一个有限的集合,其中的元素都有两种状态,结束和继续(可以用0代表继续,1代表结束),可以从一个元素检索到下一个元素,直到元素的状态为结束为止。

    dfa

    三、DFA算法优化关键词过滤

    套用DFA算法的原理,例如有一些关键词:产品经理、产品总监、程序员,构建DFA算法容器如下:

    java-dfa

    看着像一棵棵树,现在判断一个词是否在词库中,比如测试员,检索是否有”测“字开头的“树”,很快就能判断没有测试员这个词,比如检索“产品经理”,则可以找到”产“字开头的“树”,直接排除了“程序员”那棵“树”,这就大大缩小了范围。

    算一下时间复杂度,从词库中匹配关键词,时间复杂度是O(1),遍历文字段落依然和文字的个数有关,时间复杂度最差(如果文本没有一个关键词)为O(n),合起来就是小于等于O(n)。使用DFA实现关键词过滤的优化点在于:检索的时间复杂度不会因为关键词数量的增加而受影响,只与被检索的文字长度有关。

    四、java代码实现

    分析数据结构,每一个字符都要存一个状态,可以用map实现,如果状态未结束还要存下一个字符的指针,也可以用map实现,这样就是map套map。如下:一个大map里有两个key,程和产,value值又是map套map。

    {={isEnd=0,={isEnd=0,={isEnd=1}
           }
        },={isEnd=0,={isEnd=0,={isEnd=0,={isEnd=1}
              },={isEnd=0,={isEnd=1}
              }
           }
        } 
    }
    

    完整代码示例:

    public class Test131 {
        public static void main(String[] args) {
            String content= "产品经理工作内容包含需求收集,需求分析,需求落地,项目跟踪,项目上线,数据跟踪以及对业务人员进行培训,协助运营、销售、客服等开展工作。";
            Set<String> wordSet = new HashSet<String>();
            wordSet.add("产品经理");
            wordSet.add("产品总监");
            wordSet.add("程序员");
            init(wordSet);
            System.out.println("wordMap=" + m_kwWordMap);
            Set<String> haveWords = getWord(content, MIN_MATCH_TYPE);
            System.out.println("haveWords=" + haveWords);
    
        }
    
        /**
         * 初始化DFA关键词容器
         * @param words
         */
        @SuppressWarnings({ "rawtypes", "unchecked" })
        public static void init(Set<String> words) {
            // 预先 设置初始容量,以免扩容影响性能。
            Map wordMap = new HashMap(words.size());
            for (String word : words) {
                Map nowMap = wordMap;
                for (int i = 0; i < word.length(); i++) {
                    // 转换成char型
                    char keyChar = word.charAt(i);
                    // 判断是否已经有一个map树,只有在一个词的首字符有用
                    Object tempMap = nowMap.get(keyChar);
                    if (tempMap != null) {
                        // 存在,则共享一个map树根
                        nowMap = (Map) tempMap;
                    }
                    // 不存在则构建一个map树,
                    else {
                        // 设置状态位
                        Map<String, String> newMap = new HashMap<String, String>();
                        // 判断是设置 0还是1
                        newMap.put("isEnd", i == word.length() - 1 ? "1" : "0");
                        // 给keyChar该字符设置状态位
                        nowMap.put(keyChar, newMap);
                        // 将状态位map赋值给nowMap,表示下一个字符的指针和状态位在同一个map里。
                        nowMap = newMap;
                    }
                }
            }
            // 上面始终修改的是nowMap,最后形成的是wordMap,原因是,预先wordMap赋值给了nowMap,
            // 使得wordMap和nowMap中的map地址值共享,更新了nowMap中的map就是更新了wordMap。
            m_kwWordMap = wordMap;
        }
    
        /**
         * 检索关键词
         * @param txt 被检索的文本
         * @param beginIndex  被检索文本的开始位置
         * @param matchType 匹配类型
         * @return 返回检索到的关键词长度,用于从文本中截取
         */
        public static int checkWord(String txt, int beginIndex, int matchType) {
            // 匹配标识数默认为0
            Map nowMap = m_kwWordMap;
            int matchFlag = 0;
            int matchMaxFlag = 0;
            for (int i = beginIndex; i < txt.length(); i++) {
                char word = txt.charAt(i);
                // 获取指定key
                nowMap = (Map) nowMap.get(word);
                // 存在,则判断是否为最后一个
                if (nowMap != null) {
                    // 找到相应key,匹配标识+1
                    matchFlag++;
                    // 如果为最后一个匹配规则,结束循环,返回匹配标识数
                    if ("1".equals(nowMap.get("isEnd"))) {
                        // 将matchFlag赋值给matchMaxFlag,为的是,
                        // 后面要是继续按最大匹配原则匹配时,匹配不到则按最小匹配原则的结果为准。
                        matchMaxFlag = matchFlag;
                        // 最小规则,直接返回,最大规则还需继续查找
                        if (MIN_MATCH_TYPE == matchType) {
                            break;
                        }
                    }
                }
                // 不存在,直接返回
                else {
                    break;
                }
            }
            return matchMaxFlag;
        }
    
        /**
         * 从文本中检索出关键词
         * @param txt 被检索的文本
         * @param matchType 匹配类型
         * @return
         */
        public static Set<String> getWord(String txt, int matchType) {
            Set<String> set = new HashSet<String>();
            for (int i = 0; i < txt.length(); i++) {
                // 判断是否包含关键词,length > 0 有,且是关键词长度
                int length = checkWord(txt, i, matchType);
                // 存在,加入set中
                if (length > 0) {
                    // 从原文中截取 并放入set
                    set.add(txt.substring(i, i + length));
                    // 减1的原因,因为for会自增
                    i = i + length - 1;
                }
            }
            return set;
        }
    
        private static Map m_kwWordMap = null;
        // 最小匹配原则,如果关键词中有中国和中国人,文本内容为“我是中国人”,最小匹配原则匹配出中国
        public static final int MIN_MATCH_TYPE = 1;
        // 最大匹配原则,如果关键词中有中国和中国人,文本内容为“我是中国人”,最大匹配原则匹配出中国人
        public static final int MAX_MATCH_TYPE = 2;
    }
    
    // wordMap={程={isEnd=0, 序={员={isEnd=1}, isEnd=0}}, 产={品={总={监={isEnd=1},      isEnd=0}, isEnd=0, 经={理={isEnd=1}, isEnd=0}}, isEnd=0}}
    // haveWords=[产品经理]
    

    五、总结

    1. DFA算法利用map套map的原理,极大程度上优化了检索性能,时间复杂度为小于等于O(n),n是被检索文本的长度。
    2. DFA实现的关键词过滤,性能不再受限于关键词的数量,只与被检索的文本长度有关。
    3. DFA关键词过滤,是精准过滤,无法实现模糊过滤,如我是*人*匹配单个字符,%匹配多个字符。

    参考:https://www.cnblogs.com/twoheads/p/11349541.html 需要注意该文章中checkWord函数最大匹配原则时是有bug的,本人的示例已加matchMaxFlag更正。

    PS: 如若文章中有错误理解,欢迎批评指正,同时非常期待你的评论、点赞和收藏。我是徐同学,愿与你共同进步!

    展开全文
  • 实验表明,MFA构造时间比XFA略少,比DFA、STT冗余压缩算法和Hybrid-FA降低了2~3个数量级;存储空间比XFA略高,比DFA、STT冗余压缩算法、mDFA、Hybrid-FA降低了1~2个数量级;匹配时间DFA、Hybrid-FA略多,但是比...
  • DFA角度理解KMP算法

    千次阅读 2015-05-03 17:18:22
    KMP 算法KMP(Knuth-Morris-Pratt)算法在字符串查找中是很高效的一种算法,假设文本字符串长度为n,模式字符串长度为m,则时间复杂度为O(m+n),最坏情况下能提供线性时间运行时间保证。《算法导论》和其他地方在...

    KMP 算法

    KMP(Knuth-Morris-Pratt)算法在字符串查找中是很高效的一种算法,假设文本字符串长度为n,模式字符串长度为m,则时间复杂度为O(m+n),最坏情况下能提供线性时间运行时间保证。

    《算法导论》和其他地方在讲解KMP算法的时候,过于数学化且晦涩难懂,我也因此迷惑了很长时间。后来看《算法(第四版)》部分的讲解,对其中最复杂的Next数组有了重新的认识。我这里也希望用通俗的语言来将我的理解分享出来。

    KMP算法的本质是构造一个DFA确定性有限状态自动机),然后通过自动机对输入的字符串进行处理,每接收一个字符,就能转移到一个新的状态,如果自动机能够达到特定的状态,那么就能够匹配字符串,否则就匹配失败。

    先来了解一下DFA。
    自动机分为两种:DFA和NFA(非确定性有限状态自动机),都可以用来匹配字符串。很多正则表达式引擎使用的就是NFA。

    如果有过FPGA开发经验,就会很清楚,自动机与硬件描述语言中常见的状态机类似。状态机是一种流程控制的模型。一个自动机包含多个状态,状态之间可以有条件的进行转移。这个条件就是输入。

    根据输入的不同,一个状态可以转移到另一个状态,或者保持当前状态。自动机可以使用下面的状态转移图来表示。

    这里写图片描述

    上图中State0为初始状态,如果输入为input0,就继续保持State0状态,直到输入input1,状态才转移到State1,其他状态类似。

    下面我再来讲KMP算法。

    朴素的字符串查找算法使用的是暴力搜索,过程大概是这样的:
    假设要处理的文本字符串为s,要在其中查找字符串p(也称为模式字符串)。
    先将s与p的首字符对齐,然后一个字符一个字符的对比,如果到某个字符不一样,就将p字符串右移一位,然后s与p的字符指针回退到新的对齐的位置,重新开始对比。
    借用《算法(第四版)》中的代码如下,这里的i和j分别用来跟踪文本与模式字符串,i表示已经匹配过的字符序列的末端:

    public static int search(String pat,String txt){
        int j,M = pat.length();
        int i,N = txt.length();
        for (i = 0, j = 0; i < N && j < M; i++){
            if (txt.charAt(i) == pat.charAt(j)){
                j++;
            }
            else{
                i -= j;//go back
                j = 0;
            }
        }
        if (j == M){
            return i - M;//match
        }
        else {
            return N;//not match
        }
    }

    朴素查找算法在查找的时候,其实文本字符串的某些字符在前面就已经能获取相关的信息了,但是因为算法的局限,为了不漏掉中间能够匹配的字符,下一次回退的时候,又重新匹配了一次或多次,这样浪费了一定的时间。

    相比朴素的查找算法,KMP的优势在于,基本流程是一致的,不需要进行不必要的回退操作。它是用一个dfa数组(有地方叫做Next数组)来指示匹配失败的时候下一步j应该放到哪,也就是对齐的位置,这个位置不一定是朴素查找算法中的右移的一位,可能是多位,效率更高。

    所以代码变成了下面的:

    public static int search(String pat,String txt){
        int j,M = pat.length();
        int i,N = txt.length();
        for (i = 0, j = 0; i < N && j < M; i++){
            if (txt.charAt(i) == pat.charAt(j)){
                j++;
            }
            else{
                j = dfa[txt.charAt(i)][j];//use an array dfa[][]
            }
        }
        if (j == M){
            return i - M;//match
        }
        else {
            return N;//not match
        }
    }

    代码和前面的朴素查找基本一样。

    关键是这个dfa[][]数组怎么计算,这也是弄懂KMP的关键所在。

    其实这个dfa[][]数组,就是DFA自动机的一个简单的模型。txt.charAt(i)就是输入,j作为状态。

    举个例子:模式为ABABAC
    该例子构造的DFA的状态转移图如下:

    这里写图片描述

    可以看到,最初在状态0,然后每次输入新的字符,都会转移到新的状态或者保持旧状态。
    dfa[][]数组对的每一列都对应一个状态,每一行都对应一种输入。

    怎么去构造一个模式对应的DFA呢?
    这个过程是一个迭代的过程。
    代码如下:

    dfa[pat.charAt(0)][0] = 1;
    for (int X = 0, j = 1; j < M; j++)
    { 
        // Compute dfa[][j].
        for (int c = 0; c < R; c++)
            dfa[c][j] = dfa[c][X];
        dfa[pat.charAt(j)][j] = j+1;
    
        X = dfa[pat.charAt(j)][X];
    }

    以上代码是:
    对于每个j,
    匹配失败的时候,dfa[][X]复制到dfa[][j];
    匹配成功的时候,dfa[pat.charAt(j)][j]设置为j+1;
    更新X。

    为什么这么做呢?
    因为状态要向后面转移,必须是接收了与模式匹配的正确的字符,每次这个字符有且只有一种情况,这个字符是pat.charAt(j)。其他的字符只能使状态保持或者状态回退。

    状态回退也就是让DFA重置到适当的状态,就好像回退过指针一样,但是我们不想回退指针,我们已经有了足够的信息来计算这个重启的位置。

    试想一下,如果真的回退指针,我们需要重新扫描文本字符,并且这些字符就是pat.charAt(1)到pat.charAt(j-1)之间的字符(因为前面都是匹配的),忽略首字母是因为需要右移一位,忽略最后一个字符是因为上次匹配失败。
    重新扫描对比过的文本字符串,直到我们的能够找到一个最长的以pat.charAt(j-1)结尾的子串,能作为模式字符串p的前缀,然后将模式字符串与这个子串的位置对齐,然后重新开始字符对比。

    但是实际上,我们不需要回退指针,因为刚才的扫描过程,也是一个状态转移的过程,相当于是一个子问题。
    我们把pat.charAt(1)到pat.charAt(j-1)之间的字符,一个一个输入当前的得到的DFA(因为只需要处理j-1个字符,所以当前DFA已经足够处理,相当于扫描的时候,只用模式的前一部分),到pat.charAt(j-1)的时候,会停留在一个状态,这个状态就是下一个j的状态。
    这个过程利用了已经建立好的DFA的信息,进行迭代,得到新的DFA的信息,所以可以这样把整个DFA都建立起来。

    模式ABABAC的DFA建立过程如下图:
    这里写图片描述
    这里写图片描述
    这里写图片描述
    这里写图片描述
    这里写图片描述
    这里写图片描述

    这其中还有一个问题就是怎么确定复制的位置X,也就是重启的状态。
    其实也很简单,就是pat.charAt(1)到pat.charAt(j-1)之间的字符能达到的最后一个状态。由于在计算DFA的过程,也是pat模式串迭代的过程,所以,在j-1的时候,我们可以把最后一个字符输入pat.chatAt(j-1)输入到当前的DFA,得到新的状态,保存起来下次继续在该状态基础上转移即可,边构造边使用。也是就是下面这行代码:

    X = dfa[pat.charAt(j)][X];

    到这里,KMP算法原理基本就清楚了。

    《算法(第四版)》最后提到:

    在实际应用中,它比暴力算法的优势并不十分明显,因为极少有应用程序需要在重复性很高的文本中查找重复性很高的模式。但该方法的一个优点是不需要再输入中回退。这使得KMP字符串查找算法更适合在长度不确定的输入流(例如标准输入)中查找进行查找,需要回退的算法在这种情况下则需要复杂的缓冲机制。

    因为KMP基于DFA自动机,所以会有这样的优点,说到这里,硬件中之所以经常采用状态机进行编程,也是因为状态机不需要缓冲机制的原因,这便于高效地对输入流进行处理,比如通信中对以太网帧的解析,从MAC进来的比特流,可以很方便地通过计数等方法进行状态识别和转移,不需要接收完整个帧再进行处理,减少了缓存的消耗。

    参考书目:

    • 《大话数据结构》
    • 《算法导论》
    • 《算法(第四版)》
    展开全文
  • (一)KMP算法DFA解法

    千次阅读 2017-03-19 23:54:40
    简单说一下,KMP是一个时间复杂度O(n+m)的字符串匹配算法,网上也有很多其他的解法,比如next数组的解法,推荐看这里匹配的思路DFA:确定有限自动状态机 以下是ABABAC的对应的DFA: 1.假设文本为txt,待匹配的...

    简单说一下,KMP是一个时间复杂度O(n+m)的字符串匹配算法,网上也有很多其他的解法,比如next数组的解法,推荐看这里

    匹配的思路

    DFA:确定有限自动状态机
    以下是ABABAC的对应的DFA:
    这里写图片描述

    1.假设文本为txt,待匹配的子串为pat。
    
    2.未匹配是状态0,此时如果条件A(匹配到了txt的字符‘A‘),会到状态1,如果是条件B、C或其他的条件,还是状态0。如果经历了匹配ABABA之后到达状态5,再匹配C到达状态6,即停止状态,也就是匹配成功。
    
    3.很明显,dfa[][]是一个二维数组,dfa['A'][3]就是在状态3时,下一个条件是A时,要跳转到哪一个状态。
    
    4.匹配的过程就是:不断的用txt的字符 + 当时的状态去dfa取值,直到状态6 or txt匹配到最后一个字符,结束。
    
    5.匹配过程中,txt的字符是一个一个往后取,不会回溯,只是状态一直在变化,即本次使用的是上一次匹配后的状态,不会回溯,正是KMP算法相对于暴力解法的优势。
    

    DFA数组的构建

    上边的思路如果理解了,那么剩下的问题就是如何构建dfa[][],当然这也是难点。dfa[][]的元素分为两类:1,匹配成功;2,匹配失败。

    1.匹配成功
    初始可确定的状态为:
    dfa[pat[0]][0] = 1;
    即在状态0匹配到子串的第一个字符,到达状态1;
    dfa[pat[1]][1] = dfa[pat[0]][0] + 1

    2.匹配失败
    初始的第一列,即状态0时,匹配失败应该还是状态0,也就是除上述dfa[pat[0]][0] = 1外,其他都为状态0。
    那么状态j时,匹配失败:(模拟回溯)
    假设此时匹配到c = txt[i],然后查找dfa找到跳转到哪个状态,那么txt[i-j…i-1]这部分与pat[0…j-1]这部分是匹配的。因为i-j为起始而整体不匹配,所以pat要右移一位,所以txt[i-j]舍弃了,不用比较了,也就是在状态j遇到条件c的要跳转的状态,txt[i-j+1 … i-1] == pat[1 … j-1]。
    引入一个状态指示数组X,X[j]是指正确输入p[1…j-1]后进入的状态,输入p[1…j-1]c后进入的状态就是dfa[c][X[j]](在X[j]状态时输入c),即dfa[c][j]=dfa[c][x[j]]。
    X[j+1]为正确输入p[1…j]后进入的状态,即正确输入p[1…j-1]p[j]后进入的状态,也就是在X[j]状态时输入p[j]时进入的状态,就是dfa[pat.charAt[j]][X[j]],即递推公式为:X[j+1]=dfa[pat.charAt[j]][X[j]],而X[0]手动初始化为0。
    故有:

    dfa[pat[0]][0] = 1;
        int X = 0;
        for (j = 1; j < M; ++j){
            for(i = 0; i < R; ++i) {
                dfa[i][j] = dfa[i][X];
            }
            dfa[pat[j]][j] = j + 1; //匹配成功
            X = dfa[pat[j]][X]; //更新重启状态
        }

    附所有代码:

    int test_jp_search() {
        int index = jp_search("BCBAABACAABABACAA", "ABABAC");
        printf("%d\n", index);
        return 0;
    }
    
    int jp_search(char *txt, char *sub)
    {
        int M = (int)strlen(sub);
        int R = 256;
        //二维数组定义并初始化
        int dfa[R][M];
        int i = 0, j = 0;
        for (i = 0; i < R; ++i) {
            for (int j = 0; j < M; ++j) {
                dfa[i][j] = 0;
            }
        }
    
        dfa[sub[0]][0] = 1;
        int X = 0;
        for (j = 1; j < M; ++j){
            for(i = 0; i < R; ++i) {
                dfa[i][j] = dfa[i][X];
            }
            dfa[sub[j]][j] = j + 1; //匹配成功
            X = dfa[sub[j]][X]; //更新重启状态
        }
    
    
        int N = (int)strlen(txt);
        for (i = 0, j = 0; i < N && j < M; ++i){
            j = dfa[txt[i]][j];
        }
    
        if (j == M) {
            return i - M;
        } else {
            return M;
        }
    }

    ps:感觉还是有点乱,回头再整理一下思路

    参考:
    1.《算法》第四版
    2.链接

    展开全文
  • KMP算法 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。...KMP算法时间复杂度O(m+n)。1 说明 文章...

    KMP算法

    KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

    文章正式开始之前

    做如下说明
    表格模板

    1. PAT: 模式串,如 ABAACA也就是想要查找的结果。
    2. CharAt: 这里ABC是指当前用来匹配Pat的字符,比如这里有一串文本ABABABC。就是在ABC这三个字符构成的文本串里面寻找内容,取3个字母是为了精简说明过程。
    3. 状态(M): 当前匹配的状态。
    4. 前一个状态(X): 记录如果失败了应该 保留 到哪些步骤之前。
    5. dp: 构建的状态转移数组,即表格内容。

    解释

    整体的流程图

    取自《算法(第4版)》图5.3.6

    构建一个状态表,当在某个状态时,遇到了某个字符下一步应该转移到什么状态
    取自算法第四版
    j=0这个位置成功匹配到A,说明可以前往(Next)状态1

    CharAt A✔️ Next
    Pat A✔️ B A B A C
    J 0 1 2 3 4 5

    j=1这个位置成功匹配到B,说明可以前往(Next)状态2

    CharAt A✔️ B✔️ Next
    Pat A✔️ B✔️ A B A C
    J 0 1 2 3 4 5

    那么在 j=1这个位置与A不匹配(B才能成功),说明可以前往状态1

    CharAt A✔️ A❌
    Pat A✔️ B❌ A B A C
    J 0 1 2 3 4 5

    此时保留Pat的第一位A可以与CharAt的第二位A匹配,继续匹配下一个位置的字符串不需要回退在CharAt上的文本指针。

    CharAt A A✔️ Next
    Pat A✔️ B A B A C
    J 0 1 2 3 4 5

    如何构建这个转移过程

    我们将以 ABAACA来构建这个过程。

    正确转移到最后一个状态,即已经匹配成功

    ABAACA构建一个最简单的状态转移图片,它的意思是:
    状态0匹配到字符A转移到状态1,在状态1匹配到字符B转移到状态2
    直到在状态4匹配到字符C转移到状态5则获取结果成功。这是一条目前最容易定义的转移方式。
    成功转移

    圆圈内的数子代表当前状态

    那么为什么这么定义呢?

    1. 可以看到如想要到达状态2,必须已经满足状态1又成功匹配了B字符。
    2. 那么当想要到达状态6,必须已经满足状态5又成功匹配了A字符,也就是当前已经成功匹配了Pat(ABAACA)
    3. 后面的每一层状态都是由之前状态决定,所以可以从前往后计算下一步应该转移成什么状态,符合 动态规划 的过程。
    转移过程的代码

    构建转移表的过程

    for 0 <= j < M: // 状态由模式串决定
        for 0 <= c < 256: // 也可以是更大的包括中文等
            dp[j][c] = next //下一步应该前往什么状态
    

    识别过程

    int M = 0//当前初始状态
    int P = pat.length();//模式串的长度,也就是总共具有多少状态,[0...P]一共是P+1个状态
    int T = txt.length()//计算文本的长度
    for (int i = 0; i < T; i++) {
    	M = dp[M][txt.charAt(i)];//当前状态在遇到某个字符应该转移到哪里
    	if (M == P) {//当到P这个状态的时候已经满足条件,返回成功的位置
    		return i - M + 1;
    	}
    }
    
    匹配成功转移表

    匹配成功转移表

    1. 状态0匹配到第一个字符A,此时模式串与字符匹配表示可以前往状态1
    2. 状态1匹配到第二个字符B,此时模式串与字符匹配表示可以前往状态2
    3. 状态2匹配到第三个字符A,此时模式串与字符匹配表示可以前往状态3
    4. 状态3匹配到第四个字符A,此时模式串与字符匹配表示可以前往状态4
    5. 状态4匹配到第五个字符C,此时模式串与字符匹配表示可以前往状态5
    6. 状态5匹配到第六个字符A,此时模式串与字符匹配表示可以前往状态6
    7. 状态6已经满足结果,无需在匹配。
    匹配成功代码
    for 0 <= j < M:
        for 0 <= c < 256:
            if c == pat[j]: //在某个状态匹配时,前往下一个状态
                dp[j][c] = j + 1 //匹配成功
            else: 
            	?????  //匹配失败
    
    初始化不匹配的问题

    但是现实往往没有那么刚好,可能在起步的时候就跌倒了。
    那么如果第一个遇到的是非A的其它字符呢,它们显然是无法进行下去的。
    状态转移表

    初始化匹配成功代码的BaseCase(基础情况)
    dp[0] = new int[M][C]//M个状态,每个状态可以有C个字符,默认都是0
    dp[0][pat.charAt(0]) = 1 //base case dp[0]["A"] = 1
    for (int i = 1; i < M; i++) {//第一列只有遇到’A‘是1,其它是0所以跳过第一列
    	for (int j = 0; j < C; j++) {
    		if (pat.charAt(i) == j) {
    			dp[i][j] = i + 1;//匹配成功
    		} else {
    			//??? //匹配失败
    		}
    	}
    }
    
    匹配错误的跳转过程

    在这里插入图片描述
    假设之前的状态X=0,当前状态M=1
    即: (M=0M=0 转移 M=1M=1) 等同 (M=X=0M=X=0 转移 M=1M=1
    在这里插入图片描述

    图1.6

    我们从 X=0X=0 状态转移到 M=1M=1,那么M=1M=1的前一个状态就是X=0X=0 这个位置(前一个状态X状态M其实是一个类似快慢指针的模式)。

    X代表在前一个状态,也就是当状态在X的时候,已经匹配成功多少个字符了。
    M代表后一个状态,也就是当状态在M的时候,已经匹配成功多少个字符了。

    如下当A匹配完之后,B也匹配成功了。很自然的想到往Next的位置继续匹配对吧,但是这里有个很重要的点。

    CharAt A✔️ B✔️ Next
    Pat A✔️ B✔️ A B A C
    J 0 1 2 3 4 5

    也就是之前的状态X已经保留了N个字符,那么它在遇到B应该保留多少个Pat的字符呢(到某个状态)?

    X = dp[X][pat.charAt(i)]//在状态X匹配到B,切换下一个位置。
    

    此时 X=dp[0][B]=0X= dp[0][B] = 0

    AB匹配完毕

    1. 此时 M=2、X=0
    2. 在遇到下一个字符A之前已经知道可以保留到状态X,那么如何回退到X,只要将X这一列的状态拷贝给当前状态M
      状态拷贝
    dp[M][j] = this.dfa[X][j]//将X所在的状态拷贝一份到M=2不能匹配的位置
    

    那么失败则使用最长可以保留的Pat再继续往下匹配。

    dp[0] = new int[M][C]//M个状态,每个状态可以有C个字符,默认都是0
    dp[0][pat.charAt(0]) = 1 //base case dp[0]["A"] = 1
    int X = 0
    for (int i = 1; i < M; i++) {//第一列只有遇到’A‘是1,其它是0所以跳过第一列
    	for (int j = 0; j < C; j++) {
    		if (pat.charAt(i) == j) {
    			dp[i][j] = i + 1;//匹配成功
    		} else {
    			dp[i][j] = dp[X][j] //将X所在的状态拷贝一份到M=i不能匹配的位置
    		}
    	}
    	X = dp[X][pat.charAt(i)] //更新X的下一个状态
    }
    

    在这基础上自己构建一张完整图表

    x
    x
    x
    x
    x
    x
    x

    构建完毕

    构建完毕

    完整代码

    public class KMP {
    	private String pat;
    	private int[][] dfa;//存放状态表
    
    	public static void main(String[] args) {
    		KMP kmp = new KMP("abaaca");
    		int search = kmp.search("");
    		System.out.println(search);
    	}
    
    	public KMP(String pat) {
    		this.pat = pat;
    		int M = pat.length();
    		int R = 256;
    		this.dfa = new int[M][R];
    		this.dfa[0][pat.charAt(0)] = 1;
    		int X = 0;
    		for (int i = 1; i < M; i++) {
    			for (int j = 0; j < R; j++) {
    				if (pat.charAt(i) == j) {
    					this.dfa[i][j] = i + 1;
    				} else {
    					this.dfa[i][j] = this.dfa[X][j];
    				}
    			}
    			X = this.dfa[X][pat.charAt(i)];
    		}
    
    	}
    
    	public int search(String txt) {
    		int M = 0;
    		for (int i = 0; i < txt.length(); i++) {
    			M = this.dfa[M][txt.charAt(i)];
    			if (M == this.pat.length()) {
    				return i - M + 1;
    			}
    		}
    		return -1;
    	}
    }
    

    结尾

    1.博客地址
    2.源代码仓库

    如果你在代码里看到了用 数字标记的注释 如 //1.xxx 这是我写代码的顺序,希望能给你一点启发。


    😁😁😁制作动画过程不易,请大家顺手点赞收藏咯 谢谢~😁😁😁
    有其它题目不理解的也可以一起学习,如有错误欢迎指出~
    展开全文
  • 自动机的一些算法和应用

    千次阅读 2012-08-31 19:37:48
    几个月前实现了一个自动相关的算法,在一个比较乐观的测试中,将一个2.3G的url集合压缩到了27M,同时,key查找的时间复杂度是O(strlen(key))。当然,还有其它一些自动机相关的算法的优化实现,比如Aho-Corasick多模...
  • C语言 KMP算法

    2018-06-18 02:26:22
    时间复杂度O(m+n)。 KMP算法通过确定有限状态自动机DFA实现。 实现过程 字符串ABABAC的DFA: 通过DFA搜索字符串BCBAABACAABABACAA: 代码实现 #include &lt;stdio.h&gt; #include &lt;m...
  • #21. DFA

    2017-02-05 19:21:59
    首先,观察题目可知,该题...时间复杂度O(kn^2),k为未知常数,听说很小。然后施大说正解就是这样的。顿时无语到不想鏼这题。 然后考试后的汪大就默默地想出了一个n(logn)^2的算法,怒艹标算!然后我就烧四五个小
  • Trie图 先看一个问题:给一个很长很长的母串 长度为...显然时间复杂度会很高。。。 再改进一些,用kmp让每一模式串与母串进行匹配呢?时间复杂度为O((n + len(m))*m),还算可以。 可是还有没有更快的算法呢? 编...
  • 原谅我的画图工具很low~~,好了贴代码,由二维数组作为DFA,每个元素的值为下一个状态的编号,查询的时间复杂度为O(n),远低于普通算法的O(n^2);/*main.cpp 用词法分析器搜索单词在文中出现次数 By 李自乐 */ #...
  • 文章目录一、暴力破解二、显式回退三、KMP 算法3.1、确定有限状态自动机(DFA)3.2、构造 DFA ...时间复杂度和两个串的长度有关 O(m*n) public static int bruteForce(String pattern, String text) { int p
  • 前面的那个算法是n的平方复杂度,虽然这个复杂度计算都是建立在一些操作为单位时间操作的基础上。可是这些被认为的单位时间操作在我的实现中却有着平方复杂度,情何以堪,万恶的理论计算机科学家。 hopcroft实现的...
  • 在深入分析DFA状态数对算法性能影响的基础上,提出了构造最优DFA状态数的算法,该算法保证在任意有限的系统资源下具有最小的时间复杂度和空间复杂度,并且将报文匹配方式和One-Pass扫描算法相结合进行测试。...
  • 后缀自动机总结

    2015-05-21 21:35:00
    后缀自动机是一种确定性有限自动机(DFA),它可以且仅可以匹配一个给定串的任意后缀。 构造一个可以接受一个给定串...于是,人们就开始研究这种特殊的NFA,并提出了在线增量算法,用O(n)的时间复杂度构造该NFA的D...
  • java正则式简介(2)

    2010-12-26 20:19:26
    正则式解析算法 ...• DFA (确定的有穷自动机):时间复杂度O(nlogn) ,n是DFA的状态数。速度明显比NFA要高。 • 避免使用类似(a|b)*a(a|b)(a|b)…(a|b),包含了n-1个 (a|b)的正则表达式。为什么? ...
  • 聊天系统违禁词过滤

    2010-01-11 23:48:00
    本文描述了一种简单的基于DFA算法用于过滤聊天内容中的违禁词,算法的运行复杂度,遍历 输入字符串n,最多对每个字符执行一次二分查找lgn,所以最坏情况下也是O(nlgn). 因为编写这段代码的时间很短,所以代码写得...
  • 10.1.3时间复杂度 10.1.4最小不动点 10.1.5静态活跃性与动态活跃性 10.1.6 冲突图 10.2 Tiger编译器的活跃分析 10.2.1 图 10.2.2控制流图 10.2.3活跃分析 程序设计:构造流图 程序设计:活跃分析模块 ...
  • 现代编译原理C语言描述-虎书中文版

    热门讨论 2010-04-11 16:47:52
    10.1.3 时间复杂度 158 10.1.4 最小不动点 159 10.1.5 静态活跃性与动态活跃性 160 10.1.6 冲突图 161 10.2 Tiger编译器的活跃分析 162 10.2.1 图 162 10.2.2 控制流图 163 10.2.3 活跃分析 164 ...
  • 10.1.3 时间复杂度 158 10.1.4 最小不动点 159 10.1.5 静态活跃性与动态活跃性 160 10.1.6 冲突图 161 10.2 Tiger编译器的活跃分析 162 10.2.1 图 162 10.2.2 控制流图 163 10.2.3 活跃分析 164 程序设计:构造流图 ...

空空如也

空空如也

1 2
收藏数 23
精华内容 9
热门标签
关键字:

dfa算法时间复杂度