어떻게 Google"Did you mean?" 알고리즘을 작동하는가?

https://stackoverflow.com/questions/307291

08-07-2019
|

문제

나는 개발이 내부 웹사이트에 대한 포트폴리오 관리 도구이다.많은 텍스트 데이터의 회사 이름 등입니다.내가 정말 감동과 함께 몇 가지 검색 엔진 능력을 매우 신속하게 대응하는 쿼리로"당신이 평균:xxxx".

내가 필요할 수 있는 지능적으로 사용자가 쿼리로 응답하지만 원의 검색 결과뿐만 아니라"하셨습니까?"응답이 있을 때입니다 매우 가능성이 높은 대답 등

[나 개발 ASP.NET (VB-을 보유하지 않은 그것에 대해 내게!)]

업데이트:인할 수 있는 방법을 모방 이 없는 수백만의'무보수 사용자는'?

생성하는 오타를 위해 각각의'알려진'또는'정기 및 수행 조회?
다른 몇 가지 더한 방법은?

해결책

다음은 소스의 직접 설명입니다 (거의)

검색 101!

최소 22:03에서

볼 가치가있는!

기본적으로 그리고 Google의 Douglas Merrill 이전 CTO에 따르면 다음과 같습니다.

1) Google에 (틀린) 단어를 작성합니다.

2) 원하는 것을 찾지 못합니다 (결과를 클릭하지 마십시오)

3) 당신은 당신이 당신이 단어를 틀린 것을 발견하여 검색 상자에 단어를 다시 작성한다는 것을 알고 있습니다.

4) 원하는 것을 찾을 수 있습니다 (첫 번째 링크를 클릭하십시오)

이 패턴은 수백만 번을 곱하고 가장 일반적인 틀린 틀과 가장 "일반적인"수정 사항을 보여줍니다.

이런 식으로 Google은 거의 순간적으로 모든 언어에서 주문 수정을 제공 할 수 있습니다.

또한 이것은 밤새 모든 사람이 "Nigth"로 밤을 철자하기 시작한다면 Google이 대신 그 단어를 제안 할 것임을 의미합니다.

편집하다

@Thomasrutter : Douglas는 이것을 "통계 기계 학습"으로 묘사합니다.

그들은 쿼리를 수정하는 사람을 알고 있습니다. 어떤 쿼리가 어떤 사용자에게서 나오는지 (쿠키 사용)

사용자가 쿼리를 수행하고 사용자의 10%만이 결과를 클릭하고 90%가 다시 돌아와서 다른 쿼리 (수정 된 단어 포함)를 입력하고 이번에는 90%가 결과를 클릭하면 찾은 것을 알았습니다. 수정.

그들은 또한 그들이 보여주는 모든 링크의 정보를 가지고 있기 때문에 두 가지 다른 두 가지의 "관련"쿼리인지 알 수 있습니다.

또한, 그들은 이제 맞춤법 검사에 컨텍스트를 포함하고 있으므로 컨텍스트에 따라 다른 단어를 제안 할 수도 있습니다.

이것 좀 봐 Google Wave의 데모 ( @ 44m 06s) 철자를 자동으로 수정하기 위해 컨텍스트가 어떻게 고려되는지 보여줍니다.

여기 자연어 처리가 어떻게 작동하는지 설명됩니다.

그리고 마지막으로 여기에 자동 추가 할 수있는 일에 대한 멋진 데모가 있습니다. 기계 번역 ( @ 1h 12m 47s) 믹스에.

_{컨텐츠에 직접 건너 뛰기 위해 비디오에 1 분과 초 앵커를 추가했습니다. 작동하지 않으면 페이지를 다시로드하거나 마크에 스크롤하십시오.}

다른 팁

얼마 전에이 기사를 찾았습니다. 철자 수정 사항을 작성하는 방법, 작성 Peter Norvig (Google Inc.의 연구 책임자).

"철자 수정"주제에 대한 흥미로운 읽기입니다. 예제는 파이썬으로되어 있지만 이해하기가 명확하고 간단하며 알고리즘을 다른 언어로 쉽게 번역 할 수 있다고 생각합니다.

아래는 알고리즘에 대한 간단한 설명을 따릅니다. 알고리즘은 두 단계, 준비 및 단어 점검으로 구성됩니다.

1 단계 : 준비 - 데이터베이스 단어 설정

실제 검색어와 발생을 사용할 수있는 경우 가장 좋습니다. 당신이 그것이 없다면 대신 큰 텍스트 세트를 사용할 수 있습니다. 각 단어의 발생 (인기)을 계산하십시오.

2 단계 2. 단어 점검 - 확인 된 단어와 유사한 단어 찾기

비슷한 것은 편집 거리가 낮다는 것을 의미합니다 (일반적으로 0-1 또는 0-2). 편집 거리는 한 단어를 다른 단어로 변환하는 데 필요한 최소 인서트/삭제/변경/스왑 수입니다.

이전 단계에서 가장 인기있는 단어를 선택하고 수정 (단어 자체가 아닌 경우)으로 제안하십시오.

"당신은"알고리즘 이론의 이론에 대해서는 정보 검색 소개 3 장을 참조 할 수 있습니다. 사용할 수 있습니다 온라인 무료로. 섹션 3.3 (52 페이지) 정확히 질문에 답하십시오. 그리고 구체적으로 업데이트에 답하기 위해서는 단어 사전 만 필요하며 (수백만 명의 사용자를 포함하여) 아무것도 필요하지 않습니다.

Hmm...내 생각에는 구글이 사용되는 그들의 거대한 코퍼스의 데이터(인터넷)을 일부 심각한 NLP(Natural Language Processing).

예를 들어,그들은 너무 많은 데이터 전체에서 인터넷는 그들은 믿을 수 있는 횟수를 세는 단어 순서 발생합니다(라 건).그렇다면 그들은 같은 문장:"핑크 frugr 콘서트",그들은 그것을 볼 수 있는 몇 안타,다음 찾을 가능성이 가장 높은"분홍색*연주회에서"그들의 corpus.

그들은 분명히 다만의 변화는 무엇 Davide Gualano 말하고 있었지만,그래서 확실히 읽는 링크가 있습니다.구글은 물론 사용하는 모든 웹 페이지 그것을 알고 있으로 코퍼스는 알고리즘을 특별히 효과적입니다.

내 생각에 그들은 그들이 조합을 사용한다는 것입니다. Levenshtein 거리 실행중인 검색과 관련하여 알고리즘 및 수집 한 데이터의 질량. 입력 한 검색 문자열에서 Levenshtein 거리가 가장 짧은 검색 세트를 끌어 당긴 다음 가장 많은 결과를 가진 검색을 선택할 수 있습니다.

일반적으로 생산 철자 조정자는 몇 가지 방법론을 활용하여 철자 제안을 제공합니다. 일부는 다음과 같습니다.

철자 수정이 필요한지 여부를 결정하는 방법을 결정하십시오. 여기에는 불충분 한 결과, 구체적이거나 정확하지 않은 결과 (일부 측정에 따라) 등이 포함될 수 있습니다.
많은 텍스트 나 사전을 사용하십시오. 모든 사람이 올바르게 철자가있는 것으로 알려져 있습니다. 이들은 다음과 같은 장소에서 온라인으로 쉽게 찾을 수 있습니다. 링 파이프. 그런 다음 최상의 제안을 결정하려면 여러 측정을 기반으로 가장 가까운 일치하는 단어를 찾으십시오. 가장 직관적 인 것은 비슷한 캐릭터입니다. 연구와 실험을 통해 보여진 것은 2 ~ 3 개의 캐릭터 시퀀스 일치가 더 잘 작동한다는 것입니다. (Bigrams 및 Trigrams). 결과를 더욱 향상 시키려면 처음 또는 단어의 끝에서 경기에서 더 높은 점수를 얻습니다. 성능의 이유로,이 모든 단어를 트리 그램 또는 빅 람으로 색인하여 조회를 수행 할 때 N-Gram으로 변환하고 해시 가능 또는 트리를 통해 조회하십시오.
캐릭터 위치에 따라 잠재적 키보드 실수와 관련된 휴리스틱을 사용하십시오. 'w'가 'e'에 가깝기 때문에 "hwllo"는 "hello"여야합니다.
음성 키 (Soundex, Metaphone)를 사용하여 단어를 색인하고 가능한 수정 사항을 조회하십시오. 실제로 이것은 일반적으로 위에서 설명한대로 N- 그램 인덱싱을 사용하는 것보다 더 나쁜 결과를 반환합니다.
각각의 경우 목록에서 최상의 수정 사항을 선택해야합니다. 이것은 Levenshtein, 키보드 메트릭 등과 같은 거리 측정 항목 일 수 있습니다.
다중 단어 구절의 경우 한 단어 만 잘못된 단어로 표시 될 수 있으며,이 경우 남은 단어를 최상의 일치를 결정할 때 컨텍스트로 사용할 수 있습니다.

사용 Levenshtein 거리, 그런 다음 단어를 색인화하기 위해 메트릭 트리 (또는 슬림 트리)를 만듭니다. 그런 다음 가장 1 번의 이웃 쿼리를 실행하면 결과가 나왔습니다.

Google은 정확한 결과가 아니라 최상의 결과를 가진 쿼리를 제안합니다. 그러나이 경우, 아마도 철자법이 더 실현 가능할 것입니다. 물론 좋은 결과가 얼마나 좋은지에 대한 일부 메트릭을 기반으로 모든 쿼리에 대해 약간의 가치를 저장할 수 있습니다.

그래서,

사전이 필요합니다 (영어 또는 데이터 기반)
단어 격자를 생성하고 사전을 사용하여 전환에 대한 확률을 계산하십시오.
디코더를 추가하여 격자를 사용하여 최소 오차 거리를 계산하십시오. 물론 거리를 계산할 때 삽입 및 삭제를 처리해야합니다. 재미있는 것은 QWERTY 키보드가 서로 가까이 다가 가면 거리를 극대화한다는 것입니다.
최소 거리가있는 단어를 반환하십시오.
그런 다음이를 쿼리 데이터베이스와 비교하고 다른 근접 경기에 대한 더 나은 결과가 있는지 확인할 수 있습니다.

여기에 있습니다 내가 찾은 베스트 답변, 철자 조정자는 Google의 리서치 디렉터 Peter Norvig가 구현하고 설명했습니다.

이 이론에 대해 더 많이 읽으려면 읽을 수 있습니다. 그의 책 장.

이 알고리즘의 아이디어는 통계 기계 학습을 기반으로합니다.

추측으로 ... 할 수 있습니다

단어를 찾으십시오
발견되지 않은 경우 알고리즘을 사용하여 단어를 "추측"하려고 시도하십시오.

Hopfield Network 또는 Back Propagation Network와 같은 AI 또는 다른 "지문 식별", 깨진 데이터 복원 또는 Davide가 이미 언급했듯이 철자 수정 사항이 될 수 있습니다.

나는 몇 년 전에 이것에 대해 무언가를 보았으므로 그 이후로 바뀌었을 수도 있지만, 짧은 시간에 매우 유사한 쿼리를 제출하는 동일한 사용자의 로그를 분석하여 사용자 수정 방법을 기반으로 기계 학습을 사용하여 시작했습니다. 그들 자신.

단순한. 그들은 가지고 있습니다 톤 데이터의. 그것들은 쿼리가 얼마나 자주 쿼리되는지, 그리고 일반적으로 사용자가 클릭 한 결과를 산출하는 변형에 따라 가능한 모든 용어에 대한 통계를 가지고 있습니다. 더 평범한 답변.

실제로, 잘못된 검색이 가장 자주 검색되는 용어 인 경우 AlgoryThM은 올바른 용어를 사용합니다.

귀하의 질문과 관련하여 수많은 데이터가없는 동작을 모방하는 방법 - Google에서 수집 한 수많은 데이터를 사용하지 않는 이유는 무엇입니까? Google Sarch 결과를 다운로드하십시오 철자가 잘못된 단어 그리고 HTML에서 "당신이 의미 했습니까?"를 검색하십시오.

요즘 매시업이라고 생각합니다 :-)

맞춤법 검사기를 말하는 것을 의미합니까? 전체 문구가 아닌 맞춤법 검사기라면 Python에서 알고리즘이 개발되는 맞춤법 검사에 대한 링크가 있습니다. 확인하다 이 링크

한편, 본인은 텍스트를 사용하여 데이터베이스 검색을 포함하는 프로젝트를 작업하고 있습니다. 나는 이것이 당신의 문제를 해결할 것이라고 생각합니다

이것은 오래된 질문이며, 아무도 Apache Solr을 사용하여 OP를 제안하지 않았다는 것에 놀랐습니다.

Apache Solr은 다른 많은 기능 외에도 맞춤법 검사 또는 쿼리 제안을 제공하는 전체 텍스트 검색 엔진입니다. 로부터 선적 서류 비치:

기본적으로 Lucene Spell Checkers는 문자열 거리 계산의 점수와 인덱스의 제안의 주파수 (사용 가능한 경우)에 따라 제안을 먼저 정렬합니다.

위의 답변과는 별도로, 당신이 스스로 무언가를 빠르게 구현하고 싶다면 여기에 제안이 있습니다.

연산

이 알고리즘의 구현 및 자세한 문서를 찾을 수 있습니다. github.

비교기로 우선 순위 대기열을 만듭니다.
Ternay Search Tree를 만들고 모든 영어 단어를 삽입하십시오 ( Norvig의 게시물) 주파수와 함께.
TST를 가로 지르고 TST에서 발생하는 모든 단어에 대해 Levenshtein 거리를 계산합니다 (LD) input_word에서
ld ≤ 3이면 우선 순위 대기열에 넣으십시오.
마지막에서 우선 순위 대기열과 디스플레이에서 10 단어를 추출합니다.

특정 데이터 구조가 있습니다. 3 배 검색 트리 - 자연스럽게 부분 경기와 가까운 이속도 경기를 지원합니다.

가장 쉬운 방법은 Google 동적 프로그래밍입니다.

정보 검색에서 빌린 알고리즘이며 현대 생물 정보학에서 크게 사용되어 두 유전자 서열이 얼마나 유쾌한 지 확인합니다.

최적의 솔루션은 동적 프로그래밍 및 재귀를 사용합니다.

이것은 많은 솔루션에서 매우 해결 된 문제입니다. 오픈 소스 코드를 찾을 때까지 Google 만 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow