Implementierung einer grundlegenden Suchmaschine mit Präfix Baum

Question

Das Problem ist die Implementierung eines Präfix Baum (Trie) in der funktionalen Sprache ohne Verwendung von Speicher und iterative Methode.

Ich versuche, dieses Problem zu lösen. Wie soll ich dieses Problem angehen? Können Sie mir einen genauen Algorithmus oder einen Link geben, der bereits implementiert in einer beliebigen funktionalen Sprache zeigt?

Warum ich versuche = zu tun> eine einfache Suchmaschine zu schaffen mit einer Funktion von

• Zugabe Wort zu Baum
• ein Wort im Baum suchen
• ein Wort im Baum Löschen

Warum ich funktionale Sprache verwenden möchte => Ich möchte meine Problemlösungsfähigkeit noch ein wenig verbessern.

HINWEIS: Da es sich um mein Hobbyprojekt handelt, werde ich zuerst grundlegende Funktionen implementieren.

EDIT:

i) Was ich meine, über "ohne Speicher mit" => Ich möchte nicht, Variablenspeicher verwenden (ex int a), Verweis auf eine Variable, Array.. Ich möchte das Ergebnis rekursiv berechnen und dann das Ergebnis auf dem Bildschirm anzeigen.

ii.) Ich habe eine Zeile geschrieben, aber dann habe ich gelöscht, weil das, was ich geschrieben habe, mich wütend gemacht hat. Tut mir leid, dass ich meine Bemühungen nicht gezeigt habe.

Answer 1

Werfen Sie einen Blick auf Haskells Data.IntMap.Es ist rein funktionale Umsetzung von Patricia trie und es ist source ist gut lesbar.
bytestring-trie Paket erweitert diesen Ansatz ByteStrings

begleitet Papier Es Fast Mergeable Integer Maps die auch lesbar und durch ist. Es beschreibt Schritt für Schritt die Implementierung: von binären Versuchen zu Big-Endian-Patricia-Bäumen.
Hier ist ein kleiner Auszug aus dem Papier.

In ihrer einfachsten Form eine binäre Trie ist ein vollständiger binärer Baum der Tiefe gleich der Anzahl von Bits in den Tasten, wobei jedes Blatt entweder leer ist, was anzeigt, dass die entsprechende Taste ist nicht gebundenen oder voll, in in welchem ​​Fall es die Daten enthält, an die der entsprechende Schlüssel gebunden ist. Diese Art der Trie könnte in Standard ML als

datatype 'a Dict = 
    Empty 
    | Lf of 'a 
    | Br of 'a Dict * 'a Dict 

Um Lookup einen Wertes in einem binären Trie dargestellt wird wir einfach die Bits des Schlüssels lesen, links zu gehen oder rechts gerichtet, bis wir ein Blatt erreichen.

fun lookup (k, Empty) = NONE 
    | lookup (k, Lf x) = SOME x 
    | lookup (k, Br (t0,t1)) = 
     if even k then lookup (k div 2, t0) 
       else lookup (k div 2, t1) 

Answer 2

Der Schlüsselpunkt bei Implementierungen unveränderlicher Datenstrukturen ist , der von Daten und Struktur teilt. Um ein Objekt zu aktualisieren, sollten Sie eine neue Version mit möglichst vielen gemeinsamen Knoten erstellen. Konkret kann für Versuche der folgende Ansatz verwendet werden.

Betrachten wir eine solche trie (von Wikipedia):

Stellen Sie sich vor, dass Sie nicht Wort "inn" hinzugefügt haben, aber Sie haben bereits Wort "in". Um "inn" hinzuzufügen, müssen Sie eine neue Instanz des gesamten Trie mit "inn" hinzufügen. Sie sind jedoch nicht gezwungen, das Ganze zu kopieren - Sie können nur eine neue Instanz des Wurzelknotens (dies ohne Label) und das richtige Banch erstellen. Der neue Wurzelknoten zeigt auf das neue Recht banch, aber auf alte andere Zweige, so wird bei jeder Aktualisierung der größte Teil der Struktur mit dem vorherigen Zustand geteilt.

Ihre Schlüssel können jedoch ziemlich lang sein, so dass die gesamte Verzweigung jedes Mal wieder zeit- und platzaufwendig ist. Um diesen Effekt zu verringern, können Sie die Struktur auch innerhalb eines Knotens teilen. Normalerweise ist jeder Knoten ein Vektor oder eine Karte aller möglichen Ergebnisse (z. B. in einem Bildknoten mit der Bezeichnung "te" hat 3 Ergebnisse - "a", "d" und "n"). Es gibt viele Implementierungen für unveränderliche Karten (Scala, Clojure, siehe ihre Repositories für weitere Beispiele) und Clojure hat auch ausgezeichnete implementation eines unveränderlichen Vektors (der eigentlich ein Baum ist).

Alle Vorgänge zum Erstellen, Aktualisieren und Suchen von resultierenden Versuchen können rekursiv ohne einen änderbaren Status implementiert werden.