Suchen aller Namen, die mit einer Abfrage übereinstimmen: Wie verwendet man einen Suffixbaum?

Question

Frage: Sie haben ein Smartphone und Sie haben die Kontakt App geöffnet. Sie möchten einen Kontakt suchen. sagen wir mal manmohan. aber du erinnerst dich nicht an seinen vollen Namen. du erinnerst dich nur an mohan, also hast du angefangen zu tippen. In dem Moment, in dem Sie "m" eingeben, beginnt die Kontakt-App nach einem Kontakt zu suchen, der den Buchstaben "m" enthält. Angenommen, Sie haben Namen in Ihrer Kontaktliste gespeichert. ("manmohan", "manoj", "raghav","dinesh", "aman") Jetzt zeigt der Kontakt manmohan,manoj and aman als Ergebnis an. Das nächste Zeichen, das Sie eingeben, ist 'o' (bis jetzt haben Sie "mo" eingegeben) jetzt sollte das Ergebnis "man mo han" sein. Wie würden Sie eine solche Datenstruktur implementieren?

Mein Ansatz war KMP anwenden, wie Sie für Muster "M" dann "Mo" in allen verfügbaren Kontakt suchen. Zeigen Sie dann die Zeichenfolge an, die die Übereinstimmung aufweist. Aber Interviewer sagte, es ist nicht effizient. (Ich konnte mir keinen besseren Ansatz vorstellen.) Bevor er ging, sagte er, dass es einen Algorithmus gibt, der helfen wird. Wenn du es weißt, kannst du es lösen. Ich konnte es nicht tun. (Bevor ich ging, fragte ich nach dem Standard-Algorithmus. Interviewer sagte: Suffix-Baum). kann mir bitte jemand erklären wie ist es besser? oder welcher der beste Algorithmus ist, um diese Datenstruktur zu implementieren.

Answer 1

Das Problem, das Sie zu lösen versuchen, läuft im Wesentlichen auf das Folgende hinaus: Wie finden Sie bei einer festen Sammlung von Strings und einem String, der sich nur über Attends ändert, effizient alle Strings, die dieses Muster enthalten?

Es gibt ein ordentliches kleines Ergebnis für Strings, das oft nützlich ist, um Probleme mit der Teilstringsuche zu behandeln: Eine Zeichenfolge P ist eine Teilzeichenfolge einer Zeichenfolge T genau dann, wenn P ein Präfix von mindestens einem Suffix von T ist. Siehst du warum??

Also stellen Sie sich vor, dass Sie jeden Namen in Ihrer Wortbank nehmen und einen Trie aller Suffixe aller Wörter in dieser Bank konstruieren. Wenn Sie nun nach der Musterzeichenfolge P suchen, gehen Sie den Trie herunter und lesen die Zeichen von P. Wenn Sie vom Trie abfallen, dann darf die Zeichenkette P keine Teilzeichenkette irgendeiner Namensbank sein (sonst wäre es gewesen ein Präfix von mindestens einem Suffix einer der Zeichenfolgen in T). Ansonsten befinden Sie sich in einem Trie-Knoten. Dann entsprechen alle Suffixe im Teilbaum, der auf dem gerade besuchten Knoten verwurzelt ist, allen Übereinstimmungen Ihrer Teilstring in allen Namen in T, die Sie durch DFS-Eingabe des Subtrie finden und alle Suffixe aufzeichnen können finden.

Ein Suffixbaum ist im Wesentlichen eine zeit- und platzsparende Datenstruktur zum Darstellen eines Trie aller Suffixe einer Sammlung von Strings. Es kann in Zeit aufgebaut werden, die proportional zur Anzahl der gesamten Zeichen in T ist (obwohl die Algorithmen dafür bekanntlich schwer zu verstehen und zu kodieren sind) und ist so konzipiert, dass Sie alle Übereinstimmungen der fraglichen Textskette finden können, die auf a basiert gegebenen Knoten in der Zeit O (k), wobei k die Anzahl der Übereinstimmungen ist.

Zur Erinnerung, der Kerngedanke hier ist, einen Trie aller Suffixe der Strings in T zu erstellen und dann mit dem Muster P nach unten zu gehen. Für Zeit- und Raumeffizienz würden Sie dies mit einem Suffix machen Baum eher als ein Suffix Trie.