관용적 검색 및 와일드카드 검색

관용적 검색(Tolerant retrieval)은 철자 변형, 와일드카드, 음성적 차이에도 불구하고 검색 시스템이 쿼리와 일치하도록 하여, 쿼리와 텍스트가 정확히 일치하지 않을 때에도 사용자가 관련 문서를 찾을 수 있도록 합니다.

Definition

관용적 검색은 와일드카드 확장, 편집 거리 기반 철자 교정, 음성 인코딩을 포함하여 불완전하거나, 철자가 틀렸거나, 음성적으로 변형된 입력에도 불구하고 쿼리 용어를 색인된 용어와 일치시키는 사전 수준의 기술을 포함합니다.

Scope

이 주제는 사전 수준에서 정확한 용어 일치를 완화하는 기술을 다룹니다. 여기에는 순열어(permuterm) 및 k-그램(k-gram) 색인을 사용한 와일드카드 쿼리 처리, 편집 거리(edit distance) 및 문맥을 통한 철자 교정, Soundex와 같은 음성 일치(phonetic matching)가 포함됩니다. 용어 사전이 이러한 근사 검색을 지원하도록 어떻게 확장되는지, 그리고 후보 용어가 어떻게 생성되고 순위가 매겨지는지를 다루며, 표면 형태보다는 의미를 다루는 의미 일치(semantic matching)와는 구별됩니다.

Core questions

• 접두사, 접미사, 중위 패턴과 같은 와일드카드 쿼리는 사전에서 어떻게 평가됩니까?
• 순열어(permuterm) 및 k-그램(k-gram) 색인은 와일드카드 검색을 어떻게 지원합니까?
• 철자가 틀린 쿼리 용어에 대해 가장 가까운 올바른 철자 용어는 어떻게 찾아집니까?
• 편집 거리(레벤슈타인 거리)는 두 문자열 간의 차이를 어떻게 정량화합니까?
• Soundex와 같은 음성 일치는 소리가 비슷한 용어들을 어떻게 그룹화합니까?

Key concepts

• 와일드카드 쿼리
• 순열어 색인
• k-그램 색인
• 편집 거리 (레벤슈타인 거리)
• 철자 교정
• 음성 일치 (Soundex)
• 근사 문자열 일치
• 후보 용어 생성

Key theories

순열어 및 k-그램 색인을 이용한 와일드카드 색인화

와일드카드가 항상 끝에 오도록 용어를 회전시키거나(순열어), 문자 k-그램으로 용어를 색인화하면 시스템이 와일드카드 패턴을 일반적인 사전 검색으로 변환하여 후보 용어를 검색할 수 있습니다.

편집 거리 철자 교정

하나의 문자열을 다른 문자열로 변환하는 데 필요한 최소 단일 문자 삽입, 삭제 및 대체 횟수(편집 거리)는 쿼리 용어에 대한 올바른 철자 대안을 제안하는 원칙적인 측정 기준을 제공하며, 이는 종종 용어 빈도 및 문맥과 결합됩니다.

Clinical relevance

관용적 검색은 '혹시 ~을 찾으셨나요?'와 같은 철자 제안, 자동 완성 및 접두사 검색, 이름 및 제품 용어의 관용적 일치와 같은 일상적인 검색 기능을 제공합니다. 이는 쿼리에 오타가 있거나 사용자가 정확한 철자를 모를 때 검색 결과의 재현율과 사용자 경험을 크게 향상시킵니다.

History

근사 일치(approximate matching) 및 철자 교정(spelling correction)은 컴퓨팅 분야에서 오랜 역사를 가지고 있으며, Soundex는 20세기 초 기록 색인화로 거슬러 올라갑니다. Kukich의 1992년 연구는 자동 철자 교정 기술을 통합했으며, Navarro의 2001년 연구는 근사 문자열 일치를 체계화했습니다. 웹 검색이 관용적인 쿼리 처리를 필수적으로 만들면서 이러한 방법들은 검색 사전의 표준 구성 요소가 되었습니다.

Key figures

• Karen Kukich
• Gonzalo Navarro

Seminal works

• manning2008
• kukich1992
• navarro2001

Frequently asked questions

검색 엔진은 'comput*'와 같은 와일드카드를 어떻게 처리합니까?

순열어 또는 k-그램 색인과 같은 보조 사전 구조를 사용하여 패턴과 일치하는 모든 용어(computer, computing, computation 등)를 찾은 다음, 해당 용어들이 명시적으로 나열된 것처럼 원래 쿼리를 평가합니다.

편집 거리란 무엇이며 왜 철자 교정에 사용됩니까?

편집 거리는 한 단어를 다른 단어로 바꾸는 데 필요한 최소 단일 문자 삽입, 삭제 및 대체 횟수를 계산합니다. 철자가 틀린 쿼리 용어와 사전 용어 사이의 편집 거리가 작다는 것은 사전 용어가 의도된 올바른 교정일 가능성이 높음을 시사합니다.