[stock] 자동완성

자동완성에 사용되는 자료구조는?

 

Trie

- 트리형 자료구조

- 문자열 탐색을 효율적으로 할 수 있음

- 중복 저장 X

 

Trie에 데이터 저장하기

- 삽입하고자 하는 문자열을 앞에서부터 한 글자씩 가져온다.

- 트리의 루트부터 적합한 노드 위치를 찾아가면서 저장

- 마지막 글자까지 삽입이 되면 isEnd 플래그로 단어의 끝을 표시

 

Trie에서 데이터 검색하기

- 인풋으로 받은 문자열을 한 글자씩 파싱

- 파싱된 문자를 앞에서부터 비교

- 해당 문자 노드가 존재하지 않거나, 리프 노드에 도달할 때 까지 탐색

 

시간 복잡도

O(L) 

L - 문자열 길이

 

단점

메모리를 많이 차지하게 된다.

 

편의를 위해 아파치에서 제공하는 Trie를 사용하자!

 

Tire외에도 LIKE 연산자를 사용해 자동완성을 할 수 있다.

 

 

Controller

@GetMapping("/autocomplete")
    public ResponseEntity<?> autocomplete(@RequestParam String keyword){

        List<String> autocomplete = companyService.autocomplete(keyword);

        return ResponseEntity.ok(autocomplete);
    }

 

Service

public void addAutocompleteKeyword(String keyword){ // 자동완성 키워드 추가
    trie.put(keyword, null);
}

public List<String> autocomplete(String keyword){ // 자동완성 문자 찾기
    return (List<String>) trie.prefixMap(keyword)
    .keySet().stream().limit(10).collect(Collectors.toList());
}

public void deleteAutocomplete(String keyword){ // 자동완성 키워드 제거
    trie.remove(keyword);
}

Keyword를 추가해주는 함수

자동으로 keyword를 찾아주는 함수

자동 검색 keyword를 지워주는 함수

limit을 주어 갯수를 10개로 제한해주었다.

 

 

 

트라이라는 알고리즘에 대해서 말로만 들어봤지, 실제로 이렇게 자동완성 기능에 사용되는 것을 처음 알았다..!

너무 흥미로웠다.