面向用户会话的Web应用测试用例生成及其优化

测试是保证Web应用的高质量、高可靠性的一种有效手段,然而,由于其特殊性和复杂性,使得传统的测试理论与方法很难直接运用到Web应用的测试中,一个关键的问题就是测试用例的生成及其优化。提出了一种将遗传算法用于基于用户会话的Web应用测试用例生成及其优化的方法。通过分析服务器的用户日志,清除无关的数据,得到大量有意义的用户会话,利用约简技术进一步剔除其中的冗余。为便于测试的重用和并发执行,将用户会话进行合理的分组,每一组称为一个测试套件,并在测试套件之间以及测试套件内部(测试用例之间)进行初步的优先排序。这样就得到了初始的测试套件和测试用例,以及它们的初始执行顺序。这种初始的测试方案离最优解的近似程度还不是很高,需进一步利用遗传算法对它们进行分组优化并优先排序。同时提出了一种利用交叉算子产生新的测试用例的方法,新的测试用例可以检测不同用户共享数据时可能带来的冲突而产生的错误。

基于局部变化性的改进编辑距离算法

针对经典编辑距离算法在求解字符串相似度时计算效率过低的问题,提出一种改进的编辑距离算法。先求得2个字符串的最长公共前缀和最长公共后缀,再根据经典编辑距离算法得到2个字符串剩余部分之间的编辑距离,由反证法证明该编辑距离即为2个原始字符串的编辑距离。在此基础上,分析改进算法的优势并将其应用于网页篡改检测中。实验结果表明,与经典算法相比,改进算法在求解同一网址的网页相似度时具有更高的计算效率。

基于邻接字符对的三元后缀树全文索引模型

传统后缀树全文索引模型的索引建立复杂、难以维护,且空间消耗大。为此,提出一种改进的后缀树全文索引模型。将一棵完整后缀树划分为若干个三元后缀树,从而简化后缀树的组织结构,便于其建立和维护索引。将邻接字符对的公共前缀作为后缀树的根结点,以降低模型的空间消耗,提高查询效率。实验结果表明,与传统模型相比,该模型具有较高的时空效率。

基于后缀结构进行数据块优化的重复数据删除系统

为进一步提高重复数据删除系统的性能,提出基于数据分块的后缀数组SA和最长公共前缀LCP进行数据块优化的重复数据删除系统。系统首先将输入的数据流进行第一次分块,识别出相同的分块并给分块编号,创建分块编号序列的SA和LCP表,识别出最大重复队列和非重复数据块,进一步得出优化的超级块大小,然后以超级块为单元进行第二次数据分块并保存数据压缩结果。实验表明,相比于固定分块,该系统能实现给定输入流较好的压缩性和数据重构性。

一种嵌入式导航终端的兴趣点数据处理方法

嵌入式导航电子地图是一种精简的特殊电子地图,在现代车载导航系统中具有重要应用。实际的应用要求导航系统对卫星信号作出快速反应并对其数据进行实时更新,但由于设备存储资源的相对不足和软硬件功能的限制,其实际的数据存储具有显著的容量存储和读出限制。为了提高导航电子地图设备对数据的存储和快速查询性能,提出一种处理兴趣点数据POI(Point of Interest)的方法。该方法在提取导航电子地图数据所需要的POI数据时建立网格空间索引,对POI的数据按照网格进行存储;根据POI数据的特点,对字符数据寻找公共前缀子串,将其存储为公共前缀子串表,POI字符数据中如果存在公共前缀子串,则记录其在公共前缀子串表中的位置。以北京部分地图为例对该方法做调试,使用该方法 POI地图原始数据大小由原来的170 MB减小到35MB,空间查询200个POI花费的平均时间由3秒缩短至150 ms。该方法具有较高的压缩率和空间查询效率,对于导航电子地图中的POI数据处理具有较强的适应性。

基于后缀数组的分词技术

中文分词技术是机器翻译、分类、搜索引擎以及信息检索的基础,但是,互联网上不断出现的新词严重影响了分词的性能,为了提高新词的识别率,建立待分词内容的后缀数组,然后计算其公共前缀共同出现的次数,采用阈值对其进行过滤筛选出候选词语,实验结果表明,该方法在新词识别方面有一定的优势。

一种有效的后缀树建立方法

基于自顶向下的后缀树建立思想,提出一种分步建立后缀树的方法。首先对字符串中所有后缀按照字母表顺序进行排序,然后求出有序相邻后缀之间的最长公共前缀,并根据后缀顺序和最长公共前缀建立后缀树。该方法无需使用后缀链,并且可以在线性时间建立后缀树。

Fibonacci字与Fine-Wilf定理的推广

从任意两个Fibonacci字之间的公共前缀长度的研究出发,讨论了其与字的组合学中重要定理-Fine-W ilf定理的关系;用初等数论知识对Fine-W ilf定理进行了推广,得出:设u和v是A上的两个字,gcd(|u|,|v|)=1,若存在p、q使得up和vq有长度至少为|u|+|v|-k的公共前缀,则u和v中至多出现k个不同的字母.

入侵检测系统的融合模式匹配算法

运用入侵检测系统的融合模式匹配算法取得待匹配的字符串集合的公共前缀与文本匹配,若为单模式匹配则匹配结束,若为多模式匹配则将文本被分割成的字符串集中的字符串分别与模式串匹配,该融合算法对单模式匹配和多模式匹配均提高了效率,识别了正文的大小写。

基于DC3算法的非编码区序列最大串联重复识别

非编码区信息结构分析是目前生物信息学研究的热点之一。运用DC3算法构建的后缀数组以及最长公共前缀(LCP)作为辅助工具构造一个算法,用于对非编码区中存在的重复序列进行搜索,进而研究可能与其相关的功能元件,从而揭示出非编码区的结构信息。通过实验证明其实用性。

基于后缀数组检测函数克隆

为了提高检测效率,提出了一种新的函数克隆检测方法。该方法对传统后缀数组进行了改进,优化了基于后缀数组的算法。利用该算法可高效查找重复函数子串,进而检测出Type-1和Type-2类型的函数克隆。同时开发出相应的函数克隆检测工具FCD以实现该方法,并检测了24款C语言的开源软件。实验结果的分析验证了FCD能高效检测软件中的函数克隆。

维吾尔文后缀树构造算法的设计与实现

为用后缀树聚类算法对维吾尔文网页进行聚类,通过分析可扩展后缀树和维吾尔文的特点设计了维吾尔文后缀树构造算法。实验结果证明该方法能够在线性的时间范围内构造维吾尔文后缀树,并用它来对维吾尔文网页进行聚类。