文本索引和搜索.ppt

第五讲 文本索引和搜索,索引：是一种数据结构，它在关键词与包含该关键词的文档之间建立了一种映 射关系，从而加快检索的速度。,搜索：一般定义为在不使用索引技术时而快速在给定文本或文本集合中查找是 否出现某一关键词，通常也称为单模式匹配。,本讲就是针对以上三种索引结构和三种搜索算法来进行介绍和学习。,常用的文本索引技术：倒排文件、后缀数组和签名文件。,常用的文本搜索技术：BF算法、KMP算法和BM算法。,倒排文件结构,关于倒排文件在第四讲有所介绍，你还记得吗？,湖畔,夏夜,花园,蛙鸣,诗社,诗会,d1：log3/2：1,d2：log3/2：1,6,d1：log3：4,d2：log3：9,12,d2：1/2log3/2：15,d3：log3/2：2，10,d3：1/2log3：5,d3：1/2log3：13,词汇表,记录表,倒排文件一般由词汇表和记录表两部分组成。在记录表中可存储词在文档中出现的位置、文档编号等需要存储的信息。,d1：湖畔的夏夜常常很凉 d2：湖畔有家“湖畔”花园，花园里蛙鸣一片d3：“蛙鸣”诗社举办“蛙鸣”诗会,倒排文件另一种结构,湖畔：2,夏夜：1,花园：1,蛙鸣：2,诗社：1,诗会：1,d1：log3/2：1,d2：log3/2：1,6,d1：log3：4,d2：log3：9,12,d2：1/2log3/2：15,d3：log3/2：2,10,d3：1/2log3：5,d3：1/2log3：13,词汇表,记录表,显然，若记录表采用顺序存储，则不利于文档集合的更新。,湖畔有家“湖畔”花园，花园里蛙鸣一片,文档数,湖畔的夏夜常常很凉,“蛙鸣”诗社举办“蛙鸣”诗会,文档集合,倒排文件的使用,利用倒排文件进行检索，通常分为三个步骤：1、词汇表检索：即利用查询中的词检索词汇表。2、记录表检索：即检索出所有找到的词的记录表。3、记录表操作：即对检索出的记录表进行后处理，以实现相似度计算、摘要 生成等所需要任务。,显然，就倒排文件索引结构而言，词汇表检索的速度将决定该索引的效率。对于词汇表的组织一般可采用以下几种方式：,1、排序数组：即将词排序顺序存储，采用二分法查找。,2、散列：可按词的首字机内编码进行散列，但词的第二个字再散列就不再 适合散列处理，一般采用线性表存放。,3、B树：4、Trie树：B树和Trie树在数据结构中有所介绍。下面仅给出示例加以 说明。,B树与Trie树结构,B树结构,花园 蛙鸣,湖畔,夏夜,Trie树结构,诗会 诗社,记录表,湖,畔,记录表,花,园,诗,会,社,蛙,鸣,夏,夜,显然，Trie树结构不太适合于汉语词汇的组织。你还记得在第三讲切词中所采用的方法吗？,推荐方法：所有词存放在一个数组中，词所在的数组下标即为词的编号；而倒排文件中的词汇表即按此词编号顺序存储，即词编号就是词汇表中词所在数组的下标。在对查询文本切词时将查询中的词转换为对应的词编号，利用此词编号即可在词汇表中直接进行定位。这个过程相当于对词的散列。,推荐方法示例,d1：log3/2：1,d2：log3/2：1,6,d1：log3：4,d2：log3：9,12,d2：1/2log3/2：15,d3：log3/2：2，10,d3：1/2log3：5,d3：1/2log3：13,词汇数组,例如，查询为“花园”，在切词时即可获得该词编号为3，则通过 A3 可立即得到该词所对应的记录表信息。,湖畔,夏夜,花园,蛙鸣,诗社,诗会,1,2,3,4,5,6,1,2,3,4,5,6,倒排文件,A,倒排文件的存储,一般来说，检索系统的词汇表都是长期驻留内存的。而文档集合都是在磁盘上以文件的方式存储。,若检索系统的文档集合不大，即倒排文件的记录表完全可以存储在内存中，则此时在对每一个文档进行描述的过程中即可在内存中建立该倒排文件结构。正如第四讲所述。,若检索系统的文档集合非常庞大，以致于记录表无法存储在内存中。此时可考虑为每个词所对应的记录表建立一个文件。文件的命名可以利用词汇名或词汇组号。如图所示。显然，此时I/O次数就成为检索系统效率的瓶颈。,湖畔：2,夏夜：1,花园：1,蛙鸣：2,诗社：1,诗会：1,d1：log3/2：1,d2：log3/2：1,6,d1：log3：4,d2：log3：9,12,d2：1/2log3/2：15,d3：log3/2：2,10,d3：1/2log3：5,d3：1/2log3：13,词汇表,文件1,文件2,文件3,文件4,文件5,文件6,磁盘倒排文件的使用,所谓磁盘倒排文件：是指倒排文件的记录表以文件的方式存储在磁盘上。,显然，针对用户所提交的每一个查询词都必须通过读取磁盘文件来获得该词的记录信息。问题：如何才能最大限度地减少I/O次数呢？,方法是建立一个内存缓冲区。该缓冲区内维护一个小型的倒排文件子集。此时需要在检索系统中开发一个缓冲区管理程序，来负责缓冲区的维护。,磁盘,湖畔：2,夏夜：1,花园：1,蛙鸣：2,诗社：1,诗会：1,d1：log3/2：1,d2：log3/2：1,6,d3：1/2log3：5,d3：1/2log3：13,词汇表,缓冲区调度原则：1、当用户检索词记录表在缓 冲区中，则不必I/O操作,记录表内存缓冲区,2、若用户检索词记录表不在 缓冲区，则从磁盘读出对 应记录。若缓冲区有空，则放入缓冲区；若缓冲区 已满，则覆盖掉使用频率 最低的词条对应的记录表,磁盘倒排文件的维护,这里所谓的维护是指在倒排文件中插入、删除或更新文档或文档集合。,一般情况下，文档的更新采用删除再插入的方式来完成。,若检索系统的文档集变化较为频繁，则采用每次一文档的维护策略显然会降低检索系统的维护效率，尤其在磁盘倒排文件结构下。因此，常采用批处理的维护方式，即每次对一批文档进行插入或删除。,批插入策略如下：1、将一批待插入的文档子集在内存中构造成一个小型的倒排文件结构；,批删除策略如下：1、在内存中构造一个待删除文档的列表；,2、将内存中的小型倒排文件结构一次性地写入磁盘。,显然，若文档插入不及时会影响检索结果；插入过于频繁会影响系统的检索效率。这一矛盾需要根据实现情况进行平衡。,2、若用户检索结果中文档出现在述待删除列表中，则不给予检索输出；,3、定期或按某种阈值设置一次性在磁盘中删除列表中的文档。,显然，若待删除文档列表过长会影响检索效率；删除过于是频繁也会影响检索系统的效率。这也需要根据实现情况进行平衡。,词汇表的压缩,这里所谓的压缩是指如何能够减少所占用的存储空间。,1、若采用一个数组存储词汇表，则数组元素只能设为词的最大长度。,2字长词汇表A,1,n2,3字长词汇表B,1,n3,4字长词汇表C,1,n4,if nn2 则 An为记录表入口if n2 nn3 则 An-n2为记录表入口if n3 nn4 则 An-n2-n3为记录表入口,2、可考虑将等长的词分别存储在不同的词汇数组中。即长度为2的词汇构成一 个数组、长度为3的词汇构成一个数组、。,3、上述存储方式可以最大程度地压缩词汇表空间。缺点是词汇编号不再是该 词汇的数组下标，需要设计一种映射原则来实现词汇编号与其所在数组下 标的映射关系。设计的不好将影响检索效率。,4、如考虑如下策略：将词按字长大小顺序编号，且在切词词典中存储该编号 值。当在查询中切得某词编号为 n，则按如下规则判断。,记录表的压缩,1、在记录表中存有文档编号、词汇在文档中的位置等所需数据。,可考虑如下策略来压缩词汇位置值数据：对每一个文档分块，块数最多不超过256块；,该策略的优点是减少了记录表的空间，从而减少了I/O的次数。,以上所讨论的无论是磁盘倒排文件的批处理维护，还是压缩等问题，目的都是为了解决I/O访问次数。因为目前的硬件环境I/O速度是系统速度的瓶颈。,2、以词汇在文档中的位置为例，若采用一个字节来存储该数值，其最大位置值 只能是256，即文档长度不能超过256个汉字，这对于是文本文档是不够的。,3、若采用两个字节存储，则文档最大长度可达65536个汉字，对于一般的网页 性质的文档是够用的。但这也增加了记录表所占用的空间。尤其是文档集数 量非常庞大时，所增加的空间较为可观。,记录表中存储的词位置值改为块号，即采用一个字节存储块号。,当需要在文档中定位词的具体位置时，可根据块号在所在块内搜索来定位。,缺点是增加了检索时词汇在文档中定位时的运算负担。,文本的后缀,文本的后缀：是指从文本中任一位置开始直到文本末尾的子串。,例如：湖畔有家湖畔花园，花园里蛙鸣一片。该文本的后缀有：湖畔有家湖畔花园，花园里蛙鸣一片。有家湖畔花园，花园里蛙鸣一片。湖畔花园，花园里蛙鸣一片。花园，花园里蛙鸣一片。,1、一个文本的后缀有很多；,如将后缀最大长度限定为 6 个汉字，则上例文本的后缀为：湖畔有家湖畔 有家湖畔花园 湖畔花园花园 花园花园里蛙 花园里蛙鸣一 蛙鸣一片,2、后缀的起始位置一般以某个词开始，如后缀“畔有家”意义不大；,3、若文本较长，则很多后缀子串也较长。可限定后缀的最大长度；,4、在后缀中一般不保留标点等符号，也可考虑去掉停用词。,后缀数组,d2：湖畔有家湖畔花园，花园里蛙鸣一片。,1 3 5 7 10 13,湖畔有家湖畔：d2：1,有家湖畔花园：d2：3,湖畔花园花园：d2：5,花园花园里蛙：d2：7,花园里蛙鸣一：d2：10,蛙鸣一片：d2：13,查询：湖畔花园,检索策略：1、利用查询串在后缀数组中进行匹配；,后缀数组,可见，1、该检索方案能实现查询的精确匹配；2、检索过程能体现出检索词在查询中出现的顺序、距离的作用；3、缺点是当文档数量多时，占用大量的存储空间，检索速度慢。,2、按匹配的相似度排序，即为检索结果。,3、若查询串长度超过后缀长度，要么将查询串截 断，要么利用后缀数组中的位置值在文档中继 续完成匹配。,后缀树,d2：湖畔有家湖畔花园，花园里蛙鸣一片。,1 3 5 7 10 13,湖畔有家湖畔：d2：1,有家湖畔花园：d2：3,湖畔花园花园：d2：5,花园花园里蛙：d2：7,花园里蛙鸣一：d2：10,蛙鸣一片：d2：13,后缀数组,后缀树：即将后缀数组组织成Trie树结构。目的是提高检索的速度。,湖畔,有,花园,蛙鸣,有,花园,家,花园,里,一,家,湖畔,花园,湖畔,花园,里,蛙,蛙,一,片,d2:1,d2:5,d2:3,d2:7,d2:10,d2:13,显然树结构需要大量的磁盘空间，可能需要在磁盘间跳转。还需解决模糊匹配问题。,查询：湖畔花园,签名文件,签名文件：是一种基于散列技术的面向词汇的索引结构。,词汇的签名：即将每一个词用一个唯一的二进制数编码表示。,例如：技术001 000 110 010 教材000 010 101 001 检索000 000 011 110 信息101 000 100 001,文本分块：分块原则可按固定长度分块，或按固定块数分块。,例如：这是一本关于|信息检索的教材。|介绍了检索|的基本技术，|,000 000 000 000,101 010 111 111,000 000 011 110,001 000 110 010,签名文件,101 000 100 001 信息000 000 011 110 检索000 010 101 001 教材101 010 111 111,或,计算每个文本块的签名：即该块内的所有词按位进行“或”运算而得到。,签名文件的使用,这是一本关于|信息检索的教材。|介绍了检索|的基本技术，|,000 000 000 000,101 010 111 111,000 000 011 110,001 000 110 010,例如：在文本中搜索“检索”,技术001 000 110 010 教材000 010 101 001检索000 000 011 110 信息101 000 100 001,查询方法：1、利用待搜索词的签名与每个文本块的签名进行按位“与”运算；,例如，由于“检索”一词的签名为000 000 011 110，则计算如下：,000 000 011 110000 000 000 000000 000 000 000,与,000 000 011 110101 010 111 111000 000 011 110,与,000 000 011 110000 000 011 110000 000 011 110,与,可见上述文本的第二、三个块内可能包含“检索”词汇。再由块内搜索来确定。,2、若“与”运算结果与待搜索词的签名相同，则该块内可能存在该搜索词。若“与”运算结果与待搜索词的签名不同，则该块内不存在该搜索词。,词汇签名编码的重要性,这是一本关于|信息检索的教材。|介绍了检索|的基本技术，|,000,111,011,001,技术001 教材010 检索011 信息100,例如，查询“技术”一词，则由于“技术”一词的签名为001，则计算如下：,001000000,与,根据计算结果，文本的第二、三、四块内均可能包含“技术”一词，经块内搜索才可确定第二、三块内并不包含“技术”一词，即出现误检。显然误检的结果会浪费搜索时间。,001111001,与,001011001,与,001001001,与,误检的原因是词汇签名的编码不合理造成的。显然，词汇签名的编码越长且编码中1的个数越少，误检的概率越小。,签名文件的维护和特点,1、添加文档时，只需将文档分块，计算每个块的签名，并将每块的签名及指 针数据追加至签名文件即可。,000 000 000 000,101 010 111 111,000 000 011 110,001 000 110 010,2、删除文档时，只需要在签名文件中将该文档对应的块签名及其指针全部删 除即可。,3、应用签名文件时，可考虑将一个文档视为一个块。,4、经验表明，词汇签名的编码长度大约取文本平均长度的30%40%。,5、使用签名文件需要大量的磁盘I/O访问，故效率较低。,6、使用签名文件索引很难对词汇的频率和权重信息进行编码，很难支持排序 操作。,7、一般情况下，签名文件只适合于小规模文本集合的应用，在大多数应用中 还需要应用倒排文件。,文本搜索,文本搜索：可抽象为在一个长字符串中寻找短串（即模式串）的过程。,1、文本搜索技术的应用较为广泛。如在签名块内的定位或确定需要搜索；文本过滤一般只要求对文本进行一次搜索即可，无需建立索引；搜索引擎的后处理中对包含的关键词加亮显示，也需要文本搜索技术。等等。,2、许多搜索技术也可针对非文本数据进行。如在一个基因序列中搜索一个较短的基因片段等等。即只要能够抽象成在一个长序列中寻找短序列的问题都可考虑采用搜索技术。,3、本讲仅讨论单模式搜索（匹配）问题。,BF算法,算法示例：,T=a a b c b a b c a a b c a a b a b c,算法特点：思想简单、直接、算法效率低。,问题：这么一个简单的过程你能编程实现吗？,P=a b c a a b a b c,a b c a a b a b c,a b c a a b a b c,a b c a a b a b c,a b c a a b a b c,a b c a a b a b c,a b c a a b a b c,a b c a a b a b c,a b c a a b a b c,a b c a a b a b c,BF算法代码示例,T=a a b c b a b c a a b c a a b a b cP=a b c a a b a b c,i=1;j=1;while(i strlen(P)return i;else return-1;,i,j,问题：能在此基础上提高搜索速度吗？,显然匹配过程中发生不匹配时，长串中的 i 指针要发生回退。,BF算法分析,a a b c b a b c a a b c a a b a b c a b c a a b a b c,Ti-j+1 Ti-k+1 Ti-1 Ti Ti+1 P1 Pj-k+1 Pj-1 Pj Pj+1 P1 Pk-1 Pk Pk+1,T=P=,问题：此时能否达到 i 指针不回退就能确定 j 指针的下一次匹配过程的值？即 i指针不动，i 所指向的 b 与 P 串的哪一位对齐？从而开始新一轮匹配过程。,i,j,上述问题可抽象如下：,i,j,从上述的一般情况可见，当匹配至 Ti 与 Pj 不相等时，意味着 Ti-j+1Ti-1 与P1Pj-1 是相等的。若模式串向后移动，Ti 可以与 Pk 对齐时，则意味着Ti-k+1Ti-1 与 P1Pk-1 是相等的。亦即 Pj-k+1Pj-1=P1Pk-1。这说明什么？如何求 k 值？,BF算法分析（续）,Ti-j+1 Ti-k+1 Ti-1 Ti Ti+1 P1 Pj-k+1 Pj-1 Pj Pj+1 P1 Pk-1 Pk Pk+1,i,j,可见，当在模式串 Pj 位置发生不匹配时，则 Pk 完全可由 P1Pj-1 子串确定。确定原则为：满足 Pj-k+1Pj-1=P1Pk-1 的最大 k 值，即 P1Pj-1 子串的前面一部分子串与后面等长的一部分子串相等，满足该条件的最长子串，而该最长子串的长度加 1 就是 k 值，即 Ti 与模式串的第 k 位对齐。若没有子串满足上述条件，则 Ti 与模式串的第 1 位对齐。,1、按照这种思想，当发生匹配不成功时，模式串可一次性向后移动多位；2、显然，可事先求在当模式串中的每一位不匹配时，需要向后移动与 Ti 对齐 的位置 k 值，形成表格，以备查阅。3、按照这种策略形成的搜索算法称为KMP算法。,KMP算法中模式P的跳转表,1、当模式串 P 的第 1 位就不匹配时，Ti 必定与 P 的第 0 位对齐；,a b c a a b a b c,P=Shift,0 1 1 1 2 2 3 2 3,2、例如求 P 的第 4 位的 a 对应的 Shift 值：此时 P4 前面的子串为 abc，则 观察该子串中有前面最长子串 ab 与最后的等长子串 bc，两者不等；再依 次观察前面的子串 a 与后面的等长子串 c，也不相等；即不存在满足条件 的等长子串。则 P4 的 Shift 值为 1。,3、例如求 P 的第 7 位的 a 对应的 Shift 值：此时 P7 前面的子串为 abcaab，该子串长度为 6。则开始观察该子串中前面长度为 5 的子串 abcaa 与后面 等长的子串 bcaab，两者不等；再观察前面长度为 4 的子串 abca 与后面等 长的子串 caab，仍不相等；如此依次观察，当前面长度为 2 的子串 ab 与 后面等长的子串 ab，显然两者相等。所以，P7 的 Shift值为该最长子串 ab 的长度加 1，即值为 3。,KMP算法中模式P跳转表的优化,优化方法：for i=1 to strlen(P)if Pi=P Shifti then Shifti=Shift Shifti;,a b c a a b a b c,P=Shift,0 1 1 1 2 2 3 2 3,优化后的跳转表为：,a b c a a b a b c,P=Shift,0 1 1 0 2 1 3 1 1,当然，在求上述跳转表时，不必分两步来求解，完全可以一次性求出。,再次观察所求得的Shift值表。你能分析出什么？,观察 P4 下面的 Shift 值为 1，即当 Ti 与 P4 不匹配时，Ti 将与 P1 对齐。此时，由于 P4=a，Ti 与 P4 不匹配，即 Ti 一定不相等 a，而 P1 值也为 a，则 Ti 与 P1 对齐后必定产生不匹配。这说明上述Shift存在优化的可行性。,KMP算法的匹配过程,跳转表,a b c a a b a b c,P=Shift,0 1 1 0 2 1 3 1 1,T=a a b c b a b c a a b c a a b a b cP=a b c a a b a b c,可见，利用跳转表KMP匹配算法比BF算法的匹配过程速度明显加快。速度改善的程度与跳转表的值有关，若跳转表中的值越小，则匹配越快。反之，若跳转表中的值较大，例如，跳转表的值依次为 0、1、2、3、4、，则KMP算法与BF等同。问题：你能构造出具有上述特点的模式串吗？（好像不可能）,a b c a a b a b c,a b c a a b a b c,a b c a a b a b c,KMP算法跳转表求解示例,KMP算法的关键就是求跳转表。,a b c d e f g,P=Shift,0 1 1 1 1 1 1,a b c a b c a c a b,P=Shift,0 1 1 0 1 1 0 5 0 1,例1：,例2：,a a a a,P=Shift,0 0 0 0,例3：,a a a a b,P=Shift,0 0 0 0 4,例4：,你能编写出KMP算法的程序吗？当然算法中要包括求解跳转表。,KMP算法代码示例,unsigned int StrIndexByKMP(String T,String P,unsigned int pos)unsigned int TLen=strlen(T),PLen=strlen(P),i=1,j=0;if(TLen=0|PLen=0|pos TLen)return 0;unsigned int*Shift=(unsigned int*)malloc(SLen+1)*sizeof(unsigned int);/Create Shift table below.Shift0 is not used.Shift1=0;while(i SLen)return i-SLen;else return 0;,BM算法,算法示例：,T=a a b c b a b c a a b c a a b a b cP=a b c a a b a b c,算法说明：1、从模式串的最后一位开始向前进行匹配；2、显然，该匹配过程需求出模式串中每一个不匹配点之前最后一个 Ti 字符所 对应的位置值，从而构造一个跳转表；3、利用跳转表实现匹配过程。,a b c a a b a b c,a b c a a b a b c,a b c a a b a b c,a b c a a b a b c,a b c a a b a b c,a b c a a b a b c,BM算法跳转表求解,该跳转表的含义：（以表中的第 5 列为例，该列表示当 Ti 匹配至模式串的第 5 位 a 时发生不匹配，则有，1、Shifta5 表示此时的 Ti 值为 a，这是不可能的，故该值为空；2、Shiftb5 表示此时的 Ti 值为 b，则 Ti 应与第 5 位之前的最后一个 b 对 齐，故该值为 2；3、Shiftc5 表示此时的 Ti 值为 c，则 Ti 应与第 5 位之前的最后一个 c 对 齐，故该值为 3；4、跳转表的最后一行表示当 Ti 不是 a、b 或 c 时，则 Ti 必定可以与模式串的 第 0 位对齐。故跳转表的最后一行没有存在的必要。显然第1列也全为0。5、跳转表的行数由模式串中不同的字符个数决定。,跳转表,a b c a a b a b c,P=Shift,1 2 3 4 5 6 7 8 9 a 1 1 5 7 7 b 0 2 2 2 6 8 c 0 0 3 3 3 3 3 其它 0 0 0 0 0 0 0 0 0,BM算法跳转表求解示例,例1,b c d e,P=Shift,1 2 3 4 b 1 1 1c 0 2 2d 0 0 3 e 0 0 0,例2,a a a a,P=Shift,1 2 3 4 a,例3,a a a b,P=Shift,1 2 3 4 a 3b 0 0 0,BM算法关键还是求跳转表。,1、跳转表中的值越小，则匹配速度越快；2、当模式串中不同的字符个数越多，跳转表占 用的存储空间越多；3、若跳转表中某行元素全为零，则该行可不必 存储。4、一般情况下，若模式串很短（如长度13）则BF、KMP和BM算法效率差别不大；若字 母表很大，模式串也较长，则KMP算法的 效率一般较高；,关于BM算法代码请自行设计实现。,多模式匹配算法在单模式下的应用,1、多模式匹配方法当然也适用于单模式的搜索；2、关于多模式匹配方法在第三讲切词中已经详细介绍。,P=abcaababc,a,b,c,a,a,b,a,b,c,1,2,3,4,5,6,7,8,9,0,S ch S1 Act0 a 1 R0 非a 0 R 0#End1 b 2 R1 非b 02 c 3 R2 非c 03 a 4 R3 非a 04 a 5 R4 非a 1,S ch S1 Act5 b 6 R5 非b 16 a 7 R6 非a 27 b 8 R7 非b 18 c 9 R8 非c 29 3 Pr,令计数变量初值 Pos=1，在执行 R 动作的同时对 Pos 进行加 1。当到达 9 状态时，打印输出 Pos-9 的值（9为模式串长度）。利用该方法实现搜索时，在搜索之前需要建立模式的状态转换表。显然，该方法在多模式匹配时才会显出其优势。另外，生成状态转换与生成KMP算法的跳转表本质是一样的。,利用状态转换表的匹配示例,T=a a b c b a b c a a b c a a b a b c#1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19P=a b c a a b a b c,S ch S1 Act0 a 1 R0 非a 0 R 0#End1 b 2 R1 非b 02 c 3 R2 非c 03 a 4 R3 非a 04 a 5 R4 非a 1,S ch S1 Act5 b 6 R5 非b 16 a 7 R6 非a 27 b 8 R7 非b 18 c 9 R8 非c 29 3 Pr,S Pos0 11 20 21 32 43 50 50 61 72 83 94 10,Pos,S Pos5 116 122 123 134 145 156 167 178 189 19 输出 103 190 19 结束,匹配过程,状态转换表,