Code_J

 Crawler에 의해 추출된 웹페이지를 적절히 Indexing 하기 위해서는 해당 문서에 본문영역을 추출(Filtering)하는 것은 검색의 정확도에 있어 매우 중요한 부분이다.

1. Unlink Text Node를 추출하여 Dom의 Node Depth가 같은 Node의 군집을 추출한다.  (실제 구현시에는 인접노드 추출후 재병합하는 방법을 사용하였는데, 이것은 이후에 설명을 하겠다)  2. Unlink Text의 밀도를 추출하여 대량의 Text가 밀집된 영역군을 추출하고 1번에서 추출된 후보군집과의 비교를 통해 최종 추출 노드들의 공통 parent node들을 추출하고 parent의 child내의 Text Node의 조합이 본문이 된다. 여기서 추출된 parent node는 1개 이상이 된다. 덧글과 같은 비링크 데이터가 존재할 수 있기 때문이다. 그래서 다수의 후보 node 군이 추출된다. 3. 기사의 내용이 지나치게 짧다거나 기사보다 내용이 긴 덧글 등은 본문 추출의 최대의 적이다.   - 사실상 짧은 내용의 기사일 경우 정확한 추출은 불가능하다. (여러 페이지 분석을 통한 템플릿 추출 이후 가능)   - 덧글 등은 Table 태그의 구조적 Pattern 양상을 보이므로, DOM 의 구조분석을 통해서 덧글 여부를 판별 할 수 있다. 4. 가장 이상적인 방법은 언론사 사이트의 메인페이지에서 동일 level(군집)의 Link를 추출하여, 동일한 페이지 구조 템플릿을 사용하는 페이지들을 분석하여, 본문에 해당되는 DOM Tree의 Path를 추출하는 방법이다.

역시나 YGHtml Parser 0.3.5 버전을 이용하여 주말에 구현해 보았습니다.

구현한 프로그램은 자주 바뀌는 뉴스페이지에 새롭게 추가되는 내용만을 추출하여 추출된 내용을 자체정의한 RSS 파일로 추출해주는 프로그램입니다.(웹 페이지 변경 실시간 검사)

아래는 네이버(http://www.naver.com)의 메인페이지를 제가 만든 RSS 추출기를 적용하여,
자체적으로 만든 JApplet 기반의 RSS Viewer로 출력되는 화면입니다.

네이버 같은 대형포털의 경우 거의 분단위로 신규정보가 추가되기 때문에,
즉 추가되는 데이터의 양이 많으므로 거의 실시간으로 새롭게 추가되는 정보를 확인하기 위해서 아래와 같은 형태로 구현하였습니다.

아래 프로그램에서 각 문장은 오른쪽으로 스크롤됩니다. (애니메이션 화면을 캡쳐한 것입니다.)
사용자는 아래 뷰어를 단순히 보고만 있는것 만으로도 현재 새롭게 추가되는 새로운 기사를 거의 실시간으로 확인 할 수 있습니다.


웹 페이지에서 신규정보(Anchor Text)를 추출하는 작업은 쉬운 작업이 아닙니다.
아래와 같은 과정을 거쳐 신규정보를 추출 할 수 있습니다.


- Target Site 에 대한 Parsing을 통하여 DOM Tree를 생성합니다.
- 이전 DOM Tree와 비교를 통해 신규정보를 추출합니다.
- 신규정보를 이전에 추출된 정보가 저장된 DB를 검색하여 중복여부를 검사합니다.
- 신규 추출 요소를 DB에 저장합니다.
  - 저장의 이유는 각 페이지 상 주기적 랜덤으로 표시정보로 인하여 신규정보 추출시 중복을 제거하기 위함입니다.
- 신규정보가 DB에 없을경우 최종 신규 정보로 추출됩니다.

아래는 위와 같이 구현하여 실제로 Console에 출력되는 모습입니다.
잘 동작합니다만 광고를 비롯한 불필요한 정보에 대한 필터링은 필요해 보입니다.

추출 정보의 Anchor Text와 URL 정보를 토대로 RSS를 구성합니다.
RSS 구성을 위해 해당 URL 페이지의 주제문장 영역 추출이 필요한데, 웹페이지 내용요약과 주제문장 추출을 위해서는 최소한 아래의 작업을 필요로 합니다.

- 웹페이지 잡음 영역제거(필터링)
- 한국어 형태소 분석
- 문서 핵심문장 추출(시소러스, 코퍼스 적용)

위 기술에 대한 구현 방식은 본 블로그의 Web by Agent 항목의 글들을 검색해 보시길 바랍니다.
(없는 내용이 더 많을 듯..ㅋ)
내용 요약 및 핵심영역 추출에 대한 내용은 정보과학회에 관련 내용이 많으니 그 쪽 논문의 검색도 추천합니다.

이상입니다.

* Applet RSS Viewer Demo를 웹페이지에 올릴만큼 다듬는데는 2주 정도 시간이 걸릴듯 하네요.

김영곤(gonni21c@gmail..)

주말을 이용하여 만들어본 웹크롤러..

일반적인 웹크롤러는 다음과 같은 과정으로 URL을 수집합니다..

- Root Site Source Download
- 해당 페이지에서 정규식을 이용하여 'http://www~' 와 같은 주소로 인식되는 문자열 추출
- 추출 주소에 대한 재귀적 반복 (깊이 우선 탐색 or 너비 우선 탐색)

위와 같은 구현은 단일 Thread로 구현시 재귀적 호출구조를 가지므로 간단하게 구현할 수 있지만..
일반적으로는 지정 Site에서 source를 download할때 network blocking time이 크기 때문에.. (CPU를 최대로 활용 못함)

보통 Crawler는 MultiThread기반으로 만들어 집니다.

아래는 위에서 설명한 크롤러와는 틀리게 Anchor Text 기반 URL 및 Anchor Text(링크문장) 추출하는 크롤러..

다음은 위의 크롤러를 구현하면서 생각해본 크롤러 구현시 고려사항들 입니다..

1. 최근 검색의 추세로 볼때 Crawling 된 URL을 잘 활용하기 위해서는 ..
URL을 대표하는 문자열로 볼수 있는 Anchor Text의 추출이 데이터 활용 측면에서 유용해 보입니다.
물론 이러한 추출을 위해서는 HTML lexing이 필요하므로 정규식을 사용한 URL 추출보다는 속도상 손해를 감수해야 합니다.

2. Crawling 시 최대한 데이터를 빨리 수집하기 위해서는 CPU 자원을 최대로 활용할 수 있어야 한다는 것입니다.
앞서 설명했듯이 Network 사용으로 인한 Blocking으로 단일 Thread로는 자원을 최대로 쓸 수 없습니다.
 
 위의 Crawler는 Blocking Thread Pool을 이용하여 동시에 4개의 Thread가 URL-Anchor Data를 수집합니다..
하나의 주소에 대해서 Crawling Thread가 생성되면 Thread 객체 생성이 과다하므로 Thread Pool의 사용도 필수적이라 할 수 있습니다.
 
물론 Pool의 구현도 Blocking이 아닌 NonBlocking 으로 구현시 더할 나위 없겠죠..

기초적인 Thread Pool의 구현은 아래 Site를 참고하세요..
http://gyro74.zerois.net/lecture/threadpool.htm

3. Crawler의 최대 난제는 수집정보의 중복을 제거하는 것입니다.
 하나의 Root에서 시작되는 크롤러는 다수의 파생 페이지를 연쇄적으로 Crawling 하므로, 유기적인 연결구조를 가지는 웹문서의 특성상 반드시 다수의 페이지에서 중복 URL이 발생 할 수 밖에 없습니다.
이러한 중복을 check 하기 위해서 위의 크롤러에서는 검색이 빠른 Hash 함수를 사용했습니다만 depth가 깊어짐에 따라 저장 자료가 급격히 늘어나 결국 heap space Exception으로 프로그램이 종료되는 현상이 발생 하였습니다.

즉, URL 중복을 고속으로 검사하기 위해서는 추출 데이터를 메모리상에 유지해야 하지만 용량의 한계가 있기때문에, 메모리의 용량과 속도와의 타협점이 필요하다는 것입니다. 물론 중복으로 데이터를 수집하고 수집데이터에 대해 2차 보정 작업을 거치는 구현으로도 이 문제를 해결 할 수 있습니다.

결론은, Crawler를 제대로 구현할려면,
NonBlocking Queue 기반의 Crawler Process Pool,
CPU 사용량 check에 의한 Pool Size의 동적 조절,
데이터 중복 검사를 위한 적절한 자료구조의 개발이 필수적으로 보입니다.

웹페이지 잡음영역 필터링, 핵심내용 영역 추출을 구현하여 기사 페이지의 해상도 변환 기능을 구현.

잡음(?)영역 필터링은 웹페이지의 광고영역, 템플릿영역, 네비게이션 영역 등을 제거하여,
웹페이지의 핵심내용을 추출하는 기능이다.

예제인 아래 페이지의 가로 해상도는 1024 해상도이다.
하지만 페이지에서 실제 주내용 영역은 붉은색 사각형으로 체크된 부분이고..
나머지 부분은 실제 주내용에서 관련 없는 광고나 네비게이션 영역으로 구성된다..

PC의 웹브라우저로 페이지를 봤을때는 큰 문제가 없으나,
성능이 떨어지는 모바일 장비의 브라우저로 이 페이지를 열어 보았을때,
불필요한 영역까지 Rendering 하는것은 상당한 과부하가 아닐수 없다..

그래서 웹페이지에서 핵심영역의 내용만을 추출하여,
모바일 장비의 가로해상도에 맞춰 Page의 View를 변환하는 기능을 구현해 보았다.

아래는 위에 설명한 기능을 구현한 것이다.
가로 해상도를 320으로 설정하여 페이지를 변환 PC 브라우저에서 열어본 모습이다.


하나의 페이지는 핵심내용 추출영역과 Navigation 영역으로 2개의 페이지로 추출된다.

아래의 Demo Site에서 다른 기사류의 페이지도 확인해 볼 수 있다.

해상도 변환 Demo Site 가기

URL란에 변환을 원하는 사이트를 입력하고 변환 버튼을 누르면 변환페이지가 출력된다.

** 네비게이션 영역은 아직 미구현이며, 주로 네이버, 조선일부 페이지 위주로 테스트 하였으므로 다른 사이트의 오동작 가능성 높음.

이런 기능외에도 검색엔진이나 웹에이전트를 개발해본 사람이라면  
아주 써먹을 데가 많다는데 반론의 여지가 없을 것이다.ㅋ

김영곤(gonni21c@gmail.com)

YGHtml Parser VIewer로 국내주요 포탈사이트의 시작페이지를 분석해 보았다.

국내 1위의 네이버..
처리 Token 수 : 2359
대형포탈 중에서도 가장 작은 Token수를 자랑했다.

요즘 한창 말이 많아 페이지 뷰가 증가하고 있는 다음..
처리 대상 Token 수 : 2815
토큰수로 봐서는 네이버와 거의 비슷한 복잡도..
하지만 자바스크립트 코드가 네이버 보다는 훨씬 많은양이 Rendering되어 브라우저 부하량은 Token수에 비해 클것으로 판단됨..

야후코리아
처리 대상 Token수 : 4203
네이버나 다음에 비해 Token의 수가 월등히 많음..
 
마지막으로 네이트..
처리 대상  Token 수 : 5002
처리대상 Token수에서 아마 국내 최고의 복잡도를 자랑할듯..
네이버에 2배에 육박한다..
처리복잡도만 고려하면 도저히 답이 안나오는 Site다..


참고로..
아래는 친절한 구글이..
처리 대상 Token 수 : 268
처리 토큰수가 네이버에 10분의 1수준이다..

국내 포탈, 구글의 특수성을 고려하더라도..
폰이나 MP3, PMP등의 제한적인 H/W 성능을 가지는 장비로도 인터넷 브라우저 사용이 급격히 증가되고 있는 요즘,
국내 포탈의 페이지 복잡도는 한번쯤 생각해봐야 할 문제가 아닌가 생각된다..

웹페이지 주내용 추출은 기술적으로 쉽지않은 기술 중에 하나다.
HTML 문법 자체도 워낙이 변칙적이고, HTML의 정규화 과정을 거쳐 DOM Tree를 생성했다 해도..
변화무쌍한 웹페이지의 특성상, 단순 Parse Tree의 탐색에 의한 알고리즘만으로는 한계가 있으며,
데이타 마이닝이나 크롤링에 의한 문서 Template 추출에 의한 방법등의 고수준의 2차 이후 보정작업이 필요하다.

하지만..
단순 DOM Tree만을 이용하여, 간단한 알고리즘만으로도 70% 정도의 정확도를 가지는 주내용 추출기의 구현은 가능하다..

[추후추가 그림]
[주내용 추출의 원리]

아래의 사진은 해당 알고리즘을 이용하여 원본 페이지에서 주내용 추출후, 주 내용에서 주제문장을 추출하는 기능의 일부분이다.

              [원본문서]


            [축약처리된 문서]

위 그림에서 처럼, 원본 페이지의 광고영역, 네비게이션 영역, 기타 정보 영역은 제거되고 문서의 핵심내용만 추출된 모습을 볼 수 있다. 붉은 색에 해당하는 문장은 추가적으로 핵심내용에서 주제문 추출 알고리즘을 적용하여 추출된 문서를 가장 잘 대표할 수 있는 문장이다.

해당 기능을 활용하면 아래와 같은 응용구현도 가능하다.
아래의 그림은 원본 문서에서 필터링을 적용, 주내용, 그림을 추출하여, 해상도가 제한적인 모바일 장비에서 해당페이지의 내용의 손실없이 볼 수 있도록 하는 페이지 제가공 기능이다.

                                      [원본 페이지]
                                      [300px 해상도로 변환된 페이지]

아래의 기능은 소스페이지를 제가공(주내용 추출, 해상도 변환)을 거쳐 실제로 핸드폰으로 실제 웹사이트상의 웹페이지의 내용을 보여주고 있다.

               [실제 인터넷 상의 페이지를 해상도가 낮은 장비에서도 손쉽게 확인 할 수 있다]

해상도가 제한적인 장비에서 별도의 좌우 스크롤 없이도 손실없는 내용을 확인 할 수 있으며, 하나의 페이지에 대해서 주내용 모드와 네비게이션 모드로 나누어 작은 화면에서 실 인터넷 사이트의 내용을 손쉽게 확인 할 수 있다.

** 위 사진은 2006년 제작된 PIAS의 실제 구현 기능임.