来源：高德技术
道路匹配是地图数据处理方面非常基础且重要的理论，特别是道路相关业务，一定避不开道路匹配的应用，这也是业务中普遍会碰到的痛点。
道路匹配定义
道路匹配是地图匹配理论的子集，通俗讲就是两幅地图A和B，在没有唯一ID关联的情况下，如何确定地图A上的道路是B上一条道路的过程。如果做交通轨迹或者地图数据融合方面的研究，那么就一定会遇到地图匹配的问题。
地图匹配 Map Matching:不同条件下获取同一物景的地图之间的配准关系。
道路匹配是刨除了点和面状匹配之外的线状要素理论，道路的话就是路网，也是实际应用中研究最多、应用最广的一部分。
利用路网数据，采用适当算法，将目标定位映射到实际道路上的过程，具体来说道路匹配是：
l 地图匹配理论的首要子集
l 针对矢量拓扑道路数据的匹配模式
l 异源道路数据融合的关键
l 导航定位精度改善的重要手段
空间距离和评价曲线相似性的一般方法
离散点集匹配
路网匹配的两个方面应用：第一个是离散点集匹配，相对简单，随机离散点没有形状和拓扑关系，用欧氏距离作吸附即可，典型应用如离散热力图。
曲线拟合
实际中更有应用价值的是曲线拟合匹配关系，比如轨迹和路网，GPS序列和导航路的相似性。
曲线信息更多，这方面比离散点集有更多的评价要素，也有更高的复杂度。评价曲线相似性的一般要素有长度、形状、曲率、拓扑关系、方向比如正向逆向、距离、属性例如交通规则左转右转禁行等信息。
曲线匹配方法分类
基于几何信息的匹配算法考虑形状、角度等常规要素，属于早期的一些算法，实现最简单，准确度最低。基于拓扑信息的算法，准确度比几何方法大大提升，应用最广。基于概率预测的算法，实现比较困难，实际上应用不多。
目前有一些比较高级的算法理论，包括隐马模型等等，在实际应用中准确度是相对最高的。
实时算法主要用于在线导航，时间和空间复杂度低，离线算法用于数据处理的离线计算，算法复杂，追求最高准确度。
空间距离
线要素的匹配，主要通过几何、拓扑或语义相似度来进行识别，其中通过空间距离来进行要素匹配的常用方式有：
l 闵可夫斯基距离(Minkowski Distance)
l 欧氏距离(Euclidean Distance)
l 曼哈顿距离(Manhattan Distance)
l 切比雪夫距离(Chebyshev Distance)
l 汉明距离(Hamming distance)
l 杰卡德相似系数(Jaccard similarity coefficient)
l 豪斯多夫距离(Hausdorff Distance)
l 弗雷歇距离(Fréchet距离)
最准确的匹配模型-隐式马尔科夫模型HMM
20世纪60年代，Leonard E. Baum和其它作者在一系列的统计学论文中描述了隐式马尔科夫模型。它最初的应用之一是语音识别，80年代成为信号处理的研究重点，现已成功用于故障诊断、行为识别、文字识别、自然语言处理以及生物信息等领域。
核心特征
l 隐式马尔科夫模型五要素：2个状态集合和3个概率矩阵，Viterbi算法。
l 隐含状态S：马尔科夫模型中实际所隐含的状态，通常无法通过直接观测得到，这些状态之间满足马尔科夫性质。
l 可观测状态O：通过直接观测而得到的状态，在隐式马尔科夫模型中与隐含状态相关联。
l 状态转移概率矩阵A：描述隐式马尔科夫模型中各个状态之间的转移概率。
l 观测状态概率矩阵B：表示在t时刻隐含状态是Sj条件下，其可观测状态为Ok的概率。
l 初始状态概率矩阵π：表示隐含状态在初始时刻t=1的概率矩阵
路网匹配实际是一个解码问题，基于HMM的路网匹配算法是在一系列观察的前提下，寻找最有可能产生这个观察序列的隐含状态序列。一系列GPS位置点集合是可观测状态，寻找最有可能产生位置点集合的路网隐藏序列。
2012年ACM SIGSPATIAL Cup是由ACM主办的全球范围内关于地图匹配算法的科技竞赛，竞赛吸引了来自全球31支专业级的参赛队伍。所有算法当中匹配准确率最高的两个都是基于HMM的匹配算法。