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

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

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

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

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

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

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

为进一步提高重复数据删除系统的性能,提出基于数据分块的后缀数组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个不同的字母.

无线通信OFDM系统相位噪声自适应补偿

将基于循环前缀的时域相位跟踪与基于频域导频的CPE校正技术相互结合,提出了一种旨在提高无线OFDM接收机抵抗相位噪声能力、低复杂度的相位噪声自适应补偿方案,时域跟踪可以对信道相位偏移低频成分起到初步的抑制作用,而在频域则通过引入导频子载波可信度判决机制,将CPE估计放在信道判决前进行,更为精确地消除由频率选择性相位偏移对CPE估计所带来的影响.仿真结果表明,本方案能够显著改善OFDM接收机在相位噪声条件下的系统误码率性能.