웹 크롤로 검색일을 시작 해서 그런지 웹 크롤의 여러 이슈에 대해서 지금도 많은 관심이 있다. 그러다 구글에서 연구하고 실제 적용한 Deep Crawl알고리즘을 틈틈히 지하철에서 살펴볼 기회가 있었다.

구글이 이야기하는 Deep Crawl은, Form 태크의 실행(submission)으로 생성되는 get방식의  URL을 어떻게 하면 정보가 많게끔 자동으로 생성해 내느냐를 고민한 결과였다. 실제 아래와 같은 폼들을 이용해 검색 하는 방식이 주된 타겟이다. 세보면 알겠지만 아래 폼만 해더라도 엄청난 개수의 경우의 URL들이 나오게 된다. 근데, 그 URL들이 판매되는 자동차 대수만큼은 되지 않을 거라는것 정도는 쉽게 예측할 수 있을 것이다.

이들 링크들을 만들어 내기 위한 기존의 방법은 이랬다.

먼저 일반적인 버티컬 검색에서 사용하는 방법으로 각 form의 여러 요소들에 대해 시멘틱 매핑을 시켜서 이들 결과를 바로 제공하는 방식이 첫번째 방법이고, 두번째 방법은 한 도메인 내의 정보가 많이 있을만한 form의 형식을 미리 특정 URL로 생성시켜 이들을 바로 검색엔진 크롤러의 시드로 제공해 결과 페이지들과 해당 URL들을 수집하는 방식이다. 예를 들어 중고 자동차 사이트의 검색 옵션 체크박스와 리스트 컨트롤의 목록 게다가 입력되는 무작위 텍스트를 위한 인풋 텍스트 박스를 생각하자면 얼마나 많은 수의 URL들이 생성될지 감이 올 것이다. 사실 모든 경우의 URL을 생성한다 하더라도 이들 대부분의 것들은 아무 결과도 가지지 못할 경우가 많을 것이다.

그리고 위 방법들 모두 특정 도메인에 대해서 미리 선 작업을 해야 하는 노가다 성의 작업이라는게 가장 큰 문제다.

이리하여 구글이 고민을 시작했는데, 그들의 고민이 두 가지로 압축된다.

1. 어떻게 하면 정보성 있는 URL template를 만들어 낼 것이가.

2. 알고리즘이 적은수의 URL을 만들어낼 수록 사이트 콘텐츠의 커버리지는 적어지는데, 이들에 대한 벨런스를 어떻게 맞출것인가?

3. 일반적인 검색 상자에 들어갈 텍스트와 주민등록번호나 우편번호처럼 포맷이 정해진 텍스트 상자에 어떤 값을 넣어야 양질의 콘텐츠를 수집할 것인가가 마지막 고민이였다.

첫번째, URL 템플릿을 만들기 위해 시작점은, 표현만 바꾸는 입력을 제외시키는 것이다. 예를 들어서 sorting 옵션은 정보의 내용을 바꾸지 않으면서 순서만 바꾼다. 이런 결과들은 정보의 중복만 일으키니 이들 옵션들은 제외시키는것이 좋다.

두번째는 너무 많거나 적은 인자를 피해야 하는데, 직관적으로도 인자가 많다고 해서 내부 데이터베이스의 정보가 반드시 많다는건 의미하지 않기 때문이다.

이들을 고려하면서 URL 템플릿의 정보성 테스트를 수행하게 된다.

정보성 테스트는 만들어진 템플릿에 대해서 콘텐츠를 실제 수집한 다음에 이들에 대해서 클러스터링을 수행해 이들 콘텐츠의 클러스터가 특정 클러스터 수 이상으로 나온다면 이 템플릿은 옵션 하나의 변경으로 인해 다양한 정보들이 나오는 정보성 템플릿으로 분류하게 된다. 따라서 이런 테스트를 인자가 하나일때부터 n개 일때까지 반복하면서 Greedy한 방법으로 정보성 템플릿을 만들어 가게 된다. 물론 한없이 옵션을 더해 들어가기 보다는 어느 수준에 이르면 템플릿 수집을 멈추게끔 적절한 한계설정이 필요하겠다.

이런 식으로 템플릿을 만들었으면 이제 그 안에 어떤 값이 들어가느냐의 이야기가 남았다.

일반적으로 자유로운 포맷의 input textbox의 경우는 시드 옵션값들로 URL셋을 만들어 최대한 수집한 다음 이들 수집된 콘텐츠에서 단어를 추출해 이들을 다시 form의 text input값으로 쓰게 된다. 물론 키워드 자체도 tf-idf와 같은 방법으로 주제어 성질이 강한 것들을 모으는 테크닉이 필요할 것이다.

마지막으로 우편번호, 주민등록 번호와 같은 정형화된 값을 요구하는 텍스트박스값의 경우에는 미리 자주 쓰이는 포맷들의 값들을 보유하면서 이들 값들에 대해서 정보성 테스트를 다시 수행해 가장 많은 정보를 주는 포맷값이 무엇인지 판단하는 과정이 필요하다.

사실 본인도 예전에 구글 검색 결과 상위에 이런방식으로 만들어진거라 추정되는 url들을 본적이 있었다. 구글에서 이 링크들이 어디서 나왔는지 추적을 해봐도 흡사 시드인것처럼 보였던 놈들이었다. 지금도 생각나는데, 그들중에 가장 많이 눈에 띈 것이 다음의 사전 검색 결과물들이였다.

지금에서야, 이들이 어떻게 만들어진 것들이지 감이 오기 시작한다. 웹 어느곳에서 링크가 된 것들이 아니라 실제 로봇이 스스로 만들어낸 Url이라는것을 말이다. 사실 사전 검색과 같은 것은 사전 컨텐츠 내부의 단어들을 다시 이용해 검색을 하는 방식으로 웹 로봇이 url 템플릿과 입력 텍스트를 만들어 내면 되기 때문에 아마도 가장 쉬운 대상이 아니지 않았을까 생각해본다.

관련 논문에서 더 자세한 내용이 나오지만 이만 줄인다. 세계에 산재된 많은 링크들도 모자라서 더 욕심을 내고 있는 구글이니까 가능한 논문이지 않을까 하는 생각도 들지만, 읽어두면 언제가 도움이 될거라 믿는다. (WIKI)

ps. 아, 요즘은 자세하게 블로그 글 쓰는것도 힘들구나…. 쩝..

Deep Crawl by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.