は、私はこのようになりますトライデータ構造を構築したレーベンシュタイン距離の検索

Question

スウィフトトライ：

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

がUITextFieldからの入力に自動補正操作を実行します。

/** 
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()) 
} 

必要イニシャライザ：私はトライをそのような挿入物として、様々な機能が得られた

/** 
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()) 
} 

を、私は要素を反復処理することができるようにSequenceTypeにTrieを適合しました。それが離れて元のクエリからだった

戻り値が一致したサブシーケンスのリストをある

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

} 

が見つかり、最大距離：

は今、私はレーベンシュタイン距離の検索機能は次のようになり、検索を実装したいですこれは私の知識が少し欠けている場所です。私はどのように実際に私のトライで検索を実行し、挿入、削除、および置換コストを計算しながら一致したシーケンスのリストを構築するのか分からない。

Answer 1

これに対する解決策は重要ではありませんが、ペーパーFast String Correction with Levenshtein-Automataをご覧ください。あなたはトライをLevenshteinオートマトンと交差する辞書オートマトンとして扱います。探索戦略は、指定されたしきい値以下のLevenshtein距離（照会項からの）を持つ項につながる交差点に沿った経路だけをたどるために使用されます。

参考として、liblevenshteinにはJavaで実装されています。トライの検索に関するロジックについては、src/main/java/com/github/liblevenshtein/transducerを参照してください。