乐虎游戏|乐虎国际登录|欢迎你

Python字符串匹配

日期:2020-02-06编辑作者:计算机资讯

看了阮一峰的字符串匹配的KMP算法,写得很好,推荐看看。不过我想自己写个例子描述一下这个算法,顺便写个PHP实现,于是有了这篇博文。

字符串查找和匹配是一个很常用的功能,比如在爬虫,邮件过滤,文本检索和处理方面经常用到。相对与C,python在字符串的查找方面有很多内置的库可以供我们使用,省去了很多代码工作量。但是我们还是需要了解一些常用的字符串查找算法的实现原理。

假设有两个字符串:t(目标串,长度n)和p(模式串,长度m),通常m<<n。

  • 字符串搜索算法字符串搜索算法(String searching algorithms)又称字符串比对算法(string matching algorithms)是一种搜索算法,是字符串算法中的一类,用以试图在一长字符串或文章中,找出其是否包含某一个或多个字符串,以及其位置。

  • 部分算法比较 [克努斯-莫里斯-普拉特算法即KMP算法]令 m 为模式的长度, n 为要搜索的字符串长度, k为字母表长度。

    图片 1image.png

首先来看python内置的查找方法。查找方法有find,index,rindex,rfind方法。这里只介绍下find方法。find方法返回的是子串出现的首位置。比如下面的这个,返回的是abc在str中的首位置也就是3。如果没找到将会返回-1

朴素串匹配算法

  • 优点
    简单易懂
  • 缺点
    效率低
    时间复杂度分析:最坏的情况是每一趟都在模式串的最后遇到不匹配,那么每一趟比较的次数是n-m+1, 总的比较次数是 mx(n-m+1), 因为m<<n, 所以时间复杂度为O(mxn)

代码实现:

def naive_match(t,p):
    m, n = len(p), len(t)
    i, j = 0, 0
    while i < m and j < n:
        if p[i] == t[j]:
            i, j = i+1, j+1
        else:    #字符不匹配,考虑t串的下一个位置
            i, j = 0, j-i+1 # j-i+1为相对位置加1
    if i == m:  # p串完全匹配后(i++)i的值变为m
        return j-i  #此时j的值减去p串的长度(i或者m)就是所在下标
    return 'No Match!' #无匹配则返回'No Match'
#实例化
t = ' abc  de'
p = 'de'
print naive_match(t, p)
#输出 6

#换一种想法去实现
def naive_match1(p,t):
    m, n, i = len(p), len(t), 0
    for i in range(n-m+1):
        if t[i:i+n-1] == p:
            return i
    return 'No match!'
p = 'abc'
t = 'abdabc'
print naive_match1(p,t)
3.1 例子

给定字符串:

RXYZAHXFXYZAXYZAXYZ

需要搜索的字符串是:

XYZAXY

朴素匹配的步骤很简单,先对比两个字符串的第一个字母,如果不一样,对比给定字符串的下一个字母,如果一样,那么对比两个字符串的第二个字母,以此类推。这种算法的缺点是效率低,因为做了很多无用工,比如,我在匹对 RXYZAHXFXYZAXYZAXYZ和XYZAXY字符串的时候,我在匹对给定字符串的XYZAH和要搜索的字符串XYZAXY这一步,前四个字母的已经匹对成功的,这四个字母是

XYZA

这个字符串的前缀和后缀

前缀:[X,XY,XYZ]后缀:[YZA,ZA,A]

没有共同的元素,这表示在这个长度内,不会有能和要搜索字符串的前缀匹配的部分,那么就可以直接跳过这一部分字符串的对比。这就是KMP算法的核心。所以,我们首先要对要搜索的字符串生成一个匹配表。

str = "dkjabcfkdfjkd198983abcdeefg"

KMP算法(无回溯串匹配算法)

分析:算法的关键在于构建一个跳转表(pnext表),当第i个字符匹配失败时不是重新从头开始匹配(例如朴素串匹配算法),而是通过构建好的跳转表跳转到第j个字符。例如:

0 1 2 3 4 5 6 7 # 字符串的位置
a b c a b c d a # p串
0 0 0 0 1 2 3 0 # pnext表,如果匹配不成功 跳转的位置

解释:当第6位的字符d匹配失败后可以直接跳转到第3位的a, 因为它们之前的abc是相同的,不需要再匹配一遍了。

更近一步分析:如果p串i位置与t串的j位置匹配失败了,先去查找p串i位置之前的从0开始的串(假设[0,k], k<i)与t串j位置之前的串([j-k,j])是否有相同的片段,如果有找出那个k值,若木有则按照朴素匹配算法进行。

移动的位数 = 已匹配的字符数 - 对应的部分匹配值(查表)

如何得到p串每个字符的部分匹配值(如何生成next表)?
对于每个p串的字符,前缀与后缀共有字符的个数就是该字符的部分匹配值。
详细解释

那么如何构造部分匹配表(next表)呢,python代码如下:

Next表 (部分匹配表,跳转表)
def partial_table(p):
    prefix = set() #集合
    postfix = set()
    ret = [0]  #存放p串匹配值,因为第一个字符的匹配值肯定为0,先把0存进去
    for i in range(1,len(p)): #从第二个字符开始
        #获取前i+1个字符串的前缀(例如对于abc,前缀有a,ab)
        #Note:切片[0:3]-->索引0,1,2(第一个索引是0可以省略-->[:3]-->取前三个数)
        #Note:range函数也一样取不到后面的数-->rang(1,3)-->>1,2
        prefix.add(p[:i]) #因为对于不同的字符前缀都有相同的部分,这里只需要添加就行了
        #获取前i+1个字符串的后缀(例如对于abc,后缀有bc,c)
        postfix = {p[j:i+1] for j in range(1,i+1)} #对于不同的字符后缀总是不一样
        ret.append(len(prefix&postfix))
    return ret

KMP算法实现

#-*-coding=utf-8-*-
#KMP
def kmp_match(t, p):
    m,n = len(t),len(p)
    cur = 0  #起始指针cur
    table = partial_table(p)
    while cur <= m-n: #最多做m-n趟匹配
        for i in range(n): #在每一趟比较中
            if s[i+cur]!=p[i]: #匹配不成功时
                cur += max(i - table[i-1], 1) #移动的位数 = 以匹配的字符数 - 匹配值
                break
        else:
            return True
    return False

# 测试
p = 'ABCDABD'
s = 'BBC ABCDAB ABCDABCDABDE'
print partial_table(p)
print kmp_match(s, p)
3.2 部分匹配表
  • ###### 如何给字符串生成一个匹配表?
XYZAXY - X 前缀和后缀都是空,所以共有元素的长度0;- XY 前缀[X],后缀[Y], 共有元素的长度0;- XYZ 前缀[X,XY],后缀[Y,YZ],共有元素的长度0;- XYZA 前缀[X,XY,XYZ],后缀[YZA,ZA,A],共有元素的长度0;- XYZAX 前缀[X,XY,XYZ,XYZA],后缀[YZAX,ZAX,AX,X],共有元素X的长度1;- XYZAXY 前缀[X,XY,XYZ,XYZA,XYZAX],后缀[YZAXY,ZAXY,AXY,XY,Y],共有元素XY的长度2;
  • ###### 因此生成的匹配表:

图片 2image.png

print str.find('abc')

3.3 匹配

好了,现在来看一下怎么使用上一步骤的表。首先,移位的计算公式:

移动位数 = 已匹配的字符数 - 对应的部分匹配值

下面看具体步骤:

  • 步骤1

    图片 3image.png

    匹配第一个字符,不一致,则将要搜索的字符串右移一位,直至到匹配第1位字母。

  • 步骤2

    图片 4image.png

    从第一个字符串的第一个X开始,已匹配是4位,查表最后一位匹配的字母对应的匹配值是0,所以右移4位。

  • 步骤3

    图片 5image.png

    移位后发现不匹配,又要继续右移一位,直至匹配第1位字母。

  • 步骤4

    图片 6image.png

    发现匹配了X之后,下一位右不匹配了,查表得到X对应的匹配值是0,1-0=1,再右移一位。

  • 步骤5

    图片 7image.png

    继续匹配,666,发现完全匹配,所以呀,就是找到了一个出现的地方。这时候,已匹配是6个,查表部分匹配值2,移动位数6-2=4.

  • 步骤6

    图片 8image.png

    又继续匹配,发现又发现一个。这时候移位位数是4,给定字符串已经没了,所以匹配终止。

但是在str中有2个abc,那么如何去查找到第二个abc的位置呢。由于find是会返回查找到的字符串的首位置,因此我们可以利用这个位置继续往后搜索。代码如下

3.4 结论

要搜索的字符串在给定字符串出现的次数是2次,如图:

图片 9image.png

def str_search_internal():

4. 伪代码[来自《算法导论》]
  • 预处理,生成部分匹配表
//注意:伪代码下标都是从1开始,这是《算法导论》约定俗成的COMPUTE-PREFIX-FUNCTIONm = P.lengthlet π[1...m] be a new arrayπ[1] = 0k = 0for q = 2 to m while k > 0 and P[k +1] != P[q] //这一步很巧妙,但是比较难理解,下面解释 k = π[k] if P[k + 1] == P[q] //对比上一个部分匹配值的下一个字母是否与当前字母一致 k = k + 1 π[q] = k //保存q对于的部分匹配值return π

下面解释上面伪代码COMPUTE-PREFIX-FUNCTION的关键步骤

while k > 0 and P[k +1] != P[q] k = π[k]

举个比较好理解的例子:

P = XYXYXZT假设当前运行到Z,则之前生成的 π为 π[1~5] = [0,0,1,2,3];此时 k = 3, q = 6, P[4] != P[6] 符合while循环的条件,进入循环。1.P[4]= P[6]:首先,在这里为什么要比较P[4] 和 P[6]?这是因为Z前面X对于的π[5] = 3,这说明P[1~3] = P[3~5],所以一旦P[4]= P[6],则立马可以进行下一步的k=k+1(这时if的判断结果肯定的true);2.如果P[4] != P[6]:这时候我们把注意力放在P[1~3],这时候我们求的是P[1~3]前缀和P[4~6]的后缀的公共元素。这时候我们获取P[3]的部分匹配值,π[3]=1,说明P[1] = P[3]。由上面的P[1~3] = P[3~5]知道,P[1] = P[3] = P[5],那么我们只需比较P[2] = P[6],无需从头匹配一遍P[1~3]=P[4~6],假设相等,这时候就有P[1~2] = P[5~6],对应的部分匹配值+1,但是,很不幸,这时候依然不等,所以继续循环。3. 结论:k = π[k]其实是利用了部分匹配值提供的信息减少比较次数。
  • 匹配
KMP-MATCHERn = T.lengthm = P.lengthπ = COMPUTE-PREFIX-FUNCTIONq = 0for i = 1 to n while q > 0 and P[q + 1] != T[i] //这一步和上面的那一步本质上意义是相同的 q = π[q] if P[q + 1] == T[i] q = q + 1 if q == m print "Pattern occurs with shift" i - m q = π[q]
  • 运行时间分析运行摊还分析的聚合方法进行分析,过程COMPUTE-PREFIX-FUNCTION的运行时间为Θ。唯一微妙的部分是while循环总共执行时间是O。下面将说明它至多进行了m-1次迭代。我们从观察k的值开始:1)初始值0,并且增加k的唯一方法是
if P[k + 1] == P[q] k = k + 1

这个在for循环每次迭代至多执行一次,因此,k总共增加m-1次;2) 在进行for循环时,k<q,并且在for循环体的每次迭代中,q的值都增加,所以k<q总成立。这意味着每次while循环迭代时k的值都递减;3)k永远不可能为负值。综上,k的递减来自于while循环,它由k在所有for循环迭代中的增长所限定,k总共下降m-1。因此,while循环最多迭代m-1次,并且COMPUTE-PREFIX-FUNCTION的运行时间为Θ。同样的方法分析可知KMP-MATCHER的时间复杂度是Θ。

    str = "dkjabcfkdfjkd198983abcdeefg"

5. PHP实现
<?phpclass Kmp { /** * 生成部分匹配表 * @param string $p * @return array */ public function ComputePrefix { $m = strlen; $table = []; $table[0] = 0; $k = 0; for($q = 1; $q < $m; $q++) { while ($k > 0 && $p[$k] != $p[$q]) $k = $table[$k]; if($p[$k] == $p[$q]) $k = $k + 1; $table[$q] = $k; } return $table; } /** * 匹配 * @param string $str * @param string $p */ public function Matcher { $n = strlen; $m = strlen; $table = $this->ComputePrefix; $q = 0; $match = []; for($i = 0; $i < $n; $i++) { while ($q > 0 && $p[$q] != $T[$i]) $q = $table[$q]; if($p[$q] == $T[$i]) $q = $q + 1; if { $match[] = ['begin' => $i - $m + 1, 'end' => $i]; $q = $table[$q - 1]; } } return $match; }}$kmp = new Kmp();$match = $kmp->Matcher('RXYZAHXFXYZAXYZAXYZ', 'XYZAXY');

运行结果:

图片 10image.png

即匹配结果有两个,分别是

$p[8] ~ $p[13]和$p[12] ~ $p[17]

    substr='abc'

    substr_len=len(substr)

    start=0

    while start <=len(str):

        index=str.find('abc',start)

        if index == -1:

            return -1

        else:

            print index

            begin=index+substr_len #每一次查找后就将开始查找的位置往后移动字串的长度

            if begin <= len(str):

                index=str.find('abc',begin)

                print index

            else:

                return -1

            start=index+substr_len

通过返回的index方式就可以不断的往下寻找后面匹配的字符串。

前面介绍了python内置的查找函数,那么如果我们不用这些内置的函数,自己如何编写查找函数呢。首先我们来看下朴素的串匹配应用。代码如下

def str_search():

    str = "dkjabcfkdfjkd198983abcdeefg"

    substr = 'abc'

    substr_len = len(substr)

    str_len=len(str)

    i,j=0,0

    while i < str_len and j < substr_len:  

        if str[i] ==  substr[j]: #如果匹配,则主串和子串的位置同时后移一位

            i+=1

            j+=1

        else:#如果不匹配,主串移动到当前查找位置的后一位

            i=i-j+1

            j=0

        if j == substr_len:  #如果j到了子串的最后一位,表明已经找到匹配的

            return i-j

    return -1

 

从代码量的角度来看,直接使用find方法要省事得多。那么从代码的运行时间来看,谁更快呢。来比较下代码的运行时间

start=time.time()

str = "dkjabcfkdfjkd198983abcdeefg"

print str.find('abc')

end=time.time()

print 'the time elapsed %f' % (end-start)

find方法使用的时间为0.000009

/usr/bin/python2.7 /home/zhf/py_prj/data_struct/chapter4.py

3

the time elapsed 0.000009

用朴素的匹配算法运行时间是0.000026,时间是find方法的3倍

start=time.time()

ret=str_search()

print ret

end=time.time()

print 'the time elapsed %f' % (end-start)

/usr/bin/python2.7 /home/zhf/py_prj/data_struct/chapter4.py

3

the time elapsed 0.000026

 

我们考虑更极端的场景,将主串str初始化为

"dkjueireijkab139u8khbbzkjdfjdiuhfhhionknl90089122jjkdnbdfdfdfddfd981298989dhfjdbfjdbfjdbfjbj" 

          "djkjdfkdjkfbkadfffffffffffffffffffffffffffffffffffjiiernkenknkdfndkfndkfbdhfkdfjkd198983abcdeefg"

长度更长且abc位于主串的偏后的位置。此时再来比较下两种方式的运行时间。

使用find方法的时间为0.000028

/usr/bin/python2.7 /home/zhf/py_prj/data_struct/chapter4.py

180

the time elapsed 0.000028

本文由乐虎游戏发布于计算机资讯,转载请注明出处:Python字符串匹配

关键词:

在SpringMVC和Mybatis中央银行使LocalData提姆e

!--LocalDateTime-- dependency groupIdcom.fasterxml.jackson.datatype/groupId artifactIdjackson-datatype-jsr310/artifactId version2.9.2/version /dependen...

详细>>

Nginx的特性-实现优点

轻量级 CPU亲和 超强的静态文件管理技艺 缘由风度翩翩:IO多路复用epoll [TOC] 成效模块少 什么是IO复用? 1.四项确认...

详细>>

程序员,是知识工作者,还是体力工作者?

看了标题,你们或许以为我要吐槽程序员了。其实,这只是我在看《卓有成效的管理者》时,萌发的一个想法。 在现...

详细>>

Oracle与MySQL字段类型对照

序号 ORACLE MYSQL 说明 1 VARCHAR2 VARCHAR 2 NUMBER INT MYSQL有很多整数类型:tinyint、smallint、mediumint、int、integer、bigint 3 NUMBE...

详细>>