주제: String Data 검색에 특화된 자료 구조
Tries란
- Trie(트라이)는 영어 단어와 같이 컬렉션 형태로 표현 가능한 데이터를 저장하는데 특화된 트리 구조이다.
- 트라이의 장점은 접두사 매칭(perfix matching)을 다룰 때 가장 두드러진다.
Example
class EnglishDictionary {
private var words: [String]
func words(matching perfix: String) -> [String] {
words.filter { $0.hasPrefix(prefix)}
}
}- 이 알고리즘은 words 배열의 요소 수가 적을 때는 합리적인 선택입니다. 그러나 수천 개 이상의 단어와 같은 많은 양의 데이터를 다룰 때는, words(matching:) 메소드가 words 배열을 확인하는 데 소요되는 시간이 받아들일 수 없을 정도로 많아집니다. words(matching:)의 시간 복잡도는 k가 컬렉션에서 가장 긴 문자열의 길이이고, n은 확인해야 하는 단어 수일 때, O(k*n) 입니다.
- 트라이 자료 구조는 이 문제에 대해 뛰어난 성능 특성을 가지며, 여러 개의 자식을 가진 노드를 지원하는 트리로 각 노드가 단일 문자를 나타낼 수 있습니다.
구현
TrieNode
public class TrieNode<Key: Hashable> {
public var key: Key?
public weak var parent: TrieNode?
public var children: [Key: TrieNode] = [:]
public var isTerminating = false
public init(key: Key?, parent: TrieNode?) {
self.key = key
self.parent = parent
}
}- key
- 각 TrieNode가 가지는 데이터로서, 문자열의 각 문자 혹은 다른 타입을 가질 수 있습니다.
- parent
- 각 TrieNode가 부모 노드와의 연결을 갖는 weak 참조입니다. 이 연결은 나중에 remove 메서드에서 활용 됩니다.
- children
- TrieNode는 하나 이상의 자식 노드를 가지기 때문에, Dictionary 타입의 children 속성을 이용하여 다수의 자식 노드를 저장합니다.
- isTerminating
- 단어의 끝을 나타내는 변수입니다.
Trie
public class Trie<CollectionType: Collection> where CollectionType.Element: Hashable {
public typealias Node = TrieNode<CollectionType.Element>
private let root = Node(key: nil, parent: nil)
public init() { }
}- 컬렉션의 각 요소는 Hashable이여야 하는데, 이는 TrieNode의 children 딕셔너리에서 키로 컬렉션의 요소를 사용하기 때문입니다.
Insert
- Tries는 Collection 프로토콜을 채택하는 어떤 타입이든지 작동할 수 있습니다.
public func insert(_ collection: CollectionType) {
var current = root
for element in collection {
if current.children[element] == nil {
current.children[element] = Node(key: element, parent: current)
}
current = current.children[element]!
}
current.isTerminating = true
}- 현재 위치를 추적하기 위해 current가 루트 노드를 참조한다.
- Trie는 각 Collection 요소를 별도의 노드에 저장한다. 각 Collection 요소마다 먼저 현재 노드가 children 딕셔너리에 있는지 확인하고 없으면 새 노드를 만든다. 각 루프에서, current를 다음 노드로 이동한다.
- for 루프를 모두 반복한 후, current는 collection 끝을 나타내는 노드를 참조해야 한다. 그 노드를 종료 노드로 표시하고, 이 알고리즘의 시간 복잡도는 O(k)이다. 여기서 k는 삽입하려는 Collection 내 요소의 수 이다.
Contains
- contains는 insert 메소드와 매우 유사하다.
public func contains(_ collection: CollectionType) -> Bool {
var current = root
for element in collection {
guard let child = current.children[element] else {
return false
}
current = child
}
return current.isTerminating
}- 여기서는 insert와 유사한 방식으로 trie를 순회하며, Collection의 각 요소를 체크하여 tree에 포함되어 있는지 확인한다.
Remove
public func remove(_ collection: CollectionType) {
var current = root
for element in colleciton {
guard let child = current.children[element] else {
return
}
current = child
}
guard current.isTerminating else {
return
}
current.isTerminating = false
while let parent = current.parent, current.children.isEmpty && !current.isTerminating {
parent.children[current.key!] = nil
current = parent
}
}- 중간에 있는 글자는 isTerminating이 false이니깐 사전에 false로 바꿔주고, children.isEmpty를 확인해 준다.
Prefix matching
- Trie에 대한 가장 대표적인 알고리즘은 접두사 매칭(prefix - matching) 알고리즘 입니다.
public extension Trie where CollectionType: RangeReplaceableCollection {
func collections(staringWith prefix: CollectionType) -> [CollectionType] {
var current = root
for element in prefix {
guard let child = current.children[element] else {
return []
}
current = child
}
return collections(startingWith: prefix, after: current)
}- 접두사 매칭 알고리즘은
RangeReplaceableCollection를 채택한extension내부에 존재해야 합니다. - 해당 알고리즘이
RangeReplaceableCollection타입의append메서드에 접근할 필요가 있기 때문입니다. - 접두사가 트라이에 포함되어 있는지 확인을 시작합니다. 만약 포함되어 있지 않다면, 빈 배열을 반환합니다.
- 접두사의 끝을 나타내는 노드를 찾은 후에는, 현재 노드 이후의 모든 시퀀스를 찾기 위해 재귀적인 메서드
collections(startingWith: after:)를 호출합니다.
private func collections(startingWith prefix: CollectionType, after node: Node) -> [CollectionType] {
var results: [CollectionType] = []
if node.isTerminating {
results.append(prefix)
}
for child in node.children.values {
var prefix = prefix
prefix.append(child.key!)
reuslts.append(contentsOf: collections(startingWith: prefix, after: child))
}
return results
}
}
- 해당 결과를 저장할 배열을 생성합니다. 현재 노드가 종료 노드이면, 해당 내용을 결과에 추가합니다.
- 다음으로, 현재 노드의 자식들을 확인하기 해야 하며, 다른 종료 노드를 찾기 위해 재귀적으로
collections(startingWith: after:)를 호출합니다. collections(staringWith:)의 시간 복잡도는 O(km) 입니다. 여기서 K는 접두사와 일치하는 가장 긴 컬렉션을 나타내고 m은 접두사와 일치하는 컬렉션의 수를 나타냅니다.- 배열은 시간 복잡도가 O(kn)을 가지는데, 여기서 n은 컬렉션의 요소 수입니다.
- 각 켤렉션이 균등하게 분포된 대규모 데이터 세트의 경우, 트라이는 접두사 매칭을 위해 배열을 사용하는 것 보다 훨씬 좋은 성능을 가집니다.
let trie = Trie<String>()
trie.insert("cute")
trie.insert("cuddd")
print(trie.collections(startingWith: "cud"))
["cuddd"]출처(참고문헌)
제가 학습한 내용을 요약하여 정리한 것입니다. 내용에 오류가 있을 수 있으며, 어떠한 피드백도 감사히 받겠습니다.
감사합니다
