트라이(trie) 알고리즘

오늘은 트라이에 대해서 공부해보겠습니다.
사실 전화번호부 검색 알고리즘이 궁금해서 찾아보다가 트라이 개념이 나와서 시작하게 된 포스팅ㅇㅇ
그래서 이번 포스팅은 트라이 개념에 대해서 포스팅하고 다음은 트라이 한국어 탐색에 대해서 포스팅 예정입니다.

 

트라이란?
트라이(trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 검색 트리의 일종입니다.
일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조입니다.

 

트라이의 어원?
트라이가 왜 트라이인지 궁금해서 어원을 찾아봤습니다.
트라이의 개념은 1959년에 처음 공개되었고 검색을 뜻하는 retrieval(리트리벌)의 중간 음절에서 용어를 따왔다고 합니다.
당시에는 트리(tri:)로 불렀다고 하는데 기존에 존재하는 트리(tree)와 구분하기 위해서 트라이로 불렀다고 합니다.

 

트라이 원리
아래 왼쪽 그림은 apple, appear, appeal으로 트라이를 구성한 것입니다.

여기서 만약 appear을 찾는다고 가정해봅시다.
그럼 오른쪽 그림과 같이 a -> p -> p 순으로 문자 별 일치하는 노드를 찾아 e -> a -> r까지 내려가면 됩니다.
appear 문자열의 길이가 6이니 6번 타고 내려간 것처럼
트라이는 각 문자열의 길이만큼만 탐색하면 원하는 결과를 찾을 수 있습니다.
즉 길이가 k인 문자열이 주어졌을 때 O(k)으로 해당 문자열이 유효한 단어인지, 접두사인지 확인할 수 있습니다.
ㅇㅇ하나씩 비교해서 문자열 탐색하는 것보다 훨씬 효율적으로 탐색할 수 있습니다.
하지만 각 노드에 자식들에 대한 포인터들을 모두 저장하고 있다는 점에서 공간이 꽤 많이 사용된다는 단점도 있습니다.

 

트라이 관련 문제
Leetcode에 트라이를 직접 구현할 수 있는 문제가 있어서 들고 왔습니다.
208번 문제 Implement Trie (Prefix Tree)를 풀어보시면 어느 정도? 트라이에 대한 개념이 잡힐 것 같습니다.
해당 문제에서 구현해야 할 메소드는 총 3개로 아래와 같습니다. 
insert(_ word: String)
search(_ word: String) -> Bool
startsWith(_ prefix: String) -> Bool 

 

시작
딕셔너리를 활용해서 간결한 형태로 트라이를 구현해보겠습니다.
트라이를 저장할 TrieNode를 따로 선언해줍니다.

class TrieNode {
    var isWord = false
    var children = [Character: TrieNode]()
}

 

다음 삽입하는 메소드를 구현해보겠습니다.

func insert(_ word: String) {
    var node = root
    for char in word {
        if node.children[char] == nil {
            node.children[char] = TrieNode()
        }
        node = node.children[char]!
    }
    node.isWord = true
}

문자열 단어가 들어오면 for 루프를 통해 문자를 자식 노드로 붙여줍니다.
for 루프가 끝나면 해당 문자가 마지막이다 즉 단어임을 표시해주기 위해 isWord값을 true로 변경해줍니다.
? apple단어의 삽입 과정을 보겠습니다.

왼쪽 이미지는 apple을 넣은 후 트라이의 형태입니다.
즉 a부터 p p l e까지 각각의 문자가 이전 노드의 자식으로 저장이 됩니다.
그리고 e까지 for 루프를 통해서 돌고 나면 여기가 끝이다! 즉 단어임을 표시해주기 위해 isWord를 true로 변경해줍니다.

여기서 a로 시작하는 다른 단어(appeal, appear)가 추가로 들어온다고 하면 오른쪽 이미지와 같은 형태가 되겠죠.
apple, appeal, appear 단어는 app까지는 같기 때문에 같은 자식을 타고 내려가다가
달라지는 l, e 문자부터 서로 다른 노드로 분기됨을 확인할 수 있습니다.
그리고 마지막 노드(e, l, r)는 isWord값이 true가 됩니다.

ㅇㅇ트라이 트리는 삽입 시 루트부터 자식 노드가 깊어지면서 다진 트리 형태가 됩니다.

 

다음 검색하는 아래 두 메소드들을 구현해보겠습니다.
search(_ word: String) -> Bool
startsWith(_ prefix: String) -> Bool 
search(_ word: String) -> Bool는 단어가 존재하는지를 확인하는 메소드고 
startsWith(_ prefix: String) -> Bool는 해당 문자열로 시작하는 단어가 존재하는지를 확인하는 메소드입니다.
그렇기 때문에 두 메소드 동일하게 문자 단위로 깊이 탐색을 해야 합니다. 

func find(_ str: String) -> TrieNode? {
    var node = root
    for char in str {
        if node.children[char] == nil {
            return nil
        }
        node = node.children[char]!
    }
    return node
}

func search(_ word: String) -> Bool {
    if let node = find(word) {
        return node.isWord
    }
    return false
}

func startsWith(_ prefix: String) -> Bool {
    return find(prefix) != nil
}

두 메소드 동일하게 문자 단위로 깊이 탐색을 해야 하기 때문에 탐색을 위한 메소드를 따로 빼는 게 좋을 것 같습니다.
ㅇㅇ find(_ str: String) -> TreeNode? 메소드를 생성해줍니다.
문자열 단어를 전달받고 문자 단위로 파고 들어가면서
자식 노드가 있다면 즉 해당 문자가 자식으로 있다면
for 반복문을 끝까지 빠져나와 마지막 문자 노드를 리턴할 것이고 없다면 nil을 리턴해줍니다.

search(_ word: String) -> Bool는 단어가 존재하는지를 확인하는 메소드기 때문에 
find에 찾고자 하는 단어 word를 전달해 리턴되는 노드가 있는지 확인하고 리턴된 노드에 isWord값을 리턴합니다.
만약 find를 통해서 nil을 리턴 받는다면 if let 구문 안에 들어가지 않게 되고 false를 리턴해줍니다.
예를 들어 트라이에 apple이 존재하는데 find에 apple을 넣었다면 a -> p -> p -> l -> e 탐색하면서 e에 대한 노드가 리턴되고 isWord가 true기 때문에 apple이 존재한다라고 판단할 수 있습니다.
하지만 트라이에 apple이 존재하는데 find에 app을 넣었다면 a -> p -> p 탐색하면서 p에 대한 노드가 리턴되고 isWord가 false기 때문에 app이 존재하지 않는다고 판단할 수 있습니다.

startsWith(_ prefix: String) -> Bool는 해당 문자열로 시작하는 단어가 존재하는지를 확인하는 메소드기 때문에
find에 찾고자 하는 단어 prefix를 전달해 리턴되는 노드가 있으면 true를 리턴하고 없으면 false를 리턴해줍니다.
예를 들어 트라이에 apple이 존재하는데 find에 app을 넣었다면 a -> p -> p 탐색하면서 p에 대한 노드가 리턴되고 
즉 find에서 리턴되는 노드(p)가 있기 때문에 true가 리턴되고 app으로 시작하는 단어가 존재한다고 판단할 수 있습니다. 

 

전체적인 코드
(스위프트 작성)

// 트라이 노드
class TrieNode {
    var isWord = false
    var children = [Character: TrieNode]()
}

class Trie {
    let root = TrieNode()
    
    // 단어 삽입 부분
    func insert(_ word: String) {
        var node = root
        for char in word {
            if node.children[char] == nil {
                node.children[char] = TrieNode()
            }
            node = node.children[char]!
        }
        node.isWord = true
    }
    
    // 단어 존재 여부 판별
    func search(_ word: String) -> Bool {
        if let node = find(word) {
            return node.isWord
        }
        return false
    }
    
    // 문자열로 시작 단어 존재 여부 판별
    func startsWith(_ prefix: String) -> Bool {
        return find(prefix) != nil
    }
    
    // 문자 단위로 깊이 탐색하기 위함
    func find(_ str: String) -> TrieNode? {
        var node = root
        for char in str {
            if node.children[char] == nil {
                return nil
            }
            node = node.children[char]!
        }
        return node
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.Insert(word);
 * bool param_2 = obj.Search(word);
 * bool param_3 = obj.StartsWith(prefix);
 */

 

 

resource:
python algorithm book
cracking the coding interview book
https://leetcode.com/problems/implement-trie-prefix-tree/
https://en.wikipedia.org/wiki/Trie