一种多层级二分图最大匹配问题的快速算法

本文提出一种新的二分匹配问题模型,该问题的特点是待匹配的对象包含子对象,即存在父子关系,在对子对象进行匹配的同时也需要对父对象进行匹配。该模型可应用于多种场景,典型的场景如数据库模式匹配、团队比赛匹配。本文针对该匹配问题,提出一个多项式时间的算法,该算法的整体思路是将问题分解为2个经典问题的组合:二分图最大匹配和最大权匹配。这2个经典问题都有成熟的算法可以解决,分别是匈牙利算法和KM算法。算法在组合的过程中采取了贪心策略,在子对象这一层应用最大匹配问题,之后将匹配数作为权值,在父对象这层应用最大权匹配问题,从而得到最终结果。本文给出了其正确性的证明,并对算法的性能进行了实验分析。

基于反序词典的中文逆向最大匹配分词系统设计

介绍几种常见的分词算法,在改进传统的反序词典、优化逆向最大匹配算法的基础上,设计并实现基于逆向最大匹配的中文分词系统,试验证明速度和精度都有显著提高。

最大匹配图的围长(英文)

将一个图的所有最大匹配作为顶点集，称两个最大匹配相邻，若它们之一通过交换一条边得到另一个，由此所得图为该图的最大匹配图．本文研究了最大匹配图的围长，从而给出了最大匹配图是树或完全图的条件．

全二分最大匹配快速分词算法

分词对于中文信息处理的诸多领域都是一个非常重要的基本组成部分,对于诸如搜索引擎等海量信息处理的应用,分词的速度是至关重要的。该文在对中文编码体系和中文分词的算法进行研究的基础上,提出一种新的分词词典,基于这种分词设计了一种快速的分词算法,给出了算法的实现过程。

最大匹配问题的DNA表面计算模型

本文给出了一个最大匹配问题的DNA表面计算模型 ,我们在表面上逐步生成解空间的同时 ,利用酶切技术删除所产生的“不可行解” ,从而大大减少了最终生成的解空间 .最后 ,我们还研究了边的排列顺序对解空间的生成过程的影响 .结果表明 ,通过对图中的边进行合理的编排也能减小不可行解的生成 .

基于Hash结构的逆向最大匹配分词算法的改进

分析中文的语义,首先要对句子进行分词。中文分词是中文信息处理中最重要的预处理,分词的速度和精度直接影响信息处理的结果。对传统的分词词典和算法进行了改进,提出了基于Hash结构的分词词典机制,并给出了一种改进的逆向最大匹配分词算法(RMM)。该算法在重点考虑切分速度的同时兼顾了切分精度,在很大程度上消除了传统的最大匹配算法可能产生的歧义。实验结果表明,该分词算法在运行效率和结果的准确性方法有了很大的提高。

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

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

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

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

一种最大匹配问题DNA计算算法

DNA计算作为基于生化反应的一种新的计算模式,凭借其巨大的并行性和海量的存储能力已经成为解决NP难题的潜在解决方案之一.把传统计算机中的剪枝技术引入到DNA计算算法的设计中,提出一种基于Adleman模型生物操作与粘贴模型解空间的最大匹配问题DNA计算新算法.算法由图编排器、预解空间生成器、匹配生成器及最大匹配搜索器组成.与已有同类算法的对比分析表明:该算法在保持多项式操作时间的条件下,将求解最大匹配的解空间从O(2m)减少到O(1.618m),将DNA计算机在试管内可求解的最大匹配问题的规模从60(260≈1018)提高到86(1.61886≈1018).同时,与传统的穷举算法相比,该算法具有高效的空间利用率及容错技术的优点.

基于Tile自组装模型的最大匹配问题算法研究

Tile自组装模型作为一种重要的DNA计算模型,在解决NP问题时展现出了巨大优势.文中针对现有最大匹配问题DNA计算算法实验操作复杂,错误率高的缺点,提出了一种基于Tile自组装模型的最大匹配问题新算法.算法所需的Tile分子种类为O(mn),所需生物操作数为O(1),计算时间为O(m),计算空间复杂度为O(mn)(其中m为边数,n为顶点数,且O(m)=O(n2)).与现有的最大匹配问题DNA计算算法相比,本算法不仅可靠性更好,而且更具可操作性.

基于逆向最大匹配分词算法的汉盲翻译系统

汉盲翻译是把汉字源文本自动翻译为对应的盲文文本,目前存在着多音字混淆、未登录词不能增加、不符合盲文分词连写规则等挑战。构建一个基于逆向最大匹配分词算法的汉盲翻译系统,能够较好识别多音字,自主添加未登录词,得到较正确的分词连写结果,有效提高了汉盲翻译的准确率。该系统基于词库可以区分出大多数多音字,能够得到较符合盲文分词连写规则的分词结果,并可向词库自主添加未登录词,进而提高中文分词的准确率。实验结果表明该系统能够降低因中文分词错误引起的语句歧义,减少因多音字混淆引起的翻译错误,避免因音节结构分散导致的盲文方数繁多,具有一定的开放性和实用性。

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

最大匹配算法包括正向最大匹配和逆向最大匹配两种算法,是中文分词领域的基础性算法,目前被广泛应用于众多领域。文中在详细分析了最大匹配算法的优缺点的基础上,提出了一种改进的最大匹配分词算法。改进算法在分词前先对词库进行了规范化预处理,分词时由汉字检索到该字开头的词组,再按词组长度由长到短的顺序使用传统最大匹配算法检索词库。目的是解决传统方法匹配效率低下和不能切分长词的问题。经算法分析结果表明,改进的算法较传统的最大匹配算法高效,分词能力更强。

基于优化最大匹配与统计结合的汉语分词方法

汉语自动分词是中文信息处理的前提,如何提高分词效率是中文信息处理技术面临的一个主要问题。基于词典和基于统计的分词方法是现有分词技术的主要方法,但是前者无法处理歧义字段,后者需要大量的词频计算耗费时间。本文提出优化最大匹配与统计结合的分词方法,首先提出优化最大匹配算法,在此基础上提出了规则判断与信息量统计两种消歧策略。然后,给出了优化最大匹配与统计结合的分词算法,提高了分词的效率。最后,基于分词算法实现中文分词系统,并通过实验对算法进行了分析和验证。

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

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

基于改进最大匹配算法的中文分词粗分方法

中文粗分和歧义消解是中文分词的两大基本过程。通过引入广义词条和诱导词集,在最大匹配算法基础上提出一种中文分词的粗分方法,以最长广义词匹配为原则进行中文分词,利用诱导词集实现交叉型歧义识别。在保证快速准确切分无歧义汉语语句的同时,100%检测并标记有歧义汉语语句中的交叉型歧义,最大程度上简化后续歧义消解过程。通过对含有160万汉字1998年1月人民日报语料测试的结果证明了算法速度、歧义词准确率以及粗分召回率的有效性。

最大匹配问题的三链DNA计算模型

三螺旋结构的DNA链具有稳定性,在一定条件下易分解等特点,因此得到的三链模型具有错解率低的优点。利用三链模型来讨论最大匹配问题,拓展了DNA计算解决问题的方法和应用领域。

多部图的最大匹配算法

匹配理论是图论中一个重要的分支,已被广泛地应用于许多领域,如组合优化、线性规划、人工智能和矩阵论等.给出一个求解多部图的最大匹配算法,并用仿真例子说明其实用性和有效性,此算法为解决复杂的指派问题开辟了新途径.

改进的正向最大匹配分词算法

为了降低正向最大匹配分词算法的切分错误率,分析了产生这个错误率的原因,提出了一种改进的正向最大匹配分词算法,即增加一个交集型歧义字段处理模块。该方法对待切文本进行预处理,在传统正向最大匹配的过程中,调用交集型歧义字段处理模块,该模块主要是在每一次正向匹配后进行回溯匹配,即通过检测当前处理词条的尾字和下一字的成词情况,分别计算该尾字和不含该字的当前处理词条的互信息与尾字和下一字的互信息,通过比较两者的互信息大小来决定切分,最后对分词碎片进行了处理。通过对随机抽取的语料进行测试,结果表明该方法是有效的。

一种求解二部图最大匹配问题新算法及其应用

提出了解决二部图最大匹配问题的分层网络优化算法,并应用新算法对排课问题进行求解。定义了分层网络的概念及匹配的规则,结合广度优先搜索策略生成分层网络体系,然后按网络逆序找出最大匹配。实验表明,算法在解决大规模二部图最大匹配的理论问题和实际应用问题时均能获得准确的结果,具备良好的性能。

最大匹配问题的粘贴DNA算法

最大匹配问题(MMP)是图论中经典的组合优化问题。针对此问题提出了基于DNA粘贴计算模型的求解算法,阐述了该算法如何利用DNA链构建最大匹配问题的初始编码,说明了应用粘贴计算模型寻求最终解的生物操作过程,同时分析了此DNA并行算法的计算复杂度,最后给出了该算法的计算机模拟仿真结果和应用实例,得到了所给问题的最大匹配解,并对算法的可行性进行了验证和总结。