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

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

一种融合多种编辑距离的字符串相似度计算方法*

针对中西文混合字符串,采用了将汉字作为西文字符的等价单位计算编辑距离的方法,并从输入法的角度提出了采用拼音编码和五笔编码计算编辑距离的方法,最后给出了融合三种编辑距离计算字符串相似度的算法。仿真结果表明,该方法在提高相似重复记录检测的查全率的同时,也能获得较高的查准率。     

字符串匹配的自动机方法

本文讨论了字符串的连续匹配、离散匹配及求解最长公共子串的自动机算法，给出了上述各算法的形式化。     

相似单词查找方法研究与实现

论文提出一种有限分隔最长公共子串算法,将这种算法与改进的最小编辑距离算法相结合实现输入单词与词库内单词的相似度计算。最终将计算结果聚类输出。实验结果表明,应用本文提出的方法进行相似单词查找与单词联想拼写能获得令人满意的结果。另外,我们将所实现的软件与源码公开以供参考。     

相似度算法在学生课程设计评定中的应用

本文针对学生在课程设计中经常将关键字书写错误的问题,采用字符串的匹配程度来判定错误字符串与关键字的相似度,进而评定程序的优劣.本文首先介绍了一种简单的以关键词为核心的相似度算法,随后详细探讨了基于语义树的相似度算法,并给出具体实例加以验证算法的可行性与精确性.     

一种基于过滤技术的字符串模糊匹配方法研究

针对基于编辑距离的字符串模糊匹配方法搜索效率较低的问题,通过对字符串模糊匹配过程进行分析,利用并行化技术对大数据量的字符串模糊匹配过程进行优化.同时由于计算字符串间编辑距离算法性能较低,提出利用字符串过滤规则对待搜索字符串集合进行过滤后再进行模糊匹配的改进方法.实验结果表明,改进后的方法具有较高的执行效率并取得了较好的召回率和精度.     

集合和字符串的相似度查询

相似度查询是计算机学科中一个重要的问题,它的应用遍及多个领域,例如数据库、数据集成、互联网、数据挖掘以及生物信息学等.该文主要讨论在集合和字符串上的相似度查询.学术界从2000年来在这个领域内取得了大量的进展.作者总结了主要工作,并给出了作者的分析和归类.最后,该文提出了一些未来工作的方向.     

基于动态规划的汉语句子相似度算法

传统汉语句子相似度计算算法在处理大量专业词汇时准确率较低。为此,提出一种基于动态规划的汉语句子相似度算法。通过获取2个句子的公共子串集合,结合链表消重机制,从集合中获取2个句子的所有最长公共子串,并以此计算相似度。实验结果表明,对于含有大量专有名词的问题集合,该算法的测试正确率达93.6%,计算效率较高。     

字符串模糊匹配算法的探讨

字符串模糊匹配问题在计算机中有着广泛的应用．尝试探讨一种无论从算法时间复杂度上讲还是编程复杂度上都比较优秀的一种模糊匹配算法。     

基于Trie树的相似字符串查找算法

基于Trie树的相似字符串查找算法是利用编辑距离的阈值来计算每个节点的活跃节点集,已有算法由于存在大量的冗余计算,导致时间复杂度和空间复杂度都比较高。针对这个问题,采用了基于活跃节点的对称性和动态规划算法的思想对已有算法进行改进,并对活跃节点集进行了修剪,提出了New-Trie-Stack算法。该算法避免了活跃节点的重复计算,以及已有算法在保存所有已遍历节点的活跃节点集时的空间开销。实验结果表明New-Trie-Stack算法在时间复杂度和空间复杂度上都有明显的下降。     

数据集成中数据项与数据元匹配算法

近年来,随着数据元标准的建立,数据元在各行各业的数据集成过程中担任着重要角色,用于规范数据库、报表、文档中的数据项,实现各种数据源之间的映射。分析数据元的结构,提出一种数据项与数据元匹配算法,该算法基于编辑距离算法,融合最长公共子序列、权重、词语重心后移等思想,实现数据项与数据元字典中数据元的相似度计算,利用排列组合原理对匹配速度进行优化。以中石化标准数据元为实验数据进行实验,验证了该匹配算法的有效性。     

基于URL相似度的会话识别方法

随着互联网的快速发展,Web日志的用户行为分析已经成为互联网技术领域的研究热点之一.会话识别是Web日志用户行为分析的关键步骤,精准的会话识别是有效进行用户行为分析的基础.本文在IIS Web日志分析的基础上,提出了一种基于URL相似度的会话识别方法.实验结果表明,此方法可以有效的识别出用户的真实会话.     

外存中高效的字符串相似性查询处理

字符串相似性查询是众多应用的基础操作,如数据清洁、拼写校验、生物信息学和信息集成等.随着数据的爆炸性增长,大规模字符串数据日益普遍,现代的信息系统中也广泛使用字符串作为数据的表达形式.现有支持字符串相似性查询的方法大多是基于q-gram的内存倒排索引,在处理大规模字符串集合会消耗无法忍受的内存容量,甚至在数据量过大时造成内存容量不足而无法支持查询处理.现有的外存倒排索引Behm-Index在查询的过滤阶段只支持少数过滤器,不能有效地减少查询I/O代价.提出了LPA-Index：一种支持长度过滤器和位置过滤器的外存倒排索引,并通过选择查询时使用的倒排表来有效地降低查询I/O代价.实验结果表明,与现有性能最好的外存索引Behm-Index相比,LPA-Index能够大幅降低查询的I/O代价,获得了更短的查询响应时间.     

基于字符串相似度的维吾尔语中汉语借词识别

维汉机器翻译过程中会出现较多的未登录词,这些未登录词一部分属于借词(人名、地名等)。该文提出一种新颖的根据借词与原语言词发音相似这一特性进行维吾尔语中汉语借词识别的方法。该方法对已有语料进行训练,得到面向维吾尔语中汉语借词识别的维吾尔语拉丁化规则;根据以上规则对维吾尔语拉丁化,并对汉语词进行拼音化,将借词发音相似转换为字符串相似这一易量化标准;提出了位置相关的最小编辑距离模型、加权公共子序列模型以及二者的带参数融合模型。实验结果表明,综合考虑字符串全局相似性和局部相似性的带参数融合模型取得了最佳的识别效果。     

基于LCSS的数据流相似性查询处理算法研究

数据流相似性查询广泛应用于智能家居、环境监测等领域.当前以LCSS(longest common subsequence)作为相似性测度函数的研究并不多.NAIVE算法使用基本动态规划方法计算测度函数值,通过该值与相似阈值的比较得到查询结果,对基于LCSS的数据流相似性查询问题进行研究.针对NAIVE算法必须在动态规划矩阵所有成员取值的计算完成后才能得到查询结果的缺点,提出了一种基于PS(possible solution)-CC(column critical)域优化策略的数据流相似性查询处理算法.该算法划定了每个窗口上动态规划矩阵的PS域和CC域,很好地利用了这2个域中成员所具有的性质和相似性查询的特点,无须获得测度函数的最终值便可得到查询结果,省略了很多矩阵成员的计算.实验部分证明了该算法的有效性,与同类算法相比,在处理具有更高精度结果要求的查询时效果更好.     

改进的中文近似字符串匹配算法

BPM-BM算法在针对汉字等大字符集的近似字符串匹配时取得了很好的实际效果,但该算法在最差情况下的总体时间复杂度为O(!+nm)。而提出的IBPM-BM算法由于具有记忆的能力,保证了过滤阶段的无回溯,可以在理论上保证最差情况下的总体时间复杂度为O(!+n),而在最佳情况下的时间复杂度与BPM-BM算法一致。     

基于相对链码和改进 LCS 算法的图形匹配实现

研究相对链码和字符串的匹配算法,采用相对链码和改进的LCS算法实现图形的轮廓匹配。首先通过轮廓提取算法得到图形的轮廓,再通过轮廓跟踪算法得到轮廓的链码,由链码计算得到图形的相对链码,最后采用改进的最大公共子串算法计算两图形的相似度。该图形轮廓匹配算法具有计算量小,平移、旋转的不变性等优点。在Android系统上进行实验,实验结果表明该算法计算速度快,与人的视觉相吻合。     

一种基于熵的文本相似性计算方法

文本比较是求解两个文本间相似度的过程,文本间的相似度越高代表两个文本越趋于类似。传统的相似度算法主要从字符的角度度量文本的相似性,而忽略了文本内多个共同文本串对于文本相似度的影响。针对此问题,本文提出一种基于熵的相似度求解方法。该方法在对文本间字符信息的提取基础上,建立共同子文本串度量维度,然后采用熵的方法进行相似度度量。实验表明,该方法具有更平滑的相似度曲线,验证了算法的有效性和准确性。