Swift Trie levenshtein Entfernung Suche

Question

ich eine Trie-Datenstruktur aufgebaut haben, die wie folgt aussieht:

struct Trie<Element : Hashable> : Equatable { 
    private var children: [Element: Trie<Element>] 
    private var endHere: Bool 
} 

auf Autokorrektur-Operationen auf eine Eingabe von einem UITextField auszuführen. Ich habe den Trie eine Vielzahl von Funktionen, wie beispielsweise Einsatz:

/** 
Private insert function. Inserts an elements into a trie using a sequences' generator. 

- parameter g: `GeneratorType`. 
*/ 
private mutating func insert<G: GeneratorType where G.Element == Element>(g: G) { 
    var gen = g 
    if let head = gen.next() { 
     if case nil = children[head]?.insert(gen) { 
      children[head] = Trie(g: gen) 
     } 
    } else { 
     endHere = true 
    } 
} 

/** 
Insert elements into the trie. 

- parameter seq: Sequence of elements. 
*/ 
mutating func insert<S: SequenceType where S.Generator.Element == Element>(seq: S) { 
    insert(seq.generate()) 
} 

notwendige Initialisierungen:

/** 
Create an empty trie. 
*/ 
init() { 
    children = [:] 
    endHere = false 
} 

/** 
Initialize a trie with a generator. 

- parameter g: `GeneratorType`. 
*/ 
private init<G: GeneratorType where G.Element == Element>(g: G) { 
    var gen = g 
    if let head = gen.next() { 
     (children, endHere) = ([head:Trie(g: gen)], false) 
    } else { 
     (children, endHere) = ([:], true) 
    } 
} 

/** 
Construct from an arbitrary sequence of sequences with elements of type `Element`. 

- parameter s: Sequence of sequences. 
*/ 
init<S: SequenceType, Inner: SequenceType where S.Generator.Element == Inner, Inner.Generator.Element == Element>(_ s: S) { 
    self.init() 
    s.forEach { insert($0) } 
} 

/** 
Construct a trie from a sequence of elements. 

- parameter s: Sequence. 
*/ 
init <S: SequenceType where S.Generator.Element == Element>(_ s: S) { 
    self.init(g: s.generate()) 
} 

und angepasst Trie zu SequenceType so dass ich durch die Elemente laufen kann.

Nun möge ich eine levenshtein Abstand Suche implementieren, wo die Suchfunktion aussehen würde:

func search<S: SequenceType where S.Generator.Element == Element(s: S, maxDistance: Int = 0) -> [(S, Int)] { 

} 

wo der Rückgabewert ist eine Liste von passenden Teilfolgen gefunden und max Entfernung war es weg von der ursprünglichen Abfrage Sequenz, aber das ist, wo mein Wissen ein bisschen fehlt. Ich bin nicht sicher, wie man die Suche auf meinem Trie wirklich durchführt und eine Liste der zusammenpassenden Folgen beim Berechnen der Einfügungs-, Löschungs- und Wiederbeschaffungskosten aufbaut.

Answer 1

Die Lösung dafür ist nicht trivial, aber werfen Sie einen Blick auf das Papier, Fast String Correction with Levenshtein-Automata. Sie würden Ihren Trie als den Wörterbuchautomaten behandeln, der mit einem Levenshtein-Automaten geschnitten wird. Mit einer Suchstrategie werden nur die Pfade entlang des Schnittpunkts verfolgt, die zu Termen mit Levenshtein-Distanzen (aus dem Abfragebegriff) führen, die nicht größer als der angegebene Schwellenwert sind.

Als Referenz hat liblevenshtein eine Implementierung in Java. Suchen Sie in der src/main/java/com/github/liblevenshtein/transducer Logik für die Suche nach dem Trie.