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

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

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

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

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

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

基于编辑距离的Web数据挖掘

Div+CSS流行于Web页面的布局,在这种布局下,网页中很多数据记录以重复结构的形式聚集在一个层级。为了更好地从网页中挖掘数据,提出了一种新的Web数据挖掘算法,把树编辑距离转化为字符串编辑距离的计算,改进字符串编辑距离算法,利用字符串编辑距离评价树的相似度,进而找到网页中的重复模式,提取数据。通过针对不同重复模式特征的网页的实验说明,基于编辑距离的Web数据挖掘算法不仅能提取具有根节点及上面几层相同的网页的数据,对具有底层节点相同的网页也是有效的。     

编辑距离算法及其在英语易混词自动抽取中的应用

研究英语单词形态相似度的计算方法.采用可设置编辑距离上限参数的算法实现从指定词汇范围自动抽取近形词.筛选出的易混近形词经消重和分类后可以丰富英语词汇知识库的内容.易混词知识库在教材编写、词汇能力训练设计、词典编纂和真词错误拼写校正等领域具有应用价值.     

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

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

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

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

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

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

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

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

用字符串编辑距离算法筛选相似试题

对题库中的试题进行重复性检测,可以保持题库的高质量,并能降低专家的工作强度,也是进行题库资源整合的前提条件.通过实例,研究了钢铁行业技能知识网络竞赛试题筛选问题,采用字符串编辑距离算法来查找相似试题,获得了良好效果.实例中处理试题库文件的方法对类似问题的解决有一定的借鉴作用.     

基于编辑距离的网页去重策略

互联网中存在着大量的重复网页,在进行信息检索或大规模网页采集时,网页去重是提高效率的关键之一。本文在研究＂指纹＂或特征码等网页去重算法的基础上,提出了一种基于编辑距离的网页去重算法,通过计算网页指纹序列的编辑距离得到网页之间的相似度。它克服了＂指纹＂或特征码这类算法没有兼顾网页正文结构的缺点,同时从网页内容和正文结构上进行比较,使得网页重复的判断更加准确。实验证明,该算法是有效的,去重的准确率和召回率都比较高。     

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

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

An improved adaptive string searching algorithm

Sunday's OM algorithm can reduce the number of character comparisons by making use of information of character distribution in an alphabet. Smith's adaptive algorithm uses dynamic statistics to reduce comparisons and its performance is close to that of the OM algorithm in the number of character comparisons. Smith's algorithm has the advantage of language independence. Its drawback is that it runs slowly because of maintaining an ordering list. This paper presents an improved adaptive method which dispenses with the ordering list. This method treats the pattern as a circle, and first compares the mismatched character in the last checking operation. This methods is slightly worse than Smith's method in the number of character comparisons, but it much better in the running time. © 1998 John Wiley & Sons, Ltd.     

Compressed Data Cube for Approximate OLAP Query Processing

Approximate query processing has emerged as an approach to dealing with the huge data volume and complex queries in the environment of data warehouse.In this paper,we present a novel method that provides approximate answers to OLAP queries.Our method is based on building a compressed (approximate) data cube by a clustering technique and using this compressed data cube to provide answers to queries directly,so it improves the performance of the queries.We also provide the algorithm of the OLAP queries and the confidence intervals of query results.An extensive experimental study with the OLAP council benchmark shows the effectiveness and scalability of our cluster-based approach compared to sampling.     

一种改进的FastICA算法及其应用

独立分量分析是基于信号高阶统计量的信号分析方法,它可以找到隐含在数据中的独立分量,已经广泛应用到语音信号处理、图像处理及信息通信等方面。目前应用较多的快速独立分量分析（FastICA）利用了牛顿迭代法原理,具有较快的收敛速度,但对初始值的选择比较敏感。为克服其缺点,改进其优化学习算法,在牛顿迭代方向增加一维搜索,使改进后的算法的收敛性不依赖于初始值的选择。将改进的FastICA算法应用到运动目标检测中,取得稳定性较强的结果。     

基于并行处理机制的数据复用策略研究

针对频繁出现的数据冗余、数据复用效率低下等问题,将列存储方式结合并行处理机制对数据复用策略进行优化。构建了基于MapReduce的数据复用并行化处理模型,利用改进型CSM模式匹配算法结合数据挖掘过程中的数据筛选算法,提出并行化数据复用算法。该算法利用数据属性的模式匹配确定属性列之间的对应关系,使用数据检测方式验证属性列数据复用的可行性,从而进行属性列数据筛选,实现并行化的数据复用策略。在大数据环境下的数据仓库中,对大规模基准数据属性集SSB和TPCH中提取的数据实证分析,实验结果分析中存储量和处理时间分别减少了17%和35%,实验结果验证了并行化数据复用策略在数据存储量、数据处理时间等方面比普通数据复用策略更具高效性。     

工作面瓦斯涌出量数据处理程序设计及应用

针对瓦斯地质统计法中涌出量数据繁杂、处理困难等问题,分析了瓦斯涌出量数据来源,建立了瓦斯涌出量数据库,采用百分位数方法对涌出量数据进行筛选,找出能够反映矿井真实瓦斯涌出量规律的数据。采用C语言编程和CAD二次开发工具,建立了瓦斯涌出量数据筛选模块,并将其应用于平煤十二矿,结果表明采用瓦斯涌出量数据筛选模块可提高数据处理速度,节省了大量的人力、物力,并提高了瓦斯地质图的编制效率。     

改进的麻雀搜索优化算法及其应用

麻雀搜索算法SSA在求解目标函数最优解时,存在种群多样性不丰富,易陷于局部最优,多维函数求解精度差等问题,针对这些问题提出改进的麻雀搜索算法ISSA。首先,利用反向学习策略初始化种群,增加种群多样性;然后,对步长因子进行动态调整,提高算法的求解精度;最后,在侦查预警的麻雀位置更新公式中引入Levy飞行,提高算法寻优能力和跳出局部极值的能力。将ISSA、SSA和其他算法在8个测试函数上进行求解,并进行秩和检验,仿真结果表明,ISSA具有更高的寻优性能。还将ISSA应用到认知无线电的频谱分配中,实验结果表明,ISSA的系统效益和公平性优于其他算法,验证了ISSA在实际应用中的可行性。     

一种改进的协同优化算法及其应用

针对协同优化方法收敛困难、优化效率低的问题,提出了一种改进的协同优化算法—ICO算法。通过引入自适应松弛因子将一致性等式约束转化为不等式约束,同时建立混合惩罚函数,将系统级约束优化问题转化为无约束优化问题,ICO算法较好地克服了传统协同优化算法难于收敛的缺点。标准算例实验结果表明,ICO算法能够有效提高优化的稳定性、可靠性和计算效率。优化结果显示了协同优化算法解决海洋供应船的设计优化问题的有效性,为解决更为复杂工程系统的设计优化问题奠定了基础。