Swift Trie поиск Левенштейн

Question

Я построил структуру данных TRIE, которая выглядит следующим образом:

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

для выполнения операций автоисправления на входе от UITextField. Я дал TRIE различные функции, такие как вставки:

/** 
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 так что я могу итерацию по элементам.

Теперь я хочу, чтобы осуществить поиск Левенштейн, где функция поиска будет выглядеть:

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.