[Data Structure] Trie를 이용한 자동완성 구현

 

 

오늘은 이렇게 검색어를 치면 그 단어를 포함한 단어를 보여주는

자동완성을 구현해볼거에요

구현 하는 방법은 여러가지가 있을 수 있겟지만!

우선 방대한 리스트가 있거나 유동적인 데이터라면

서버와 통신을 통해서 자동완성을 구현하는 방법을 택하는게 좋을 것 같다는 생각이 들어요

 

이 게시글은

적당량(?)의 데이터를 가지고 자동완성을 구현하는거에요

 

Trie...??

Trie가 뭔지 알고 가야겠죠?

 

Trie

 

트리 자료 구조 이구요

아래 그림과 같이 생겼어요

(빨간점은 단어가 끝났음을 의미해요, 아래에 이 점이 왜 있는지 이유가 나와요)

 

 

 

• 문자열을 탐색할 때 단순하게 하나씩 비교하면서 탐색을 하는것보다 훨씬 효율적
• 빠르게 탐색이 가능하다는 장점
• 각 노드에서 자식들에 대한 포인터(참조)들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점

문자열길이를 M라고 했을 때

삽입시 시간복잡도는 O(M) 이에요

nsios를 삽입한다고하면

n -> s -> i -> o -> s를 순서대로 넣을거니까요

 

탐색할 때는 트리구조니까 긴 문자열의 문자길이를 M이라고하면

아무리 오래 걸려도 그 문자열의 길이보다 길게 탐색할 순없잖아요?

nsios면 n->s->i->o->s 처럼 문자열의 길이만큼 탐색해요

 

만약 nsi, nsa, nab, nac 가 있을 때

ns를 검색한다면

n->s->i,

n->s->a,

n->s->b,

n->s->c

이렇게 타고 들어가겟죠??

 

깊게 문자열의 길이(N)만큼

 

따라서 탐색시 시간복잡도는 O(N)일것 같아요

 

nsios를 저장하고 ns를 저장하게된다면

n->s에 마지막문자 표시(빨간점)을 해줘서 구분할 수 있어요

 

이렇듯 한글자한글자 비교하는 방식보다는 확실히 좋은 효율을 가지고 있기 때문에

검색어 자동완성, 사전에서 찾기, 문자열 검사등에서 활용 된다고 하네요

 

저 역시 검색어 자동완성에 사용해요

 

 

구현하기 전에 흐름이나 알고리즘을 말로 설명해 볼게요

다양한 방법이 존재하고 제 구현이 틀릴 수도 있다는것을 감안하고 봐주세요 :)

 

root 가 존재하고

그 root에서부터 시작 문자를 저장할거에요

key: value 형식의 Dictionary를 사용해서 그 문자가 가지고있는 자식들의 문자를 저장할거에요

abc와 zxy를 저장한다고하면

트리를 만드는 것과 비슷해요

root가 a와 z를 키로 가지고있는 노드를 저장할거에요

a노드로 이동하고 a노드에서 b노드를 만들어서 연결시켜주고

b노드로 이동하고 b노드에서 c노드를 만들어서 연결하고

마지막값일때는 bool값을 이용해서 체크하고 마지막에만 문자열을 저장 시켜줄거에요

a(값 nil)->b(값 nil)->c(값 abc)

 

노드는

자신의 값을 가지고있고

자신의 자식의 키와 그 노드를 저장하는 배열을 가지고있어요

 

 

위의 그림으로 보자면 n이 부모고

s,a 가 키가되겟네요

[s: s노드, a: a노드] 이렇게 s와 a를 키로가지고있는 노드배열이 되겠죠?

 

다시돌아와서

기존에있던 데이터에 추가로 azx가 저장된다고하면

기존에 abc, zxy를 저장했으니

a노드가 존재하겠죠

새로 만들지않고 그 노드에 키로 z를 추가하는거에요 z: z노드

a->z->x를 하고나면

 

a-> b -> c

  -> z -> x

 

와같이 구성되겠죠??

 

이런식으로 트리를 저장하는 것 처럼하면되고

 

탐색도 트리와 같아요

a를 검색하면

 

a가 있는지 키값을 검사해서 찾고

있다면 a의 노드를 타고 들어가서 또 그 자식의 노드를 끝까지 탐색해서 저장한 값을 배열로 저장한뒤에

보여주면

a검색시

abc, azx가 뜨겟네요!!

 

제가 잘 설명했는지 모르겟네요 ㅎㅎ...

 

 

코드로 한번 구현해볼까요!!?

 

간단한 기능명세를 하자면

protocol TrieNode {
    associatedtype Node
    
    var value: String { get set }
    var children: [String: Node] { get set }
    var isFinal: Bool { get set }
    var data: String? { get set }
    /// 현재단어에 추가
    func add(value: String)
}

protocol Trie {
    /// 새단어 추가
    func insert(word: String)
    /// 단어검색
    func search(prefix: String) -> [String]
}

노드에는

현재 문자, 자식 배열, 마지막단어여부, 현재 문자열을 저장하고

현재 단어에 단어를 추가 즉, 자식노드를 만드는 함수를 정의할거구요

 

트라이(루트가 될 객체)에는

새단어 추가 즉, 현재 저장된 단어가 없어서 새로 시작하는 단어를 생성해주는 함수를 정의하고

검색하는 함수를 정의했어요

 

 

이 기능을 구현해보면

 

 

정렬도 마지막에 해줘서 가나다 순으로 잘나오게끔 했어요

테스트결과는...

 

 

잘 구현된것같아요...!!

 

구현하기위해 많은고민을 하고 공부해가며 짯던것같아요

부족한 부분 많은 피드백 부탁드려요 :)