亚星游戏官网-www.yaxin868.com

专利名称：压缩的导航地图数据的制作方法
技术领域：
本发明涉及用于从未压缩的导航地图数据产生压缩的导航地图数据的方法，涉及配置成产生压缩的导航地图数据的压缩模块，涉及用于向用户提供导航信息的方法以及涉及向用户提供导航信息的导航系统。
背景技术：
执行功能例如在两个位置之间的路线搜索的导航系统是已知的。现代导航系统也可提供额外的功能，例如用作在要求时输出关于名胜的信息的旅行指南，等等。一些导航系统甚至可包括旅行指南功能以输出详细的解释、m正文和/或多媒体形式。此外，显示车辆周围环境的三维视野变得普遍，其中除了道路以外，建筑物等也显示在三维形式中。三维表示应便于找到正确的路。给用户提供的不同类型的信息都存储在可移动数据存储单元例如CD ROM或DVD上，或信息在硬盘上被提供。在本上下文中，存在对最小化导航地图数据所需的存储空间的需要，导航地图数据包括用于通知用户所需的信息的不同类型的信息。

发明内容
因此，存在对提供允许有效地减小存储导航地图数据所需的存储空间的方法的需要。这个需要由独立权利要求的特征满足。在从属权利要求中，描述了另外的实施方案。根据本发明的第一方面，提供了用于从未压缩的导航地图数据产生压缩的导航地图数据库的方法。未压缩的导航数据包含导航数据的不同构造块，每个构造块处理导航数据的特定功能方面，且每个构造块包含数据的字节序列或串。为未压缩的导航地图数据的不同构造块确定包含在构造块中的最频繁的子串。此外，对于构造块，构造块的所确定的最频繁的子串存储在至少一个种子块中。此外，在构造块中，用对所述至少一个种子块的引用(reference)代替在串中的存储在所述至少一个种子块中的所确定的最频繁的子串，从而产生压缩块。此外，压缩块和所述至少一个种子块被存储，以便产生压缩的导航地图数据库。所有导航数据被视为属于构造块之一，每个构造块描述导航数据的预定功能方面，例如功能块是路线构造块、名称构造块。应理解，导航地图数据进一步分成不同的地理区，以及数据可另外划分成不同水平的细节。然而在本发明的上下文中，分成功能块被讨论，每个功能构造块描述在导航系统中使用的不同方面以向用户提供输出，例如驾驶推荐。作为例子，路线构造块提供路线选择计算的特征，名称构造块包含在地图上显示的街道的名称。在每个构造块中，数据存储在串中，且根据块的内容，串可以是街道名称或可提供图像的颜色信息。通过在构造块中确定存在于每个块中的最频繁的子串，可能组合所述至少一个种子块中的最频繁的子串，并在构造块中包括对所述至少一个种子块的来代替最频繁的子串。以这种方式，获得需要比未压缩的导航地图数据更小的存储容量的压缩块。从上文中很清楚，压缩程度取决于存储在种子块中的最频繁的子串的数量，以及哪些子串不再包含在压缩块中，但用对种子块的引用代替哪些子串。在一个实施方案中，可能多个构造块的最频繁的子串存储在一个种子块中。这意味着，两个或更多个构造块的最频繁的子串可包含在一个种子块中。在另一实施方案中，然而可能为每个构造块确定包含最频繁的子串的种子块。在该实施方案中，对于每个构造块，种子块和压缩块存在，而在该实施方案中，对于每个构造块，压缩块存在，但不一定对于每个压缩块都有一个种子块。此外，可能每个构造块在压缩之前分成几个部分，其中为构造块的每个部分确定最频繁的子串。构造块的不同部分的最频繁的子串可接着存储在单个种子块中。优选地，代替的引用包含偏移信息和长度信息，偏移信息指示所代替的最频繁的子串位于种子块中什么地方。长度信息提供关于所代替的最频繁的子串的长度的信息。当压缩的导航地图数据应再次由导航系统使用时，对偏移信息和长度信息的引用可能是必要的。为了产生完整的信息，用存储在种子块中的最频繁的子串再次代替引用。对于该代替，在相应的代替的最频繁的子串存储在种子块中的地方使用该信息。此外，代替的最频繁的子串多长的信息被使用。确定块的最频繁的子串的一个可能性是产生包含在块中的串的前缀树以及确定前缀树中的最频繁的子串。在前缀树中，在树中的串的位置定义它所相关的串。节点的所有后代具有与该节点相关的串的共同前缀。当频率值与每个节点相关时，确定块的最频繁的子串无疑是可能的。未压缩的导航地图数据可包含不同的块、路线构造块、名称构造块、交通信息构造块、3D物体构造块、枢纽站视野构造块或数字地形构造块。本发明此外涉及配置成产生压缩的导航地图数据的压缩模块，该模块包括包含未压缩的导航地图数据的第一数据库，未压缩的导航地图数据包含导航数据的不同的构造块，每个构造块处理导航地图数据的特定功能方面，且每个块包含数据的串。此外，提供在压缩模块中的第二数据库和配置成确定如上提到的压缩块和所述至少一个种子块的处理单元。本发明此外涉及向用户提供导航信息的导航系统，导航系统包括包含压缩的导航地图数据的存储单元，压缩的导航地图数据包含导航地图数据的不同构造块，且每个构造块处理导航地图数据的特定功能方面。压缩的导航数据包含至少一个种子块和压缩块，所述至少一个种子块包含压缩块的最频繁的子串，其中在压缩块中，用对所述至少一个种子块的引用代替存储在所述至少一个种子块中的所确定的最频繁的子串。此外，导航系统包括向用户提供导航信息的信息单元。作为例子，导航信息可以是2D或3D的视觉输出。导航系统此外包括配置成从压缩的导航地图数据产生未压缩的导航地图数据的解压缩单元。解压缩单元对于每个构造块访问压缩块和所述至少一个种子块，并用所述至少一个种子块的相应的最频繁的子串代替包含在压缩块中的引用，以便产生未压缩的导航地图数据。解压缩单元此外配置成基于未压缩的导航地图数据产生导航信息，信息单元使用未压缩的导航地图数据来向用户提供导航信息。
在一个实施方案中，对于解压缩，种子块用作压缩和解压缩的虚拟前缀，以简化压缩和解压缩算法。自然地，在没有每个块的种子块的情况下，解压缩不是可能的。这也提供导航地图数据的轻量级加密，如果种子块与压缩块分开地被存储，因为当没有为压缩块提供种子块时导航地图数据的使用不是可能的。本发明此外提供了用于向用户提供导航信息的方法，其中未压缩的导航地图数据从压缩的导航数据产生，其中通过访问压缩块和所述至少一个种子块并通过用存储在所述至少一个种子块中的相应的最频繁的子串代替包含在压缩块中的引用来为每个块产生未压缩的导航数据。用户的导航信息接着基于未压缩的导航地图数据而产生，且导航信息基于未压缩的导航地图数据提供给用户。


当结合附图阅读时，从实施方案的下面的详细描述中，前述和其它特征和实施方案将变得更明显。在附图中，图1是配置成产生压缩的导航地图数据的压缩模块的示意图，图2是包含为了产生压缩的地图导航数据而执行的步骤的流程图，图3是使用以图1的系统产生的压缩的导航地图数据的导航系统的示意图，以及图4是包括为了在使用之前对压缩的导航地图数据解压缩而执行的步骤的流程图。
具体实施例方式在图1中，示出了能够从未压缩的导航地图数据产生压缩的导航地图数据的压缩模块的示意图。压缩模块包括第一数据库110，其中数据111的不同块存储在第一数据库110中。存储在数据库110中的地图数据覆盖某个地理区域。此外，导航地图数据可例如通过将地理区域分成瓦片来分成不同的地理区。在图1所示的实施方案中，所示的实施方案并不反映分成不同的地理区。在所示实施方案中，考虑到地图数据的功能方面来执行导航地图数据的划分。作为例子，图1所示的第一个块可以是路线选择构造块，路线选择块将用于路线选择应用的地图数据的特征聚集在一起。路线选择构造块可包含将用于计算路线的道路网络的表示。图1所示的第二个构造块可以是向地图上示出的不同物体特别提供名称的名称构造块。图1所示的构造块3可以是将地图显示应用的特征聚集在一起的地图显示构造块。它可包含提供二维地图以及其几何数据所必需的特征。应理解，可在数据库110中提供更多的构造块，例如交通信息构造块、PoI (名胜)构造块、语音构造块、3D物体构造块等。处理单元110访问第一数据库并处理块111中的每个，使得它预先计算包含在每个块中的最频繁的子串。存储在块中的信息条是串。处理单元将识别在每个块中的多个最频繁的子串。块的最频繁的子串的数量可取决于包含在每个块中的串的数量和数据的类型，该数量例如在100和大约5000之间变化。可通过为每个块产生前缀树并通过识别在这个前缀树中的最频繁的子串来确定最频繁的子串。在本上下文中，子串是串的子单元。在名称构造块中，最频繁的子串可包含以不同的名称出现的最频繁的字符序列。最多的子串被识别为将被代替的最频繁的子串，压缩率将更高。处理单元100现在将用对块指定的种子块的引用代替出现在不同的块111中的所确定的最频繁的子串，所确定的最频繁的子串存储在该种子块中。具有最频繁的子串的这个种子块可起待压缩的数据的(虚拟)前缀的作用。处理单元将压缩的数据存储在第二数据库中。如图1所示，为块111产生包括块I的最频繁的子串的种子块121a以及压缩块122a，在压缩块122a中，用对种子块121a的引用代替包含在种子块121a中的最频繁的子串。该引用此外包含指示省略的子串存储在种子块内的哪个位置的偏移信息。此外，该引用包含指示所代替的子串的长度的长度信息。此外，为数据库110的块2产生种子块121b和压缩块122b。种子块121c包括块3的最频繁的子串，且压缩块122c包括其它未代替的串以及对种子块的引用。在所示实施方案中，为包含在第一存储单元110中的构造块中的每个构造块产生压缩的导航地图数据。然而，应理解，不一定为包含在数据库110中的每个块都产生压缩块和种子块。作为例子，如果数据库110的块111之一与其它块比较在尺寸上小得多，则这样的块的压缩可被省略。在图1所示的实施方案中，为每个构造块产生一个种子块。然而，也可能两个或更多个构造块的最频繁的子串存储在单个种子块中，在该实施方案中，一个种子块例如种子块121a将包括压缩块I和压缩块2的最频繁的子串。此外，可能块111在压缩之前分成不同的部分，其中为构造块的不同部分中的每个确定最频繁的子串，以便为每个压缩块产生压缩部分例如图1中的部分125、126和127。在该实施方案中，不同的压缩部分125-127的最频繁的子串存储在一个种子块中。在不同的压缩部分中的压缩块的划分可与多于一个的构造块的最频繁的子串存储在单个种子块中的实施方案组合。因此，在该实施方案中，压缩块I的压缩部分和例如压缩块2的压缩部分将存储在单个种子块中。然而，也可能为包含压缩部分的每个压缩块产生种子块。在图2中，概述了为了产生压缩的导航地图数据而执行的步骤。方法在步骤20中开始，且在步骤21中，为包含在块中的串确定最频繁的子串。在下一步骤22中，在步骤21中确定的最频繁的子串在种子块中被存储并聚集在一起。此外，当将被存储在种子块中的子串的数量被确定时，用对种子块的引用代替在块中的三个子串(步骤23)。在步骤24中，接着存储种子块和压缩块。该方法在步骤25结束。在图1所示的实施方案中，第一数据库110和第二数据库120被示为单独的实体。应理解，第一数据库和第二数据库可由单个物理存储单元表示，使得未压缩块111存储在与相应的压缩数据相同的物理存储单元上。存储在存储块120中的压缩的导航地图数据可由图3所示的导航系统使用。图3所示的导航系统300包括存储单元310，具有种子块121和相应的压缩块122的压缩的导航地图数据存储在存储单元310中。存储在数据库310中的数据相应于存储在图1的数据库120中的数据。数据库310可包括各种存储器或存储介质的任一个或任何组合，例如随机存取存储器、闪存或硬盘，但也可以是可移动存储器，例如光盘、DVD、存储卡等。导航系统此外包括配置成计算从第一位置到第二位置的最快或最短路线的路线计算单元320。用户可经由输入单元330控制导航系统的运行。输入单元可包括触觉设备，例如可被压下或旋转的按钮。输入单元此外可包含允许使用语音命令控制导航系统的运行的语音识别模块。由路线计算单元计算的信息可显示在显示器340上。此外，也可使用话音命令来输出驾驶推荐。可提供接收卫星信号的天线350，其中用于计算导航系统的位置的信号被接收。导航系统如何计算从规定的位置到期望目的地的方法在本领域中是已知的，且将不被详细描述。为了清楚起见，只示出导航系统的对本发明的理解有帮助的部件。应理解，导航系统可包含不同的模块和没有在图3的示意图中示出的另外的特征。 此外，不同的模块可通过软件或硬件或通过软件和硬件的组合来合并。导航系统还包括解压缩单元，其在存储在数据库310中的导航数据可由路线计算单元使用之前或在它们可显示在显示器340上之前对它们进行解压缩。解压缩单元用存储在相应的种子块121a、121b中的子串代替压缩块122a、122b中的引用。换句话说，对于解压缩，种子块或子串块用作压缩的数据块的虚拟前缀，当它与种子块一起被存储为虚拟前缀时。如也可从上文看到的，导航地图数据的解压缩在没有种子块的情况下是不可能的。这意味着对于不同的功能块，种子块和压缩块的使用提供对数据的加密，因为导航数据不能在没有相应的种子块的情况下被使用。当解压缩单元350通过用相应的子串代替所有引用来对块解压缩时，未压缩的导航地图数据可接着由路线计算单元和导航系统的其它模块使用。当种子块与压缩块分开地被存储时，第一加密被获得。此外，可能存储该种子块或多个种子块以及压缩块，并使用已知的加密方法例如AES (高级加密标准)或RSA (RivestShamir和Adleman Encryption)来对种子块进行加密。在图4中，概述了用于解压缩的不同步骤。方法在步骤40中开始，且在步骤41中，访问种子块，以及在步骤42中，访问压缩块。在每个压缩块中，在相应的种子块中识别由引用代替的子串，且将所代替的子串再次引入压缩块中，以便产生未压缩块(步骤43)。基于未压缩的导航地图数据，将被输出给用户的导航信息可在步骤44中产生。该方法在步骤45如可从上文中看到的，本发明提供导航地图数据的有效压缩。同时，压缩方法提供数据的加密，因为导航地图数据不能在没有相应的种子块的情况下被使用。为了改进加密，此外可使用已知的加密方法来加密在种子块中提供的信息。
权利要求
1.一种用于从未压缩的导航地图数据产生压缩的导航地图数据库的方法，所述未压缩的导航地图数据包含导航数据的不同构造块(111)，每个构造块处理所述导航数据的特定功能方面，且每个块包含数据串，所述方法包括下列步骤 -为所述未压缩的导航地图数据的构造块确定包含在所述构造块中的最频繁的子串， -对于所述构造块，将所述确定的最频繁的子串存储在至少一个种子块(121)中， -在所述构造块中，用对所述至少一个种子块的引用代替在所述串中的存储在所述至少一个种子块(121)中的所述确定的最频繁的子串，从而为每个构造块产生压缩块(122)， -存储所述压缩块(122)和所述至少一个种子块(121 )，以便产生所述压缩的导航地图数据库。
2.如权利要求1所述的方法，其中所述代替的引用包含偏移信息和长度信息，所述偏移信息指示所述代替的最频繁的子串位于所述种子块中什么地方，所述长度信息指示所述代替的最频繁的子串的长度。
3.如权利要求1或2所述的方法，其中通过确定块的前缀树并通过确定所述前缀树中的最频繁的子串来产生所述块的所述最频繁的子串。
4.如前述权利要求中任一项所述的方法，其中所述未压缩的导航地图数据包含下列块中的至少一个路线构造块、名称构造块、交通信息构造块、3d物体构造块、枢纽站视野构造块或数字地形构造块。
5.如前述权利要求中任一项所述的方法，其中多个构造块的所述最频繁的子串存储在一个种子块中。
6.如权利要求1至4中任一项所述的方法，其中为每个构造块确定包含所述最频繁的子串的种子块。
7.如前述权利要求中任一项所述的方法，其中每个构造块在压缩之前分成几个部分，其中为构造块的每个部分确定所述最频繁的子串，构造块的所述不同部分的所述最频繁的子串存储在一个种子块中。
8.一种配置成产生压缩的导航地图数据库的压缩模块，所述模块包括 -第一数据库(110)，其包含未压缩的导航地图数据，所述未压缩的导航地图数据包含导航数据的不同的构造块(111)，每个构造块处理导航地图数据的特定功能方面，每个构造块包含数据串， -第二数据库(120)， -处理单元(100)，其配置成为所述未压缩的导航地图数据的所述构造块(111)确定所述构造块的最频繁的子串，配置成对于所述构造块将所述构造块的所述确定的最频繁的子串存储在至少一个种子块(121)中，配置成对于所述构造块用对所述至少一个种子块(121)的引用代替在所述串中的存储在所述至少一个种子块中的所述确定的最频繁的子串，从而为每个构造块产生压缩块(122)，并配置成将压缩块(122)和所述至少一个种子块(121)存储在所述第二数据库(122)中，以便产生所述压缩的导航地图数据库。
9.如权利要求8所述的压缩模块，其中所述处理单元(100)配置成在所述代替的引用中包括偏移信息和长度信息，所述偏移信息指示所述代替的最频繁的子串位于所述种子块中什么地方，所述长度信息指示所述代替的最频繁的子串的长度。
10.如权利要求8或9所述的压缩模块，其中所述处理单元(100)配置成通过产生块的前缀树并通过确定所述前缀树中的所述最频繁的子串来确定所述块的所述最频繁的子串。
11.一种向用户提供导航信息的导航系统(300)，所述系统包括 -存储单元(310)，其包含压缩的导航地图数据的导航地图数据库，所述压缩的导航数据包含导航数据的不同构造块，每个构造块处理所述导航数据的特定功能方面，每个构造块包含数据串，所述地图数据库包含至少一个种子块(121)和压缩块(122)，所述种子块(121)包含至少一个构造块的所述最频繁的子串，其中在所述压缩块(122)中，用对所述至少一个种子块的引用代替存储在所述至少一个种子块(121)中的所述确定的最频繁的子串， -信息单元(340)，其向所述用户提供所述导航信息， -解压缩单元(350)，其配置成从所述压缩的导航地图数据产生未压缩的导航地图数据，其中所述解压缩单元(350)配置成访问所述压缩块(122)和所述至少一个种子块(121)，用存储在所述至少一个种子块(121)中的所述相应的最频繁的子串代替包含在所述压缩块(122)中的引用，以便产生所述未压缩的导航地图数据，并配置成基于所述未压缩的导航地图数据产生所述导航信息，其中所述信息单元(340)使用所述未压缩的导航地图数据来向所述用户提供所述导航信息。
12.—种向用户提供导航信息的方法，所述方法包括下列步骤 -从压缩的导航地图数据产生未压缩的导航地图数据，所述压缩的导航地图数据包含导航地图数据的不同构造块，每个构造块处理所述导航地图数据的特定功能方面，每个构造块包含数据串，所述压缩的导航数据包含至少一个种子块(121)和所述压缩块(122)，所述至少一个种子块(121)包含所述构造块的所述最频繁的子串，其中在所述压缩块(122)中，用对所述至少一个种子块(121)的引用代替存储在所述至少一个种子块中的所述确定的最频繁的子串，其中通过访问所述压缩块(122)和所述至少一个种子块(121)并通过用存储在所述至少一个种子块中的所述相应的最频繁的子串代替包含在所述压缩块中的引用来产生所述未压缩的导航数据，以便产生所述未压缩的导航地图数据， -基于所述未压缩的导航地图数据产生所述导航信息，并基于所述未压缩的导航地图数据向所述用户提供所述导航信息。
全文摘要
本发明涉及用于从未压缩的导航地图数据产生压缩的导航地图数据库的方法，所述未压缩的导航地图数据包含导航数据的不同构造块，每个构造块处理所述导航数据的特定功能方面，每个块包含数据串，所述方法包括下列步骤-为所述未压缩的导航地图数据的每个块确定该块的最频繁的子串，-对于每个块，将所述确定的该块的最频繁的子串存储在种子块中，-对于每个块，用对所述种子块的引用代替在所述串中的存储在所述种子块中的所述确定的最频繁的子串，从而为每个块产生压缩块，-为每个块存储所述压缩块和所述种子块，以便产生所述压缩的导航地图数据库。
文档编号G01C21/32GK103047988SQ20121038910
公开日2013年4月17日 申请日期2012年10月15日 优先权日2011年10月14日
发明者P.库纳思, M.海特曼, S.巴普蒂斯特, Cc.斯平德勒, S.米特拉基斯 申请人:哈曼贝克自动系统股份有限公司