From: http://hi.baidu.com/absolute8511/blog/item/b576e1c8df5235107e3e6ffc.html
字符串搜索或匹配是经常用到的技术,因此也发展了多个算法,介绍几个著名的算法。
1.单模式匹配
就是在一些文本中查找某一个子字符串的算法,效率较高的有以下几种。
KMP算法:全称Knuth-Morris-Pratt算法 预处理时间Θ(m) 匹配搜索时间 Θ(n)
BM算法:全称Boyer-Moore string search algorithm 预处理时间Θ(m + |Σ|) 匹配搜索时间Ω(n/m), O(n)
2. 有限模式集合匹配
就是在字符串中查找多个子字符串的算法,常用于查找字典中的单词和一些脏字匹配算法
Aho-Corasick算法:这是一种字典匹配算法,它用于在输入文本中查找字典中的字符串。时间复杂度是线性的。
基本原理:该算法利用类似后缀树的方法构造一个trie结构,匹配时利用该结构来搜索。
Commentz-Walter 算法:详细未知
Rabin-Karp string search算法:该算法最差复杂度不好,因此运用的并不广泛。
以上资料来源于维基百科,感兴趣的可以搜索维基百科词条String searching algorithm以获取更多信息。
=============================
字符串多模匹配算法之AC自动机理解心得
absolute8511 总结于 2009-2-26
AC自动机算法全称Aho-Corasick算法,是一种字符串多模式匹配算法。用于在一段文本中查找多个模式字符串。最近看到这个算法的一些文章,由于理解能力有限,琢磨了许久才有一些眉目,故记下此时的理解过程,防止过久了又要琢磨许久才能理解,也希望能帮助其他人加深理解,如有理解不当之处还望指出修正。^_^
总结如下:
该算法有两个主要步骤,一个是字典树的构造,一个是搜索路径的确定。
1. 字典树的构造
这个比较好理解,就是把要匹配的一些字符串添加到树结构中去,树边就是单词中的字符,单词中最后一个字符的连接节点添加标志,以表示改节点路径包含1个字典中的字符串,搜索到此节点就表示找到了字典中的某个单词,可以直接输出。
例子:某字典P={he,she,his,hers}对应的字典树如下图:
图中有数字的节点到根节点的路劲正好对应字典中的字符串,数字表述单词在字典中的顺序,也可以是其他标志。
【转载请注明出处:http://hi.baidu.com/absolute8511/blog/item/73ffcbf293d86e14b17ec5e9.html】
2. 搜索路径的确定
就是这部分我琢磨了很久,我的理解是 利用后缀字符串来确定。后缀字符串就是某个字符串的后面的一部分。比如abcde的后缀字符串有bcde,cde,de和e。
假定目标字符串为ushers,字典为上图所示。
搜索过程目标字符串指针指向的字符和字典中的字符会有以下几种情况:
a. 当前字符匹配,表示从当前节点沿着树边有一条路径可以到达目标字符,此时只需沿该路径走向下一个节点继续匹配即可,目标字符串指针移向下个字符继续匹配;
如:当指针指到s处,此时字典树指针处于根,要从根到s处,可以看到图中有一条从根经s连接到的节点,因此字典树节点指针指向此节点,目标字符串指针移动到下一字符h继续匹配;显然当前节点有一条经h连接到的节点,于是重复操作到有数字标志的节点2处,表示已找到,该匹配字符串就是"she",输出该字符串的位置后,目标字符串指针增1指向"r",字典指针指向数字2节点,进行下次匹配。
b. 当前字符无匹配,表示当前节点的任何一条边都无法达到要匹配的字符,此时不能沿现有路径前进,只能回溯,回溯到存在的最长的后缀字符串处,如果没有任何后缀字符串匹配则回溯到树根处。然后从当前回溯节点判断是否可以到达目标字符串字符。
如:接上,由于数字2节点无经"r"的连接,因此回溯,she的后缀字符串he在字典树中,因此字典树指针指向带有数字1的标志节点,由于带有标志,直接输出该节点"HE"(存疑,很多文章没有提到此处需要输出,正常路径移动的字典指针节点要判断是否可以输出,那么由回溯路径改变的字典指针指向的节点要不要判断是否输出?),然后从数字1节点判断是否有经"r"到下一节点的路径,显然图中有。因此字典树节点指向下一节点,重复以上操作,最后找到"hers",此时匹配搜索也结束了。
以上两种情况直到目标字符串指针直到末尾结束匹配。在匹配过程中遇到有标志的节点说明找到了字典中的某个词,可以直接输出。
更新:输出说明:每次目标串指针移动前都需要判断当前节点是否可以输出,并递归的判断当前节点回溯路径上的节点是否可以输出(其实就是判断所有后缀字符串,she匹配时,其后缀he也会匹配,即使she不匹配,其后缀he也可能匹配,因此需递归判断后缀字符串),直到树根结束递归。
由于固定字典的字符串的后缀字符串都是已知的,因此可以在字典树结构中存储匹配失败的路径方向,因此只要字典树构造完毕,就可以根据字典树的路径进行匹配了,效率非常快。以上就是我对该算法的全部过程的理解,疏漏之处在所难免。
附1:含匹配失败的情况的路径选择的字典树,实线表示匹配成功的正常路径,虚线表示失败的回溯路径
附2:伪代码实现
T为目标字符串,长度为m,q为字典树的节点指针,g函数返回从节点q经过路径T[i]到达的下一节点指针,f函数返回节点q的回溯节点指针。flag判断节点是否为标志节点
q := 0; // initial state (root)
for i := 1 to m do
while g(q,T[i]) = NULL do
q := f(q); // 回溯
q := g(q,T[i]); // 前进
node:=q;
while(node!=root){
if flag(node) exist ; then print i, out(node);
node = f(node); //查找回溯节点
}
endfor;
参考资料:Biosequence Algorithms, Spring 2005 Lecture 4: Set Matching and
Aho-Corasick Algorithm. Pekka Kilpelainen
【转载请注明出处:http://hi.baidu.com/absolute8511/blog/item/73ffcbf293d86e14b17ec5e9.html】
关键词:AC多模式字符串匹配算法,字符串搜索,查找字典中出现的字符串,字符串多模式匹配算法,多个字符串查找
分享到:
相关推荐
一个简单的 Java GUI 程序,它接受用户的输入(从 a 到 z ),无论字符串是小写还是大写,或者字符串之间是否有空格,并使用密钥( String )进行加密和解密过程 笔记 这个简单的 Java GUI 程序不会检查密钥是否...
对于一般级别的数据加密算法,使存储的二进制数据不会被常用的软件轻易打开,实现一定意义上的加密存储和传输!
简介:这份资源是我以前偶然...递归,拷贝一个目录或者文件到指定路径下,简单的txt转换xml,字母排序(A-Z)(先大写,后小写),列出某文件夹及其子文件夹下面的文件,并可根据扩展名过滤,字符串匹配的算法,写入日志。
根据字符串表达式计算出结果,封装常用公式算法api,代码简单调用即可实现。下载查看用例使用,仅供参考
密码学综合工具,飘云大牛的综合了各种密码学的加密算法... 更新说明: ...1.代码由VB转为Delphi,全部重写;...3.增加了一些常用的密码学算法;...7.应网友强烈要求,加入了简单适用的逻辑计算器、字符串转换器、进制转换器
字符串转换 中等的 数学 9 回文数 简单 数学 10 正则表达式 难的 动态编程 11 盛最多水的容器 中等的 大批 12 整转罗马数字 中等的 细绳 13 罗马数字转 简单 细绳 14 简单 细绳 15 三数之和 中等的 两个指针 16 最...
leetcode寻找最近的 Leetcode coding record. All questions come from . Folder ...字符串转换整数 (atoi) t8 9 回文数 t9 10 正则表达式匹配 t10 11 盛最多水的容器 t11 12 整数转罗马数字 t12 , 13
1.4.29 LastIndexOf方法——确定字符在字符串中最后索引 70 1.4.30 Matches方法——检查字符串是否有重复的词出现 71 1.4.31 MONTH函数——返回指定日期中月部分的整数 73 1.4.32 PadLeft方法——在左边用空格填充 ...
字符串算法 前缀功能(KMP) Z算法 特里 后缀数组 图论 算法/ DS DSU(不交集联合) 克鲁斯卡尔 迪克斯特拉 弗洛伊德·沃歇尔(Floyd-Warshall) SPFA(最短路径更快算法)/ Bellman-Ford Dinic流O(V ^ 2E) ...
ltrim("") 丢掉字符串左边空格 rtrim("") 丢掉字符串右边空格 trim("") 丢掉字符串首尾空格 len("") 长度 strreverse("") 字符串反转 replace("","","") 字串内替换 instr("","") 字串内出现指定字符的首位置...
2012-06-11 21:40 60 access连接字符串.txt 2012-06-11 21:08 666 adc-test.c 2012-06-11 21:07 765,000 AS3游戏编程大学.pdf 2012-06-11 21:40 750,563 ATL开发指南源码.rar 2012-06-11 21:05 186,863 BIOS练习工具...
'1' 是字符占一个字节,"1"是字符串占两个字节(含有一个结束符号)。字符结束标志为’\0’ '0' 的ASCII数值表示为48,'a' 的ASCII数值是97,'A'的ASCII数值是65。 一般考试表示单个字符错误的形式:'65' "1" ...
RAR 常规解压缩算法的速度有稍微的提高,Rar 压缩算法的不同会导致不一样。RAR 解压缩不能使用多处理器核心,所以它的速度不依赖于核心数。 3. ZIP 压缩的改变: a) 现在 ZIP 压缩支持多处理器核心,这样在多...
Hello 函数是一个无参函数,当被其它函数调用时,输出Hello world字符串。 2.有参函数的一般形式 类型说明符 函数名(形式参数表) 型式参数类型说明 { 类型说明 语句 } 有参函数比无参函数多了两个内容,其...
PDU字符串为: 08 91 683108701305F0 11 00 0D 91 3176378290F9 00 00 00 02 C834 ⑴08—短信息中心地址长度。指(91)+(683108701305F0)的长度。 ⑵91—短信息中心号码类型。91是TON/NPI遵守International/E.164...
获取字符串尺寸 行数 I IC卡读写模块 1.0 IP地址编辑框2.0 J 记录集读写操作 加解密文本1.1 加密 加密解密文本1.0 加密配置文件操作模块 加强执行1.0 加载进度条 加载进度条v2.0 结束进程模块 进程模块 ...
1)字符型文字(字符串) 'tom' (单引号) 'tom''s pen' ''为2个单引号(标识转义) 为tom's pen 2)数字型 123 -4 +56 0 9.0 1.23E5 9.8e-3 3)布尔型 TRUE FALSE NULL 7. 变量声明 语法 Var_name [CONSTANT](标识...
算法1:适应两条线结点比较平均的线,算法2:适应拐角较少的两条线,算法3:适应拐角较大的两条线。 2、先按V键,接着拉框选择两条等高线,然后执行菜单 “1辅助工具\四点插入等高线”,依次在两条等高线上点击,当...
{1.4.4}转义字符}{25}{subsection.1.4.4} {1.4.5}Boolean 布尔值}{25}{subsection.1.4.5} {1.5}基本类型变量的初始值}{26}{section.1.5} {1.6}数据类型转换}{26}{section.1.6} {1.7}方法}{26}{section.1.7} {...