藏文语义本体中的上下位关系模式匹配算法
第25卷 第4期2011年7月
中文信息学报
JOU RNAL OF CH INESE INFORM AT ION PROCESSIN G
V ol.25,No.4Jul.,2011
文章编号:1003 0077(2011)04 0045 05
藏文语义本体中的上下位关系模式匹配算法
邱莉榕1,2,翁彧1,2,赵小兵1,2
(1.中央民族大学信息工程学院,北京100081;
2.国家语言资源监测与研究中心少数民族分中心,北京100081)
摘 要:语义本体是共享概念模型显示的形式化规范说明,其目标是将杂乱无章的信息源转变为有序易用的知识源。目前语义本体还主要依赖于手工创建模式。上下位关系是一种基本的语义关系,常用于语义本体中概念的自动获取和验证。该文首先描述了藏文语义本体的创建方法,进而给出了藏文中的上下位关系模式以及模式匹配算法。上下位关系的模式可以辅助进行概念扩充,也可以作为建立和维护本体的辅助工具,这在一定程度上降低了创建和维护本体的成本。
关键词:知识获取;语义本体;概念获取;上下位关系中图分类号:T P391 文献标识码:A
Acquisition Method of Hyponymy C oncepts Based on Patterns in Tibetan Semantic Ontology
Q IU L irong 1,2
,WENG Yu 1,2
,ZHA O Xiaobing
1,2
(1.Depar tment o f Informat ion T echno lo gy ,M inzu U niv ersit y of China,Beijing 100081,China;
2.M inor ity Languag es Branch,N ational Lang uag e Reso urce M onito ring and Research Center,Beijing 100081,China)Abstract:Semant ic ontolog y is a fo rmal,explicit specification o f a shar ed conceptualization,which pr ov ides a shared vocabulary used to mo del a domain that is,the type of objects and/or co ncepts that ex ist,and their pro per ties and relat ions.H ypony my patter n is a basic semant ic r elatio nship betw een co ncepts,which is used t o co ncepts acquisition in an o nto lo gy auto matically.In this paper,hyponymy patter n is represented as a pair of a meaning fr ame defining the necessar y infor matio n ex traction in T ibetan languag e.T hen the concept acquisition algo rithm and the method o f ho w to get pattern match sentences a re pr esented.T he r esear ch of hypony my relationship pattern can assist co ncept enr ichment in onto log y,w hich can reduce the co st during the ontolog y engineer ing pro cess.Key words:know ledge acquisit ion;semantic onto log y;concepts acquisitio n;hyponymic relat ion
收稿日期:2011 04 13 定稿日期:2011 05 22
基金项目:国家科技支撑计划资助项目(2009BA H 41B04);教育部资助项目(M Z115 94)
作者简介:邱莉榕(1978 ),女,博士,副教授,主要研究方向为自然语言处理、异构资源整合;赵小兵(1967 ),女,博士,教授,主要研究方向为计算语言学、民族语言信息处理技术;翁彧(1980 ),男,博士,讲师,主要研究方向为分布式计算,Web 文本挖掘。
1 前言
藏文显示技术、藏文编码技术以及藏文输入技术得到了较好的解决
[1]
。藏文信息处理在字处理、
词和短语处理方面已经陆续取得了相对突破,句处理阶段的攻关已经开始。在句处理阶段,句法知识、语义知识、语用知识的基础理论研究是亟待解决的关键性问题。
词典中定义的概念本身并没有二义性,它能唯
一地、准确地指向现实世界中的实体或对象。但在句处理中,句中的概念是由词表示的。例如概念词
木马 在下面三个句子中至少可以表示三种概念:
(1)木马是一种玩具。
(2)木马是一种运动器械。
(3)木马是一种病毒。
因此所谓概念二义性,就是由于一个概念词可以表示多个概念引起的。而藏语也会因为上下文语
中文信息学报2011年
境的不同,其汉语有不同译文
:
同学们正在学习。
圣人的如释迦牟尼。
语言文字本身存在的语义模糊性和歧义性增加了机器分析的难度。文字(对于计算机而言就是二进制数据)仅仅是传达语义的媒介,而语义的表达才是交流的核心和关键。
对具有某种知识水平的人来说,可以根据句子的语境理解概念要传达的明确语义。例如:如果 木马 同 计算机 程序 等词同时在文中出现的话,那么可以根据已有知识,得到此处的 木马 应该指 木马 病毒的可能性最大。
知网(H ow Net)的作者董振东先生提出 自然语言处理系统最终需要更强大的知识库的支持
[2]
。
语义的核心是知识,语义本体就是共享概念模型显示的形式化规范说明[3],用于描述(特定领域的)知识。
我们可以创建计算机领域本体,如果这个领域
本体中包含了 木马、计算机、程序 等概念,并定义了这些概念之间的关系,那么计算机在使用这个本体的时候,就相当于有了这些储备知识。
藏语的语义本体的创建研究在以下问题解决上,具有突出意义:
(1)有助于扩大词典规模:当前已经手工建立了许多词典用于自然语言处理,但是词典的容量毕竟是有限的,不可能包含所有的词,特别是未登录词。本体中的上下位关系定义了概念和概念之间的层次,基于这种上下位关系,可以获得更多语义新词。
(2)支持进一步的高层(语义级、知识级)智能应用:语义本体的最终目标是将杂乱无章的信息源转变为有序易用的知识源,通过语义本体的描述,可以整合浩如烟海且瞬息万变的信息,从中发现、选择和组织有用的信息和知识,传递给需要的人或需要的系统,从而支持进一步的高层(语义级、知识级)智能应用。
(3)缓解民族语言数据稀疏问题:虽然藏文是少数民族语言中使用人口较多的语言,但相对于汉语和英语来说,藏文语言资源相对匮乏,特别是带标注文本和双语对齐的文本稀少,这对藏文的信息处
理带来不利影响。利用本体中词的语义关系,可以减少数据稀疏的影响,大大提高藏语信息处理精度。
本文首先介绍了藏文语义本体的创建过程,详
细描述藏文语义本体创建的各个步骤。然后针对上下位这种基础的语义关系,提出了藏文上下位关系模式,以及基于这种模式的匹配算法。
2 相关工作
20世纪90年代初期,国际计算机界举行了多次关于本体的专题研讨会,本体成为包括知识工程、自然语言处理和知识表示在内的诸多人工智能研究团体的热门课题,其主要原因在于本体使人与人、人与机器、机器与机器之间的交流建立在共识知识的基础上。
目前中英文自然处理领域,已经有很多语义本体的研究成果,其中最突出的是WordN et 和H ow Net 。
英文本体WordNet [4]的词汇包括名词、动词、形容词、副词和功能词。每个词(更确切地说是词的一条意项)是一个网络节点。节点之间通过 同义关系 、 反义关系 、 上位关系 、 下位关系 、 部分 整体关系 、 形态关系 等联系在一起。
中文本体H ow Net [5]是揭示概念与概念之间以及概念所具有属性之间的关系为基本内容的常识知识库,从1996年研发至今,已有汉语词项96744条,多家科研单位研发基于H o wN et 知识表示的信息处理技术。
在藏语的语义层面的研究中,一些工作对藏语句法行为的规律性进行了研究,有些研究者利用句法和语义信息将词划分成类别,从而更细致全面地反映各种类型藏语句式的语法结构框架,如句子的语序、词格标记和句法助词,并对藏语从句行为进行了分析[6]。多杰卓玛给出了基于框架的藏语词语语义研究[7]
,通过对框架进行结构信息的描述增加语义信息。龙从军研究了藏语名词语义关系,提出组织名词的基本单位是义类,联系名词与名词、名词与其他词之间的关系是语义关系
[8]
。
但目前,查新还没有查到藏文语义本体表示层面的藏文处理相关研究内容。基于语义的本体库在文本处理、信息抽取、基于文本的数据挖掘、自动翻译中都有广泛的应用,合适的本体库将成为文本自动处理中的一个重要环节。
46
4期邱莉榕等:藏文语义本体中的上下位关系模式匹配算法
3 本体创建过程
语义本体的创建是耗时耗力的艰苦工作,需要语言学家、知识工程师和信息处理人员合作完成。目前的语义本体的创建,有手工创建和自动生成两种策略。完全手工创建的本体一般规模较小,无法应付海量的知识源。自动策略一般采用有监督或无监督的机器学习技术从文本语料中自动获取概念和关系,人工干预程度较低。但自然语言处理的语义表达的复杂性和模糊性,完全的自动处理精度太低,处理结果的可用性很差。况且针对藏语来说,不同于英语和汉语具有大规模的标注语料和现有的语义词典,藏语语义本体建设可用的藏语资源很有限。
基于此,本文采用半自动本体创建策略,第一步,由知识工程师和语言专家手工建立上层本体,利用电子词典进行同义词扩充后,在多语言本体库(汉英语言创建的本体)中根据对应的上下位关系模式进行基于模式匹配的词汇扩充和翻译。第二步,根据本体概念和对应的上下位关系,在已标注语料或电子词典中查找近义词,并基于词汇语义相似度算法进行相似度从高到低的排序。知识工程师对排序结果进行修订,
编辑本体。
采用半自动本体创建策略,如图所示,分以下步骤展开:
(1)由知识工程师和语言专家手工编辑建立基于H ow Net 的上位本体,并研究藏语上下位关系的模式表示方法;
(2)上位本体中出现的概念,利用电子词典的释义,创建概念的同义词词汇集;
(3)在多语言本体库(汉英语言创建的本体)中进行概念的上下位关系模式匹配,扩充本体概念层次;
(4)本体概念和抽取的上下位关系模式匹配,
在已标注语料或电子词典中查找近义词;
(5)基于词汇语义相似度算法进行相似度从高到低的排序[9]
;
(6)知识工程师对排序结果进行修订、编辑本体。
在整个本体创建过程中,上下位关系是确定本体中概念分层的语义因素。上下位关系的模式可以辅助进行概念扩充,也可以作为建立和维护本体的辅助工具,这在一定程度上降低了创建和维护本体的成本。
4 上下位模式及匹配算法
首先,我们借鉴刘磊博士的博士学位论文[10],给出上下位关系的定义。
定义1 上下位关系,H y po ny my:如果给定概念C 1和C 2,C 1的同义集合为{C 1,C 1 , },C 2的同义集合为{C 2,C 2 , },若C 2的外延包含C 1的外延,则认为C 1和C 2具有上下位关系,其中C 1称为C 2的下位概念(hypo ny m),C 2称为C 1的上位概念(hyperny m),记作hr (C 1,C 2)。判断hr (C 1,C 2)是否成立的简单方法是看句子: C 1是一种/类/个C 2 是否可以接受。
上下位关系模式学习主要包括三个问题:1)种子上下位关系的选取;
2)模式的获取算法 模式自动生成器的构造问题;
3)获取模式分类和评价。4.1 上下位模式
(1)单对单模式:只提取一个下位概念C 1和一个上位概念C 2,组成一个上下位关系hr (C 1,C 2)。如:
基本模式:
C2>
是一种 匹配句子
:
{冰箱}C1 是一种 {电器}C2。提取关系
:hr(冰箱,电器)
(2)多对单模式:多对单模式提取多个下位概
47
中文信息学报2011年
念C1,C2, ,Cm 和一个上位概念Cm+1,组成一组上下位关系hr (C1,Cm +1),hr (C2,Cm +1), ,hr (Cm,Cm+1)。如:
基本模式:
. .
Cm >.
.
.、.. 等 .
匹配句子
:
衣柜里面有{上衣}C1、{裤子}C2、{袍子}C3
等 很多{服装}C4
提取关系
:
hr (上衣,服装),hr(裤子,服装),hr (袍子,服装)
(3)单对多模式:单对多模式提取一个下位概念C1和多个上位概念C2,C3, ,Cm,组成一组上下位关系hr(C1,C2),hr(C1,C3), ,hr(C1,Cm )。如:
基本模式:
>
C3>
. 即是 .. 又是 .匹配句子
:
{扎西}C1 即是 {老师的一个好{学生}C2} 又是 妈妈的乖{儿子}C3
提取关系
:
hr(扎西,学生),hr(扎西,儿子)
(4)多对多模式:多对多模式提取多个下位概念C1,C2, ,Cm 和多个上位概念Cm+1,Cm+2, ,Cm+n,组成一组上下位关系hr (C1,Cm+1),hr(C2,Cm+1), ,hr(Cm,Cm+1), ,hr (C1,Cm+2),hr (C2,Cm+2), ,hr(Cm,Cm+2), ,hr(C1,Cm+n),hr(C2,Cm+n), ,hr(Cm,Cm +n)。如:
基本模式:...
.
.
C4>
.<、>.. 既是 .. 又是 .
匹配句子
:
{卓玛}C1、{格桑}C2 既是 校医院的{大夫}C3 又是 医学院的{老师}C4
提取关系
:
(5)多层次模式:多层次模式可以提取一组概念C1,C2,C3。使得hr(C1,C2),hr(C2,C3)多层上下位关系成立,如:
基本模式:.
..
.
C3>
. 是所有 .. 中 .匹配句子
:
{次央}C1 是所有 {服务员}C2 中 文化程度最高的{人}C3
提取关系
:
提取关系:hr(次央,服务员),hr(服务员,人)
4.2 模式匹配算法
模式匹配问题可以描述为:上下位关系模式集合P ={p 1,p 2, ,p m },语料库G,G 中含有句子集合S ={s 1,s 2, ,s n },对任意s S,若通过模式匹配算法得到p 1,p 2, ,p k (p i P,i =1,2, k)与s 匹配,记作(s,{p 1,p 2, ,p k }),若不存在模式与s 相匹配,则记作(s, )。
模式匹配算法步骤如下: 上下位关系模式匹配算法
输入:上下位关系模式集合P,语料库G,输出:模式匹配结果
Step 1:预处理,将语料G 分割转换为句子序列S =
{s 1,s 2, ,s n };
Step 2:若S 不为空,对每一个句子s S,执行Step3-Step5;
Step 3:对s 先进行分词处理;
Step 4:在P 中搜索s 所满足的上下位关系模式,得到
48
4期邱莉榕等:藏文语义本体中的上下位关系模式匹配算法
s 所满足上下位关系模式p 1,p 2, ,p k (p i P,i =1,2, ,k );
St ep 5:根据p 1,p 2, ,p k 中每个模式的上位概念域
和下位概念域属性提取对应的上位概念部分和下位概念部分;
St ep 6:输出所有匹配结果。
例句
s:
衣柜里面有上衣、裤子、袍子等很多服装。模式p:
Defpattern 上下位关系模式//定义一个多对一模式
{
基本模式:
. .
.
.
.、.. 等 .下位概念域:
下位变量项:,和 下位概念个数:多个,和单个 下位概念位置:右,和右上位概念域:
上位变量项:上位概念个数:单个上位概念位置:右}
模式匹配结果
:
衣柜里面有/上衣/、/裤子/、/袍子/等很多服装。
提取上位概念部分和下位概念部分:
下位概念域
=
下位概念域
=上位概念域
=
下位概念域=衣柜里面有上衣、裤子下位概念域=袍子上位概念域=服装候选上下位关系:
hr
hr
hr(上衣、裤子,服装)
hr(袍子,服装)正确上下位关系:
hr
hr
hr
hr(上衣,服装)hr(裤子,服装)hr(袍子,服装)
5 总结
语义本体是共享概念模型的显示的形式化规范说明,其目标是将杂乱无章的信息源转变为有序易用的知识源。目前语义本体还主要依赖于手工创建模式。上下位关系是一种基本的语义关系,常用于语义本体中概念的自动获取和验证。本文首先描述了藏语语义本体的创建方法,进而给出了藏文中的上下位关系模式以及模式匹配算法。
后续的工作包括用于上下位关系验证的概念空间构造方法研究、模式匹配验证算法、基于概念空间的上下位关系迭代概念学习算法等。
参考文献
[1] 江荻,龙从军.藏文字符研究 字母、读音、编码、排序、
图形、拉丁字母转写规则研究[M ].北京:社会科学文献出版社.2010.
[2] 董振东,董强,郝长伶.知网的理论发现[J].中文信息学报,2007,21(4):3 9.
[3] R.Studer ,V.R.Benjamins,and D.Fensel.K now l
edge eng ineering :Pr inciples and metho ds[J].Data and Know ledge Engineer ing,1998,25(1 2):161 197.
[4] Wor dN et[OL ],http://w ordnet.pr inceto https://www.wendangku.net/doc/9f9594304.html,/w or d net/.
[5] Ho wN et[O L ],htt p://ww w.keenag https://www.wendangku.net/doc/9f9594304.html,/.
[6] 江荻.现代藏语动词的句法语义分类及相关语法句式
[J].中文信息学报,2006,20(1):37 43.[7] 龙从军,周学文.藏语名词语义关系研究.http://d.g.wanfang https://www.wendangku.net/doc/9f9594304.html,/Co nfer ence_7143464.aspx.[8] 多杰卓玛.藏语语义框架的理解与描述[J].西北民族
大学学报,2009,30(74):17 21.[9] 刘群,李素建.基于 知网 的词汇语义相似度计算
[C]//第三届汉语词汇语义学研讨会,中国台北,2002.[10] 刘磊,概念和上下位关系的获取理论和方法研究
[D].中科院计算所博士论文,2007.
49
模式匹配的KMP算法详解
模式匹配的KMP算法详解 模式匹配的KMP算法详解 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。
模式匹配算法的设计与实现
五、详细设计 #include int KMPFindImprove(String &P); //改进的KMP匹配算法 void Output2(); //输出子串在主串中出现的位置 }; int String::KMPFindImprove(String &P) { int sum=0; int j=KMPFindImprove(0,P); while(j!=-1) { count[sum++]=j; if(j<=n-P.n) j=KMPFindImprove(j+P.n,P); } return sum; } void String::Output2() //输出子串在主串中的位置 { int i=0; while(count[i]!=count[i+1] && i 在前面的图文中，我们讲了“串”这种数据结构，其中有求“子串在主串中的位置”（字符串的模式匹配）这样的算法。解决这类问题，通常我们的方法是枚举从A串（主串）的什么位置起开始与B串（子串）匹配，然后验证是否匹配。假设A串长度为n，B串长度为m，那么这种方法的复杂度是O(m*n)的。虽然很多时候复杂度达不到m*n（验证时只看头一两个字母就发现不匹配了），但是我们有许多“最坏情况”，比如： A=“aaaaaaaaaaaaaaaaaaaaaaaaab”，B=“aaaaaaaab”。 大家可以忍受朴素模式匹配算法（前缀暴力匹配算法）的低效吗？也许可以，也许无所谓。 有三位前辈D.E.Knuth、J.H.Morris、V.R.Pratt发表一个模式匹配算法，最坏情况下是O(m+n)，可以大大避免重复遍历的情况，我们把它称之为克努特-莫里斯-普拉特算法，简称KMP算法。 假如，A=“abababaababacb”，B=“ababacb”，我们来看看KMP是怎样工作的。我们用两个指针i和j分别表示，。也就是说，i是不断增加的，随着i 的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。 例子： S=“abcdefgab” T=“abcdex” 对于要匹配的子串T来说，“abcdex”首字符“a”与后面的串“bcdex”中任意一个字符都不相等。也就是说，既然“a”不与自己后面的子串中任何一字符相等，那么对于主串S来说，前5位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2到第5位的字符相等。朴素算法步骤2,3,4,5的判断都是多余，下次的起始位置就是第6个字符。 例子： S=“abcabcabc” T=“abcabx” 实验四：KMP算法实验报告 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： 竭诚为您提供优质文档/双击可除串的模式匹配算法实验报告 篇一：串的模式匹配算法 串的匹配算法——bruteForce(bF)算法 匹配模式的定义 设有主串s和子串T，子串T的定位就是要在主串s中找到一个与子串T相等的子串。通常把主串s称为目标串，把子串T称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串T；不成功则指目标串s中不存在模式串T。bF算法 brute-Force算法简称为bF算法，其基本思路是：从目标串s的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串s的第二个字符开始重新与模式串T的第一个字符进行比较。以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串s中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回0。 实现代码如下： /*返回子串T在主串s中第pos个字符之后的位置。若不存在，则函数返回值为0./*T非空。 intindex(strings,stringT,intpos) { inti=pos;//用于主串s中当前位置下标，若pos不为1则从pos位置开始匹配intj=1;//j用于子串T中当前位置下标值while(i j=1； } if(j>T[0]) returni-T[0]; else return0; } } bF算法的时间复杂度 若n为主串长度，m为子串长度则 最好的情况是：一配就中，只比较了m次。 最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是o(n+m). 模式匹配算法 源程序如下： #include printf("匹配的结果:%d\n",n); } //KMP模式匹配算法 int index_KMP(char *s,char *t,int pos) { int i=pos,j=1; while (i<=(int)strlen(s)&&j<=(int)strlen(t)) { if (j==0||s[i]==t[j-1]) { i++; j++; } else j=next[j]; } if(j>(int)strlen(t)) return i-strlen(t)+1; else return 0; } void get_next(char *t,int *next) { int i=1,j=0; next[0]=next[1]=0; while (i<(int)strlen(t)) { if (j==0||t[i]==t[j]) { i++; j++; next[i]=j; } else j=next[j]; } } 运行效果如下： 实验三串的模式匹配 一、实验目的 1．利用顺序结构存储串，并实现串的匹配算法。 2．掌握简单模式匹配思想，熟悉KMP算法。 二、实验要求 1．认真理解简单模式匹配思想，高效实现简单模式匹配； 2．结合参考程序调试KMP算法，努力算法思想； 3．保存程序的运行结果，并结合程序进行分析。 三、实验内容 1、通过键盘初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置； 2、参考程序给出了两种不同形式的next数组的计算方法，请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法，并与简单模式匹配算法进行比较。 参考程序: #include "stdio.h" void GetNext1(char *t,int next[])/*求模式t的next值并寸入next数组中*/ { int i=1,j=0; next[1]=0; while(i<=9)//t[0] { if(j==0||t[i]==t[j]) {++i; ++j; next[i]=j; } else j=next[j]; } } void GetNext2(char *t , int next[])/* 求模式t 的next值并放入数组next中 */ { int i=1, j = 0; next[1]= 0; /* 初始化 */ while (i<=9) /* 计算next[i+1] t[0]*/ { while (j>=1 && t[i] != t[j] ) j = next[j]; i++; j++; if(t[i]==t[j]) next[i] = next[j]; else next[i] = j; } } void main() { char *p="abcaababc"; int i,str[10]; GetNext1(p,str); printf("\n"); for(i=1;i<10;i++) printf("%d",str[i]); GetNext2(p,str); printf("\n"); for(i=1;i<10;i++) printf("%d",str[i]); printf("\n\n"); } 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： ...ababd... ababc ->ababc 这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串无关。 《数据结构》上给了next值的定义： 0 如果j=1 next[j]={Max{k|1 关于快速高效的模式匹配算法的剖析与改进 摘要：模式匹配算法是现代化网络入侵检测中的关键环节，本文主要介绍了几种常用的模式匹配算法，并在此基础上，提出一种更快捷、更高效的改进方法，以提高模式匹配的效率与质量，确保网络安全。 关键词：模式匹配入侵检测改进 随着我国计算机与网络技术的飞速发展，网络应用已涉及到人们生产、生活的各个领域，其重要性日益凸显。随之而来的网络攻击问题也备受关注，给网络安全性带来挑战。传统的网络防御模式，主要采取身份认证、防火墙、数据加密等技术，但是与当前网络发展不适应。在此背景下，入侵检测技术营运而生，并建立在模式匹配基础上，确保检测的快捷性、准确性，应用越来越广泛。 1、模式匹配原理概述 模式匹配是入侵检测领域的重要概念，源自入侵信号的层次性。结合网络入侵检测的底层审计事件，从中提取更高层次的内容。通过高层事件形成的入侵信号，遵循一定的结构关系，将入侵信号的抽象层次进行具体划分。入侵领域大师kumar将这种入侵信号划分为四大层次，并将每一个层次与匹配模式相对应。以下将分别对四大层次进行分析： (1)存在。只要存在审计事项，就可以证明入侵行为的发生，并深层次挖掘入侵企图。存在主要对应的匹配模式就是“存在模式”。可以说，存在模式就是在固定的时间内，检查系统中的特定状态， 同时判断系统状态。 (2)序列。一些入侵的发生，是遵循一定的顺序，而组成的各种行为。具体表现在一组事件的秩序上。序列对应的是“序列模式”，在应用序列模式检测入侵时，主要关注间隔的时间与持续的时间。 (3)规则。规则表示的是一种可以扩展的表达方式，主要通过and 逻辑表达来连接一系列的描述事件规则。一般适用于这种模式的攻击信号由相关活动组成，这些活动之间往往不存在事件的顺序关系。 (4)其他。其他模式是不包含前面几种方法的攻击，在具体应用过程中，难以与其他入侵信号进行模式匹配，大多为部分实现方式。 2、几种常用的模式匹配算法 2.1 ac算法 ac算法（aho-corasick）是一种可以同时搜索若干个模式的匹配算法，最早时期在图书馆书目查询系统中应用，效果良好。通过使用ac算法，实现了利用有限状态自动机结构对所有字符串的接收过程。自动机具有结构性特征，且每一个前缀都利用唯一状态显示，甚至可同时应用于多个模式的前缀中。如果文本中的某一个字符不属于模式中预期的下一个字符范围内，或者可能出现错误链接的指向状态等，那么最长模式的前缀同时也可作为当前状态相对应的后缀。ac算法的复杂性在于o（n），预处理阶段的复杂性则在于o（m）。在采取ac算法的有限状态自动机中，应该在每一个字符的模式串中分别建立节点，提高该算法的使用效率与质量。目前，应用有限 /** *时间：2010年8月26日7:09:57 *功能：模式匹配算法代码 */ #include"stdio.h" #include"malloc.h" void kmp(int *ikmp,char *t,int t_length) { int k=0; int q=0; ikmp[0]=k; for(q=1;q while(t[t_length]!='\0') { t_length++; } /*测试*/ printf("t_length is %d\n",t_length); /*求t的kmp值*/ ikmp=malloc(t_length*sizeof(int)); kmp(ikmp,t,t_length); /*匹配过程*/ for(q=0;q //算法功能：串的朴素模式匹配是最简单的一种模式匹配算法，又称为 Brute Force 算法，简称为BF算法 #include int main() { SString S, T; int m; char strs1[MAXL]; //建立主串S char strs2[MAXL]; //建立模式串T printf("请输入主串和子串:\n"); printf("主串S: "); scanf("%s", strs1); printf("子串T: "); scanf("%s", strs2); StrAssign(S, strs1); StrAssign(T, strs2); m = Index(S, T, 1); if(m) printf("主串 S = {%s}\n子串 T = {%s}\n在第 %d 个位置开始匹配！\n", strs1, strs2, m); else printf("主串 S = {%s}\n子串 T = {%s}\n匹配不成功！\n", strs1, strs2); return 0; } Brute Force(BF或蛮力搜索) 算法： 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐，然后从左向右一个一个进行比较，如果不成功则模式串向右移动一个单位。 速度最慢。 那么，怎么改进呢？ 我们注意到Brute Force 算法是每次移动一个单位，一个一个单位移动显然太慢，是不是可以找到一些办法，让每次能够让模式串多移动一些位置呢？ 当然是可以的。 我们也注意到，Brute Force 是很不intelligent 的，每次匹配不成功的时候，前面匹配成功的信息都被当作废物丢弃了，当然，就如现在的变废为宝一样，我们也同样可以将前面匹配成功的信息利用起来，极大地减少计算机的处理时间，节省成本。^_^ 注意，蛮力搜索算法虽然速度慢，但其很通用，文章最后会有一些更多的关于蛮力搜索的信息。 KMP算法 首先介绍的就是KMP 算法。 这个算法实在是太有名了，大学上的算法课程除了最笨的Brute Force 算法，然后就介绍了KMP 算法。也难怪，呵呵。谁让Knuth D.E. 这么world famous 呢，不仅拿了图灵奖，而且还写出了计算机界的Bible 简单的模式匹配算法_Brute-Force算法 在串的操作中，子串的定位操作Index_string(s，t)，通常称之为模式匹配(其中：子串t称之为模式串)。其功能是：主串s＝“c0c1...c n-1”中，去查找子串t＝“t0t1...t m-1”，若找到则返回子串t在主串s中的位置,否则查找不成功，返回-1。 为了便于理解，我们举例进行说明。 1．例子 例如：主串s=”ababcabcacbab”,t=”abcac”。其匹配过程如图6－12所示。 第一趟匹配: i=2 a b a b c a b c a c b a b a b c j=2 第二趟匹配: i=1 a b a b c a b c a c b a b a j=0 第三趟匹配： i=6 a b a b c a b c a c b a b a b c a c j=4 第四趟匹配： i=3 a b a b c a b c a c b a b a j=0 第五趟匹配： i=4 a b a b c a b c a c b a b a j=0 第六趟匹配： i=10 a b a b c a b c a c b a b a b c a c j=5 图6－12 Brute-Force算法中串的匹配过程 2．算法思想 算法的基本思想是：分别设置计数指针i和j指示主串s和模式串t中当前正待比较的字符位置。从主串的第一个字符和模式的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较。依次类推，直到模式串中的每个字符依次和主串中的一个连续的字符序列相等，则称匹配成功，函数值为和模式串中第一个字符相等的字符在主串中的序号，否则称匹配不成功。 这个算法简单，易于理解，但效率不高，主要原因是：主串指针i在若干个字符序列比较相等后只要有一个字符比较不等便需回溯。 Boyer-Moore 经典单模式匹配算法 BM模式匹配算法-原理（图解） 由于毕业设计（入侵检测）的需要，这两天仔细研究了BM模式匹配算法，稍有心得，特此记下。 首先，先简单说明一下有关BM算法的一些基本概念。 BM算法是一种精确字符串匹配算法（区别于模糊匹配）。 BM算法采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。 BM算法的基本流程: 设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较，如下图所示: 若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。 下面，来详细介绍一下坏字符规则和好后缀规则。 首先，诠释一下坏字符和好后缀的概念。 请看下图： 图中，第一个不匹配的字符（红色部分）为坏字符，已匹配部分（绿色）为好后缀。 1）坏字符规则（Bad Character）： 在BM算法从右向左扫描的过程中，若发现某个字符x不匹配，则按如下两种情况讨论： i. 如果字符x在模式P中没有出现，那么从字符x开始的m个文本显然不可能与P匹配成功，直接全部跳过该区域即可。 ii. 如果x在模式P中出现且出现次数>=1，则以该字符所在最右边位置进行对齐。 用数学公式表示，设Skip(x)为P右移的距离，m为模式串P的长度，max(x)为字符x在P中最右位置。 可以总结为字符x出现与否，将max(x)=0作为初值即可。 例1： 下图红色部分，发生了一次不匹配。 计算移动距离Skip(c) = m-max(c)=5 - 3 = 2，则P向右移动2位。 移动后如下图： 2）好后缀规则（Good Suffix）： 若发现某个字符不匹配的同时，已有部分字符匹配成功，则按如下两种情况讨论： i. 如果在P中位置t处已匹配部分P'在P中的某位置t'也出现，且位置t'的前一个字符与位置t的前一个字符不相同，则将P右移使t'对应t方才的所在的位置。 ii. 如果在P中任何位置已匹配部分P'都没有再出现，则找到与P'的后缀P''相同的P的最长前缀x，向右移动P，使x对应方才P''后缀所在的位置。 目录 目录 摘要 .......................................................................................................................... I ABSTRACT ............................................................................................................... I II 第1章绪论 .. (1) 1.1课题背景及研究的目的和意义 (1) 1.2模式匹配概述 (2) 1.3研究现状分析 (3) 1.3.1 精确模式匹配算法 (4) 1.3.2 近似模式匹配算法 (14) 1.3.3 并行模式匹配算法 (17) 1.3.4 基于硬件的模式匹配方法 (19) 1.3.5 网络内容安全中模式匹配存在的关键问题 (22) 1.4本文的研究内容及组织结构 (23) 1.4.1 本文研究内容 (23) 1.4.2本文章节安排 (24) 第2章基于扩展BLOOM FILTER的并行模式匹配方法 (26) 2.1引言 (26) 2.2B LOOM F ILTER结构 (27) 2.3扩展B LOOM F ILTER (EBF) (29) 2.4并行扩展B LOOM F ILTER(PEBF) (32) 2.5PEBF在GPU上的实现(G-PEBF) (35) 2.6G-PEBF算法分析 (37) 2.7实验结果及分析 (40) 2.8本章小结 (44) 第3章基于矩阵模型的并行模式匹配方法 (46) 3.1引言 (46) 3.2基于向量模型的单模式匹配方法 (46) 3.3基于矩阵模型的多模式匹配方法 (48) 3.4基于矩阵模型的匹配算法在GPU上的实现 (51) 3.4.1 MBMPA在GPU上的实现(G-MBMPA) (52) 3.4.2 MBMPE在GPU上的实现(G-MBMPE) (55) 个人觉得这篇文章是网上的介绍有关KMP算法更让人容易理解的文章了，确实说得很“详细”，耐心地把它看完肯定会有所收获的～～，另外有关模式函数值next[i]确实有很多版本啊，在另外一些面向对象的算法描述书中也有失效函数f(j)的说法，其实是一个意思，即next[j]=f(j-1)+1，不过还是next[j]这种表示法好理解啊： KMP字符串模式匹配详解 KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数： int Index_BF ( char S [ ], char T [ ], int pos ) { /* 若串S 中从第pos(S 的下标0≤pos 串的匹配算法——Brute Force (BF)算法 匹配模式的定义 设有主串S和子串T，子串T的定位就是要在主串S中找到一个与子串T相等的子串。通常把主串S称为目标串，把子串T称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串S中找到一个模式串T；不成功则指目标串S中不存在模式串T。 BF算法 Brute-Force算法简称为BF算法，其基本思路是：从目标串S的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串S的第二个字符开始重新与模式串T的第一个字符进行比较。以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串S中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回0。 实现代码如下： /*返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0. /*T非空。 int index(String S, String T ,int pos) { int i=pos; //用于主串S中当前位置下标，若pos不为1则从pos位置开始匹配int j =1; //j用于子串T中当前位置下标值 while(i<=S[0]&&j<=T[0]) //若i小于S长度且j小于T的长度时循环 { if(S[i]==T[j]) //两个字母相等则继续 { ++i； ++j； } else //指针后退重新开始匹配 { i=i-j+2; //i退回到上次匹配首位的下一位 j=1； } if(j>T[0]) return i-T[0]; else return 0; } } BF算法的时间复杂度 若n为主串长度，m为子串长度则 最好的情况是：一配就中，只比较了m次。 最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m 次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m 从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是O(n+m). 三种模式匹配算法 作业要求：分别用KMP、MonteCarlo、LasVegs算法编制三个程序，随机生成不小于5000对长度不等的01串（三个程序使用相同的串），然后统计算法的执行时间和MonteCarlo算法的出错比率，并根据运行结果对三种算法进行深入的比较。 1、算法思路 KMP算法的主要特点是指向主串的指针不需要回溯，只向右移动，即模式串在与主串失配时，并不回溯主串的指针与模式串重新匹配，而是根据已经得到的匹配信息将模式串尽可能远的向右滑动一段。滑动距离的大小取决于模式串的失效函数next, next[k]（0<=k<=m-1）的值表示当模式串在下标为k的字符处与主串失配时应该向右移动到下标为next[k]的字符处再与主串重新匹配。算法首先要求模式串的失效函数next，然后再根据next的值进行模式匹配，在最坏情况下的时间复杂度为O（m*n），m为模式串的长度，n为主串的长度，当如果模式串中有较多相同的字符时，时间复杂度一般可达到O（m+n）。 MonteCarlo随机算法主要是通过比较模式串和主串中与模式串等长的串的“指纹”来匹配的，若两者指纹相等，则可以认为在概率意义下两者是相等的，算法中要求用到一个随机产生的素数作模运算，该素数的选取直接影响了算法的准确率，算法的时间复杂度为O（m+n）。但有一定的出错率，即选取主串中比较串的指纹与模式串相等时但比较串与模式串并不相等，理论上这种情况出现的概率为1/n，只与主串的长度有关，与模式串的长度无关，但实际上只要选取素数合适出错率比1/n要小的多。 LasVegas算法是对MonteCarlo算法的改进，当模式串的指纹与主串中的比较串相等时，此时并不直接返回匹配的位置，而是判断两个字符串是否真的相等，相等则返回，否则继续匹配。所以，该算法总能得到正确的位置，但算法的执行时间稍微比MonteCarlo算法要长一点（判断字符串是否相等的耗费），时间复杂度的期望值不超过O(m+n)。 要完成上述三个模式匹配算法的比较，需要一个0/1串的随机发生器和一个素数发生器。程序中头文件”randstr.h”包含的RandomString类是用来产生MAXSIZE对的主串和模式串的，0/1串的长度和内容都是随机的，为了便于比较，规定主串的长度一定大于模式串的长度。”random.h”包含的Random类封装了产生随机数的函数。素数发生器首先产生MAXSIZE个随机数保存在prime数组中，供随机算法使用。本程序中随机生成了10000对0/1串作为测试数据，即MAXSIZE=10000。”defs.h”定义了所用的常量。 2、算法分析和比较 运行PatternMatching可以发现： 1）三个算法运行的时间处于同一数量级的，其中在大多数情况下MonteCarlo的算法都要快于KMP和LasVegas算法，从理论上分析MonteCarlo算法的平均时间复杂度优于KMP算法，一般情况MonteCarlo 时间复杂度为O（m+n），而KMP最好情况O（m+n），最坏为O(n*m)。LasVegs要比MonteCarlo稍微慢一点点，这是预料之中的，因为判断字符串相等耗费了额外的时间。KMP和LasVegs算法的平均时间复杂度大致相等。 2）随机选取的素数大小直接影响了MonteCarlo算法的出错率。在模式串不是很长时，当素数大于某个数时我们可以发现出错率可以降到0。设模式串的最长长度为m，当随机产生的素数p>2m时，Y和X(j)的对p作模运算后的“指纹”Ip都要小于p, 此时p不可能可以整除|Y ? X(j)|，因此不会出现当Ip（X(j)）=Ip(y)时却有X(j)≠Y的误判情况，所以这种情况下MonteCarlo出错率为0。 3）素数一定大时，MonteCarlo算法的出错率比理论值1/n要小的多，即当Ip（X(j)）= Ip(y)时却有X(j)≠Y 的情况很少。相反，当素数很小时，不同0/1序列对素数作模运算的结果相同的可能性增大，出错率相应地变大。 4）当模式串的长度比主串小很多时，三个算法的执行时间明显快了，KMP和MonteCarlo算法的执行时间几乎相等。这也是比较容易理解的，模式串很短意味着它与主串匹配成功的可能性就大，算法不需要从头到尾扫描一遍主串就可以在主串的较前面找到匹配串的位置，此外，模式串的长度小则说明耗费在扫描一遍模式串的时间就短，因此执行算法所花费的时间就少得多，KMP时间复杂度接近O(m+n)，与MonteCarlo算法相等。 数据结构面试之十四——字符串的模式匹配 题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。 十四、字符串的模式匹配 1. 模式匹配定义——子串的定位操作称为串的模式匹配。 2. 普通字符串匹配BF算法（Brute Force 算法，即蛮力算法） 【算法思想】： 第（1）步；从主串S的第pos个字符和模式的第一个字符进行比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较之。 第（2）步骤；依次类推，直至模式T中的每一个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功；函数值为和模式T中第一个字符相等的字符在主串S中的序号，否则称为匹配不成功，函数值为0。 比如对于主串S=”abacababc”; 模式串T=”abab”; 匹配成功，返回4。 对于主串S=”abcabcabaac”; 模式串T=”abab”; 匹配不成功，返回0。 【算法实现】： //普通字符串匹配算法的实现 int Index(char* strS, char* strT, int pos) { //返回strT在strS中第pos个字符后出现的位置。 int i = pos; int j = 0; int k = 0; int lens = strlen(strS); int lent = strlen(strT); while(i < lens && j < lent) { if(strS[i+k] == strT[j]) { ++j; //模式串跳步 ++k; //主串(内)跳步 } else { i = i+1; j=0; //指针回溯，下一个首位字符 k=0; } }//end i if(j >= lent) { return i; } else { return 0; } }//end [算法时间复杂度]：设主串长度为m,模式串的长度为n。一般情况下n字符串的模式匹配算法
模式匹配KMP算法实验报告
串的模式匹配算法实验报告
数据结构-模式匹配算法
实验三____串的模式匹配
模式匹配KMP算法实验步骤
关于快速高效的模式匹配算法的剖析与改进
模式匹配算法
串的朴素模式匹配算法(BF算法)
字符串匹配算法总结
简单的模式匹配算法
BM模式匹配算法图解
高性能在线模式匹配算法研究
KMP字符串模式匹配算法解释
串的模式匹配算法
三种模式匹配算法的比较和分析
C语言字符串模式匹配