Kraftfahrzeug

Die Erfindung betrifft ein Verfahren zum Durchführen einer Suche nach möglichen Zielen mittels eines Navigationssystems eines Kraftfahrzeugs. Die Erfindung betrifft außerdem ein Navigationssystem sowie ein Kraftfahrzeug mit einem Navigationssystem, wobei das Navigationssystem zum Durchführen eines solchen Verfahrens ausgebildet ist.

Navigationssysteme für Kraftfahrzeuge sind bereits Stand der Technik und dienen zur Ausgabe von Navigationshinweisen, welche den Fahrer beim Führen des Kraftfahrzeugs zu einem bestimmten Zielort unterstützen. Vorliegend richtet sich das Interesse auf die Durchführung einer Suche nach möglichen Navigationszielen in einer

Navigationsdatenbank eines Navigationssystems. In diesem Zusammenhang ist es beispielsweise bereits bekannt, dass das gewünschte Navigationsziel über eine hierarchische Zieleingabe gefunden werden kann. Hierbei muss der Benutzer zunächst das Land sowie die gewünschte Stadt oder aber die Postleitzahl eingeben, um dann konkreter die gewünschte Straße und die Hausnummer definieren zu können. Des Weiteren sind auch Navigationssysteme bekannt, bei denen mittels einer sogenannten Voiltextsuche das Auffinden von Navigationszielen anhand einer möglichst eindeutigen Zeichenkette möglich ist. Eine solche Voiltextsuche ist besonders benutzerfreundlich und ermöglicht das Auffinden des gewünschten Ziels mit lediglich einer einzigen Zieleingabe.

Aus der Druckschrift DE 10 2006 057 921 A1 ist ein Navigationssystem bekannt, bei welchem ausgehend von einer vom Benutzer eingegebenen Buchstabenkombination eine Liste von möglichen Navigationszielen vorgeschlagen wird. Nach jeder Eingabe eines Zeichens oder einer Zeichengruppe wird bereits eine Suche in einer Datenbank auf Grundlage der von dem Benutzer bislang eingegebenen Teileingabe durchgeführt. Eine für diese Suche bereitgestellte Sucheinheit kann eine Freitextsuche oder eine

Voiltextsuche in der Datenbank auf Grundlage eines Volltextindexes durchführen. Die Suche kann auf Navigationsziele beschränkt werden, die sich in einem vorbestimmten Radius um die aktuelle Position des Navigationsgeräts befinden.

Das Dokument DE 10 2010 005 502 A1 beschreibt ein Verfahren zum Durchführen einer Suche in einem Infotainmentsystem eines Kraftfahrzeugs, wobei das Infotainmentsystem eine Mehrzahl von Funktionalitäten aufweist, die durch Betätigen eines der jeweiligen Funktionalität zugeordneten Festfunktions-Bedienelements aufgerufen werden können. Aufgrund einer alphanumerischen Eingabe eines Benutzers wird nach Ordnern, Dateien oder Dateiinhalten in einem vorbestimmten Suchfeld gesucht, und die Suchergebnisse werden zu diesem vorbestimmten Suchfeld auf einer Anzeigeeinrichtung angezeigt. Wird dann die Betätigung eines Festfunktions-Bedienelements erfasst, so erfolgt eine

Änderung des Suchfelds aufgrund der Betätigung, und es werden neue Suchergebnisse zu diesem neuen Suchfe!d angezeigt.

Ein Verfahren zur Durchführung einer Volltextsuche in einer Datenbank eines

Navigationssystems ist des Weiteren aus der EP 2 354 984 A1 bekannt. Um die

Volltextsuche aufwandsärmer gestalten zu können, werden mehrere Indextabellen verwendet, die über eine übergeordnete Tabelle miteinander verknüpft sind. Ein einzelner Datenbankeintrag kann hier neben den eigentlichen, eindeutigen Objektbezeichnungen für Navigationsziele auch Kategoriedaten beinhalten, die beispielsweise angeben, dass ein bestimmtes Navigationsziel ein Restaurant ist.

An den bekannten Navigationssystemen ist als nachteilig der Umstand anzusehen, dass die Datenbanken der Navigationssysteme relativ komplex aufgebaut und somit verhältnismäßig groß sind. Dies bewirkt wiederum, dass das Durchführen der Suche insgesamt recht lange dauern kann, weil jeweils die gesamte Datenbank in aufwendiger Weise nach dem gewünschten Ziel durchsucht werden muss. Außerdem wird für die Bearbeitung der großen Navigationsdatenbank ein entsprechend großer Arbeitsspeicher benötigt, in welchen die Datenbank während der Suche geladen werden muss. Solche Arbeitsspeicher stehen jedoch insbesondere bei Kraftfahrzeugen nur bedingt zur

Verfügung.

Es ist Aufgabe der Erfindung, einen Weg aufzuzeigen, wie bei einem Verfahren der eingangs genannten Gattung der Rechen- und/oder Datenaufwand während der Suche nach den möglichen Zielen im Vergleich zum Stand der Technik reduziert werden kann.

Diese Aufgabe wird erfindungsgemäß durch ein Verfahren, durch ein Navigationssystem sowie durch ein Kraftfahrzeug mit den Merkmalen gemäß den jeweiligen unabhängigen Patentansprüchen gelöst. Vorteilhafte Ausführungen der Erfindung sind Gegenstand der abhängigen Patentansprüche, der Beschreibung und der Figuren. Ein erfindungsgemäßes Verfahren dient zum Betreiben eines Navigationssystems eines Kraftfahrzeugs für eine Suche nach möglichen Zielen. Das Navigationssystem beinhaltet eine erste sowie eine zweite Datenbank, in der ersten Datenbank sind Datenbankeinträge gespeichert, die geografische Regionen bzw. Gebiete angeben. Demgegenüber sind in der zweiten Datenbank Datenbankeinträge gespeichert, weiche Straßennamen und/oder Sonderziele angeben, wobei in der zweiten Datenbank zusätzlich zu jedem

Straßennamen und/oder Sonderziel ein Verweis auf zumindest eine geografische Region aus der ersten Datenbank angegeben ist. Mittels einer Recheneinrichtung des

Navigationssystems wird eine Sucheingabe empfangen, die ein Benutzer bei einer Eingabeeinrichtung vornimmt. Dann wird mittels der Recheneinrichtung die erste

Datenbank in Abhängigkeit von der Sucheingabe nach passenden Datenbankeinträgen durchsucht und hierbei eine erste Ergebnisliste von passenden Datenbankeinträgen bereitgestellt. Unabhängig davon wird in Abhängigkeit von derselben Sucheingabe auch die zweite Datenbank nach passenden Datenbankeinträgen durchsucht, und hierbei wird eine zweite Ergebnisliste von passenden Datenbankeinträgen bereitgestellt. Dann erfolgt eine Zuordnung der Datenbankeinträge aus der zweiten Ergebnisliste zu den

Datenbankeinträgen aus der ersten Ergebnisliste anhand der Verweise: Die

Datenbankeinträge aus der zweiten Ergebnisliste werden jeweils zu demjenigen

Datenbankeintrag aus der ersten Ergebnisliste zugeordnet, auf den der jeweilige Verweis zeigt. Es werden somit Eintragspaare bestimmt, die jeweils einen Datenbankeintrag aus der ersten Ergebnisliste und einen Datenbankeintrag aus der zweiten Ergebnisliste beinhalten. Dann wird auf einer Anzeigeeinrichtung eine die Eintragspaare als die möglichen Ziele umfassende Auswahlliste angezeigt, so dass der Benutzer eines der angezeigten Ziele auswählen kann. Wird ein bestimmtes Ziel ausgewählt, berechnet die Recheneinrichtung eine entsprechende Navigationsroute, über welche das Kraftfahrzeug zu dem ausgewählten Ziel geführt werden kann.

Erfindungsgemäß wird somit vorgeschlagen, das Navigationssystem so auszugestalten, dass die Daten in zwei verschiedenen Datenbanken geordnet sind, und zwar derart, dass in der ersten Datenbank lediglich geografische Regionen in Form einer Liste abgelegt sind, während in der zweiten Datenbank die eindeutigen, konkreten Straßennamen und/oder Sonderziele jeweils mit einem Verweis auf zumindest eine geografische Region abgelegt sind, zu welcher die jeweilige Straße beziehungsweise das jeweilige Sonderziel geografisch gehört. Durch eine solche Datenstruktur wird insgesamt ein Suchindex geschaffen, bei welchem die jeweilige Datenbank mittels einer linearen Suche durchsucht werden kann, so dass die Suche nach den möglichen Zielen mit einer Laufzeitkomplexität von O(n) durchgeführt werden kann. Einerseits ist somit der zeitliche Aufwand im Vergleich zu anderen Datenbankstrukturen deutlich reduziert; andererseits ist auch die Größe der beiden Datenbanken reiativ gering. Entsprechend wird in dem Kraftfahrzeug kein großer Arbeitsspeicher benötigt.

Mittels der Recheneinrichtung wird also abhängig von der Sucheingabe einerseits eine erste Ergebnisliste mit Datenbankeinträgen aus der ersten Datenbank sowie andererseits eine zweite Ergebnisliste mit Datenbankeinträgen aus der zweiten Datenbank generiert. Dann erfolgt ein„Matching" der gefundenen Straßennamen und/oder Sonderziele zu den gefundenen geografischen Regionen anhand der jeweiligen Verweise. Wird dabei festgestellt, dass der Verweis einer gefundenen Straße und/oder eines Sonderzieis auf eine Region zeigt, welche nicht in der Ergebnisliste enthalten ist, so können diese Datenbankeinträge verworfen werden.

Das erfindungsgemäße Verfahren kann anhand des folgenden Beispiels veranschaulicht werden: Von dem Benutzer werden als Sucheingabe die beiden Begriffe„München Hanau" eingegeben. Die Recheneinrichtung durchsucht nun die erste Datenbank und findet als geografische Regionen sowohl die Stadt„München" als auch die Stadt„Hanau". Die erste Ergebnisliste beinhaltet somit die beiden Städte:„München" sowie„Hanau". Die Recheneinrichtung durchsucht auch die zweite Datenbank und findet dort die„Münchener Straße" sowie die„Hanauer Straße". Die zweite Ergebnisliste beinhaltet somit die beiden Straßen: die„Münchener Straße" sowie die„Hanauer Straße". Bei einer Zuordnung stellt die Recheneinrichtung fest, dass bei der„Hanauer Straße" ein Verweis auf die Stadt „München" gegeben ist, während es bei der„Münchener Straße" keinen solchen Verweis auf die Stadt„Hanau" gibt. Ein einziges mögliches Eintragspaar aus diesen beiden Ergebnislisten ist somit:„Hanauer Straße in München". Dieses Ziel wird dann auf der Anzeigeeinrichtung angezeigt.

Die Datenbankeinträge der zweiten Datenbank können zusätzlich jeweils eine Referenz in eine Navigationskarte beinhalten, um dann einzelne Ziele letztendlich geographisch auflösen zu können. Alternativ können die Datenbankeinträge der zweiten Datenbank auch aus der Navigationskarte referenziert werden, sofern das Datenformat der

Navigationskarte dies zulässt bzw. vorsieht.

!n einer Ausführungsform ist vorgesehen, dass in der zweiten Datenbank die

Datenbankeinträge - das heißt die Straßennamen und/oder die Sonderziele - alphabetisch geordnet abgelegt sind. Bei einer linearen Suche kann somit die für die Suche benötigte Zeit auf ein Minimum reduziert werden. Es erweist sich als vorteilhaft, wenn die in der ersten Datenbank angegebenen geografischen Regionen hierarchisch in zumindest zwei Hierarchiestufen geordnet sind, so dass zu jeder Region einer bestimmten Hierarchiestufe eine Mehrzahl von zu dieser Region geografisch gehörigen Regionen einer dazu untergeordneten Hierarchiestufe zugeordnet sind. Die hierarchische Struktur kann beispielsweise entsprechend einer staatlichen Verwaltungsgliederung aufgebaut sein, welche die in den unterschiedlichen Staaten jeweils bestehenden vertikalen administrativen Strukturen bezeichnet. Es können dabei zum Beispiel insgesamt zehn verschiedene Hierarchiestufen vorgesehen sein. Eine erste Hierarchiestufe - eine Hauptstufe - kann beispielsweise die Staaten beinhalten, also beispielsweise„Deutschland",„Frankreich",„Österreich" und dergleichen. Die Staaten wiederum können in Bundesländer unterteilt sein, die dann eine zweite

Hierarchiestufe bilden. Die Bundesländer können dann die jeweiligen weiteren

Verwaltungseinheiten als dritte Hierarchiestufe beinhalten, und so weiter.

Hinsichtlich der benötigten Suchzeit hat es sich als vorteilhaft erwiesen, wenn die in der ersten Datenbank angegebenen geografischen Regionen entsprechend einer

Baumstruktur in einer solchen Reihenfolge abgelegt sind, dass unmittelbar nach einer bestimmten Region alle zu dieser Region gehörigen untergeordneten Regionen folgen. Auf diese Art und Weise können die zu einer bestimmten Region untergeordneten Regionen besonders schnell in der Datenbank aufgefunden werden. Die Regionen innerhalb derselben Hierarchiestufe sind dabei vorzugsweise alphabetisch geordnet.

Wird abhängig von der Sucheingabe des Nutzers eine Region aus einer bestimmten Hierarchiestufe gefunden, so werden in die erste Ergebnisliste vorzugsweise zusätzlich noch alle dieser Region untergeordneten Regionen aufgenommen. Wird anhand der Sucheingabe beispielsweise die Region„Bad Tölz" gefunden, so werden in die erste Ergebnisliste auch die untergeordneten Regionen„Bad Tölz Mitte",„Bad Tölz Süd" sowie „Bad Tölz Ost" aufgenommen. Auf diese Art und Weise wird eine sehr präzise und einfache Zuordnung der gefundenen Straßennamen und/oder Sonderziele zu der entsprechenden Region ermöglicht. Beispielsweise kann dabei auch vorgesehen sein, dass die genannten Verweise, die in der zweiten Datenbank angegeben sind, auf die kleinste Region - das heißt auf die Region aus der letzten Hierarchiestufe - zeigen, in welcher sich die jeweilige Straße und/oder das jeweilige Sonderziel befindet.

Ergänzend oder alternativ kann auch vorgesehen sein, dass, falls abhängig von der Sucheingabe eine bestimmte Region sowie eine dazu untergeordnete Region gefunden werden, in die erste Ergebnisliste ausschließlich die untergeordnete Region aufgenommen wird. Somit wird die Rechenzeit bei der Suche weiterhin reduziert. Wird beispielsweise die Sucheingabe„Bad Tölz Mitte" empfangen, so wird in die erste

Ergebnisliste ausschließlich die Region„Bad Tölz Mitte" aufgenommen, nicht jedoch die übergeordnete Region„Bad Tölz".

In einer bevorzugten Ausführungsform sind die erste und/oder die zweite Datenbank komprimiert, insbesondere delta-komprimiert, in einem Datenspeicher abgelegt. Somit wird der benötigte Speicherplatz auf ein Minimum reduziert. Diese Ausführungsform erweist sich insbesondere in Bezug auf die zweite Datenbank als besonders vorteilhaft, in weicher die Straßennamen und/oder die Sonderziele abgelegt sind. Die zweite Datenbank beinhaltet nämlich deutlich mehr Datenbankeinträge als die erste Datenbank, so dass durch die Komprimierung der zweiten Datenbank insgesamt viel Speicherplatz gespart werden kann. Eine Delta-Komprimierung kann beispielsweise so aussehen, dass bei jedem Datenbankeintrag zunächst eine Zahl definiert wird, welche angibt, wie viele Anfangsbuchstaben aus dem unmittelbar vorherigen Datenbankeintrag übernommen werden sollen. Werden beispielsweise die folgenden beiden Datenbankeinträge „Aachener Straße" sowie .Aachener Weg" komprimiert abgelegt, so kann der zweite Datenbankeintrag folgendermaßen gespeichert werden:„9 Weg". Dies bedeutet, dass die ersten neun Buchstaben des zweiten Datenbankeintrags von dem vorherigen Eintrag übernommen werden.

Es kann vorgesehen sein, dass die erste und/oder die zweite Datenbank in eine Mehrzahl von Teildatenbanken unterteilt ist, in denen jeweils eine Untermenge der

Datenbankeinträge abgelegt ist. Jede Teildatenbank kann dabei jeweils in Form einer separaten Datei bereitgestellt sein, welche in einem Datenspeicher abgelegt ist. Die Unterteilung der ersten und/oder zweiten Datenbank in mehrere Teildatenbanken hat den Vorteil, dass die Recheneinrichtung die einzelnen Teildatenbanken bei der Durchführung der Suche dynamisch nachladen kann, so dass sich insgesamt eine verbesserte

Speicherauslastung ergibt. Es wird somit auch ein kleinerer Arbeitsspeicher benötigt, und die Suchzeit wird weiterhin reduziert. Das Vorsehen mehrerer Teildatenbanken hat auch Vorteile hinsichtlich der Aktualisierung beziehungsweise„Updates" der Datenbank. Es können dabei lediglich partielle Updates vorgenommen werden, so dass nicht die gesamte Datenbank aktualisiert zu werden braucht. Die Unterteilung in mehrere

Teiidatenbanken kann beispielsweise für größere geografische Gebiete vorgenommen werden, wie beispielsweise für die USA. Ist eine der Datenbanken in mehrere Teildatenbanken unterteilt, so kann die

Recheneinrichtung während der Suche nach den möglichen Zielen zumindest eine der Teildatenbanken aus einem nicht-flüchtigen Speicher, in welchem die erste und die zweite Datenbank abgelegt sind, in einen flüchtigen Arbeitsspeicher laden bzw. kopieren und dann nach den passenden Datenbankeinträgen in der Teildatenbank des

Arbeitsspeichers suchen. Beispielsweise kann eine Teildatenbank nach der anderen oder auch zeitlich parallel nachgeladen und durchsucht werden. Es brauchen jedoch bei einer bestimmten Sucheingabe nicht alle Teildatenbanken durchsucht zu werden, sondern lediglich diejenigen, die für die empfangene Sucheingabe als plausibel beurteilt werden. Diese Ausführungsform sorgt im Aligemeinen für eine weitere Beschleunigung der Suche.

Wie bereits ausgeführt, kann das Durchsuchen der ersten und/oder der zweiten

Datenbank mittels einer linearen Suche, insbesondere mit einer sogenannten Skip- Funktion, erfolgen. Bei einer Skip-Funktion können einzelne Einträge der Liste

übersprungen werden. Auch dies reduziert die Suchzeit.

Vorzugsweise erfolgt die Generierung der Auswahlliste in Echtzeit: In einer

Ausführungsform ist vorgesehen, dass bereits während der Sucheingabe, wenn in einem Eingabefeld von dem Benutzer die Sucheingabe fortlaufend ediert beziehungsweise vervollständigt wird, wiederholt jeweils eine bislang vorgenommene Teileingabe durch die Recheneinrichtung empfangen und die Auswahlliste abhängig von der jeweils aktuellen Teileingabe fortlaufend aktualisiert wird. Insbesondere kann die Auswahlliste nach jedem neuen Zeichen oder jedem neuen Suchbegriff der Sucheingabe in Abhängigkeit von der jeweils aktuellen Teiletngabe aktualisiert werden. Der Benutzer bekommt somit die möglichen Ziele in der Auswahlliste angezeigt, ohne dass er die Sucheingabe

vervollständigen oder bestätigen muss. Werden die gefundenen möglichen Ziele entsprechend priorisiert, so kann es sogar möglich sein, dass das gewünschte Ziel bereits nach der Eingabe von wenigen Zeichen angezeigt wird, so dass der Aufwand für den Benutzer bei der Suche nach seinem gewünschten Ziel minimal ist.

Es ist bevorzugt, wenn den möglichen Zielen, welche durch die Recheneinrichtung aufgefunden und in der Auswahlliste angezeigt werden, jeweils ein Prioritätswert zugeordnet wird. Dann kann die Reihenfolge der möglichen Ziele in der Auswahlliste in Abhängigkeit von den Prioritätswerten bestimmt werden. Auf diesem Wege gelingt es, diejenigen möglichen Ziele an vorderster Stelle in der Auswahlliste anzuzeigen, welche gegenwärtig plausibler als andere Ziele erscheinen. Eine solche Vorgehensweise ist besonders benutzerfreundlich, weil der Benutzer zuerst die plausiblen Ziele angezeigt bekommt und sein gewünschtes Ziel entsprechend schnell auffinden kann.

Hinsichtlich der Priorisierung der gefundenen Ziele hat es sich weiterhin als vorteilhaft erwiesen, wenn die genannten Prioritätswerte in Abhängigkeit von zumindest einem der folgenden Parameter bestimmt werden:

Die Prioritätswerte können in einer Ausführungsform in Abhängigkeit von einer Häufigkeit bestimmt werden, mit welcher das jeweilige Ziel bislang zur Berechnung einer

Navigationsroute durch den Benutzer ausgewählt wurde. Wurde ein bestimmtes Ziel häufiger als andere Ziele ausgewählt, so kann dieses Ziel weiter vorne in der Auswahlliste als die anderen Ziele angezeigt werden, so dass der Benutzer dieses beliebte Ziel ohne viel Aufwand auffinden beziehungsweise schnell erfassen kann.

Ergänzend oder alternativ können die Prioritätswerte in Abhängigkeit von einer aktuellen Position des Kraftfahrzeugs bestimmt werden. Auch die aktuelle geografische Position des Kraftfahrzeugs stellt einen Parameter dar, welcher eine gewisse Rolle bei der Beurteilung der Plausibilität der gefundenen Ziele spielt.

Die Prioritätswerte können beispielsweise in Abhängigkeit von einer Entfernung des jeweiligen Ziels von der aktuellen geografischen Position des Kraftfahrzeugs bestimmt werden. Beispielsweise können diejenigen Ziele in der Auswahlliste höher als die anderen Ziele angezeigt werden, welche der aktuellen Position des Kraftfahrzeugs näher liegen. Diese Ausführungsform macht sich die Tatsche zunutze, dass die Ziele, die sich in einer relativ großen Entfernung von dem Kraftfahrzeug befinden, insgesamt seltener als die näheren Ziele ausgewählt werden.

Weiterhin ergänzend oder alternativ kann vorgesehen sein, dass die Prioritätswerte in Abhängigkeit von einem Übereinstimmungsgrad des jeweiligen Ziels mit der Sucheingabe des Benutzers bestimmt werden. Dabei kann die Beziehung gelten, dass je größer der Übereinstimmungsgrad ist, desto höher die jeweiligen Ziele in der Auswahlliste angezeigt werden.

Die Prioritätswerte können ergänzend oder alternativ auch in Abhängigkeit von einem Typ, insbesondere einem Verwaltungstyp und/oder der Kategorie (z.B. POI), des jeweiligen Ziels bestimmt werden. So können beispielsweise Städte oder kleinere Regionen anders als Straßen oder Sonderziele priorisrert werden. Beispielsweise kann dabei gelten, dass je genauer und eindeutiger das Ziel ist, desto höher dieses Ziel in der Auswahlliste angezeigt wird.

Wird als mögliches Ziel eine Stadt gefunden, so kann der Prioritätswert auch abhängig von einer Anwohneranzahl der Stadt bestimmt werden.

Die oben genannten Parameter können bei der Bestimmung der Prioritätswerte beispielsweise mit einer vorgegebenen Gewichtung berücksichtigt werden.

Dem Benutzer kann auch die Möglichkeit bereitgestellt werden, die angezeigten möglichen Ziele einzeln in eine Favoritenliste aufzunehmen. Bei einer nachfolgenden späteren Suche können dann diejenigen Ziele an vorderster Stelle platziert werden, welche in der Favoritenliste enthalten sind.

Beinhaltet die Sucheingabe mehrere Suchbegriffe (sogenannte„Tokens"), welche mit einem Leerzeichen oder mit einem anderen Trennzeichen voneinander getrennt eingegeben werden, so kann die Recheneinrichtung die beiden Datenbanken unabhängig von der Reihenfolge der Eingabe dieser Suchbegriffe durchsuchen. Die Sucheingabe „München Hanauer Straße 46" führt somit insgesamt zu der gleichen Auswahlliste, wie beispielsweise die Sucheingabe„Hanauer Straße 46 München" oder„46 Hanauer Straße München". Es werden bevorzugt auch Straßennamen unterstützt, welche mit einer Zahl beginnen, wie beispielsweise„50th Avenue". Auch diese Straßennamen können an beliebiger Stelle in der Sucheingabe angegeben werden.

Die Recheneinrichtung unterstützt vorzugsweise auch unvollständige und/oder fehlerhafte Sucheingaben. Eine solche Situation kann zum Beispiel dann auftreten, wenn statt „München" der Suchbegriff„Münch" oder aber„München" eingegeben wird. Die

Recheneinrichtung kann dabei einen Ähnlichkeitsgrad der eingegebenen Suchbegriffe mit den abgelegten Datenbankeinträgen bestimmen und diesen Ähnlichkeitsgrad mit einer vorgegebenen Schwelle vergleichen. Überschreitet der Ähnlichkeitsgrad diese Schweife, so wird der gefundene Datenbankeintrag ausgewählt.

Werden mehrere Suchbegriffe eingegeben, so kann die Recheneinrichtung bestimmte Suchbegriffe optional auch zusammenfassen. Beispielsweise kann dies dann

vorgenommen werden, wenn bei der Suche die Begriffe„Hanauer Straße" eingegeben werden. Diese beiden Suchbegriffe können zusammengefasst werden, so dass in den Datenbanken nach der„Hanauer Straße" gesucht wird. Das erfindungsgemäße Verfahren ermöglicht insgesamt eine flexible und vollständige Suche nach möglichen Zielen in einer Laufzeitkomplexität von O(n). Die Suchergebnisse werden anhand unterschiedlicher Parameter bewertet und letztendlich in einer nach Benutzerkontext sortierten Auswahlliste bereitgestellt. Das Verfahren basiert auf einem verbesserten Datenformat für den Suchindex, weicher in zwei unterschiedliche

Datenbanken beziehungsweise Tabellen gegliedert wird: einerseits die geografischen Regionen („Area Hierarchie") sowie andererseits die Straßennamen und/oder Sonderziele („Straßen/POl Hierarchie"). Die Erstellung der Datenbanken für den Suchindex erfolgt für statische Daten insbesondere in einem Kompilationsschritt bei der

Fertigung/Programmierung des Navigationssystems. Für dynamische Änderungen der Ausgangsdaten, wie beispielsweise der vom Benutzer selbst definierten Kontaktdaten, werden Teile des Suchindexes im Betrieb des Kraftfahrzeugs neu kompiliert und entsprechend angepasst. Der entscheidende Vorteil des Verfahrens liegt insbesondere in der Aufbereitung der Datenbanken beziehungsweise in dem Datenformat für den

Suchindex. Einerseits wird die erste und/oder die zweite Datenbank hochkomprimiert abgelegt, um möglichst wenig Speicherplatz im Kraftfahrzeug zu belegen; andererseits wird der Suchindex möglichst vollständig für alle relevanten Ziele (Adressen, POIs, Kontakte und so weiter) erstellt und für schnelle Abfragen während der Suche optimiert. Durch dieses Datenformat kann insgesamt Speicherplatz gespart werden. So benötigt die größere zweite Datenbank für alle Straßennahmen sowie Sonderziele in Deutschland lediglich ca. 8 MB, während für dieselben Informationen in dem NDS Free Text Search Building Block etwa 300 MB benötigt werden.

Die Erfindung betrifft außerdem ein Kraftfahrzeug, insbesondere einen

Personenkraftwagen, mit einem Navigationssystem, welches zum Durchführen eines erfindungsgemäßen Verfahrens ausgebildet ist. Die mit Bezug auf das erfindungsgemäße Verfahren vorgestellten bevorzugten Ausführungsformen und deren Vorteile gelten entsprechend für das erfindungsgemäße Kraftfahrzeug.

Weitere Merkmale der Erfindung ergeben sich aus den Ansprüchen, den Figuren und der Figurenbeschreibung. Alte vorstehend in der Beschreibung genannten Merkmale und Merkmalskombinationen sowie die nachfolgend in der Figurenbeschreibung genannten und/oder in den Figuren alleine gezeigten Merkmale und Merkmalskombinationen sind nicht nur in der jeweils angegebenen Kombination, sondern auch in anderen

Kombinationen oder aber in Alleinstellung verwendbar. Die Erfindung wird nun anhand eines bevorzugten Ausführungsbeispiels sowie unter Bezugnahme auf die beigefügten Zeichnungen näher erläutert.

Es zeigen:

Fig. 1 in schematischer Darstellung einen vorderen Bereich eines Innenraums eines Kraftfahrzeugs mit einem Navigationssystem gemäß einer

Ausführungsform der Erfindung;

Fig. 2 ein Blockdiagramm des Navigationssystems;

Fig. 3 den Aufbau einer ersten Datenbank;

Fig. 4 den Aufbau einer zweiten Datenbank; und

Fig. 5 ein Flussdiagramm eines Verfahrens gemäß einer Ausführungsform der

Erfindung.

Bezug nehmend auf Fig. 1 beinhaltet ein als Personenkraftwagen ausgebildetes

Kraftfahrzeug 1 einen Innenraum 2, dessen Frontbereich in Fig. 1 schematisch dargestellt ist. Auf einer Fahrerseite befindet sich in an sich bekannter Weise ein Lenkrad 3, welches zwischen einer Windschutzscheibe 4 und einem nicht dargestellten Fahrersitz angeordnet ist und zur Lenkung der vorderen Räder des Kraftfahrzeugs 1 dient. Zwischen der Windschutzscheibe 4 einerseits und dem Lenkrad 3 andererseits ist ein Armaturenbrett 5 angeordnet, das sich in Fahrzeugquerrichtung über die gesamte Breite des innenraums 2 erstreckt und zu welchem eine Mitteikonsole 6 gehört. Die Mittelkonsole 6 befindet sich mittig zwischen dem Fahrersitz und dem Beifahrersitz. in dem Kraftfahrzeug 1 ist ein Infotainmentsystem 7 fest installiert, welches in

unterschiedlichen Betriebsmodi betrieben werden kann, wie insbesondere in einem Navigationsmodus, einem Teiefonie-Modus und dergleichen. Das Infotainmentsystem 7 umfasst eine Anzeigeeinrichtung 8 mit einer beispielsweise durch eine

berührungssensitive Anzeigefläche 9 gebildeten Eingabeeinrichtung 10. Die

Anzeigeeinrichtung 8 ist beispielsweise in Form eines LCD-Displays bereitgestellt, wobei die Erfindung nicht auf eine bestimmte Displayart beschränkt ist und die

Anzeigeeinrichtung 8 grundsätzlich beliebig ausgestaltet sein kann, etwa auch in Form eines Head-Up-Displays und/oder in Form eines dreidimensionalen Displays. Die Anzeigeeinrichtung 8 kann beispielsweise in die Mittelkonsole 6 integriert sein, wie dies in Fig. 1 schematisch angedeutet ist. Sie kann aber auch ein frei programmierbares

Kombiinstrument sein.

Das Infotainmenisystem 7 beinhaltet also ein Navigationssystem 1 1 , dessen

Blockdiagramm in Fig. 2 dargestellt ist. Zum Navigationssystem 11 gehört eine

Recheneinrichtung 12, welche beispielsweise als digitaler Signaiprozessor ausgebildet ist. Die Recheneinrichtung 12 kann optional eine für das gesamte Infotainmenisystem 7 gemeinsame Recheneinrichtung sein. Die Recheneinrichtung 12 ist mit der

Anzeigeeinrichtung 8 gekoppelt und steuert diese an. Außerdem ist die

Recheneinrichtung 12 mit der Eingabeeinrichtung 10 verbunden, weiche zum

Durchführen von Eingaben dient. Wie bereits ausgeführt, kann diese Eingabeeinrichtung 10 durch die berührungssensitive Anzeigefläche 9 gebildet sein. Ergänzend oder alternativ kann die Eingabeeinrichtung 10 auch eine separate Tastatur und/oder einen Steuerknüppel und/oder ein Spracherkennungssystem umfassen.

Die Recheneinrichtung 12 ist des Weiteren mit einem Navigationsempfänger 13 gekoppelt, welcher zum Empfangen von Positionsdaten des Kraftfahrzeugs 1 ausgebildet ist. Ais Navigationsempfänger 13 kann beispielsweise ein GPS-Empfänger eingesetzt werden. Optional kann die Recheneinrichtung 12 auch an einen Fahrzeugbus, insbesondere den CAN-Bus, angebunden sein, um zum Beispiel Odometriedaten empfangen zu können.

Wird ein bestimmtes Ziel durch den Benutzer ausgewählt, so kann die Recheneinrichtung 12 eine Navigattonsroute berechnen, über welche das Kraftfahrzeug 1 bis zu dem festgelegten Ziel geführt werden kann. Die entsprechenden Navigationshinweise, welche den Fahrer dann zu dem ausgewählten Ziel führen, können einerseits über die

Anzeigeeinrichtung 8 und andererseits optional auch mit Hälfe eines Lautsprechers 14 akustisch ausgegeben werden. Bei der Berechnung der NavIgationsroute greift die Recheneinrichtung 12 auf eine insgesamt mit 15 bezeichnete Speichereinrichtung zu.

Das Interesse gilt vorliegend der Durchführung einer Suche nach möglichen Zielen. An der Eingabeeinrichtung 10 kann der Benutzer eine Sucheingabe vornehmen, anhand welcher die Recheneinrichtung 12 dann nach möglichen Zielen in der Speichereinrichtung 15 sucht. In der Speichereinrichtung 15 - etwa in einem gemeinsamen Speicher - sind dabei zwei separate Datenbanken abgelegt, nämlich eine erste Datenbank 16 sowie eine zweite Datenbank 17. Zusätzlich ist auch eine Navigationskarte vorgesehen, um die gefundenen Ziele dann geographisch auflösen bzw. in der realen Welt orten zu können.

Bezug nehmend nun auf Fig. 3 wird der Aufbau der ersten Datenbank 16 des

Suchindexes näher erläutert: Die erste Datenbank 16 ist in Form einer Tabelle

bereitgestellt und beinhaltet eine Vielzahl von Datenbankeinträgen 18, welche in der Indextabeile entsprechend geordnet sind. Die Tabelle beinhaltet drei Spalten: Eine erste, mit„ID" bezeichnete Spalte gibt die fortlaufende Nummer des jeweiligen

Datenbankeintrags 18 in der Reihenfolge ein. Der Kern der ersten Datenbank 16 ist durch eine zweite Spalte gebildet, in welcher geografische Regionen bzw. Gebiete angegeben sind. Jeder Datenbankeintrag 18 gibt dabei ein geografisches Gebiet an. Die

Datenbankeinträge 18 beziehungsweise die geografischen Regionen sind dabei hierarchisch in mehreren Hierarchiestufen geordnet und entsprechend einer

Baumstruktur so abgelegt, dass unmittelbar nach einer übergeordneten Region alle zu dieser Region gehörigen untergeordneten Regionen folgen. Die Hierarchiestufen sind dabei in der dritten Spalte angegeben. Diese Hierarchiestufen entsprechen insbesondere der jeweils geltenden politischen Verwaltungsstruktur des jeweiligen Staates. Wie aus Fig. 3 hervorgeht, hat der Staat aHeine (in diesem Falle„Deutschland") die höchste Hierarchiestufe„1". In der zweiten Hierarchiestufe„2" sind die Bundesländer angegeben, in der dritten Hierarchiestufe„3" die weiteren untergeordneten Regionen, in der

Hierarchiestufe„4" die Städte und so weiter. Nach dem Datenbankeintrag„Deutschland" folgen also alle Regionen, die zu der Region„Deutschland" gehören. Unmittelbar nach dem Dateneintrag„Bayern" folgen alle Regionen, die zu„Bayern" gehören, und so weiter. Innerhalb derselben Hierarchiestufe beziehungsweise Hierarchieebene können die jeweiligen Regionen optional alphabetisch geordnet sein.

Optional können die Datenbankeinträge 18 in der ersten Datenbank 16 auch komprimiert abgelegt sein, insbesondere delta-komprimIert.

Die Komprimierung erweist sich jedoch insbesondere bei der zweiten Datenbank 17 als besonders vorteilhaft, deren Aufbau in Fig. 4 schematisch dargestellt ist. In der zweiten Datenbank 17 sind Datenbankeinträge 19 abgelegt, welche Straßennamen und/oder Sonderziele (sogenannte„Points of Interest") angeben. Diese Straßennamen und/oder Sonderziele sind dabei delta-komprimiert, so dass zu jedem Datenbankeintrag 19 in der ersten Spalte„Comp" die Anzahl von Anfangsbuchstaben angegeben ist, welche von dem jeweils unmittelbar vorhergehenden Datenbankeintrag 19 übernommen werden sollen. Im Ausführungsbeispiel gemäß Fig. 4 ist als erster Datenbankeintrag 19 die„Aachener Straße" abgelegt. Es werden keine Buchstaben von einem vorherigen Eintrag

übernommen. Bei dem zweiten Datenbankeintrag 19 werden neun Buchstaben von dem vorherigen Datenbankeintrag 19 übernommen, das heißt der Anfangsteil„Aachener". Der zweite Datenbankeintrag 19 lautet folglich„Aachener Weg". Bei dem dritten

Datenbankeintrag 19 wird lediglich der erste Buchstabe„A" übernommen, so dass bei dem dritten Datenbankeintrag 19 die„Augsburger Straße" angegeben ist. In der zweiten Datenbank 17 sind die Datenbankeinträge 19 vorzugsweise alphabetisch abgelegt.

Die Datenbankeinträge der zweiten Datenbank können zusätzlich jeweils eine Referenz auf die genannte Navigationskarte beinhalten, um dann die gefundenen Ziele letztendlich geographisch orten zu können. Alternativ können die Datenbankeinträge der zweiten Datenbank auch aus der Navigationskarte referenziert werden, sofern das Datenformat der Navigationskarte dies zulässt bzw. vorsieht.

Mit erneutem Bezug auf Fig. 2 können die erste Datenbank 16 und/oder die zweite Datenbank 17 in mehrere Teildatenbanken 20 beziehungsweise 21 gegliedert sein. Die Teildatenbanken 20, 21 beinhalten dann lediglich eine Untermenge der jeweiligen Datenbankeinträge 18 beziehungsweise 19. Jede Teildatenbank 20, 21 kann dabei in Form einer separaten Datei bereitgestelft sein, welche in dem Speicher 15 abgelegt ist. Die Unterteilung in mehrere Teildatenbanken 20, 21 kann beispielsweise derart vorgenommen werden, dass größere Gebiete - wie beispielsweise die USA oder Europa - in mehrere kleinere Regionen - zum Beispiel in Staaten oder Bundesländer - aufgeteilt werden und zu jedem Teilgebiet jeweils eine separate Teildatenbank 20, 21 bereitgestellt wird. Beim Durchführen der Suche kann die Recheneinrichtung 12 dann eine oder mehrere der Teildatenbanken 20, 21 aus dem Speicher 15 in einen flüchtigen

Arbeitsspeicher kopieren beziehungsweise laden und dann nach den passenden

Datenbankeinträgen suchen. Dies reduziert die Rechenzeit auf ein Minimum.

Bezug nehmend nun auf Fig. 5 wird nachfolgend ein Verfahren gemäß einer

Ausführungsform der Erfindung näher erläutert:

In einem ersten Schritt S1 empfängt die Recheneinrichtung 12 eine Sucheingabe, welche der Benutzer an der Eingabeeinrichtung 10 vornimmt. Es kann sich hier zunächst um eine Teileingabe handeln, welche beispielsweise nur einen Suchbegriff beinhaltet. In einem wetteren Schritt S2 durchsucht die Recheneinrichtung 12 die erste Datenbank 16 - oder zumindest eine der Teildatenbanken 20 - nach passenden Datenbankeinträgen 18 abhängig von der empfangenen Sucheingabe. Die gefundenen Datenbankeinträge 18 werden in einer ersten Ergebnisliste gemäß Schritt S3 zusammengefasst.

Unabhängig davon - gleichzeitig oder im Anschluss - durchsucht die Recheneinrichtung 12 abhängig von derselben Sucheingabe auch die zweite Datenbank 17 nach passenden Datenbankeinträgen 19. Die Suche nach passenden Straßennamen und/oder

Sonderzielen erfolgt gemäß Schritt S4. Gemäß Schritt S5 werden die gefundenen Datenbankeinträge 19 aus der zweiten Datenbank 17 in einer zweiten Ergebnisliste zusammengefasst.

In einem weiteren Schritt S6 überprüft die Recheneinrichtung 12 die Verweise der gefundenen Datenbankeinträge 19 in der zweiten Ergebnisliste. Zeigt ein Verweis auf die _" ID" einer gefundenen Region aus der ersten Ergebnisliste, so werden diese beiden Datenbankeinträge 18, 19 zu einem Eintragspaar zusammengefasst und als mögliches Ziel gemäß Schritt S7 in eine Auswahlliste aufgenommen. Diejenigen Datenbankeinträge 18, 19, welche keine Zuordnung erfahren, werden gemäß Schritt S8 verworfen. Die Auswahlliste wird dann gemäß Schritt S9 auf der Anzeigeeinrichtung 8 angezeigt.

Wie in Fig. 5 angedeutet, wird das Verfahren wiederholt durchgeführt, während der Benutzer seine Sucheingabe vervollständigt. Das Verfahren wird beispielsweise nach jedem neuen Zeichen der Sucheingabe oder aber nach jedem neuen Suchbegriff durchgeführt und die Auswahlliste entsprechend der jeweils vollständigeren Sucheingabe aktualisiert. Eine separate Bestätigung der Sucheingabe durch den Benutzer ist dabei nicht erforderlich, kann am Ende der Sucheingabe jedoch optional vorgenommen werden.

Die Suchzeit ist insgesamt minimal, weil die beiden Datenbanken 16, 17 mittels einer linearen Suche mit einer so genannten„Skip"-Funktion durchsucht werden, bei welcher Teile der Liste übersprungen werden können. Für die Reduktion der Suchzeit sorgt außerdem die spezielle Rethenfolge der jeweiligen Datenbankeinträge 18, 19, mit welcher diese Datenbankeinträge 18, 19 in der jeweiligen Datenbank 16, 17 abgelegt sind.

Wird als Sucheingabe beispielsweise„München Hanau" eingegeben, so führt die Suche in der ersten Datenbank 16 zur folgenden ersten Ergebnisliste:

München

Hanau Die Suche in der zweiten Datenbank 17 führt wiederum zu einer zweiten Ergebnisliste, nämlich:

Münchener Straße

Hanauer Straße

Die Recheneinrichtung 12 stellt dann fest, dass bei der Hanauer Straße ein Verweis auf die Region„München" angegeben ist, jedoch der Datenbankeintrag„Münchener Straße" keinen Verweis auf die Region„Hanau" beinhaltet. Folglich ist lediglich eine einzige Kombination möglich, nämlich:„Hanauer Straße in München". Dieses mögliche Ziel wird dann in der Auswahlliste ausgegeben.

Gemäß einem weiteren Beispiel führt die Sucheingabe„Harn Str Münch" am Standort München zu folgender Auswahlliste:

Hamburger Straße in München

Hammersbacher Straße in München

Münchener Straße in Hammelburg

Edvard-Munch-Straße in Hamburg

Wird beim Durchsuchen der ersten Datenbank 16 eine bestimmte Region gefunden, so können in die erste Ergebnisliste gemäß Schritt S3 (vergleiche Fig. 5) zusätzlich auch alle dieser Region untergeordneten Regionen aufgenommen werden. Der in der zweiten Datenbank 17 angegebene Verweis zeigt nämlich auf die kleinste Region, so dass insgesamt eine präzise Zuordnung der Datenbankeinträge 18, 19 zueinander möglich ist.

Die möglichen Ziele können in der ausgegebenen Auswahlliste auch priorisiert und dementsprechend in einer speziell definierten Reihenfolge ausgegeben werden. Die Recheneinrichtung 12 kann jedem möglichen Ziel der Auswahlliste jeweils einen

Prioritätswert zuordnen, welcher abhängig von zumindest einem der folgenden Parameter ist: einer Häufigkeit, mit welcher das jeweilige Ziel bislang zur Berechnung der Navigationsroute ausgewählt wurde, und/oder

einer aktuellen geografischen Position des Kraftfahrzeugs 1 und/oder

einer Entfernung des jeweiligen Ziels von der aktuellen Position des

Kraftfahrzeugs 1 und/oder einem Übereinstimmungsgrad des jeweiligen Ziels mit der Sucheingabe und/oder einem Verwaltungstyp des jeweiligen Ziels und/oder

einer Einwohneranzahl des jeweiligen Ziels, falls als Ziel eine Stadt gefunden wird.

Im Ausführungsbeispiel kann dem Benutzer auch die Möglichkeit gegeben werden, die angezeigten möglichen Ziele einzeln in eine Favoritenliste aufzunehmen. Bei einer nachfolgenden späteren Suche können dann diejenigen Ziele an vorderster Stelle platziert werden, welche in der Favoritenliste enthalten sind. Wird ein gefundenes Ziel durch den Benutzer ausgewählt, so kann auch vorgesehen sein, dass dieses Ziel beispielsweise automatisch in die Favoritenliste aufgenommen wird. Es kann auch die Beziehung gelten, dass je öfter ein Ziel ausgewählt wird, desto höher sein Prioritätswert bzw. seine Gewichtung für die Favorisierung ist.