一种基于数据划分的字符串相似连接外存算法

字符串相似连接操作具有广泛应用,因而将着重研究基于编辑距离的字符串相似连接。而现有的字符串相似连接算法大多为内存算法。实际应用中的数据集越来越大,有必要针对超大规模数据集研制字符串相似性连接外存算法。利用组合频率向量划分数据集,并提出了基于编辑距离的字符串相似性连接外存算法框架,证明了磁盘调度问题的难度并提出了不同的启发式磁盘调度方法。此外,还提出了基于该外存算法框架实现字符串相似性连接增量式计算的方法。实验结果表明,数据划分方法可以有效地过滤不相关的数据子集;磁盘调度算法能够有效减少磁盘IO次数;外存算法是高效的;增量式计算方法能够高效地处理数据更新。     

浅谈字符串模式匹配的常用算法

简要叙述了字符串的定位操作即字符串模式匹配的基本概念和算法,探讨了字符串模式匹配操作的最基本的BF匹配算法以及改进以后的模式匹配的KMP算法。     

应用软件特征字符串挖掘技术

文章探究了如何利用频繁项挖掘技术寻找应用软件通信数据包中的特征字符串,该特征字符串具有大量重复出现,且在一台固定计算机上的某一应用软件通信中保持不变的特点。文中用几个认可度较高的应用软件为例,验证了用频繁项挖掘技术寻找特征字符串的正确性并对实验结果做了对比说明,指出该特征字符串技术可用于识别计算机应用软件,以及计算机的追踪和防盗。     

基于藏文元音构件的字符串匹配算法

本文提出了一种适用于藏文字符集的字符串匹配算法——TVM(Tibetan vowel matching)。TVM算法利用藏文拼读时的音节特点,将藏文字拆解为构件,通过元音字符查找并匹配,可以有效提高藏文字符串匹配效率。实验结果表明,本文所提算法在处理藏文字符串匹配问题时具有较高的效率,可很好地应用于藏文字取证、拼写检查器以及抄袭检测等领域。     

基于字符串编辑距离的图像检索算法

从大规模图像数据库中快速、有效地检索出相关图像是目前一个重要又富有挑战性的研究课题,为提高图像检索效果,提出了一种基于字符串编辑距离的图像检索算法。受图像感知哈希算法的启发,该算法首先将图像大小归一化并压缩色彩空间,并把图像特征动态映射成字符串形式,然后采用编辑距离进行字符串相似度计算从而实现图像检索。该算法不仅考虑到图像中的颜色特征,而且将字符串编辑距离引入到图像检索中,利用字符串相似度评价图像的相似性,在提高检索率的同时又加快了检索速度。采用不同类型的图像进行实验,实验结果表明,该算法具有较高的检索效率。     

探究基于MapReduce的top-k查询算法

借助不断发展的互联网技术,各种数据在数量上与类型上呈现出爆炸性增长的态势。原有的数据处理已经不能满足现在的数据查询,因此在发展与现实需要的基础上出现了基于Map Reduce的top-k查询算法,这种建立在top-k查询方式的基础上联合Map Reduce可以大大提高查询效率。文章就以基于Map Reduce的top-k查询算法为研究重点进行展开论述,在简单阐述top-k查询算法、Map Reduce的基础上分析两者结合之后的性能。     

ERSearch:一种高效的子图查询算法

子图查询是图数据库研究中的一个重要问题,许多方法基于“过滤-验证”策略进行子图查询,算法研究的重点为快速找到有效的特征集.通过对特征模式在数据图集中的嵌入信息进行分析,离线建立基于重叠关系、邻接关系和近邻关系的嵌入关系索引,提出基于嵌入关系的子图查询算法ERSearch.在给定查询图后,利用特征共现关系与特征嵌入关系联合进行过滤操作,并将过滤阶段的嵌入关系比对结果用于验证过程,提高验证效率.在真实及模拟数据上的实验表明,通过与PathIndex等方法的对比,ERSearch算法有效缩减了候选集的规模,能有效提高过滤与验证阶段的执行效率.     

基于 GPU 加速的并行字符串匹配算法

在分析了经典的串行字符串匹配算法（BF ,KMP ,BM ,BDM ,Shift -And/Shift -Or ,ZZL）基础上,对ZZL算法的预处理过程进行改进,并结合GPU的单指令多线程的并行计算特点,对ZZL算法进行并行改进,以达到处理大规模数据的速度提升。     

基于FPGA的字符串匹配算法

在全字节比较法的基础上提出了一种基于FPGA的子字符串LUT重用算法。该算法通过位宽扩展．以及流水线问字符串、LUT共享，用低端FPGA成功解决了高速字符串匹配问题，与传统字符串匹配算法相比．该算法大幅缩小了匹配算法芯片资源的占用率，是一种高效的并行多模式字符串匹配算法。     

字符串相似度在自动评分系统中的应用

在对编程语言类的自动评分系统中,程序设计类型的填空题大多采用字符串精确匹配的方法,而编程题的自动评分是一个难点.在分析两类题型的特点及目前采用的评测方法的优缺点的基础上,提出使用字符串相似度算法对程序设计题进行评判,并给出了评分过程的整体流程图.经过实际的使用,证明该方法是目前采用方法的一个很好补充,使评分的过程更加客...     

基于局部最大相似设想的串匹配算法

在设计盲打机考自动判卷系统时,需要一种有效的文本相似度判别算法。为此提出了一种基于局部最大相似设想的串匹配算法来解决此类问题,通过分别比较错误发生部位局部子字符串在插入片段、漏打片段或错打片段的的得分并选取失分最小者,实现了精确判定考生得分的目的。该算法无回溯,效率高,已应用于自动机考系统中。     

云计算中的轻量级查询结果验证机制

存储在云计算服务器上的数据可能被篡改或删除,查询完整性验证的作用是确保查询用户能够验证查询结果中的数据是真实的,且包含所有满足条件的数据。提出了一种基于签名链结构的查询完整性验证机制。方案使用代数签名机制替代数字签名实现校验值的计算,从而有效降低计算和查询验证开销。此外,通过维护一种新的、简单的索引结构实现了仅需下载少量数据即可实现校验值的更新。实验结果表明,所提方案比基于数字签名的签名链方案具有更小的更新开销和更高的验证效率。     

可有效同步注册的短的群签名方案(英文)

Group signature schemes are fundamental cryptographic tools. A group signature scheme allows members of a group to anonymously sign misuse, the anonymity messages. To counter can be revoked by the group manager. The group joining operation is a critical component of group signature scheme, the framing attack can be prevented by group joining processes. This paper presents an efficient group signature scheme with a simple joining protocol that is based on a ＂single message and signature response＂ interaction between the prospective user and the group manager. The security of our group signature is based on the Discrete Logarithm assumption and Decisional Linear Diffie- Hellman assumption. The formal security proof of our scheme is given in the random oracle model. Our scheme is also a very efficient short group signature scheme with efficient concurrent join.     

一个高效的有向传递签名方案

传递签名是由Micali和Rivest在2002年首先提出的,主要用于对二元传递关系进行签名.已有的传递签名方案都是无向的,只适用于对等价关系签名,提出有向传递签名方案是个留待解决的公开问题.该文提出一个高效的全序有向传递签名方案,并证明该方案在选择明文攻击下是安全的.在方案中,签名的β_uv部分被限定在0和q/2之间,以防止敌手由(u,v)的签名伪造(v,u)的签名,从而保证签名的有向性.将该方案与无向传递签名方案结合,提出一个可对任何有向二元传递关系进行签名的方案.     

Efficient Certificateless Aggregate Signature Scheme

In ubiquitous computing, data should be able to be accessed from any location, and the correctness of data becomes vital during the communication. Suppose that many users sign different messages respectively, before forwarding or sending these messages, then the verifier must spend a lot of computing time to verify their signatures. Consequently, the aggregate signature scheme is an effective method of improving efficiency in this kind of systems, which provides the convenience for the verifier. In this paper, we propose a new certificateless aggregate signature scheme which is efficient in generating a signature and verification. This scheme is provably secure under the extended computational Diffie-Hellman assumption.     

一个高效的随机化的可验证加密签名方案

 在基于对的可验证加密签名方案中,对运算是最为耗时的,故应在此类方案中尽量减少对运算的次数.为此,在给出一个新的基于对的签名方案的基础上,给出一个新的随机化可验证加密签名方案.新方案具有最少的对运算,即只有一个对运算.因此,与类似的方案相比,新方案更为有效.方案的安全性依赖于k-合谋攻击问题和离散对数问题困难假设.     

ElGamal数字签名方案的发展与应用

ElGamal数字签名方案作为目前最为重要的数字签名方案之一,极大地促进了现代密码学的发展。分析了几个主要的ElGamal型数字签名方案的优缺点,并阐述了ElGamal型数字签名方案的一些应用状况。     

Efficient Membership Revocation in ACJT Group Signature

How to find efficient and secure member- ship revocation algorithms is one of the most important issues standing in the way of real-world applications of group signatures. In this paper, the proof of knowledge of divisibility is given and a novel membership revocation method in ACJT group signature scheme is proposed： the group manager issues the product E of the public keys of current members in the group, when a group member wants to sign, he should not only proves that he has a membership certificate, but also proves that the public key in his certificate divides exactly the public key product E with zero knowledge. The proposed method is efficient since the group manager only needs one division and one exponentiation when a group member is deleted, while the signing and verifying procedure are independent of the number of current group members and excluded members, as well as the original group public key and membership certificates needn＇t be changed.