[iOS] 학과 검색 알고리즘 개선 (초성검색)

[iOS] 학과 검색 알고리즘 개선 (초성검색)

쿠링에 학과 검색 알고리즘을 아주 살짝(?) 개선했다.
우선 쿠링 서비스의 학과와 관련한 시퀀스를 살펴보자

 

앱 시작 시퀀스

 

해당 시퀀스로 설계하게 된 당시의 배경으로는

1. debounce 등 클라단 로직이 줄어들어 개발 공수가 훨씬 줄어든다.

2. 학과 검색 과정에서 api 응답까지 지연시간이 없으므로 사용자에게 더 좋은 경험을 줄 수 있다.
3. 서버도 학과 검색 개발 로직이 줄어들어 개발 공수가 줄어든다.
4. 한번에 내려줘야하는 학과의 갯수가 api를 통한 페이징 혹은 검색을 통해 받을 만큼 많지 않다.

 

여러모로 당시 상황을 고려했을때 이런 방향으로 설계를 주장했었는데, 다행히도 다른 분들도 승낙해 주셔서 해당 시퀀스로 구현되었다.

 

다만 해당 시퀀스 형태로 구현 몇 가지 문제점도 존재했습니다.

바로 클라단에서 검색 알고리즘을 구현하는 것.

유의어, 사용자가 입력한 단어의 약간의 오타, 특정학과의 줄임말 등을 모두 검색에 걸리게 하려니 알고리즘을 구현하는게 단시간에 할 수 있는 작업이 아니였다.

 

당시 코드를 보니 그런 점을 어느정도 보완하고자 글자의 갯수가 같으면 검색되는 로직도 포함되어 있긴했다.

예를 들면
전자전기공학부의 경우에는 "전전"이라는 키워드 만으로도 검색이 가능하다.

다만, perfectMatch가 있을 경우에는 perfectMatch된 키워드를 검색어로 반환한다.

 

v1에 적용된 쿠링 검색 알고리즘

 

 

학교 인공지능 수업시간에 학습한 Fuzzy 문자열 검색 알고리즘을 도입하면 좋다고 생각했다.

- (구현 아이디어 정리)
   - matrix를 만든 후 형태소마다 가중치를 부여하여 완성된 문자열의 가중값이 0.9 이상이면 match로 하면 될 것 같음
   - 가중치에는 입력한 글자에서 형태소를 추출하여 형태소면 가점, 다른 형태소면 감점.
   - 다만 이럴경우 3중 for 문이 들어갈 것 같은데, 알고리즘의 성능이 쓸만한지도 고민.

   - 성능까지 고민하니 결국 시간내에 어렵겠다 싶어서 리서치를 하는 시간을 더 많이 가져보기로.

다만, 회사일 동아리 그리고 적절한 휴식과 개인적인 삶 등등이 겹쳐서 해당 알고리즘을 바로 구현해서 붙이기에는 테스트 코드를 통한 검증이나 등등,,, 매우 오랜 시간이 걸릴 것으로 판단되었다.

 

"전기전자공학부"를 검색하려고 할 때 "ㅈㄱㅈㅈ"로 혹은

"경제학과"를 검색하려고 할 때 "ㄱㅈ"만 쳐도 검색이 된다면 훨씬 더 좋은 사용성을 갖출 수 있겠다 싶어

 

초성 검색 알고리즘을 도입하기로 결정했다. (난이도도 어렵지 않았음)

 

이론 설명

 

유니코드에서 한글은 총 11172개로 아래의 범위값을 가진다.

0xAC00 ~= 0xD7A3 (16진수)

44032 ~= 55203 (10진수)

 

초성 = ((문자코드 - 0xAC00) / 28) / 21

중성 = ((문자코드 - 0xAC00) / 28 % 21

종성 = (문자코드 - 0xAC00) % 28

 

28과 21은 한글 자모의 조합 규칙 때문에 사용된다.
한글은 초성, 중성, 종성으로 구성되어 있으며, 기본적으로 자음이나 모음이 각각 자리를 차지하는데, 이를 위해 28과 21이 사용된다.

1. 초성 (consonant):
   • 초성은 총 14개의 기본 자음이 있다. (ㄱ, ㄴ, ㄷ, ..., ㅎ)
   • 28은 14개의 초성을 표현하기 위한 수. 즉, 28로 나누면 각 초성이 자리를 차지.
2. 중성 (vowel):
   • 중성은 총 21개의 기본 모음이 있다. (ㅏ, ㅑ, ㅓ, ..., ㅣ)
   • 21은 21개의 중성을 표현하기 위한 수. 즉, 21로 나누면 각 중성이 자리를 차지.
3. 종성 (final consonant):
   • 종성은 총 28개의 기본 자음이 있다. (ㄱ, ㄴ, ㄷ, ..., ㅎ + no sound)
   • 28은 종성이 있는 경우의 수를 나타낸다. 종성이 없는 경우를 포함하여 28로 나누면 종성이 각 자리에 할당

 

샘플 코드

 

import Foundation

final class SearchChosungEngine {
    private let hangeul = ["ㄱ","ㄲ","ㄴ","ㄷ","ㄸ","ㄹ","ㅁ","ㅂ","ㅃ","ㅅ","ㅆ","ㅇ","ㅈ","ㅉ","ㅊ","ㅋ","ㅌ","ㅍ","ㅎ"]

    /// 해당 keyowrd가 초성문자인지 검사
    func isChosung(_ keyword: String) -> Bool {
        var result = false
        
        for char in keyword {
            if 0 < hangeul.filter({ $0.contains(char) }).count {
                result = true
            } else {
                result = false
                break
            }
        }
        
        return result
    }
    
    /// 초성 검색
    func searchChosung(_ keyword: String) -> String {
        var result = ""
        
        for char in keyword {
            // unicodeScalars: 유니코드 스칼라 값의 모음으로 표현되는 문자열 값
            let octal = char.unicodeScalars[char.unicodeScalars.startIndex].value

            // ~=: 왼쪽에서 정의한 범위 값 안에 오른쪽의 값이 속하면 true, 아니면 false 반환
            if 44032...55203 ~= octal {
                let index = (octal - 0xac00) / 28 / 21
                result = result + hangeul[Int(index)]
            }
        }
        return result
    }
}

 

 

결과물!

 

현재 쿠링에서 지원하는 검색 알고리즘

 

 

 

요즘 힙이나 우선순위 큐, 인공지능 수업시간에 배웠던 퍼지 알고리즘 등 실무에서 쓰는 알고리즘 들이 꽤나 많다.

해당 알고리즘을 활용해 앱의 퍼포먼스 및 로직을 개선할 때 많은 희열을 느끼고 있어서 알고리즘이랑 자료구조를 다시금 들여다보고 있다.

 

마지막으로 가중치를 포함한 알고리즘도 도입해보자!

 

 

 

 

 

참고

https://www.zehye.kr/ios/2022/04/15/iOS_chosung/

iOS searchBar 초성검색 기능 추가해보기 · 지혜의 개발공부로그

https://hongssup.tistory.com/130

[Swift iOS] Section Index Title 한글 초성 가져오기 UnicodeScalar