IMPROVEMENT AND REALIZATION FOR THE MAXIMUM WEIGHT MATCHING ALGORITHM

Some new concepts of effective incidence matrix,ascending order adjacency matrix andend-result vertex are introduced,and some improvements of the maximum weight matchingalgorithm are made.With this method a computer program in FORTRAN language is realized onthe computers FELIX C-512 and IBM-PC.Good results are obtained in practical operations.

基于Contig的单面基因组框架填充2-近似算法

随着基因测序技术的持续发展,基因组框架填充问题受到广泛关注。该文针对基于contig的单面含重复基因的基因组框架填充问题开展研究。通过设计有效的近似算法,完成根据参照基因组,将缺失基因填充至基因测序获得的不完整框架中,提高基因组框架的完整性。前期研究的基因组框架填充问题,缺失基因可以插入到不完整序列的任意两个基因之间,而基于片段重叠群(contig)的基因组框架填充,缺失基因的插入位置被限制在两个contig之间,更具一般性,该问题已被证明是NP完全问题。现有的近似算法中,2-近似算法处理的实例具有特殊性,2.57-近似算法针对一般实例,但近似性能比不够理想。该文以缺失基因、基因位点和断点三者之间的对应关系为基础,采用贪婪策略和最大匹配相结合的方式避免在填充过程中出现冗余公共邻接,并通过生成新的contig增加外邻接的数量,将针对一般实例的算法近似性能比提高到2,完成了基于Python的可视化程序开发,进一步验证了算法的有效性。

基于预训练模型的中文电子病历实体识别

为提升传统中文电子病历实体识别预训练模型的语义特征提取能力并增强中文隐含特征表示,提出基于改进预训练语言模型的医疗命名实体识别方法。提出动态词长的逆向最大匹配算法对病历文本进行标注歧义处理,在此基础上构建用户自定义医疗实体字典辅助PKU分词,提高预训练模型掩码效果。输入向量层加入字向量,引入注意力机制学习字向量的全局语义特征。改进预训练模型mask策略和机制并去掉下一句预测,提升词向量语义表征能力。实验结果表明,该方法有效提高了医疗实体的识别效果,F1值达到90.57%。

Time Complexity Analysis of an Evolutionary Algorithm for Finding Nearly Maximum Cardinality Matching

Most of works on the time complexity analysis of evolutionary algorithms havealways focused on some artificial binary problems. The time complexity of the algorithms forcombinatorial optimisation has not been well understood. This paper considers the time complexity ofan evolutionary algorithm for a classical combinatorial optimisation problem, to find the maximumcardinality matching in a graph. It is shown that the evolutionary algorithm can produce a matchingwith nearly maximum cardinality in average polynomial time.

基于正则表达式的变电站集中监控信息解析方法

随着国家电网公司"大运行"体系建设的深入开展,海量、繁杂且存在不规则现象的集中监控信息的识别,已成为设备监控信息智能告警技术提升面临的主要问题。文中结合集中监控信息既定规则的特点,提出一种基于正则表达式描述的集中监控信息解析方法。通过正则表达式规则提取信息关键要素进行信息解析,并采用最大分词匹配算法进行信息识别匹配,实现变电站集中监控信息实时解析及自动校验,为设备监控信息智能告警技术的进一步提升奠定了良好基础。实际工程应用验证了所提方法有效性和实用性。

一种改进的中文分词正向最大匹配算法

正向最大匹配分词FMM(Forward Maximum Matching)算法存在设定的最大词长初始值固定不变的问题,带来长词丢失或匹配次数较多的弊端。针对此问题提出了根据中文分词词典中的词条长度动态确定截取待处理文本长度的思想,改进了FMM算法。与此相配合,设计了一种词典结构,使之能够有效地支持改进的算法。改进的算法与一般正向最大匹配算法相比大大减少了匹配次数,分析表明中文分词的速度和效率有了很大提高。

基于Lucene的中文字典分词模块的设计与实现

在分析Lucene语言分析器结构的基础上,采用基于中文字典的正向最大匹配分词算法,设计实现能够在基于Lucene的搜索引擎中处理中文信息的中文分词模块。

自然语言表达实时路况信息的路网匹配融合技术

目前我国大中城市交通信息采集和传输的技术瓶颈已经基本解决,但是实时交通路况信息难以进一步与底层路网空间信息匹配和融合,造成大量路况信息难以得到有效应用,直接影响车载导航系统、公众出行信息平台、物流运输系统等位置服务(LBS)与智能交通系统(ITS)应用的服务水平。本文针对多以自然语言表达的实时路况信息与路网空间信息匹配融合这一技术难题,分析了实时路况信息的多源异构线性参照方法(LRM)表达形式,将中文自然语言理解技术融入信息融合过程,利用改进最大匹配算法实现了自然语言表达实时路况信息的自动化、智能化处理,并通过原型系统实现和实例应用验证了技术方案的有效性。

综合最大匹配和歧义检测的中文分词粗分方法

中文分词是中文文本信息处理的重要预处理。针对目前中文分词中存在的准确率低和粗分结果集大的问题,在最大匹配算法基础上,采用文本切分时的组合歧义检测和交叉歧义检测以及全切分算法,提高了文本粗分的准确率,并减小了粗分结果集的规模,为进一步正确分词奠定基础。通过公共语料库数据集的实验对比,取得很好的效果。

基于正向最大匹配算法的电力两票安全识别

为了让计算机具有处理甚至理解自然语言的能力,人们发明了很多自然语言语义分析理论。但是应用在电力系统工作票和操作票的领域中还很少。在中文分词的理论基础上利用正向最大匹配算法,针对电厂两票安全措施的语句进行自动识别,并分析了两票安全措施语句的语意。结果表明基于两票填写内容=动作词+设备名称词+状态词这种表示结构下,计算机能够很好的识别和理解电厂两票安全措施。这样计算机系统就能够对电力两票知识进一步的计算和推理,从而为深度人工智能开票提供了广泛的应用前景。

基于改进Trie树结构的正向最大匹配算法

提出一种改进的Trie树结构,树节点记录了字符串与构词的位置信息,子节点采用哈希查找机制,在此基础上优化了中文分词的正向最大匹配算法。分词过程中利用自动机机制判断是否构成最长词,解决了正向最大匹配算法需要根据词长调整字符串的问题。算法时间复杂度为1.33,对比试验结果表明有较快的分词速度。基于改进Trie树结构的正向最大匹配算法提高了中文分词速度,尤其适用于词典结构需要实时更新的场合。

基于双哈希结构的整词二分词典机制

为提高逆向最大匹配分词算法的速率,分析传统的整词二分词典机制,针对哈希结构尾字词典的不足,提出一种基于双哈希结构的整词二分词典机制,并改进对应的逆向最大匹配算法。利用记录词长的尾字词典机制,使用双哈希结构保存词条,降低词典的词条匹配时间复杂度。实验结果表明,该词典机制将逆向最大匹配算法的分词速率提高近一倍。

基于语义与最大匹配度的短文本分类研究

为了解决基于VSM方法在进行短文本分类时存在的严重数据稀疏问题,提出了基于语义与最大匹配度的短文本分类方法。以《知网》为知识源,设计了基于义原距离、义原深度与区域密度的义原相似度计算方法,实现基于词类的词语相似度计算;提出了基于语义与最大匹配度的方法计算短文本相似度,应用KNN算法进行短文本分类。实验结果表明,该方法与基于语义、基于AD_NB等方法相比,正确率、召回率和F值均得到了明显的提高。

基于Viterbi改进算法的高棉语分词研究

采用最大匹配算法对高棉语进行分词准确率较低,且难以正确识别词库中没有的新词。针对该问题,采用改进的Viterbi算法,利用自动机实现音节切分,通过最优选择及剪枝操作提高分词效率,以统计语言模型对未知新词进行数据平滑,提高识别正确率。实验结果表明,改进的Viterbi算法具有较高的分词效率和准确率。

求二部图的最大匹配图的一种算法

一个图的最大匹配图是以这个图的最大匹配集作为顶点集,两个顶点相邻当且仅当这两个最大匹配恰有一条边不同.本文首先对Gallai-Edmonds结构定理中的三部分顶点在二部图中进行了详细刻画.然后讨论了构造最大匹配图问题的计算复杂性.最后深入研究了二部图最大匹配图的结构性质并给出了构造二部图的最大匹配图的一种算法.

一种新的基于局部重力图逼近的组合匹配算法

惯性导航系统定位误差随时间积累发散,利用重力场辅助惯性导航已成为组合导航领域的新方向,该技术对实现潜艇无源定位意义重大.首先利用二维高斯基函数对局部离散格网重力异常基准图进行逼近获取其解析表达式,在此基础上对传统相关极值匹配算法进行重新建模,采用拟牛顿BFGS非线性寻优方法对该模型进行解算,最终完成基于连续解析形式重力异常基准图的相关极值匹配算法设计.为进一步提高算法性能进行以下两点改进:(1)采用TERCOM算法进行预匹配以缩小寻优范围提高寻优速度;(2)采用差分法减小实测过程中Etvs效应对重力匹配的影响.最后在2′×2′卫星测高反演重力异常数据库基础上进行了三组对比仿真实验,从实验结果可以看出,在重力测量误差、系统误差及初始定位误差较大的情况下,通过该组合匹配算法获得的匹配定位仍能以较高的精度跟踪真实航迹,且其性能较传统单一匹配算法有较大提高.

一种实用的资源稀缺条件下的分词方法

在一些使用人数较少的语言中,缺少人工标注语料,研究在资源稀缺条件下的分词方法成了亟待解决的问题。研究了无监督的VE算法,以及最大匹配间隔标注算法,在此基础上提出一种无监督分词方法与最大匹配方法相结合的分词方法,并在汉语语料上进行实验。该分词方法显著提高了最大匹配分词方法的分词效果,同时也优于当前最好的无监督分词结果。实验表明,该方法快速、有效,利用较小的资源获得了较好的分词效果。

中文分词中的正向增字最大匹配算法研究

针对正向最大匹配算法的长词丢失、匹配次数较多、歧义字段处理的准确率较低等问题,基于Trie树词典提出了3种正向增字最大匹配算法,分别使用逐词扫描、尾部折半扫描和尾部减一扫描这3种扫描方式采集歧义字段,并建立了一套歧义处理方法。实验结果表明,该3种算法在分词速度和准确率上均有显著提高,错误率降低到了原算法的三分之一以下。当文本规模大于200 MB时,3种正向增字最大匹配算法的分词速度均比原最大匹配算法提高30%以上。

基于字、词、词组的中文搜索引擎分词系统

分析了全文检索系统中常用的基于字表和基于词表的中文分词方法的优缺点 ,提出了基于字、词、词组混合模型的中文搜索引擎分词系统 ;并利用广义语词概念 ,设计了分词词典 ,改进了最大匹配分词算法 (MM) ;最后把分词系统应用于全文检索中。

基于最大匹配和歧义检测的中文分词粗分方法

中文分词是中文文本信息处理的重要预处理。针对目前中文分词中存在的准确率低和粗分结果集大的问题,在最大匹配算法基础上,采用文本切分时的组合歧义检测和交叉歧义检测以及全切分算法,提高了文本粗分的准确率,并减小了粗分结果集的规模,为进一步正确分词奠定基础。通过公共语料库数据集的实验对比,取得很好效果。