'Study'에 해당되는 글 21건

3.1 사전용 탐색 구조

• 역색인과 질의가 제시되었을 때 수행할 작업
• 각 질의 용어가 어휘집(Vocabulary)에 포함되어 있는지를 판단
• 만약 포함되어 있다면, 해당 문헌 포스팅에 상응하는 포인터를 확인
• 어휘집 조회 연산은 사전(Dictionary)이라 불리는고전적인 자료 구조를 이용
• 사전은 해싱과 탐색 트리라는 두 가지 큰 갈래의 구현 방법이 있음
• 두 가지 방법 중 선택 시 고려 사항
• 몇 개의 키를 가질 것인가?
• 그 수를 고정시켜 놓을 것인가 혹은 번번히 변화시킬 것인가?
• 변경시킬 경우 새로운 키를 사전에 삽입만 되게 할 것인가?
• 아니면 몇몇 키는 삭제도 되게 할 것인가?
• 다양한 키에 접근하는 상대적 빈도는 어떠한가?
• 해싱(Hashing)
• 몇몇 검색 엔진에서 사전 조회용으로 사용됨
• 각 어휘집 용어(키)는 해시 충돌이 일어나지 않도록 충분한 저장 공간에서 정수값으로 해시됨
• 탐색 트리
• 가장 잘 알려진 탐색 트리는 이진트리(Binary tree)로 각 내부 노드가 두 개의 자식 노드를 가짐
• 용어 탐색은 트리의 루트부터 시작됨
• 효율적인 탐색이 되기 위해서는 트리가 균형을 이루어야 하며, 각 노드에 달려있는 두 개의 하부 트리에 저장된 용어의 수가 동의하거나 1의 차이를 가져야 함
• 가장 중요한 이슈는 트리를 재균형화하는 문제로서, 용어가 이진 탐색 트리에 삽입되거나 삭제될 경우에도 트리의 균형성이 유지되도록 균형이 재조정되어야 함
• B-트리(B-tree): 재균형화의 부담을 덜기 위해 내부 노드에 붙어있는 하부 트리의 수가 일정한 간격을 두고 변하도록 하는 것

3.2 와일드 카드 질의

• 후방 절단 질의(Trailing wildcard query)
• mon*의 경우 B-트리에서 mon을 가진 용어들의 집합 W를 열거함
• 전방 절단 질의(Leading wildcard query)
• *lemon의 경우 역 B-트리에서 ‘root-n-o-m-e-l’의 경로에 따라 집합 R을 열거함
• 순열 색인(Permuterm index)
• 특수 기호 $를 사용하여 용어의 끝을 표시 한 후 다양한 형태로 회전된 각각의 용어가 어휘집 용어와 연결되며, 순열 어휘집(Permuterm vocabulary)를 만듦
• 예를 들어 m*n의 경우 $를 붙이고 회전을 통해 n$m*을 찾으면 man과 moron이라는 용어가 회전하며 *이 여러개일 경우 *의 위치에 기반하여 부분으로 하나씩 확인하면서 없는 것들을 걸러냄
• 따라서 순열 색인은 각 용어를 모두 회전시켜야 하기 때문에 사전의 규모가 커지는 단점이 있음
• 와일드카드 질의를 위한 k-gram 색인
• K 문자들의 연속으로 집합을 구성함
• castle의 경우 $ca, cas, ast, stl, tle, le$임
• 사후 필터링(Postfiltering)
• red*의 경우$re와 red라는 2가지 3-gram색인을 논리곱 연산한 것을 포함하고 있지만, 원래의 와일드카드 질의인 red*과는 매치되지 않기 때문에 단순 문자열-일치 연산으로 오류를 해소함

3.3 철자 교정

• 철자 교정의 단계는 다음과 같음
• 편집거리(Edit distance)에 기반하는 방법
• k-gram 중복(k-gram overlap)에 기반하는 방법
• 철자 교정의 원칙
• 가장 근접한 철자로 수정
• 근접한 철자가 다수일 경우 다른 사용자들이 보다 많이 이용하는 질의를 철자 교정에 이용함
• 고립 단어 교정(Isolated-term correction)
• 한 번에 하나의 질의 용어를 수정함
• 편집 거리는 문자열 s1을 s2로 변환하는데 필요한 편집 연산(Edit operation)의 최소수로 Levenshtein 거리(Levenshtein distance)라고도 함
• 철자 교정을 위해 k-gram 색인을 이용하는 경우 선형 스캔 교집합(Linear scan intersection) 연산을 통해 질의 q로부터 고정된 수의 k-gram을 포함하고 있는 어휘집 용어와 단순히 일치되는 것을 찾는 단점이 바로 드러남
• 이는 |A ∩ B| / |A ∪ B|로 정의되는 Jaccard 계수(Jaccard coefficient)를 사용하여 A와 B 집합 사이의 중복 부분을 측정할 수 있음
• 음성학적 교정
• 사용자가 자신이 목표한 용어처럼 소리나는 질의를 입력하기 때문에 생긴 철자 오류를 교정하는 것
• 특히 사람 이름을 검색할 때 적용할 수 있음
• 각각의 용어에 대한 음성 해시(Phonetic hash)를 생성하는 것으로 통칭하여 Soundex 알고리즘(Soundex algorithm)이라고 함