->293722
->394522
-*586332
—21241
—142141
->232641
-*404563
检索词字符树表
检索词字符树表的生成吸收了Aho和Corasick的思想，将所有检索词构造成有限自动机状态表，该表是一个由字符（英文字母、数字及其他符号）和状态层次组成的二维表，其结构如表4.11所示。
字符树表内窖根据状态转移函数填写，一个检索词结束就调用函数output（工）填写地址表指针。例如，检索词簇｛he,she,his，hers，shot,history｝，它们在檢索词地址表中的位置如表4.12所示，由表4.12生成的检索词字符树表见表4.13。
检索词地址表
检索词地址表中的位置检索词地址表中的位置
he5,25hers20
she8shot7
his9history15
构造表4.13的总体思路为：对每一个检索词总是从0状态出发，在0状态遇有该检索词首字母字符位置已登记过时，即#0，x）匹配成功，就顺其走下去。不论在何种状态下，凡是匹配失败，就构造一个新的状态。随着检索词的增多，该字符树表就会变得密起来，这就表明，虽然捡索词成倍增加，但字符树表的扩充是缓慢的。
为了更清晰地展示出该检索词族的字符树结构，图4-1给出了表4.I3的树形结构。图中凡是粗斜体字的元素为检索词的终极节点。
在实际的检索系统中，可以根据不同的检索词类型分别构造逻辑树状态表，如作者、主题词、分类代号等。
逻辑树法检索
逻辑提问式最终转换为逻辑树的3个表：主逻辑树表、检索词地址表、检索词字符树表。这3个表构成了用户检索提问档，整个检索主要依赖这3个表。
实际检索过程为：从文档中读取一条记录，用记录中的标引项（主题词、责任者、可供检索的其他著录项）去匹配相关的检索词字符树，匹配成功者，根据检索词地址指针去判断检索词地址表对应的检索登录区，若为“1”，表明该词已命中过，不需再处理；若为“0”，则将该项置为“1”，同时根据本行的“主表位置”字段去修改主逻辑树表。
主逻辑树表的检索处理较为复杂，因为它不只是处理指针指向的检索词项，而且要爬行到它的父项进行相关的处理和判断。具体处理过程为：在主逻辑树表中该词的“处理标志”栏中填上“1”，然后根据父项地址的指针找到父项行，对“检索处理”栏作加“1”运算，再査看“处理标志”栏。若为“1”，表示该子项已做过向上爬行处理，可返回进行下一词的处理；若为“0”，则根据“运算种类”做相应处理。
若为“+”运算，在完成标志栏置“1”，再向父项移动。
若为“*”运算，对“检索处理”与“子项个数”的值进行比较：相等，则在完成标志栏置“1”，再向父项移动；不等，就返回进行下一词的处理。
若为“一”运算，则顺着父项进行注销处理。
随着父项指针移动到顶行时，若该行的处理标志为“1”，则表示谪记录对于这一提问为命中文档，并将提问号和记录号写入命中文档。为了减少重复查询，实际应用时対于命中提问应采取屏蔽手段，确保该提问不再被这一记录访问处理。
与其他顺排检索算法比较，该算法虽然在分解逻辑提问式方面扫描次数可能多于其他算法（如表展开法），但由于判断次数的减少，其处理速度反而加快了；虽然该法对提问式的处理需要产生3个表，但它的处理是一次性的，不像展开表法分前、后处理两步；更为重要的一点是，顺排文档检索对提问式的处理是一次性的，而且是后台处理的，即使在加工提问式的过程中耗费一点机时，但为检索带来了极大的便利。
BF算法
第一个字符和模式T的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串S的下一字符起，重新与T第一个字符比较。直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值一1。
例如主串S=“abcdefg”，模式串T=“cde”，则模式匹配的过程如图4-2所示。
BF（Brute-FOrce）算法是一种串的模式匹配的算法。BF算法的设计思想是将主串S的第一次匹配abcdefgcdez=0,7=1
第二次匹配a$cdefgi=,7=0cde
第三次匹配abfdefgi=2,j=2ide四配成功图4-2串的匹配过程
对应于不同的串的存储结构，串的模式匹配的具体实现也不一样。
下面给出Brute-Force算法的实现。typedefstruct{charstr[MaxSize]；intlength；
,}String；
intBFIndex（StringS,intstart,StringT）{inti=start,j=0
while（i
{if（S.str[i]==T.str[j]）{i++；j++；}else{i=i-j+l；j=O；}
}
if（j==T.length）v=i-T.length；elsev=-1；returnv；
}
KMP算法
KMP（Knuth-Morris-Pratt）匹配算法是由D.E.Knuth、J.H.Morris和V.R.Pratt同时发现并改进的一种快速的模式匹配算法。
待解决的问题
假设P为给定的子串（也叫模式串），T是待査找的字符串（也叫目标串），要求从T中找出与P相同的所有子串，这称为模式匹配问题。下面先来看个例子。
T:ht2h……tn-
P：PoPlP2p??Pm——
从T的最左边开始比较，使得TK=PK，宁波seo优化则匹配成功。
解决模式匹配问题的方案
最简单和最直接的模式匹配算法是，用P中的字符依次与T中的字符进行比较，遇到不相等的字符，则可将P右移一个字符，重新进行比较，直到某次匹配成功或者到达P的最右字符移出T为止。
若P=“aaaba”，T=“aaabbaaaba”，则匹配过程如图4-3所示。
T：aaabbaaabaP:?aaaba
aaaba
aaaba
图4-3模式匹配的过程
从上面分析可以看出，最坏的情况是：每次比较都在最后一个字符出现不等，每趟最多比较M次，最多比较N-M+1趟，S的比较次数最多为M（N—M+1），时间复杂度为O（湖）。在P右移一位时，不管上一趟比较的中间结果是什么，因此回溯是不可避免的（如前3个aaa不需要一位一位的移）。
KMP算法解决匹配的主要问题
KMP算法需要解决匹配的主要问题是：当字符串比较出现不等时，确定下一趟比较前应该将P右稃多少个字符？P右移后，应孩从哪个字符开始和T中刚才比较时不等的那个字符继续开始比较？
通过朴素模式匹配的例子来引出问题。在第一次比较过程中失败的是P的第5个字符a，这表明P的前4个字符是成功的。模式P的第4个字符b在它的前3个字符中并未出现。因此，在下一次比较时候，至少要将P向后移4个字符；再看P的第一个字符与最后一个字符是相同的，因此将P右移4个字符后，再从第一个字符比较，也是不等的。综上所述，应该将P右移5个字符，再从P的第0个字符和T的第5个字符开始比较。
KMP算法的核心是：KMP算法借助于一个辅助数组next来确定当匹配过程中出现不等时，模式P右移的位置和开始比较的位置。next[/]的取值只与模式P本身的前/+1项有关，而与目标T无关。匹配过程中遇到A不等于。时，若next[/]>0,则应将P右移Z—nextU]位个字符，用P中的第next[G个字符与——进行比较；若next[i]=—1，P中的任何字符都不必再与——比较，而应将P右移/+1个字符，使扒和——+1从新开始下一轮比较。
因此只要计算出与模式P相关的next数组，按上面的含义，就可以很容易地给出串的匹配算法。以P=“01001010100001”为例。
Z：0123456
P:0100101
j（next[z]）：-1001123
修正（next[z]）：-10--13
例子中的7（nex:t[d）为未修正前的next数组。
例如，要算next[2]的值，P本身的前2个字符为01，在这个字符串01中，找到左右相同的最大字符串，此字符串所含字符的个数就为nextD]的值。将字符串“01”和“01”比较，左右相同的字符串不存在，所以next[z]-0o又如，要算next[6]的值，P本身前6个字符为010010，此字符串中前3个字符串和后3个字符串相等，所以左右相同的最大字符串为010,个数为3。因此next[/]=3。
再如，要算next[5]的值，P本身前5个字符为01001，此字符串中前两个字符串和后两个字符串相等，所以左右相同的最大字符串为01,个数为2。因此next：/>2o下面给出实现KMP算法的C程序。
Cmystring；：GenKMPNext（int*next,CMyString*s）{inti=0；j=-1;
next[0]=-1；while（ilength）
{
while（j〉=0&&s-〉str[i]!=s-〉str[j]）j=next[j]；i++;j++;
if（s-〉str匸==s-〉str[j]）next[i]=next[j];elsenextQi]=j；}
}
//////////////串类的find（）方法KMP匹配算法////////////intCMyStringI:find（constCMyString*S）{
inti,j,*next=newint[s-〉length];GenKMPNext（next，s）；
for（i=0,j=0;i if（s->str[i]==str[j]）{i++,j++;}elseif（next[i]〉=0）i=next[i]；
else
}
if（i>=s->length）returnj-s-〉length;else
return-1
BM算法
BM（BOyer-MOOre）算法是一个精确字符串匹配的算法，它可以实现髙效率的模式匹配。BM算法的关键和KMP类似，也是构造一个辅助数组，不过，不同于KMP算法的是，BM算法的辅助数组大小只和匹配串的字符集大小相关（一般情况下也就是ASCII字符集，256个字符），其内容和模式串相关，辅助数组的内容即是模式串的索引。
给定一个特定的字串P（通常又称为模式），在一个大的文本T中进行査找，确定P是否在T中出现，出现则给出相应位置。BM算法的基本思想是先对模式P进行预处理，计算两个偏移函数：BadChar（坏字符）和Goodsuffix（好后缀），然后将文本和模式对齐，从右往左进行匹配，当文本字符与模式字符不匹配时，根据函数BadChar和Goodsuffix计算出的偏移值，取两者中的大者。将文本指针往右移，匹配成功则予以输出。
BadCharEa]—min{j|—1且—1—=
如果a未在模式字符中出现，则
BadCharQa]=m
suff[/]=max{^1T[z一是+1，？“，Z]=—是，”？，zn—1]，即suff是P[0…；]和T的最长一般后缀。计算suff数组使得计算Goodsuffix函数变得简洁。
Goodsuffix[??7—1—suff[/]]=m——i在某次匹配中，文本字符T[/+J]与模式字符p[y]匹配不成功，按BM算法，则比较BadChar[T[z+J]]—（W—1—））与Goodsuffix[j]的值，取大者作力偏務量，然后将文本指针i往后移动偏移量，然后再从后往前进行比较。
如果模式被扫描完，则找到了模式的一次出现，文本指针右移GoodSuffix[0]。
以上述方式处理文本直至文本末尾，可以找出模式的所有出现位置。
从上面可以看出，BM算法用了3种有效的方法：从右到左扫描，坏字符规则和好后缀规则。
从右到左扫描的意思是从最后一个字符开始向前匹配，而不是习惯上的从开头向后匹配。
坏字符规则是，从右到左的扫描过程中，发现Z,与久不同，如果P中存在一个字符么与心相同，且々＜/，那么就将直接将P向右移使九与对齐，然后再从右到左进行匹配。如果P中不存在任何与6相同的字符，则直接将P的第一个字符与Z,的下一个字符对齐，再从右到左进行比较，如图4-4所示。
T:abcbadft
P：cbaxad
P：cbaxad
图4-4比较过程1
用R表示字符T在P中出现的最右位置，此例中R=2。可以看出使用从右到左扫描和坏字符规则可以跳过T中的很多位置不去检查，从而使时间复杂度低于线性。
好后缀规则是，从右到左的扫描过程中，发现Z,与久不同，检查一下相同的部分Z是否在P中的其他位置，出现，如图4-5所示。
如果￡与，的前一个字母不相同，就将P向右移，使，与T中的i对齐。
如果/没有出现，则找到与Z的后缀相同的P的最长前缀：r，向右移动P，使：r与T中的后缀相对应。
T：abcbadftbcfaqVtbce
P：cbcabceabc
cbcabceabcf
图4-5比较过程2
可见，并不是将P向右移让外与对齐，而是让p2与对齐，因为A与外不相同。用LG）表示？的最大位置，此例中，L=3。
:123456789101112131415161718
T：abcbadfTbcfaqVtbce
P:bc‘、cabceTbc
本文转载自
宁波seo优化www.leseo.net
补充词条：宁波网站seo
宁波网站排名优化
宁波seo外包
宁波谷歌seo
宁波谷歌优化
