Ich frage mich, ob es eine effiziente Datenstruktur zu führen "Retrieve alle Zeichenfolgen mit Levenshtein Abstand weniger als X".Weg zu implementieren "Get alle Zeichenfolgen mit Levenshtein Abstand weniger als X"
Ein paar Dinge, die ich habe Interesse an:
dies nächste neighborer Suche in einem metrischen Raum mit levenshtein Abstand als Metrik (oder Abstand) Funktion
a VP-tree ist einer der Wege zur Lösung dieses Problems
Diese Python VP-tree implementation ist eine funktionierende Demo, die zeigt, wie ein VP-Baum funktioniert, z. B. eine Wortliste, eine interaktive Shell, wo man ein Wort eingibt und die Wörter in dieser Liste, die nicht mehr als X Abstand von dem eingegebenen Wort sind
Klingt nach einem einfachen breadth-first search, wobei jede Generation nur eine "Bearbeitung" weg von der vorherigen ist - und mit Kontrollen, um sicherzustellen, dass eine Zeichenfolge in einer einzigen Ebene erscheint.
Dies wäre einfach mit ein paar Hashsets/Hashtables in einem Paar Schleifen implementiert werden.
Kühl. Ich weiß nicht, warum es mir nie in den Sinn gekommen ist, dass Leute versuchen würden, dieses Problem in allgemeinen metrischen Räumen zu lösen. Ich werde es mir ansehen. –