Swift 特里列文斯坦距离搜索

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([=13=]) }
}

/**
 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)] {

}

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

Answer 1

这个问题的解决方案很重要，但请看一下这篇论文，Fast String Correction with Levenshtein-Automata。您会将您的 trie 视为字典自动机，它与 Levenshtein 自动机相交。搜索策略用于仅沿着交叉路口的路径，这些路径导致 Levenshtein 距离（与查询词）不大于指定阈值的词。

作为参考，liblevenshtein has an implementation in Java. For the logic pertaining to searching the trie, look in src/main/java/com/github/liblevenshtein/transducer。

Swift 特里列文斯坦距离搜索

Swift Trie levenshtein distance search

ios

swift

trie

levenshtein-distance

autocorrect