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

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

基于混合专业词典的继电保护定值在线智能比对方法

继电保护在线定值比对需要将整定定值和运行定值对应的定值名称进行匹配,针对此过程中存在的匹配效率不高、准确度差等问题,提出一种基于混合专业词典的防误比对方法以实现智能化匹配。该方法首先改进整词二分词典结构,增加同义词标志项和复合型字符标志项,同时将中文、英文和序号类字符均纳入字典,采用改进的正向最大匹配算法(forward maximum matching,FMM)提高分词准确度;其次,提出类型和首项的双重过滤机制以减小目标搜索空间的大小;然后针对继电保护定值名称的特殊性,采用不计词序的Jaccard相似度替代编辑距离计算的相似度,提高匹配准确度;最后通过定值项取值比较结果的反馈进行二次匹配,进一步提高匹配的准确度。算例分析验证所提方法能够有效提高比对的效率和精度。

基于改进编辑距离算法的保护装置测试模板开发

继电保护测试子模板实例化过程需要人工将实际参数赋给相应的数据接口,存在匹配繁琐、效率不高、准确性差的问题。为此,研究了一种改进编辑距离(improved lenvenshtein distance,ILD)算法来实现测试子模板实例化过程中数据匹配与数值传递的自动化和智能化。首先改进整词二分词典结构,即改进正向最大匹配(forward maximum matching,FMM)算法对字符串进行分词预处理,减少1/2的匹配复杂度;其次提出长度和后缀结合的双重过滤-验证机制,减小多字符串匹配时目标字符串搜索空间的大小;然后在编辑距离(lenvenshtein distance,LD)计算时以子串为单位取代逐字符,改进LD算法,提高字符串匹配效率;最后通过测试算例验证改进FMM算法在字符串分词处理上的高效性和正确性,实现在测试子模板实例化过程中数据匹配与数值传递的自动化与智能化。