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

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

쿠링에 학과 검색 알고리즘을 아주 살짝(?) 개선.

 

 

시퀀스 분석

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

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

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

 

이러한 점들을 종합적으로 고려했을 때, 클라이언트 단에서 전체 학과 데이터를 한 번에 내려받고
검색을 로컬에서 처리하는 방향이 최적이라고 판단했고, 다행히 팀 내에서도 같은 의견이 모여, 해당 시퀀스로 구현을 진행.

앱 시작 시퀀스

 

 

구현 이후 발견된 문제점

가장 큰 이슈는 검색 알고리즘을 클라이언트 단에서 직접 구현해야 한다는 점

사용자 입력의 유의어, 오타, 약칭(예: 줄임말) 등을 모두 포괄적으로 처리하려면, 상당히 정교한 문자열 매칭 로직이 필요
이는 단기간 내 구현하기 어려운 과제로 느껴짐.

 

코드 스크린샷

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