地图匹配的容灾方法、装置、设备及存储介质

摘要

本申请公开了一种地图匹配的容灾方法、装置、设备及存储介质，涉及地图匹配领域。具体实现方案为：基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹；基于第二轨迹和预先建立的路径集合，确定第二轨迹的路径，以根据确定的第二轨迹的路径进行地图匹配，路径集合包括多条路径，每条路径包括多个关键节点。本申请能够提高地图匹配的容灾效果。

说明书

技术领域

本申请涉及数据挖掘领域，具体涉及地图匹配领域。

背景技术

轨迹挖掘在智能交通、导航路线挖掘、数字地图制作、智能引擎情报等方面具有广泛的应用。轨迹挖掘需要大量的轨迹数据，轨迹数据的精确度影响着其在各个方面的应用效果，因此，在轨迹挖掘过程中，需要对轨迹数据进行地图匹配。

地图匹配过程中，经常会进行容灾处理，例如将轨迹数据下发至地图匹配装置的过程中，会过滤轨迹数据中的一些轨迹点，再下发至地图匹配装置。但地图匹配过程中，轨迹数据越完整，地图匹配的计算代价就越小，同时，对于下游的应用，例如路况、ETA的应用效果也越好。目前，地图匹配无法同时兼顾减少下发数据量和减小计算量，导致容灾效果不好。

发明内容

第一方面，本申请实施例提供了一种地图匹配的容灾方法，包括：基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹；基于所述第二轨迹和预先建立的路径集合，确定所述第二轨迹的路径，以根据确定的所述第二轨迹的路径进行地图匹配，所述路径集合包括多条路径，每条所述路径包括多个关键节点。

本申请实施例通过对GPS分发系统下发的第一轨迹，进行基于预先设定的关键节点的抽稀，从而减小数据量，之后在地图匹配确定路径阶段，基于预先建立的路径集合，对抽稀后的第二轨迹确定路径，由于预先建立的路径集合中包括多条路径，且每条路径包括多个关键节点，因此，可以直接在路径集合中对抽稀后的轨迹查找相应的路径，不需要在地图中搜索所有路径再确定唯一路径，计算代价小，能够保证地图匹配的稳定性要求，达到很好的容灾效果。

可选的，所述基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹，包括：将所述关键节点周围第一预设范围内的轨迹点保留，并过滤其余轨迹点，得到第二轨迹。

可选的，所述GPS点分发系统下发的第一轨迹中的每个轨迹点对应有标识信息，所述标识信息用于标识所述轨迹点是否位于关键节点周围第一预设范围内；所述将所述关键节点周围第一预设范围内的轨迹点保留，并过滤所述第一轨迹上的其余轨迹点，得到第二轨迹，包括：在所述标识信息是所述轨迹点位于所述关键节点周围第一预设范围内的情况下，接收所述轨迹点；在所述标识信息是所述轨迹点位于所述关键节点周围第一预设范围之外的情况下，过滤所述轨迹点。

本实施例中，通过对GPS点分发系统采集的轨迹点对应设置标识信息，用于标识轨迹点是否位于关键节点周围第一预设范围内，从而能够使得地图匹配装置实现快速抽稀，提高地图匹配的效率。

可选的，所述将所述关键节点周围第一预设范围内的轨迹点保留，并过滤所述第一轨迹上的其余轨迹点，得到第二轨迹，包括：确定所述关键节点是否合法；在所述关键节点合法的情况下，确定所述关键节点周围第二预设范围内是否存在其他关键节点；在所述关键节点周围第二预设范围内不存在其他关键节点的情况下，将所述关键节点周围预设范围内的轨迹点保留，并过滤所述第一轨迹上的其余轨迹点，得到第二轨迹。可选的，所述基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹，包括：在预设时间内，调用所述第一轨迹超时的次数超过预设次数的情况下，基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹。

本实施例中，通过根据调用第一轨迹超时的次数，来判断是否触发抽稀，能够在实时地图匹配过程中，通过匹配效果降级的方式保证地图匹配的稳定性，从而为下游的应用提供很好的服务，不影响下游对地图匹配结果的应用。

可选的，所述第一轨迹为实时轨迹；所述基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，包括：在所述实时轨迹的起点不在所述关键节点周围预设范围内，且在所述实时轨迹到达第一个关键节点之前，接收所述GPS点分发系统下发的所有轨迹点；在所述实时轨迹的起点在所述关键节点周围预设范围内的情况下，将所述关键节点周围第一预设范围内的轨迹点保留，并过滤其余轨迹点，得到第二轨迹。

可选的，所述第一轨迹为离线轨迹，所述离线轨迹包括起点和终点；所述基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，包括：在所述离线轨迹的起点和/或终点不在关键节点周围预设范围内的情况下，确定所述离线轨迹为所述第二轨迹；在所述离线轨迹的起点和终点在关键节点周围预设范围内的情况下，将所述关键节点周围第一预设范围内的轨迹点保留，并过滤所述第一轨迹上的其余轨迹点，得到第二轨迹；在所述离线轨迹的起点或终点在关键节点周围预设范围内，且所述起点和终点之间存在其余关键节点的情况下，将所述关键节点周围第一预设范围内的轨迹点保留，并过滤所述第一轨迹上的其余轨迹点，得到第二轨迹；在所述离线轨迹的起点或终点在关键节点周围预设范围内，且所述起点和终点之间不存在其余关键节点的情况下，确定所述离线轨迹为所述第二轨迹。

可选的，所述路径集合包括多个位置点，且相邻的两个位置点之间具有至少一条路径，每条路径的起点和终点之间包括至少一个关键节点；所述基于所述抽稀轨迹和预先建立的路径集合，确定所述第二轨迹的路径，包括：在所述路径集合中，对所述第二轨迹中相邻的两个轨迹点分别匹配相应的第一位置点和第二位置点；将所述第一位置点和所述第二位置点之间的路径，确定为所述第二轨迹中对应的两个轨迹点之间的路径；重复上述过程，得到所述第二轨迹的路径。

本实施例通过在路径集合中查找相邻两个轨迹点之间的路径，来确定第二轨迹的路径，能够缩短确定路径的时间，减小计算代价，保证地图匹配的稳定性要求，达到很好的容灾效果。

可选的，所述路径集合按照如下方法建立：基于标志性建筑物，在所述地图中确定多个位置点；基于所述多个位置点之间的历史轨迹，确定所述多个位置点之间的路径，得到所述路径集合。

第二方面，本申请实施例提供了一种地图匹配的容灾装置，包括：抽稀模块，用于基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹；路径确定模块，用于基于所述第二轨迹和预先建立的路径集合，确定所述第二轨迹的路径，以根据确定的的所述第二轨迹路径进行地图匹配，所述路径集合包括多条路径，每条所述路径包括多个关键节点。

可选的，所述抽稀模块在基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹时，具体包括：将所述关键节点周围第一预设范围内的轨迹点保留，并过滤其余轨迹点，得到第二轨迹。

可选的，所述GPS点分发系统下发的第一轨迹中的每个轨迹点对应有标识信息，所述标识信息用于标识所述轨迹点是否位于关键节点周围第一预设范围内；所述抽稀模块在将所述关键节点周围第一预设范围内的轨迹点保留，并过滤所述第一轨迹上的其余轨迹点，得到第二轨迹时，具体包括：在所述标识信息是所述轨迹点位于所述关键节点周围第一预设范围内的情况下，接收所述轨迹点；在所述标识信息是所述轨迹点位于所述关键节点周围第一预设范围之外的情况下，过滤所述轨迹点。

可选的，所述抽稀模块在将所述关键节点周围第一预设范围内的轨迹点保留，并过滤所述第一轨迹上的其余轨迹点，得到第二轨迹时，具体包括：确定所述关键节点是否合法；在所述关键节点合法的情况下，确定所述关键节点周围第二预设范围内是否存在其他关键节点；在所述关键节点周围第二预设范围内不存在其他关键节点的情况下，将所述关键节点周围预设范围内的轨迹点保留，并过滤所述第一轨迹上的其余轨迹点，得到第二轨迹。

可选的，所述抽稀模块在基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹时，具体包括：在预设时间内，调用所述第一轨迹超时的次数超过预设次数的情况下，基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹。

可选的，所述第一轨迹为实时轨迹；所述抽稀模块在基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀时，具体包括：在所述实时轨迹的起点不在所述关键节点周围预设范围内，且在所述实时轨迹到达第一个关键节点之前，接收所述GPS点分发系统下发的所有轨迹点；在所述实时轨迹的起点在所述关键节点周围预设范围内的情况下，将所述关键节点周围第一预设范围内的轨迹点保留，并过滤其余轨迹点，得到第二轨迹。

可选的，所述第一轨迹为离线轨迹，所述离线轨迹包括起点和终点；所述抽稀模块在基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀时，具体包括：在所述离线轨迹的起点和/或终点不在关键节点周围预设范围内的情况下，确定所述离线轨迹为所述第二轨迹；在所述离线轨迹的起点和终点在关键节点周围预设范围内的情况下，将所述关键节点周围第一预设范围内的轨迹点保留，并过滤所述第一轨迹上的其余轨迹点，得到第二轨迹；在所述离线轨迹的起点或终点在关键节点周围预设范围内，且所述起点和终点之间存在其余关键节点的情况下，将所述关键节点周围第一预设范围内的轨迹点保留，并过滤所述第一轨迹上的其余轨迹点，得到第二轨迹；在所述离线轨迹的起点或终点在关键节点周围预设范围内，且所述起点和终点之间不存在其余关键节点的情况下，确定所述离线轨迹为所述第二轨迹。

可选的，所述路径集合包括多个位置点，且相邻的两个位置点之间具有至少一条路径，每条路径的起点和终点之间包括至少一个关键节点；所述路径确定模块在基于所述抽稀轨迹和预先建立的路径集合，确定所述第二轨迹的路径时，具体包括：在所述路径集合中，对所述第二轨迹中相邻的两个轨迹点分别匹配相应的第一位置点和第二位置点；将所述第一位置点和所述第二位置点之间的路径，确定为所述第二轨迹中对应的两个轨迹点之间的路径；重复上述过程，得到所述第二轨迹的路径。

可选的，所述路径确定模块按照如下方法建立所述路径集合：基于标志性建筑物，在所述地图中确定多个位置点；基于所述多个位置点之间的历史轨迹，确定所述多个位置点之间的路径，得到所述路径集合。

第三方面，本申请实施例提供了一种电子设备，包括：至少一个处理器；以及与所述至少一个处理器通信连接的存储器；其中，所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述至少一个处理器执行，以使所述至少一个处理器能够执行第一方面所述的方法。

第四方面，本申请实施例提供了一种存储有计算机指令的非瞬时计算机可读存储介质，所述计算机指令用于使所述计算机执行第一方面所述的方法。

第五方面，本申请实施例提供了一种地图匹配方法，包括：对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹；在预先建立的路径集合中，确定与所述第二轨迹对应的路径，以根据确定的所述第二轨迹的路径进行地图匹配。

上述申请中的一个实施例具有如下优点或有益效果：通过对GPS分发系统下发的第一轨迹，进行基于预先设定的关键节点的抽稀，从而减小数据量，之后在地图匹配的确定路径阶段，基于预先建立的路径集合，对抽稀后的轨迹确定路径，由于预先建立的路径集合中包括多条路径，且每条路径包括多个关键节点，因此，可以直接在路径集合中对抽稀后的轨迹查找相应的路径，不需要在地图中搜索所有路径再确定唯一路径，计算代价小，能够保证地图匹配的稳定性要求，达到很好的容灾效果。因为采用对GPS分发系统下发的第一轨迹，进行基于预先设定的关键节点的抽稀，以及在地图匹配确定路径阶段，基于预先建立的路径集合，对抽稀后的轨迹确定路径，由于预先建立的路径集合中包括多条路径，且每条路径包括多个关键节点技术手段，所以克服了对抽稀后的轨迹需要在地图中搜索所有路径确定唯一路径，导致计算代价大，容灾效果不好的技术问题，进而达到保证地图匹配的稳定性要求，达到很好的容灾效果的技术效果。

上述可选方式所具有的其他效果将在下文中结合具体实施例加以说明。

附图说明

附图用于更好地理解本方案，不构成对本申请的限定。其中：

图1为本申请实施例提供的地图匹配的容灾系统的结构示意图；

图2为本申请实施例提供的未经过抽稀的轨迹数据的示意图；

图3为现有技术对轨迹进行抽稀的原理示意图；

图4为本申请实施例提供的对图2所示的轨迹进行抽稀的结果示意图；

图5为本申请实施例提供的地图匹配的容灾方法流程图；

图6为本申请实施例提供的对轨迹进行抽稀的原理示意图；

图7为图6的对轨迹进行抽稀后的结果示意图；

图8为本申请实施例提供的根据抽稀后的轨迹确定路径的示意图；

图9为本申请实施例提供的路径集合的示意图；

图10为本申请实施例提供的地图匹配的容灾装置的结构示意图；

图11为用来实现本申请实施例的地图匹配的容灾方法的电子设备的框图。

具体实施方式

以下结合附图对本申请的示范性实施例做出说明，其中包括本申请实施例的各种细节以助于理解，应当将它们认为仅仅是示范性的。因此，本领域普通技术人员应当认识到，可以对这里描述的实施例做出各种改变和修改，而不会背离本申请的范围和精神。同样，为了清楚和简明，以下的描述中省略了对公知功能和结构的描述。

图1为本申请实施例提供的地图匹配的容灾系统的结构示意图。请参阅图1，该容灾系统10包括：全球定位系统(Global Positioning System，GPS)点分发系统11、地图匹配集群12和存储集群13；其中，GPS点分发系统11与地图匹配集群12之间设置有地图匹配接口，GPS点分发系统11通过地图匹配接口将GPS采集的实时轨迹下发至地图匹配集群12，地图匹配集群12包括多个地图匹配装置，同样，存储集群13包括多个存储装置。

由于GPS的精度问题，导致直接将GPS采集的轨迹点投影到路网中，投影点会明显偏离真实道路，因此，需要地图匹配集群12根据轨迹数据进行地图匹配，地图匹配是指在保证获取位置信息的前提下，修正GPS精度导致的投影偏差以提高定位准确性。此外，路网中一些路线在绘制时，由于绘制的路线本身存在偏差，故需要根据绘制路线，对接收到的轨迹点进行修正。

地图匹配集群12根据轨迹数据完成地图匹配后，会将处理后的轨迹数据存储至存储集群13，以应用于处于地图匹配下游的智能交通、导航或者数据引擎情报等方面，例如路况分析、预计抵达时间(Estimated Time of Arrival，ETA)、实时路网挖掘、路线挖掘、绑路、路段的开通、路段的阻断、路段的挂接、新路发现和交通限制等。

在上述的地图匹配过程中，地图匹配对于稳定性要求很高，而在节假日等高峰期间，GPS点分发系统下发给地图匹配集群的轨迹数据量就会增大很多，导致地图匹配的稳定性受到影响。为了保证地图匹配的稳定性，目前采用容灾策略，容灾可以理解为对GPS点分发系统下发的轨迹数据进行抽稀，或者是丢弃部分用户的轨迹数据，以换取地图匹配稳定性的方案。

图2为本申请实施例提供的未经过抽稀的轨迹数据的示意图。请参阅图2，可以看到，该条轨迹中包括起点(图2中从左往右数第1个轨迹点)、终点(图2中从左往右数第6个轨迹点)以及起点和终点之间的4个轨迹点，根据这6个轨迹点所构成的形状，能够确定起点和终点之间的唯一路径。

轨迹由在时序上连续的多个轨迹点构成，对轨迹进行抽稀，可以理解为将轨迹中的一些轨迹点除去，剩余轨迹点即为抽稀后的轨迹。图3为现有技术对轨迹进行抽稀的原理示意图。如图3所示，图中空心圆点代表抽稀过程中过滤掉的轨迹点，黑色实心圆点代表抽稀后剩余的轨迹点。可以了解，这种抽稀操作能够减小数据量。

但地图在根据轨迹进行地图匹配过程中，经常需要确定两个轨迹点之间的唯一路径。图4为本申请实施例提供的对图2所示的轨迹进行抽稀的结果示意图。图4是对图2中位于起点和终点之间的轨迹点过滤后得到的，请参阅图4，地图匹配过程中，在确定第1个轨迹点和第5个轨迹点之间的路径的过程中，需要搜索第1个轨迹点和第5个轨迹点之间所有可能的路径，最终确定唯一路径。如此，地图匹配过程中，在地图中寻找路径的计算代价反而会增大，影响地图匹配的稳定性，导致容灾效果不好。另外，丢弃部分用户的轨迹数据对于下游的应用也会有影响。

本申请实施例提供的地图匹配的容灾方法，旨在解决现有技术的如上技术问题。

下面以具体地实施例对本申请的技术方案以及本申请的技术方案如何解决上述技术问题进行详细说明。下面这几个具体的实施例可以相互结合，对于相同或相似的概念或过程可能在某些实施例中不再赘述。下面将结合附图，对本申请的实施例进行描述。

图5为本申请实施例提供的地图匹配的容灾方法流程图。本申请实施例针对现有技术的如上技术问题，提供了地图匹配的容灾方法，请参阅图5，该方法具体步骤如下：

步骤501、基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹。

如图1所示，由GPS点分发系统11从GPS获取GPS采集的第一轨迹，并下发至地图匹配装置。第一轨迹是全量轨迹数据，全量轨迹数据可以理解为GPS采集的完整的轨迹数据。

本实施例中，地图匹配装置可以基于预先设定的关键节点对第一轨迹进行抽稀，抽稀后的全量轨迹数据称之为第二轨迹。

可选的，第一轨迹为实时轨迹，第一轨迹包括多个实时轨迹点，地图匹配装置基于预先设定的关键节点对第一轨迹进行抽稀，包括：地图匹配装置确定是否接收GPS点分发系统当前下发的实时轨迹点。

本实施例中，预先设定的关键节点，是指在地图中，预先设定一些关键节点，关键节点包括兴趣点(Point of Interest，POI)，可以是具有标识性的位置点，例如具有标志性的建筑物等，例如地铁站、医院、路口、变道口等。

步骤502、基于第二轨迹和预先建立的路径集合，确定第二轨迹的路径，以根据确定的第二轨迹的路径进行地图匹配。

其中，预先建立的路径集合包括多条路径，每条路径包括多个关键节点，关键节点包括起点、终点，起点和终点之间的关键节点称之为中间节点。

可选的，基于第二轨迹和预先建立的路径集合，确定第二轨迹的路径，包括：对第二轨迹在预先建立的路径集合中匹配相应的路径，将对第二轨迹匹配的路径作为第二轨迹的路径。

其中，根据确定的第二轨迹的路径进行地图匹配的过程可以参见现有技术的介绍，本实施例在此不再赘述。

本申请实施例通过对GPS分发系统下发的第一轨迹，进行基于预先设定的关键节点的抽稀，从而减小数据量，之后在地图匹配确定路径阶段，基于预先建立的路径集合，对抽稀后的轨迹确定路径，由于预先建立的路径集合中包括多条路径，且每条路径包括多个关键节点，因此，可以直接在路径集合中对抽稀后的轨迹查找相应的路径，不需要在地图中搜索所有路径再确定唯一路径，计算代价小，能够保证地图匹配的稳定性要求，达到很好的容灾效果。

可选的，基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹，包括：将第一轨迹中，位于关键节点周围第一预设范围内的轨迹点保留，并过滤第一轨迹上的其余轨迹点，得到第二轨迹。

例如，以关键节点所在位置点为圆心，预设距离为半径R2确定关键节点的预设范围，并确定第一轨迹中的轨迹点是否位于该圆形范围内，若第一轨迹中的轨迹点位于该圆形范围内，则将该轨迹点保留；若实时轨迹中的轨迹点位于该圆形范围之外，则过滤该轨迹点。对于位于该圆形周长上的轨迹点，可以保留。经过上述过程，保留的轨迹点形成的形状就是抽稀轨迹。

请参阅图6，在地图中，假设第一轨迹的起点为百度大厦，终点为西二旗地铁站，百度大厦和西二旗地铁站之间具有两条路径，每条路径上存在3个关键节点，其中，百度大厦和西二旗地铁站也可以认为是关键节点，图6中的轨迹点构成百度大厦到西二旗地铁站的第一轨迹，在抽稀时，可以将相邻的两个关键节点之间位于圆形(图中以虚线圆圈示出)圈定的范围之外的轨迹点过滤，剩余的轨迹点，就是抽稀后的轨迹，即第二轨迹。

请参阅图7，是对图6中的第一轨迹进行抽稀后的轨迹。可以看到，抽稀后的轨迹丢弃了关键节点之间，且位于两个关键节点各自的周围预设范围之外的轨迹点。例如，将位于两个关键节点之间，且位于关键节点周边50米范围之外的轨迹点丢弃，其余的轨迹点就是实时地图匹配装置最终接收到的轨迹点。在地图匹配的过程中，可以根据保留的这些轨迹点，还原用户的轨迹路线。如此，既节省了存储空间，又减少了计算量，在流量规模超限的情况下，可以快速达到容灾的效果。

可选的，GPS点分发系统下发的第一轨迹中的每个轨迹点对应有标识信息，标识信息用于标识轨迹点是否位于关键节点周围预设范围内；将第一轨迹的起点及其关键节点周围预设范围内的轨迹点保留，并过滤第一轨迹上的其余轨迹点，得到第二轨迹，包括：在标识信息是轨迹点位于关键节点周围预设范围内的情况下，接收轨迹点；在标识信息是轨迹点位于关键节点周围预设范围之外的情况下，过滤轨迹点。其中，过滤轨迹点可以理解为丢弃轨迹点，或者是不接收该轨迹点。本实施例中，GPS点分发系统下发的实时轨迹点对应有标识信息，该标识信息用于标识该轨迹点是否为位于兴趣点POI周围预设范围内，若该轨迹点位于兴趣点POI周围预设范围内，则将其标注为第一标识信息，若该轨迹点不在POI周围预设范围内，则将其标注为第二标识信息。例如，若轨迹点在POI周围预设范围内，则标注为1，若轨迹点不在POI周围预设范围内，则标注为0。在正常情况下，地图匹配装置会接收GPS点分发系统下发的所有轨迹点，包括标注为1和0的所有轨迹点。在触发容灾后，地图匹配装置会对GPS点分发系统下发的所有轨迹点进行分析，以确定接收哪些轨迹点。例如，接收所有标注为1的轨迹点，以通过地图匹配的匹配效果降级的方式来保证地图匹配的稳定性。

可选的，容灾可以通过如下方式触发：在预设时间内，调用第一轨迹超时的次数超过预设次数的情况下，则触发容灾。容灾触发后，则基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀。本实施例对容灾的触发判断，可以理解为抽稀策略的执行之前，首先判断是否触发了容灾处理，若触发了容灾处理，再进行基于预先设定的关键节点对实时轨迹进行抽稀的实施方式的技术方案。例如，在预设时间段T内，地图匹配装置调用地图匹配接口获取轨迹数据的总次数为10次，其中有6次的调用时长超过了预设调用时长，则认为有6次都超时了，也就是说在预设时间T内，超时的比例为60％，假设预设比例为40％，就认为此时需要触发容灾。

可选的，将第一轨迹的关键节点周围预设范围内的轨迹点保留，并过滤第一轨迹上的其余轨迹点，得到第二轨迹，包括：确定第一轨迹的关键节点是否合法；在关键节点合法的情况下，确定关键节点周围第二预设范围内是否存在其他关键节点；在关键节点周围第二预设范围内不存在其他关键节点的情况下，将关键节点周围预设范围内的轨迹点保留，并过滤第一轨迹上的其余轨迹点，得到第二轨迹。具体的，GPS点分发系统下发给地图匹配集群的第一轨迹包括实时轨迹和离线轨迹。那么，在第一轨迹是实时轨迹的情况下，可以基于第一轨迹当前的运动趋势信息确定第一轨迹将要到达的关键节点是否合法；在关键节点合法的情况下，确定关键节点是否为第一轨迹待经过的唯一的关键节点；在关键节点合法且唯一的情况下，将第一轨迹的起点及其关键节点周围预设范围内的轨迹点保留，并过滤第一轨迹上的其余轨迹点，得到第二轨迹。本实施例中，实时轨迹当前的运动趋势信息，可以根据相邻两个轨迹点之间的时间间隔、速度、加速度、方向等信息来确定。

其中，确定关键节点是否合法，至少包括如下几种可选的实施方式：

在第一种可选的实施方式中，确定关键节点是否合法，包括：在实时轨迹将要到达关键节点的情况下，确定实时轨迹是否会经过关键节点。具体的，可以是在实时轨迹的当前实时轨迹点距离关键节点预设距离的情况下，确定实时轨迹是否会经过关键节点。以根据时间间隔确定关键节点的合法性为例，若从A地点到B地点，正常情况下，开车需要10分钟，但是GPS采集的实时轨迹所对应的时间超过了10分钟，例如1小时，那么认为该实时轨迹的轨迹点很大概率不会经过该关键节点，该关键节点不合法。对于速度和方向等信息来确定合法性，可以参见时间间隔的介绍，此处不再赘述。

在第二种可选的实施方式中，GPS采集的轨迹点是与关键节点对应的轨迹点，确定关键节点是否合法，包括：基于GPS采集的轨迹点的半径信息确定当前轨迹点是否合法。例如，GPS采集的轨迹点在微观来看，可以认为是一个圆形，若GPS采集的轨迹点的半径超过预设的半径，则确定该关键节点不合法，否则，确定该关键节点合法。

确定了关键节点合法后，还需要确定该关键节点是否为该实时轨迹将会经过的唯一关键节点。例如，在起点和终点之间，具有两条关键路径，这两条关键路径近乎相同，仅分布的关键节点存在差异，并且两条关键路径上的关键节点之间的距离小于预设距离，那么认为该关键节点不唯一，对当前的实时轨迹不做抽稀处理。

可选的，若第一轨迹为离线轨迹，则可以采用第二种可选的实施方式来确定其是否合法。

可选的，第一轨迹为实时轨迹，则在实时轨迹的起点不在关键节点周围预设范围内，且在实时轨迹到达第一个关键节点之前，接收GPS点分发系统下发的所有轨迹点；在实时轨迹的起点在关键节点周围预设范围内的情况下，将关键节点周围第一预设范围内的轨迹点保留，并过滤其余轨迹点，得到第二轨迹。对于实时轨迹，若起点不在关键节点周围预设范围内，针对起点进行抽稀，后续在路径匹配时，无法通过路径集合确定起点和关键节点的唯一路径，因此，对起点与关键节点之间的所有轨迹点全部接收，不做抽稀。

可选的，第一轨迹为离线轨迹，离线轨迹包括起点和终点；

在离线轨迹的起点和/或终点不在关键节点周围预设范围内的情况下，确定离线轨迹为所述第二轨迹；在所离线轨迹的起点和终点在关键节点周围预设范围内的情况下，将关键节点周围第一预设范围内的轨迹点保留，并过滤第一轨迹上的其余轨迹点，得到第二轨迹；在离线轨迹的起点或终点在关键节点周围预设范围内，且起点和终点之间存在其余关键节点的情况下，将关键节点周围第一预设范围内的轨迹点保留，并过滤第一轨迹上的其余轨迹点，得到第二轨迹；在离线轨迹的起点或终点在关键节点周围预设范围内，且起点和终点之间不存在其余关键节点的情况下，确定离线轨迹为第二轨迹。对于离线轨迹，若起点和终点均不在关键节点周围预设范围内，或者起点不在关键节点周围预设范围内，或者终点不在关键节点周围预设范围内，针对起点、终点或者二者都进行抽稀，那么后续在路径匹配时，则无法通过路径集合确定起点和关键节点，以及关键节点和终点之间的唯一路径，因此，对起点与距离起点最近的关键节点(起点和终点之间的第一个关键节点)和/或终点与距离终点最近的关键节点(起点和终点之间的倒数第一个关键节点)之间的轨迹点全部接收，不做抽稀。

可选的，路径集合包括多个位置点，且相邻的两个位置点之间具有至少一条路径，每条路径的起点和终点之间包括至少一个关键节点；基于抽稀轨迹和预先建立的路径集合，确定第二轨迹的路径，包括：在路径集合中，对第二轨迹中相邻的两个轨迹点分别匹配相应的第一位置点和第二位置点；将第一位置点和第二位置点之间的路径，确定为第二轨迹中对应的两个轨迹点之间的路径；重复上述过程，得到第二轨迹的路径。本实施例通过在路径集合中直接获取路径，而不在地图的解空间中实时寻找路径，因此能够加快路径查询速度。

请参阅图8，地图匹配过程中，地图可以根据百度大厦周围保留的轨迹点A和关键节点周围保留的轨迹点B，确定百度大厦和关键节点之间的唯一路径，之后根据关键节点周围保留的轨迹点C和西二旗地铁站周围保留的轨迹点D确定关键节点和西二旗地铁站之间的唯一路径。

可选的，预先建立的路径集合按照如下方法建立：基于标志性建筑物，在地图中确定多个起点和多个终点；基于历史轨迹，确定各个起点和各个终点之间的关键路径，得到路径集合。例如，在地图中选取两个标志性POI建筑分别作为起点和终点，并基于起点和终点之间的大量历史轨迹，建立路径集合。路径集合中相同的起点和相同的终点之间包括预设数量的路径，可以理解为相同的起点和相同的终点之间存在预设数量条路线，相同的起点和相同的终点之间的预设数量条路线是基于大量历史轨迹筛选得到的很大概率会经过的路线。在确定了起点和终点之间的关键路线后，可以基于多个起点和多个终点之间的关键路线进行挖掘，得到至少一个关键节点，关键节点可以选取路口、变道口等路网中的交叉点。例如，用户在从百度大厦到西二旗地铁站会经过节点1，而百度大厦到回龙观医院也会经过节点1，则确定节点1为百度大厦到西二旗地铁站的关键节点，以及百度大厦到回龙观医院的关键节点。

请参阅图9，选取百度大厦和西二旗地铁站分别作为起点和终点，通过大量历史轨迹，确定百度大厦和西二旗地铁站之间的关键路线有2条，这2条关键路线请参见图9中百度大厦、关键节点1和西二旗地铁站之间的路线，以及百度大厦、关键节点2和西二旗地铁站之间的路线。

可选的，在对第一轨迹进行抽稀之前，本实施例的方法还包括：对第一轨迹进行预筛选。其中，对第一轨迹进行预筛选，包括：若第一轨迹不是车辆轨迹或者第一轨迹为稀疏轨迹，则不对第一轨迹进行抽稀处理。例如，若第一轨迹为货车的轨迹，货车轨迹可能几分钟或者几公里才会产生一个轨迹点，这种情况下，无法保证第一轨迹会经过关键节点，因此，对该种情况下货车的第一轨迹不做抽稀处理。

上述实施例中，实时轨迹将要到达的轨迹点或者关键节点可以理解为采集的实时轨迹的下一时刻的采样点。

根据本申请的实施例，本申请还提供了一种地图匹配的容灾装置。图10是本申请实施例提供的地图匹配的容灾装置的结构示意图。如图10所示，地图匹配的容灾装置100包括：抽稀模块101和路径确定模块102；其中，抽稀模块101，用于基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹；路径确定模块102，用于基于所述第二轨迹和预先建立的路径集合，确定所述第二轨迹的路径，以根据确定的第二轨迹的路径进行地图匹配，所述路径集合包括多条路径，每条所述路径包括多个关键节点。

可选的，所述抽稀模块101在基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹时，具体包括：将所述关键节点周围第一预设范围内的轨迹点保留，并过滤其余轨迹点，得到第二轨迹。

可选的，所述GPS点分发系统下发的第一轨迹中的每个轨迹点对应有标识信息，所述标识信息用于标识所述轨迹点是否位于关键节点周围第一预设范围内；所述抽稀模块101在将所述关键节点周围第一预设范围内的轨迹点保留，并过滤所述第一轨迹上的其余轨迹点，得到第二轨迹时，具体包括：在所述标识信息是所述轨迹点位于所述关键节点周围第一预设范围内的情况下，接收所述轨迹点；在所述标识信息是所述轨迹点位于所述关键节点周围第一预设范围之外的情况下，过滤所述轨迹点。

可选的，所述抽稀模块101在将所述关键节点周围第一预设范围内的轨迹点保留，并过滤所述第一轨迹上的其余轨迹点，得到第二轨迹时，具体包括：确定所述关键节点是否合法；在所述关键节点合法的情况下，确定所述关键节点周围第二预设范围内是否存在其他关键节点；在所述关键节点周围第二预设范围内不存在其他关键节点的情况下，将所述关键节点周围预设范围内的轨迹点保留，并过滤所述第一轨迹上的其余轨迹点，得到第二轨迹。

可选的，所述抽稀模块101在基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹时，具体包括：在预设时间内，调用所述第一轨迹超时的次数超过预设次数的情况下，基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀，得到第二轨迹。

可选的，所述第一轨迹为实时轨迹；所述抽稀模块101在基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀时，具体包括：在所述实时轨迹的起点不在所述关键节点周围预设范围内，且在所述实时轨迹到达第一个关键节点之前，接收所述GPS点分发系统下发的所有轨迹点；在所述实时轨迹的起点在所述关键节点周围预设范围内的情况下，将所述关键节点周围第一预设范围内的轨迹点保留，并过滤其余轨迹点，得到第二轨迹。

可选的，所述第一轨迹为离线轨迹，所述离线轨迹包括起点和终点；所述抽稀模块101在基于预先设定的关键节点对GPS点分发系统下发的第一轨迹进行抽稀时，具体包括：在所述离线轨迹的起点和/或终点不在关键节点周围预设范围内的情况下，确定所述离线轨迹为所述第二轨迹；在所述离线轨迹的起点和终点在关键节点周围预设范围内的情况下，将所述关键节点周围第一预设范围内的轨迹点保留，并过滤所述第一轨迹上的其余轨迹点，得到第二轨迹；在所述离线轨迹的起点或终点在关键节点周围预设范围内，且所述起点和终点之间存在其余关键节点的情况下，将所述关键节点周围第一预设范围内的轨迹点保留，并过滤所述第一轨迹上的其余轨迹点，得到第二轨迹；在所述离线轨迹的起点或终点在关键节点周围预设范围内，且所述起点和终点之间不存在其余关键节点的情况下，确定所述离线轨迹为所述第二轨迹。

可选的，所述路径集合包括多个位置点，且相邻的两个位置点之间具有至少一条路径，每条路径的起点和终点之间包括至少一个关键节点；所述路径确定模块102在基于所述抽稀轨迹和预先建立的路径集合，确定所述第二轨迹的路径时，具体包括：在所述路径集合中，对所述第二轨迹中相邻的两个轨迹点分别匹配相应的第一位置点和第二位置点；将所述第一位置点和所述第二位置点之间的路径，确定为所述第二轨迹中对应的两个轨迹点之间的路径；重复上述过程，得到所述第二轨迹的路径。

可选的，所述路径确定模块102按照如下方法建立所述路径集合：基于标志性建筑物，在所述地图中确定多个位置点；基于所述多个位置点之间的历史轨迹，确定所述多个位置点之间的路径，得到所述路径集合。

根据本申请的实施例，本申请还提供了一种电子设备和一种可读存储介质。

如图11所示，是根据本申请实施例的地图匹配的容灾方法提供的电子设备的框图。电子设备旨在表示各种形式的数字计算机，诸如，膝上型计算机、台式计算机、工作台、个人数字助理、服务器、刀片式服务器、大型计算机、和其它适合的计算机。电子设备还可以表示各种形式的移动装置，诸如，个人数字处理、蜂窝电话、智能电话、可穿戴设备和其它类似的计算装置。本文所示的部件、它们的连接和关系、以及它们的功能仅仅作为示例，并且不意在限制本文中描述的和/或者要求的本申请的实现。

如图11所示，该电子设备包括：一个或多个处理器1101、存储器1102，以及用于连接各部件的接口，包括高速接口和低速接口。各个部件利用不同的总线互相连接，并且可以被安装在公共主板上或者根据需要以其它方式安装。处理器可以对在电子设备内执行的指令进行处理，包括存储在存储器中或者存储器上以在外部输入/输出装置(诸如，耦合至接口的显示设备)上显示GUI的图形信息的指令。在其它实施方式中，若需要，可以将多个处理器和/或多条总线与多个存储器和多个存储器一起使用。同样，可以连接多个电子设备，各个设备提供部分必要的操作(例如，作为服务器阵列、一组刀片式服务器、或者多处理器系统)。图11中以一个处理器1101为例。

存储器1102即为本申请所提供的非瞬时计算机可读存储介质。其中，所述存储器存储有可由至少一个处理器执行的指令，以使所述至少一个处理器执行本申请所提供的地图匹配的容灾方法。本申请的非瞬时计算机可读存储介质存储计算机指令，该计算机指令用于使计算机执行本申请所提供的地图匹配的容灾方法。

存储器1102作为一种非瞬时计算机可读存储介质，可用于存储非瞬时软件程序、非瞬时计算机可执行程序以及模块，如本申请实施例中的地图匹配的容灾方法对应的程序指令/模块(例如，附图10所示的抽稀模块101、路径确定模块102)。处理器1101通过运行存储在存储器1102中的非瞬时软件程序、指令以及模块，从而执行服务器的各种功能应用以及数据处理，即实现上述方法实施例中的地图匹配的容灾方法。

存储器1102可以包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需要的应用程序；存储数据区可存储根据实现地图匹配的容灾方法的电子设备的使用所创建的数据等。此外，存储器1102可以包括高速随机存取存储器，还可以包括非瞬时存储器，例如至少一个磁盘存储器件、闪存器件、或其他非瞬时固态存储器件。在一些实施例中，存储器1102可选包括相对于处理器1101远程设置的存储器，这些远程存储器可以通过网络连接至实现地图匹配的容灾方法的电子设备。上述网络的实例包括但不限于互联网、企业内部网、区块链网络、局域网、移动通信网及其组合。

实现地图匹配的容灾方法的电子设备还可以包括：输入装置1103和输出装置1104。处理器1101、存储器1102、输入装置1103和输出装置1104可以通过总线或者其他方式连接，图11中以通过总线连接为例。

输入装置1103可接收输入的数字或字符信息，以及产生与实现地图匹配的容灾方法的电子设备的用户设置以及功能控制有关的键信号输入，例如触摸屏、小键盘、鼠标、轨迹板、触摸板、指示杆、一个或者多个鼠标按钮、轨迹球、操纵杆等输入装置。输出装置1104可以包括显示设备、辅助照明装置(例如，LED)和触觉反馈装置(例如，振动电机)等。该显示设备可以包括但不限于，液晶显示器(LCD)、发光二极管(LED)显示器和等离子体显示器。在一些实施方式中，显示设备可以是触摸屏。

此处描述的系统和技术的各种实施方式可以在数字电子电路系统、集成电路系统、专用ASIC(专用集成电路)、计算机硬件、固件、软件、和/或它们的组合中实现。这些各种实施方式可以包括：实施在一个或者多个计算机程序中，该一个或者多个计算机程序可在包括至少一个可编程处理器的可编程系统上执行和/或解释，该可编程处理器可以是专用或者通用可编程处理器，可以从存储系统、至少一个输入装置、和至少一个输出装置接收数据和指令，并且将数据和指令传输至该存储系统、该至少一个输入装置、和该至少一个输出装置。

这些计算程序(也称作程序、软件、软件应用、或者代码)包括可编程处理器的机器指令，并且可以利用高级过程和/或面向对象的编程语言、和/或汇编/机器语言来实施这些计算程序。如本文使用的，术语“机器可读介质”和“计算机可读介质”指的是用于将机器指令和/或数据提供给可编程处理器的任何计算机程序产品、设备、和/或装置(例如，磁盘、光盘、存储器、可编程逻辑装置(PLD))，包括，接收作为机器可读信号的机器指令的机器可读介质。术语“机器可读信号”指的是用于将机器指令和/或数据提供给可编程处理器的任何信号。

为了提供与用户的交互，可以在计算机上实施此处描述的系统和技术，该计算机具有：用于向用户显示信息的显示装置(例如，CRT(阴极射线管)或者LCD(液晶显示器)监视器)；以及键盘和指向装置(例如，鼠标或者轨迹球)，用户可以通过该键盘和该指向装置来将输入提供给计算机。其它种类的装置还可以用于提供与用户的交互；例如，提供给用户的反馈可以是任何形式的传感反馈(例如，视觉反馈、听觉反馈、或者触觉反馈)；并且可以用任何形式(包括声输入、语音输入或者、触觉输入)来接收来自用户的输入。

可以将此处描述的系统和技术实施在包括后台部件的计算系统(例如，作为数据服务器)、或者包括中间件部件的计算系统(例如，应用服务器)、或者包括前端部件的计算系统(例如，具有图形用户界面或者网络浏览器的用户计算机，用户可以通过该图形用户界面或者该网络浏览器来与此处描述的系统和技术的实施方式交互)、或者包括这种后台部件、中间件部件、或者前端部件的任何组合的计算系统中。可以通过任何形式或者介质的数字数据通信(例如，通信网络)来将系统的部件相互连接。通信网络的示例包括：局域网(LAN)、广域网(WAN)区块链网络和互联网。

计算机系统可以包括客户端和服务器。客户端和服务器一般远离彼此并且通常通过通信网络进行交互。通过在相应的计算机上运行并且彼此具有客户端-服务器关系的计算机程序来产生客户端和服务器的关系。

应该理解，可以使用上面所示的各种形式的流程，重新排序、增加或删除步骤。例如，本发申请中记载的各步骤可以并行地执行也可以顺序地执行也可以不同的次序执行，只要能够实现本申请公开的技术方案所期望的结果，本文在此不进行限制。

上述具体实施方式，并不构成对本申请保护范围的限制。本领域技术人员应该明白的是，根据设计要求和其他因素，可以进行各种修改、组合、子组合和替代。任何在本申请的精神和原则之内所作的修改、等同替换和改进等，均应包含在本申请保护范围之内。