크롤러와 크롤링

웹 크롤러

웹페이지를 한 개 가져오고, 그 페이지가 가리키는 모든 웹페이지를 가져오고, 다시 그페이지들이 가리키는 모든 웹페이지를 가져오는 일을 재귀적으로 반복하는 웹을 순회하는 로봇이다.

인터넷 검색엔진은 웹을 돌아가디면서 그들이 만나는 모든 문서를 끌어오기 위해 크롤러를 사용한다.

시작지점 : 루트 집합

[!info] 루트 집합(root set) 크롤러가 방문을 시작하는 URL들의 초기 집합

일반적으로 좋은 루트 집합은 크고 인기있는 웹사이트, 새로 생성된 페이지들의 목록, 자주 링크되지 않는 잘 알려져 있지 않은 페이지들의 목록으로 구성되어 있다.

순환 피하기

image-85.png

로봇이 웹 크롤링을 할 때 루프나 순환에 빠지지 않도록 매우 조심해야한다. 사진처럼 링크를 단순히 따라가기만 하면 순환이 있는 링크에 계속 머물 수도 있다. 순환을 피하기 위해서는 반드시 그들이 어디를 방문했는지 알아야 한다.

루프가 크롤러에게 해로운 이유

  1. 크롤러를 루프에 빠뜨려서 꼼짝 못하게 만들 수 있다.
  2. 같은 페이지를 반복해서 가져오면 고스란히 웹 서버의 부담이 된다. 실제 사용자도 사이트에 접긍할 수 없도록 막아버리게 될 수도 있다.
  3. 크롤러는 많은 수의 중복된 페이지를 가져오게 된다. 예로 수백개의 정확히 똑같은 페이지를 반환하는 인터넷 검색엔진이 있다.

어떻게 방문한 URL을 저장할 것인가?

세상에는 수십억개의 서로 다른 웹페이지들이 존재한다. 이를 위해 수십억 개의 URL에 대해 어디를 방문했었는지 계속 추적하는 작업은 꽤나 도전적일 수 있다.

속도와 메모리 사용 면에서 효과적이며, 빠르게 방문한 url을 알기 위하여 복잡한 자료구조를 사용해야만 한다.

방법들

  1. 트리와 해시 테이블 해시 테이블을 통해서 빠른 검색
  2. 느슨한 존재 비트맵 존재 비트 배열(presence bit array)같은 느슨한 자료 구조를 사용한다. 크롤링 시, URL을 해시 함수에 넣어 고정된 크기의 숫자로 변환 후, 이와 대응하는 존재비트를 생성한다. 존재비트는 배열 내에 존재하는 원소로 해당 원소에 체크해둔다. (당연히 배열 접근이니까 O(1)이다.)

추가적인 내용들