好久没更新Blog了，真是一毕业就克制不住自己的懒惰，以后要做个不仅高产，而且有优质文章的“农民”。加油啦，新起点就尝试翻译以下Swift Algorithm Club的文章，算法很重要，Swift是一门很优雅的语言，要跟上节奏，夯实基础，学习新知😂，不扯皮了。
翻译自：https://www.raywenderlich.com/139410/swift-algorithm-club-swift-trie-data-structure
开始
字符存储在树的每个节点的 n-元(n-ary)树称作单词查找树。单词查询树是一种可以促进英文高效地前缀匹配的键值结构。
SwiftAlgClub_TrieData-trie-1.png
上述例子：“Cat”，“Cut”，“Cute”，“To”，“B”
为什么使用单词查找树
单词查找树对某些情况非常实用。除了非常好地存储英文，它同样可以作为‘哈希表’的替代， 它有以下几个优势：
- 查找值时通常有一个更好的最坏的时间复杂度
- 不像哈希表，单词查找树不用担心键冲突问题
- 不需要哈希算法保证每个元素有一个独一无二的路径
- 单词树可以按照字母顺序排序
实现
你的实现将由一个TrieNode和一个Trie类构成，每个TrieNode代表单词 一个字符。例如，“cute”将有以下的节点构成：c->u->t->e。Trie将管理节点的插入逻辑并且一直关联着这些节点
我们首先实现简单的TrieNode类
TrieNode
class TrieNode<T: Hashable> {
var value: T?
weak var parent: TrieNode?
var children: [T: TrieNode] = [:]
init(value: T? = nil, parent: TrieNode? = nil) {
self.value = value
self.parent = parent
}
}
上面是TrieNode类的一般实现。它存储着一个值（对于英文而言就是字符）并且有一个父节点和孩子们子节点的引用。这里有以下几点需要注意：
-
class TrieNode<T:Hashable> ，泛型类型，这说明TrieNode适用于任何遵循Hashable协议的类型
-
parent节点使用weak，防止出现循环引用问题，因为对于某个节点而言它的父节点中的children数组肯定包含该节点， 如果这里在使用默认的strong引用父节点就出现了循环引用。某个节点包含父类的引用是必须的，对于移除操作remove会使用的到
-
TrieNode必须遵循Hashable协议。因为你将会使用这个值作为children字典的key，在Swift中只要能作为能作为字典的key就必需遵循Hashable协议
接下来在TrieNode中添加add操作
func add(child: T) {
// 1. 确保插入的“字符”子节点在当前子节点数组中不存在
guard children[child] == nil else { return }
// 2. 创建一个新节点将传入的值插入
children[child] = TrieNode(value: child, parent: self)
}
Trie
Trie类的职责是管理节点。
class Trie {
fileprive let root: TrieNode<Character>
init() {
root = TrieNode<Character>()
}
}
以上就是Trie类的基础，声明一个root属性去关联你的 ”字典树“ 的根节点。因为我们要实现一个特定于英文的“字典树”所以我们使用的节点类型是Character，它是Hashable的子协议，初始化方法实现一个简单的初始化实现一个空节点
Typealiasing
再继续往下之前将Trie类做如下更新：
class Trie {
typealias Node = TrieNode<Character>
fileprivate let root: Node
init() {
root = TrieNode<Character>()
}
}
上面添加了一个Node typealias， 它允许你使用Node去替代TrieNode，除了能够缩短语法，他还可以使程序变得更加“健壮”；
Insertion
Trie类管理者“单词树”Trie的操作，当实现insertion方法时，记住Trie是高效的，因为它总是使用已经存在的节点去完成一个排序。例如有两个单词“Cut”，“Cute”，仅需要使用4个节点，因为“Cut”是“Cute”的前缀
extension Trie {
func insert(word: String) {
// 如果word是个空字符串，直接返回
guard !word.isEmpty else {
return
}
// 将从根节点开始执行迭代
var currentNode = root
// 每个单词在Trie中都表现为一连串的字符节点
// 例如cute：c->u->t->e
// 因为你要一个一个地插入字符，将单词装换成一个字符数组能更方便地保留字符的插入的轨迹
let charcters = Array(word.lowercased().characters)
var currentIndex = 0
//TODO:
while currentIndex < charcters.count {
// 得到当前将要插入的字符
let character = charcters[currentIndex]
// 判断该字符是否在当前节点的“孩子们”子节点数组中是否存在
if let child = currentNode.children[character] {
currentNode = child // 如果存在，只需简单地将当前节点移动到这个存在的节点即可开始下一个字符的插入操作
} else {
// 如果不存在， 那就添加个，并移动当前节点的指针到新创建的节点上
currentNode.add(child: character)
currentNode = currentNode.children[character]!
}
currentIndex += 1
}
}
}
SwiftAlgClub_TrieData-trie-2.png
Teminating Nodes
到现在为止，insert方法可以很好到执行插入操作。但是这里会有个问题，例如如果你插入的是“cute”，该这样确定“cut”已经存在呢？？
如果没有一些分类的指示器好像很难去确定。回到TrieNode，添加如下属性
var isTerminating = false // 负责指示一个单词是否结束
回到“cute”那个例子，如果插入“cute”，isTerminating是这样标识的
SwiftAlgClub_TrieData-trie-3.png
小黑点标识cute的结束；接下来如果插入“cut”就会将“t”标识为结束点
SwiftAlgClub_TrieData-trie-4.png
在insert的while中添加如下代码
// 如果currentIndex等于单词字符的数量，就说明已经到达单词的结尾，可以将结束标识置为true
if currentIndex == characters.count {
currentNode.isTerminating = true
}
Contains
接下来处理contains函数，这个方法的职责是检查单词是否存在
func contains(word: String) -> Bool {
guard !word.isEmpty else {
return false
}
var currentNode = root
let characters = Array(word.lowercased().characters)
var currentIndex = 0
// 这里将尝试遍历基于传递的word字符的节点
// 1. 创建一个while循环， 有两个条件
// (1). 没有到达单词的结尾
// (2). 存在字符对应的节点
while currentIndex < characters.count,
let child = currentNode.children[characters[currentIndex]] {
// 当while成功执行结束时，currentNode将会指向最终的节点， currentIndex并且是字符串的长度
currentIndex += 1
currentNode = child
}
// 成功遍历完所有的字符，并且该结束节点是某个字符串的结尾，则返回true， 否则返回false
if currentIndex == characters.count &&
currentNode.isTerminating {
return true
} else {
return false
}
}
至此Trie完成
源码：https://github.com/X-Liang/Swift-Algorithm
网友评论