匹配算法论文精品(七篇)

序论：写作是一种深度的自我表达。它要求我们深入探索自己的思想和情感，挖掘那些隐藏在内心深处的真相，好投稿为您带来了七篇匹配算法论文范文，愿它们成为您写作过程中的灵感催化剂，助力您的创作。

篇(1)

【关键词】藏文分词 匹配算法 哈希表 词典机制

1 引言

藏文信息处理存在着分词的问题，而藏文分词是对藏文词性标注、藏语音合成、机器翻译、大型语料库建设和信息检索等藏文信息处理的基础。藏文分词的效果会对进一步研究的藏文词性标注、藏语音合成、机器翻译、大型语料库建设和信息检索等藏文信息处理软件的性能和效果产生影响。

为了提高分词的准确率，需要有一个足够大的词库，面对足够大的词库，对词库中的词语的搜索技术就显得十分重要，对词库中词语的搜索速度直接关系到分词系统的性能。词库目前主要是采用索引的机制来实现的，一般用到的索引结构的包括线性索引、倒排表、Trie树、二叉树等。线性索引、倒排表都是静态的索引结构，不利于插入、删除等操作。

2 分词

2.1 词典机制算法

本系统采用的是基于Hash索引的分词词典。分词词典机制可以看作包含三个部分：首字Hash表、词索引表、词典正文。词典正文是以词为单位txt文件，匹配过程是一个全词匹配的过程。首先，通过首字Hash表确定该词在词典中的大概位置，然后根据词索引表进行定位，进而找到在词典正文中的具置。该系统是采用Myeclipse10平台，使用Java语言进行实现的，直接调用Java里的hashmap创建函数，找到该词之后，然后进行字符串匹配。

2.2 基于匹配算法分词

主流的分词方法有三种：分别为基于语言学规则的方法、基于大规模语料库的机器学习方法、基于规则与统计相结合的方法，鉴于目前藏文方面还没有超大型的句子语料库。该系统便采用了基于语言学规则的根据词典进行匹配的方法对藏文进行分词。

根据匹配的方向不同，分为正向和逆向两种匹配算法。本系统采用的是正逆向匹配算法相结合的减字匹配法对藏文进行分词的，因为藏文在每个字的结束时，都会以“”作为分界；每个句子会以“”或者“” 作为分界。因此，对藏文进行分词的减字算法首先以藏文的字符“”或者“”切分出句子，如此一来，原文就被分为相应的若干个句子了。接下来，再对每一个句子进行词典的匹配，如果没有匹配成功就根据藏文字符中“”从句末尾减去一个字符，然后再次进行匹配，直到匹配成功为止。对每个句子重复这些流程，直到每个句子全部分解为词为止。逆向最大匹配是从句子的末尾选择计算最大词的长度，从后往前匹配、切分，其基本原理是和正向最大匹配的原理是相同的。

为了提高切分的精度，该系统使用的是正向最大匹配和逆向最大匹配相结合的方法进行分词，先分别采用两种方法分词，然后根据概率比较两种分词结果，选择概率较大的那种匹配算法作为分词结果。

本系统的逆向最大匹配和正向最大匹配均是采用减字匹配算法，减字算法实现简单，切分效果也比较理想，流程如图1所示。

正向最大匹配（MM） 对于文本中的字串 ABCD，ABCD？W，若ABC∈W，并且AB∈W，然后再判别CD是否属于W，若是，则就切分为AB/CD，如果不是，则切分为AB/C/D。其中W 为分词的词典。逆向最大匹配对于文本中的字串 ABCD，ABCD？W，BCD？W，CD∈W，并且AB∈W，其中W为分词的词典，那么就取切分 AB/CD，根据藏文词组最长的为6个字符组成的，所以进行匹配算法的时候，初始化藏文最大字符串长度为6，流程图如图2所示。而逆向最大匹配算法是从句子的末尾开始进行匹配，其核心算法与正向最大匹配算法相同，只不过开始匹配的方向不同而已。

无论是正向匹配（MM）算法还是逆向匹配（RMM）算法都会产生大量的歧义字段。我们很容易举出这样的例子，如：（五十六个民族心连心）这一句藏语，采用正向匹配算法分词的结果为：，采用逆向匹配算法的分词结果为：，在采用逆向匹配的时候，将会被划分为，而（五十六）实际是一个词，不该划分，诸如此类的藏文句子还有很多，例如 等，无论使用正向最大匹配算法或者使用逆向最大匹配算法都会产生歧义，这种歧义称为组合歧义。为了减少这种歧义的影响，本系统使用两种分词方法相结合的方式。首先分别使用两种算法进行分词，然后通过统计的方法消除部分歧义。具体实现为：设正向最大匹配算法所切分的n个词分别为，则这个句子切分的频率则为；设逆向最大匹配算法所切分的n个词分别为，则这个句子切分的频率则为。如果，则选择正向最大匹配算法所切分的结果，反之，则选择逆向最大匹配算法所切分的结果。

3 结果和分析

结合26个大小不同的实验文本，对基于哈希表索引和匹配算法的分词系统的准确率进行了分析，准确率如图3所示。结果显示，该分词系统的准确率在92%以上。由此可得基于哈希表索引和匹配算法的分词系统在准确率上有不错的效果。

参考文献

[1]华却才让.基于树到串藏语机器翻译若干关键技术研究[D].陕西师范大学，2014.

[2]石方夏，邱瑞，张|，任帅.藏文信息隐藏技术综述[J].物联网技术，2014，12：28-32.

[3]王思力，张华平，王斌.双数组Trie树算法优化及其应用研究[J].中文信息学报，2006，05：24-30.

[4]陈硕，桂腾叶，周张颖等.信息检索在论文写作和项目申报中的应用[J].科技展望，2015，13：274-275.

[5]黄昌宁，赵海.中文分词十年回顾[J]. 中文信息学报，2007，03：8-19.

[6]奉国和，郑伟.国内中文自动分词技术研究综述[J].图书情报工作，2011，02：41-45.

[7]贺艳艳.基于词表结构的中文分词算法研究[D].中国地质大学（北京），2007.

[8]戴上静，石春，吴刚.中文分词中的正向增字最大匹配算法研究[J].微型机与应用，2014，17：15-18.

[9]刘遥峰，王志良，王传经.中文分词和词性标注模型[J].计算机工程，2010，04：17-19.

作者简介

陈硕（1995-），男，自治区拉萨市人。本科在读，主研领域为自然语言处理，数学建模及其应用。

周欢欢（1994-），女，湖南省衡阳市人。本科在读，研究方向为数学建模及其应用、交通运输规划与管理。

通讯作者简介

赵栋材（1976-），男，现为大学藏文信息技术研究中心副教授。主要研究方向为藏文信息处理。

作者单位

篇(2)

关键词：入侵检测；KMP算法；BM算法；RK算法；AC算法；AC－BM算法

中图分类号：TP301文献标识码：B

文章编号：1004 373X(2009)02 063 05

Application of Pattern Matching Algorithm in Intrusion Detection Technique

RAN Zhanjun1,YAO Quanzhu2,WANG Xiaofeng1,ZOU Youjiao1

(1.Xi′an University of Technology,Xi′an,710054,China;2.College of Computer Science and Engineering,Xi′an Unversity of Technology,Xi′an,710048,China)

Abstract：Relying solely on traditional passive defense technology has been unable to meet today′s network security needs,IDS based on pattern－matching is becoming a hotspot of research and application,the efficiency of pattern matching determines the performance of this kind of IDS.A survey of the intrusion detection system classic pattern matching algorithm is given in this paper,including single pattern matching algorithm:KMP algorithm,BM algorithm,RK algorithm and multi－pattern matching algorithm －AC algorithm,AC－BM algorithm.Meanwhile,the efficiency of various algorithms is summarized.Through analysis of algorithms,future research directions of this kind of algorithm are advanced.

Keywords：intrusion detection;KMP algorithm;BM algorithm;RK algorithm;AC algorithm;AC－BM algorithm

0 引 言

随着网络技术的发展，各种基于网络的应用层出不穷。面对日益突出的网络安全问题，仅靠传统的被动防御已经不能满足要求，能够主动检测并预防的入侵检测系统应运而生。

根据采用的分析方法，入侵检测分为误用检测和异常检测。误用检测是指：根据己知的攻击方法，预先定义入侵特征，通过判断这此特征是否出现来完成检测任务。异常检测是指：根据用户的行为或资源的使用状况的正常程度来判断是否属于入侵。由于异常检测的误检率和漏检率高，因此目前大多数入侵检测系统产品均主要采用误用检测的方法。误用检测中使用的检测技术主要有: 模式匹配、专家系统、状态转移等，其中模式匹配原理简单，可扩展性好，而且最为常用。据统计，现在大约95%的入侵检测都是特征匹配的入侵检测。

由此可见，模式匹配算法性能的好坏直接影响到入侵检测系统的效率。随着网络传输速度的大幅度提高，入侵检测系统需要处理的数据量越来越大，如果模式匹配算法来不及处理这些实时的大量的数据包，必然会丢弃部分数据包，而这些被丢弃的数据包中很可能就包含有入侵信息，从而造成漏报。在此介绍几种著名的用于入侵检测的模式匹配算法，包括单模式匹配算法和多模式匹配算法，通过对它们进行剖析和实际测试，提出入侵检测系统中模式匹配算法的选择策略和未来的研究方向。

1 单模式匹配算法

1.1 相关定义

模式匹配：是指在给定长度为n的目标串T=T1T2…Tn中查找长度为m的模式串P=P1P2…Pm的首次出现或多次出现的过程。这里Ti(1≤i≤n)，

Pj(1≤j≤m)∈∑(字符集)，若P在T中出现1次或多次，则称匹配成功，否则称匹配失败。

单模式匹配算法：在目标串中1次只能对1个模式串进行匹配的算法。

多模式匹配算法：在目标串中可同时对多个模式串进行匹配的算法。

最简单的模式匹配算法是Brute－Force算法(BF算法)。在BF算法的目标串和模式串的字符比较中，只要有1个字符不相等，而不管前面已有多少个字符相等，就需要把目标串T回退，下次比较时目标串T只后移1个字符。虽然算法简单，但效率低下，不适合用于入侵检测系统中，不做重点介绍。

高效的模式匹配算法都是设法增大不匹配时目标串T或模式串P之间的偏移量，以减少总的比较次数。下面介绍3种经典的快速单模式匹配算法。

1.2 KMP算法

1970年，S.A.Cook从理论上证明了一维模式匹配问题可以在O(m+n)时间内解决［1］。D.E.Knuth，V.R.Pratt和T.H.Morris 在BF算法的基础上提出了一种快速模式匹配算法，称为KMP算法［1］，该算法消除了BF算法的目标串指针在相当多个字符比较相等后，只要有1个字符比较不等便需要回溯的缺点，使算法的效率得到了大幅度提高，时间复杂度达到最理想的O(m+n)，空间复杂度是O(m)。

KMP算法的基本思想是：若某趟匹配过程中Ti和Pj不匹配，而前j-1个字符已经匹配。此时只需右移模式串P，目标串T不动，即指针i不回溯，让Pk与Ti继续比较。移动后重新开始比较的位置k仅与模式串P有关，而与目标串T无关，因此k可以通过下面的next函数事先确定。

定义next［j］函数为：

next［j］=max{k|1＜k＜j且 P1P2…Pk=

Pj-kPj-k+2…Pj-1} ，集合非空

0，其他情况

-1(标记)，j=0时

1.3 BM算法

相对于BF算法，KMP算法虽然消除了主串指针的回溯，在不匹配时能使模式串右滑若干位，但由上述next函数可知：右滑的最大距离不会超过1趟匹配操作所进了的比较次数j，原因在于KMP算法的匹配操作是从左到右进行的。受到KMP算法的启发，R.S.Boyer和J.S.Moore提出一种新的快速字符串匹配算法－BM算法［1－3］。

BM算法基本思想是：开始时将目标串T与模式串P左对齐，自右至左逐个字符进行比较(即首先比较Pm与Tm)；当某趟比较时Ti与模式串的对应字符不匹配，则把模式串右滑d(x)一段距离，执行由Pm与Ti+d(x)起始的自右至左的匹配检查。BM算法采用以下两条规则计算模式串右移的距离：

(3) g是转移函数，该函数定义如下：g(s,a)：从当前状态s开始，沿着边上标签为a的路径所到的状态。假如(u,v )边上的标签为a，那么g ( u,a ) =v；如果根节点上出来的边上的标签没有a，则g(0,a) =0，即如果没有匹配的字符出现，自动机停留在初态；

(4) f(不匹配时自动机的状态转移)也是转移函数，该函数定义如下：

f(s)：当w是L(s)最长真后缀并且w是某个模式的前缀，那么f(s)就是以w为标签的那个节点；

(5) q0∈Q是初态(根节点，标识符为0)；

(6) FQ，是终态集(以模式为标签的节点集)。

这样，在目标串中查找模式的过程转化成在模式树中的查找过程。查找一个串T时从模式树的根节点开始，沿着以T中字符为标签的路径往下走：若自动机能够抵达终态v，则说明T中存在模式L (v)；否则不存在模式。

AC算法模式匹配的时间复杂度是O(n)，并且与模式集中模式串的个数和每个模式串的长度无关。无论模式串P是否出现在目标串T中，T中的每个字符都必须输入状态机中，所以无论是最好情况还是最坏情况，AC算法模式匹配的时间复杂度都是O(n)，包括预处理时间在内，AC算法总时间复杂度是O(M+n)，其中M为所有模式串的长度总和。

2.3 AC－BM算法

对多模式串的匹配而言，虽然AC算法比BM算法高效得多，但AC算法必须逐一查看目标串的每个字符，即必须按顺序输入，不能实现跳跃，而BM算法则能够利用“右滑”跳过目标串中的大段字符，从而提高搜索速度。如果将BM算法的这种启发式搜索技术应用到AC算法中，则可大大提高多模式匹配算法的效率。许多人据此给出了各种改进的算法。Commentz－Walter最先将BM算法和AC算法结合在一起给出了Commentz－Walter算法；Baeza－Yates结合BMP算法和AC算法也给出了多模式匹配改进算法。

AC－BM算法［5］是Jang－Jong在1993年结合AC算法的有限自动机和BM算法的连续跳跃思想提出来的新算法，利用劣势移动表和优势跳转表来实现跳跃式地并行搜索，算法的时间复杂度为O(mn)。

该算法的思想是：首先把要查找的多个模式构成一个关键字树，把相同的前缀作为树的根节点。模式树从目标串的右端向左移动，一旦模式树确定在适当的位置，字符比较从左向右开始进行。模式树移动时同时使用坏字符移动和好前缀移动。坏字符移动的策略为:如果出现不匹配的情况，移动模式树，使得树中其他模式的能与当前目标串正在比较的字符相匹配的那个字符移动到与当前目标串正在比较的字符的相同位置上，如果在当前的深度上，目标字符没有出现在任何模式中，则模式树的偏移量为树中最短模式的长度。好前缀移动的移动策略为：将模式树移动到一个已被发现是另一个模式子串完全前缀的下一个位置，或者移动到作为树中另一个模式后缀能够正确匹配目标串的某个前缀的下一个位置。在模式树的移动过程中，必须确保模式树的偏移量不能大于树中最短的模式长度。

2.4 AC，AC－BM算法改进情况简介

文献［10］中卢汪节等人针对AC算法在构造状态机时空间冗余较大的情况，对状态机各结点进行压缩存储，使空间性能和时间性能都有提高；文献［11］中万国根等人对AC－BM算法的改进借鉴了BMH算法的思想，取消了原算法的好前缀跳转，优化了坏字符跳转，并修改了skip的计算方法，对大字符集的情况在平均情况下具有更优的性能；文献［12］对AC－BM的改进则是通过预处理思想实现的，在进行AC-BM匹配之前首先扫描首和(或)尾字符，确定其位置，再到相应位置进行匹配，相当于把目标串按模式串首、尾字符分成数段，每段进行比较，段间不含首字符的就直接跳过，不用比较，从而提高效率。

3 算法的实际执行效率

上述这些算法究竟哪种算法具有最好的执行效率呢?能不能仅通过时间复杂度来进行衡量呢？时间复杂度仅是一个度量的范围，表示受几个参数的影响，并不代表一个具体的值，还需要在具体的环境中进行测试。

文献［13］测试了包括上述算法在内的多种单模式和多模式匹配算法的性能。测试平台为：硬件：CPU Intel Xeon 3.46 GHz X 2，内存2 GB DDR，硬盘200 GB SCSI；软件：Windows 2003 Server,Intel IXA SDK4.1。单模式匹配测试的规则集，使用随机生成的8，16，32，48，128位具有代表意义的规则，可以对应端口、IP地址，MAC地址、IPv6地址等，对多模式匹配测试采用Snort系统2.4.3规则集。

单模式匹配算法主要测试模式长度与匹配时间、占用空间及预处理时间的变化关系。测试结果表明：各算法的测试指标在规则长度增长的情况下均呈递增趋势，但BM算法的增长速度最为缓慢，在不太在意存储空间的情况下，BM可以作为优先考虑的算法，同时对IPV6地址也更为合适。

多模式匹配算法的测试项目为规则数与单位匹配时间、占用储存单元、单位预处理时间的变化关系。测试结果表明AC－BM算法在上述3项测试中取得了很好的性能平衡。这也是新

版的Snort系统中选用AC－BM算法的重要原因。

4 入侵检测系统中模式匹配算法的研究方向

常用的模式匹配算法所采用的思想主要有基于字符比较、基于自动机、基于hash查找、基于位逻辑运算和基于Tries树型机构搜索。鉴于目前网络的实际状况，多模式匹配算法更加适合于基于模式匹配的入侵检测系统。这里认为应该从下面3个方面着手：一是继续研究和改进精确的模式匹配，将快速的单模式匹配算法和多模式匹配算法相结合，充分借鉴同类算法的先进思想，如：引入Hash函数、引入自动机、对字符串分块等来不断提高多模式匹配算法的性能；二是尝试采用模糊匹配的策略，国外对此已经开始进行相应的研究；三是对网络数据包和入侵特征进行研究，总结出这两类字符串特点，有针对性地对这两类字符串的匹配问题进行研究。

5 结 语

网络带宽的不断增加、日益严重的网络安全状况要求必须尽快提高网络入侵检测系统的性能。虽然入侵检测系统可以采用很多技术，并且这些技术也在不断的研究和发展中，但是目前主流的实用的入侵检测技术仍然是基于模式匹配的。因此如何提高模式匹配的效率成为研究入侵检测系统的一个关键所在。在此对已有的经典模式匹配算法进行了系统综述，并对入侵检测系统中模式匹配算法的未来研究方向给出了观点。

参考文献

［1］庞善臣,王淑栋,蒋昌俊.BM串匹配的一个改进算法［J］.计算机应用,2004,12(12):11－13.

［2］Boyer R S,Moore J S.A Fast String Searching Algorithm ［J］.Communications of ACM,1977,20(10):762－772.

［3］张立航,潘正运,刘海峰.基于改进的KR算法在网闸中的实现［J］.微计算机信息(管控一体化),2008(24):137－138.

［4］Johnson T,Newman－Wolfe R E.A Comparison of Fast and Low Overhead Distributed Priority Locks ［J］.Journal of Parallel and Distributed Computing,1996,32(1):74－89.

［5］Jason C C,Staniford S,McAlemey J.Towards Faster String for Intrusion Detection or Exceeding the Speed of Snort ［EB/OL］./sotfware/acbm/speed－of－snort－03－16－2001.padf,2003.

［6］黄占友,刘悦.对KMP串匹配算法的改进［A］.第四次全国便携计算机学术交流会论文集［C］.北京:科学出版社,1997.

［7］涛,方滨兴,胡铭曾.对BM串匹配算法的一个改进［J］.计算机应用,2003,23(3):6－8.

［8］张国平,徐汶东.字符串模式匹配算法的改进［J］.计算机工程与设计,2007,28(20):4 881－4 884.

［9］蔡晓妍,戴冠中,杨黎斌.一种快速的单模式匹配算法［J］.计算机应用研究,2008,25(1):45－46,81.

［10］卢汪节,鞠时光.入侵检测系统中一种改进的AC算法［J］.计算机工程与应用,2006(15):146－148.

［11］万国根,秦志光.改进的AC－BM字符串匹配算法［J］.电子科技大学学报,2006,35(4):531－533.

［12］周四伟,蔡勇.AC－BM算法的改进及其在入侵检测中的应用［J］.微计算机应用,2007,28(1):27－31.

［13］王琢,赵永哲,姜占华.网络处理模式匹配算法研究［J］.计算机应用研究,2007,24(12):310－312.

作者简介

冉占军 男，1977年出生，陕西西安人，讲师，硕士研究生。主要研究方向为算法、网络安全。

姚全珠 男，1960年出生，博士，教授。主要研究方向为算法、数据库、网络安全。

篇(3)

关键词:点云数据;配准;ICP算法

中图分类号:TP391.7 文献标识码:A

The Research of Cloud Data Alignment

CHEN San-qing

(School of Computer, Panzhihua University, Sichuan Panzhihua 617000)

Key words: cloud data; alignment;ICP algorithm

为了得到物体真实的三维模型,人们需要获得三维物体表面的真实数据。但是,由于受到测量设备和环境的限制,物体表面完整测量数据的获得往往需要通过多次测量完成。点云(三维数据)就是使用各种三维数据采集仪采集得到的密集数据,它记录了有限体表面在离散点上的各种物理参量。三维曲面的重建就是依据这种密集的点云数据来恢复原始曲面,进而实现三维模型的真实重现的目的。

由于每次测量得到的点云数据往往只覆盖物体部分表面,并且可能出现平移错位和旋转错位,为了得到物体完整表面的点云数据,需要对这些局部点云数据进行整合和配准。因此,在得到点云数据之后,为了得到三维模型的原始曲面,必须要将不同角度,不同位置扫描得到的大容量三维空间数据点集转换到一个统一的坐标系中,该技术称之为数据缝合,即三维点云数据的配准。点云配准是点云数据获取后的第一步处理,也是所有后续处理的基础。因此,配准的精度将直接关系到建模精度。

1 点云数据配准算法的研究进展

一般情况下点云都是以高密度形态存在,为了有效处理各种形式的点云,根据点云的分布特征(如排列方式、密度等)可以把点云分为[1]:散乱点云,即测量点没有明显的几何分布特征,呈散乱无序状态;扫描线点云,即点云由一组扫描线组成,扫描线上的所有点位于扫描平面内;网格化点云,即点云中所有点都与参数域中一个均匀网格的顶点对应;多边形点云,即测量点分布在一系列平行平面内,用小线段将同一平面内距离最小的若干相邻点依次连接可形成一组有嵌套的平面多边形。

针对上述各种形式的点云数据,在20世纪80年代中期,很多学者对其配准进行了大量研究。1987年,Horn、Arun等人用四元数法提出点集对点集配准方法。这种点集与点集坐标系匹配算法通过实践证明是一个解决复杂配准问题的关键方法。1992年,计算计视觉研究者Besl和Mckay[2]介绍了一种高层次的基于自由形态曲面的配准方法,也称为迭代最近点法ICP(Iterative Closest Point),并在此基础上产生了许多的变种算法。ICP主要用于解决基于自由形态曲面的配准问题。但ICP算法对两个点云相对的初始位置要求比较高,点云之间初始位置不能相差太大,并且要求两个匹配点集中的一个点集是另外一个点集的子集。当条件不满足,或相差太大时,会影响ICP算法的收敛结果,使得配准变的不可靠。

Chen等运用两个曲面在法矢方向的距离来代替某一点到其最近点的距离,并将其作为匹配的目标评价函数。这一设想最初是由Potmesil于1983年提出的,它被推广为最优加权的最小二乘方法。Masuda等对点集进行随机采样,用最小中值平方误差作为度量准则,该方法在每次迭代后都需要进行重新采样。Johnson等使用特征提取策略去除没有启发信息的平面点来提高配准速度,在点云数据法矢连续、突变比较少的情况下,其速度没有明显的提高。也有一些学者通过引入参考点的方法来实现三维点云数据的配准,这些参考点实际也是一种标签,需要在测量前粘贴在被测物体上。此外,G.Barequet等人在几何哈希技术基础上采用投票机制实现了部分曲面匹配算法。还有使用卡尔曼估计子的三角片曲面匹配方法等。

2 ICP点云数据配准算法及其改进算法

ICP算法最初由Besl和McKay,提出来的时候,其原意是迭代最近点(IterativeClosestpoint)匹配算法,后来被广泛理解为迭代对应点(IterativeCorrespondingpoint)匹配算法。ICP法实质上是基于最小二乘法的最优匹配方法,它重复进行“确定对应关系点集并计算最优刚体变换”的过程,直到某个表示正确匹配的收敛准则得到了满足。目前,ICP算法在点云数据配准中应用相当广泛,并且得到了许多学者的进一步研究和扩充。基于ICP算法点云数据配准过程如图1所示:

2.1Beslhe和Mckay提出的原始ICP算法[2]

设扫描匹配过程中的参考扫描模型为Sr,待匹配的当前扫描模型为Sc,模型中的数据点个数为N。参考扫描模型和当前扫描模型间的变换矩阵为P=(p0,pl,p2,p3,p4,p5,p6)T 其中,PR=(p0,p1,p2,p3)T四元组表示旋转偏移量,可转化为3×3的旋转矩阵R(PR),PT =(p4,p5,p6)T表示平移偏移量。这样,模型间的变换矩阵可以表示为P=( PR | PT )T 。ICP算法在进行点对匹配时采用的是比较点间欧式距离的方法,而扫描模型间的变换矩阵是通过最小化欧式距离平方函数得到。

整个ICP算法描述如下:

第一步:初始化迭代,P0=( l,0,0,0,0,0,0 )T,迭代次数k,设置欧式距离均方差阀值r以及最大迭代次数Kmax 。

第二步:迭代步骤:

(1)对待匹配扫描模型中的每个点搜索其在参考扫描模型中欧式距离最近的点,生成整个扫描模型的邻近点对集合Yk。

(2)由参考模型中的扫描点和匹配点对集合计算扫描模型间的变换矩阵Pk=(PR k | PT k )T和匹配点对间的欧式距离误差dk。

(3)根据变换矩阵Pk=( PR k | PT k )T变换当前扫描模型Sr中的所有扫描点位置。

(4)计算变换后,参考扫描模型与当前扫描模型间的对应点对间的欧式距离误差dk+1,并计算第k和k+1次迭代中误差变化量。当该变化量小于欧式距离均方差阀值r或迭代次数k大于k max时,停止迭代。

ICP算法是一种迭代算法,具有很高的匹配精度。但由算法描述可知,它存在计算量较大且迭代过程可能无法收敛到全局最优解的缺陷。ICP算法最耗费时间的步骤是求解邻近点对的过程,因为它采用的是全局搜索。为适应不同的环境并克服ICP算法自身的部分缺陷,许多研究人员对其进行了改进。

2.2ICP的改进算法

为了提高基本ICP方法的可靠性和鲁棒性,从匹配点的选择到最小二乘度量目标函数的选取等ICP匹配算法中的各个阶段,许多研究者都提出了各种的优化方法,形成了相应的ICP变型算法。ICP算法的各个阶段划分如下[3]:

(1)匹配模型中进行匹配的数据点的选取采样;

(2)两模型中有对应关系的匹配点对的选择;

(3)匹配点对的适当权值赋予;

(4)过滤某些错误的匹配点对;

(5)度量准则的选取;

(6)最优化方法的确定。

对ICP算法的改进主要集中在如下四点[4]:

(1)点集的不同选取方法。一般情况下点集的选取方法包含如下五种情况,分别是选取所有可用点作为点集;随机选取抽样点作为点集;采用平均抽样方法进行点集选取;根据点的特征信息(如梯度信息等)进行点集选取;选取边缘点作为点集。

(2)点的对应方法。点的对应方法主要有二种,一种是搜索最近点作为对应点;另一种是采用投影求交的方法确定对应点。

(3)点对的拒绝。点对拒绝的实现主要有以下三种情况:对于边缘点的拒绝;对于对应点对中距离过大的点对的拒绝;考虑法向量的点对的拒绝。

(4)加速迭代。主要采用减少迭代次数或使用非迭代的方法来实现,作用是减少运算量,提高计算速度。

Chen和Medioni两位学者在Besl和Mckay的经典ICP算法的基础上进行了改进,该算法的不同之处在于改进后算法的目标函数中的距离是点到对应点出的切平面的距离。事实上,因为一开始的匹配点对通常都是不精确的,这种方法认为在这种不精确的意义下,严格地极小化匹配点对之间的距离平方和不能达到快速的收敛,因此它选取了到匹配点处的切平面的距离来代替点到点的距离。这种方法的好处是一开始就可以使迭代误差很快地减小,也就是快速的收敛,但是因为它用切平面来代替真正的曲面,也就是忽略了目标函数的Hessian中的二次项信息,所以这种方法有时候会不收敛,尤其当目标物体表面曲率变化明显时,这时,二次项信息在目标函数种占有更多的比重。事实上,这种方法是一种Gauss-Newton法,它不保证收敛,但是如果收敛,速度会比较快,是二次收敛。后来有研究者对这种方法提出了改进,加上了步长控制[5](Levenberg-Marquart方法),这样可以保证该方法收敛,而且如果步长选取地合适,并不影响收敛速度,仍然二次收敛。此外,Mitra等引入平方距离(Squared Distance)的概念。把Chen和Medioni的改进中所忽略的二阶信息做了一个理想的近似加入了迭代中,因此能保证更好的收敛性。这种方法在满足标准假设的情况下,是一种准牛顿方法。准牛顿方法是收敛的,而且是二次收敛的。

3 结束语

近年来随着三维扫描技术的发展,特别是三维激光扫描技术的出现,高效、快速、准确的获取真实场景的高精度三维点云数据变得较为容易。利用这些点云数据可以恢复重建具有准确几何信息和真实感的原始物体。本文对点云数据处理中的配准方法进行了论述。本文首先总结分析了点云数据配准算法的研究现状,然后对其中比较具有代表性的ICP算法及其改进算法进行了具体的探讨。目前,对ICP算法研究的主要集中在如何提高ICP算法的稳定性、收敛性和可靠性等方面上,通过改进搜索最近点以及计算的收敛性,来提高ICP算法的配准精度和配准速度。

参考文献:

[1]张舜德,朱东波,卢秉恒.反求工程中三维几何形状测量及数据预处理[J].机电工程技术,2001,30(l):7-10.

[2]Besl P J, MeKay N D. A method for registration of3-D shapes.IEEE Trans onPattern Analysis and Maehine Intelligenee ,1992 ,14(2): 239-256.

[3]潘小林.三维曲面匹配技术研究[D].南京航空航天大学硕士论文,2004.

篇(4)

关键词：SIFT；相似性度量；图像匹配

引言

在计算机视觉领域，图像匹配仍然是当前研究的热点问题。基于特征的匹配方法[1]，因为根据图像中趋于稳定的少量特征进行匹配，使得运算速度快、匹配效果好，所以成为目前研究最多、应用最广泛的一种方法。但是，这种方法需要在图像间进行遍历性的匹配运算，存在计算量大，且精度不高的问题。

1999年，Lowe提出了SIFT（Scale Invariant Feature Transform）算法[2]，该算法利用高斯差分在图像的多尺度空间中快速求解高斯拉普拉斯空间中的极值点，加快了特征提取的速度，提取的SIFT特征对于图像平移、缩放、旋转具有不变性，并且对于仿射变换、视觉变化、光照变化有较强的稳定性和很好的匹配鲁棒性，所以被广泛应用于计算机视觉的图像匹配、图像检索和模式识别等方面[3，5]。虽然SIFT 算法具有上述的优点，但该算法首先要将彩色图像灰度化，仅利用图像的灰度信息和特征点的局部邻域信息，忽略了图像的颜色信息，导致不能识别图像内具有相似结构的特征点。

文章提出基于SIFT的多特征相似性度量算法，首先对彩色壁画图像提取SIFT特征点与特征向量，然后对每个特征点提取HSI彩色特征，最后按定义的相似性度量公式计算两个特征点之间的距离，确定二者是否匹配。

1 特征提取

1.1 SIFT特征提取

尺度空间极值点的检测采用DOG方法，将一个像素点与它相邻的26个点相比较，如果是最大值或最小值，就作为图像中的一个特征点。以特征点为中心，在16×16的邻域内，将采样点与特征点的相对方向通过高斯加权后，分别归入8个方向的梯度方向直方图，最后获得4×4×8的128维特征向量来描述一个SIFT特征点。

SIFT算法的两个关键步骤是关键点检测和关键点描述。在关键点检测阶段，大多是利用两种不同的方法，即尺度不变检测和致密采样。文章采用致密采样进行特征检测，理由如下。一方面，尺度不变检测器在描绘均匀信息时是低效的，而壁画图像中包含着这样的信息。另一方面，在特征匹配时，通过致密采样得到的关键点优于随机抽样和尺度不变的探测器[6]。

SIFT算法首先将彩色图像灰度化，提取的特征关注图像的梯度信息，忽视了图像的彩色信息。文章对彩色图像提取特征，实验发现图像的误匹配点中，存在着彩色信息不一致的问题。因此，文章对图像既提取SIFT特征，又提取颜色特征，对多特征融合设计相似性度量方案，可以减少误匹配率，提高匹配效果。

1.2 颜色特征提取

为了解决误匹配中存在的SIFT梯度信息一致，彩色信息不一致的问题，我们在对特征点提取SIFT特征后，再次提取其颜色特征。由于RGB颜色模型只考虑图像的亮度信息，而HSI颜色模型全面考虑图像的亮度和颜色信息，因而在开发基于彩色描述的图像处理算法中，HSI模型更为有用[7]，文章提取HSI彩色特征。

HSI颜色模型中，H表示色调，指的是人的感官对不同颜色的感受，描述纯色的属性；S表示饱和度，描述的是颜色的纯度；I表示强度，描述的是颜色的明亮程度。

常用的最近邻方法原理是，对于基准图像中的每个特征点，在待匹配图像中寻找距离最近的特征点，然后形成一组匹配对。因为最近邻获得的匹配对中存在大量的误匹配，所以Lowe在论文[8]中对于基准图像中的每个特征点，在待匹配图像中寻找距离最近和次近的两个特征点，当这两个距离的比值小于预设的阈值时，才认为找到了一组正确的匹配对，这样消除了大量的误匹配，取得了不错的匹配效果。文章设阈值为thr，且0

3 实验结果及分析

为了观察算法性能，我们从互联网上寻找了两张有重叠部分的壁画图片进行了实验。图像如图1所示。采用Matlab7.7.0编程，运行在AMD A6-3400M CPU 1.4GHZ和4G内存的PC机上，Windows 7.0操作系统。

实验首先寻找图像的SIFT特征点，然后提取特征点的SIFT特征和HSI特征，再对图1a和图1b按公式（9）进行相似性度量，再分别用欧式距离和卡方距离作为相似性度量，并且thr分别选用0.5，0.6，0.7，0.8进行特征对提纯。结果表明，匹配过程在使用同样的阈值时，三种相似性度量方法中，所得到的匹配正确率相同，而匹配时间不同，按公式（9）计算的距离稍快一些。随着thr值的增大，所得匹配对数减少，当thr取值为0.6时，具有较好的匹配结果。图2为thr取值为0.6时的匹配结果。

另外，实验同时表明，对于图像分别提取SIFT特征和HSI特征，如果仅按SIFT特征或HSI特征计算相似性，所得到的匹配正确率都低于两个特征按公式（9）计算相似性的情况。

因此，对图像提取SIFT特征和HSI特征，按我们定义的相似性度量计算方法，确实提高了图像匹配的效率。

4 结束语

文章采用的算法对彩色壁画图像同时提取SIFT特征和HIS彩色特征，有效地去除了梯度信息一致而彩色信息不一致产生的误匹配。通过定义的相似性度量公式，在计算两个特征点之间是否匹配时，速度更快一些。由于SIFT 算法计算量大，算法复杂，提高图像匹配的实时性，将是下一步的研究工作。

参考文献

[1]ZHU Q，WU B，XU Z.Seed point selection method for triangle constrained image matching propagation[J].IEEE Geoscience and Remote Sensing Letters，2006，3（2）：207-211.

[2]LOWE D G.Object recognition from local scale-invariant feature[C]// Proc.the Seventh IEEE International Conference on Computer Vision.Corfu，Greece： IEEE Press，1999：1150-1157.

[3]张书真，宋海龙，向晓燕，等.采用快速SIFT算法实现目标识别[J].计算机系统应用，2010，19（6）：82-85.

[4]王瑞瑞，马建文，陈雪.多传感器影像配准中基于虚拟匹配窗口的SIFT算法[J].武汉大学学报（信息科学版），2011，36（2）：163-166.

[5]钟金琴，檀结庆，李莹莹，等.基于二阶矩的SIFT特征匹配算法[J].计算机应用，2011，31（1）：29-32.

[6]K.Mikolajczyk，C.Schmid. A performance evaluation of local descriptors [J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1615-1630.

[7]何川.高压输电线路视频监控技术研究[D].北京：北京交通大学，2012.

篇(5)

[关键词]模糊匹配 模糊查找 位置匹配 C语言算法

[中图分类号]TP391.41 [文献标识码]A [文章编号]1009-5349（2013）02-0061-01

引言

为了提升用户拨号的快捷性，要求用户在输入号码的时候，对用户已输入号码进行模糊匹配，并以列表的形式呈现给用户，供用户选择。用户使用手机键盘拨号速度最快不超过100毫秒，这就要求手机必须在100毫秒以内查找结束并把结果呈现给用户。而手机号码、SIM卡号码、最近通讯录号码总和在3000个左右。利用传统的字符串查找已不能满足要求。

本论文仅阐述核心算法部分。

一、算法实现

本算法使用以空间换取时间的办法，通过记录不同数字所在的位置，并通过移位操作来实现模糊查找。此算法复杂度仅仅和用户输入的字符串长度有关，而和实际的字符串长度无关。因此，不同于常规的字符串查找算法。

（一）字符映射

首先，把手机号码中存在的字符映射成16个字符，方法为：把字符“0”-“9”转换成数字0～9；把“*”“#”“+”“p”“w”分别转换成数字10、11、12、13、14；把可能存在的字符“-”或其他字符转换成数字15。

（二）数据结构定义

用元素来定义电话号码的存储结构，一个元素存储一个号码。格式可以如下：

typedef struct

{tCellType nData[16]；

}tElement；

其中tCellType可以为unsigned short或unsigned long。前者代表可容纳电话号码的最大长度为16，后者代表可容纳的最大长度为32（32位机器下）。

（三）数据结构建立

把一个电话号码放到一个元素中去，保证：元素中nData[0]记录数字0所在的位置，nData[1]记录数字1所在的位置，依次类推，nData[15]记录数字15所在的位置。

添加一个电话号码到号码映射中。方法如下：（1）从字符串中取第一个字符，并根据字符映射规则映射为数字。（2）以映射成的数字为索引（index），并记录字符所在的位置为（i），位置从0开始计数。（3）取元素中索引为index的变量，并把位置为i的位设为1。即：nData[index] |=0x01

举例：假如电话号码为“13511051123”，则在nData[1]的0、3、4、7、8的位置1，nData[2]的9的位置1，nData[3]的1、10的位置1，nData[5]的2、6的位置1， nData[0]的5的位置1。

（四）查询方法

假如用户仅仅输入一个字符则只需要一次判断即可。算法复杂度为O（1）。假如用户输入n个字符，则需要：首先判断第0个字符对应元素中的值是否为真，如果是则继续。接着取第1个字符对应的元素值并右移1次，和第0个元素相与得结果tm，如果tm为真则继续。然后取第2个字符对应的元素值并右移2次，和上一次得到的结果相与得到新的tm，如果tm为真则继续。依次执行直到字符串结束。

算法复杂度分析：最好情况下一次判断即可获取结果，即用户输入的第一个字符对应的元素值为0；最坏情况下需要：n-1次移位操作，n-1次与运算，及n次判断操作。但一般用户输入的待查找字符串长度n远远小于原始字符串的长度。

算法示例：取临时变量tm，list为用户输入的待查找字符串通过字符映射得到的数组，n为字符串长度。

tCellType tm = nData[list[0]]；

for（i = 1； tm&&i

{tm&=nData[list[i]] >>（i）；}

if（tm） {//处理找到的记录}

举例：假如电话号码为“13511051123”，如果用户输入的待查找字符串为“105”，则需要判断nData[1]| （nData[0]>>1）|（nData[5]>>2）显然nData[1]在第4位上为1；nData[0]在第5位上为1，右移一位变成第四位；nData[5]在第6位上为1，右移二位变成第四位；相与后仍然为真。

假如用户输入的为“15”，而nData[5]仅仅在2、6的位置上为1，右移一位变成第1、5位，显然nData[1]在1、5位上均为0，相与后仍然为0。

其他说明：实际应用中可以通过一定的方法记录结果，新的查找基于上一次的查找结果进行查找，而没有必要对所有记录重新查找。

篇(6)

关键词：被动定位，匹配场，水下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.

篇(7)

本文基于对大规模出租车GPS数据进行分析，结合交通量OD分布概率模型计算热点小区的交通量，给出拥堵预测模型，帮助城市管理者更好地管理城市交通管理问题。

【关键词】城市交通拥堵 GPS终端定位 OD分布概率

1 研究背景

出租车是城市客运交通的重要组成部分，是常规公共交通的重要补充。随着出租车数量的不断增长，出租车交通量已成为城市道路交通总量中的重要组成部分，成为影响城市道路交通分布及分配预测准确性的重要因素之一。由于出租车运行的随机性，没有固定的起讫点和运行线路，给定量分析带来一定的困难。

各大城市越来越多的出租车的安装了GPS终端，这些终端能够每隔1分钟向出租车管理中心发送本车的位置、速度和方向等信息，是车辆GPS实时数据。原始数据主要保存出租车上装配的GPS终端所采集的数据，这些数据包括序号，车牌号码，GPS时间，经度，纬度，车辆状态（空车、重车），车辆速度，车辆方向（8个方向）等信息。这些GPS数据为我们研究出租车交通情况题共了参考和依据。

2 传统交通分析模型存在的问题

现阶段在交通拥堵方面主要集中在研究某个路口的情况，并且用缓冲区方法，而没有对整个区域有个整体的描述，而对于整个区域的研究则是基于交通需求建立模型，数据采集的精度不高。

目前公共交通设施是最常见的移动轨迹数据采集途径。从已有的研究工作看，针对移动轨迹数据的分析碰到的问题可能有：

2.1 数据存储

大规模轨迹数据的存储一般都采用基于R-tree索引（或在R-tree基础上改良的索引，如Quad-tree）的数据库，这类索引的好处是给定查询点以后，可以从查询点所在索引结点出发，沿着树型索引依次访问到离查询点距离越来越远的被索引的点；最近，有很多研究者提出了针对路网距离的索引，使得路网距离下也可以类似的由近及远的访问被索引的点。基于以上这类索引结构，kNNT问题可以转化为信息检索领域中的聚合Top-k查询问题。

2.2 地图匹配问题

地图匹配算法可以按照其考虑的轨迹范围分成全局算法和局部算法。局部算法又称递增式算法，该类方法采用贪心的策略依次将每个轨迹点匹配到相应的路段上。这类算法通常基于距离和角度的相似性，对于每个轨迹点找到局部最优的路段进行匹配。

2.3 移动数据的收集与处理问题

现阶段针对交通拥堵的研究主要集中在交通路口，对数据的收集主要为车辆的行驶速度与方向信息，其中不包含车辆的具体信息如车牌、车辆具置等，这样不能够做到对行驶车辆的实时监测和数据的精确处理。

2.4 缺少居民出行信息

在研究拥堵问题时必须要考虑到对周边居民的影响，之前的算法中不包含此类信息，诸如周边小区居民出行的高峰时段与高峰时间，不能做到将这些信息及时的反馈。

3 基于移动数据的拥堵预测算法

3.1 算法的详细过程

本算法主要通过大规模出租车GPS数据进行分析，结合路网信息，首先获取热点区域和热点小区；其次结合交通量OD分布概率模型计算热点小区的交通量，然后计算各个小区的总体出行情况，从而获取各小区的交通出行量，同时结合时间信息查找各时段拥堵路段和拥堵路口，最后依据上述信息得到具体的算法过程：

（1）首先，由安装在各个出租车上的GPS装置得到实时的出租车载客信息，包含着各个时刻出租车的位置信息。我们可以利用马克威分析系统中关于快速聚类的方法来对各小区进行划分，得到每个小区的具体坐标和热点小区的具置信息。

（2）其次，通过建立的交通量OD分布概率模型，利用Bayes方法对该模型进行参数估计与效果检验，由马克威分析系统得到各小区的交通量信息，求解出交通量的OD分布。

（3）再次，通过得到的小区交通量的OD分布，来绘制各热点小区交通量的分布模型。

（4）然后，通过采集周边各小区的居民出行数据，得到各小区居民出行的高峰时段与出行的热点小区区域，并且将得到的热点出行区域信息与上面步骤中得到的出租车出行的热点小区区域进行匹配，得到交叉地带。

（5）最后，通过收集出租车的GPS数据，筛选出有用的数据，由上述算法，便可以查找到车辆比较拥堵的路段与时段信息。将该信息与上面采集到的居民出行的高峰时段与热点小区区域进行比较匹配，即可得到居民出行的拥堵路段与时段信息。

3.2 算法的创新之处

针对大规模轨迹数据的分析问题，现有的解决思路往往都是通过构造地图来进行热点扫描和偏好轨迹扫描。针对大规模轨迹数据，之前已经完成了离线预处理、频繁轨迹图模型、以及在线打车推荐部分算法。本算法的关键特色是从大规模GPS数据快速抽取热点和热点小区，然后绘制频繁小区地图，结合交通量分析计算热点小区出行量，再根据各个小区的总体出行情况，获取各个小区的交通出行量，从而查找各时段拥堵路段和拥堵路口，根据上述参数获取拥堵预测模型。具体说来，本算法的创新之处有：

（1）由安装在出租车上的GPS得到出租车每个时段的行驶信息，可以得到实时的运行信息。

（2）设计与实现了热点和热点小区的识别算法。

（3）建立交通量OD分布概率模型，求解出交通量的OD分布。

（4）由采集到的GPS数据动态构造各个时段拥堵路段和路口的计算模型。得到拥堵路段与时段模型。

（5）增加了居民的出行信息，通过采集到的小区居民出行高峰时段与路段信息与出租车拥堵路线进行匹配，可以得出居民出行的拥堵区域与时段信息，更加方便小区居民进行出行选择，同时提高了该算法的应用性。

4 结论

当前是一个信息爆炸的年代，由于物联网技术的发展，我们已经进入了大数据时代。

本文基于GPS终端的海量数据，计算随时间变化的车流状态，结合交通量分布OD分布概率模型来计算热点小区的交通量，最终得到拥堵的预测模型，可有效地帮助城市管理者管理城市交通和小区居民选择更加合适的出行方式与时间，在北京、上海等大中城市具有很高的应用前景。

参考文献

[1]黄凤忖.电信运营业发展的影响因素分析[D].首都经贸大学硕士学位论文，2005（03）.

[2]李勇平.遗传神经网络在电信业务收入预测中的应用研究[J].商场现代化，2008（11）.

[3]胡德敏，曹桓.四网协同无线网络规划策略与综合评价研究[J].通信管理与技术，2012（12）.