Trie 자료구조 활용
Trie?
Trie 연관검색어
1. 연관검색어 저장:
연관검색어를 저장하기 위한 Trie 자료구조를 구현한다.
각 노드는 한 문자를 나타내며, 연관검색어가 입력되면 문자 단위로 Trie에 저장한다.
검색어의 마지막 문자까지 이동한 후, 해당 위치의 노드를 표시하여 검색어의 끝임을 나타낸다.
2. 연관검색어 검색:
연관검색어를 사용자가 입력하면 Trie 자료구조에서 해당 검색어를 찾아낸다.
입력된 검색어의 마지막 문자까지 Trie를 따라가며 연관검색어를 추출한다.
3. 자동완성 및 연관검색어 추천:
사용자가 검색어를 입력하는 동안 해당 접두어에 해당하는 연관검색어를 추천
4. 메모리 사용 및 최적화:
Trie 자료구조를 메모리에 저장하는 경우, 모든 연관검색어를 메모리에 보관해야 하므로 대용량 데이터의 경우 고려해야 한다.
데이터의 크기 및 자주 변경 여부에 따라 메모리 사용을 최적화할 수 있는 방법을 고려.
코드예시
import java.util.ArrayList;
import java.util.List;
// Trie 노드 클래스 정의
class TrieNode {
TrieNode[] children; // 알파벳 26개에 대한 자식 노드 배열
boolean isEndOfWord; // 단어의 끝을 나타내는 플래그
TrieNode() {
children = new TrieNode[26]; // 소문자 알파벳만 다루므로 배열 크기는 26
isEndOfWord = false; // 단어의 끝으로 초기화
}
}
// Trie 클래스 정의
public class Trie {
private TrieNode root; // Trie의 루트 노드
public Trie() {
root = new TrieNode(); // 루트 노드 초기화
}
// 단어를 Trie에 삽입하는 메서드
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int index = c - 'a'; // 알파벳 인덱스 계산
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEndOfWord = true; // 단어의 끝 표시
}
// 지정된 접두사로 시작하는 모든 단어를 검색하는 메서드
public List<String> searchWordsWithPrefix(String prefix) {
List<String> result = new ArrayList<>();
TrieNode node = root;
for (char c : prefix.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
return result; // 접두사가 Trie에 없으면 빈 결과 반환
}
node = node.children[index];
}
findAllWordsWithPrefix(node, prefix, result);
return result;
}
// 지정된 노드 아래에서 모든 단어를 찾는 재귀적인 메서드
private void findAllWordsWithPrefix(TrieNode node, String currentWord, List<String> result) {
if (node.isEndOfWord) {
result.add(currentWord); // 현재 단어의 끝이면 결과에 추가
}
for (char c = 'a'; c <= 'z'; c++) {
int index = c - 'a';
if (node.children[index] != null) {
findAllWordsWithPrefix(node.children[index], currentWord + c, result);
}
}
}
public static void main(String[] args) {
Trie trie = new Trie(); // Trie 객체 생성
trie.insert("apple"); // 단어 삽입
trie.insert("app");
trie.insert("application");
trie.insert("banana");
trie.insert("bat");
String prefix = "app"; // 검색할 접두사
List<String> wordsWithPrefix = trie.searchWordsWithPrefix(prefix); // 접두사로 시작하는 단어 검색
System.out.println("Words with prefix '" + prefix + "': " + wordsWithPrefix); // 결과 출력
}
}
Redis 연관검색어
Trie 사용보다 나은이유
1. 메모리 사용:
Trie는 모든 데이터를 메모리에 저장합니다. 대용량 데이터를 다룰 때 메모리 사용량이 크게 증가할 수 있다.
Redis는 데이터를 디스크에 저장하고 필요할 때 메모리로 로드하여 메모리 사용을 효율적으로 관리할 수 있다.
2. 검색 성능:
Redis는 데이터 검색 및 캐싱에 특화된 솔루션으로, 검색 성능이 뛰어나다.
Trie는 복잡한 검색 쿼리 및 색인화를 구현하려면 더 많은 노력이 필요하다.
3. 분산 시스템:
Redis는 분산 환경에서 데이터를 효율적으로 관리할 수 있는 다양한 옵션과 레디스 클러스터를 제공한다.
Trie는 분산 시스템에 대한 별도의 개발 및 구현이 필요하다.
Redis 사용예시
public class AutoCompleteService {
private final RedisTemplate<String, String> redisTemplate;
private static final String AUTOCOMPLETE_KEY = "autocomplete";
private final String[] chs = {
"ㄱ", "ㄲ", "ㄴ", "ㄷ", "ㄸ", "ㄹ", "ㅁ", "ㅂ", "ㅃ",
"ㅅ", "ㅆ", "ㅇ", "ㅈ", "ㅉ", "ㅊ", "ㅋ", "ㅌ", "ㅍ", "ㅎ"};
// 검색어 등록
public void addAutoCompleteWord(String restaurant) {
redisTemplate.opsForZSet().add(AUTOCOMPLETE_KEY, restaurant, 0);
}
// 등록된 검색어 삭제
public void deleteAutoCompleteWord(String restaurant) {
redisTemplate.opsForZSet().remove(AUTOCOMPLETE_KEY, restaurant);
}
// 자동완성 검색
public AutoCompleteDto autoComplete(String input) {
List<String> matchingKeywords = new ArrayList<>();
if (isKoreanConsonant(input.charAt(0))) {
// 초성 검색
Set<String> consonantKeywords = redisTemplate.opsForZSet().rangeByScore(AUTOCOMPLETE_KEY, 0, 0);
consonantKeywords.forEach(restaurant -> {
if (extractConsonant(restaurant).contains(input)) {
matchingKeywords.add(restaurant);
}
});
} else {
// 일반 검색
Set<ZSetOperations.TypedTuple<String>> rankedKeywords = null;
if (!isKoreanConsonant(input.charAt(0))) {
rankedKeywords = redisTemplate.opsForZSet().rangeWithScores(AUTOCOMPLETE_KEY, 0, -1);
}
if (rankedKeywords != null && !rankedKeywords.isEmpty()) {
List<String> sortedKeywords = rankedKeywords.stream()
.sorted((a, b) -> Double.compare(b.getScore(), a.getScore())) // 내림차순 정렬
.map(ZSetOperations.TypedTuple::getValue)
.collect(Collectors.toList());
String trimmedInput = removeKoreanCharacters(input).trim();
sortedKeywords.forEach(keyword -> {
if (keyword.contains(trimmedInput)) {
matchingKeywords.add(keyword);
}
});
}
}
return AutoCompleteDto.builder()
.restaurants(matchingKeywords)
.build();
}
// 문자에서 초성을 추출
private String extractConsonant(String text) {
StringBuilder chosung = new StringBuilder();
text.chars().forEach(unicode -> {
if (isKoreanCharacter((char) unicode)) {
int chosungIndex = (unicode - '가') / (28 * 21);
chosung.append(chs[chosungIndex]);
}
});
return chosung.toString();
}
// 한글 문자인지 확인
private boolean isKoreanCharacter(char ch) {
return ch >= 0xAC00 && ch <= 0xD7A3;
}
// 한글 모음인지 확인
private boolean isKoreanConsonant(char ch) {
return ch >= 'ㄱ' && ch <= 'ㅎ';
}
// 만약 일반 조회일 경우 완성되지 않은 한글을 제거
private String removeKoreanCharacters(String text) {
return text.replaceAll("[ㄱ-ㅎㅏ-ㅣ]+", "");
}
}
하지만 ElasticSearch가 최고의 방법인 이유
1. 풍부한 검색 엔진:
Elasticsearch는 강력한 검색 및 쿼리 엔진을 제공한다. 텍스트 데이터를 색인화하고 다양한 검색 쿼리를 지원하여 사용자가 원하는 검색 결과를 신속하게 얻을 수 있다.
2. 스케일 가능성:
Elasticsearch는 대용량 데이터와 대규모 트래픽을 처리하는 데 적합한 스케일 아웃 아키텍처를 제공한다.
데이터 양이 증가하더라도 검색 성능을 유지할 수 있습니다.
3. 실시간 업데이트:
Elasticsearch는 실시간으로 데이터를 업데이트하고 색인화할 수 있다.
새로운 검색어나 검색어 변경 사항이 발생하면 빠르게 업데이트하여 자동완성 데이터를 유지할 수 있다.
4. 다양한 검색 방식:
Elasticsearch는 접두사 일치, 와일드카드, 오타 허용 등 다양한 검색 방식을 지원한다.
이를 통해 사용자 경험을 향상시키고 정확한 자동완성 기능을 제공할 수 있다.
5. 고급 토큰 분석: Elasticsearch는 다국어 지원, 다양한 토큰 분석기 및 필터를 통해 검색어 처리를 향상시킬 수 있다.
이는 다국어 환경에서도 효과적인 자동완성을 가능하게 한다.
6. 확장성:
Elasticsearch는 클러스터링을 통해 확장 가능한 아키텍처를 제공하므로 데이터의 증가와 요청 트래픽 증가에 대응할 수 있다.