ios - Swift Trie levenshtein 距离搜索

Question

我构建了一个如下所示的 trie 数据结构:

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

对来自 UITextField 的输入执行自动更正操作。我给了trie多种功能比如insert:

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

并使 Trie 符合 SequenceType 以便我可以遍历元素。

现在，我想实现一个 levenshtein 距离搜索，搜索函数如下所示:

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

}

其中返回值是找到的匹配子序列的列表以及它与原始查询序列的最大距离，但这是我的知识有点缺乏的地方。我不确定如何在我的 trie 中实际执行搜索并在计算插入、删除和替换成本时构建匹配序列列表。

Answer 1

这个问题的解决方案并不简单，但请看一下这篇论文:Fast String Correction with Levenshtein-Automata .您可以将您的 trie 视为字典自动机，它与编辑自动机相交。搜索策略用于仅遵循沿着交叉点的路径，这些路径通向编辑距离(距查询术语)不大于指定阈值的术语。

作为引用，liblevenshtein在Java中有一个实现。有关搜索 trie 的逻辑，请查看 src/main/java/com/github/liblevenshtein/transducer .