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

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

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

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

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

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

一种自适应信息集成方法

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

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

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

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

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

汉字／字符串编辑距离和编辑路径的有效求解技术

本文提出了一种有效的编辑距离和编辑路径求解技术，该技术不但适合于单字符字符串而且也适合于双字节汉字串的编辑距离和编辑路径的计算。它首先通过一有效的字符串相似匹配算法计算出串编辑距离，而后通过简单的二进制字位运算正确计算出串（最短）编辑路径。文章也给出了本技术的完整实现算法并分析了算法的复杂性。     

允许错误的（汉字）字符串快速检索技术

在计算机应用的诸多领域中都会遇到字符串似检索问题。本提出了一种技术。它通过应用搜索状态向量及字符－模式匹配向量，将字符串匹配比较转化简单的整数字位运算，有效地解决了字符／汉字串的相似匹配问题，中也给出了实现算法并分析了算法的复杂性。     

一种改进的字符串匹配算法

基于字符串匹配的检测方法是入侵检测系统中的一种重要方法。在分析了几种常见的字符串匹配算法（BF、KMP、BM、Sunday等）的基础上，提出了一种改进的字符串匹配算法——sundayNcw。该算法使每一次匹配不成功后都能跳过尽可能多的字符以进行下一轮匹配，并且匹配次数大大减少，从而提高了匹配效率。最后，分析了该算法的性能，并用具体的实验数据给出了几种匹配算法的测试结果。     

几种字符串匹配算法的分析和比较

字符串匹配技术在许多领域里被广泛应用。分析了BF、KMP、BM算法以及一些重要的改进算法,并对其性能进行了测试,为不同的应用领域采用适当的算法提供了思路。     

Dynamic computation of generalised median strings

The generalised median string is defined as a string that has the smallest sum of distances to the elements of a given set of strings. It is a valuable tool in representing a whole set of objects by a single prototype, and has interesting applications in pattern recognition. All algorithms for computing generalised median strings known from the literature are of static nature. That is, they require all elements of the underlying set of strings to be given when the algorithm is started. In this paper, we present a novel approach that is able to operate in a dynamic environment, where there is a steady arrival of new strings belonging to the considered set. Rather than computing the median from scratch upon arrival of each new string, the proposed algorithm needs only the median of the set computed before together with the new string to compute an updated median string of the new set. Our approach is experimentally compared to a greedy algorithm and the set median using both synthetic and real data.     

双向过滤的字符串相似连接验证方法

字符串相似连接是指在字符串集合中找出相似的字符串对,是许多应用的关键操作,寻找高效的字符串相似连接算法已成为研究热点。基于划分的过滤-验证方法（Pass-Join）与其他方法相比具有较高的效率。它按照字符串长度递增的顺序访问字符串集合,通过查找一个字符串的划分块是否存在于另一个字符串中,快速筛选出可能相似的字符串对（候选集）,然后利用编辑距离进行相似性验证。研究发现,按照字符串长度递减的顺序进行过滤（长度递减过滤）的效果优于按照长度递增的顺序过滤（长度递增过滤）的效果,基于此,提出双向过滤-验证机制：在过滤阶段对长度递减过滤的结果再进行一次长度递增过滤,进一步减小候选集大小;在验证阶段利用双向过滤产生的两对划分块和其匹配子串分隔字符串对,从而减小需要验证的字符串的长度,加速验证过程。实验证明,双向过滤-验证算法在真实数据集上优于原算法。     

基于短序列分组和拼接策略的子序列快速查询算法

子序列查询技术在金融、商业、医疗等领域均有重要应用,但因DTW（dynamic time warping）等相似性比对算法的时间复杂度较高,子序列长度对检索时间影响很大,限制了数据集上长子序列检索的效率。针对这一问题提出一种子序列快速查询算法。首先对数据集中特定长度下所有子序列进行分组并标记出代表性子序列;然后在查询时将查询序列切分成定长的小段序列,并用DTW算法确定与小段序列相似的代表子序列候选集;最后对候选集进行序列拼接,获取到查询结果序列。实验表明新算法效率较典型算法提高约10倍。     

基于独立分量分析的自适应在线算法

独立分量分析(ICA)是近几年兴起的一种高效的信号处理方法,学习步长的优化问题是自适应ICA重要的一方面,基于变步长思想,定义了一种描述信号分离状态的相似性测度,来衡量输出分量之间的相似性程度,并由此提出一种改进的自适应在线算法。根据相似性程度所反映的信号分离状态自适应调节步长,并建立学习步长和相似性测度变化量的非线性关系,克服了传统算法在信道矩阵变化时对步长自适应调整的不足。性能指标分析和仿真实验证明了算法的收敛性和稳态性能。     

PageCluster:一种Web页面层次聚类方法

提出了Web页面聚类算法PageCluster及相应的改进算法ImPageCluster。该方法在兼顾Web站点结构和页面链接的同时,基于各个页面的重要程度对各个超链接进行赋权。与传统聚类算法相比,该算法不需要事先给定相似度阈值。实验结果证实了该算法的可行性和高效性。     

基于粒子群优化的文档子内容查重算法

现存的文档相似性算法虽然能够获得2篇文档的相似度,但不能判断出重复或最相似子内容的位置。为此,提出一种基于粒子群优化(PSO)的文档内部子内容的查重算法。利用PSO方法查找2篇文档中最佳相似子内容的位置和长度,设计一种相关函数来判断字符串之间的相似程度,从而得到粒子群的评估函数。测试表明,该查重算法能够快速准确地确定出重复或最相似子内容的位置与长度。     

一种快速的字符串匹配算法

字符串匹配技术在许多领域里广泛应用，本文在分析了BF、BM算法以及一些重要的改进算法的基础上，提出了一种新的改进算法——BMH2C，该算法利用两个字符计算右移量并保存在二维数组里，使右移量增大，比较次数减少，有效地提高了匹配速度．最后本文还给出了几种匹配算法的测试结果。     

String similarity search and join: a survey

String similarity search and join are two important operations in data cleaning and integration, which extend traditional exact search and exact join operations in databases by tolerating the errors and inconsistencies in the data. They have many real-world applications, such as spell checking, duplicate detection, entity resolution, and webpage clustering. Although these two problems have been extensively studied in the recent decade, there is no thorough survey. In this paper, we present a comprehensive survey on string similarity search and join. We first give the problem definitions and introduce widely-used similarity functions to quantify the similarity. We then present an extensive set of algorithms for string similarity search and join. We also discuss their variants, including approximate entity extraction, type-ahead search, and approximate substring matching. Finally, we provide some open datasets and summarize some research challenges and open problems.     

MED算法及其在网页搜索中的应用

针对传统方法不能很好地处理网页中简短域和用户查询之间的相关性排序问题,提出一种改进的编辑距离(MED)排序算法,在编码和计算过程中引入查询词分布的位置、顺序和距离等信息,将查询和简短域之间的相关性问题转化为编码字符串的相似性问题。仿真实验结果表明,与传统的相关性排序算法相比,该算法可以提高网页搜索中简短网页域的相关性排序性能。     

Local coupled extreme learning machine

Due to the significant efficiency and simple implementation, extreme learning machine (ELM) algorithms enjoy much attention in regression and classification applications recently. Many efforts have been paid to enhance the performance of ELM from both methodology (ELM training strategies) and structure (incremental or pruned ELMs) perspectives. In this paper, a local coupled extreme learning machine (LC-ELM) algorithm is presented. By assigning an address to each hidden node in the input space, LC-ELM introduces a decoupler framework to ELM in order to reduce the complexity of the weight searching space. The activated degree of a hidden node is measured by the membership degree of the similarity between the associated address and the given input. Experimental results confirm that the proposed approach works effectively and generally outperforms the original ELM in both regression and classification applications.