实验报告自动批阅中关键字匹配的算法分析

《实验报告自动批阅中关键字匹配的算法分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验报告自动批阅中关键字匹配的算法分析【摘要】实验报告自动批阅实现方案需用到关键字搜索、匹配技术。实验报告中多为多关键字，主要解决多关键字匹配问题，把单关键字作为多关键字特殊情况处理，本文就关键字匹配问题分析其算法。【关键词】实验报告自动批阅；关键字匹配；算法一、关键字匹配技术多关键字匹配任务即在文本Y中发现所有包含于X中的关键字，并记录相关信息进行存储和处理。经查阅，得到一种较合适的算法，即将单关键字匹配Qs的思想应用到多关键字匹配算法中，对多关键字SunWu算法改进，使用更精确的跳跃距离计算法，使得最大跳跃距离迖

2、到m+1且平均跳跃距离更大；使用不同的部分匹配判断条件，提高空间利用率和算法效率。把该算法记为QMS(quickmulti—patternsearch)算法。二、SunWu算法SunWu算法以单关键字匹配的Boyer-Moore算法为基础。与BM不同是SunWu算法使用长度为B字符块代替坏字符，B实际取值为2或3,其匹配阶段主要步骤：，Ym)1、使用当前窗口最后B个字符(Ym-b+1,计算散列值h。2、检查SHIFT[h]取值：如果SHIFT[h]〉O，跳跃相应距离并转1继续；否则转3。3、计算当前窗口前缀的散列值t

3、ext_prefix。4、对于HASH[h]指向列表中的指针，检查是否有等式PREFIX[P]=text_prefix成立。如成立，直接将真实关键字和文本作匹配，发现匹配则报告。5、将当前窗口向后跳跃一个字符，转1继续。三、QMS算法分析获得高匹配率，克服SimWu算法不足，增大跳跃距离，将QS算法与SunWu算法结合实现。直接将QS算法用于多关键字匹配，其困难是随着被处理的关键字数量增大，正文中越多的字符出现在某些关键字中，导致跳跃距离快速减小和算法效率快速降低。QMS继承SunWu算法的字符块思想，并继承使用散列

4、技术和前缀表减少需要实际进行匹配的关键字数量。1、预处理过程首先计算全部关键字最短距离m，并且在预处理阶段只考虑每个关键字前m个字符，即假设所有关键字长度都为m。在匹配阶段尝试窗口大小为m。描述SHIFT表初始化，HASH表和PREFIX表的初始化参见SunWu算法预处理过程。由于每次跳跃距离至少为1，在计算跳跃距离时考虑当前窗口的紧邻后一个字符带来的信息。将该字符和当前窗口的最后B-1个字符一起考虑，作为获得跳跃距离的根据。设该字符块为Kb=kl，……,kb,该Kb通过一个散列函数映射为一整数，即访问SHIFT表的

5、索引值。SHIFT表中对应项的值确定此时可以安全跳过的字符数。设Kb的散列值为i，针对Kb在关键字集合中的出现情况，按照如下规则计算跳跃距离：(1)Kb作为子串出现在某些关键字中。设Kb在所有关键字中最右的出现位置为q，此时可以安全的跳跃字符数为m-q+1,即SHIFT[i]=m-q+l。(2)Kb不出现在任何关键字中，但是其某一长度的后缀出现在某些关键字的前缀中。设该后缀的长度为L(0