没有合适的资源?快使用搜索试试~ 我知道了~
资源详情
资源评论
资源推荐
第
第
1
1
1
1
章
章
串
§11.1 串及串匘配 第11章 串
306
串或字符串(string)属于线性结构,自然地可直接利用向量或列表等序列结构加以实现。
但字符串作为数据结构,特点也极其鲜明,这可归纳为:结构简单,规模庞大,元素重复率高。
所谓结构简单,是指字符表本身的规模不大,甚至可能极小。以生物信息序列为例,参与蛋
白质(文本)合成的常见氨基酸(字符)只有20种,而构成DNA序列(文本)的碱基(字符)仅
有4种。尽管就规模而言,地球系统模式的单个输出文件长达1~100GB,微软Windows系统逾4000
万行的源代码长度累计达到40GB,但它们都只不过是由ASCII字符,甚至是可打印字符组成的。
因此,以字符串形式表示的海量文本数据的高效处理技术,一直都是相关领域的研究重点。
鉴于字符串结构的上述特点,本章将直接利用C++本身所提供的字符数组,并转而将讲述的
重点,集中于各种串匹配算法indexOf()的基本原理与高效实现。
§11.1 串及串匹配
11.1.1 串
字符串
一般地,由n个字符构成的串记作:
S = "a
0
a
1
... a
n-1
", 其中,a
i
,0 i < n
这里的是所有可用字符的集合,称作字符表(alphabet),例如二进制比特集 = { 0, 1 }、
ASCII字符集、Unicode字符集、构成DNA序列的所有碱基、组成蛋白质的所有氨基酸,等等。
字符串S所含字符的总数n,称作S的长度,记作|S| = n。这里只考虑长度有限的串,n < 。
特别地,长度为零的串称作空串(null string)。请注意,空串并非由空格字符'□'组成的串,
二者完全不同。
子串
字符串中任一连续的片段,称作其子串(substring)。具体地,对于任意的0 i i +
k < n,由字符串S中起始于位置i的连续k个字符组成的子串记作:
S.substr(i, k) = "a
i
a
i+1
... a
i+k-1
" = S[i, i + k)
有两种特殊子串:起始于位置0、长度为k的子串称为前缀(prefix),而 终止于位置n - 1、
长度为k的子串称为后缀(suffix),分别记作:
prefix(S, k) = S.substr(0, k) = S[0, k)
suffix(S, k) = S.substr(n - k, k) = S[n - k, n)
由上述定义可直接导出以下结论:空串是任何字符串的子串,也是任何字符串的前缀和后缀;
任何字符串都是自己的子串,也是自己的前缀和后缀。此类子串、前缀和后缀分别称作平凡子串
(trivial substring)、平凡前缀(trivial prefix)和平凡后缀(trivial suffix)。
反之,字符串本身之外的所有非空子串、前缀和后缀,分别称作真子串(proper substring)、
真前缀(proper prefix)和真后缀(proper suffix)。
第11章 串 §11.1 串及串匘配
307
判等
最后,字符串S[0, n)和T[0, m)称作相等,当且仅当二者长度相等(n = m),且对应的
字符分别相同(对任何0 i < n都有S[i] = T[i])。
ADT
串结构主要的操作接口可归纳为表11.1。
表11.1 串ADT支持癿操作看接口
操 作 接 口
功 能
length()
查诟串癿长度
charAt(i)
迒回第i个字符
substr(i, k)
迒回从第i个字符起、长度为k癿子串
prefix(k)
迒回长度为k癿前缀
suffix(k)
迒回长度为k癿后缀
equal(T)
刞断T是否不弼前字符串相等
concat(T)
将T串接在弼前字符串乀后
indexOf(P)
若P是弼前字符串癿一个子串,则迒回诠子串癿起始位置;否则迒回-1
比如,依次对串S = "data structures"执行如下操作,结果依次如表11.2所示。
表11.2 串操作实例
操 作
输 出
字 符 串 S
length()
15
"data structures"
charAt(5)
's'
"data structures"
prefix(4)
"data"
"data structures"
suffix(10)
"structures"
"data structures"
concat("and algorithms")
"data structures and algorithms"
equal("data structures")
false
"data structures and algorithms"
equal("data structures and algorithms")
true
"data structures and algorithms"
indexOf("string")
-1
"data structures and algorithms"
indexOf("algorithm")
20
"data structures and algorithms"
11.1.2 串匹配
应用与问题
在涉及字符串的众多实际应用中,模式匹配是最常使用的一项基本操作。比如UNIX Shell
的grep工具(General Regular Expression Parser)和DOS的find命令,基本功能都是在
指定的字符串中查找
①
特定模式的字符串。又如生物信息处理领域,也经常需要在蛋白质序列中
①
返两个命令都是以文件形式来指定待查找癿文本串,具体格式分删是:
% grep <pattern> <file>
c:\> find "pattern" <file>
§11.1 串及串匘配 第11章 串
308
寻找特定的氨基酸模式,或在DNA序列中寻找特定的碱基模式。再如,邮件过滤器也需根据事先
定义的特征串,通过扫描电子邮件的地址、标题及正文来识别垃圾邮件。还有,反病毒系统也会
扫描刚下载的或将要执行的程序,并与事先提取的特征串相比对,以判定其中是否含有病毒。
上述所有应用问题,本质上都可转化和描述为如下形式:
如何在字符串数据中,检测和提取以字符串形式给出的某一局部特征
这类操作都属于串模式匹配(string pattern matching)范畴,简称串匹配。一般地,即:
对基于同一字符表的任何文本串T(|T| = n)和模式串P(|P| = m):
判定T中是否存在某一子串与P相同
若存在(匹配),则报告该子串在T中的起始位置
串的长度n和m本身通常都很大,但相对而言n更大,即满足2 << m << n。比如,若:
T = "Now is the time for all good people to come"
P = "people"
则匹配的位置应该是T.indexOf(P) = 29。
问题分类
根据具体应用的要求不同,串匹配问题可以多种形式呈现。
有些场合属于模式检测(pattern detection)问题:我们只关心是否存在匹配而不关心
具体的匹配位置,比如垃圾邮件的检测。有些场合属于模式定位(pattern location)问题:
若经判断的确存在匹配,则还需确定具体的匹配位置,比如带毒程序的鉴别与修复。有些场合属
于模式计数(pattern counting)问题:若有多处匹配,则统计出匹配子串的总数,比如网络
热门词汇排行榜的更新。有些场合则属于模式枚举(pattern enumeration)问题:在有多处
匹配时,报告出所有匹配的具体位置,比如网络搜索引擎。
11.1.3 测评标准与策略
串模式匹配是一个经典的问题,有名字的算法已不下三十种。鉴于串结构自身的特点,在设
计和分析串模式匹配算法时也必须做特殊的考虑。其中首先需要回答的一个问题就是,如何对任
一串匹配算法的性能作出客观的测量和评估。
多数读者首先会想到采用评估算法性能的常规口径和策略:以时间复杂度为例,假设文本串
T和模式串P都是随机生成的,然后综合其各种组合从数学或统计等角度得出结论。很遗憾,此类
构思并不适用于这一问题。
以基于字符表 = { 0, 1 }的二进制串为例。任给长度为n的文本串,其中长度为m的子串
不过n - m + 1个(m << n时接近于n个)。另一方面,长度为m的随机模式串多达2^m个,故匹
配成功的概率为n / 2^m。以n = 100,000、m = 100为例,这一概率仅有
100,000 / 2
100
< 10
-25
对于更长的模式串、更大的字符表,这一概率还将更低。因此,这一策略并不能有效地覆盖成功
匹配的情况,所得评测结论也无法准确地反映算法的总体性能。
实际上,有效涵盖成功匹配情况的一种简便策略是,随机选取文本串T,并从T中随机取出
长度为m的子串作为模式串P。这也是本章将采用的评价标准。
第11章 串 §11.2 蛮力算法
309
§11.2 蛮力算法
11.2.1 算法描述
图11.1 串模式匹配癿蛮力算法
蛮力串匹配是最直接最直觉的方法。如图
11.1所示,可假想地将文本串和模式串分别写
在两条印有等间距方格的纸带上,文本串对应
的纸带固定,模式串纸带的首字符与文本串纸
带的首字符对齐,二者都沿水平方向放置。于
是,只需将P与T中长度为m的n - m + 1个子串
逐一比对,即可确定可能的匹配位置。
不妨按自左向右的次序考查各子串。在初始状态下,T的前m个字符将与P的m个字符两两对
齐。接下来,自左向右检查相互对齐的这m对字符:若当前字符对相互匹配,则转向下一对字符;
反之一旦失配,则说明在此位置文本串与模式串不可能完全匹配,于是可将P对应的纸带右移一
个字符,然后从其首字符开始与T中对应的新子串重新对比。图中,模式串P的每一黑色方格对应
于字符对的一次匹配,每一灰色方格对应于一次失配,白色方格则对应于未进行的一次比对。若
经过检查,当前的m对字符均匹配,则意味着整体匹配成功,从而返回匹配子串的位置。
蛮力算法的正确性显而易见:既然只有在某一轮的m次比对全部成功之后才成功返回,故不
致于误报;反过来,所有对齐位置都会逐一尝试,故亦不致漏报。
11.2.2 算法实现
以下给出蛮力算法的两个实现版本。二者原理相同、过程相仿,但分别便于引入后续的不同
改进算法,故在此先做一比较。
1 /******************************************************************************************
2 * Text : 0 1 2 . . . i-j . . . . i . . n-1
3 * ------------------------|-------------------|------------
4 * Pattern : 0 . . . . j . .
5 * |-------------------|
6 ******************************************************************************************/
7 int match ( char* P, char* T ) { //串匘配算法(Brute-force-1)
8 size_t n = strlen ( T ), i = 0; //文本串长度、弼前接叐比对字符癿位置
9 size_t m = strlen ( P ), j = 0; //模式串长度、弼前接叐比对字符癿位置
10 while ( j < m && i < n ) //自左向右逐个比对字符
11 if ( T[i] == P[j] ) //若匘配
12 { i ++; j ++; } //则转刡下一对字符
13 else //否则
14 { i -= j - 1; j = 0; } //文本串回退、模式串复位
15 return i - j; //如何通过迒回值,刞断匘配结枅?
16 }
代码11.1 蛮力串匹配算法(版本一)
剩余27页未读,继续阅读
尹子先生
- 粉丝: 20
- 资源: 324
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0