해당 블로그는 이전 블로그 에 이어서 내용이 이어집니다.
개요
이전 블로그에서는 오직 영어만을 활용하여 자동 완성 시스템을 설계를 하였습니다. 다만 영어만 지원하다보니 "ABC초콜릿" , "냉장고" , "청소기" 와 같은 다국어는 검색할 수가 없었습니다.
이번 포스팅에서는 아래 그림과 같이 11번가 , 네이버 와 비슷하게 자동 완성 단어를 지원하는 로직을 구현해보겠습니다.
개발 목표
한글로 입력되었을 때 트라이에 노드로 저장하기 위해 분리, 병합하는 과정이 필요합니다. ( 추가 구현체 ( 자순 분리 및 병합 클래스 ) )
이때 자순을 분리하지 않고 영어와 같이 "햄>햄버>햄버거" 로 나눠 트라이에 저장해도 되지만, "ㅎ" 을 눌렸을 때 ㅎ로 시작하는 단어 ( ex) 햄버거, 후라이, 행거 ) 들을 조회하는 목표로 하기에 모든 자순을 분리하고 하나씩 병합하는 과정 ( ㅎ>해>햄>햄ㅂ>햄버>햄버ㄱ>햄버거 ) 으로 구현을 합니다.
영문와 한글의 차이점
입력하는 과정 ( 초성으로 ) 노드 탐색
영어는 단순히 글자가 하나 씩 구성되어 있기에 특별한 로직이 필요하지 않습니다. 하지만 한글의 경우 하나의 단어가 완성되기 전까지는 탐색이 되지 않습니다. ( ex) 햄버거를 탐색하는데 'ㅎ'이나 '해' 의 경우 노드를 탐색할 수 없습니다. )
따라서 자순을 하나씩 나눠서 ( ㅎ,해,햄 ) 입력하는 과정에서도 글자가 탐색될 수 있게 구현을 해야합니다.
방법은 노드의 depth 를 ( 햄>햄버>햄버거 ) 로 나누지 않고 ( ㅎ>해>햄>햄ㅂ>햄버>햄버ㄱ>햄버거 ) 로 나누어야 합니다.
노드 병합의 차이
추가적으로 한글은 분리된 자순을 병합하는 과정에서 해당 문자열을 담고있는 배열이 필요합니다.
예를 들어 영어 hamburger 는 substring 만으로도 하나씩 붙여가면서 노드에 붙일 수 있습니다. ( ex) h>ha>ham>hamb>hambu>hambur>hamburg>hamburge>hamburger )
다만 한글의 경우 햄버거 를 substring 으로 자를 경우 ( ㅎ>해>햄>햄ㅂ>햄버>햄버ㄱ>햄버거 ) 가 아니라 ( 햄>햄>햄>햄버>햄버>햄버거>햄버거>햄버거 ) 가 저장이 됩니다. substring() 은 자순이 아니라 글자 길이로 자르기 때문에 병합하는 과정을 배열에 매번 넣는 로직이 필요합니다.
구현 시 고려 사항
한글 + 영문 혼합식
오직 영어이거나 한글만 입력하는 경우, 각각의 로직으로 분리해도 상관 없지만 문제는 한글과 영문이 입력되는 경우입니다.
이때는 substring() 를 통해 문자열을 하나의 문자로 나누고 하나의 문자가 한글인지 영문인지 판단 후 해당 문자에 알맞은 로직을 실행하면 해결됩니다.
추가 구현체 ( 자순 분리 및 병합 )
public class GraphemeSeparation {
// 초성 ( ㄱ ~ ㅎ ) /*ㄱ ㄲ ㄴ ㄷ ㄸ ㄹ ㅁ ㅂ ㅃ ㅅ ㅆ ㅇ ㅈ ㅉ ㅊ ㅋ ㅌ ㅍ ㅎ */
private static final char[] initialConant = {0x3131, 0x3132, 0x3134, 0x3137, 0x3138, 0x3139, 0x3141, 0x3142, 0x3143, 0x3145, 0x3146, 0x3147, 0x3148, 0x3149, 0x314a, 0x314b, 0x314c, 0x314d, 0x314e};
// 중성 ( ㅏ ~ ㅣ ) /*ㅏㅐㅑㅒㅓㅔㅕㅖㅗㅘㅙㅚㅛㅜㅝㅞㅟㅠㅡㅢㅣ*/
private static final char[] neutrality = {0x314f, 0x3150, 0x3151, 0x3152, 0x3153, 0x3154, 0x3155, 0x3156, 0x3157, 0x3158, 0x3159, 0x315a, 0x315b, 0x315c, 0x315d, 0x315e, 0x315f, 0x3160, 0x3161, 0x3162, 0x3163};
// 종성 ( ㄱ ~ ㅎ )
private static final char[] finality = {0x0000, 0x3131, 0x3132, 0x3133, 0x3134, 0x3135, 0x3136, 0x3137, 0x3139, 0x313a, 0x313b, 0x313c, 0x313d, 0x313e, 0x313f, 0x3140, 0x3141, 0x3142, 0x3144, 0x3145, 0x3146, 0x3147, 0x3148, 0x314a, 0x314b, 0x314c, 0x314d, 0x314e};
public static List<Map<String, Integer>> separation(String word) {
List<Map<String, Integer>> list = new ArrayList<Map<String, Integer>>();
// 글자 길이에 따라 반복합니다.
for (int i = 0; i < word.length(); i++) {
Map<String, Integer> map = new HashMap<String, Integer>();
char test = word.charAt(i); // 문자열의 한 문자만 가지고 옵니다.
if (test >= 0xAC00) { // 만약 해당 글자가 'ㄱ' 코드 이상이라면
char uniVal = (char) (test - 0xAC00);
// 해당 글자를 기준으로 초성 중성 종성을 구하는 공식
char initialConant = (char) (((uniVal - (uniVal % 28)) / 28) / 21);
char neutrality = (char) (((uniVal - (uniVal % 28)) / 28) % 21);
char finality = (char) (uniVal % 28);
map.put("initialConant", (int) initialConant);
map.put("neutrality", (int) neutrality);
map.put("finality", (int) finality);
list.add(map);
}
}
return list;
}
public static List<String> absorption(Map<String, Integer> map) {
List<String> result = new ArrayList<>();
int a = map.get("initialConant");
int b = map.get("neutrality");
int c = map.get("finality");
// 나눠진 자순을 하나로 합치는 공식
// 이때 초성 , 중성 , 종성 하나씩 합치는 중간에 list에 추가하여 ㅎ>하>한 이 저장되게 구현
result.add(String.valueOf((char) initialConant[a]));
result.add(String.valueOf((char) (0xAC00 + 28 * 21 * (a) + 28 * (b))));
if (c != 0x0000) {
result.add(String.valueOf((char) (0xAC00 + 28 * 21 * (a) + 28 * (b) + (c))));
}
return result;
}
}separation() 메서드는 한글을 입력받아 초성 중성 , 종성으로 분리하는 메서드입니다.
예시로 "휴지통" 이 입력되었다면 반환 값으로는 [["initialConant" : "ㅎ" , "neutrality" : "ㅠ" , ["initialConant" : "ㅈ" , "neutrality" : "ㅣ" , ["initialConant" : "ㅌ" , "neutrality" : "ㅗ" , "finality" : "ㅇ"]]
이 반환되게 됩니다.
absorption() 메서드는 위의 seperation() 메서드를 통해 글자들을 병합하는 메서드입니다. 인자로 ["initialConant" : "ㅌ" , "neutrality" : "ㅗ" , "finality" : "ㅇ"] 가 입력되었다면 통 이 반환되게 됩니다.
트라이 구현체 수정
기존 트라이 구현체는 영어만 다뤘기 때문에 단순히 한 문자씩 트리에 넣는 과정을 거쳤습니다.
하지만 다국어 ( 영어 + 한글 ) 를 처리해야 하기 때문에 한글은 자순을 분리하여 하나씩 조립하여 트리에 넣어야하고 , 영어는 기존 방식 그대로 처리해야합니다.
또한 각 문자열이 영어인지 한글인지 구분하고 rootNode에서부터 하나씩 depth를 내려갈 수 있게 수정해주어야 합니다.
이때 한글의 자순을 하나씩 분리하는 이유는 ㄱ 을 검색했을 때 "가방' , "고기" 처럼 연관된 검색어를 도출해야 하기 때문입니다. 또한 "고" 를 검색했을 때 "고기" , "곡물" 이 검색되기 위함입니다.
구현 방법은 다음과 같습니다.
한글 트라이 구현
- 입력받는 한글을 모두 분리합니다. ex ) 한글 -> ㅎㅏㄴㄱㅡㄹ
- 분리한 한글을 한 글자씩 병합 하면서 트리에 넣습니다. ex ) ㅎ>하>한>한ㄱ>한그>한글
한글 트라이 노드 탐색
노드를 탐색할 때에도 한글을 모두 분리 후 , 한 글자씩 병합하면서 노드를 탐색합니다. ex ) ㅎ>하>한>한ㄱ>한그>한글
한글 트라이 탐색 방법
반복문을 통해 위의 한글이 병합하는 데이터를 기반으로 Node의 depth를 하나씩 들어가면서 해당 노드를 탐색합니다.
영어 + 한글의 경우
살짝 복잡한 부분인데, 해당 문자열 전체가 한글인지 아닌지 판단하여 로직을 수정하면 문제가 발생하기에 substring() 메서드를 사용하여 문자 하나씩 한글인지 아닌지 판단하여 문제를 해결할 수 있습니다.
이때 영어와 한글이 반복되기 때문에 Node는 처음에만 root에 두고 이후 for문을 통해 탐색합니다.
영어라면 별다른 로직 없이 차례대로 노드의 depth에 진입 , 한글이라면 자순을 분리 및 하나씩 병합하면서 해당 노드에 하나씩 접근해나갑니다. ex ) A>AB>ABC>ABCㅁ>ABC마>ABC마ㅌ>ABC마트
만약 해당 문자열 전체가 한글인지 영문인지 탐색하는 로직을 구현하면 A 는 'ㄱ' 보다 유니 코드가 전에 있기 때문에 로직을 실행하지 않고 바로 다음 로직으로 실행합니다.
- 입력받은 문자열을
substring()메서드를 활용해 하나씩 분리합니다. ( split도 가능 ) - 분리된 각 하나의 문자열이 한글인지 아닌지 판단하여 각 로직을 실행합니다.
public class Trie {
Node rootNode = new Node("Empty");
// 노드 삽입
public Node insert(String str) {
Node node = this.rootNode;
Node currentNode;
String [] completeWord = new String[str.length()];
for(int i = 0; i < str.length(); i++) {
String targetString = str.substring(i , i + 1); // 하나의 문자를 추출합니다.
completeWord[i] = targetString;
// 해당 배열은 한글이 포함되어 있을 경우, 조립되는 과정을 담는 배열
// 해당 배열이 없다면 한글은 ㅎ>하>한 이 아니라 한>한>한이 저장이 됨 ( substring() 의 한계 극복 )
// 물론 조립은 addTrieNode 메서드 안에서 이루어짐
// 한글인지 아닌지 파악 후 노드 생성
if(isHangul(targetString)) {
node = addTrieNode_Hangul(targetString, node, completeWord, i);
} else {
node = addTrieNode_English(targetString, node, completeWord);
}
}
currentNode = createOrLoadAutoComplete(node.word);
node.isContainWord = true;
node.frequency = currentNode.frequency;
return node;
}
public static boolean isHangul(String str) {
return str.matches(".*[ㄱ-ㅎㅏ-ㅣ가-힣]+.*");
}
public static String convertArrayToString(String [] arr) {
return String.join("" , arr).replaceAll("null","");
}
public Node addTrieNode_Hangul(String word, Node node, String [] totalWord, int index) {
List<Map<String, Integer>> separatedWord = GraphemeSeparation.separation(word);
// 글자 분리 ( 해당 코드에서는 한 글자씩 전송하기에 List는 필요 없지만 확장성을 고려하여 List로 구현하였습니다. )
for(int i = 0; i < separatedWord.size(); i++) {
List<String> resultWord = GraphemeSeparation.absorption(separatedWord.get(i));
// 분리된 자순을 하나씩 조립한 List ( ㅎ>하>한 )
for(int j = 0; j < resultWord.size(); j++) {
String targetWord = resultWord.get(j);
totalWord[index] = targetWord;
// 조립되는 한글을 배열에 저장
// 해당 배열로 ㅎ>하>한 이 저장이 됨
// 해당 배열을 사용하지 않고 subString을 사용한다면 한>한>한이 저장
node = node.childedNode.computeIfAbsent(targetWord, key -> new Node(convertArrayToString(totalWord)));
// 노드가 없다면 새로운 노드 생성
}
}
return node;
}
public Node addTrieNode_English(String str, Node node, String[] totalWord) {
for(int i = 0; i < str.length(); i++) {
// 이때 대소문자 구분을 제거하기 위해 toLowerCase() 를 사용
node = node.childedNode.computeIfAbsent(str.substring(i , i + 1).toLowerCase(), key -> new Node(convertArrayToString(totalWord)));
}
// 한글에 비해 너무 단순한 로직..
return node;
}
// 탐색 메서드도 마찬가지로 한글 , 영어인지 구별 후 노드를 탐색
public List<UtilInitDto> searchComplete(String searchWord) {
List<UtilInitDto> result = new ArrayList<>();
Node node = this.rootNode;
// 초기 노드는 최 상단 노드를 가리킵니다.
for(int i = 0; i < searchWord.length(); i++) {
String targetWord = searchWord.substring(i , i + 1);
// 현재 문자열 하나씩 접근하면서 노드에 하나씩 접근해 나갑니다.
if(isHangul(targetWord)) {
node = searchSearchWord_Hangul(targetWord, node);
// 이때 점차적으로 depth 를 내려가야하기 때문에 반환받은 node를 저장
} else {
node = searchSearchWord_English(targetWord, node);
}
if(node == null) {
return result;
}
}
// 위의 로직에서 찾은 result ( Node ) 로 넓이 우선 탐색 ( BFS )을 통해 노드의 모든 자식노드의 데이터를 가져오는 로직
Queue<Node> queue = new LinkedList<>();
queue.offer(node);
while(!queue.isEmpty()) {
Node currentNode = queue.poll();
if(currentNode.isContainWord) {
result.add(new UtilInitDto(currentNode.word, currentNode.frequency));
}
// 노드를 탐색하되, 해당 단어가 포함되어 있으면 결과 값에 포함
for(String str : currentNode.childedNode.keySet()) {
queue.offer(currentNode.childedNode.get(str));
}
}
// 빈번수를 기준으로 내림 차순
Collections.sort(result, new Comparator<UtilInitDto>() {
@Override
public int compare(UtilInitDto o1, UtilInitDto o2) {
return o2.getFrequency() - o1.getFrequency();
}
});
// 가장 탐색 수가 많은 10개를 제외하고 모두 제거
if(result.size() > 10) {
result.subList(10, result.size()).clear();
}
return result;
}
// 영문 노드를 탐색하는 코드
private Node searchSearchWord_English(String str, Node node) {
for(int i = 0; i < str.length(); i++) {
node = node.childedNode.getOrDefault(str.substring(i , i + 1).toLowerCase(), null );
if(node == null) {
return null;
}
}
// 단순히 subString 을 통해 해당 노드에 점진적으로 접근할 수 있습니다.
return node;
}
// 한글 노드를 탐색하는 부분
private Node searchSearchWord_Hangul(String str, Node node) {
List<Map<String, Integer>> separatedWord = GraphemeSeparation.separation(str);
// 모든 문자열을 분리합니다.
if(separatedWord.isEmpty()) {
// 만약 분리된게 아니라면 공백( space bar = ' ') 일 수 있기에 따로 처리하는 로직 구현
return node.childedNode.getOrDefault(str, null);
}
for(int i = 0; i < separatedWord.size(); i++) {
List<String> resultWord = GraphemeSeparation.absorption(separatedWord.get(i));
// 한글이 ㅎ>하>한>한ㄱ>한그>한글로 분리된 resultWord 변수
for(int j = 0; j < resultWord.size(); j++) {
// resultWord를 기준으로 node에 점진적으로 들어가면서 해당 문자열을 가지고 있는 node가 존재하는지 탐색
node = node.childedNode.getOrDefault(resultWord.get(j), null);
// 만약 해당 문자열을 가진 node가 존재한다면 한 depth 에 접근 , 없다면 null 을 반환
if(node == null) {
return null;
}
}
}
return node;
}
}