[스위프트:자료구조] 트라이: Trie: 문자열 찾기: 단어 찾기

안녕하세요 !  씩이 입니다!

저는 Swift 와 iOS 를 공부하고 연구하는 대딩 ( 대학생 ) 이구요!

같은 분야를 공부하는 분들에게 조금이라도 도움이 주고 싶어서 공부하는 것들을 공유합니다.

제 3자가 있다고 가정하고 설명하기 때문에 존대를 하지 않는점 이해 부탁드립니다.

공유가 미래 라고 생각합니다. 

한국의 모든 개발자분들 존경합니다!

---

• Swift version : Swift 4.2  ( 18.09. 01 ~ ) Swift 언어
• 참고한 것들
• DataStructures and Algorithms in Swift
• Swift-Algorithm-club 깃허브 
• 스위프트 데이터 구조와 알고리즘

• 씩이 Github
• 자료구조 소스파일 있습니다.
• iOS 관련 자료들, 정보들 정리해 두었습니다.

• 스위프트로 구현한 자료구조 : DataStructures in Swift4
• Swift4 : 연결리스트 (1 / 3) : #LinkedList : #DataStructrue : #자료구조
  
• Swift4 : 연결리스트 (2 / 3) : #LinkedList : #값 추가하기, push, append : #값 삽입하기,insert
• Swift4 : 연결리스트 (3 / 3) : #LinkedList : #값 제거하기, pop, removeLast, remove(at: )
• [스위프트 : 자료구조] 스택: Stack: 자료구조: DataStructure: 쌓기
• [스위프트 : 자료구조] 스택 : Stack : 프로토콜 지향 스택 구현하기
• [스위프트 : 자료구조] 큐 (1 / 4): Queue: #자료구조: #배열로 구현한 큐: #배열의원리
• [스위프트 : 자료구조] 큐 (2 / 4): Queue: #자료구조: #연결리스트: #더블연결리스트: #DoublyLinkedList
• [스위프트 : 자료구조] 큐 (3 / 4): Queue: #자료구조: #Stack으로 구현: #더블스택: #DoubleStack: #제일좋음
• [스위프트 : 자료구조] 큐 (4 / 4): Queue: #자료구조: #RingBuffer: #링버퍼로 구현한 큐: #고정된배열: #마지막!!
  
• [스위프트 : 자료구조] 큐: Queue: 프로토콜 지향 큐 구현하기
• 스위프트: 트리: Tree: #자료구조: #깊이우선탐색: #레벨정렬탐색: #검색알고리즘: Swift4
• 스위프트: 이진 탐색 트리(1 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• 스위프트: 이진 탐색 트리(2 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• [스위프트 : 자료구조] AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능오짐
• [스위프트:자료구조] 트라이: Trie: 문자열 찾기: 단어 찾기
  

• 스위프트로 구현한 알고리즘 : Algorithms in Swfit4
• [스위프트 : 알고리즘] 재귀호출 (1 / 6) : recursive: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
  
• [스위프트 : 알고리즘] 재귀 : 팩토리얼 (2 / 6) : factorial: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
• [스위프트 : 알고리즘] 재귀 : 거듭제곱 (3 / 6) : Power: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
• [스위프트 : 알고리즘] 재귀 : 피보나치 수열(4 / 6) : Fibonacci: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
  
• [스위프트 : 알고리즘] 재귀 : 하노이의 탑 (5 / 6) : Hanoi: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
  
• [스위프트 : 알고리즘] 재귀 : 최대공약수 (6 / 6) : GCD: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수

• Swift 주제별 분류
• [스위프트] 데이터 구조와 알고리즘을 배우는 이유
• Swift4 : 제어 전달 명령문( Control Transfer Statement ) : #continue, #break, #return 키워드
• Swift4 : 클래스와 구조체 : #값을 대하는 방식 : #참조타입, 값 타입 : #===
• Swift4 : 프로퍼티 : #Property : #get, set : #willSet, didSet
• Swift4 : 메소드 : #Method : #영향력 범위 : #self : #mutating : #값타입 수정
• Swift4 : 프로토콜 1 : #Protocol : #설계 : #요구사항 : #델리게이트 패턴 전처리 (1 / 2)
• Swift4 : 프로토콜 2 : #델리게이트 패턴 : #델리게이션 (2 / 2)
• Swift4 : 제네릭 : #Generics : #왜필요해? : #where키워드 : #제약사항걸기
• Swift4 : 자동 참조 카운팅 : #Automatic Referece Counting : #ARC :#강한참조 : #Strong Reference Cycle : #메모리 누수
• Swift4 : 클로저: Closure: #표현방식: #왜필요해?: #효율적: #간결성: #생략
• [스위프트 : 기초] 서브스크립트 : Subscript : 지름길
  
  
  

Trie : 트라이 

트라이가 뭐야?

• 트라이는 트리의 일종이야.
• 이진트리, 이진검색트리, AVL 트리 등등 이전에 구현했던 트리들은 이전 노드의 값과 연관성이 없고 
• 하나의 노드로 그 속에 포함된 값이나 숫자로 의미를 부여했었지? 
• 하지만 현실세계에서 하나의 노드가 가지는 값이 아니라, 공통 분모를 지닌 일련의 데이터 노드를 저장해야 하는 경우가 많거든?
• 예를 들어 전화번호부의 숫자들, 영어 단어에서 접두사, 접미사에 따라 나열되는 연관단어들.
• apple, banana, car, care, cared 라는 문자열이 트리에 저장되 있다고 해보자.
• cared 찾으려고 apple, banana 부터 cared 까지 트리에 있는 모든 단어를 검색한다면? 
• 단어가 몇 갠데 언제 다 찾고있냐.. 컴퓨터가 뭔죄야.
• 그래서 cared 를 찾으려면 car 까지 찾고 car 가 접두사인 단어들 3개 중에 cared 찾는거야.  매우 효율적이지? 

                      

트라이를 굳이 왜 쓰게 된걸까?

• 알파벳으로 이루어진 단어들이 몇개 없다면 효율성을 따지거나, 굳이 안따지거나 상관없겠지만
• 한 언어의 단어는 몇천 몇만 개가 훌쩍 넘어가기 때문에 메모리나 수행속도를 생각하지 않을 수 없어서 생긴 것이란 자연스러운 추측 해본다 ^^

트라이는 어떻게 이루어져 있어? ( 트라이의 특징이 뭐야? )

• 트라이는 한 단어안에 여러 단어가 있을 수 있어
• "cute" 를 표현하고 싶은데 그 안에 "cut" 도 포함되어 있는 것 처럼
• 이 문제를 해결하기 위해 표시를 해 줘야해. 점으로 찍어서 표시한다면 아래 그림과 같아.
• 이 점을 코드에선 terminating: Bool 로 표현했어!
• 트라이 트리는 루트 노드부터 시작해서 루트 노드의 자식노드 부터 내부 요소들이 포함되 있어. ( 이 경우엔 내부요소는 알파벳 이지? )

TrieNode 부터 구현하자

• 자식 노드들을 표현하기 위해 Dictionary를 사용하기 때문에 Key에 Hashable 프로토콜 채택
• ( 딕셔너리의 키 값은 Hashable 프로토콜을 채택해야 하는 해 )
• parent 프로퍼티가 다른 트리와의 차이점이지?
• 이 때문에 단어를 삭제하는 연산이 가능해. 
• weak 은 강한참조문제를 방지하기 위해 써준거야. 그냥 넘어가도 되지만 모른다면 여기
• isTerminating 은 위에서 설명한 점찍어주는 표현이야. 

public class TrieNode<Key: Hashable> { // 제네릭
    public var key: Key? // 노드의 데이터 
    public weak var parent: TrieNode? 
    // 부모노드 정보 가지고 있어야 삭제 연산을 구현 가능한데
    // 부모와 내가 서로 참조하고 있으면 강한참조문제가 발생할 가능성 있으므로 weak 써준거야.
    public var children: [Key: TrieNode] = [:] // 이진 트리와 다르게 자식 노드 오지게 많을 수 있지? dictionary
    public var isTerminating = false  // 한 단어면 끝에 점 표시했던거. 끝을 표시하는 용도.
    public init(key: Key?, parent: TrieNode?) {
        self.key = key
        self.parent = parent
    }
}
 

Trie 구현 하자

• Trie 클래스의 제네릭에 Collection 프로토콜을 채택하는 CollectionType 을 만들어준 이유는
• 반복문을 사용하기 위해서야. Collection 프로토콜을 채택하고 있는 객체만 반복문을 수행할 수 있어.
• 우리의 경우엔 알파벳을 정렬할 거니까  문자열이 되겠지? String 은 Collection 타입중 하나야.
• 시퀀스와 컬렉션 프로토콜에 대해 여기에서 간략하게 설명하고 있어.

public class Trie<CollectionType: Collection> where CollectionType.Element: Hashable {
    // Trie 의 제네릭 타입인 CollectionType 은 Collection 프로토콜을 채택한 것이어야.
    // 그러한 CollectionType 중에 Element 가 Hashable 프로토콜을 채택한 것이어야 함.
    public typealias Node = TrieNode<CollectionType.Element> // 너무 기니까
    
    private let root = Node(key: nil, parent: nil) // 루트 노드
    
    public init(){ }
}
 

insert 메소드 구현 하자

• 트라이에 한 단어를 추가할 때 사용하는 메소드

    public func insert(_ collection: CollectionType) {
        var current = root // 루트를 시작으로 추적하겠다는 아이디어
        
        for element in collection { // 추가하는 과정.
            // for loop 에 collection 쓸 수 있는 이유는 Collection protocol 채택했기 때문
            if current.children[element] == nil {  // 없는 거면 새로운 인스턴스 만든다.
                current.children[element] = Node(key: element, parent: current)
            }
            current = current.children[element]! // 반복문 다음입력으로~
        }
        current.isTerminating = true // 단어 완성 시켰으면 마지막 알파벳에 점찍어주기~
    }

contains 메소드 구현하자!

• 트라이에 찾고자 하는 단어 포함되어 있는지 확인할 수 있는 메소드
• insert 와 동일한 아이디어

    public func contains(_ collection: CollectionType) -> Bool{
        var current = root
        
        for element in collection {
            guard let child = current.children[element] else { // 노드가 nil 이면 없는거니까.
                return false // 끝까지 와서 일치하는게 없으면 false 반환
            }
            current = child // 입력 다음입력으로 변화
        }
        return current.isTerminating // 있다면 끝 부분 isTerminating 반환.
    }

remove 메소드 구현하자!

• 처음에 점 찍혀있는거 먼저 지워주고 
• 여기에서 current.isTerminating 이 true 면 current 가 루트노드가 아니라는 것 까지 체크하쥬?
• 이 시점에서 고찰에 빠지기 시작하는데 지우려는 단어 중간에 다른 단어가 끼어있다면 ?
• 예를들어 cut , cute , cuted 가 들어있는 트라이를 생각해보자.

•  cut 지우려는데 cute 은 다른 단어이므로 지워지면 오류잖아? -> 자식노드의 여부로 판단
• current.children.isEmpty

• cuted 지우려는데 cute 는 다른 단어이므로 isTerminating 이 true 인 상태일 거잖아? -> current 의 isTerminating 여부로 판단
• !current.isTerminating
• 위에 guard 로 이미 확인했다고 생각할 수 있는 시점인데 위와 아래의 current 는 다른거야~ 
• 아래의 current 는 한칸 위로 올라간 후의 current 임을 주의
• 제거연산에서 current.parent 프로퍼티를 이용해서 current 노드를 제거하므로 parent 프로퍼티에 weak 키워드 붙여준거야.
• 강한 참조 사이클에 걸릴 수 있으니까. 모르겠다면 여기 걍넘어가도 됨^^

    public func remove(_ collection: CollectionType) {
        
        var current = root
        for element in collection { 
            guard let child = current.children[element] else { return }
            current = child
        }
        guard current.isTerminating else { return print("완성 단어가 아님.") } 
        // dot 찍혀있는지 확인. 정확한 단어 찾았는지 확인
        // 동시에 루트노드가 아니란 것도 알 수 있음.
        current.isTerminating = false // dot 먼저 해제 시켜주구 먼저 지우구.
        while current.children.isEmpty && !current.isTerminating{ 
            // 1. 자식 노드가 비어있지 않으면 중복되지만 더 긴 단어가 있다는 것이므로 삭제하면 안돼!
            // 2. dot 찍혀있으면 다른 단어가 있는 것이니 더 이상 지우면 안돼
            current.parent!.children[current.key!] = nil 
            current = current.parent!
        }
    }

collections 메소드 구현하자 . 접두사로 검색하면 검색되는 단어 반환해 주는 메소드임

• 이거 하려고 트라이 만든거쥬?
• RangeReplaceableCollection 프로토콜을 채택한 이유는 prefix 에 append 메소드 쓰기 위해서야.
• RangeReplaceableCollection 을채택하지 않으면 append 메소드 쓸 수 없고 우리가 쓰는 배열이 이 프로토콜을 채택해서 append 메소드 쓸 수 있는거야.
• 재귀호출 로 반복시킬 예정이야.
• 재귀호출는 종료조건과 문제의 범위가 작은 방향으로 간다는 조건을 만족해야 하는데 잘 모른다면 여기에서 볼 수 있어!

extension Trie where CollectionType: RangeReplaceableCollection {
    // RangeReplaceableCollection 프로토콜은 Collection 프로토콜을 상속한 프로토콜
    // Array 의 append 메소드는 Array가 RangeReplaceableCollection 프로토콜을을 상속해서 쓸 수 있는 것!
    public func collections(startingWith prefix: CollectionType) -> [CollectionType] {
        var current = root
        for element in prefix {
            guard let child = current.children[element] else { return [] } // if 문 실행해보기
            current = child
        }
        return collections(startingWith: prefix, after: current)
        // 접두어 끝이 현재의 현재 노드니까 현재노드에 딸려있는 단어들 배열로 가져올 메소드 따로 만들자.
    }
    
    private func collections(startingWith prefix: CollectionType,
                             after node: Node)                     
                             -> [CollectionType] 
    {
        var result = [CollectionType]() // 단어들 여기에 담을거야
        if node.isTerminating { // prefix 자체가 한 단어이면 반환배열에 포함시켜야지?
            result.append(prefix) 
        }
        for child in node.children.values { 
            // values 는 dictionary 구조체의 프로퍼티임^^
            // 자식 노드의 수만큼만 반복 => 자식노드 없으면 반복 안함.
            var prefix = prefix
            prefix.append(child.key!) 
            // 자식노드 있는지 확인 안하고 강제 언래핑 가능. 반복 횟수가 이미 정해저 있으니까.
            // prefix 는 RangeReplaceableCollection 프로토콜을 채택한 타입이기 때문에 append 메소드 사용 가능.
            result.append(contentsOf: collections(startingWith: prefix, after: child)) 
            // 재귀호출 시작, 1. 종료조건 : 반복문의 node.children.values 이 0 이면 종료 -> 만족
            // 2. 작은 방향으로 이루어 지는지 : prefix 가 커져서 트리의 자식노드인 하위로 이동하므로 문제의 범위는 작아짐. -> 만족
        }
        return result
    }
}
 

실행과 결과

전체 소스 코드