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

-精选财经经济类资料- -最新财经经济资料-感谢阅读- 1 实验报告自动批阅中关键字匹配的 算法分析 【摘 要】实验报告自动批阅实 现方案需用到关键字搜索、匹配技术。 实验报告中多为多关键字，主要解决多 关键字匹配问题，把单关键字作为多关 键字特殊情况处理，本文就关键字匹配 问题分析其算法。 中国论文网 /5/view-5892322.htm 【关键词】实验报告自动批阅； 关键字匹配；算法 一、关键字匹配技术 多关键字匹配任务即在文本 Y 中 发现所有包含于 X 中的关键字，并记录 相关信息进行存储和处理。经查阅，得 到一种较合适的算法，即将单关键字匹 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 2 配 Qs 的思想应用到多关键字匹配算法 中，对多关键字 Sun Wu 算法改进，使 用更精确的跳跃距离计算法，使得最大 跳跃距离达到 m+1 且平均跳跃距离更 大；使用不同的部分匹配判断条件，提 高空间利用率和算法效率。把该算法记 为 QMS（quick multipattern search） 算法。 二、Sun Wu 算法 Sun Wu 算法以单关键字匹配的 Boyer-Moore 算法为基础。与 BM 不同 是 Sun Wu 算法使用长度为 B 字符块代 替坏字符，B 实际取值为 2 或 3，其匹 配阶段主要步骤： 1、使用当前窗口最后 B 个字符 （Ym-b+1， ，Ym）计算散列值 h。 2、检查 SHIFTh取值：如果 SHIFTh0，跳跃相应距离并转 1 继续； 否则转 3。 3、计算当前窗口前缀的散列值 text_prefix。 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 3 4、对于 HASHh指向列表中的 指针，检查是否有等式 PREFIXP =text_prefix 成立。如成立，直接将真实 关键字和文本作匹配，发现匹配则报告。 5、将当前窗口向后跳跃一个字 符，转 1 继续。 三、QMS 算法分析 获得高匹配率，克服 Sun Wu 算 法不足，增大跳跃距离，将 QS 算法与 Sun Wu 算法结合实现。直接将 QS 算法 用于多关键字匹配，其困难是随着被处 理的关键字数量增大，正文中越多的字 符出现在某些关键字中，导致跳跃距离 快速减小和算法效率快速降低。QMS 继承 Sun Wu 算法的字符块思想，并继 承使用散列技术和前缀表减少需要实际 进行匹配的关键字数量。 1、预处理过程 首先计算全部关键字最短距离 m，并且在预处理阶段只考虑每个关键 字前 m 个字符，即假设所有关键字长度 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 4 都为 m。在匹配阶段尝试窗口大小为 m。描述 SHIFT 表初始化， HASH 表和 PREFIX 表的初始化参见 Sun Wu 算法 预处理过程。 由于每次跳跃距离至少为 1，在 计算跳跃距离时考虑当前窗口的紧邻后 一个字符带来的信息。将该字符和当前 窗口的最后 B-1 个字符一起考虑，作为 获得跳跃距离的根据。设该字符块为 Kb=k1，kb，该 Kb 通过一个散 列函数映射为一整数，即访问 SHIFT 表 的索引值。SHIFT 表中对应项的值确定 此时可以安全跳过的字符数。设 Kb 的 散列值为 i，针对 Kb 在关键字集合中的 出现情况，按照如下规则计算跳跃距离： （1）Kb 作为子串出现在某些关 键字中。设 Kb 在所有关键字中最右的 出现位置为 q，此时可以安全的跳跃字 符数为 m-q+1，即 SHIFTi=m-q+1。 （2）Kb 不出现在任何关键字中， 但是其某一长度的后缀出现在某些关键 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 5 字的前缀中。设该后缀的长度为 L（0LB ） ，此时可以安全的跳跃 m- L+1 个字符，即 SHIFTi=m-L+1。 （3）既不属于情况（1） ，也不 属于情况（2） 。此时可以安全地跳跃 m+1 个字符，即 SHIFTi=m+1。 为生成 SHIFT 表，将其所有项的 初始值设为 m+1，然后逐一使用 X 中 的每一个关键字来修改 SHIFT 表。设 XiX 为 X 中的第 i 个关键字，对 Xi 的处理分为 2 步： （1）对 Xi 的每一个长度为 B 的 子串 Aj-b+1， ，Aj，使用散列函数 计算其散列值 h，并将 SHIFTh项设为 其当前值与 m+1-j 中的较小者。 （2）处理 Xi 长度为 I 到 B-1 的 前缀：当 B 取值为 2 时，对于任何字符 块 Kb=Vc+Xi1，Vc，计算其散列 值，并将 SHIFT 中相应项设为当前值与 m 的较小者，当 B 的取值为 3 时，对于 任何字符块 Kb=Vc+Xi1+Xi2， -精选财经经济类资料- -最新财经经济资料-感谢阅读- 6 Vc，计算其散列值，并将 SHIFT 中 相应项设为当前值与 m-1 的较小者；对 于任何字符块 Kb=Vc1+Vc2+Xi1， （Vc1，Vc2）计算其散列值，并将 SHIFT 中相应项设为当前值与 m 的较 小者。 经过预处理，SHIFT 表比 Sun Wu 算法中的更准确，具有更大跳跃距 离，作用更加单一。 2、匹配过程 每次尝试之后，不管成功与否， 使用 Kb 计算散列值并查找 SHIFT 表获 得跳跃距离。匹配阶段的主循环主要包 括如下步骤： （1）使用当前窗口的最后 B 个 字符（Ym-b+1 ，Ym ）计算散列 值 h； （2）检查 HASHh的取值：如 果 HASHh非空，转 3，否则转 5； （3）计算当前窗口的前缀的散 列值 text_prefix； -精选财经经济类资料- -最新财经经济资料-感谢阅读- 7 （4）对于 HASHh指向列表中 的每个关键字，检查等式 PREFIXP =text_prefix 是否成立。如成立，将真实 关键字和正文作逐字符比较，如发现匹 配则报告； （5）使用当前窗口的最后 B-1 个字符和当前窗口下一个字符（Ym- b+2，Ym+1）计算出散列值 h1，向后跳跃 SHIFTh1个字符，转 1 继续。 四、举例 假定搜索文本：模板等级优秀实 验名称负反馈放大器 搜索关键字：实验名称 1、使用当前窗口的最后 4 个字 符，计算散列值 h；即得到：Wb=模板 等级， m=4。 2、检查 HASHh值为空，则取 当前窗口的最后 3 个字符和当前窗口的 下一个字符。即得到：Kb=板等级优。 3、计算 Kb 的散列值，确定跳跃 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 8 字符 SHIFTh1；因为此时 Kb 不是关 键字的子串，且 Kb 的后缀“秀” 并不是 某一关键字的前缀，所以此时可以安全 地跳跃 m+1 个字符，即 SHIFTi =m+1=5。得到新窗口： Wb=秀实验名。 4、计算当前窗口散列值 h，此时 HASHh值非空，进行当前窗口的前缀 的散列值 text_prefix 的计算，并检查等 式 PREFIXP=text_prefix 是否成立。结 果不成立，发生部分匹配。 5、取当前窗口最后 3 个字符和 当前窗口下一字符。即得到：Kb=实验 名称。因为此时 Kb 是关键字子串，且 Kb 在所有关键字中最右出现位置为 4， 此时可以安全跳跃字符数为 m-4+1，即 SHIFTi=