匹配算法论文大全11篇

匹配算法论文篇（1）

0  引言

公路货物运输业一直是国民经济发展中的一个基础性和先导性产业。统计公报显示，2017全年货物运输总量479亿吨。公路货物运输总量368亿吨，同比增长10.1%;可见公路运输的占比在所有交通运输方式中是最高的。随着我国货运总量连年提升，公路货运的占比也在不断提高。但目前我国货车实载率不及60%，远低于发达国家 80%～95%的水平。传统线下物流大多数存在着多、小、散、弱等问题，人找车难、车找货难的问题也屡见不鲜。随着中国互联网飞速发展，“互联网+”、大数据、云计算等早已深入货运行业。车货匹配信息平台有效的缓解了信息不对称，减少了车辆空载和社会成本，同时为车货双方提供了货物配载信息服务，但目前还不具备按双方需求实现快速智能匹配的功能。为了解决当前物流需求多样性，服务对象不确定性，车货匹配信息不对称及车货匹配效率低等问题，减少较大的经济损失和社会资源浪费。本文从车货匹配的决策建模，理论方法及信息平台等三个方面，汇总了针对车货匹配的国内外学者观点，并且囊括近些年来相关领域的优化问题，回顾了相关成果的研究热点、模型特征，并提出了未来公路车货匹配研究中应该关注的主要问题。

1  车货匹配决策建模理论研究

车货的有效匹配可以提高物流资源的利用率，降低运输车辆的空驶率。本文主要从车货匹配决策建模方面对前人的研究文献做简要综述。

陈进博等人[1]基于信息、功能及效益三大模块并应用MA-OWA算子进行权重赋值，结合车货匹配网站的业务流程构建了评价指标体系。姚国龙[2]提出结合精益物流思想特征和专家调查法对车货匹配中的具体要素进行评价，采用定性与定量的AHP模糊综合评价法分析过程中的问题。张庆英等人[3]，采用权重分析法对物流企业和个体用户交易指标进行打分，以承运商和托运方估值之和作为车货信息匹配交易的撮合机制。孙彬[4]通过构建智能匹配模型及指标体系实现了基于地域因素的第四方物流平台的供需智能匹配。李慧[5]运用理论分析法，模糊综合评价法和多目标匹配排序法为供需匹配模块建立以货源方、车源方为主的车货两层筛选匹配指标体系。胡觉等人[6]提出了利用信息评价体系，大小数量规模下的TS算法和PSO算法，PSO-TS混合算法等证明了TS算法在车货匹配问题上的有效可行性。郭静妮[7]，利用三角模糊数及清晰化的效用函数构建了车货双方多指标语言评价体系。黄美华[8]等人根据车货信息平台的特点用最小二乘支持向量机来匹配需求信息，并建立了车货信息匹配模型。吴广盛[9]以货源方和车源方为主导偏好因素提出车货供需匹配排序模型，并提出匹配指标和信誉评价体系。牟向伟等[10]提出了利用量子进化算法对车货匹配模型进行设计与改进，并采用约束惩罚的适应度衰减方法解决了量子群初期无强可行解时最优量子个体的选择问题。陈火根[11]等人讨论了在电子交易市场上利用网络服务信息建立了子目标任务，人工干预交易协商，并实现车货匹配资源自动配对。陆慧娟等人[12]利用软件及服务（SaaS）与计算机支持的协同工作（CsCw）相结合，采用车辆混合禁忌搜索算法，构建“货找车”的高智能车货匹配系统。王训斌等人[13]构建了多目标多层级公路车货匹配系统，并采用车辆混合禁忌搜索算法对其进行优化。陆江[14]研究了基于虚拟物流平台的公路零担运输车货匹配模型，选定遗传算法作为模型的求解算法，并使用Java语言实现了算法。张涛和赵冰洁[15]运用遗传算法对车辆调度实际问题进行研究。李建民[16]等人针对车货配载过程中的货选车和混载的问题构建了多目标规划模型，并提出运送价格和车主可靠程度是其重要的影响因素。顾佳倩[17]利用Java程序，以语义网本体和自定义推理规则为知识导向搭建了车货基于语义的相互匹配。张璐[18]通过了解交易双方策略，研究并分析了基于公路货运信息平台的组合拍卖机制对运力资源的订单分配等领域问题。蒋忠中等人[19]分析了多属性商品交易中存在的模糊信息，并建立了的新的交易匹配模式。常连玉，陈海燕[20]基于主体诉求和运价机制，利用神经网络和微粒子群智能算法对运力组织优化模型进行了求解。Karen Renee Smilowitz[21]通過分析研究实例UPS路网对多式联运运输系统网络发表了最新的见解。Lao和Goh[22]用JAZZ技术实现了一个基于智能匹配的网上支持4PL业务的系统。研究成果提出了很多建模决策方法例如 “语义网技术”，禁忌算法，模糊综合评价法，层次分析法，神经网络，微粒子群等。对车货智能匹配功能和车货双方的多指标评价体系也进行了较丰富的研究。

2  车货匹配相关理论方法研究

在合理的市场机制下双方能够基于各自的偏好进行稳定的市场匹配称之为双边匹配理论，以其为基础导向从车货匹配平台与车、货双方关系出发，运用分析方法和建模，能够有效的解决实际问题。所以本文重点探讨双边匹配理论在车货匹配问题上的研究。

国内相关研究成果：贾兴洪等人[23]基于双边市场和演化博弈理论，构建了车货匹配平台双边用户交易博弈模型，提出平台用户单归属比率提升的最优控制。宋娟娟等人[24]提出物流信息平台具有双边服务、交叉网络外部性等特性，并建立配套信用机制对平台用户资质进行认证。赵保燕[25]以双边市场理论为基础构建了车货物流平台并用平衡计分卡模型对模式的各个维度进行评价。李铭洋等人[26]基于车货双方的序值偏好，构建了主体序值和最小的目标函数模型。樊治平等人[27]基于双边匹配稳定满意的出发点，建立了以满意度最大化为目标的双边匹配模型。张振华和汪定伟[28]从权匹配的角度阐述了稳定性匹配问题，提出按重要性从大到小排序，使每一个结点上的匹配主体都尽量得到最优匹配。

国外相关研究成果：Roth[29]最早明确公开提出双边匹配的概念，在1985年发表的文章“Conflict and conflicting interests in two sided matching markets”中界定了“双边匹配”和“双边”的概念，并分析了双边匹配的现实例子。Gale和Shapley[30]于1962年在“American Mathematical Monthly”上“大学录取和稳定婚姻匹配问题”。Rochet等人[31]在其working paper中首先从价格结构的不对称性角度给出了双边市场的定义。Armstrong [32]进一步强调了双边市场中一边用户对另一边用户数量的依赖性。 Gardenfors [33]以指派理论为依据研究了双边匹配问题。Vate[34]在研究中指出最大化线性目标函数的稳定匹配能够通过线性规划计算出来，认为稳定匹配是一个线性规划问题。Fleinr[35]提出可以用不动点理论来解释双边匹配问题并分析了Gale-Shapley的稳定婚姻理论与Tarsk不动点理论的联系。Roth[36]在双边匹配市场的理论基础上创新性的提出了如何识别非空内部点的方法，同时在Shapley和Shubik[37]研究的转让市场的理论核心基础上得出一套固定点。Korkmaz等人[38]提出双边匹配模型是将雇员和雇主进行有效匹配并使每一边都接受匹配结果，还指出双边匹配理论可以用在指派问题中。

双边匹配理论为匹配的稳定性，线性规划都做了开拓性的研究。车货匹配依据双边匹配理论可以分为一对一匹配，一对多匹配，多对多匹配模型。但双边匹配理论针对车货匹配问题的研究尚处于探索阶段，已有的成果还存在不足之处。

3  车货匹配信息平台研究

当下我国公路货运成本居高不下，存在大量物流资源的浪费，而其中很重要的原因就是物流信息不对称。车货匹配信息平台的设计就是为了减少或消除信息不对称，实现车货在最优条件下的匹配。本文主要是从车货匹配信息平台方面进行阐述。

刑鹏[39]针对车货匹配信息平台问题提出加强云计算与配送之间的联系，从而产出云配送模式。熊然[40]分析了部分地区公路货运行业的主要问题，不仅指出了车货匹配信息平台给车货双方和社会带来的正面意义还提出交易安全性和信息真实性的重要性。王博，朱杰[41]分析了代表性行业的物流现状，对物流信息平台与车货匹配信息平台进行对比，强调了资源整合的重要性 。张松[42]针对货运配载行业的发展现状提出了影响公路货运返程配载效率的因素，并比较分析了南京主流的配载模式。汪逸敏[43]从公路货运平台经济的角度出发，指出配货需求不能局限于落地配等单一模式应当趋于随机与碎片化模式。熊宜强[44]提出利用“反馈式竞争法”进行权重改进，研究了车货匹配排序诚信激励机制和信号博弈模型等级划分机制。

匹配算法论文篇（2）

在我国的图像处理技术中，图像的匹配技术不仅仅是其中的重要组成部分，同时还是很多图像技术的发展创新的技术基础。例如图像技术中的立体视觉技术；图像技术中的运动分析技术以及图像技术中的数据融合技术等。通过上述内容可以看出，在我国的图像技术中，图像匹配技术具有非常广泛的应用。随着我国的相关技术不断的创新和发展，对于图像匹配技术的要求也是越来越高。这样就要求我国的图像匹配技术有更深层次的研究和发展。我国现阶段的研究主要是针对图像匹配过程中的匹配算法进行研究，希望借助研究能够更加有效的提升在实际的工作应用中的图像质量，同时也能够在很大程度上提升图像处理的图像分别率。文章的主要陈述点是通过图像匹配技术的具体方法进行优点和缺点的分析，通过分析优点和缺点来论述我国图像处理技术中的图像匹配技术的发展方向以及改进措施。近些年出现了很多的图像匹配方法，针对现阶段的新方法以及新的研究思路我们在实际的应用过程中要有一个非常清醒的选择。文章针对这一问题主要有三个内容的阐述。第一个是图像匹配技术的算法融合；第二个是图像匹配技术中的局部特征算法；最后一个是图像匹配技术中的模型匹配具体算法。

1 现阶段在世界范围内较为经典的图像匹配技术的算法

关于现阶段在世界范围内的较为经典的图像匹配技术的算法的阐述，文章主要从两个方面进行分析。第一个方面是ABS图像匹配算法。第二个方面是归一化相互关图像匹配算法。下面进行详细的论述和分析。

（1）算法一：ABS图像匹配算法。ABS图像匹配算法最主要的原理就是要使用模板的图像以及相应的匹配图像的搜索用窗口之间的转换差别来显示两者之间的关联性。图像匹配的大小在数值上等同于模板图像的窗口滑动顺序。窗口的每一次滑动都会引起模板图像的匹配计算。现阶段ABS的算法主要有三个，如下：

在选择上述三种计算方法的过程中要根据实际情况社情相应的阀值，否则会出现很高的失误率。上述的三种算法使用范围较狭窄。只使用与等待匹配的图像在模板影像的计算。

（2）算法二：归一化相互关图像匹配算法。归一化相互关的图像匹配算法在现阶段是较为经典的算法。通常专业的称法为NC算法。此计算方法主要是采用计算模板以及待匹配模板相互之间的关值来进行匹配程度的计算和认定。具体的定义公式如下：

2 图像技术中的图像匹配的三个主要因素

关于图像技术中的图像匹配的三个主要因素，文章主要从三个方面进行阐述。第一个方面是图像匹配的特征空间。第二个方面是图像匹配的相似性度量。第三个方面是图像匹配的搜索策略。下面进行详细的分析和论述。

（1）因素一：图像匹配的特征空间。图像的特征空间的组成有很多种，主要石油参与匹配的图像的基本要素构成。包括了很多的方面。例如图像的灰度值；图像的轮廓和图像的统计特征等。在图像匹配的过程中，选择合适并且恰当的图像特征非常重要，这样能够有效的提升图像匹配的性能。

（2）因素二：图像匹配的相似性度量。相似性的度量主要指的是匹配图像图形的的确定方式。通常的方式是函数的形式或者是函数的表达方式。较为主要的函数形式是Minkowski函数距离。伴随着科学技术的发展，会有越来越多的函数表达形式被应用和创新。

（3）因素三：图像匹配的搜索策略。搜索策略主要是一种图像匹配的搜索空间的选择方法。通过有效的搜索策略能够将图像匹配的相似性有效的提升。搜索策略主要的方法有分层搜索以及动态规划等。

3 图像技术中图像匹配相关算法的主要分类

图像匹配的算法很多，但基本原则是不变的：有效性，稳定性以及实时性。文章将匹配算法分为基于区域的匹配方法、基于特征的匹配方法、基于模型的匹配和基于变换域的匹配。基于区域的匹配方法又称为基于图像灰度的配准方法，通常直接利用整幅图像的灰度信息，建立两幅图像之间的相似性度量，然后采用某种搜索方法，寻找使相似性度量值最大或最小的变换模型的参数值。基于图像特征的配准方法需要对图像进行预处理，然后提取图像中保持不变的特征，如边缘点、闭区域的中心、线特征、面特征、矩特征等，作为两幅图像配准的参考信息。基于模型的匹配方法在计算机视觉领域中的应用非常广泛，它可以分为刚体形状匹配和变形模板匹配两大类。Kass提出的Snake主动轮廓模型是比较典型的自由式变形模板模型。

4 未来我国图像技术中图像匹配的发展方向

关于未来我国图像技术中图像匹配的发展方向的阐述和分析，文章主要从四个方面进行分析和论述。第一个方面是图像匹配算法融合的内容。第二个方面是图像匹配算法的局部特征主要内容。第三个方面是图像匹配算法关于模型的深入研究。第四个方面是图像匹配技术研究中的色彩图像研究。下面进行详细的分析和论述。

（1）图像匹配算法融合的内容。在图像匹配的众多算法中，每一种算法都有相应的特点和主要的应用范围，这样就需要我们在使用匹配算法过程中能够有效的将算法进行融合以及相互渗透，这样能够有效的克服单一匹配算法的应用局限性，能够在很大的程度上提升图像匹配的适应性。

（2）图像匹配算法的局部特征主要内容。现阶段我国的很多图像匹配算法采用的都是全局的图像特征进行计算，这种算法对于图像质量要求非常高。同时进行图像匹配的图像有时候很难得到完整的图像，这样就会降低图像匹配的准确性。我国在图像匹配的方法上的研究方向还是要在局面的图像特征发展，这样能够更好的提升我国图像特征匹配的准确性。

（3）图像匹配算法关于模型的深入研究。在图像匹配的模型算法创新过程中，能够为我国的边缘图像监测以及图像的切割研究提供另外一种可能性。这种创新方法在现实的使用过程中也展现出了非常好的技术特性。现阶段我国对于这种方法的研究还是处在一种初级阶段，我们应该更加深入的进行研究，最大程度上提升我国图像匹配结算量较大的问题。

（4）图像匹配技术研究中的色彩图像研究

我国现阶段对于色彩图像的匹配的技术基础是图像颜色的特征。通过颜色特征来进行图像特征的匹配，但是对于图像的其他特征还没有很好的匹配计算。这一方面的图像匹配方法还不是很多，这一研究方向也是我国的一种研究重点。

参考文献

[1]章毓晋.图像工程[M].北京：清华大学出版社，2000.

[2]沈振康，孙仲康.数字图像处理及应用[M].北京：国防工业出版社，1983.

匹配算法论文篇（3）

中图分类号： TP301.6

文献标志码：A

0 引言

串匹配是指在文本串中查找模式串的第一次出现或所有出现。串匹配算法在文本检索、语言翻译、数据压缩、搜索引擎等应用中起着关键作用。近年来，在病毒检测、网络入侵检测、网络协议识别、计算生物等领域也都大量应用了串匹配技术。因此，串匹配算法一直是计算机科学领域的研究焦点之一。

根据扫描策略的不同，已有的精确串匹配算法大致可以分为三类：1）自左向右匹配窗口中文本串与模式串的最大前缀，具有线性的最差时间复杂度；2）自右向左匹配窗口中文本串与模式串的最大后缀，具有亚线性的平均时间复杂度；3）自右向左匹配窗口中文本串与模式串的最大子串，也具有亚线性的平均时间复杂度，甚至能达到最优平均时间复杂度。

BM（BoyerMoore）算法[1]是最早的第二类算法。在BM算法的各种变形[2-5]中，Horspool算法、Sunday算法是BM算法的简化；CommentzWalter算法是BM算法在多模式匹配的推广，SetHorspool算法是Horspool算法在多模式匹配的推广；WuManber算法则是SetHorspool算法的一个改进。

BM算法及其各种变形一直被认为是实际应用中最有效的串匹配算法。例如，开源入侵检测系统Snort就是采用BM算法，在监听到的数据中匹配系统的安全规则，根据发现的入侵情况采取相应的安全措施。

BM算法通过两个预先计算好的函数来确定下一个窗口的起始位置，本文中，这两个函数分别记为skip与shift。其中，skip十分简洁且容易计算，在大字母表、小模式串的情形具有很高的效率；然而，shift的计算却远比skip困难得多。1977年，Boyer与Moore在1975年最初定义的基础上，给出了shift的一个改进了的定义，但没有给出构造算法。同年，Knuth等[6]也给出了一个定义并描述了构造算法，但没有详述计算方法，其算法也不完全正确。1980年，Rytter[7]完善了Knuth等的构造算法，但没有给出计算方法的严格的形式证明。因此，Hume等[8]指出shift的构造算法难以理解，Horspool甚至认为shift并不真正实用，这也正是Horspool算法中仅保留并改进了skip而去掉了shift的原因。近年来，对BM算法的各种改进也主要是针对skip的改进[9-11]。

其实，shift保证了BM算法在最坏情况下是线性时间复杂度[6，12-13]，这在小字母表情形（例如基因序列匹配和蛋白质序列匹配）以及模式串与文本串相似度较大的情形[14]是非常重要的。随着串匹配技术应用领域的不断扩大和理论研究的不断深入，研究人员逐渐开始关注串匹配算法应用环境因素及其之间的关系，尤其是模式串与文本串之间的关系；在网络内容安全方面，也开始关注串匹配算法的抗攻击性能。现在看来，仅仅根据传统文本检索的实验结果，并不足以低估shift的作用。所以，建立shift及其构造算法的严格、清晰的形式理论，对于BM算法及其各种变形的研究与改进是十分必要的。

2009年，Yang[15]试图通过一个新的辅助数组suffixLength计算shift并给出了形式证明，但辅助数组suffixLength既不如Knuth所引入的辅助数组直观，而且证明过程也非常冗长复杂。

本文给出了shift及其计算方法的严格、清晰的形式表述和数学证明，并在此基础上给出了shift的一个新的构造算法。

6 结语

本文首先分析了BM算法中函数shift的经典定义，给出了shift及其计算方法的严格、清晰的形式表述和数学证明；在此基础上，给出了shift的一个新的构造算法，证明了其时间复杂度与空间复杂度均为O（m）。

值得注意的是，随着串匹配技术应用领域的不断扩大，基于软件的实现已经不能充分满足对匹配速度日益增长的需求，因此，基于硬件的实现逐渐出现，并成为当前的研究热点。理论分析与计算结果表明，本文给出的shift构造算法比已有的算法更简单，计算复杂度更低，从而更适合硬件实现。

BM算法及其各种变形的平均时间复杂度仍然是一个尚未完全解决的问题。目前的研究结果主要集中在没有shift的Horspool算法，最近的结果有：在文本字符相互独立且同分布的假设下，Mahmoud等[16]证明了Horspool算法的平均时间复杂度是渐进正态的，Smythe[17]应用Markov链理论也得到了这一结果。至于BM算法，shift使得算法分析变得更加复杂，虽然Boyer与Moore证明了是亚线性的，但其概率模型有待商榷。因此，BM类算法的平均时间复杂度有待进一步研究。

参考文献：

[1]BOYER R S， MOORE J S. A fast string searching algorithm [J]. Communications of the ACM， 1977， 20（10）： 762-772.

[2]HORSPOOL R N. Practical fast searching in strings [J]. Software Practice and Experience， 1980， 10（6）： 501-506.

[3]SUNDAY D M. A very fast substring search algorithm [J]. Communications of the ACM， 1990， 33（8）： 132-142.

[4]COMMENTZWALTER B. A string matching algorithm fast on the average [C]// Proceedings of the 6th Colloquium， on Automata， Languages and Programming， LNCS 71. Berlin： SpringerVerlag， 1979： 118-132.

[5]WU S， MANBER U. A fast algorithm for multipattern searching， TR-94-17 [R]. Tucson： University of Arizona， 1994.

[6]KNUTH D E， MORRIS J H， PRATT V R. Fast pattern matching in strings [J]. SIAM Journal of Computing， 1977， 6（2）： 323-350.

[7]RYTTER W. A correct preprocessing algorithm for BoyerMoore string searching [J]. SIAM Journal of Computing， 1980， 9（3）： 509-512.

[8]HUME A， SUNDAY D M. Fast string searching [J]. Software Practice and Experience， 1991， 21（11）： 1221-1248.

[9]张红梅，范明钰.模式匹配BM算法改进[J]. 计算机应用研究，2009， 26（9）： 3249-3252.

[10]

董明明，巩青歌，张琦.入侵检测系统中模式匹配算法的改进[J]. 计算机应用与软件，2011， 28（5）： 272-274.

[11]王浩，张霖.基于坏字符序检测的快速模式匹配算法[J]. 计算机应用与软件，2012， 29（5）： 114-116.

[12]GUIBAS L J， ODLYZKO A M. A new proof of the linearity of the BoyerMoore string searching algorithm [J]. SIAM Journal of Computing， 1980， 9（4）： 672-682.

[13]COLE R. Tight bounds on the complexity of the BoyerMoore algorithm [J]. SIAM Journal of Computing， 1994， 23（5）： 1075-1091.

[14]刘萍，刘燕兵，郭莉，等.串匹配算法中模式串与文本之间关系的研究[J]. 软件学报，2010， 21（7）： 1503-1514.

匹配算法论文篇（4）

 

Rete算法是一个快速的模式匹配算法，它通过形成一个Rete网络进行模式匹配，利用基于规则的系统的两个特征，即时间冗余性（Temporalredundancy）和结构相似性（structural similarity），提高系统模式匹配效率。

一、模式匹配的基本概念

1、可满足规则：一个规则称为可满足的，若规则的每一模式均能在当前工作存储器中找到可匹配的事实，且模式之间的同一变量能取得统一的约束值。形式化地说，规则

if P1,P2,…Pmthen A1,A2,…An

称为可满足的，若存在一个通代σ，使得对每一个模式Pi，在工作存储器中有一个元素Wi满足

Piσ=Wii=1,2,3 …m

这里，σ作用在某个模式的结果称为模式实例，σ作用在整个规则的结果称为规则实例。在专家系统中，可满足的规则称为标志规则。

2、冲突集：由全体规则实例构成的集合称为冲突集，也称上程表。免费论文参考网。

3、模式匹配算法的任务是：给定规则库，根据工作存储器的当前状态，通过与规则模式的匹配，把可满足规则送入冲突集，把不可满足的规则从冲突集中删去。

二、Rete算法的依据和基本思想

Rete算法快速匹配的重要依据是：

1、时间冗余性。免费论文参考网。工作存储器中的内容在推理过程中的变化是缓慢的，即在每个执行周期中，增删的事实只占很小的比例，因此，受工作存储器变化而影响的规则也只占很小的比例。由产生式系统的折射性，只要在每个执行周期中记住哪些事实是已经匹配的，需要考虑的就仅仅是修改的事实对匹配过程的影响。

2、结构相似性。许多规则常常包含类似的模式和模式组。

Rete算法的基本思想是：保存过去匹配过程中留下的全部信息，以空间代价来换取产生式系统的执行效率。

三、Rete匹配网络结构与过程

Rete算法的核心是建立Rete匹配网络结构，其由模式网络和连接网络两部分构成。其中，模式网络记录每一模式各域的测试条件，每一测试条件对应于网络的一个域结点，每一模式的所有域结点依次连起来，构成模式网络的一条匹配链。

Rete网络匹配过程由模式网络上的模式匹配和连接网络上的部分匹配构成。在模式网络的机器内部表示中，我们把共享一个父结点的所有结点表示成一条共享链。同时，把每一模式匹配链中的结点表示成一条下拉链，于是，每一结点由共享链和下拉链指向其后继结点，模式网络就是一棵可以使用典型遍历算法进行测试的二叉树。

四、智能防火墙Rete算法设计

Rete快速匹配算法，函数Rete设计为:取IP地址、端口号各部分折叠、异或运算后，以Rete长度取模。免费论文参考网。算法如下(无关或部分无关称为集合A，相关、包含相等和相等的称为集合B):

1、Addr=sa+da sa:源地址 da:目的地址

2、Port=sp+dp sp:源端口号 dp:目的端口号

int Rete(long addr, int port)

{int addrxor,key；\地址折叠异或

addrxor=(addr&～(～0﹤﹤16))∧((addr﹥﹥16)&～(～0﹤﹤16))；

key=addrxor∧port； \与端口异或

return(key % max)； }\max为Rete表长度

防火墙初始化时，首先从规则集A用该散列函数构造Rete表R为

Void Initialization(RULE-SET A){

FOR(r∈A)DO{ \r为每条规则

idx=Rete(r.addr,r.port)；

R[idx]=&r； \R代表规则集合A

}}

因为Rete表的长度有限，但是如果设计太大会浪费存储空间，也降低了查找速度，所以免不了会出现冲突。解决冲突的方法是:如果两条规则经过散列后落到同一位置，则把这两条规则按照插入顺序组成一个链表结构。主要算法如下:

if(R[Rete(r.addr,r.port)]=NULL)\R为Rete表,r为规则

R[Rete(r.addr,r.port)]=&r；\没有冲突，则插入Rete表

Else{J=R[Rete(r.addr,r.port)]；\冲突解决方法

while (j->next!=NULL) {j=j->next；} \插入链表末尾

j->next=&r;}

数据包匹配流程：当防火墙收到一个数据包以后，用算法Match查找规则集(A和B)。

Match(IP-Packet p) { \p为数据包

Int idx=Rete(p.addr,p.port) ； \首先用Rete算法查找A类规则

IF (R[idx].addr≧p.addr&& R[idx].port=p.port) \找到匹配规则

return R[idx] ；

Else {int idex I =halfquery(p.addr) ； \利用折半查找索引表

J=L[indexl] ； \L代表规则集合B

While(j!=NULL){\顺序匹配找到的规则链

IF (Matchrule(p)) return j； \ Matchrule为规则匹配函数

Else j=j->next；

}}

Return(Norulematch)；

}

参考文献：

[1] 闫丽萍，潘正运. RETE算法的改进与实现.微计算机信息，2006 (36）

[2] 庞伟正，金瑞琪，王成武. 一种规则引擎的实现方法.哈尔滨工程大学学报，2005(03)

匹配算法论文篇（5）

 

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.

匹配算法论文篇（6）

中图分类号：TP242 文献标识码：A 文章编号：1007-9416(2011)12-0059-02

引言

双目视觉是一种通过两幅图像获取物体三维信息的方法，具有通过二维图像认知物体三维立体信息的能力，其关键技术就是要解决两幅图像中对应点的匹配问题［1］。立体匹配一直都是机器视觉领域中的难点和热点，论文根据结合变电站及巡检机器人双目视觉系统的特点，运用匹配辅助区域匹配算法实现立体匹配，获得密集准确的深度图。

1、立体匹配原理

立体匹配基于视差原理，如图1所示。其中基线距B=两摄像机的投影中心连线的距离；摄像机焦距为f。设两摄像机在同一时刻观看空间物体的同一特征点，分别在“左眼”和“右眼”上获取了点的图像，它们的图像像素坐标分别为

采用平行摄像机模型，两摄像机的图像在同一个平面上，并且特征点p的图像坐标y坐标在左右图像平面上相同，

可以得到：

要想根据左右图像对完成立体匹配任务，就把只需计算左右图像对的立体视差，立体视差是景物点在左右图像中图像像素的横坐标之差，即：

从而就可以建立立体视差图(又称深度图)。所建立的立体视差图可以细分为两个子区域，零视差子区域和非零视差子区域，零视差子区域为机器人可以自由行走的无障碍平坦区域；非零视差子区域为平坦区域上的凸出区域，可能是障碍物存在的区域。

根据式(3)及立体视差原理，可以方便地计算世界坐标下的特征点在摄像机坐标系下的三维坐标：

左摄像机像面上的任意一点只要能在右摄像机像面上找到对应的匹配点，就可以确定出该点的三维坐标。这种方法是完全的点对点运算，像面上所有点只要存在相应的匹配点，就可以根据式(5)计算出对应的三维坐标。

2、立体匹配设计

经过图像预处理，可以为立体匹配提供较理想立体图像对，降低了匹配算法的难度。论文结合变电站、检机器人双目视觉系统的特点，运用特征辅助区域匹配算法实现立体匹配，该算法结合特征匹配算法及区域匹配算法的优点，可以在计算量不大的情况下，生成密集准确的立体视差图。

算法的总体上分三步：

2.1 匹配初始化阶段

匹配初始化阶段需要完成以下工作：对双目摄像机参数的标定；对摄像机所采用的图像运用高斯―拉普拉斯模板进行图像预处理；对预处理的图像运用加速主成分分析法实现图像的特征提取；这些过程都是为后面的立体匹配做准备，为之提供较理想的立体图像对。

2.2 特征匹配阶段

根据各种匹配准则缩小匹配点的搜索范围，利用特征匹配算法确定正确的匹配点。

2.3 区域匹配阶段

由于前面特征提取算法限制，不可能把景物所有特征点全部提取到，所以特征点匹配完成后，还存在一些有价值的非特征点未被匹配。但是这些未被匹配点被已匹配点限制在较小的范围内，对这些小范围点的匹配就是区域匹配算法的工作。

对多个可能的候选匹配点比较时，可能使用的依据有灰度、曲率、拉普拉斯变换、梯度等。结合变电站实际环境，运用连续性约束准则和灰度、x方向的灰度梯度、梯度方向唯一确定匹配点［2］。思路如下：

①┍算视觉连续性约束相关系数

其中d为已匹配点的视差均值，d为当前候选匹配点的视差。若，1为预先设定视觉连续性约束相关系数阈值，排除此候选匹配点，重复执行此步直到时，执行第2步；否则直接执行第2步执行。

②计算候选匹配点与待匹配点的灰度相关值Vcorr、x方向的灰度梯度接近程度系数Kgard_r、梯度方向相关系数式(7)-(8)中，K_gard_x、K_gard_y为基准图像上特征点x和y方向的梯度，Rgrad_x、Rgrad_y为候选匹配点x和y方向的梯度，fl、fr为左右图像的灰度函数，、为特征点和候选匹配点在窗口(2N+2M+1)中灰度均、为两点在窗口中灰度标准差。若有Vcorr

③计算总判断依据

计算出所有候选匹配点的Iall值，其Iall值最大者即认为是最佳候选匹配点，即特征点Pleft在右图像中的匹配点。

要匹配固定大小的图像窗口中的像素，相似约束准则是两幅图像在窗口中的相关性度量，当被搜索区域的点与待匹配点间相似约束准则最大化时，认为搜索区域的点是待匹配点的匹配点［3］。

设有立体图像对IMG1、IMGr，Pl、Pr为两幅图像中的像素点，相关窗口大小为，为图像IMGl中像素点Pl在图像3、实验与结果

图2中左右两图像，是左右摄像机对同一景物拍摄所得。

根据上图的左右两图，运用立体匹配算法求得立体视差图。实验结果如图3所示，其中左图像素深度图，右图是对左图经median处理后的效果图，看起来对左图清晰了不少，但不能显示真实图像视差关系。此算法消耗较长时间，将在以后工作中改进。

参考文献

［1］杨俊,贾秀芳.变电站防火防盗图像识别的研究.中国高等学校电力系统及其自动化专业第20届学术年会，2004.7.

［2］林琳.机器人双目视觉定位技术研究［D］．西安电子科技大学硕士学位论文,2009.

匹配算法论文篇（7）

中图分类号：TP399 文献标识码：A文章编号：1009-3044(2011)23-5698-03

NCC Algorithm Optimization Based on the Wavelet Multi Scale

FU Yan-li

(Shandong SHENG DA Construction Group Limited Company, Jining 272000, China)

Abstract: Algorithms based on pixel gray value are already very common in mage template matching problem, which normalized cross correlation algorithm (Normalized CROSS Correlation. NCC) is one of the classic algorithm based on gray matching, and is widely applied, but the algorithm also has the disadvantages of high time complexity. Multi scale theory and the multiple resolution image are representation and analysis of relevant, i.e. a digital image can be expressed as a multiple resolution sub-images collection. Its characteristic cannot be found in a resolution while in the characteristics of another resolution is easy to find, the wavelet multi-scale analysis is an important tool, known as mathematical microscope, can be used to construct different adaptive filter with improved filter convergence, which is also one of the advantages of wavelet transform. Image after wavelet decomposition, in the lowest layer of the low frequency sub image resolution, retaining only the most information of image, that is after wavelet transform of image of a feature. Based on the wavelet multi scale NCC algorithm not only optimize the algorithm itself at the same time optimization based on gray matching search path, so that guarantee the NCC algorithm accuracy, and reduce the matching time, and also the simulation experiments show that this algorithm is effective.

Key words: image matching; normalized cross algorithm; wavelet transform; multi-scale; tower structure

图像匹配是对两幅图像找其对应的映射关系或根据已知模式到另一副图中寻找相应的模式。图像匹配是一种极其重要的图像处理和分析技术，无论在图像理解还是在视觉计算中都具有重要作用和地位，其成功应用到航空航天、地球物理信息、海洋船载导航和地理特征探测、工业生产、医疗卫生等，因此图像匹配技术越来越受到人们的重视和青睐。

图像匹配的实用的技术方法一般分为两大类，即基于灰度匹配和基于特征匹配。基于灰度匹配是把待匹配图像中的某一像素点的灰度邻域作为匹配模板或者称为子窗口，在参考图中搜索具有相同或者相似灰度值分布的对应的邻域，从而实现两副图的匹配。基于特征的图像匹配不是利用图像中的像素值进行匹配，而是通过灰度导出符号特征（如：拐点、角点、边缘线段、图像轮廓）实现图像的匹配。前者作为一种基本的匹配方法之一，在很多地方得到了充分的应用，可以充分利用图像的所有信息、尤其适合在图像仅有平移和模板图像中非零项比较少的情况下，便于匹配的实现。但是弱点也是很明显的，即对图像的几何变形、光照强度、对比度都很敏感，并且计算量大，不适合实时匹配。后者利用从图像得到的符合特征作为匹配的基元，有效的克服了前者的弱点，但是特征匹配过于依赖图像的特征点，并且特征点的提取涉及到几何和图形形态学的计算，没有统一的模型可以利用，需要对不同图像选择不同的自适应特征，需要额外的特征提取的计算，往往计算也比较复杂。

1 归一化交叉相关算法

归一化交叉相关算法[1] (Normalized Cross Correlation．简称NCC)定义如下：

假设模板图像w(s,t)的尺寸为m×n，其中m,n往往取奇数，参考图像f(x,y)是一个大小为M×N，（1≤m≤M, 1≤n≤N），则：

（1）

其中a=(m-1)/2,b=(n-1)/2

由于表示模板的能量所以是一个常量，，当模板移动距离比较小时，也近似一个常量，所以为使D(x,y)最小则需要达到最大值，由于对w(s,t)和f(x,y)的副值的变化比较敏感，所以定义归一化互相关函数为：

（2）

其中a=(m-1)/2,b=(n-1)/2

为了进一步克服噪声的影响和理想状态匹配时C(s,t)相同值太多，还进一步简化（2）式即：

（3）

其中a=(m-1)/2,b=(n-1)/2，Ef,Ew分别为f(x,y)和w(s,t)的期望。

当C(s,t)达到最大值时，两图匹配成功。

通过对NCC算法的理论分析，不难发现：为了让算法达到理想状态进行图像匹配，牺牲时间，换取了理想的匹配。通过对公式（1）（2）（3）分析，可以看出公式越来越复杂，计算量越来越大，匹配的时间越来越多，由于小波变换可以作为一个平滑过滤器来使用，所以小波变换可以消除图像的幅值和图像的噪音，因此选择了NCC算法的中的公式（1），这样就可以节省大量的计算时间，提高匹配的速度。

2 小波变换的多尺度分析

小波在1987年首次作为分析工具首次出现，小波是多尺度分析的重要工具，被誉为数学上的显微镜[3]，因为小波变换具有时间-频率局部化的特点，即在小波变换中，时间窗函数的宽度与频域函数窗口的函数的都是一个常数，根据测不准原理，他们的乘积也是一个常数。在对低频分析是可以加宽时间窗，减少频率窗；而对于高频分析是，可以增高频率窗，减少时间窗，这种特性被称为“自适应窗口特性”所以小波的这种特性是小波变换能提高为多尺度分析的基础，可以用来构建不同的自适应滤波器以改进滤波器的收敛性。

小波多尺度分析的表示：以多分辨率来解释图像的一种有效并且容易理解的结构就是图像金字塔如图1。一副图像金字塔是一系列以金字塔形式排列的分辨率逐层降低的图像集合。0层是N×N的图像，对0层的图像进行小波亚抽样，可以达到一个原图四分之一的较粗略的缩略图。这个过程是可以重复进行直到N层，这时图像是1×1的图像。这时图像的分辨率也从0层最高到N层逐次下降，是原来图像的四分之一。这样一个图像的金字塔结构共（logN 2+1）层，或者有这么多不同的图像组成，并且图像所用的容量只是原来的图像的4/3N2。

多尺度小波的特点[3]：1）多尺度小波具有窗口自适应的特性，即可以使图像的小波分析聚集到间断点、奇异点和边缘，体现了局部特点；同时也可以获得全局的视点。这个特性是小波变换独有的，对非稳定性和快速变换的信号的分析特别有用的。2）小波变换相当于一组多分辨率的带通滤波器。利用这个特性，可以将图像的信号分解为如图1所示的频率子带上，在每个子带可以用小波变换进行处理。3）多尺度小波分解图像的所有子图的和等于原图像的大小，即不增加存储空间。4）分解后的图像，没有信号损失，保证图像的完整性，便于对低频和高频的处理和上层对下层的实时重建。

3 基于小波多尺度的匹配算法

多尺度小波匹配主要利用了小波多尺度的特性对待配图和参考图进行金字塔式分解，结构如图1，匹配基本流程如图2所示，具体步骤如下：

1）首选判断待配图和参考图的大小，一般待配图比参考图像小多，这时就是在参考图中寻找待配图的位置；反之就是在待配图中搜索作为目标的参考图的过程。两者原理是一样的，所以匹配算法是基于前者论述和测试的。

2）判断待配图和参考图的灰度光照强度、对比度、物体在拍摄时的遮挡情况以及空间几何等，这些都会对基于灰度匹配造成错误的匹配，进行图像匹配前的预处理。

3）以上两步看作图像预处理的过程。接下来选择小波，这步非常重要，本课题选择了Daubechies（db4）小波，因为此小波在运动估计中应用非常广泛，可以很好的保留低频中图像的绝大部分信息，去掉高频信号中的噪声，是一个行之有效的小波。然后利用小波的多尺度特性将待配图和参考图像分解为N层，结构如图1，待配图和参考图未分解的图像为0层（有些文献是将原图定义1层），从低到上，分解的最大层为N层（或者分解的最大尺度为N层），在MATLAB中实现小波变换的最大层的函数是wmaxlev()。但是为了保证低频的中含有未解图的绝大部分信息，尤其是灰度变化比较剧烈的区域，一般分解的层次为：一维分解的分解尺度N不超过5；二维的分解尺度N不超过3。第N层图像的尺寸和大小都是原图来1/(N+1)2。

4）通过前三步，待配图和参考图的原图被分为N层不同频率子图的集合，现在可以在分辨率最低的N层进行待配图的子图与参考图的子图进行匹配。采用了经典灰度相似度量算法：归一化交叉相关算法NCC进行对待配图和参考图进行匹配。整个匹配过程就是将N层的待配图看作模板，匹配的实现基本过程：1）在第N层利用归一化交叉相关算法NCC进行匹配，即求出（1）式的最大值；找出对应匹配区域；2）在N-1层按照N层的算法，再在对应匹配区域进行NCC匹配；3）重复第5步直到0层；4）输出匹配结果。

4 仿真实验

本算法使用Matlab2007b进行了大量的仿真实验，图3是选择了最著名lena图进行算法的仿真说明。

结果分析：

1）为了与其他文献在匹配速度和精确度的可比性，选择了其中的一组著名图像：lena图，如图3和图4中的A图所示。进行尺度为2的小波分解，两幅图像中的尺度为2的低频子图，基本上无法辨认，即所需要的信息基本上都被过滤，所以在第2层匹配是无法匹配的，根据第4节的匹配步骤，只能在第1层子图匹配，匹配实验的结果证明是可行的。

2）将这幅lena的待配图和参考图如表1所示的各种算法进行匹配。通过表1可以看出，此算法是可行的。

5 结束语

论文的创新是首选剖析了NCC算法，选择了算法的中间过渡式作为本算法的一部分，好处是减少图像匹配的计算量，同时也保证了匹配的精确度；采用了小波变换的多尺度特性，优化了匹配的搜索策略，提高了匹配的精确度和匹配的时间，所以结合两者的特点可以很好的完成某些领域中图像的实时匹配。

参考文献：

[1] Gongzalez R C,Woods R E.Digital Image Processing[M].2nd Edition (DIP/2e).北京:电子工业出版社,2005.

[2] 李强,张钹.一种基于图像灰度的快速匹配算法[J].软件学报,2006,17(2):216-222.

[3] Luigi Di Stefan.Stefano Mattoccia Fast template matching using bounded panial correlation[J].Machine Vision and Applications,2003(13):213-221.

[4] Bamea D I,Silverman H F.A class of algorithms for fast digital image registration[J].IEEE Trans on Computers,1972,C-21:179-186.

[5] 郑运平,陈传波.一种新的灰度图像表示算法研究[J].计算机学报,2010,33(12):2398-2406.

[6] 李健,梁琨.基于小波多分辨率分析的快速图像匹配[J].陕西科技大学学报,2006,24(6):81-84.

[7] 刘莹.基于灰度相关的图像匹配算法的改进[J].应用光学,2007,28(5):537-540.

[8] 杜杰.两种基于灰度的快速图像匹配算法[D].大连:大连海事大学,2007.

[9] 范俐捷,王岩飞.一种新的基于灰度的图像匹配方法[J].微计算机信息,2007,23(30):296-297.

匹配算法论文篇（8）

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）34-8117-02

入侵检测系统（Intrusion detection system，简称“IDS”）[1]是一种对网络传输进行即时监控，在发现可以传输数据时发出警报或者采取主动反应措施的网络安全设备。

1 入侵检测系统Snort

Snort[2]入侵检测是一个基于Libpcap的轻量级入侵检测系统软件，是从著名的tcpdump软件发展而来的。它是个基于Libpcap包的网络监视软件，是一个十分有效的网络入侵监测系统。Snort入侵检测系统基本由四部分组成：嗅探器，预处理器，检测引擎，日志报警[3]。如图1所示。

其中检测引擎， 是 Snort 的核心部件， 主要功能是规则分析和特征检测。当数据包从预处理器送过来后， 检测引擎依据预先设置的规则检查数据包，使用某种模式匹配算法 一旦发现数据包中的内容和某条规则相匹配， 就通知报警模块。

2 单模式匹配算法研究与改进

为了提高入侵检测系统的准确率，减少误报率，在实际的入侵检测系统中一般大都采用精确的模式串匹配算法。模式匹配问题分为单模式匹配算法和多模式匹配算法[4]。该文主要对单模式匹配算法（BM）进行研究和改进。

2.1 单模式匹配算法（BM）

仅一次在文本串中查找一个模式串出现的过程，称为单模式匹配，相应的算法称为单模式匹配算法。目前比较常见的单模式匹配算法有KMP（Knuth-Morris-Pratt）算法，BM 算法，BMH 算法等。其中， BM 算法由于使用了启发式搜索，采用从右向左的比较方式， 使用好后缀和坏字符来决定模式串移动的距离，通常同时使用两个来加快查找速度。能够在搜索过程中跳过大部分文本，从而使执行效率得到很大的提高，因而在 IDS 中运用最为广泛。

Boyer-Moore算法（简称为BM算法）[5]是一个著名的字符串匹配算法，它把被匹配的字符串模板与匹配字符串自左向右对齐，并从字符串的最后一个字符开始自右向左进行比较。BM算法并不是对每个字符依次进行比较，当出现不匹配的字符时，它使用两步启发式搜索过程来决定字符串向右移动多少个字符继续与文本串进行比较，从而减少比较次数。

其中：n>m，需要从T中查找出与P完全匹配的子串，并返回该子串在正文串的首字母的位置。

BM算法采用从右向左比较 的方法，同时应用到了两种启发式规则，即坏字符规则 和好后缀规则 ，来决定向右跳跃的距离。 BM算法的基本流程： 设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较 。若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则 和好后缀规则 ，来计算模式串向右移动的距离，直到整个匹配过程的结束。

2.2 BM算法改进

尽管BM算法是拥有高效，考虑全面，简便易懂等优点，但是由于其使用了两个数组，预处理时间较大，匹配次数较多，造成许多重复、不必要的比较，还是存在很多需要改进的地方。

通过对BM算法的分析，我们可以发现，原算法虽然是用到了两种启发式规则，即坏字符规则和好后缀规则。但是，在算法的分析中我们看到，当进行字符或者字符串匹配时，大多数匹配都用到的规则是坏字符规则。因此我们可以只用坏字符规则，通过移动量和规定字符这两个方面对BM算法进行一些改进。

根据改进算法的思想，可以对BM算法进行如下改进。由文本串和模式串最后一个位置对应的字符的下一个字符做启发向右滑动。其作用在于在每次匹配失败后，把模式向右滑动的距离变大，减少了模式匹配中一些不必要的和重复的比较，缩短了模式匹配的时间。

首先，对模式串和文本串进行分析，将文本串中文本串与模式串最后一个位置对应的字符的下一个字符（假设为x）与模式串进行匹配。当字符x在模式串中不存在时，那么显然从x开始的m个文本不可能与模式串 匹配成功，所以直接跳过，移动距离为模式串长度+1。当x在模式串中出现，并且x的前一位字符也存在于模式串中。移动模式串使字符对齐，计算偏移量。利用原BM算法进行匹配。当x在模式串中出现，但是x的前一位字符不存在于模式串中，计算移动模式串使字符x对齐时的偏移量和原BM算法中字符不存在模式串中时的偏移量，进行比较，取两者中的偏移量大的进行匹配。

2.3 算法性能比较

分别对BM算法和改进后的BM算法进行性能测试，用同一主程序分别调用BM算法和改进后的BM算法进行匹配测试，匹配算法实验中均插入CPU内部时间戳进行高精度计时，同时统计两种算法在匹配时模式串向右移动的次数。

初始条件：文本串：whiccmnxmxammm 模式串： emam

下图是分别用BM算法和改进后的BM算法对文本串和模式串进行匹配后所得到的数据。

3 结论

本文以目前最著名、最活跃的、基于误用检测的Snort为基础，针对目前应用最广泛的模式匹配算法BM算法的缺陷进行改进。但由于各个方面的局限性，该文研究还有不足和待改进的地方。总之，网络安全是技术问题，也是管理的问题。只有提高使用者的安全意识，合理使用网络及安全工具，才能达到网络的真正安全。

参考文献：

[1] 蒋建春，冯登国.网络入侵检测原理与技术[M].北京：国防工业出版社，2001.

[2] Brian Caswell，Jay Beale C Foster，Jeffrey Posluns.snort2.0入侵检测[M].宋劲松，译.北京：国防出版社，2004.

[3] Jack Koziol.Snort入侵检测实用解决方案[M].吴薄峰，许诚，译.北京：机械工业出版社，2005.

[4] 李晓芳，姚远.入侵检测工具Snort的研究与使用[J].计算机应用与软件，2006，23（3）：123-124.

匹配算法论文篇（9）

1.引言

入侵检测=4，故应继续向右滑动4个字符位置，即从第26个位置开始比较。

④ VIRIS

HERE/HAVE/A/VIRILEUS/VIRIS

此时，M5=“S”，T26=“S”，M5=T26，因为匹配成功，所以继续向左匹配，不难看出，M4=T25，M3=T24，M2=T23，M1=T22。因此可以得出结论，匹配完全成功，匹配开始位置为T22。

(3)匹配成功，比较结束。

上例中，使用Boyer-Moore算法，只需进行10次比较操作。这是BF算法(BF算法应用在本例中要比较31次)匹配速度的三倍以上。Boyer-Moore算法的预处理阶段的时间复杂度是O(j+δ)，δ是与M、T相关的有限字符集的长度。查找阶段的时间复杂性在最坏情况下是O(j·k)，在最好情况下是O(k/j)。在一般情况下，BM算法的时间复杂度比BF算法和KMP算法有很大的提高。

3.新算法的设计与实现

匹配算法论文篇（10）

压缩感知是一种新型的采样方法，通过信号记录每个观测过程中投影的数据，如果感知信号资源小，则可以将这些信号资源进行压缩处理，以保证在观测值数量少的情况下信号结构的准确性和完整性。相对于重构结构复杂的感知信号，信号和图像的重构步骤复杂，且重构效果很差，面对这些不能被正确重构的感知信号，应采用采样的方法将特征量从样本数据中采集出来，通过检测目标信号，完成检测流程。综上所述，通过正交匹配追踪研究压缩感知信号的检测算法，其综合应用性能很好，检测范围和效果很好。

一、感知信号检测

1. 感知信号理论概述

信息获取是压缩感知信号理论的核心内容，其理论基础建立在信号系数、样本数据处于非相关性的状态下的数据测算，通过数据重构和特征量数据采集，以局部分析整体的方式，完成检测流程。压缩感知理论的内容主要包括：①将感知信号的投影在观测向量上，利用重构思想对样本数据进行重构测算，并建立检测集合，如果信号程度为M，则其重构集合稀疏度为K（K

2. 感知信号检测原理

二、基于正交匹配追踪的压缩感知信号检测算法

1.检测算法。正交匹配追踪是一种新型改进算法，其检测方法的理论依据是正交匹配理论，和其他感知信号检测算法相比，正交匹配追踪算法的检测流程更为简单，检测结果的准确度很高。其检测特点是在每次迭代中将选出的列用Gram-Schmidt正交化方法进行正交化处理，将采集到的样本数据选列在空间投影中，通过直观的数据变化曲线，选择精确的检测算法，这种检测方式不仅可以简化检测过程，还能提高样本数据各特征量的收敛速度。在数据迭代次数相同的情况下，空间投影出的采样信息的更新速度很快，检测人员可以通过采样值选出最优投影，并随时更新系数，以确保空间投影的真实性，检测结果的准确度。

2. 实验结果分析。实验结束后，通过检测结果进行分析可知，在每次迭代中，OPM检测算法的感知信号的波形都相对平稳，在一段时间内，其特征量不会随着加性高斯白噪声的变化而变化。当采集样本数据在规定资源数量时，OPM的检测结果和MP的检测结果大体相同，当检测阈值超过3时，OPM的检测结果的准确率明显由于MP检测算法。实验结果表明，与MP检测算法相比，本文提出的OMP检测算法其检测成功率很高，可以在提高检测成功率，所需采样点数、抑制噪声等方面有更好的性能，所以正交匹配追踪压缩感知信号检测算法是一种综合应用性能很好的信号检测方法。

结论：通过上文对正交匹配追踪压缩感知信号检测算法进行系统分析可知，通过匹配追踪定位感知信号，采集特征量，不仅可以方便于检测人员搜集信号样本，还能大大提高检测结果的准确性。通过对每次迭代的特征量进行及时、系统修正，可以延长采集样品的有效时间，以获得更科学、更真实的检测结果。

参 考 文 献

匹配算法论文篇（11）

中图分类号：TP393.08

藏文网络舆情是当前必须关注的舆论涌现与信息传播现象。近几年藏文网络舆情的数量呈现递增的增长趋势，网络信息的传播途径也呈现出多样化和复杂化。由于藏文网络的这些显著的特点，藏文信息处理相对滞后于英文和中文等，短时间内迅速的获取大量信息则不容易。另，目前藏文网站大量的涌现，网页数量巨大，处理起来速度相对慢，以往藏文网络舆情页面的统计都是基于手工统计实现的，效率低，很难对网络舆情的变化做出快速响应。模式匹配技术是内容过滤的核心技术，是计算机信息技术领域研究的基础问题之一，研究敏感词作为模式串的藏文模式匹配算法具有重要的研究意义。

BM算法是Boyer和Moore提出的一种字符串快速匹配算法。其基本思想是从右向左的把模式字符串同文本做比较。开始时仍是P的最左边与T的最左边对齐，当在某一趟比较中出现不匹配时，计算模式串右移的距离，把模式串向右移动该距离，再进行从右至左的匹配，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。

1 BM算法在藏文中的改进

藏文字符匹配中应用BM算法时，必须结合藏文文字特征，对BM算法进行改进以符合藏文的特点，提高匹配效率。

1.1 藏文文字结构及编码特点

藏文是由多个基本字符通过纵向叠加组成的字符串，构成一个完整藏文词素的基本单位是由藏文中的“音节分割符tsheg bar”来确定。一个或多个音节构成一个藏文词。音节，则是由音节分割符（音节点）或者其他藏文标点符号来划分的。一个音节中基字符是不能被省略的，其余相关构件都可以减少掉一个或几个这样仍然可以成一个音节（藏字）。七个构件中辅音字母在各部位依据藏文语法要求都有一定限制并不是所有的辅音字母都能够做前加字或者后加字等。

藏文在计算机中进行编码时一个音节需要用多个编码来表示，长度是不定的，这使得藏文在信息系统中的实现非常的麻烦。

（1）国内的几种藏文处理系统将藏文作为整字给予编码。将藏文垂直组合的部分作为一个处理单元编码（预先进行垂直组合，称为垂直预组合，垂直预组合后的字符称为藏文字丁），比如北大方正的报刊排版系统、华光藏文排版和同元藏文处理系统、激光照排系统等，这几个系统都有各自的编码方案这类编码采用双字节进行编码。这样，具有完整构件组合的藏字（即一个音节最多由4个字丁组成）。因此，国内的这几种编码方式一个音节就最多有4个编码。国家标准的扩A和扩B编码方案采用的是也是整字编码方案。

（2）国外的几种藏文编码方式也是采用整字编码方案，但是将带元音的字丁与元音分离后分别进行了编码。一个藏文音节最多就由5个字丁组成，即一个藏文音节由5个编码组成。

（3）ISO/IEC 10646藏文基本集是国际标准的编码方案，它完全将藏文视做拼音文字，字丁则是通过字母的动态组合实现的。即将一个藏文音节拆分成不同构件的独立的部分，对每一个构件都单独进行编码。采用国际标准后一个藏文音节最多由7个编码组成。基于不同编码的方式使得一个音节的编码个数不同，即使具有相同编码个数的同一种编码方案，由于编码范围不同编码值也将不一致。1997年，我国的藏文基本字符集被收入了国际标准ISO/IEC 10646《信息技术通用多八位编码字符集》。藏文编码标准得到了统一。故本匹配算法以小字符集国际编码标准（ISO/IEC 10646）编码进行讨论。

依据藏文采用小字符集编码中音节字的特点：

（1）具有完整构件的音节具有7个编码且每个编码都是两个字节，则对一个藏文音节字的表示则最多需要14个字节，最少也需要两个字节。匹配过程中只有在一个音节的所有字节都相等的情况下，一个藏文音节才匹配成功。

（2）藏文音节与音节之间由音节点分割，在小字符集中该音节点为0X0F0B。

1.2 基于藏字特征改进的BM算法

改进后的BM模式匹配算法的具体思路：

（1）用模式串P的尾字符与文本串T进行比较，结果失配，且文本串字符不为音节点，则模式串P右移到下一个出现的音节点处在新的位置继续比较。

（2）用模式串P的尾字符与文本串T进行比较，结果匹配，再把模式串第一个字符与文本串T比较，结果匹配。则将模式串与文本串T由右向左依次比较。当所有字符都能匹配上时，则找到字符串返回查找结果并结束；如果模式串第一个字符与文本串T比较，结果不匹配，则：

求move（o）=First（OT）-First（OP），将模式串移动move（o）个字符。

其中First（OT）：表示文本串T出现的第一个音节点；First（OP）：表示模式串P出现的第一个音节点。move（o）：距离差值；

（3）用模式串P的尾字符与文本串T进行比较，结果匹配，再把模式串第一个字符与文本串T比较，结果匹配。则将模式串与文本串T由右向左依次比较。如果在模式串P的某一字符x失配，则转4；

（4）如果失配的字符x在模式P中没有出现，则：

求：First（x）：从x起始的字符到第一个出现的音节点的距离。那么从字符x开始的m（模式串的长度）+First（x）个文本显然不可能与P匹配成功，直接全部跳过该区域即可，则模式串移位m+First（x）个位置；

（5）如果失配的字符x在模式P中出现，则：以该字符进行对齐。设move（x）为P右移的距离，m为模式串P的长度，max（x）为字符x在P中最右位置。作模式串移位：[m-max（x）]+First（x）。

通过上对面算法的分析，我们可以看出，改进后的BM算法可以减少比较的次数，提高匹配的速度。

2 结束语

越来越多的藏文出版作品在以数字化方式存储，网络上的藏文资料也日益增多，改进针对西文以及中文的搜索算法，寻找适合藏文文字特点的字符查找算法是值得研究的。改进的BM模式匹配算法就是利用藏文字符构字特征以及编码特点，改变了BM算法的比对方式，从而提高匹配的效率。

参考文献：

[1]江涛，于洪志.基于藏文文本的网络舆情监控系统研究[A].全国计算机安全学术交流会论文集[C]，2006.

[2]闵联营，赵婷婷.BM算法的研究与改进[J].武汉理工大学学报，2006（03）：528-530.

[3]殷丽华，张冬艳，方滨兴.面向入侵检测的单模式匹配算法性能分析[J].计算机工程与应用，2004（24）：46-47.

[4]扎西加，珠杰.面向信息处理的藏文分词规范研究[J].中文信息学报，2009（04）：113-117.

[5]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，1999.