Datenstruktur, um Namen von Dateien zu suchen und seinen Pfad

Question

Ich werde Namen von Dateien in einer dynamischen Weise, etwa bis 1 Milliarde Namen einfügen. Außerdem möchte ich auch den Pfad speichern, in dem sich die Dateien befinden, um die folgenden Abfragen auszuführen:

• Suche, ob der Name einer Datei gespeichert wird, um seinen Pfad zu erhalten.
• Suche nach dem Namen aller Dateien, die mit einer Teilzeichenfolge übereinstimmen, eine Art von Like-Abfrage (zB Wenn eine Suche * o *, es gibt mir Joel, Hola, Ola, Oso, Osea, Algo, wenn a Suche aa *, es wird mir aaab zurückgeben und wenn ich * so suche, wird es oso zurückgeben.
• Löschen Sie den Namen einer Datei.

Also, ich versuche, eine Art von Trie-Datenstruktur in der folgenden Art und Weise zu machen:

Ich habe 26 Knoten (das Englisch Alphabet az, ich werde nicht alle Knoten im Bild setzen weil space) so, dass, wenn ich das Wort "hola" einfüge, ich eine Kante vom Knoten mit dem Buchstaben 'h' zum Knoten mit dem Buchstaben 'o' erzeuge und dessen Kante eine Daten 1 hat, da diese Zahl die Ebene der Tiefe darstellt . Außerdem werde ich in dem Knoten, in dem 'a' gespeichert ist, eine Map-Struktur haben, um den Pfad der Datei zu speichern, da ich sicher viele Pfade in dem Knoten gespeichert habe, der den Buchstaben 'a' enthält. .

Nachdem ich das gesagt habe, habe ich die folgenden Wörter eingefügt: Joel, Hola, Ola, Oso, Osea, Algo, Aaab.

Ich habe so getan, weil ich viele Knoten mit dem Sama lettres (zB a, b, usw.), aber das Problem ist, haben möge, dass ich eine Menge von Kanten und die sctructure brauchen nicht

bekam

Byte Speicher (ich Programmieren in C++), wobei W eine Kette von Größe ist .

Wie Sie sehen können, wenn ich nach dem Namen der Datei "jola" suche (die nicht eingefügt wird), wird kein Pfad zurückgegeben und dies sagt uns, dass diese Datei nicht gespeichert wird.

Wie kann ich das verbessern? Kann man die Anzahl der Kanten reduzieren? oder gibt es eine bessere Struktur und einen Weg, dies zu tun? Ich bin sehr offen dafür, irgendeinen Vorschlag zu hören.

Answer 1

können Sie entweder eine DAG (gerichteter azyklischer Graph) oder können auch die disjunkt Satz Operationstechniken verwenden (Schnellsuche Technik (* als Hauptziel zu finden ist))