[performance] Google이 어떻게 그렇게 빠를 수 있습니까?

내가 웃긴 사실을 발견 한 한 가지 사실은 Google이 실제로 생물 정보학에 의해 운영된다는 것입니다 ( ‘좋아요, 내가 생물 인 자라서 재미 있다고 생각합니다. 설명하겠습니다.

생물 정보학은 초기에 거대한 문자열의 작은 텍스트를 매우 빠르게 검색하는 데 어려움을 겪었습니다. 우리에게“거대한 끈”은 당연히 DNA입니다. 종종 단일 DNA가 아니라 다른 종 / 개체의 여러 DNA 데이터베이스입니다. 작은 텍스트는 단백질이거나 그에 상응하는 유전자 인 유전자입니다. 컴퓨터 생물학 자의 첫 번째 작업의 대부분은 유전자 간의 상 동성을 찾는 것으로 제한되었습니다. 이것은 이미 알려진 유전자와의 유사점을 주목하여 새로 발견 된 유전자의 기능을 확립하기 위해 수행됩니다.

이제 이러한 DNA 문자열은 실제로 매우 커지고 (손실이 있습니다!) 검색을 매우 효율적으로 수행해야합니다. 따라서 현대의 문자열 조회 이론의 대부분은 컴퓨터 생물학의 맥락에서 개발되었습니다.

그러나 꽤 오래 전부터 기존의 텍스트 검색이 소진되었습니다. 즉, 각각의 단일 문자를 보지 않고도 부 선형 시간에 큰 문자열을 검색 할 수있는 새로운 접근 방식이 필요했습니다. 이것은 큰 문자열을 사전 처리하고 그 위에 특별한 인덱스 데이터 구조를 구축함으로써 해결할 수 있음을 발견했습니다. 많은 다른 데이터 구조가 제안되었습니다. 각각 장단점이 있지만 일정한 시간에 조회가 가능하기 때문에 특히 주목할만한 것이 있습니다. 이제 Google이 운영하는 규모에 따라 서버 간의 부하 분산, 전처리 및 기타 정교한 작업을 고려해야하기 때문에 더 이상 엄격하게 사실이 아닙니다.

그러나 본질적으로 소위 q-gram 인덱스 는 일정한 시간에 조회를 허용합니다. 유일한 단점은 데이터 구조가 엄청나게 커진다는 것입니다. 기본적으로 최대 q 자 (따라서 이름) 의 문자열 조회를 허용 하려면 가능한 q 문자 조합 (즉, q ^S , 여기서 S 는 알파벳 크기)에 대해 하나의 필드가있는 테이블이 필요합니다. , 36 (= 26 + 10)). 또한 인덱싱 된 문자열의 각 문자 위치에 대해 하나의 필드가 있어야합니다 (또는 Google의 경우 각 웹 사이트에 대해).

깎아 지른듯한 크기를 완화하기 위해, 구글은 아마 여러 인덱스를 사용합니다 (사실, 그들이 어떻게 , 맞춤법 교정 등의 제공 서비스). 맨 위에있는 것은 문자 수준에서 작동하지 않고 대신 단어 수준에서 작동합니다. 이것은 q를 줄이지 만 S를 무한히 커지게하여 무한한 수의 다른 단어에 대처하기 위해 해싱 및 충돌 테이블을 사용해야합니다.

다음 수준에서 이러한 해시 된 단어는 다른 인덱스 데이터 구조를 가리키고 차례로 웹 사이트를 가리키는 문자를 해시합니다.

간단히 말해서, 이러한 q- gram 인덱스 데이터 구조는 틀림없이 Google 검색 알고리즘의 가장 핵심적인 부분입니다. 불행히도, q -gram 인덱스의 작동 방식을 설명하는 비 기술적 인 논문은 없습니다 . 그러한 색인이 어떻게 작동하는지에 대한 설명을 포함하는 내가 아는 유일한 출판물은… 아아, 나의 학사 논문 입니다.