《数据结构串》PPT课件.ppt

数据结构-串,齐 恒 大黑楼 B0912,中国互联网发展状况,中国网民数量有多少？,中国互联网发展状况,在网上干什么？,QQ？微信？ 看新闻？ 查资料？ 听音乐？ 看视频？ 玩微博？ 购物？,在网上干什么？,全球网民在干什么？,在互联网中，信息搜索引擎的应用是最为广泛的,Google搜索引擎源于拉里佩奇和谢尔盖布林在斯坦福大学读书时所做的一个研究项目。他们最开始是在佩奇简陋的宿舍搞研究。 1996年初，佩奇和布林开始合作研究一名为“BackRub”的搜索引擎，到1998年上半年逐步完善这项技术后，两人开始为这项技术寻找合作伙伴。他们找到雅虎的创始人之一戴维菲洛。菲洛认为他们的技术确实很可靠，但建议他们自己建立一个搜索引擎公司发展业务，发展起来后再考虑合作。,拉里佩奇（Larry Page）,信息检索技术,信息检索(Information retrieval, IR)是指将信息按照一定的方式组织和存储起来，并根据信息用户的需求找出有关的信息的过程和技术。它的全称应该叫“信息存储与检索”（Information Storage and Retrieval）。,信息存储：对信息进行特征描述、加工并使其有序化。,信息检索：借助一定的设备和工具，采用一系列方法 和策略查找出所需要的信息。,基础,目的,狭义的信息检索指的是后一过程.,信息检索历史,单机批处理检索阶段 ： 1946年，世界上第一台数字式电子计算机诞生，1951年，美国麻省理工学院开始对利用计算机代码化文摘进行可行性研究。 这一阶段也称为脱机检索时期，一是单机由专人操作；二是只能进行批处理不能即问即答。 联机检索阶段： 1960年，美国国家医学图书馆开始建立“医学文献分析与检索系统”。 网络化检索阶段： 20世纪80年代中期，美国国家科学基金会计算机网络（NSFnet）将各地的一些大学、科研机构及政府机构的局域网络联结成一个全国性的计算机信息网络 。进入90年代，世界各国在仿效NSFnet建立全国性文献信息计算机网络基础上，设法与美国联网，因而产生了国际计算机互联网络Internet。,Internet搜索引擎历史,1990年,加拿大麦吉尔大学(University of McGill)计算机学院的师生开发出Archie，查找FTP主机中的文件。Archie被公认为现代搜索引擎的鼻祖. 1993年MIT大学的Matthew Gray开发了 World Wide Web Wanderer,这是第一个利用HTML网页之间的链接关系来检测万维网规模的“机器人(Robot)“程序.开始,它仅仅用来统计互联网上的服务器数量,后来也能够捕获网址(URL). 1994年4月,斯坦福大学(Stanford University)的两名博士生,美籍华人Jerry Yang(杨致远)和David Filo共同创办了Yahoo。 1994年初,华盛顿大学(University of Washington )的学生Brian Pinkerton开始了他的小项目WebCrawler。它是互联网上第一个支持搜索文件全部文字的全文搜索引擎。 1994年7月,卡内基梅隆大学(Carnegie Mellon University) 的Michael Mauldin创建了Lycos。Lycos第一个在搜索结果中使用了网页自动摘要,而最大的优势还是它远胜过其它搜索引擎的数据量。 1994年底,Infoseek正式亮相.其友善的界面,大量的附加功能,使之和Lycos一样成为搜索引擎的重要代表。,Internet搜索引擎历史,1995年,一种新的搜索引擎形式出现了元搜索引擎(A Meta Search Engine Roundup)。第一个元搜索引擎,是Washington大学硕士生 Eric Selberg 和 Oren Etzioni 的 Metacrawler. 1995年12月,DEC的正式发布AltaVista。AltaVista是第一个支持自然语言搜索的搜索引擎,第一个实现高级搜索语法的搜索引擎(如 AND, OR, NOT等)。 1997年8月,Northernlight搜索引擎正式现身.它曾是拥有最大数据库的搜索引擎之一。 1998年10月之前,Google只是斯坦福大学(Stanford University)的一个小项目BackRub。1995年博士生Larry Page开始学习搜索引擎设计,于1997年9月15日注册了的域名,1997年底,在Sergey Brin和Scott Hassan,Alan Steremberg的共同参与下,BachRub开始提供Demo。 1999年2月,Google完成了从Alpha版到Beta版的蜕变.Google公司则把1998年9月27日认作自己的生日。2006年4月,Google宣布其中文名称“谷歌”,这是Google第一个在非英语国家起的名字。,国内Internet搜索引擎历史,1996年8月,sohu公司成立,制作中文网站分类目录,曾有“出门找地图,上网找搜狐“的美誉.随着互联网网站的急剧增加,这种人工编辑的分类目录已经不适应. 1998年1月，台湾中正大学吴升教授所领导的GAIS实验室创立了Openfind搜索引擎。Openfind起先只做中文搜索引擎,鼎盛时期同时为三大著名门户新浪,奇摩,雅虎提供中文搜索引擎。 2000年1月,两位北大校友,超链分析专利发明人,前Infoseek资深工程师李彦宏与好友徐勇(加州伯克利分校博士后)在北京中关村创立了百度 (Baidu)公司。 2001年8月发布B搜索引擎Beta版(此前Baidu只为其它门户网站搜狐新浪Tom等提供搜索引擎),2001年10月22日正式发布Baidu搜索引擎,专注于中文搜索。2005年8月5日在纳斯达克上市, 创下了5年以来美国股市上市新股当日涨幅最高纪录。,词袋模型（bag-of-words）,文本信息检索中的索引机制,词汇表,- 词袋模型（bag-of-words model, BoW） - 倒排文件索引（inverted file）,词袋模型示例,构建倒排文件,网页的BoW表示,检索条件的BoW表示,Internet,第四章 串,4.2 串的抽象数据类型的定义,4.3 串的表示和实现,4.4 串的模式匹配算法,4.1 串的相关术语,串是普遍存在的数据对象 人名，地名，货物名， 文字编辑中的各种字符 信息检索和问答系统中的输入信息 源程序，目标程序,4.1 串的相关术语,2. 串的定义 由零个或多个字符组成的有限序列. 一般记为：s= a1a2an ，n=0 串名：s = 变量名 = 字符串 串值： a1a2an =空格串: a1,a2,an 均为空格 串长：n = n=0 =空串 空格串不同于空串,子串：串中任意个连续的字符组成的子序列 =原串：主串 位置：字符的位置，子串的位置 串相等：当且仅当两个串的串值相等,4.2 串的抽象数据类型的定义如下：,ADT String ,数据对象：,D ai | aiCharacterSet, i=1,2,.,n, n0 ,数据关系：,R1 | ai-1, ai D, i=2,.,n ,基本操作：,StrAssign (&T, chars),StrCopy (&T, S),DestroyString(&S),StrEmpty (S),StrCompare (S, T),StrLength(S),Concat (&T, S1, S2),SubString (&Sub, S, pos, len),Index (S, T, pos),Replace (&S, T, V),StrInsert (&S, pos, T),StrDelete (&S, pos, len),ClearString (&S), ADT String,StrAssign (&T, chars) 初始条件：chars 是字符串常量。 操作结果：T赋值为 chars 的值。,StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。,DestroyString (&S) 初始条件：串 S 存在。 操作结果：串 S 被销毁。,StrEmpty(S) 初始条件：串S存在。 操作结果：若 S 为空串，则返回TRUE， 否则返回 FALSE。,注： 表示空串，其长度为0。,StrCompare(S,T) 初始条件：串 S 和 T 存在。 操作结果：若S T，则返回值 0 若S T，则返回值 0 若S T，则返回值 0,比较原则：按字母顺序，逐位比较 实际上是按ASCII码顺序比较,例如：StrCompare(data, state) 0 StrCompare(cat, cat) = 0,StrLength (S) 初始条件：串 S 存在。 操作结果：返回 S 的元素个数， 称为串的长度。,注：空格在串中占一个位置， 其长度为1。,Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。,例如： Concat( T, man, kind) 求得 T = mankind,SubString (&Sub, S, pos, len) 初始条件： 串 S 存在，1posStrLength(S) 且0lenStrLength(S)-pos+1。 操作结果： 用 Sub 返回串 S 的第 pos 个字符起 长度为 len 的子串。,例如： SubString( sub, commander, 4, 3) 求得 sub = man ； SubString( sub, commander, 1, 9) 求得 sub = commander； SubString( sub, commander, 9, 1) 求得 sub = r；,子串为“串”中的一个字符子序列,SubString(sub, commander, 4, 7) sub = ?,SubString(sub, beijing, 8, 2) = ? sub = ?,SubString(student, 5, 0) = ,起始位置和子串长度之间存在约束关系,长度为 0 的子串为“合法”串,Index(S,T,pos) 初始条件：串S和T存在，T是非空串， 1posStrLength(S)。 操作结果： 若主串 S 中第pos个字符之后 存在和串 T 值相同的子串, 则 返回它在主串 S 中第pos个字符 之后第一次出现的位置； 否则函数值为0。,假设 S = abcaabcaaabc, T = bca,Index(S, T, 1) = 2；,Index(S, T, 3) = 6；,Index(S, T, 8) = 0；,“子串在主串中的位置”意指子串 中的第一个字符在主串中的位序。,Replace(&S, T, V) 初始条件：串S, T和 V 均已存在， 且 T 是非空串。 操作结果：用V替换主串S中出现 的所有与（模式串）T 相等的不重叠的子串。,例如：,假设 S = abcaabcaaabca，T = bca,若 V = x， 则经置换后得到 S = axaxaax,若 V = bc， 则经置换后得到 S = abcabcaabc,StrInsert (&S, pos, T) 初始条件：串S和T存在， 1posStrLength(S)1。 操作结果：在串S的第pos个字符之前 插入串T。,例如：S = chater，T = rac， 则执行 StrInsert(S, 4, T)之后得到 S = character,StrDelete (&S, pos, len) 初始条件：串S存在 1posStrLength(S)-len+1。 操作结果：从串S中删除第pos个字符 起长度为len的子串。,ClearString(&S) 初始条件：串S存在。 操作结果：将S清为空串。,对于串的基本操作集可以有不同的定义方法。 在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。,gets(str) ：输入一个串； puts(str) ：输出一个串； strcat(str1, str2) ：串联接函数； strcpy(str1, str2) ：串复制函数； strcmp(str1, str2) ：串比较函数； strlen(str) ：求串长函数；,例如： 标准C语言函数库string.h中， 提供下列串处理函数,在上述抽象数据类型定义的13种操作中， 串赋值StrAssign、 串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString 五种操作构成串类型的最小操作子集。,即：利用这些操作可以实现字符串的所有操作 （ClearString和DestroyString除外）。,例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。,算法的基本思想为：,StrCompare(SubString(S, i, StrLength(T),T ) ? 0,int Index (String S, String T, int pos) / T为非空串。若主串S中第pos个字符之后存在与 T相等的子串，则返回第一个 这样的子串在S中的位置，否则返回0 if (pos 0) n = StrLength(S); m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / while / if return 0; / S中不存在与T相等的子串 / Index,又如串的置换函数：,S 串,T 串,V 串,V 串,sub1,i,new 串,sub1,sub2,串的逻辑结构和线性表极为相似，区别 仅在于串的数据对象限定为字符集。,串的基本操作和线性表有很大差别。,在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”或子串作为操作对象。,在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值（即字符序列）即可。但在多数非数值处理的程序中，串也以变量的形式出现。,4.3 串的表示和实现,一、串的定长顺序存储表示,二、串的堆分配存储表示,三、串的块链存储表示,按照预先定义的大小，为每个串变量分配一个固定长度的存储区（一组地址连续的存储单元，用以存储串值）,一、串的定长顺序存储表示,#define MAXSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned char Sstring MAXSTRLEN + 1; / 0号单元存放串的长度,按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”。,串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为 “截断” 。,Status Concat(SString S1, SString S2, SString / Concat,例如：串的联接算法中需分三种情况处理：,T1S10 = S11S10; TS10+1S10+S20 = S21S20; T0 = S10+S20; uncut = TRUE; ,if (S10+S20 = MAXSTRLEN) / 未截断,else if (S10 MAXSTRSIZE) / 截断s2,else / 截断S1，并舍弃s2,T1S10 = S11S10; TS10+1MAXSTRLEN = S21MAXSTRLENS10; T0 = MAXSTRLEN; uncut = FALSE; ,T0MAXSTRLEN = S10MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; ,为每个串变量动态分配一个存储区，该存储区称为“堆”(heap)，也是一组地址连续的存储单元，用以存储串值。 利用C语言的动态分配函数malloc()和回收函数free()管理堆。 约定:串长也要存储 基本操作:仍为 “字符序列的复制”,二、串的堆分配存储表示,结构定义： typedef struct char *ch; / 若是非空串，则按串长分配存储区， / ch指向首地址，否则为NULL int length; / 串长度 HString; 特点：串长不受限制，较为灵活。,C语言中的串以一个0为结束符， 串长是一个隐含值。,这类串操作实现的算法为： 先为新生成的串分配一个存储空间，然后进行串值的复制。,Status Concat(HString / Concat,Status SubString(HString / 空子串 else / 求完整子串, Sub.ch = (char *)malloc(len*sizeof(char); Sub.ch0len-1 = Spospos+len-1; Sub.length = len; return OK; / SubString,三、串的块链存储表示,可用链表(块+链)来存储串值。由于串的数据元素是一个字符（ 8 位二进制数），因此 ，用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。 空间填补：用“#”填补最后一个结点,#define CHUNKSIZE 80 / 可由用户定义的块大小 typedef struct Chunk / 结点块结构 char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的链表结构 Chunk *head, *tail; / 串的头和尾指针 int curlen; / 串的当前长度 LString;,例如: 在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即: 同一行的串用定长结构(80个字符), 行和行之间用指针相联接。,实际应用时，可以根据问题所需来设置结点的大小。,这是串的一种重要操作，很多 软件，若有“编辑”菜单项的话， 则其中必有“查找”子菜单项。,4.4 串的模式匹配算法,初始条件：串S和T存在，T是非空串， 1posStrLength(S)。 操作结果：若主串S中第pos个字符之后 存在和串T值相同的子串 返回它在主串S中第pos个 字符之后第一次出现的位置； 否则函数值为0。,首先，回忆一下串匹配(查找)的定义:,INDEX (S, T, pos),下面讨论以定长顺序结构表示串时的几种INDEX (S, T, pos)算法,一、简单算法,三、KMP算法 (D.E.Knuth,J.H.Morris ,V.R.Pratt),二、首尾匹配算法,一、简单匹配算法,算法思想： 从主串S的第pos个字符起，和模式串T的第一个字符相比较，如相同，则继续比较后续字符，否则从主串的下一个字符起，再重新和模式串的字符相比较，依次类推，直至模式串T中的每个字符依次与主串S中的一个连续字符序列相等，则称匹配成功，否则称匹配不成功。,例：S=ababcabcacbab, T=abcac， 求INDEX(S, T, 1) 简单匹配算法：6趟扫描,int Index(SString S, SString T, int pos) / 返回子串T在主串S中第pos个字符之后的位置。若不存在， / 则函数值为0。其中，T非空，1posStrLength(S)。 i = pos; j = 1; while (i T0) return i-T0; else return 0; / Index,时间复杂度：o(n*m),先比较模式串的第一个字符， 不相等，则找主串下一位置， 如相等，再比较模式串的最后一个字符， 不相等，则找主串下一位置， 如相等，再按上述方法，继续比较模式串中从第二个到第n-1个字符。,二、首尾（同时）匹配算法,int Index_FL(SString S, SString T, int pos) i = pos; j = 1; m=i+T0-1; n=T0 while (i T0/2 ) return i-T0; else return 0; / Index,时间复杂度：o(n*m),例：S=ababcabcacbab, T=abcac， 求INDEX(S, T, 1) 首尾匹配算法：6趟扫描， 但是单个字符比较次数有所减少,KMP算法的时间复杂度可以达到O(m+n),问题：当 Si Tj ，出现不匹配时， Si是否可以不回溯？如果可以？ Si应和T的那个字符继续比较？,三、KMP算法 (D.E.Knuth,J.H.Morris,V.R.Pratt),例：S: abcabbabcabbabd, T: abcabbabd,i,j,j,不失一般性地，当 Si Tj 时， 已经得到的结果是： T1j-1 = Si-j+1i-1 若使i不回溯，则应使Si 和某个 Tk 相比较(kj)， 则应有： T1k-1 = Si-k+1i-1 因已有： Tj-k+1j-1 = Si-k+1i-1 则应有： T1k-1 = Tj-k+1j-1,反之，如果有： T1k-1 = Tj-k+1j-1 则Si 可以和 Tk比较，继续匹配过程,S: S1Si-j+1Si-j+2 Si-k+1 Si-1 Si T: T1 T2 T k-1 Tk Tj-k+1 Tj-1Tj,当SiTj时，i, j变化规律： 当T1不匹配时，应设置+i , j=1 , 从主串下一字符继续比较； 当存在T1k-1 = Tj-k+1j-1，则Si 应和（最大的） Tk比较（i不变，j=k = nextj）, 继续比较； 其他情况， i不变，j=1, 继续比较,模式串的nextj函数： j的下一位置k,int Index_KMP(SString S, SString T, int pos) / 1posStrLength(S) i = pos; j = 1; while (i T0) return i-T0; / 匹配成功 else return 0; / Index_KMP,时间复杂度: O(n),如何求nextj函数值 =递推过程 分析如下:,已知: next1 = 0, nextj = k，求nextj+1 =T1k-1 = Tj-k+1j-1,如果: Tj = Tk=T1k = Tj-k+1j,则: nextj+1= k+1=nextj+1=nextj+1,这实际上也是一个匹配的过程， 不同在于：主串和模式串是同一个串,若： Tj Tk，则需往前回朔，比较 Tj 是否等于 T nextk,可以仿造KMP算法，求nextj+1,void get_next(SString / get_next,j 1 2 3 4 5 6 7 8 模式 a b a a b c a c Nextj 0 1 1 2 2 3 1 2,时间复杂度： O(m),还有一种特殊情况需要考虑： 例如： S = aaabaaaab T = aaaab,next15=0 1 2 3 4,问题：有些比较是多余的，需改进 方法：用nextvali 代替nexti,void get_nextval(SString / get_nextval,时间复杂度： O(m),计算nextvalj的方法： （1）按照算法进行求解； （2） 先计算出nextj，再计算nextvalj.,例： T = aaaab next15=0 1 2 3 4 nextval15=0 0 0 0 4,KMP算法总结 1. 关于nextj函数的含义：当主串的Si与模式串的Tj比较而不相等时，nextj指示应与Si 继续比