基于n-gram的字符串分割技术的算法实现

相似字符串的模糊查询一直是人们致力研究的方向,目前基于关键字的查询技术都是前缀匹配,无法查找到与搜索字符串相似的结果。本文提出一种基于n-gram的字符串分割技术的算法,该技术是实现基于关键字的模糊查询技术的基础,通过对数据集以及搜索关键字的字符串进行分割,利用编辑距离实现相似字符串的模糊查询,该技术在数据挖掘以及论文抄袭等方面都有很重要的应用。     

云计算中加密数据的模糊关键字搜索方法

传统的可搜索加密方案仅支持精确匹配的搜索,在效率和性能上都不能适应云计算环境。用支持多种字符串相似性操作的R+树构建索引,实现了云计算中对加密数据的模糊关键字搜索;用编辑距离来量化关键字的相似度,提出了一种可以返回与关键字更接近的文件检索方法。通过字符串聚类提高了模糊关键字搜索的效率。     

多键值字符串键树的原理及实现

允许一个字符串关键字对应多个键值,且字符串关键字又非常多时,用键树保存有关的信息,在算法实现上有很好的时空性能.本文给出了解决该问题的一个实用的C 算法,并对源码作了详细的分析,最后给出了一个该算法在表达式解释系统中的应用实例.     

基于改进编辑距离的字符串相似度求解算法

编辑距离(LD)算法在求解两个字符串的相似问题时只考虑了编辑操作次数,未考虑字符串之间的公共子串对相似度的影响。为此,提出一种基于改进编辑距离的字符串相似度求解算法,对字符串相似度度量公式及Levenshtein矩阵计算方法进行改进。在计算编辑距离时,以原有矩阵求出两字符串的最长公共子串及所有LD回溯路径。选取一个单词作为源串,一组与源串不同程度相似的单词为目标串,将改进的相似度度量公式与现有的字符串相似度计算方法进行比较,改进公式减少了进入胜者表的目标串数,相似度的样本极差和标准差分别为0.331和0.150。实验结果表明,改进算法在不改变空间复杂度的情况下,计算字符串相似度的准确性更高,且查询方式更灵活。     

允许错误的并行字符串匹配技术

本文提出了一种允许错误的并行字符串查找技术，通过引入搜索状态向量及字符－模式匹配向量，该技术将字符串匹配比较转化为简单的整数字位运算，通过对字符串方向相反的搜索有效地实现了多处理机对字符串的并行相似检索，文中也给出了并行实现算法，同时分析了算法的复杂性。     

多种字符串相似度算法的比较研究

对计算字符串相似度的编辑距离算法、最长公共子串算法、贪心字符串匹配算法、RKR-GST等多种算法,根据匹配过程是否有序,对这些算法进行了分类。然后对每种算法的实现原理进行了描述,并给出每个算法的运行步骤,结合一个实际的例子列出了算法运行的结果,最后给出每种算法计算相似度的计算公式和算法时间复杂度及应用领域。由于字符串相似度具有广泛的应用领域,对其中经典的几种算法进行总结对比是一件十分有意义的研究工作。     

基于部分-整体匹配的文档结构相似度计算

传统的计算数字文档之间的结构相似度(DSS)的方法是基于树的编辑距离或Fourier变换.本文提出利用查询问题的结构化描述树Q与文档元数据描述树T之间的部分-整体匹配求解DSS.给出用字符串表示有向标记树的方法,并把上述树之间的相似度计算转化为对应Q和T的字符串表示之间的匹配计算,从而导出高效的DSS算法.实验表明,对给定的结构化查询,本文算法在查全率和查准率上优于树编辑距离算法.     

基于相似度模型的自动阅卷算法

自动阅卷算法一直以来都是各个在线考试系统的重点和难点.这里设计的自动阅卷算法通过解析学生答案中关键字,并计算这些关键字的排布与答案关键字的排布的相似度,给出一个相对合理的分值.经过反复测试调优,该算法提供的分值已经具有相当好的可参考性.     

结合分词技术与语句相似度的主观题自动判分算法

针对网络考试系统中主观题自动评分面临的困难和问题,提出一种基于中文分词技术结合语句相似度的主观题自动判分算法.该算法利用字典与统计相结合技术将语句切分成具有独立意义的单词,通过计算词与词之间的相似度,并结合词形、词序和语句长度等多层次相似度计算得到整句的相似度.利用语句相似度计算结合改进关键字匹配算法得到最终分值.经课题中多媒体简答题的测试,结果表明了该算法的有效性.     

基于扩展倒排索引的不确定XML关键字查询算法

现有的不确定XML关键字查询算法均需遍历不确定XML文档,并且算法在执行过程中需要频繁的字符串比较,造成时间浪费。针对上述问题,提出基于扩展倒排索引的不确定XML关键字查询算法Pr E。扩展倒排索引有效地存储了不确定XML文档中节点的相关信息,根据扩展倒排索引即可初始化动态哈希表和序号编码链表,并且Pr E算法在执行过程中利用整数的比较代替了字符串的比较。理论分析与实验结果表明,Pr E算法是一种高效的不确定XML关键字查询算法。     

关联规则挖掘AprioriTid算法的改进

提出了一种将AprioriTid算法与事务压缩和项目压缩相结合的改进算法。该算法中候选项目集及支持度计算是在每条事务压缩后通过联接产生,候选项目集采用关键字识别,省去了AprioriTid算法中的剪枝和字符串模式匹配步骤。实验结果表明,改进的算法执行效率明显优于AprioriTid算法。     

面向教学资源查询的语义相似度和相关度算法

在基于距离的语义相似度计算方法的基础上,综合多种因素对相似度的影响,提出一种新的相似度和相关度计算方法。将其应用到教学资源领域本体,计算本体概念间的相似度和相关度。实验结果显示该算法可以提高传统基于距离的相似度算法的性能。最后比较了利用该算法的语义查询与传统关键字查询的结果。     

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

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

一种自适应信息集成方法

检测相似重复记录是信息集成中的关键任务之一,尽管已经提出了各种检测相似重复记录的方法,但字符串匹配算法是这些检测方法中的核心。在提出的自适应信息集成算法中,用一个综合了编辑距离和标记距离的混合相似度去度量字符串之间的相似度。为了避免由于表达方式的差异而造成的字符串之间的不匹配,字符串被分割成独立的单词后按单词的第一个字符进行排序。在单词的匹配中,对拼写错误和缩写有一定的容错功能。实验结果表明,自适应信息集成方法比用Smith Waterman和Jaro距离有更高的正确率。     

一种基于语义词典的本体对齐框架

提出一种基于语义词典的本体对齐框架.首先抽取出代表本体元素的字符串,这些字符串包括本体中的概念、实例、关系等,并利用现有的词典和语义资源将字符串变为词的集合;然后将本体对齐转换为单词集合间的映射,通过多相似度的匹配算法来进行相似度计算,从而实现本体对齐.实验结果表明,所提出的方法是有效的且较之以前的对齐方法有一定的提高.     

分段处理的1／p概率字符串匹配

现有的概率字符串匹配算法通过计算字符串之间的最小失配字符数(编辑距离),可求出字符串之间的相似度.这些算法平等地看待模式串和文本串,虽然可求出二者之间完整的编辑距离,但并不能解决以下问题:即判断是否模式串中至少有1/p的字符顺序地出现在文本串中.基于动态规划字符串匹配算法,提出了一个改进算法.该算法通过将字符串分段,在段内执行改进的概率匹配算法可求出段内的编辑距离,再结合回溯策略可以很好地解决上述问题.该算法的复杂性要低于基本动态规划匹配算法,且在某些情况下效率更高.就问题的一般性而言,该算法可广泛地应用于计算生物学、信息安全和信号处理等诸多领域.     

应用于动态异构web服务器的相似度求解方法

针对经典的基于编辑距离的字符串相似度计算方法计算效率低且准确率差的不足,提出一种基于编辑距离和最长公共子串的改进字符串相似度求解方法,引入最长公共前缀和最长公共后缀,定义新的相似度计算公式。将该方法应用于基于异构平台的动态异构web服务系统模型,通过网页篡改检测实验验证,与经典算法和经典公式相比,改进的相似度计算方法能够在适应自身差异性的基础上,提高相似度计算的准确性和计算效率。     

维汉机器翻译未登录词识别研究

针对维汉统计机器翻译中未登录词较多的现象和维吾尔语语言资源匮乏这一现状,结合维吾尔语构词特征以及相应的字符串相似度算法,提出了一种基于字符串相似度的维汉机器翻译未登录词识别模型。该模型借助短语表和外部词典,与未翻译的维语词求相似度,取相似度最大短语对应的汉语翻译作为此未登录词的最终翻译。实验证明,与基于词干切分的未登录词识别方法相比,此模型较好地保留了维吾尔语词信息,提高了译文的质量。     

CAD模型自动语义标注

为了解决基于关键字检索方式难以获得符合设计意图的CAD模型的问题,通过对CAD模型自动添加语义标签来改进传统关键字方式检索CAD模型的准确性.首先提出一种利用属性图比较CAD模型形状相似性的算法,根据图的邻接矩阵及顶点属性构造图顶点集的序列,通过动态编程方法求出图的最大公共子图,得到CAD模型之间的形状相似度;然后根据求出的未知模型与已知模型之间的形状相似度,利用概率方法实现对未知模型的自动语义标注.实验结果表明,采用文中方法可以使基于关键字的检索方法具有搜索形状相似模型的功能,在很大程度上改进了传统关键字方式检索CAD模型的准确性.     

基于规则的中文字符串近似匹配研究

字符串近似匹配在网络安全中有广泛的应用。本文从中文字符串相似度角度出发,提出了通过单个汉字的细分来提高字符相似度的想法,并从汉字＂成簇性＂方面进行分析,引出了汉字的Key表示方法,将汉字与Key的映射关系归结为规则,讨论了规则的获取方法。设计了基于规则的中文字符串近似匹配的框架,提出了新的相似度计算模型,并通过实验对整个流程加以验证,证明基于规则的中文字符串近似匹配的优越性。