트라이 : 텍스트 데이터 특화 트리

hy1as ㅣ 2023. 3. 27. 16:04

검색창의 자동 완성 기능의 동작 방법에 대해 궁금해하신 적이 있으신가요?
단어의 자동완성을 위해 검색창은 DB에 저장된 전체 데이터에 접근합니다.
이런 단어들에 대해서 어떤 자료구조로 저장하고 있을까요?
정렬되지 않은 배열로 저장되었다면 탐색 시 전체 배열을 탐색해야 하기에 $ O(N) $ 의 시간이 걸리게 됩니다.
정렬된 배열은 어떨까요?
정렬되어 있기 때문에 단계를 진행할수록 많은 후보군이 사라지고 $ O(logN) $ 만큼의 단계 안에 탐색을 마칠 수 있습니다.
정렬된 배열도 매우 빠르지만 무려 상수 시간 안에 자동 완성 기능을 실행할 수 있는 자료 구조가 존재합니다.
오늘은 해당 자료구조에 대해 포스팅 해보도록 하겠습니다.

1. 트라이 (Trie)란?

트리의 한 종류인 트라이 (trie)는 자동 완성과 같은 텍스트 기반 기능에 이상적입니다.
대부분의 트리 처럼 트라이도 다른 노드를 가리키는 노드들의 컬렉션입니다.
트라이는 이진 트리와 달리 자식 노드의 갯수 제한이 존재하지 않습니다.
각 트라이 노드마다 해시테이블을 포함하며 키는 문자, 값은 다른 노드입니다.

트라이 노드를 코드로 구현하면 다음과 같이 작성됩니다.

class TrieNode {
	// 해시 테이블
    children;

	// 노드 생성 시 해시 테이블 생성
    constructor() {
        this.children = new Map()
    }
}

완벽하게 트라이를 생성하려면 루트 노드를 추적하는 Trie 클래스를 별도로 필요합니다

class Trie {
    root;

    // Trie 클래스 생성 시 비어있는 root node 생성
    constructor() {
        this.root = new TrieNode()
    }
}

이렇게 구현해서 트라이 클래스를 생성하면 비어있는 루트 노드와 함께 생성됩니다.

2. 단어 저장

이번엔 트라이가 단어를 어떻게 저장하는지 살펴보도록 하겠습니다.
트라이는 각 단어의 각 문자를 각각의 트라이 노드로 바꿔 저장합니다.

노드를 자세히 보면 마지막 문자 노드 또한 키를 가지고 있습니다.
바로 "*" (Asterisk) 이고 이는 단어의 끝을 나타냅니다.
해당 노드에서 완성되는 단어와 끝이 나지 않는 더 긴 단어를 구별해 주기 위해 존재합니다.

3. 트라이 검색

트라이 연산 중 가장 대표적인 연산으로 트라이에 어떤 문자열이 존재하는지 확인하는 연산입니다.
문자열이 완전한 단어인지, 문자열이 최소한 어떤 단어의 접두사인지 알아내는 것이 목적입니다.
접두사를 찾다 보면 완전한 단어도 자연스럽게 찾아낼 수 있습니다.
접두사 검색 알고리즘은 다음과 같은 단계를 수행합니다.

currentNode 변수 생성 후 root node를 가리킴
검색 문자열의 각 문자를 순회
검색 문자열의 각 문자를 가리키며 currentNode의 해시 테이블에 해당 문자를 가리키는 키가 존재하는지 확인
자식이 없으면 해당 문자열은 존재하지 않는 것 => null 반환 후 검색 종료
자식이 있으면 currentNode를 해당 자식 Node로 업데이트
검색 문자열의 마지막 문자까지 순회했으면 해당 검색 문자열은 트라이 내에 존재

코드로 다음과 같이 구현할 수 있습니다.

search(word) {
        // 순회중인 현재 노드 ( root에서 시작 )
        let currentNode = this.root
        // 문자열 => 문자 배열
        const chars = [...word]
        for (let i = 0; i < chars.length; i++) {
            // 현재 문자
            const char = chars[i]
            // 현재 노드의 해시 테이블에 현재 문자가 존재 하는지 여부
            const nextNode = currentNode.children.get(char)
            // 존재 한다면 해당 노드로 이동
            if (nextNode != null) {
                currentNode = nextNode
                // 존재 하지 않는다면 null 반환
            } else {
                return null;
            }
        }
        // 마지막 노드 ('*') 반환
        return currentNode
}

검색의 시간 복잡도는 어떻게 될까요?

해시 테이블의 접근은 $ O(1) $ 의 시간이 걸립니다.
문자열 내의 문자의 수만큼 해시 테이블의 접근 단계가 걸리게 되므로 알고리즘은 검색 문자열 내 문자 수만큼 걸리게 됩니다.
단계 수가 검색 문자열의 길이에 따라 달라지기 때문에 상수는 아닙니다.

하지만 자료 구조 내의 데이터는 아니기 때문에 $ O(N) $ 으로 나타낼 수도 없습니다.
많은 참고자료에서 이 복잡도를 $ O(K) $라고 부르고 있습니다.
$ K $ 는 검색 문자열 내의 문자 수를 나타냅니다.
검색 문자열마다 길이가 다르기 때문에 $ O(K) $ 가 상수는 아니지만 상수 시간 복잡도라고 정의할 수 있습니다.
자료구조 내 데이터 양이 달라진다 하더라도 검색하고자 하는 문자열의 길이만 같다면 걸리는 시간이 변하지 않기 때문입니다.

4. 트라이 삽입

트라이에 새 단어를 삽입하는 과정은 기존 단어를 검색하는 과정과 유사합니다.

currentNode 변수 생성 후 root node를 가리킴
검색 문자열의 각 문자를 순회
검색 문자열의 각 문자를 가리키며 currentNode의 HashTable에 해당 문자를 가리키는 키가 존재하는지 확인
자식이 있으면 currentNode를 해당 자식 Node로 업데이트
자식이 없으면 자식 노드를 생성하고 currentNode를 생성된 노드로 업데이트
삽입할 단어의 마지막 문자를 삽입했다면 마지막 노드에 '*' 자식 노드를 추가해 단어가 끝났음을 알림

코드로 다음과 같이 구현할 수 있습니다.

 insert(word) {
        const chars = [...word]
        // 순회중인 현재 노드 ( root에서 시작 )
        let currentNode = this.root
        for (let i = 0; i < chars.length; i++) {
            const char = chars[i]
            // 현재 노드에 현재 문자가 있는지 확인
            const nextNode = currentNode.children.get(char)
            // 존재 한다면
            if (nextNode != null) {
                // 다음 노드로 이동
                currentNode = nextNode
                // 존재하지 않는다면
            } else {
                // 새로운 노드 생성 후 다음 노드로 이동
                const newNode = new TrieNode()
                currentNode.children.set(char, newNode)
                currentNode = newNode

            }
        }
        // 문자열 마지막 노드에 * 삽입
        currentNode.children.set('*', null)
}

삽입 또한 검색처럼 $ O(K) $ 의 단계가 걸리게 됩니다.

5. 자동 완성

이제 포스트의 시작에서 언급했던 자동 완성을 구현해 보도록 하겠습니다.
우선 보조할 Method를 우선 만들어 보겠습니다.
트라이 내 모든 단어를 배열로 반환하는 Method입니다.
실제로 모든 단어를 반환할 일은 드물지만 시작 노드를 지정하고 그 노드부터 시작되는 모든 단어를 나열할 수 있습니다

 // 현재 노드 아래 모든 문자열 찾아 순회
    collectAllWords(node = null, word = '', words = []) {
        // 입력된 노드가 없다면 root에서 출발
        let currentNode = node === null ? this.root : node
        // 현재 노드의 자손 노드 순회
        currentNode.children.forEach((value, key) => {
            if (key === '*') {
                // 문자열의 마지막 도달 시 Memoization
                words.push(word)
            } else {
                // 자손 노드에 대한 재귀 호출
                this.collectAllWords(value, word + key, words)
            }
        })
        // Memoization 배열 반환
        return words
    }

이제 앞서 구현한 모든 단어를 출력하는 함수를 통해 자동 완성 Method를 만들어 보겠습니다.

autocomplete(prefix) {
        // 입력된 문자열의 마지막 노드 검색
        let currentNode = this.search(prefix);
        // 발견 시
        if (currentNode != null) {
            // 현재 노드 부터 입력된 문자열로 시작한는 모든 문자열 반환
            return this.collectAllWords(currentNode, prefix)
            // 미발견 시
        } else {
            return null;
        }
}

6. 추가 기능 : 접근 횟수

자동 완성 데이터를 제공하는데 사용자에게 더 유용한 데이터를 제공하고 싶습니다.
가장 자주 쓰이는 데이터를 제공한다면 더 만족할 만한 자동 완성 기능이 될 듯합니다.
해당 기능을 구현하기 위해 단어 접근 횟수 데이터를 함께 저장하면 되겠습니다.
앞서 트라이 구현 시 키 "*"를 할당할 때 그 값을 null로 초기화했습니다.
해당 값에 아무 의미가 없었기 때문인데요
이 값을 활용해 접근 횟수를 넣어주면 해당 데이터를 통해 접근 횟수로 정렬하여 사용자에게 제공할 수 있겠습니다.

{ "*" : 10 }

7. 추가 기능 : 자동 수정 기능

사용자가 입력한 오탈자를 올바른 단어로 바꿔주는 기능의 구현입니다.

  autocorrect(word) {
        let currentNode = this.root;
        let ret = ''
        const chars = [...word]
        for (let i = 0; i < chars.length; i++) {
            const char = chars[0]
            const nextNode = currentNode.children.get(char)
            // 일치 하는 ( 문자들이 존재하는 ) 노드 까지 이동
            if (nextNode != null) {
                ret += char
                currentNode = nextNode
            } else {
            // 일치 하지 않는 문자 노드 발견 시
            // 지금까지 일치한 문자열을 prefix로 하여 나머지 문자열 후보 중 첫번째 문자열 반환
                return ret + this.collectAllWords(currentNode)[0]
            }
        }
        // 모든 문자가 트라이에 존재한다면 input 반환 
        return word
    }

'Computer Science > 자료구조' 카테고리의 다른 글

그래프 (2) : 탐색의 방향? (0)	2023.03.30
그래프 (1) : SNS가 이거에요 (0)	2023.03.29
힙과 우선순위 큐 : 제일 큰 값, 작은 값 (0)	2023.03.25
이진 탐색 트리 : 검색, 삽입, 삭제 모두 O(logN) (0)	2023.03.24
연결리스트 : 대량 삽입과 삭제에 유리한 Node 기반 자료구조 (0)	2023.03.18

꾸준합니다