一种基于编辑距离的中文字符串近似匹配算法

字符串近似匹配是模式匹配领域中的一个重要研究方向。在中文字符串近似匹配中,基于字符操作的编辑距离不能准确衡量由复制、剪贴等操作导致的相似关系。基于此,在传统编辑距离的基础上引入了字符串的平移和复制操作,给出了一种在贪心算法基础上进行动态规划搜索的计算方法,能有效计算改进的编辑距离,在真实数据集上的实验结果和分析显示了对文本检索的有效性。

一种改进的编辑距离算法及其在数据处理中的应用

基于数据处理的需要,在分析原有编辑距离算法的基础上,通过拓展交换操作减少编辑操作的数量。与仅对计算点之前相邻位置字符间的交换操作相比,通过对计算点前后非相邻位置字符间的交换操作改进该算法,能够得到更理想化的编辑距离。将改进的编辑距离算法应用于煤矿隐患数据的处理,提高了隐患数据分类分级的有效性和执行效率。

快速中文字符串模糊匹配算法

本文解决了中文字符串模糊匹配的两个主要问题 :空间问题和时间问题。目前字符串模糊匹配的两个主要方法是位向量方法和过滤方法。由于汉字众多 ,应用位向量方法时 ,需要大量空间。对于某些内存很少的小型计算机 ,比如嵌入式系统 ,这将会是一个问题。本文改进了位向量方法 ,使其在应用于中文字符串时 ,空间需求降低到约 5 %。本文还利用汉字非常多的特点 ,提出一种新的基于过滤方法的中文字符串模糊匹配算法 ,BPM BM ,其速度比世界上最快的算法至少提高 14 %;在大部分情况下 ,是其速度的 1 5～ 2倍。

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

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

基于过滤的中文多模式近似字符串匹配算法

当前近似字符串匹配算法主要针对英文等中小字符集,该文针对汉字等大字符集的有效算法很少,尤其缺少适合汉字等大字符集的多模式近似匹配算法的情况,提出了一种适合汉字等大字符集的多模式近似匹配算法——MBPM-BM,通过实验证明了该算法的有效性。

数据分析和清理中相关算法研究

数据清理的一个主要作用是识别重复的记录.结合过滤算法和启发式剪枝算法提出了启发式剪枝改进算法.然后,针对重复记录的特点提出了长度约束条件,能有效地提高比较字段不等长时的执行速度.数据库中经常会出现各种形式不同的缩写,而启发式剪枝算法等无法识别缩写情况下的重复记录,本文因此提出了基于动态规划的缩写发现算法,该算法既可以用于缩写发现也可用于缩写存在时的重复记录识别.另外,重复记录的甄别目前必须人工处理,传统方式下用户不得不逐条浏览和分析,工作时间冗长而且乏味,容易引入新的数据质量隐患,作者提出了聚类清除方案和聚类闭包算法,它将重复的记录聚类显示,用户一次可以处理完一个重复聚类,在有效提高速度的同时方便了用户.

基于编辑距离和相似度改进的汉字字符串匹配

为解决中文字符串匹配精度较低的问题,提出了一种基于编辑距离和相似度改进的汉字字符串近似匹配算法,针对汉字字符串特点,使用汉字拼音和五笔编码计算;通过改进动态规划算法,能够有效提高编辑距离的计算准确度以及执行效率;再引入考虑交换问题的归一化算法,以语义编辑距离与长句长度的比值作为归一化结果,以此来提高近似匹配算法的准确度。实验结果表明,改进后算法计算的相似度质量要优于改进前的算法结果,且对提高算法效率和查全率、查准率和时间性能等指标均有明显改善,证明该算法的可行性和有效性。

支持块编辑距离的索引结构

在近似字符串匹配中,传统的编辑距离不能很好地衡量诸如人名、地址等数据的相似关系,而块编辑距离可以很好地衡量两个字符串的相似性.如何有效地支持块编辑距离,进行近似字符串查询处理具有重要的意义.计算两个字符串的块编辑距离是一个NP完全问题,因此希望提供有效的方法可以增强过滤能力,并减少假通过率.设计了一种支持移动编辑距离的新颖的索引结构SHV-Trie,通过研究移动编辑距离的操作特性,使用字母出现的频率作为支持移动编辑距离操作的一个下界,并且提出相应的查询过滤算法,同时,针对索引SHV-Trie的空间开销过大的问题,提出一种优化字母排列的索引结构和一种压缩的索引结构及相关查询过滤算法.真实数据集上的实验结果与分析显示了所提出的索引结构具有良好的过滤能力,并通过减少效率假通过率提高查询的效率.

基于GPU实现允许k-差别近似串匹配并行算法

为了在GPU上实现允许k-差别近似串匹配并行算法,并进一步提高在GPU上的算法性能,在综合考虑GPU的存储层次前提下,采取了多种访存优化措施,并提出了避免bank冲突的解决方案。测试结果表明,所用优化措施及方案使算法性能明显提高。

一种改进的安全传真服务器设计方法

传真服务器存在对垃圾传真防范能力不足的问题。为此,在现有安全传真服务器的设计基础上,提出一种改进方案。在接收传真之前增加图灵检测功能用于筛选自动传真,采用近似串匹配技术对垃圾传真进行确认,进而通过黑名单功能实现垃圾传真的过滤,并将聚类功能作为发现新垃圾传真、丰富关键词库的辅助手段。仿真实验表明,该方法在精度、对垃圾传真反应速度以及智能性等方面均优于原有设计。

PRAM和LARPBS模型上的近似串匹配并行算法

近似串匹配技术在网络信息搜索、数字图书馆、模式识别、文本挖掘、IP路由查找、网络入侵检测、生物信息学、音乐研究计算等领域具有广泛的应用.基于CREW-PRAM(parallel random access machine with concurrent read and exclusive write)模型,采用波前式并行推进的方法直接计算编辑距离矩阵D,设计了一个允许k-差别的近似串匹配动态规划并行算法,该算法使用(m+1)个处理器,时间复杂度为O(n),算法理论上达到线性加速;采取水平和斜向双并行计算编辑距离矩阵D的方法,设计了一个使用a(m+1)个处理器和O(n/a+m)时间的、可伸缩的、允许k-差别的近似串匹配动态规划并行算法,+<11mna.基于分治策略,通过灵活拆分总线和合并子总线动态重构光总线系统,并充分利用光总线的消息播送技术和并行计算前缀和的方法,实现了汉明距离的并行计算,设计了两个基于LARPBS(linear arrays with reconfigurable pipelined bus system)模型的通信高效、可扩放的允许k-误配的近似串匹配并行算法,其中一个算法使用n个处理器,时间为O(m);另一个为常数时间算法,使用mn个处理器.

基于动态规划的缩写发现算法

数据清理中重复记录的识别一般采用动态规划算法或过滤算法,然而很少算法考虑了数据中的缩写问题,因此容易漏掉一些重复记录,影响了数据清理的质量,因此在动态规划的基础上提出了缩写发现算法,同已有算法相比,它的算法复杂度较小,而且能够发现汉语等无分隔符的语言中的缩写,最后给出了缩写情况下判断字符串近似匹配的方法.

基于压缩后缀数组的近似字符串匹配算法

近似字符串匹配是模式匹配研究领域中的一个重要研究方向。压缩后缀数组是字符串匹配、数据压缩等领域广泛使用的索引结构,具有检索速度快和适用广泛的优点。利用压缩后缀数组,提出了适合近似字符串匹配搜索算法的数据结构,并在此基础上提出了一种匹配搜索算法。实验结果表明,相对于现有的算法,提出的算法在小字母表的情况下具有计算优势。

一种自适应信息集成方法

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

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

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

异构机群系统上基于多轮分配方式的近似串匹配并行算法

在给定正文串分配轮数的前提下,考虑处理机节点具有不同计算速度、不同通信能力的情形,根据从处理机是否允许重叠执行计算和通信操作,提出异构机群计算环境下的最优正文串多轮分配策略;同时提出一种周期性的正文串多轮分配策略并给出了相应的正文串多轮分配的闭合解,此策略可以求出最优的分配轮数.实验结果表明,正文串多轮分配策略比正文串单轮分配策略大大缩短了近似串匹配并行处理的时间,并且在正文串多轮分配策略中,当近似串匹配应用的规模较小时,分配轮数比参与近似串匹配并行处理的从处理机数更能影响近似串匹配并行处理的完成时间,反之,从处理机数对近似串匹配并行处理的完成时间影响更大.

一种支持多种子近似串匹配的q-gram索引

如何在大型文本库中快速找出给定串的近似串是大数据时代要解决的关键问题。基于多种子的近似串匹配算法因匹配速度快而得到众多学者的青睐,但巨大的索引空间消耗也使其难以处理大型文本库。提出了一种支持多种子的q-gram索引结构,通过该索引能够快速地计算出给定任意长度连续种子的地址集合,解决了多种子近似串匹配算法中种子的数目和长度受存储空间限制的问题。实验数据显示,新索引方案成倍地减少了存储空间的消耗。实验结果表明,提出的索引方案在大数据环境下的多种子近似匹配中具有一定的优势。

对基于MPN的相似重复记录识别算法的改进

相似重复记录识别是数据清理中的一个关键问题。文章针对常用的多趟邻接排序法提出了两点改进:一是在多趟排序识别过程中直接合并有重叠的相似记录集,取消了最后计算传递闭包的环节;二是利用关键字按字典序排序的特性,在求编辑距离之前先过滤前面的公共子串,减少了相似记录比较的开销。文章最后给出了改进算法与原算法的对比试验结果。

一种挖掘相似子趋势的可变递增步长算法

通过引入趋势相似和趋势分布的概念 ,分析了趋势分布与趋势序列相似度之间的关系 ,发现趋势分布可排除掉满足一定的不相似条件的侯选子趋势 ,并且可采用“跳跃”的方式来进行相似子趋势的搜索 .提出了在时间序列数据库中进行相似子趋势的数据挖掘的快速算法 VISL (variable increm ental step length) .对比于两个已有算法(一个具有与相似度阈值无关的运行时间 ,另一个在高相似度阈值下具有目前领域内最好的时间性能 )进行了仿真数据集上的运行实验 ,在较长的序列长度及高相似度阈值的情况下 ,得到了较对比算法更优的时间性能 .

一种有效的并行汉字／字符串相似检索技术

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