匹配算法论文精选(九篇)

第1篇：匹配算法论文范文

关键词：双边匹配理论；发展；应用；金融市场

中图分类号：F830 文献标识码：A 文章编号：1674-2265（2013）06-0020-04

2012年的诺贝尔经济学奖得主研究的一个重要问题是如何使不同的市场主体匹配起来，并且达到一个稳定的状态。同其他市场一样，金融市场的一项重要的功能就是把市场的一方主体与另一方主体匹配起来。但是如何使双方达到一个稳定匹配的状态，使匹配更有效率，是当前金融市场面临的一个核心问题。本文将对双边匹配理论的发展与应用进行梳理，并重点对该理论在金融市场的应用问题进行研究。

一、关于双边匹配理论

（一）双边匹配理论的起源与发展

罗思（Roth，1985）是最早明确公开提出双边匹配概念的，他不仅明确地界定了“双边”和“双边匹配”的概念，而且分析了双边匹配的现实案例。罗思认为双边就是指事先被指定好的两个互不相交的集合，而双边匹配是指在这些市场中双边人的匹配。

2012年诺贝尔经济学奖的颁布丰富了双边匹配问题的研究方法。诺贝尔经济学奖得主提出了“稳定匹配”的概念，从而使匹配由“个人理性匹配”①走向了“稳定匹配”。沙普利（Shapley）采用合作博弈理论，在比较了不同匹配方法的基础上，用“G—S算法”来保证总能获得稳定的匹配，这一算法还可对各方试图操纵匹配过程的做法加以限制。罗思在沙普利的理论基础上，通过一系列的研究，发现稳定是市场机制运行成功的关键因素，并运用这些研究成果重新设计了现有的很多市场匹配机制，使匹配更有效率。

（二）双边匹配理论与搜寻—匹配理论的关系

搜寻—匹配理论与双边匹配理论都起源于20世纪60年代，搜寻—匹配理论研究的是在“摩擦市场”中，哪些因素会影响求职者的求职策略、工作搜寻强度及失业持续时间，以及如何匹配市场上的空缺职位和失业者；而双边匹配研究的是在具有双边市场特征的市场上，如何使市场双方主体匹配起来，并且形成稳定的状态。戴翔（2012）指出，搜寻—匹配理论的核心思想是：因为现实中存在着各种交易摩擦，从而产生了搜寻与匹配成本，这最终会致使交易的不顺利；双边匹配理论的核心是双边市场的双方人如何达到一个稳定的匹配状态。搜寻—匹配理论的研究方法包括匹配函数、劳动力市场基准模型——DMP基准模型；双边匹配理论的研究方法包括G-S算法、H-R算法、线性规划方法等；搜寻—匹配理论主要应用在网络金融信息等方面，双边匹配理论的应用方面更广，主要包括劳动力市场、人与组织匹配、电子商务、器官捐献和金融市场的风险投资、企业合并、银行信贷等方面。

（三）稳定的双边匹配与有效配置②的关系

有效配置状态就是指处于帕累托最优状态。稳定匹配的概念强于帕累托最优匹配，因为每个稳定匹配是帕累托最优的，然而不是每个帕累托最优匹配都是稳定的。帕累托最优要求没有两个人希望匹配在一起并且需要对方的同意。相比之下，稳定匹配要求没有两个人希望匹配在一起，无论对方是否同意。

二、双边匹配理论在国内外的应用

学者们对双边匹配问题进行深入研究并加以提炼，针对现实中的双边匹配问题进行了分析，尝试用双边匹配决策理论来解释具体的现象和问题。双边匹配理论的研究结合实际应用背景进行了有实用意义的扩展，广泛地应用于很多领域。

（一）双边匹配理论在国外的应用

1. 实习生与医院的双边匹配。实习生与医院的匹配是匹配理论较早的运用。在美国有一个制度，医学院的学生毕业后都要到各医疗机构实习。在早期，医学院毕业生实习市场比较无序，双方匹配很不稳定。为了达到稳定匹配，这个市场引入了“全国住院医生匹配项目（NRMP）”，刚开始比较成功，但后来NRMP也遇到了问题。1995年罗思和他的同事合作，对已有的匹配算法进行了改进，从而使这个市场运行更加稳定。

2. 学生与学校的双边匹配。学生入学匹配问题也是较早提出的双边匹配问题之一，匹配双方是学校和学生。学生在学校的录取优先权排序是学校对学生的偏好排序，而学生对学校的偏好排序是传统匹配理论中的排序，匹配的目标是使学生与学校都达到满意的结果。张、塞特曼和谭（Teo、Sethuraman和Tan，2001）对新加坡小学生升入中学进行了研究，研究发现小学生和学校在匹配过程中诚实地表达自己的偏好有利于形成稳定的匹配结果。

3. 人—组织双边匹配理论的应用。关于人—组织的双边匹配，目前主要有两种观点：大多数学者认为人—组织的匹配就是组织成员的个人特征与组织特征之间的相互包容性；少数学者认为人—组织的匹配是组织成员的个人特征与组织特征之间的互补性。克里斯托夫（Kristof，1996）认为一致性匹配就是组织的价值观、目标、文化等基本特征与个人的价值观、目标、人格等基本特征在很大程度上都一样，而互补性特征就是组织和个人双方的特征可以互为补充。另外，卡普兰（Caplan，1987）构建了关于个人—组织匹配的模型，包括需要—提供匹配和要求—能力匹配两种模型。其中需要—提供匹配就是组织能提供满足个人需要的岗位；要求—能力匹配是个体的能力能够适应组织的需要。

4. 电子商务中双边匹配的应用。匹配理论在电子商务方面的运用起于20世纪，并一直运用到现在，而且运用面更广、更灵活。郑（Jung，2000）用人工智能的方法来研究电子商务中的双边匹配问题，并且获得了稳定的匹配结果。萨尔尼和克劳斯（Sarne和Kraus，2008）建立了在电子商务中面向多个人的分布式的双边匹配机制。

（二）双边匹配理论在国内的应用

国内关于双边匹配的研究起步较晚，相关的理论研究相对滞后，研究成果主要是应用方面，但是应用研究范围相对较窄，研究的领域主要包括高考招生、劳动力市场、电子商务和金融市场等。

1. 高考招生中的双边匹配理论应用。双边匹配理论在高考招生中应用的研究范围涵盖了稳定匹配方案的存在性、研究方法的选择、信息环境对匹配效率的影响等。温忠麟（2006） 使用操作性方法验证了校方优先方案和考生优先方案，即稳定匹配的方案是存在的。李坤明（2010）分析了完全信息条件和不完全信息条件下考生的偏好，表明信息环境对高考录取机制配置效率有重要的影响，反过来高考录取机制又对信息环境具有依赖性。

2. 劳动力市场中双边匹配理论应用。张成（2010）借鉴双边匹配理论在国外劳动力市场的应用，并结合国内劳动力市场的特点，利用双边匹配理论的语言建立模型对我国大学毕业生劳动力市场进行描述。赵希男等（2008）构建了组织中人—岗匹配的纵向匹配度和横向匹配度测算模型来测算人与岗位的匹配程度，并通过实际案例证实了模型的有效性。

3. 电子商务中的双边匹配理论应用。近年来电子商务飞速发展，在电子商务中基于电子中介买卖双方的匹配问题，是一个典型的双边匹配问题。对双边匹配理论在电子商务中应用的研究是由理论到实证层层推进的。徐晓辉和陈剑（2000） 从产品和服务的标准化程度、顾客对产品网上销售的态度和顾客体验度三个方面，提出了一个判断产品是否适合在网上销售的标准框架，从而开启了对产品电子商务匹配度的初步探讨。基于电子商务业务的特殊性，可能出现多对多的情况，张振华、贾淑娟等（2008） 将Gale-Sharply和H-R算法从理论上扩展到了“p-k”的情况，以处理多对多双边匹配问题。

三、双边匹配理论在金融领域的应用

在我国金融领域，有些市场是研究双边匹配理论的天然场所，但是国内外学者们对双边匹配理论在金融领域的应用只有一些具体金融方面的研究，至今未形成一个体系。目前的研究主要在风险投资项目、企业并购、投资以及银行信贷方面得到应用。

（一）双边匹配理论在风险投资中的应用

在市场经济活动中风险投资商与风险投资项目或者创业者的匹配是一种典型的双边匹配模式，最优秀的风险投资商期望能够选择最好的风险投资项目，最好的项目也期望能有一个最优秀的风险投资商对其投资。 索伦森（Sorensen，2007） 采用定量分析方法分析了风险投资商与风险投资项目的双边匹配效应，认为双边匹配模式对风险投资商和风险投资项目产生双向的正的积极影响。在国内，曹国华、胡义（2009）认为，风险投资家和创业者的合作都是为了获得最大价值，所以两者之间建立稳定的匹配关系非常重要。他们根据自身的评价标准选择与对方建立匹配关系的理论基础，建立了风险投资家和创业者之间的双边匹配模型，并加以应用。

（二）双边匹配理论在企业并购中的应用

目前，双边匹配理论在企业并购中应用的研究比较零散，大都是从企业并购活动的某一个方面来研究的，如战略匹配、资源匹配等单个方面的研究，缺乏一个系统性的研究。

刘仲英等（2004）研究了企业并购活动中的战略匹配问题，建立了EKMS柔性和环境不确定性的匹配模型。马锐军、张勇（2006）分析了企业并购中人力资源匹配的问题，他认为人力资源的匹配要以人的能力为核心的管理和人力资源能力建设为主要内容。张海珊（2007）将企业并购活动中的资源匹配分为资产匹配和能力匹配，并通过建立BP神经网络模型来判断并购双方总体的匹配性。

（三）双边匹配理论在银行信贷中的应用

双边匹配理论在银行信贷方面应用的研究比较少。文胜（2006） 认为我国银行信贷市场存在着两个有完全不同运行机制的市场——目标客户信贷市场和非目标客户信贷市场。目标客户信贷市场的议价过程可以采用递延接受算法，结果稳定；非目标客户信贷市场如果采用递延接受算法，运行结果不稳定，因此需要设计一个中央化的匹配程序以保证结果的稳定。张继军（2011）通过分析中小企业贷款现状和贷款难的原因及城市商业银行为中小企业贷款的实际案例，认为小银行和中小企业的贷款需求是匹配的。

银行和贷款客户之间的稳定匹配，对于银行来说，可以规避客户的违约风险、减少银行的不良贷款、实现银行的稳健经营；对于贷款客户来说，稳定匹配可以减少贷款客户的搜寻成本、贷款成本，实现企业的持续稳定经营。所以学者们有必要深入的研究双边匹配理论在银行信贷中的应用。

四、结论与启示

通过对目前国内外关于双边匹配研究文献的回顾与综述可以发现，国外学者对双边匹配问题进行了大量探索性的研究，并取得了一系列的研究成果。学者们在研究中明晰并扩展了双边匹配理论的应用背景，探索了匹配的目标和获得稳定匹配结果的算法，并尝试在研究中用双边匹配思想来阐明并解决现实中大量存在的、不同参与主体之间的匹配问题。2012年诺贝尔经济学奖的颁布必然将双边匹配理论的研究和应用推向一个新的阶段。

毋庸置疑，双边匹配理论尚处于发展过程中，还有许多尚待进一步明确的具体问题。另外，国内学者对双边匹配问题的关注和研究还相对较少，研究内容也较为分散。但是，在我国金融领域，有许多市场是研究双边市场理论的天然场所，尤其是在双边市场条件③下运作的银行卡市场。作为一种典型的双边市场，市场需求和供给均呈现独特性，发卡机构必须围绕双边用户的联合需求提品和服务、必须协调双边用户的需求以达到均衡。因此，加强对发卡机构、特约商户、持卡人、银行卡组织等多方匹配机制的研究，能从根本上提高银行卡市场的匹配效率，这对于竞争不断加剧的银行卡市场④而言，无疑是增强银行卡市场竞争力的有效途径。

注：

①匹配研究是从“个人理性匹配”概念入手的。如果每个人对其派遣结果是可接受的，这就是个人理性匹配。

②有效配置意味着在资源和技术条件限制下尽可能满足人类需要的运行状况。帕累托最优状态表示，当事物的状态在给定的约束条件内时，通过重新改变这种事物的状态使之满足可用的约束条件，已经不可能使任何一个人的处境按照自己的观点来说变得更好。

③罗切特和蒂罗勒（Rochet和Tirole，2004）将双边市场定义为，通过一个或几个平台能够使最终用户相互作用，并通过合理地向每一方收费而试图把双方维持在平台上的市场。双边市场涉及到两种类型截然不同的用户，每一类用户通过共有平台与另一类用户相互作用而获得价值。

④截至2011年底，银行卡发卡量累计超过28.5亿张，同比增长18%。银行卡跨行交易全年超过16万亿元、104亿笔，同比分别增长44%、24%。其中，POS跨行交易13.4万亿元，同比增长47%；ATM跨行交易2.3万亿元，同比增长37%。刷卡消费额超过16万亿元，同比增长超过50%，占社会消费品零售总额的比重预计超过40%，比2010年提高约6个百分点——中国行业研究网。

参考文献：

[1]Gale，Shapley.1962.College Admissions and the Stability of Marriage [J].American Mathematical Monthly， 69，（1）.

[2]Roth，mon and Conflicting Interests in Two-sided Matching Markets[J].European Economic Review，27，（1）.

[3]Teo C.P，Sethuraman.J，Tan.W.P.2001.Gale-Shapley stable marriage Problem revisited：issues and applications[J].Management Seienee，47（9）.

[4]李坤明. 基于双边匹配理论的中国高考录取机制研究[D].华南理工大学硕士论文，2010.

[5]张成. 双边匹配理论及其在我国大学应届毕业生劳动力市场的应用[D].华南理工大学硕士论文，2010.

[6]赵希男，温馨，贾建锋. 组织中人岗匹配的测算模型及应用[J].工业工程与管理，2008，（2）.

[7]徐晓辉，陈剑. 关于产品电子商务匹配度的研究[J].南开管理评论，2000，（4）.

[8]张振华，贾淑娟，曲衍国. 基于稳定匹配的电子中介匹配研究[J].控制与决策，2008，（4）.

[9]李晓慧. 基于优先级的双边匹配方法在B2B电子商务中的应用研究[D].西安电子科技大学硕士论文，2010.

[10]张海珊. 战略并购双方的匹配性研究[D].北京交通大学博士论文，2007.

第2篇：匹配算法论文范文

关键词：被动定位，匹配场，水下GPS，动目标分析

 

1.引言

声纳按照工作方式一般分为主动声纳和被动声纳。对于被动声纳，由于它不发射声波，它具有很好的隐蔽性，且具有作用距离远、不容易被发现等优点，在军事领域中有着很好的应用前景。近年来，世界各国都加紧了对被动定位技术的研究和开发，被动定位技术受到广泛的重视。随着水中兵器作用距离和打击精度的提高，对被动声纳的定位性能提出了更高的要求，远程定位问题引起人们的广泛关注，出现了多种新型的定位方法。

2.传统被动声纳定位技术及面临的问题

2.1 传统的被动定位技术

传统的水声被动定位技术是六十年代研究开发出来的,这类定位技术利用沿不同距离路径传播的水下声脉冲间的时间差或相位差对水面、水中目标进行定位，其典型代表就是三子阵法和球面内插法。三子阵被动测距方法是己经实用化了的被动定位技术，它是六十年代后期出现的噪声测距方法。它利用时延估计技术求出到达三个基阵的相对时延，然后得到目标的方位和距离。但是，三子阵定位方法对水声信道进行了简化，三子阵系统是在同一平面内进行定位的，它不考虑信道声速的垂直分布，也不考虑信道的多途效应。，动目标分析。，动目标分析。不过这种定位方法算法简单，而且对近距离声源定位能达到较高的精度，目前在工程上已经得到广泛应用。

2.2 传统被动声纳定位技术面临的问题

传统被动定位方法在理论和实际应用中都存在很大的缺陷，主要表现在以下两个方面。

2.2.1 远程定位精度不高

传统的被动定位方法，利用球面波或柱面波波前曲率的变化，通过测量各基元的相对时延，估计目标的距离和方位。测距精度与时延估计精度、目标距离、方位、基阵孔径、基阵安装精度等因素有关，其中时延测量精度是关键，然而对于有限的基阵孔径，随着声纳探测距离的增加，波前曲率的变化越来越小，加上信道传播起伏的影响，时延的精确测量以及距离信息的提取变得越来越困难，因此传统的定位方法难以实现远程定位。此外，由于海洋中的声速分布是不均匀的，特别在远距离定位时，声速的不均匀分布使传统的定位算法存在较大的误差。为此，研究人员必须寻求新的被动定位方法。

2.2.2 定位效果受声场环境影响大

由于海水介质的不均匀性，在海水信道中由于温度、盐度、压力的不同，导致了海水介质中各点的声学特性差异很大，特别是不同深度层的声学特性差异很大，导致了声波在海洋中的传播非常复杂，声传播受海洋信道的影响比人们想象的要大得多。要提高声纳的探测效果，必须要充分研究海洋信道特点。

3. 匹配场被动定位技术

匹配场声源定位是国际上新兴的水声定位方法，它根据海洋声信道性，在声场建模的基础上，运用一定的匹配场处理算法反演声源位置。匹配场定位技术充分利用了海洋信道特点来反演声源位置，因此它可以有效消除信道对定位的影响，它的定位精度比传统的被动定位精度高。

3.1 匹配场被动定位原理[1]

匹配场定位的被动原理图如图1所示。匹配场定位首先将水听器阵列接收到的数据经过傅立叶变换后计算频域协防方差矩阵。假设声场中某一位置有目标，已知海洋声场环境参数时，利用现有的声场模型可以计算出该目标声源产生声信号在接收水听器阵列处的声场值，通常称之为拷贝场向量。最后将拷贝场向量和测量信号的协方差矩阵进行匹配运算从而输出定位模糊表面，如果实际目标位置与假设声源位置一致，则匹配处理器有最大值输出，这样从定位模糊表面上可以读出目标的位置。

图1 匹配场定位原理图。

3.2 匹配场被动定位关键技术及发展趋势

匹配场定位有两个重要环节，一是拷贝声场的计算，二是匹配处理器的设计。拷贝声场可利用现有的声场模型计算得到。，动目标分析。现有的声场模型主要有简正波模型、声线模型、抛物方程模型等。其中，最常用的2种传播模型是射线模型和简正波模型。射线模型具有简捷、直观的特点，适用于描述深海声场。在浅海存在严重的多途和较强的海底散射，射线模型不再适用。简正波模型考虑了各种海底边界的影响，适用于研究浅海、低频的声传播问题。目前声传播模型的研究主要集中在快速、高精度的声场模型的研究上。

匹配处理器就是将拷贝场与实测声场进行匹配运算的算法，从理论上来说，匹配场处理器是传统的阵列信号处理的波束形成概念的推广，因此，很多传统的阵列处理方法都可以用于匹配场处理，而且人们已经证明其中的很多方法是很有效的。按照匹配场处理器的权向量是否与测量数据有关，将其分为线性匹配处理器（CMFP）和自适应匹配处理器(AMFP)。常用的MFP处理器有线性处理器(Bartlett)、最小方差估计器(MV)和匹配模处理器(MMP)。随着人们对传播理论研究的深入以及阵处理技术的飞速发展，匹配场处理技术的研究取得了一些突破性的进展。近年来，匹配场处理技术逐渐走向实用阶段，宽带、稳健自适应[1]、高分辨率[2]的匹配场处理技术成为研究热点，以试验研究带动理论研究成为主要的研究方法。，动目标分析。

4.水下GPS定位

水下GPS技术的设计灵感来自于GPS,该技术可以用于潜艇定位，进行爆炸军火处理，还能用于水雷对抗许多领域。水下GPS利用空间GPS系统在海洋中布放一系列声纳浮标，形成网格，在水面用空间GPS，在水下用水声通信。法国的ASCA公司已经开发了用水下全球定位系统进行搜索与救援的系统，它可以利用水下的GPS信号确目标的三维坐标。，动目标分析。该系统可以用于跟踪水下的飞机或潜艇中黑匣子的声波发器，从而找到目标。系统包括GPS浮标，控制站及声波发送器。浮标下有水听器，浮标通过水面上的三个天线与指挥、控制、通信等系统联系。利用目标发射的信号与浮标接收信号的时间延迟得到浮标和目标的相对位置，同时，利用分GPS接收机能精确测量出浮标的精确位置。空间GPS技术已相当成熟。，动目标分析。

5.结束语

由于传统的被动定位方法在理论和实际应用中都存在一些问题，研究人员致力于研究新的被动定位方法，其中匹配场被动定位技术充分利用了海洋信道，在远距离复杂水文条件下，其定位精度较高，有着诱人的应用前景，随着研究的不断深入，这项技术正逐步走向实用阶段，但匹配场的模型精确性，匹配算法的计算速度以及匹配场的定位的稳健性问题还急需解决。水下GPS技术系统使用条件相对苛刻，不适用于非合作被动目标的探测，工程应用受到了一定的限制。

参考文献：

[1]杨坤德,等.水声信号的匹配场处理技术研究[D].西北工业大学,2003,06.

[2]周俊山，陶进绪等.一种基于MUSIC算法的匹配场定位方法[J].电子技术，2010，01：21～23.

第3篇：匹配算法论文范文

关键词：双边匹配理论 敏感性偏好 个性化职业指导

中图分类号：C934 文献标识码：A 文章编号：1674-098X（2014）08（b）-0195-02

1 相关理论概述

1.1 双边匹配理论的内涵和主要类型

匹配理论作为新兴的经济学分支，最早被美国两位数学家David Gale & Lolyd Shapley（1962）提出并引用于大学录取与婚姻匹配问题，它是对市场匹配功能进行系统化研究而得出的，如工人和企业、学校和学生，其中“双边”指的是市场中的参与者始终只属于两个互不相交的集合之一，“匹配”指的是市场双边交换的本质，即各自“敏感性偏好清单”。

根据双边匹配理论的匹配稳定存在性而将其分为三种类型：一对一、多对一、多对多的双边匹配理论。

1.2 双边匹配理论的匹配算法

通过文献综述，对于双边匹配理论模型的算法可归结于两种：①Gale-Shapley递延接受算法，一般用于男女婚配。该算法能从任何偏好排序清单开始产生一个稳定匹配，最多经过n2-2n+2个步骤，使得参与人最终匹配或仍单身。②中央化的匹配（NIMP）算法――“尝试―派遣―最新修正”，20世纪初用于美国匹配优质类医学实习生问题。1998年起，美国绝大多数的职位匹配都是运用了加入补充性偏好的新中央清算程序，但是依然是以NIMP为基础。这一算法直至现在依然在为美国的劳动力市场匹配问题服务。这也便是本文匹配模型构建的算法依据。

2 双边匹配模型的构建设计

2.1 设计依据及思路

双边匹配模型是解决用人单位和毕业生在搜寻过程中双边“偏好”匹配问题，由此设计思路为：（1）双方“敏感性偏好”集的确定；（2）量化设计；（3）匹配计算。

2.2 “敏感性偏好”指标确定

依据双边匹配理论模型，敏感性偏好应该是参与一方对另一方的偏好集合，并能清楚的说明各偏好等级或具体排列顺序，因此评价指标需要界定与评价。评价指标的确定一般有个案研究法、问卷调查法、专题访谈法、经验总结法。

结合问卷调查及《国务院各有关部门直属企事业单位名录》和《毕业研究生用人重点单位介绍》为主要依据，将以下指标确定为企业对大学毕业生“敏感性偏好”指标。

大学毕业生对求职岗位的评价指标是毕业生在搜寻过程中根据自己满意的职位条件和待遇等因素最优先圈定求职企业范围的偏好指标。结合调研报告及闵维方、丁小浩教授的“高等教育规模扩展与劳动力市场”课题结论，确定大学毕业生对求职岗位的“敏感性偏好”指标如图2所示。

2.3 “敏感性偏好”指标的量化设计

对评价指标的量化是一项复杂工作，一般情况，对指标进行量化评价有两种方法：一是利用模糊数学理论进行模糊评价；二是利用运筹学的知识进行多目标评价决策。

本研究评价指标既有定量也有定性，评价方法应该多种方法结合起来。将偏好指标划分为①判断型指标一般为先决性指标，用1和0表示；②区间型指标，量化时可用区间段进行赋值；③语言评价型指标，一般分别赋值1，0.8等。

2.4 偏好集评分与匹配计算

依据匹配算法，由学生和用人单位分别对参与匹配的两个集合进行自我意愿的评价打分，得出各自的评分矩阵P和Q，进而进行NIMP匹配。依据Irving和Leather对改变稳定匹配指数仍可得到新的匹配集合的研究，引入匹配值。匹配值是人为确定双方匹配水平的数值，因实际匹配时不可能100%绝对匹配，只能形成稳定的满意匹配，通常为0.6≤≤1，匹配值越高说明双方匹配满意度越高。

可以看出，P0和Q0互为转置矩阵，而且恰好两者相互匹配。根据结果为1的元素显示，学生A1与求职岗位W1相互匹配；学生A2与求职岗位W3相互匹配，学生A3与求职岗位W2相互匹配。

基于以上算法原理，可借助计算机辅助技术完成相关匹配计算。

3 个性化职业指导设计与应用

3.1 个性化职业指导体系设计

个性化职业指导体系的提出是在双边匹配模型的基础上，针对在校三年级学生提出的，皆在让学生：①提早认清企业需求和自身现状；②模拟应招后，知道自己的企业认同度；③有针对性规划培养个人能力。本课题结合文献将个性化职业指导定义为：在对大学生能力、性格、兴趣、价值观等进行认识与判断的基础上，根据学生的身心发展进程和需求，积极提供相应的职业指导环境和条件，对学生进行有针对性的职业引导，进而促进大学生个性全面和谐健康地发展，特别注重发展其职业能力，提高其就业成功率，顺利完成从大学生到职业人的角色转型。结合高校就业指导中心的整体教学思路，提出“基于宏观、微观维度的指导体系图”。基于此，本课题组认为，个性化职业指导更适合运用于职业指导的微观维度。

3.2 基于双边匹配模型的个性化指导应用

通过双边匹配模型的指标获取可以帮助学生了解企业的真正需求与偏好，同时对自身的定位与企业“价值”能有更真实的了解。个性化职业指导主要是针对大三在校生通过匹配模型尝试“模拟“匹配后，适当培养更适合满意企业的技能和能力，从而实现毕业的真正匹配。

本研究在13年9月对本校10级学生8名学生进行应用，通过初次“模拟“匹配后，只有1名同学获得企业认可且匹配成功，其他学生均表现过高的期望值。之后对此8名学生进行个性化培养，主要侧重能力与满足企业需求角度。

（1）明确企业需求。

将企业需求调查情况与双边匹配中企业对学生偏好的数据传递给学生，是学生清楚当下职场对毕业生各项因素的偏好情况。

（2）重新评估自我。

通过专业软件测试帮助学生对自我性格、兴趣、价值观及能力进行初步测试并分析，联系实际使学生对自我认知更为客观，找到自身优势与劣势，并对前期的模拟求职进行重新思考和定位。

（3）探索求职需求。

通过自我的重新认知与定位，结合前期对企业的模拟偏好测试，明确将来的求职需求及范围。

（4）制定提升计划。

根据需求找到与目标的差距，制定改善计划，包括：专业知识技能、技术操作能力、专业实习实践（与偏好职业相关的）、综合性能力等方面，制定更佳详尽的短期、近期目标，并界定时间期限。

3.3 个性化指导成果

本课题组对参加测试的八名同学进行了个性化指导方案的设计与实施，2014年4月，在本校的招聘会上，我们又邀请了这八名同学进行了正式应聘测试，目的：1.帮助学生探究一年的针对性培养效果如何；2.帮助学生及企业进行初步匹配。重新登录偏好界面进行双方信息登记及偏好赋值，结果如下：

本次应用是以稳定最有效匹配为前提进行的，基于两矩阵的数值，取=（0.65，0.65，0.65，0.65），对P（学生对企业偏好值矩阵集）和Q（企业对学生偏好值矩阵集）进行NIMP的匹配计算，最终计算机得出匹配结果：学生1与求职岗位1匹配；学生3与求职岗位3匹配；学生4与求职岗位2匹配；学生7与求职岗位4匹配。

此次实践为四家企业及四位毕业生建立了匹配关系，经过双方进一步的面试沟通，最终均确定了雇佣关系。通过电话访谈的方式，对四组参与者就采用此方式确定的雇佣关系是否满意等问题进行回访调查，调查结果表明，企业都认为这种方式对其搜寻较合适的毕业生起到积极作用，节约了企业的招聘成本。同时学生认为一年的个性化指导对自身的提升效果较明显，运用匹配方式求职更加便捷。

参考文献

[1] Gale，D.and Shapley，L.S.College admissions and the stability of marriage[J].American Mathematical Monthly，1962（69）：9-15.

[2] Roth，Alvin E. Marilda Sotomayor.Two Sided Matching：A Study inGame-Theoretic Modeling and Analysis[M].New York：Cambridge University Press，1990.[D].

[3] 文胜.双边匹配理论及在中国银行信贷市场中的运用[D].华中科技大学，2006.

[4] 王远博.大学生失业的经济学原因探讨[J].经济问题探索，2005（2）.

第4篇：匹配算法论文范文

关键词：框架；智能预案；相似度；匹配算法

中图分类号：TP391.1 文献标识码：A 文章编号：1007-9599 （2013） 02-0000-03

1 引言

突发公共卫生事件应急系统的建立对于保障公共安全，建设社会主义和谐社会具有特殊重要的现实意义。目前国内外在应急响应领域已经取得了很大的进步，但对应急预案系统的研究才刚刚处于起步阶段。作为整个系统中最为基础和根本的一环，应急预案对于应急响应的实施具有重要作用。

本文通过对现有应急预案和应急响应过程的分析，通过框架技术对应急预案的知识进行表示，研究了预案的匹配算法，给出了预案相似度以及价值评估的计算方法。

2 智能预案匹配

应急预案是应急事件处置的领域知识来源。应急预案管理系统可以在对处置预案、资源分布转台、事件处置状态自动初步生成事件处置方案。再经过处置人员对初步方案进行调整，经过认可后即可作为高效地应急响应处理的指导方案。

2.1 基于框架的匹配

预案采用框架的智能化存储结构表示，预案的智能匹配自然和框架体系的匹配息息相关。基于框架体系的匹配系统一般由两大部分组成：

（1）由框架及其相互关联构成的知识库。提供求解问题所需要的知识；

（2）由一组解释程序构成的框架推理机。针对用户提出的问题，通过运用知识库中的相关知识完成求解问题的任务，给出问题的解；

2.2 匹配过程及算法

3.2 数据相似度研究

预案是介于数据与知识之间的一种知识存在形式，存储预案的框架结构具有不同数据类型的槽和侧面属性。计算不同数据类型属性的相似度，首先要讨论属性即槽值和侧面值的数据类型。一般来说，属性的数据类型分为以下三个大类。针对以上三大类型，分别来讨论其相似度算法。

4 结论

本文主要论述了智能预案框架表示与预案知识匹配机制。通过对现有应急预案和应急响应过程的分析，提出一个对应急预案的描述方法。利用框架结构完整的描述预案实体单元，依据各框架间的纵向联系和横向联系，从而形成框架网络。利用框架知识表示，研究了预案的智能匹配与相似度比对。最后讨论了预案相似度算法，给出了预案相似度以及价值评估的计算方法，讨论了预案框架中不同数据类型属性的相似度算法，重点研究了数值类型和文本类型的属性相似度算法。

参考文献

[1]Nilsson NJ. Artificial Intelligence： A New Synthesis[M].Copyrighted Matenal，2000.

[2]Sui YF，Gro Y， Cao CG.Ontologies， Frames and Logical Theories in NKI[J].Journal of Software，2005，16（12）.

[3]李晨阳，曹忠升，冯玉才.一种基于框架和中间件模型的知识库系统[J].计算机应用，2000（12）：1298-1300.

[4]张荣梅.基于CBR与MAS的智能决策支持系统研究及应用[D]：[硕士学位论文].北京：北京科技大学，2001.

[5]刘义刚.基于预案库的快速智能决策支持系统的研究[D]：[硕士学位论文].北京：北京理工大学，2001.

[6]杨健，赵秦怡.基于案例的推理技术研究进展及应用[J].计算机工程与设计，2008，29（3）：710.

[7]魏元凤，骆洪青，辛崇波.属性相似案例的检索模型比较研究[J].华东船舶工业学院学报，1999，13（4）：41-44.

第5篇：匹配算法论文范文

关键词:入侵检测;模式匹配;BM算法;AC算法;AC_BM算法

中图分类号:TP309文献标识码:A 文章编号:1009-3044(2010)04-0821-03

Application of Improved Algorithm for Pattern Matching in Intrusion Detection

WANG Da-yong

(College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China)

Abstract: With the rapid development of the network, the security question is outstanding day and day, intrusion detection technique nowadays becomes the focus which the people pays close attention to.An effcetive and precise pattern matching algorithm is important to intrusion decetion system. In this paper, based on the analysis of existing pattern matching algorithms,proposed an improved algoruthm for AC_BM, the algorithm and model in the text after the failure of a particularmatch, skipping as many characters, in order to achieve faster matching process. Results show the improved algorithm greatly improved the performance of detection.

Key words: intrusion detection; pattern matching; BM algorithm; AC algorithm; AC_BM algorithm

随着网络技术的高速发展,个人、企业以及政府部门越来越多的依靠网络传递信息,然而网络的开放性与共享性容易使它受到外界的攻击与破坏,信息的安全保密性受到严重影响。网络安全问题已成为世界各国政府、企业及广大网络用户最关心的问题之一。试图破坏信息系统的完整性、机密性、可信性的任何网络活动都称为网络入侵。

传统的防火墙技术只是一种被动防御性的网络安全工具。首先,入侵者可以找到防火墙的漏洞,绕过防火墙进行攻击。其次,防火墙对来自内部的攻击无能为力。它所提供的服务方式是要么都拒绝,要么都通过,而这是远远不能满足用户复杂的应用要求的。于是就产生了能够主动检测并预防的入侵检测技术。入侵检测技术作为一种积极主动地安全防护技术,已成为网络安全研究领域中的热点[1]。

根据入侵检测系统对数据分析方法的不同,可将其分为两大类:误用检测和异常检测。误用检测是指:根据己知的攻击方法,预先定义入侵特征,通过判断这此特征是否出现来完成检测任务。异常检测是指:根据用户的行为或资源的使用状况的正常程度来判断是否属于入侵[2]。由于异常检测的误检率和漏检率高,因此目前大多数人侵检测系统产品均主要采用误用检测的方法。据统计,现在大约95%的入侵检测都是特征匹配的入侵检测。由此可见,模式匹配算法性能的好坏将直接影响到入侵检测系统的效率。在已有的模式匹配算法中,主要有Boyer-More(简称BM算法)、Aho-Corasick(简称AC算法),AC_BM算法等。本文在分析以上算法的基础上,提出了一种新的改进的AC_BM算法。

1 现有模式匹配算法的分析

1.1 BM算法

BM算法是由R.Boyer和J.Moore提出的一种快速字符串匹配算法。著名的开放源代码的入侵检测系统snort采用的就是BM算法[3]。BM算法的主要思想:BM算法区别于KMP算法,它采用从右向左比较的方法,当匹配发生失败时,模式T右移的计算方法发生了较大的变化。为方便讨论,对给定的模式T=t0t1t2…tm,定义一个从字符到正整数的映射:

dist : c->{1,2,…,m+1}

函数 称为滑动距离函数,它给出了正文中可能出现的任意字符在模式中的位置。函数dist定义如下:

m-j,j为c在模式中的下标,以后面的为准

dist(c)=m+1,若c不在模式中或c=tm。例如,T=”pattern”,则dist(p)=6-0=6,dist(a) =6-1=5,dist(t)=6-4=2,dist(e)=2,dist(r)=1,dist(n)=6+1=7。BM算法的基本思想是:假设将主串中自位置 起往左的一个子串与模式进行从右到左的匹配过程中,若发现不匹配,则下次应从主串的i+dist(si)位置开始重新进行新一轮的匹配,其效果相当于把模式和主串向右滑过一段距离dist(si),即跳过dist(si)个字符而无需进行比较。因为在实际应用中,字符表中的大部分字符不出现在模式串中,所以应用BM算法可以大大加快串匹配的速度。

但是随着入侵方法、方式的多样性,入侵的匹配规则也在急速上升,这时仅用BM算法来进行规则匹配,就显得力不从心,效果不佳。

1.2 Aho-Corasick算法

Aho-Corasick算法(简称AC算法)是同时搜索多个模式的经典匹配算法。由贝尔实验室Alfred V.Aho和Margaret J.Corasick发明,最早被使用在图书馆的书目查询程序中,取得了很好的效果[4-5]。AC算法使用了有限状态自动机的结构来接收集合中所有的字符串。自动机是结构化的,这样每个前缀都可用唯一的状态来标志,甚至是那些多个模式的前缀。当文本中的下一个字符不是模式中预期的下一个字符中的一个时会出现一条失败链指向那个状态。代表最长的模式前缀同时也是当前状态的相应后缀。AC算法的复杂性是o(n),预处理阶段的复杂性是o(m)。在用AC算法构造的有限状态自动机中,要为每一个模式串的每一个字符建立一个节点,这样无疑使得该算法的空间使用效率很高。

有限自动机算法是以空间换时间的经典算法,当模式集较大时可能产生空间膨胀问题。AC算法在对输入串进行搜索时没有跳跃而是按顺序输入无法跳过没必要的比较因此在规则不是非常多的实际搜索过程中AC算法性能不佳。

1.3 Aho-Corasick_Boyer-Moore(AC_BM)算法

AC_BM算法把Aho-Corasick和BM算法结合在一起,它具有AC算法的多模式匹配和BM算法的滑动跳跃式移动的特点,并具有线性时间复杂度。AC_BM算法将具有相同前缀的不同模式放在一棵模式树上,然后对这棵树使用BM算法进行匹配[6]。AC_BM算法不像标准BM算法那样一次只移动一个模式,而是移动整棵模式树,同时使用不良字符和良好后缀进行跳跃,以消除不必要的比较。

AC_BM算法尽管效率比BM,AC算法优越,但是构造模式树的速度比较慢,在构造树的过程中会导致内存浪费,并且节点个数多和无规则性导致了状态转向的速度慢,动态增删模式串也比较麻烦。

2 新的模式匹配算法

随着网络流量的迅速增加,以上各种算法的匹配规则和匹配效率已经不能完全适应高速网络的要求,尤其是如今的检测规则在不断增加,对每个数据包可能要匹配的次数也在飞速增加,因此其性能不能完全被满足。在这种情况下,我们在AC_BM算法的基础上并充分结合QS算法中充分利用本次匹配不成功的思想,在文本与模式某次匹配失败后,跳过尽可能多的字符,实现更快的匹配过程。

QS 算法是一种简化的 BM 算法,可以描述为:当P[1…n]与T[i…i+n-1]对齐,就进行匹配,若匹配失败,则分析T[i+n]这个字符,来决定P[1…n]右移的距离,因为当某一次匹配失败后,模式至少向右移动一个位置,在一般情况下,T[i+n]这个字符会出现在下一次的匹配过程中,于是在匹配失败后,可先考虑T[i+n],而不是T[i…i+n-1]中的字符,使得模式的最大右移距离为n+1,而 BM 算法中模式的最大右移距离为n [7]。

改进之一:改进的AC_BM 算法中,当文本与模式树某次匹配失败后,对文本T[i…i+n-1]左边的字符T[i-1]使用坏字符移动,对文本T[i…i+n-1]使用好前缀移动,文本指针移动的距离取其中大的一个,最大移动距离为minlength+1,minlength为模式集合中最短模式的长度。对于文本中任一字符ω,坏字符移动函数可定义如下:

如果ω出现在{P}中,执行*式,否则执行**式。

改进之二:AC_BM 算法在每次文本与模式树匹配失败后都要计算坏字符启发函数和好前缀启发函数,然后取最大值作为偏移量,然而计算好前缀启发函数的时间开销较大,因此,我们在改进的 AC_BM 算法中采用坏字符优先的策略,当利用坏字符启发能得到n或n+1的偏移量时就不再计算好前缀启发函数,而且当模式树在文本中的出现较为稀疏时,改进的 AC_BM 算法在大多数移动过程中可容易得到n+1的最大偏移量,这样就可避免好前缀启发函数的计算,从而可大大缩短模式匹配所需要的时间。

下面对改进的 AC_BM 算法的性能进行分析。改进的 AC_BM 算法预处理阶段时间复杂度为o(|∑|+|P|),这里的|∑|是字符集大小,|P|是模式集P中所有模式长度的总和。最佳性能情况:在每次进行模式树第一个字符与文本比较时都不匹配,且具有最大的偏移量minlength+1, 改进算法具有最佳性能,此时的比较次数为

时间复杂度为o()

最差性能情况:在每次都进行到模式树中最长模式的最后一个字符与文本比较时才发生不匹配,且具有最小偏移量 1,改进算法具有最差性能,此时的比较次数为minlength+[n-2(minlength-1)]maxlength,时间复杂度为o(n maxlength)。平均情况下的时间复杂度与字符的出现概率有关,因此需要通过概率模型进行计算,平均情况下的算法的性能通过找出不匹配字符所花的代价和发现该不匹配后能够移动的距离之比的概率平均值来确定,因为改进的AC_BM 算法在坏字符移动时与原算法不同,因此只需要比较改进算法与原算法在坏字符移动时的平均性能情况,根据上述的确定方法,其平均性能

,

Ccost(i)为计算skip函数所花的代价Sskip(i)为发现字符不匹配后平均能够跳过的字符,而式中Pskip(i,k)为查询第i个字符时,发现不匹配后能够跳过k个字符的概率,而在 AC_BM 算法中

显然,改进的 AC_BM 算法中Sskip(i)比 AC_BM 算法要大,而通常情况下分子Ccost(i)相同,因此改进算法比 AC_BM 算法具有更好的平均性能。

3 实验分析

为了对各个算法的性能、效率做具体的评测,在同一台计算机上进行了算法实现并进行了测试。实验机配置联想台式机,CPU Pentium双核4200,内存1G,硬盘160G,操作系统Windows2000,算法实现的环境是Visual C++6.0。试验中测试了BM,AC,AC_BM和改进的AC_BM算法。我们选取了10M 的纯英文字母作文本,选取长度为5,15,20,30,40,50 的字符作模式串,用上述几种算法进行搜索,比较它们的实际效率。最后得到以下一组数据,如表1所示。

从上面的测试数据可以看出,改进后的算法和前几种算法相比较,在匹配时间上明显缩短,尤其在模式串长度比较长的情况下。

4 结论

随着各种网络应用的不断出现以及网络带宽的不断增加,目前的网络入侵检测系统的处理性能已不能适应大流量网络环境的要求,这就迫切需要提高入侵检测系统的处理性能。本文对模式匹配算法BM和AC和AC_BM算法作了简要的分析,并提出了改进的AC_BM算法。将改进的算法应用到入侵检测系统中,可以有效地提高系统的检测效率。

参考文献:

[1] 曾志峰,杨义先.网络安全的发展[J].计算机工程与应用,2006,24(7):101-103.

[2] 周国民.入侵检测产品市场扫描[J].网络安全技术与应用,2004,12(5):64-67.

[3] Knuth D E,Morris J H,Pratt V R.Fast Pattern Matching in String[J].SIAM Journal on Computing,1977,11(6):323-350.

[4] Aho,A.V,M.J.Corasick.Efficient string matching:an aid to bibliographic search[J].Communications of ACM,1975,18(6):333-340.

[5] 唐正军.入侵检测技术导论[M].北京:机械工业出版社,2004:124-135.

第6篇：匹配算法论文范文

关键词：查找搜索；字符串匹配；KMP算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）20-4696-03

文本，一直是计算机这一领域中最基本的元素，无论是计算机刚诞生的年代，还是如今多媒体技术绚烂夺目的时代，文本一直都作为奠基性质的元老角色而存在着。

在对文本的编辑中，会遇到需要查找匹配特定模式的情况。比如，在一个文本文件中查找“ABC”这一小段，或者查找“不知道”这一词语。当文本的内容比较少时，人们可以通过简单的逐行查找来找到匹配的特定模式，然而，当文本具备一定的规模后，在其中查找特定的模式就足以令人抓狂了。

在当下这个信息大爆炸的时代，拥有大规模内容的文本实在不在少数，无论是金融界、文学界、政界还是计算机专业界，每天面对大量的文字信息实在令人欲罢不能，在其中寻找重要的关键词、关键句或者关键段落时，更是令人痛不欲生，即使是交给计算机去做，也需耗费大量的开销。因此，设计出一种好的算法，以高效地查找大容量文本文件中的特定匹配模式，不仅可以大大提高文本编辑的响应性能，还能改善人类的生活。

此外，随着学科之间交叉性的提高，很多领域也需要在大量的信息中查找某些特定模式及其出现的位置，例如DNA测序定位、海洋数据查询、高效搜索引擎等。

幸运的是，目前已经有了高效的字符串匹配算法，并且，此类算法仍在不断发展进化，向着更高的效率进发。

在本文中，作者研究分析了效率高超的KMP字符串匹配算法，并使用C语言对其进行了实现。

1 KMP算法研究与分析

历史上人们通过对字符串的研究而得出的字符串匹配问题的算法很多，其中很重要的一类匹配算法分为两步：第一步先对要匹配的模式进行一些预处理，第二步再寻找模式在全文本中的所有有效位移（即匹配）。KMP算法即是其中最高效的算法之一。

KMP字符串匹配算法，是由Knuth、Morris和Pratt三人设计的线性时间字符串匹配算法。假设要搜寻的模式有m个字符单位，整个文本有n个字符单位（一般来说n > m），则KMP算法所用时间花销在n+m这个数量级上，比起很多其他的算法要快不少。

KPM算法简单来说，可以从以下的事实获得灵感：对于在文本中搜寻特殊模式的情形来说，文本所包含的的信息毫无疑问比起特定模式要多得多，其不确定信息也更多。比如，在很长的文本中，下一个出现的字符可能是任何字符，变化可能会很大，然而，对于较短的确定的特定模式来说，在模式中出现的字符却基本上是确定的，因为模式是特别选出的，而且模式比起文本要短得多。一个最常见的例子就是在谷歌中搜寻“平板电脑”这一关键词，很明显，我们对“平板电脑”这四个字中所包含的信息可以说几乎完全确定，而对于在互联网中会出现什么样的网站能匹配这次搜索却包含着极大的不确定性。

因此，可以先对特定模式进行分析，得出所需要的信息，从而利用这些信息来加快匹配速度。

KMP的核心思想，便是充分利用特定模式本身所包含的信息，通过对特定模式的预处理而得出一个前缀函数，从而能够在对文本的匹配搜索中避免一般搜索所花费的无用功。

首先，让我们来看一下什么是前缀函数。

一个字符串的前缀相信不难理解，比如“abc”的前缀可以是“a”也可以是“ab”。在这里，前缀都指的是严格意义上的前缀，比如在刚刚的例子中，“abc”就不是字符串“abc”的前缀。

KMP的前缀函数则是包含有模式与其自身的位移进行匹配的信息的函数。通过前缀函数的生成，我们可以获得特定模式中以每一位字符所引领的前缀匹配原来特定模式的位移，并且通过这个位移，我们可以充分利用特定模式中先前已经与文本比较过的前缀所包含的信息，从而能快速准确地递归得出下一个最大匹配字符数。

以上的描述可以通过以下这个简单的例子来说明：

假设我们的特定模式为“abcabcde”，可以看出，若此模式在搜索匹配时，已经有“abcabc”与文本中的信息匹配上了，却在其后一位不匹配，此时，我们可以充分利用其本身所包含的信息，即“abc”这一前缀可以匹配“abcabc”的后三位，因此，我们可以立即将原模式“abcabcde”在此时文本中进行匹配的位置向文本结尾处移三位，从而以“abc”已经匹配的事实继续检验下一位是否匹配，因为事实上在搜索中文本的下一位是不确定的，所以以“abc”作为新的已经匹配的字符串是完全合理的。

由于在KMP算法中前缀的定义为严格前缀，因此，最终能够递归地完成匹配任务。

由上述描述，可以对KMP前缀函数进行更深入的研究。

现在假设有一特定模式P，且有一文本T，P有q个字符，可以用P[1，2，3…q]来表示。现在，已知P[1，2，…，y]与T[g+1，g+2，g+3，…，g+y]匹配（y < q），即P[1，2，…，y] = T[g+1，g+2，g+3，…，g+y]，那么满足P[1，2，…，x] = T[g`+1，g`+2，…，g`+x]的最小位移g`>g是多少？这里位移g+y = g`+x。此处的位移g`是大于g的未必非法的文本中的第一个位移，因为由于前缀匹配的关系，我们可以立马排除g+1，g+2，…，g`位，这些位会造成原匹配的下一位不匹配，而对于g`+1以后的位，我们则可以完全放心。

于是，从特定模式的角度来说，可以利用模式与其自身进行比较，以预先计算出需要的信息。由此，现在可以来正式的介绍前缀函数。还是以特定模式“abcabcde”来说明，假设前缀函数为h（i），i为第几个字符的位置，h（i）代表了第i位匹配而第i+1位不匹配时最大的匹配其本身的前缀字符数。例如，在“abcabcde”中，若已经匹配了“abcabc”，其后一位不匹配，可以看出，“abc”是匹配“abcabc”的最长的前缀，因此可以直接将模式向后移三位，即h（6） = 3，同时，可知h（1） = 0，因为光是一个“a”字符匹配并且下一位不匹配并不能说明什么，没有严格上的前缀子字符串可以使用，只能继续用“a”来与文本的下一个字符进行比较看是否匹配，同理，光是“ab”或者“abc”匹配也无法得到什么，因为当下一位不匹配时这两个字符串都得完全从“a”开始重新匹配，因此，h（1） = h（2） = h（3） = 0。在上个例子中，h（i）的全部数值如下：h（1） = h（2） = h（3） = 0，h（4） = 1，h（5） = 2，h（6） = 3，h（7） = 0。

KMP的前缀函数是整个KMP字符匹配算法的核心，当通过对特定模式的分析而得出前缀函数后，一切就手到擒来了，剩下的只是将特定模式与文本进行比较并使用这个前缀函数。

在与文本匹配时，一开始就像一般的比较字符一样，看开头是否相等，然后比较下一位，若最终整个模式，都被匹配，那则是很幸运的取得了开门红，可以继续比较文本的下一个词；倘若不是整个字符串都能匹配的上，那便可以利用前缀函数所透露的信息，将模式向后移动，直到移到最长的前缀被匹配，然后在比较下一位，相同则继续比较，否则再看前缀函数，再移动直到最长的前缀被匹配。

以上便是KMP字符匹配算法的所有步骤。

KMP这一算法经过无数能人志士的推导和检验，早已证明其是一个高效且易实现的算法，正如前文所述，其所用时间花销在m+n这一数量级上，是各种同类算法中耗时最少的。

下面，作者根据对KMP算法的分析，使用C语言对算法进行了实现。

2 KMP算法实现

根据上文的分析，作者首先写出了KMP算法的伪代码，其中，前缀函数为next（），P为特定模式，T为要匹配的文本，如下所示：

计算前缀函数：

以上便是KMP匹配算法的伪代码，其中，伪代码分为两部分，第一步首先先对特定模式进行分析，生成需要的前缀函数next（），然后第二步再使用生成的前缀函数来配合特定模式与文本进行匹配。

根据如上的分析，作者首先实现了生成前缀函数的C语言源代码：

以上便是使用C语言实现的KMP匹配算法。

可以看到，在程序中，作者首先用getnext（）函数生成得到前缀函数的对应于特定模式每一位的数值，然后在kmp（）函数中再使用特定模式的字符数组m[]和储存前缀函数相应位数值的next[]数组来对文本中的内容进行匹配查找过程，当获得一处匹配时便返回匹配处在文本中的位置，若整个文本没有内容能匹配特定模式，则kmp（）函数最终返回-1。

3 总结

本文探究分析了著名字符串匹配算法——KMP算法。在文中，作者分析了KMP算法的思想和原理，并通过简单的例子进行了演示，最后使用C语言对其进行了实现。

KMP算法可以说是字符串匹配算法中运行速度最快的算法之一，相对于同类别的RK算法和有限自动机算法，其速度有可观的提高，并且，KMP算法中充分利用已知信息的思想，也启发着日后算法的发展，相信在不久的将来，会有更高效的算法出现！

参考文献：

[1] Mark Allen Weiss.数据结构与算法分析[M].人民邮电出版社，2005.

[2] George F.Luger.Artificial intelligence.China Machine Press，2010.

[3] Robert Sedgewick算法.C语言实现[M].机械工业出版社，2009.

第7篇：匹配算法论文范文

关键词：后缀数组分布式存储串匹配

1引言

键，在分布式环境下加速后缀数组的构造需要充分考虑到通信对算法性能的影响。串匹配问题是计算机科学中研究得最广泛的问题之一，在文字编辑与处理、图像处理、信息检索、分子生物学等领域都有很广泛的应用。本文解决的是分布式存储环境下的精确串匹配问题。在串匹配的许多实际应用中一个确定的文本常常被查询很多次(比如对非常长的基因序列的查询)。针对这种情况，manber.u和e.w.myers提出建立后缀数组(suffixarrays)〔1〕来提高查询的性能，而后缀数组最大的不足是它的构造时间过长。因此一直以来，如何快速有效地构造后缀数组成了提高基于后缀数组的串匹配算法性能的关

2usaa算法

假设n，m为文本串和模式串的长度，p为处理器数，算法设计思路如下:

(1)将长为n的文本串a均匀划分成互不重盛的p段，分布于处理器。~(p一l)中，且使相邻的文本段分布在相邻的处理器中，显然每个处理器中局部文本段的长度为〔n/p〕。

(2)除了处理器o外，其它每个处理器利用kmp算法计算分配到自己的文本串的头个字符与模式串，基金项目:国家自然科学基金重点项目(60533020) 的匹配信息。如果存在匹配情况，就向相邻的前一个处理器发送最大匹配后缀长度maxsuffixlen，否则就发送一个负数。每个处理器可独立地计算和发送该值，所以这一步的计算复杂度为o(m)，通信复杂度为o(1)。

(3)处理器1~(p-l)接收前一个处理器的信息。

(4)利用manber.u和e.w.myers在文献〔〔1〕中的算法各处理器并行地构造局部文本段的后缀数组。

(5)利用manber.u和e.w.myers在文献〔1〕中的算法各处理器并行地进行模式申的匹配。算法的计算复杂度为o((n/p(109109(n/p)))，通信复杂度为0(1)，大大降低了通信复杂度。

3实验结果及分析

我们在基于分布存储的32节点hprx2600高性能机群系统上测试了上述算法，比较了usaa和目前理论值最好的mmsortlz〕算法之间的性能，其计算复杂度为，通信复杂度为。

图1给出了当m一16、p~2时，n的取值对算法执行时间的影响。从图中看出当时，由于n、p的取值成了影响算法复杂度的主项，因此在实际应用中usaa算法比mmsort算法表现要好。

图2给出了当n变大时，usaa算法和mmsort算法的通信时间比较。可以看出，随着文本串的规模变大，由于处理器间需要进行的通信量增加，mmsort算法的通信时间有明显的上升，而usaa算法的上升幅度要显著小于mmsort。

4结论

本文提出的usaa算法通过采取均匀的后缀分配方式来降低处理段间匹配时的通信消耗，在(n/p)m的情况下使算法在保持计算复杂度的同时大大降低了通信复杂度。通过实验结果可以看到，usaa算法很好地解决了在分布式存储环境下降低后级数组构造中的通信复杂度的问题。

参考文献

[1]u.manber，g.myers.suffixarrays:anewmethodforon-linestringsearehes[c〕.inproeeedingsofthe

第8篇：匹配算法论文范文

关键词：中文全文索引；中文分词；Lucene

中图分类号：TP391文献标识码：A文章编号：1009-3044(2012) 03-0722-05

Chinese Full-text Index for the Chinese Word Segmentation Strategy

XI Chao-qiong

(Guangdong Food and Drug School, Guangzhou 510663, China)

Abstract: Chinese Segmentation is the basic step of Chinese information processing. It plays an important role especially in the Chinese full text indexing. This paper first makes comparison between algorithms of Chinese segmentation, and then chooses the most suitable one, which is based on the statistical model of word frequency, to apply to the open source full text indexing project Lucene. By comparison with the traditional Chinese segmentation method, we find that the new full text indexing, which applied new Chinese segmentation meth? od, not only saves huge amount of space of indexing, but also improves the quality of searching significantly.

Key words: Chinese Full Text Indexing; Chinese segmentation; Lucene

1概述

相对于以字母为基本语言单位的拉丁语系而言，东亚语言（以中、日、韩CJK语言为代表）是以具有独立意义的单字作为最小的语言组织单位。两种语系都以最小语言组织单位通过相互排列和组合不断产生新的单词。但是东亚语言最大的特点，就是单词与单词之间没有明显分隔标记[1]。试想假如英文文本把所有单词之间的空格都去掉，然后让计算机进行信息化处理，那么这一过程的首要一步就是把连续的单词串进行切分识别。同样对于天然没有明显标记作为词的分界的东亚语言来说，在对其进行信息化处理时，分词成为首要而且必不可少的步骤[2]。

以汉语为例，中文分词具有广阔的应用前景。在文本校对、汉字的简体/繁体转换、自然语言理解、文本分类和机器翻译等中文信息处理系统都以分词作为其最基本的模块。本论文排版所使用MS WORD所提供的文本自动校对功能、简繁体转换功能和自动取词功能等，便是以分词作为系统的一个基本模块[3]。校对系统运用分词模块对文本进行分词，然后运用词语之间搭配的合理性来识别可能的错误；简繁体转换功能，不但从字一级把如“学习”转成“”，而且还进行相应的习惯用词变换，如“硬件”转成“硬”，而后一级的用词转换是离不开分词模块；自动取词功能，让用户左键双击中文汉字时，其所组成的中文词语则被高亮选中，用户可以对选中的词语作进一步的编辑。这一功能同样是运用分词系统来实现的。

2中文分词算法

正如引言所述，传统上的中文分词算法分为三类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。

第一类，基于字符串匹配的分词方法。

这种方法的原理，是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）[1]。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大匹配和最小匹配。一般来说，由于中文单字成词的特点，最大匹配的效果远远高于最小匹配。据统计分析，逆向匹配的正确率高于正向匹配[5]。

这种机械的划分的优点，就是实现简单。前期工作只要具备一个充分大的词条条目的机器词典；后期工作就是选择一个兼顾效率与准确率的分词策略――逆向最大匹配。当然，它的缺点也是显然易见的，对于歧义问题不能很好地处理。中文分词所遇见的歧义问题主要分为两大类[5]：（1）交集型歧义字段，据统计，这种歧义字段占全部歧义字段的85%以上[6]。所以这也是分词系统所要重点解决的问题。在字段ABC中，这里，A,B,C分别代表有一个或多个汉字组成的字串。A,AB,BC,C分别都是词表中的词，则称该字段为交集型歧义字段。如：“研究生#命起源”，“研究#生命起源”两种切分结果。（2）组合型歧义在字段ABC中，A,B,AB分别 都是词表中的词，则称该字段为交集型歧义字段。如“：学生#会#参加#献血”，“学生会#参加#献血”。

无论哪一种歧义，由于基于字符串匹配的分词没有利用上下文语境，只单纯从词的匹配角度进行机械的划分，因此其处理歧义的能力是相当弱，总体来说他的准确率在三大类中是较低的一种。

第二类，基于理解的分词方法。

从常识角度看，理解上下文的语义是分词正确且有效的途径。基于理解的分词方法其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。然而正如前文所言，理解与分词有时是互为前提的，没有正确的分词难有正确的理解，没有正确的理解也不可能有正确的分词。这便陷入先有鸡还是先有蛋的逻辑矛盾[6]。

在当今自然语言处理(Natural Language Processing)还有待发展的今天，这种分词方法还处于理论研究阶段，离真正实用还有一段好长的距离。

第三类，基于统计的分词方法。

基于字符串匹配的分词方法没有很好地利用句子中上下文所提供的语言背景知识。而基于理解的分词的立足点是要充分利用语义信息，但实现却相当困难。在这两者之间，人们找到一个平衡点―从统计角度处理语言背景所提供知识。

基于统计的分词方法，所统计的对象是多元的。最常见的是基于字与字之间的结合频率[7]来决定是否成词。这种方法的原理是在上下文中，如果相邻的字之间出现次数越多，那么它们是单词的概率就越高。用形式化的语言来描述是：

设字串C={C1 C2 C3 C4 C5 }，

假定划分成为两个词（即两个字串切分）S1={C1C2}，S2={C3C4C5}

定义Prob(C)、Prob(S1)和Prob(S2)，分别为C、S1和S2出现的概率。

则两切分之间的相互信息（Mutual Information）

假定两个不同的阈值γ1

基于统计的分词的好处就是事先不需要大词条的词典，只需对字、词的频率进行统计。比起第一类的算法，它能有效地识别歧义和未登录词。但它也有局限性，首先算法的执行比第一类的算法需要相当大的运算量，其次对于常用的高频非词组性的习惯用语不能正确切分，如“我的”、“之类”等。

事实上，在实际应用的分词系统上，并不是单纯采用某类的算法，而是扬长避短综合地运用。下文所使用的基于词频统计的匹配分词算法，便是将第一与三类算法作综合，在执行效率与歧义处理之间取得较好的平衡点。

3基于词频统计的匹配中文分词

在进行全文索引时，利用中文分词技术，把中文文本切分成一个个长度较小的中文序列，接着把分词产生的中文序列及其位置等相关信息，生成倒排索引表(Inverted Index Table)[8]。倒排索引表的逻辑结构就像每一本书后的索引表一样，以关键词（即分词产生的中文序列）为索引表的关键字，页码（即中文序列的相关信息）为其查找内容。在进行查找时，同样要利用中文分词技术分析用户输入的内容，然后按照分析结果直接在倒排索引表查找相关内容。不论是前期的索引工作抑或是后期的搜索工作，中文分词的作用都是举足轻重的。尤其是前期索引的分词的好坏，直接影响后期搜索的准确率和召回率的高低。

无论是一元切分还是二元切分，它们都没有有效利用文本中的语义信息。单纯的机械切分虽然带来100%的召回率，但对于海量的信息，用户所关注的不是返回的检索的多寡，而是检索的质量。尤其是应用于互联网的搜索引擎，一个关键字至少可以带来几十万的查询结果，这时检索的准确率将优先于召回率作为首要考虑因素。而要提高检索的准确率，必然要引入此前所讲三大类的传统分词算法。

接下来的部分，我们将引入现今一个较成功的分词算法基于词频统计的匹配分词到全文索引项目Lucene中。前半部分将详述分词的原理，后半部分将描述移值至Lucene的相关细节。

3.1基于词频统计的匹配分词原理

利用已有的词典对字串进行完全匹配的粗分，生成含有所有可能的切分方案，然后构造一个反映所有切分方案的有向无环图。最后通过Dijkstra的最短路径算法求出概率最大的切分方案。

3.2模型求解步骤

模型定义：

字串C={C1 C2 C3…Cn}，Ci为字串的第i个单字，字串C长度为n，n>=1。模型目标：

生成切分可能性最大的分词串S={S1 S2 S3…Sm }，其中Si为分词串第i个词。模型求解步骤：

1）粗分字串，产生所有可能的分词串方案，并构造相应的有向无环图

首先构造初步的有向无环图G ，其中该图的结点个数| V | = n+1。每一个结点Vi代表字串中的单字Ci（i

图1

接着，对图中的Vi（1

图2

2）利用Dijkstra的最短路径算法，选择最优划分

用数学语言精确地描述我们的模型目标，对于字串C={C1 C2 C3…Cn}，切分成分词串S={S1 S2 S3…Sm }，使到条件概率Prob ( S | C )达到最大值。

其中Prob ( S | C )=Prob ( S，C )÷Prob( C ) = Prob ( S )×Prob ( C | S )÷Prob( C )

我们知道，Prob ( C )是一个定值；而对于某一个分词串S，其对应的字串C是一定的，所以Prob ( C | S )恒为1。因此，要使Prob ( S | C )取得最大值，必先令Prob ( S )达最大值。假定对于分词串S，Si与Si+1 ( 1

则Prob(S)=Prob(S1,S2,S3...Sm)=∏

按照如下规则给有向无环图的边赋于权值：

（1）若Si为数字串或英文串，赋权值0至边。

（2）若Si为汉字串（串长为n），赋权值-logki+100至边。（加100的目的是使权值为非负）最后，利用Dijkstra的最短路径算法求最优划分方案。

4基于词频统计匹配分词策略应用于全文索引项目Lucene

4.1 Lucene简介

Lucene是一个开放源代码的Java全文索引引擎工具包。比起商业的笨重和昂贵的全文索引工具，它可以按照需要进行扩展和剪裁，方便的嵌入到各种应用中实现针对应用的全文索引/检索功能。Lucene起初是由著名搜索引擎Excite的架构师Doug Cutting在SourceForge作为开源项目。到2002年，Lucene 1.2版正式作为Apache Software Foundation的子项目。

由于Lucene的卓越的架构所带来良好的扩展性，吸引了开源社区对其不断功能扩展，尤其是分词部分，迄今已经从原来单纯的英语切分，扩展到俄、德等多种语言。随着其功能续步完善，Lucene有越来越多应用案例。比如，Web论坛系统Jive的检索部分和开放开发平台Eclipse的帮助索引部分都嵌入Lucene作为其后台的全文索引。

4.2中文分词实现

本次实现所使用的带词频的词典来自于中科院的ICTCLAS分词系统[2]，其格式说明参考至网上“计算所汉语词法分析系统ICT? CLAS字典格式解析（字典格式说明）”[10]，特次致谢。

由于Lucene各模块之间的关系是松耦合，因此对其扩展改动所涉及的面相当少。本次加入中文分词实现只涉及Lucene的org. apache.lucene.analysis中与分析相关的package。

实现架构规划，如图3。

1）com.rickyzhang.lucene.省略

功能说明：包含一元切分、二元切分和基于词频统计匹配切分的Analyzer和Tokenzier实现。主要类图说明图4。

图4

说明：AbstractChineseAnalyzer所含的Chinese_STOP_WORDS包含高频的汉语虚词，如“但是”“因为”等，其目的是过滤(Filter)这些高频词条。

2）com.rickyzhang.lucene.util

功能说明：包含求最短路径的有向无环图的类SegmentGraph，词典类Dictionary，对文本进行初次切分Token的SimpleTokenizer和对外最终接口SentenceSegment。

图5

3）com.rickyzhang.lucene.test

功能说明：包含测试中使用的索引工具Indexer和检索工具Searcher。

5与二元切分和一元切分作比较

本次评测内容分为索引和检索两部分。所索引的对象内容范围广泛，包括：现代小说，人物传记，学术论文，哲学简史和文言文经典。此次共索引49个文件，总大小为6.12MB。5.1索引评测

对比数据如表1：

说明：测试机器AMD Duron 1.6GHz，内存512MB

1）从索引速度看，基于词频统计匹配切分比一元切分和二元切分差一个数量级。

其原因可以从算法复杂度中推出，一元切分和二元切分的计算复杂度是O(N)，而基于词频统计匹配切分是O( N2)（主要是在计算最短路径上Dijkstra算法上）

2）从索引所占空间看，二元切分所占的空间约为一元切分和基于词频统计匹配切分的两倍。

正如此前分析，由于二元切分所分出来的词条是以物理位置作为划分界限，比起基于词频统计匹配切分所分出的具语义的单词，它们重复的几率相对较低，故二元切分占索引空间相当大。而一元切分之所以是最省空间的，其原因就是常用高频汉字大概只有三千个左右，因此在所有切分中，其倒排索引表所含的表项是最少。

5.2检索评测

传统上检索评测分为三部分：召回率、准确率和检索时间。

召回率是指检索出的相关内容和索引中所有的相关内容的比率。

准确率是检索出的相关内容和检索出的内容的比率。

定义所述的“相关内容”是一个相对概念，这与检索者的主观意向有密切的关联。

然而对于何一个检索系统来讲，召回率和准确率是不可能两全其美：召回率高时，准确率低；反之，准确率高时，召回率低。

本次，评测以抽查的方式列举了10个不同的关键字作为检索对象，分别用三种不同的切分方法所生成的索引进行检索。（由于Lucene检索时使用的是相同算法，而且关键字长度较短，用不同切分方法对关键字进行分析所花费时间可忽略，故检索时间不作为评测部分。）对比数据如表2：

表2检索评测对比数据说明：测试机器AMD Duron 1.6GHz，内存512MB

1）以语义作为切分的检索的准确率高

很明显“理解越深，越准确”，单纯的机械切分严重割裂了文本的语义。比如，以“华人”作为关键字，一元切分和二元切分都把含有“中华人民共和国”的文本作为检索结果。

2）切分的准确性真接影响召回率

由于基于词频统计匹配切分对于未登录词的切分相对较弱，因此对于某些地名、人名等专有名词的检索效果远差于一元和二元切分。这是造成基于词频统计匹配切分的召回率低于机械切分的主要原因。

6结论

中文分词技术对全文索引起着举足轻重的影响。不论是前期索引的时空效率，抑或是后期检索的质量，都与中文分词工作有密不可分的关系。通过本次探索，应用基于词频统计匹配切分的全文索引的质量明显优于应用传统的一元和二元切分技术的全文索引。前者不但节省索引空间，而且带来更高的检索质量。

然而基于词频统计匹配切分还有提高的空间。鉴于大部分的检索关键字为专有名词，而基于词频统计匹配切分的全文索引在这方面略差于传统的机械切分，因此在后续工作有必要对专有名词如人名、地名等进行专门优化切分，以此提高其检索的召回率。

参考文献：

[1]孙宾.现代汉语文本的词语切分技术[Z].北京大学计算语言学研究所.

[2]计算所汉语词法分析系统ICTCLAS[DB/OL].mtgroup.ict.省略/~zhp/ICTCLAS/.中国科学院计算研究所.

[3]张华平,刘群.基于N-最短路径方法的中文词语粗分模型[Z].中国科学院计算技术研究所软件实验室.

[4]李东,张湘辉.汉语分词在中文软件中的广泛应用[Z].微软中国研究开发中心.

[5]梁南元.书面汉语自动分词系统-CDWS[J].中文信息学报,1987(2).

第9篇：匹配算法论文范文

关键词：图像匹配；序贯相似性检测算法（SSDA）；小波分解；水下导航

Abstract: the article introduces the image matching and the basic theory of wavelet transform is proposed based on wavelet multiresolution analysis of sequential similarity of fast image matching algorithm testing and the application of the underwater navigation. The experiment shows that the algorithm in computing time and precision than the traditional template method has greatly improved. Apply to the realization of the real-time underwater navigation.

Keywords: image matching; Sequential similarity detection algorithm (SSDA); Wavelet decomposition; Underwater navigation

中图分类号： TN957.52 文献标识码：A 文章编号：

引言

图像匹配技术是一个跨学科的领域，它涉及到了计算机视觉、计算机图形学和图像处理等多个领域的知识，是图像信息处理领域中极为重要的一项技术，被广泛应用于图像识别、图像分析和计算机视觉等许多领域。图像匹配一般分为基于灰度相关的方法和基于特征的匹配方法两类。目前，基于特征的匹配方法难以从自然环境中自动、稳定、一致地提取高质量的图像特征，因而不易硬件实现。本文采用基于灰度的匹配方法，结合小波多尺度分析对海底地貌图像匹配及其水下导航应用进行了研究。

1.传统模板匹配算法

设参考图S为大小为M M的图像，实时图T是大小为N N的图像，且M>N。图像匹配是将实时图T叠放在参考图S上平移，模板覆盖下的那块大小为N N的搜索图叫做子图 ，（u,v）为这块子图的左上角像点在S图中的坐标，称为参考点，（u,v）取值范围为：

1 u, v

传统的匹配方法有：

（1） 平均绝对差算法（MAD）

（2） 平均平方差算法（MSD）

（3） 归一化相关算法（NCC）

式中： 和 分别是实时图T和图像 的均值：

传统的模板匹配算法的基本搜索策略是遍历性的，为了找到最优匹配点，传统方法均必须在搜索区域内的每一个像素点上进行区域相关匹配计算，图像相关匹配的数据量和计算量很大，匹配速度较慢。

2.序贯相似性检测算法（SSDA）

巴尼娅和希尔弗曼在1972年最先突出了序贯相似性检测算法（SSDA）。大大提高了匹配的速度。SSDA算法的要点如下：

1） 定义绝对误差为：

(1)

2)取不变阈值 。

3）在子图 中随即选取像素点，计算它同T中对应点的误差值 ，然后把这差值同其他点对的差值累加起来，当累加r次直到超过 ，就停止累加，并记下次数r，定义SSDA的检测曲面为：

(2)

4)计算所有点的r值，并把r值最大的点定为匹配点。

从上述固定阈值 的SSDA算法可以看出，模板要在每个子图 上运算很多次数（累加随机像素点的 直至超过固定阈值 ），在非匹配点做了很多无谓的计算，其计算量还是很大的。本文对上述固定阈值算法进行改进，采用了一种自适应阈值SSDA算法，对阈值进行自适应更新，从而减少运算量。算法要点如下：

(1) 在参考图像最开始左上角的位置计算所有像点的 ，并将其累加之后作为初始阈值 。

(2) 将模板图像移至下一位置，并计算其与对应子图的所有像点的 并累加，将累加值记为 。

（3）在上步累加的过程中不断比较 与 的大小。本文采用每计算完一行像素的 的累加就比较其大小。如果 时，则停止累加；如果 ，则用 更新 ，并记录此时的坐标点（u,v）,即下式所示

（4）最后将模板移至下一位置重复第（2）操作，搜索完成后可得到最佳匹配点位置。

该算法减少了很多非匹配点的运算，SSDA算法效率得到了很大的提高。

3.图像小波分解

小波分析具有将不同频段图像信息分离为高频和低频的能力，其中低频保留了原始信息的基本特征，且图像匹配中的特征点基本均包含在该低频信息中[5,6]。对于二维图像f(x, y)和小波函数 ，其中f， ∈L2（R2），图像的小波变换为：

(3)

Mallat在1989年提出了著名的快速小波分解算法（FWT），FWT将小波变化的计算问题转化为小波变换后的系数计算问题，即给出M+1尺度上的离散采样值{fM+1(m, n)}数据，并计算M尺度层上的小波变换系数。设H={hn}，G={Gn}分别为分解时的小波低通和高通滤波器，则张量积小波计算分解系数的过程为：

(4)

LL：LH：

HL：HH： （5）

其中，sM+1m,n为M+1尺度层时的小波系数，也是原始图像数据；而sMm,n是M尺度层的图像数据，是M+1层的图像数据sM+1m,n进行分解后的低频分量数据（LL）；Mm,n为sM+1m,n进行小波分解后在 方向上的低频部分和在 方向上的高频细节部分（LH）；Mm,n为sMm,n进行小波分解后在 方向的低频部分和在 方向上的高频部分（HL）；Mm,n为sM+1m,n进行小波分解后在 方向上的高频部分和在 方向上的高频部分（HH）。

下面给出本文基于小波分解的自适应阈值SSDA快速匹配算法。

1） 首先对原图像与模板图像进行小波分解，假设分解层数为L层；

2） 在L层上，将原图像与模板图像的低频部分用SSDA算法进行匹配，找到一个最大的匹配点（i,j）。

3） 根据分解后的像素对应关系，找出L-1层上对应于L层上最大匹配点（2i,2j）的像素点。为了确保匹配的精度，可以设定一个阈值，把与像素点(2i,2j)的距离在所设定阈值范围内的像素点并入候选点集。

4） 在L-1层的候选点集范围内进行匹配，找出最大匹配点。

5） 重复 2、3、4步骤直到最上层。

4.实验结果及分析

在MATLAB 7.0平台上对上述算法进行了编程实现。硬件环境为：CPU1.6GHz,512内存。

原始图像（声呐图像） 模板图像匹配结果

原始图像（声呐图像） 模板图像 匹配结果

为了验证算法的匹配速度，采用不同大小的原始声呐图像和模板图像进行仿真实验。并与传统的模板匹配方法进行比较，并取得了良好的效果。各种算法匹配效果如下表1。

表1 各算法匹配速度结果

上述实验结果与理论分析相一致，该方法节省了大量运算时间，极大加快了图像匹配的速度，尤其对于模板图像较大的模板匹配情况，本算法更能提高匹配速度。

5.基于小波多尺度分析的SSDA算法在水下导航中的应用

水下地貌获取主要通过侧扫声纳或多波束扫侧来完成，一次可以获取一个条带的海床地貌图像，若将之应用于匹配导航，相对点序列匹配，增加了匹配的信息量，提高了匹配导航的精度和可靠性。为此，下面研究并给出一种基于海床特征地貌的水下匹配导航定位算法，以期在特征海床区，获得较高的匹配导航精度，实现对现有水下自主导航方法的补充。为缩小搜索范围，提高匹配速度，可根据INS的工作时间以及漂移速率，估计前期积累误差，并根据该积累误差，在背景场内锁定搜索范围。以锁定的背景图像为参考，借助小波分解结合改进后的SSDA方法，寻找匹配点，实现实测地貌图像与背景地貌图像的匹配。

以North California 州立大学海底绘图实验室实测的Mackerricher State Reserve的声呐海底地貌图像（如图1所示）作为研究对象，在MATLAB 7.0平台上对上述算法进行了编程实现。硬件环境为：CPU1.6GHz,512内存。 该背景图像尺寸为5331像素×3001像素，像素代表的实际尺寸为0.5m×0.5m。根据侧扫声纳测量原理，在该图像上不同位置提取出5个子块，子块大小均为100像素×250像素，各子图及其位置如图1所示。定义INS前期积累误差为5°，初始位置偏差为X方向50像素，Y方向50像素。根据定义的INS前期方位积累误差和初始位置偏差，结合提取子图中心位置计算的每段的方位和距离，模拟推求了INS航迹。

由INS航迹点以及INS积累误差为依据，缩小图像搜索的范围。以此缩小了的搜索范围图像为背景场，以选取的5个子图像作为实测图像，运用小波变换及改进型SSDA相结合的快速匹配算法，实现子图与背景场图像的匹配。

图1 匹配导航示意图

表2仿真实验分析

由表中实验数据表明：该方法大大提高了模板匹配的速度，当匹配图像较大时，更能体现此算法的优越性。同时精度没有丝毫的降低。MAD和NCC分别代表在匹配点用平均绝对差算法和归一化相关算法对匹配图像和参考图像上的匹配子图像的相似性评价结果。由此可以说明本文提出的基于INS与侧扫声呐及超短基线水下组合导航是可行的，该方法降低了搜索匹配时间，有利于实时匹配导航的实现。

参考文献

[1] 张红源，陈自力.图像匹配经典算法及其改进方法研究[J].兵工自动化.2008.27(9):91-94

[2] Barnea DI, Silverman H E. A class of algorithms for digital image registration [J]. IEEE, 1972, C-21(2):179-186

[3] Mallat S G. A theory for multiresolution signal decomposition: The wavelet representation [J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989, 11(7):674-693