[algorithm] Google은 “무슨 의미인가요?” 알고리즘 작동?

포트폴리오 관리 도구를위한 내부 웹 사이트를 개발하고 있습니다. 많은 텍스트 데이터, 회사 이름 등이 있습니다. “Did you mean : xxxx”라는 쿼리에 매우 빠르게 응답 할 수있는 일부 검색 엔진 기능에 깊은 인상을 받았습니다.

지능적으로 사용자 검색어를 가져 와서 원시 검색 결과뿐만 아니라 “정말입니까?”로 응답 할 수 있어야합니다. 대체 답변 등이있을 경우의 응답

[ ASP.NET 에서 개발 중입니다 (VB-나에게 대항하지 마십시오!)]

업데이트 : OK, 수백만의 ‘무상 사용자’없이 어떻게 이것을 모방 할 수 있습니까?

  • 각 ‘알려진’또는 ‘올바른’용어에 대한 오타를 생성하고 조회를 수행 하시겠습니까?
  • 다른 더 우아한 방법?


답변

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

검색 101!

최소 22:03

볼 가치가있는!

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

1) Google에 철자가 틀린 단어를 씁니다.

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

3) 단어의 철자가 틀렸다는 것을 알고 검색 창에 단어를 다시 씁니다.

4) 원하는 것을 찾으십시오 (첫 번째 링크를 클릭하십시오)

이 패턴은 수백만 번 곱 해져서 가장 일반적인 철자가 무엇인지, 그리고 가장 “일반적인”수정이 무엇인지 보여줍니다.

이런 식으로 Google은 거의 모든 언어에서 철자 교정을 제공 할 수 있습니다.

또한 이것은 밤새 모든 사람들이 “nigth”구글이 그 단어를 대신 제안하는 것처럼 밤에 철자를 시작한다는 것을 의미합니다.

편집하다

@ThomasRutter : Douglas는이를 “통계 기계 학습”으로 설명합니다.

쿠키를 사용하여 어떤 사용자가 어떤 쿼리를 가져 왔는지 알기 때문에 누가 쿼리를 수정하는지 알고

사용자가 쿼리를 수행하고 사용자 중 10 %만이 결과를 클릭하고 90 %가 되돌아 가서 다른 단어 (정확한 단어 포함)를 입력하면 이번에는 90 %가 결과를 클릭하면 찾은 것을 알게됩니다. 정정.

또한 이들이 표시하는 모든 링크에 대한 정보를 가지고 있기 때문에 두 개의 서로 다른 “관련된”쿼리인지 알 수 있습니다.

또한, 이제 철자 검사에 컨텍스트를 포함 시키므로 컨텍스트에 따라 다른 단어를 제안 할 수도 있습니다.

철자가 자동으로 수정되도록 컨텍스트가 어떻게 고려되는지를 보여주는 이 Google 웨이브 데모 (44m 06s)를 참조하십시오 .

여기에 자연어 처리 방법이 설명되어 있습니다.

마지막으로 자동 기계 번역 (@ 1h 12m 47s)을 믹스에 추가하여 수행 할 수있는 작업에 대한 멋진 데모입니다 .


콘텐츠에 직접 건너 뛰기 위해 비디오에 분과 초의 앵커를 추가하여 작동하지 않으면 페이지를 다시로드하거나 손으로 마크를 스크롤하십시오.


답변

나는 몇 시간 전에이 문서를 발견 : 맞춤법 교정 작성하는 방법 에 의해 작성, 피터 노빅 (구글 사의 연구 이사).

“맞춤법 교정”주제에 대한 흥미로운 내용입니다. 예제는 파이썬으로되어 있지만 이해하기 쉽고 명확하며 알고리즘을 다른 언어로 쉽게 번역 할 수 있다고 생각합니다.

아래는 알고리즘에 대한 간단한 설명입니다. 알고리즘은 준비 및 단어 확인의 두 단계로 구성됩니다.

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

실제 검색어와 그 단어를 사용할 수 있다면 가장 좋습니다. 그렇지 않은 경우 큰 텍스트 집합을 대신 사용할 수 있습니다. 각 단어의 발생 (인기)을 세십시오.

2 단계. 단어 검사-검사 한 단어와 유사한 단어 찾기

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

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


답변

“당신은 의미 했습니까”알고리즘에 대한 이론은 정보 검색 소개 3 장을 참조하십시오. 그것은 사용할 수 있습니다 온라인 무료. 섹션 3.3 (52 페이지)은 귀하의 질문에 정확하게 답변합니다. 또한 업데이트에 구체적으로 대답하려면 단어 사전 만 있으면됩니다 (수백만 명의 사용자 포함).


답변

흠 … 구글은 방대한 양의 데이터 (인터넷)를 사용하여 심각한 NLP (Natural Language Processing)를 수행했다고 생각했다.

예를 들어, 전체 인터넷의 데이터가 너무 많아서 3 워드 시퀀스가 ​​발생하는 횟수를 계산할 수 있습니다 ( trigram 이라고 함 ). 따라서 “핑크 프 루거 콘서트”와 같은 문장을 보면 히트 횟수가 적다는 것을 알 수있을 것입니다.

그들은 분명히 Davide Gualano의 말을 변형시킨 것이므로 분명히 그 링크를 읽으십시오. 물론 구글은 알고있는 모든 웹 페이지를 코퍼스로 사용하므로 알고리즘이 특히 효과적입니다.


답변

내 생각에 그들은 Levenshtein 거리 알고리즘과 그들이 실행하는 검색에 관해 그들이 수집하는 대량의 데이터 의 조합을 사용한다고 생각 합니다. 입력 한 검색 문자열에서 Levenshtein 거리가 가장 짧은 검색 세트를 가져온 다음 가장 많은 검색 결과를 선택할 수 있습니다.


답변

일반적으로 생산 맞춤법 교정기는 여러 가지 방법론을 사용하여 맞춤법 제안을 제공합니다. 일부는 :

  • 철자 수정이 필요한지 결정하는 방법을 결정하십시오. 여기에는 불충분 한 결과, 구체적이지 않거나 정확하지 않은 결과 (일부 조치에 따라) 등이 포함될 수 있습니다.

  • 전체 또는 대부분 철자가 정확한 것으로 알려진 큰 본문 또는 사전을 사용하십시오. LingPipe 와 같은 곳에서 온라인으로 쉽게 찾을 수 있습니다 . 그런 다음 최선의 제안을 결정하기 위해 여러 측정 값을 기준으로 가장 가까운 단어를 찾습니다. 가장 직관적 인 것은 비슷한 캐릭터입니다. 연구와 실험을 통해 밝혀진 것은 2 ~ 3 개의 문자 시퀀스 일치가 더 잘 작동한다는 것입니다. (비 그램 및 트라이 그램). 결과를 더 향상 시키려면 단어의 시작 또는 끝에서 일치하는 점수가 더 높습니다. 성능상의 이유로이 모든 단어를 trigram 또는 bigram으로 색인화하여 조회를 수행 할 때 n-gram으로 변환하고 hashtable 또는 trie를 통해 조회하십시오.

  • 문자 위치에 따라 키보드 오류와 관련된 휴리스틱을 사용하십시오. ‘w’가 ‘e’에 가깝기 때문에 “hwllo”는 “hello”여야합니다.

  • 발음 키 (Soundex, Metaphone)를 사용하여 단어를 색인화하고 가능한 정정 사항을 찾아보십시오. 실제로 이것은 일반적으로 위에서 설명한 것처럼 n-gram 인덱싱을 사용하는 것보다 더 나쁜 결과를 반환합니다.

  • 각각의 경우 목록에서 최상의 수정을 선택해야합니다. 이것은 levenshtein, 키보드 메트릭 등과 같은 거리 메트릭 일 수 있습니다.

  • 여러 단어로 된 문구의 경우 한 단어 만 철자가 틀릴 수 있으며,이 경우 나머지 단어를 문맥 상 가장 일치하는 단어로 사용할 수 있습니다.


답변

사용 Levenshtein 거리 , 다음 인덱스 단어에 메트릭 트리 (또는 슬림 트리)를 만들 수 있습니다. 그런 다음 1-가장 가까운 이웃 쿼리를 실행하면 결과가 나타납니다.