[Kotlin] 문자열(String) 유사도 검사하기 - (1)

문장(문자열)의 유사도 분석?

최근 프로젝트에서 이러한 형태의 구현이 필요했었다

• EditText(내가 구현해둔 검색 창) 에 사용자가 어떠한 Keyword 를 검색한다.
• 해당 Keyword 를 DB(Room Database 를 사용 중이다) 에서 Search 하여 Data List 를 불러온다.
• 해당 Data List를 EditText 아래로 Vertical 한 List 로 표현해준다.

여기 세번째 부분에서 이런 얘기가 나왔다

 

"키워드가 다 들어있는 건 많은데 정작 내가 찾으려던 아이템을 보려면 스크롤을 많이 내려야 한다"

 

그래서 데이터 리스트 중 검색 키워드와 가장 비슷한 단어(-> 검색 키워드를 아이템의 이름으로 편집할 때 필요한 문자열 조작 횟수, 적을수록 유사한 단어로 판단) 순으로 정렬하는 알고리즘

 

LevenshteinDistance(레벤슈타인 거리)

 

를 만들어보았다.

 

 

 

각설하고 코드부터 보자면

    private fun getSimilarity(keyword: String, target: String): Int {
        val dp = Array(keyword.length + 1) { IntArray(target.length + 1) }

        for (i in 0..keyword.length) {
            for (j in 0..target.length) {
                when {
                    i == 0 -> dp[i][j] = j
                    j == 0 -> dp[i][j] = i
                    else -> {
                        dp[i][j] = if (keyword[i - 1] == target[j - 1]) {
                            dp[i - 1][j - 1]
                        } else {
                            1 + minOf(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
                        }
                    }
                }
            }
        }

        return dp[keyword.length][target.length]
    }

 

코드를 보면서 dp라는 단어에 익숙함이 느껴지신다면 코딩 테스트에서 흔히 볼 수 있는 그 DP 가 맞다.

2차원 Dp 로 Target 과 keyword 를 사용하는 형태인데 위 코드를 표로 설명을 하면 이렇게 된다.

예시는 Cook과 Cold, Came이다.

		C	O	L	D
	0	1	2	3	4
C	1	0	1	2	4
O	2	1	0	1	2
O	3	2	1	1	2
K	4	3	2	2	2

 

		C	A	M	E
	0	1	2	3	4
C	1	0	1	1	2
O	2	1	1	2	2
O	3	2	2	2	3
K	4	3	3	3	3

 

 

따라서 Cook 과 Cold 의 편집거리는 2 이고 Came 와의 편집거리는 3 이다.

 

만약 Item 의 이름을 Cook 로 검색했을 때 이 셋이 동시에 List에 있다면.

 

fun searchItems(keyword: String):List<Item>{
	val itemList: List<Item> = itemDao.search 
        return itemList.sortedBy{ item ->
            val distance = getSimilarity(keyword,item.name) // 위의 코드 블럭의 메서드를 이용
            distance 
}

 

이 메서드의 결괏 값은 itemList 기존 순서와 관계 없이 "Cook"이후에 "Cold" 가 "Came" 보다 앞에 올 것이다.