트라이 해보는 것도 나쁘지 않다.

유방현·2022년 10월 1일
자료구조 및 알고리즘
0

자료구조와 알고리즘

목록 보기
17/17

자동완성을 생각해보자. 자동완성이 될 단어는 사전에 저장되어있다. 그렇다면 내가 원하는 단어를 핸드폰에서 나한테 알려주기 위해 사전에 등록된 모든 단어를 확인해야 할 것이다.

이러한 동작은 O(N) 시간 복잡도를 가진다.

그리고 배열에 단어가 알파벳 순으로 정렬되어 있다면 O(logN)에 시간 복잡도를 가질 것이다.
하지만 특수한 트리 기반 자료구조를 사용하면, 이 보다 더욱 빠른 O(1)만에 자동 완성 단어를 찾을 수 있다.

트라이는 자동 완성, 수정 같은 중요한 기능을 지원한다. 또한 IP 주소나 전화번호를 처리하는 애플리케이션에도 사용된다.

트라이

트라이는 트리의 한 종류로, 자동완성 같은 텍스트 기반 기능에 이상적이다.

트라이는 프리픽스 트리, 디지털 트리라고 불리기도 한다.

트라이는 여러가지 방법으로 구현할수 있다.

트라이 노드

대부분의 노드처럼 트라이 노드 또한 다른 노드를 가리키는 노드들의 컬렉션이다. 하지만 트라이 노드는 자식 노드 개수에 제한이 없다.

class TrieNode<K,V> {
    private Hashtable<K,V> hashtable;
    public TrieNode(){
        hashtable = new Hashtable<>();
    }
}

알파벳순으로 정렬하는 트라이를 구현한다고 가정하자. 이 때 트라이의 키는 알파벳이고, 값은 다른 트라이 노드를 가르킨다. 그렇기 트라이 노드는 해시 테이블만을 포함하고 있다.

class Trie{
    TrieNode root;
    public Trie(){
        this.root = new TrieNode();
    }
}

트라이를 생서하려면 트라이 노드를 관리하기 위한 트라이 클래스가 필요하다. 이 코드는 빈 트라이 노드를 트라이의 루트로 가르키게 한다.

단어 저장

그렇다면 트라이에서는 어떻게 단어를 저장할까??

트라이 노드가 ace라는 단어를 포함하고 있다면, 이 때 트라이 노드의 루트 노드는 a를 키 값으로 가지고 있다. a 노드의 하위 노드는 c를 c노드의 하위 노드는 e를 가리키고 있다. 이렇게 노드를 따라서 내려가면 ace라는 단성가 완성된다. 이 때 단어가 완성 됐다는 것을 알리기 위해 마지막 노드에 키로 *을 넣고 값으로 null을 넣는다.

별표의 필요성

트라이가 bat, batter라는 단어를 포함하고 있다. 이 때 트라이에서는 각 단어를 어떻게 찾을 수 있을까??

바로 이 때 *가 중요해진다. 루트 노드에서 두 단어를 찾기 위해서 하위 노드를 따라서 내려간다. 이 때 b -> a -> t순으로 노드를 탐색할 것이다. 이 때 t 노드에 값에는 *,t노드가 존재 한다. *를 만났기 때문에 bat라는 단어가 하나의 완성된 단어라는 걸 알수 있게된다.

따라서 단어가 하나의 완성된 단어라고 컴퓨터에게 알려줄수 있는 수단(*)은 아주 중요하다.

트라이 검색

검색은 트라이에 대표적인 연산이다. 검색의 목적은 크게 두가지다. 하나는 문자열이 완전한 단어인지 확인하는 것이고, 또 다른 하나는 최소한 어떤 단어의 접두사인지 알아내는 것이다.

접두사 검색 알고리즘은 다음과 같이 동작한다.
1. currentNode라는 변수를 생성한다. 알고리즘을 시작 할 때 이 노드는 root를 가르킨다.
2. 검색 문자열의 각 문자를 순회한다.
3. 검색 문자열의 각 문자를 가리키면 currentNode에 그 문자를 키로 하는 자식이 있는지 본다.
4. 자식이 없으면 검색 문자열이 트라이에 없다는 뜻이니 null을 반환한다.
5. currentNode 현재 문자를 키로하는 값이 있다면 currentNode 그 자식 노드로 업데이트 한다. 이어서 2단계로 돌아가서 각 내 문자를 순회한다.
6. 검색 문자를 끝까지 순회했으면, 문자열을 찾았다는 뜻이다.

코드 구현: 트라이 검색

class Trie{
    TrieNode root;
    TrieNode currentNode;
    public Trie(){
        this.root = new TrieNode();
    }
    public TrieNode search(String data){
        this.currentNode = root;
        for (int i = 0; i < data.length(); i++){
            //현재 노드에 현재 문자를 키로하는 자식이 있으면
            if (currentNode.getHashtable().get(data.charAt(i)) != null)
                // 현재 노드를 자식 노드로 업데이트
                currentNode = (TrieNode) currentNode.getHashtable().get(data.charAt(i));
            else
                //현재 노드의 자식중에 현재 문자가 없으면 트라이에 해당 단어는 존재 X
                return null;
        }
        return currentNode;
    }
}

트라이 검색의 효율성

트라이 검색은 속도는 매우 빠르다. 정렬된 배열의 경우 검색하는데 O(logN)이 걸린다. 하지만 트라이 검색의 경우 문자열의 길이만큼 동작하면 검색을 할수 있다. 예를 들어 cat라는 문자열이 있다면 3단계 걸린다.

하지만 트라이의 시간 복잡도는 O(1)아니다. 문자열이 길이가 얼마나 클지 모르기 때문이다. 또한 O(N)도 아니다. N은 트라이 안에 데이터 개수이다. N의 크기는 문자열 길이보다 훨씬 크다.

이러한 트라이의 시간 복잡도를 O(K)라고 나타낸다. K는 검색 문자열 내 문자 수다.

트라이 삽입

트라이 삽입 알고리즘은 다음과 같이 동작한다.
1. rootNode를 가르키는 currentNode를 만든다.
2. 검색 문자열의 각 문자를 순회한다.
3. 검색 문자열의 각 문자를 가르키며 currentNode에 그 문자를 키로하는 자식이 있는지 확인한다.
4. 자식이 있으면 currentNode를 자식 노드로 업데이트하고 2단계로 돌아간다.
5. 자식이 없다면 자식 노드를 생성하고, currentNode를 이 새 노드로 업데이트한다. 2단계로 돌아가 검색 문자열 내 다음 문자로 넘어간다.
6. 삽입할 단어의 마지막 문자까지 삽입했다면, 마지막 노드에 *자식을 추가해 단어가 끝났음을 알린다.

코드 구현: 트라이 삽입

    public void insert(String data){
        currentNode = root;
        for (int i = 0; i < data.length(); i++){
            // 현재 노드에 현재 문자를 키로 하는 자식이 있으면
            if (currentNode.getHashtable().get(data.charAt(i)) != null)
                // 자식 노드를 따라간다.
                currentNode = (TrieNode) currentNode.getHashtable().get(data.charAt(i));
            // 자식이 없다면
            else {
                // 새로운 노드를 생성하고
                newNode = new TrieNode();
                //그 문자를 새 자식으로 추가한다.
                currentNode.getHashtable().put(data.charAt(i),newNode);
                // 새로운 노드를 따라간다.
                currentNode = newNode;
            }
        }
        //단어 전체를 삽입 후 마지막으로 *을 추가한다.
        currentNode.getHashtable().put('*',new TrieNode<>());
    }

자동 완성 개발

자동 완성 기능을 좀 더 쉽게 개발하기 위해 이 기능을 돕는 단순한 함수를 먼저 만든다.

단어 수집

추가할 메서드는 트라이 내의 모든 단어를 배열로 반환하는 메서드다. 실제로 사전 전체를 나열할 일은 아주 드물지만, 이 메서드는 트라이의 어떤 노드든 인수로 받아 그 노드로부터 시작되는 모든 단어를 나열할 수 있다.

    public static ArrayList collectAllWords(TrieNode node, String word, ArrayList<String> words) {
        // 메소드는 인수 세 개를 받는다. 첫 번째 인수인 node는 그 자손들에게서 단어를 수집할 노드이다.
        // 두 번째 인수인 word는 빈 문자열로 시작하고, 트라이를 이동하면서 문자가 추가된다.
        // 세 번째 인수인 words는 빈 배열로 시작하고, 함수가 끝날 때 모든 단어를 포함한다.

        //현재 노드는 첫 번째 인자로 전달 받은 node이다.
        TrieNode currentNode = node;

        // 현재 노드의 모든 자식을 순회한다.
        currentNode.hashtable.forEach((key,value) ->
                // 현재 키가 *이면 완전한 단어에 도달했다는 뜻이므로 words 배열에 word를 추가한다.
                {
                    if ((Character) key == '*') {
                        words.add(word);
                    }
                    else // 아직 단어 중간이면 그 자식 노드에 대해 이 함수를 재귀적으로 호출한다.
                    collectAllWords((TrieNode) value, word+key, words);
                });
        return words;
    }

메서드는 node, word, words라는 인자를 받는다. node는 트라이 내 어떤 노드에서 단어 수집을 시작할지 명시한다. 만일 이 노드를 넘기지 않으면 메서드는 루트 노드에서 시작해 전체 트라이 내의 모든 단어를 수집한다.

word와 words 인자는 메서드 재귀 호출에 쓰이므로 처음에 명시하지 않아도 된다.
words 인자의 기본값은 빈 배열이고, 트라이에서 완전한 단어를 찾을 때마다 그 문자열을 배열에 추가해 함수 마지막에 반환한다.
word 인자의 기본값은 빈 문자열이고, 트라이 사이를 옮겨 다니며 word에 문자를 추가한다. "*"가 나오면 완전한 단어라는 뜻이니 words 배열에 추가한다.

currentNode가 루트 노드라고 가정하고, for문으로 currentNode의 자식 해시 테이블에 있는 모든 키-값 쌍을 순회한다.
이때 key는 항상 문자 하나짜리 문자열이고, childNode는 또 다른 TrieNode 인스턴스다.

else 절에서 collectAllWords 메서드를 재귀 호출하며 첫 번째 인자로 childNode를 전달한다. 이러한 방식으로 트라이를 순회한다.
두 번째 인자로 word + key를 전달한다. 단어를 완성하기 위해 트라이의 각 노드를 옮겨 다니며 현재 word에 key를 계속 추가한다.
마지막 인자로 words 배열을 넘겨주며 완전한 단어를 수집해 목록을 생성한다.

기저 조건은 키가 "*"일 때, 즉 한 단어를 완성했을 때이다. 이 때의word를 words 배열에 추가한다.

함수 마지막에서 words 배열을 반환한다.

재귀 연습(walk-through)

단순 트라이를 사용해 단어 수집 과정 확인해 보자. 트라이에는 can과cat이라는 두 단어가 들어있다.

cant
an, t**
  1. 첫 번째 호출: collectionAllWords를 처음 호출할 때 currentNode는 root-node로 시작하며, word는 빈 문자열, words는 빈 배열이다.
  • word = ""
  • words = []

루트 노드의 자식을 순회한다. 루트 노드에 자식 키는 c하나 이고, 이 키는 한 자식 노드를 가르킨다. 이 자식 노드에 collectionAllWords를 재귀적으로 호출하기 전에 현재 호출을 호출 스택에 추가해야 한다.
이어서 자식 노드인 c에 대해 collectionAllWords를 재귀적으로 호출한다. 이때 words 인수에 wo여rd + key를 전달한다. word는 비어 있고, key는 c이므로 word + key = c이다. 또한 여전히 빈 배열인 words도 전달한다.

  • word = "c"
  • words = []
  • 호출 스택 : collectionAllWords(root,"",[])
  1. 두 번째 호출: 현재 노드의 자식 노드를 순회한다. c 노드의 자식 노드는 a하나다.
    따라서 word = ca가 된다.
  • word = "ca"
  • words = []
  • 호출 스택 : collectionAllWords(root,"",[]),collectionAllWords(a node,"c",[])
  1. 세 번째 호출: 현재 노드의 자식은 n과t를 순회한다. 우선 n부터 순회한다.
  • word = "can"
  • words = []
  • 호출 스택 : collectionAllWords(root,"",[]),collectionAllWords(a node,"c",[]),collectionAllWords(n node,"ca",[])
  1. 네 번째 호출 : 현재 노드의 자식들을 순회한다. 이떄 자식은 * 하나 뿐이다. 즉 기저 조건이다. 현재 word인 can을 words 배열에 추가한다.
  • words = [can]
  1. 다섯 번째 호출 : 호출 스택에서 가장 최근 호출을 팝한다. 자식 키가 n과t이고 word가 ca였던 노드에 대한 collectionAllWords이다.
  • word = "ca"
  • words = [can]
  • 호출 스택 : collectionAllWords(root,"",[]),collectionAllWords(a node,"c",[])
    배열은 값을 추가해도 메모리에서 계속 같은 객체이므로 배열을 호출 스택 위아래로 전달할 수 있다.

    반면 문자열을 수정하면 문자열 객체를 수정하는 것이 아니라 새 문자열을 생성한다. 따라서 word를 수정해도 이전에 호출한 스택에는 호출할 당시 word의 값만 접근할 수 있다.
  1. 여섯 번째 호출 : 이미 키 n은 순회 했으니 루프에서 이제 키 t를 할 차례다. 자식 노드t에 collectionAllWords를 다시 호출한다. 따라서 collectionAllWords(t node,"ca",[])를 호출 스택에 다시 추가한다.
  • word = "cat"
  • words = [can]
  • 호출 스택 : collectionAllWords(root,"",[]),collectionAllWords(a node,"c",[]),collectionAllWords(t node,"ca",[])
  1. 현재 노드의 자식을 순회한다. 이때 자식은 * 하나 뿐이므로 현재 word를 words에 추가한다.
  • words = [can,cat]

    호출 스택에서 각 호출을 팝하며, words 배열을 반환하고, 실행을 완료함으로써 호출 스택을 해제할 수 있다. 이 모든 호출을 시작시켰던 첫 번째 호출, 즉 마지막 호출도 words를 반환하며 끝낸다. 이 배열에 문자열 can과cat이 있으니 트라이에 전체 단어 목록을 성공적으로 잘 반환했다.

자동 완성 마무리

public ArrayList autocomplete(String prefix){
        currentNode = search(prefix);
        if(currentNode == null) return null;
        return  collectAllWords(currentNode, prefix, new ArrayList<String>());
    }

autocomplte는 문자열을 인자로 받는다. 해당 문자열이 트라이에 존재 한다면, 해당 문자열을 포함하는 모든 단어를 collectAllWords에서 찾아서 반환한다. 존재 하지 않는다면 null을 반환한다. 따라서 최종적으로 사용자 접두사로 시작하는 모든 배열을 반환하고, 이 배열은 자동 완성 옵션으로 사용자에게 표시된다.

값을 포함하는 트라이: 자동 완성 업그레이드

사용자가 입력할 만한 단어를 전부 표시하는 건 꼭 훌륭하지만은 않다. 16개의 단어가 해당한다고 모두 보여줄 필요는 없으니, 널리 쓰이는 단어만 추려서 보여주는 편이 낫다.

가장 많이 쓰이는 단어 위주로 옵션을 표시하려면 트라이에 단어 인기도 데이터를 함께 저장해야 한다.

각 단어의 완성을 나타내는 노드인 "*"의 값으로 null을 할당했는데, 이 값에 인기도 데이터를 저장하면 된다. 이후 트라이 내 단어를 수집할 때 점수를 함께 수집해 인기도 순으로 단어를 정렬하면 된다.

결론

이진 탐색 트리, 힙, 트라이 세 종료의 트리를 배웠다. 이 밖에 AVL 트리, 레드-블랙 트리, 2-3-4 트리 등 많은 종류의 트리가 있다. 각 트리마다 특정 상황에 유용하게 쓰일 만한 고유한 성질과 동작을 지닌다. 다양한 종류의 트리를 알고 있으면 많이 도움이 될 것이다. 지금까지 배운 내용으로 다양한 트리가 어떠한 문제를 해결할 수 있는 알 수 있었다.

profile
유방현
코딩하는 직장인
이전 포스트

힙으로 우선순위 유지하지

0개의 댓글