TIL 2026.04.11

Informate Retrieval

Tolerant Retrieval

정보 검색을 할 때 사용자가 정확히 하지 않을 때에도 결과를 반환해야한다.

미리 알고 시작하기 - Binary Search Tree

단어를 hash table에 저장한다면 O(1)로 검색이 가능하지만 범위 검색이 불가능하다. 반대로 Binary Search Tree에 저장한다면 O(log n)으로 검색이 가능하지만 범위 검색이 가능하다.

Wildcard

* 를 사용해서 검색한다.

예를 들어 *book 이라고 검색하면 book, notebook, textbook 등을 반환한다.

이걸 알고리즘으로 구현하면 어떻게 할 수 있을까?

이전에 말한 BST(Binary Search Tree)를 사용하면 prefix 검색이 가능하다. 예: nom* $\rightarrow$ nom $<=$ nom* $<$ non

위와 같이 접두사 검색이 가능하다.

그렇다면 suffix 검색은 어떻게 될까?

예: *nom $\rightarrow$ mon $<=$ mon* $<$ non

위와 같이 suffix를 prefix로 바꿔서 검색하면 된다.

문제는 hel*o 와 같이 wildcard 가 중간에 있으면 이렇게 해결하기 어렵다.

Permuterm index

term 이 들어올 때 $라는 끝을 나타내는 문자를 붙여서 rotation 한 것들을 다 매핑한다.

hello $\rightarrow$ hello$:

hello$
$hello
o$hell
lo$hel
llo$he
ello$h

그러면 hello 라는 term에 rotation 된 것들이 다 매핑된다. 그리고 hel*o 를 검색하면 hel*o$ -> o$hel* 를 검색하는 것과 같다. 그러면 이제 o$hel* 를 prefix 검색되어 o$hell 를 찾을 수 있다. 그러면 결국 hello 를 찾게 된다!

k-gram

term에 앞뒤로 $를 붙여서 k-gram을 만든다. k 길이 만큼 씩 쪼개서 매칭하고 query 되는 term 의 k-gram을 모두 and 연산해서 반환한다.

기존 Permuterm index 는 ${termLength}^2$ 만큼 index 를 생성해야하지만 k-gram 은 ${termLength + 2 - k + 1} \times k$ 만큼의 추가 데이터가 필요하기에 더 효율적이다.

하지만 후처리가 필요하다는 단점이 존재한다.

red* -> $r, re, ed

rested 라고 하면 red* 가 매칭된다 하지만 이는 실제로 매칭된게 아니므로 후처리 단계에서 없애야함

Edit Distance

기본 연산 (삽입, 삭제, 대체)을 통해서 한 단어를 다른 단어로 바꾸는 데 필요한 최소 연산 횟수

이게 왜 필요하냐면 사용자가 단어를 잘못 입력했을 때 이를 보정해서 검색 결과를 반환하기 위해서이다.

예를 들어 book 이라고 검색했을 때 boook 이나 boko 를 검색 결과로 반환하기 위해서이다.

알고리즘은 단순하게 dynamic programming 을 사용하면 된다.

LevenshteinDistance(s1, s2):
    for i <- 0 to |s1|:
        do m[i, 0] <- i
    for j <- 0 to |s2|:
        do m[0, j] <- j
    for i <- 1 to |s1|:
        do for j <- 1 to |s2|:
            do if s1[i] = s2[j]:
                then m[i, j] = min(m[i-1, j] + 1, m[i, j-1] + 1, m[i-1, j-1])
            else:
                then m[i, j] = min(m[i-1, j] + 1, m[i, j-1] + 1, m[i-1, j-1] + 1)
    return m[|s1|, |s2|]

Spelling Correction

Principle

Correcting documents being indexed
Correcting user queries

Method

Isolated word
- 각 단어 별로 스펠링 체크
- 정확해도 문맥상 틀린 단어 발생 가능: ‘I’m form korea’ -> from
Context-sensitive
- 문맥을 고려해서 스펠링 체크
- from/form 의 에러 체크 가능

Isolated Word Spelling Correction

주변 단어 상관없이 각 단어별로 오타 잡기

사전과 같이 올바른 단어가 있고 그걸 바탕으로 한다

올바른 단어와 현재 단어사이의 얼마나 비슷한지 계산

edit distance 사용
가중치 편집 거리: 사용자 키보드 타이핑 습관
k-gram overlap 사용

Context-Sensitive Spelling Correction

주변 단어를 고려해서 오타 잡기

Hit-based (결과 수 기반) 접근법: “flew form munich”라는 질의가 주어졌을 때, 각 단어의 유사 단어들(예: flew $\rightarrow$ flea, form $\rightarrow$ from)을 조합하여 다양한 구문(Phrase) 조합을 만듦
이후 만들어진 조합(“flea form munich”, “flew from munich” 등)을 검색 엔진에 실제로 던져보고, 가장 검색 결과(Hit)가 많이 나오는 구문을 올바른 교정본으로 최종 선택

Soundex

발음을 숫자로 변환해서 비슷한걸 찾는 것

단계

단어 첫 알파벳은 그대로 둔다.
모음은 0 으로 치환한다.
자음은 발음이 비슷한 것끼리 같은 숫자로 치환한다.
연속된 중복 숫자 제거
0 모두 제거. 총 4자리로 맞춘다.

하지만 뭐 별 큰 의미는 없음