algorithm - machine - seq2seq spell check




Google은 "당신이 원하셨습니까?"알고리즘 작동 방식은 무엇입니까? (12)

나는 포트폴리오 관리 도구를위한 내부 웹 사이트를 개발 해왔다. 많은 텍스트 데이터, 회사 이름 등이 있습니다. "검색하셨습니까 : xxxx"라는 검색어에 매우 신속하게 응답 할 수있는 검색 엔진 기능에 정말 감동했습니다.

나는 지능적으로 사용자 쿼리를 취할 수 있어야하고 원시 검색 결과뿐만 아니라 "응답하셨습니까?"라고 응답 할 수 있어야합니다. 대체 가능성이 높은 답변 등이있을 때 응답

[나는 ASP.NET 에서 개발 중이다 (VB - 나에 대해 잡아 먹지 마라!)]

업데이트 : 좋아, 어떻게 수백만의 '미 지불 사용자'없이 이것을 모방 할 수 있습니까?

  • '알려진'용어 또는 '올바른'용어에 대한 오타를 생성하고 조회를 수행합니까?
  • 좀 더 우아한 방법?

"당신이 의미 한"알고리즘에 대한 정보 검색 소개의 3 장을 참조 할 수 있습니다. 무료로 online 에서 사용할 수 online . 3.3 절 (52 쪽)에 정확하게 답해 준다. 특히 업데이트에 대한 답변을 얻으려면 단어 사전 만 있으면되고 수백만 명의 사용자가 필요합니다.


Google은 정확한 결과가 나오는 검색어를 제안했지만 올바르게 작성된 검색어는 제안하지 않았습니다. 그러나이 경우 아마 맞춤법 교정기가 더 적합 할 것입니다. 물론 결과가 얼마나 좋은지에 대한 통계를 토대로 모든 쿼리에 대한 가치를 저장할 수 있습니다.

그래서,

  1. 사전이 필요합니다 (영어 또는 데이터 기반)

  2. 단어 격자를 생성하고 사전을 사용하여 전환에 대한 확률을 계산하십시오.

  3. 트 렐리 스를 사용하여 최소 오류 거리를 계산하는 디코더를 추가하십시오. 물론 거리를 계산할 때 삽입 및 삭제를 처리해야합니다. 재미있는 점은 QWERTY 키보드가 서로 가까이있는 키를 치면 거리를 최대화한다는 것입니다. (cae는 자동차를 돌릴 것이고 cay는 고양이를 돌릴 것입니다)

  4. 최소의 거리를 가지는 단어를 돌려줍니다.

  5. 그런 다음 쿼리 데이터베이스와 비교하여 다른 근접 일치에 대해 더 나은 결과가 있는지 확인할 수 있습니다.


근원에서 (거의) 설명은 여기있다.

101 검색!

분 22시 3 분에

볼 가치가있는!

기본적으로 Google의 더글러스 메릴 (Douglas Merrill) 전 CTO에 따르면 다음과 같습니다.

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

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

3) 검색 상자에 단어를 다시 쓸 수 있도록 단어의 철자가 틀린 것을 알고 있습니다.

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

이 패턴에는 수백만 배가 곱셈되어 가장 흔히 쓰이는 철자 오류와 가장 일반적인 "교정"오류가 표시됩니다.

이렇게하면 Google이 거의 모든 언어로 맞춤법을 제공 할 수 있습니다.

또한 이것은 "밤새"Google이 그 단어를 대신 제안 할 때 밤새 철자를 시작하는 경우를 의미합니다.

편집하다

@ThomasRutter : Douglas는 이것을 "통계 기계 학습"이라고 설명합니다.

그들은 어떤 쿼리가 어떤 사용자 (쿠키를 사용)에서 왔는지 알기 때문에 누가 쿼리를 수정했는지 알 수 있습니다.

사용자가 쿼리를 수행하고 사용자 중 10 % 만 결과를 클릭하고 90 %가 돌아가서 다른 단어 (수정 된 단어 포함)를 입력하고 90 %가 결과를 클릭하면 이번에는 발견 된 것으로 나타납니다 수정.

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

게다가, 그들은 지금 문맥을 문법 검사에 포함하고 있습니다, 그래서 그들은 문맥에 따라 다른 단어를 제안 할 수 있습니다.

맞춤법을 자동으로 수정하기 위해 컨텍스트가 고려되는 방법을 보여주는 google 파 (@ 44m 06s) 데모를 참조하십시오.

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

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

동영상에 분 및 초 앵커를 추가하여 콘텐츠로 직접 건너 뛰거나 작동하지 않는 경우 페이지를 다시로드하거나 손으로 마크로 스크롤 해 봅니다.


단순한. 그들은 많은 양의 데이터를 가지고 있습니다. 그들은 검색어를 얼마나 자주 사용하는지에 따라 가능한 모든 용어에 대한 통계를 가지고 있으며, 사용자가 클릭 한 결과가 일반적으로 어떤 결과로 나타나는지 ... 그래서 검색 용어에 대해 자주 철자를 잘못 입력했다고 생각하면 제안을 제안합니다 더 평범한 대답.

실제로, 잘못 철자가 가장 자주 검색된 용어 인 경우, algorythm은 올바른 단어를 취합니다.


몇 년 전에 뭔가를 보았으므로 이후 변경되었을 수 있습니다. 그러나 분명히 짧은 시간 내에 매우 유사한 쿼리를 제출하는 동일한 사용자에 대한 로그를 분석하여 시작했으며 사용자가 수정 한 방법에 따라 기계 학습을 사용했습니다 그들 자신.


부분 일치 및 근접 인접 검색 을 자연스럽게 지원하는 특정 데이터 구조 ( 3 진 검색 트리) 가 있습니다.


위의 답변을 제외하고, 직접 무언가를 구현하려는 경우, 여기에 제안 사항이 있습니다.

연산

GitHub 에서이 알고리즘의 구현과 상세한 문서를 찾을 수 있습니다.

  • 비교 자로 우선 순위 대기열을 만듭니다.
  • Ternay Search Tree를 만들고 그 빈도와 함께 모든 영어 단어 ( Norvig의 게시물에서 )를 삽입하십시오.
  • TST를 건너 뛰고 TST에서 만나는 모든 단어에 대해 input_word에서 Levenshtein Distance ( LD )를 계산합니다.
  • LD ≤ 3이면 우선 순위 대기열에 넣습니다.
  • 마지막으로 우선 순위 대기열에서 10 단어를 추출하여 표시합니다.

이것은 오래된 질문이며, 아무도 Apache Solr을 사용하여 OP를 제안한 것이 놀랍습니다.

Apache Solr는 다른 많은 기능 외에도 맞춤법 검사 또는 쿼리 제안을 제공하는 전체 텍스트 검색 엔진입니다. documentation :

기본적으로 Lucene 맞춤법 검사기는 먼저 문자열 거리 계산의 점수로 제안을 정렬하고 색인에서 제안의 빈도 (가능한 경우)로 정렬합니다.


추측에 따르면 ...

  1. 단어 검색
  2. 발견되지 않으면 단어를 "추측"하려고 시도하는 알고리즘을 사용하십시오.

Hopfield 네트워크 나 백 전파 네트워크 또는 뭔가 다른 "지문 식별", 깨진 데이터 복원 또는 Davide가 이미 언급 한대로 맞춤법 교정과 같은 인공 지능에서 발생할 수 있습니다 ...


필자가 찾은 가장 좋은 답변 은 Google의 Peter Irvig 연구 책임자가 구현하고 설명하는 맞춤법 교정기입니다.

이 이론의 배경에 대해 더 알고 싶다면 그의 책의 장을 읽으십시오.

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


필자는 얼마 전에이 기사를 보았습니다 : Peter Norvig (Google Inc. 연구 이사)가 작성한 철자 교정자 작성 방법 .

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

다음은 알고리즘에 대한 간단한 설명입니다. 알고리즘은 준비와 단어 검사의 두 단계로 구성됩니다.

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

가장 좋은 방법은 실제 검색어와 해당 검색어를 사용할 수 있는지 여부입니다. 그렇게하지 않으면 큰 텍스트 집합을 대신 사용할 수 있습니다. 각 단어의 출현 (인기)을 계산합니다.

2 단계. 단어 검사 - 확인한 단어와 유사한 단어를 찾습니다.

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

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


흠 ... 나는 구글이 방대한 NLP (Natural Language Processing)를하기 위해 방대한 자료 (인터넷)를 사용했다고 생각했다.

예를 들어, 그들은 인터넷 전체에서 나오는 많은 양의 데이터를 가지고있어 3 단어 시퀀스가 ​​발생하는 횟수를 세는 수 있습니다 ( 트라이 그램 이라고 함). 따라서 "핑크색 frugr 콘서트"와 같은 문장을 보게되면 히트 곡이 거의 없다는 것을 알게되고 가장 큰 "핑크색 콘서트"가 코퍼스에서 발견됩니다.

그들은 명백하게 Davide Gualano가 말하고있는 것의 변형을 분명히하지만, 분명히 그 링크를 읽습니다. Google은 물론 코퍼스로 알고있는 모든 웹 페이지를 사용하므로 알고리즘이 특히 효과적입니다.





text-search