문맥 (context)
최근 과학기술의 발전 및 경제 수준의 향상으로 인해 초고속 인터넷과 같은 통신망의 보급과 초고속 통신망 이용자의 급격한 증가가 이루어졌고, 초고속 통신망 이용자의 급격한 증가는 통신망을 통한 신규 서비스의 개발 및 서비스 아이템의 다양화를 가능하게 하였다. 이러한 통신망을 이용한 서비스 중 가장 일반적인 서비스가 검색 서비스라 할 수 있다.
검색 서비스란 사용자로부터 질의어가 입력되면, 입력된 질의어에 상응하는 검색 결과(예컨대, 입력된 질의어를 포함하는 웹 사이트, 입력된 질의어를 포함하는 기사, 또는 입력된 질의어를 포함하는 파일명을 갖는 이미지 등)를 사용자에게 제공하는 서비스를 의미 한다.
그러나, 검색 서비스를 이용하는 사용자들은 질의어를 입력함에 있어서, 질의어를 정확하게 입력하지 못하고 오타 질의어를 입력하거나 자신이 원하는 질의어를 정확히 알지 못하여 자신이 입력하기 원했던 질의어를 정확하게 입력하지 못할 수도 있는데, 이러한 경우 검색 서비스 제공자는 실제로 입력된 질의어를 기준으로 검색을 수행할 수 밖에 없어 결과적으로 사용자들은 자신이 원하는 검색결과를 제공 받을 수 없게 된다는 불편함이 있다.
이러한 불편함을 해결하기 위해 최근의 검색 서비스는, 사용자가 입력한 질의어에 대한 추천 질의어 제공 또는 연관 질의어 제공 등과 같은 다양한 검색 서비스를 제공하고 있는데, 여기서, 추천 질의어 제공이란, 사용자에 의해 입력된 질의어와 유사한 질의어들 중 일부를 추천 질의어로 제공하는 서비스를 의미한다.
일반적으로 이러한 추천 질의어를 제공하기 위해 근접 문자열 매칭(Approximate String Match)을 통해 데이터베이스에 저장된 질의어들 중 사용자가 입력한 질의어와 유사한 질의어들을 추천 질의어로 제공하였다. 이러한 근접 문자열 매칭을 위해 종래에는 편집 거리 계산이 많이 이용되었다. 편집 거리란 두 문자열이 같아지기 위해 필요한 삽입연산, 삭제연산, 교체연산의 개수로 정의된다.
그러나, 이러한 편집 거리 계산은 계산 복잡도가 매우 높기 때문에 데이터베이스에 저장된 모든 질의어들에 대해 사용자가 입력한 질의어와의 편집 거리를 계산하는 것은 매우 비효율적이라는 문제점이 있다.
또한, 이러한 편집 거리 계산은 유사한 문자열을 구분하는 데에는 유용할 수 있지만 유사한 발음을 구분하는 데에는 유용하지 못하기 때문에, 사용자에게 사용자가 입력한 질의어와 발음이 유사한 질의어를 추천 질의어로 제공할 수 없다는 문제점이 있다.
지시문 (instruction)
문맥에서 관련 배경과 원인을 찾아 논리적인 문장으로 설명하라.
질문 (question)
종래의 근접 문자열 매칭을 위해 이용되었던 편집 거리 계산 방식이 가진 두 가지 문제점은 무엇인가?
추론 과정 (compact_reasoning)
-
1과제 해석
task_interpretation편집 거리 계산 방식이 가진 문제점 두 가지를 찾는 작업이다.
-
2정보 추출
information_extraction편집 거리 계산의 특징과 한계점이 언급된 부분을 추출한다.
- 편집 거리 계산은 계산 복잡도가 매우 높기 때문에 데이터베이스에 저장된 모든 질의어들에 대해 사용자가 입력한 질의어와의 편집 거리를 계산하는 것은 매우 비효율적이라는 문제점이 있다.
- 또한, 이러한 편집 거리 계산은 유사한 문자열을 구분하는 데에는 유용할 수 있지만 유사한 발음을 구분하는 데에는 유용하지 못하기 때문에...
-
3근거 선택
evidence_selection문제점을 명시적으로 나타내는 구절을 선별한다.
- 계산 복잡도가 매우 높기 때문에... 매우 비효율적이라는 문제점
- 유사한 발음을 구분하는 데에는 유용하지 못하기 때문에... 유사한 질의어를 추천 질의어로 제공할 수 없다는 문제점
-
4논리 통합
logical_integration효율성 측면의 문제와 기능적 측면의 문제를 통합한다.
-
5결론 도출
conclusion_formulation계산 복잡도로 인한 비효율성과 발음 유사성 구분 불가라는 두 가지 결론을 도출한다.
-
6답변 생성
answer_generation질문에 맞게 두 가지 문제점을 정리하여 답변을 작성한다.
- 계산 복잡도가 매우 높아 데이터베이스 내 모든 질의어와 계산하는 것이 비효율적임
- 유사한 발음을 구분하는 데 유용하지 못함
최종 답변 (final_answer)
첫째, 계산 복잡도가 매우 높아서 데이터베이스에 저장된 모든 질의어에 대해 편집 거리를 계산하는 것이 매우 비효율적이라는 문제점이 있다. 둘째, 유사한 문자열을 구분하는 데는 유용할 수 있으나 유사한 발음을 구분하는 데에는 유용하지 못하여 발음이 유사한 질의어를 추천할 수 없다는 문제점이 있다.
핵심 해석 (core_interpretation)
기존 편집 거리 기반 근접 문자열 매칭 방식의 연산 효율성 한계와 발음 유사성 반영 불가라는 기술적 결함이다.