검색 엔진을 만드는 데 대한 질문이요
웹페이지 검색 엔진을 한번 만들어 보고 싶은데요
물론 당장 구글 같은 화려하고 강력한 검색 엔진을 만든다는 것은 절대 불가능하겠지만
간단한 뼈대라도 한번 나름대로 만들어 보고 싶은데
웹페이지 검색 엔진을 만들려면 무엇무엇을 공부해야 하죠?
(물론 몇달만에 뚝딱 만들겠다는 것은 아니고 1년, 2년 그 이상 걸리더라도
지금 공부하면서 한번 만들어가보겠다는 것입니다. 경험삼아)
(일단 저는 지금 컴퓨터공학을 공부하고 있는 학생이고
아는 것이라고는 C언어밖에 모릅니다)
그 수많은 웹페이지에서 검색어를 검색하는 원리는 무엇일까요?
검색 사이트마다 검색하는 방법이 비공개일 것 같긴 한데
기본적인 검색 방법이 있긴 하겠죠..?
어디에 어떻게 있을지도 모르는 웹사이트들을 어떻게 찾아내는 거죠?
웹사이트 측에서 검색 사이트에 일일이 등록을 하는건지..
검색 엔진 만드는건 C언어랑 무관한 것인지는 모르지만 제가 아는게 C언어밖에 없어서
되도록이면 C언어로 만들거나 C언어를 이용해서 만드는 방법으로 알려주셨으면 좋겠고요
아니라면 다른 어떤 언어를 알아야 하고 어떤 것들을 알고 공부해야 하는지 알려주세요
C언어 아니더라도 효율적인 방법이라던가 많이 쓰이는 강력한 방법 이런 거요
그러니까 제 질문은 다시 말해서 웹페이지 검색 엔진을 만드는 방법이나 테크닉이 아니라
검색 엔진을 만들려면 어떤 언어를 공부해야 하고
어떤 것들을 공부해야 하는지 입니다
예를 들어서 C++, ASP, CGI, UNIX, PHP, KBS, MBC, 알고리즘 등을 공부해야 합니다! 이렇게 답변주세요
(제가 잘 몰라서 그냥 예시로 아무거나 나열한 것입니다.ㅡ.ㅡ;)
아 그리고 메신저 만들려면 무엇을 공부해야 하는지도 덤으로 알려주셨으면 더욱 감사드리겠습니다.
검색엔진은 크게
검색엔진은 크게 3부분으로 나뉘는데요,
1. crawl
2. 색인 DB 생성
3. 검색
crawl은 웹문서를 긁어오는 엔진입니다. 웹문서를 긁어오고 링크의 그래프를 만든다음에, 그래프를 방문하면서, 웹문서를 긁어옵니다.
crawl로 얻어온 문서를 이용해서, 의 목록을 만드는 작업입니다. 문서를 토큰을 이용해서 쪼갠다음에, 의 목록을 만들고 나중에 이걸 다시 로 역변환 해서 파일로 저장합니다. 검색은 실질적으로 Term을 키로 하기 때문에, 정렬되어서 저장이 되어야 겠죠.
검색엔진은 사용자 질의어를 분석후 색인DB를 뒤져서 해당 Term을 포함한 문서의 정보를 얻어오는 부분입니다. 단순히 가져오는 정도로는 원하는 품질의 검색결과를 내놓을 수 없기 때문에, 나름대로의 검색알고리즘이 필요한 영역입니다.
필요한 기술은 대략 다음과 같습니다.
1. 대용량 데이터 처리기술, 1억건의 문서가 있다면 1주일이내에 crawl을 해서 색인파일을 생성해야 합니다. 물론 crawl엔진을 만드는 것도 상당한 도전과제인데, nutch와 같이 잘만들어진 툴이 있으니 이 툴을 사용하면 될겁니다.
대용량 분산처리 기술을 위해서 MapReduce 프로그래밍 모델이 사용되고 있습니다. 이 기술로 crawl, 색인DB생성등의 작업을 더 빠른시간내에 처리할 수 있습니다.
2. 효과적인 검색 알고리즘
검색엔진의 최소 요구사항은 100만건의 문서에서 검색어를 던졌을 때, 최소 0.5초 이내에 결과가 나오도록 해야 한다는 겁니다. 이건 순전히 자료구조와 알고리즘과 연관된 문제죠.
일반적인 방법으로 문서를 검색하고 스코어공식을 적용해서는 이 요구사항을 만족 시킬 수가 없거든요.
이건 캐쉬를 사용하지 않았음을 가정했을 때의 요구사항이구요, 캐쉬등을 사용할 것을 가정 하면 1000000만 건 문서 기준 0.5초이내로 시간을 맞추어야 합니다.
3. 형태소 분석
특히 한글문서를 제대로 검색하기 위해서는 필수적이며, 제대로 만들고자 한다면, 이 자체가 하나의 과제입니다. 네이버와 같은 포털에 형태소분석기만을 납품하는 회사가 있을 정도니까요.
검색엔진 기술은 구글수준의 품질을 요구한다고 봤을 때 이미 거의 완성단계에 이르렀습니다. 수행속도 부분을 제외하고 본다면, 구글과 공개검색엔진과 큰 차이가 나지 않는 수준이라고 볼 수 있습니다.
우선 공개검색엔진인 lucene&nutch쪽을 한번 보시기 바랍니다. 문서의 양이 크지 않다면, (좀 느리긴 해도) 꽤나 괜찮은 결과를 보여주는 검색시스템을 만들 수 있을 겁니다. 물론 한글문서의 경우 형태소 분석기가 붙어있지 않다면, 좀 문제가 있긴 하지만, 검색엔진 원론적인 기능으로 보자면 훌륭한 시스템의 구성이 가능합니다. 참고로 이들은 Java로 만들어졌습니다. lucene의 경우에는 C,C++로 만들어진 것들이 있지만, 분산처리를 맡고 있는 nutch쪽에는 마땅한 대안이 없습니다.
만약... 문서의 양을 천만단위로 늘리게 된다면, 분산시스템/분산처리라는 새로운 문제에 직면하게 될겁니다. 위에 소개한 nutch가 분산시스템 환경을 구현하고 있긴 하지만, 그대로 사용해서는 성능이 나오지 않기 때문에, 상당히 많은 튜닝과 서버구성에 있어서 기술적인 고민을 해야 합니다.
결론적으로 말하자면, 검색엔진은 게임과 마찬가지로 종합예술이라고 보시면 될거 같습니다. 시스템 운용, 시스템 프로그래밍 능력, 데이터 분석, 분산시스템/처리, 언어에 대한 능력, 네트워크에 대한 이해, 이 모두에 대해서 일정수준이상의 능력이 필요합니다.
http://www.joinc.co.kr/modules/moniwiki/wiki.php/JCvs/Search/Document 에 개인적으로 정리한 문서가 있으니 참고하시면 도움이 되리라 생각되네요.
메신저 프로그램은
메신저 프로그램은 시스템 프로그래밍과 네트워크 프로그래밍의 응용입니다.
당연히... 시스템 프로그래밍과 네트워크 프로그래밍에 대한 지식이 있어야 합니다.
언어는 C,C++,자바,Python,Perl 뭘 선택 하셔도 상관이 없습니다.
시스템 프로그래밍과 네트워크 프로그래밍은 모든 프로그래밍의 기본이라고 할 수 있습니다.
결국... 기초부터 차근차근 해나가셔야 합니다.
이는 게임, 네트워크 관리, 시스템 관리, DB응용, 검색엔진개발, 분산처리 시스템개발, 보안관련 소프트웨어 인터넷 서비스.. 모두에 공통적으로 적용됩니다.
구글의 원리는..
처음 구글이 화려하게 대비했을때가 기억나네요.
정말 간단한 아이디어로 일반 유저들보다 저같은 컴퓨터 공학도들 사이에서 먼저 화제가 됬었죠.
그 당시에는 yahoo가 검색쪽은 싹쓸이하고 있었고 좀 더 확실한 검색을 요하면 metacrawler같은 여러 검색엔진들을 두루 검색해주는 싸이트들이 인기있었는데요, 다들 각 검색결과들의 relevance (검색하고자 하는 콘택스트와 근접함)에서 별로 대단한 기술을 보여주지 못하고 있었거든요.
컴퓨터학자들은 AI를 도입해서 싸이트의 내용을 natural language engine으로 이해해야한다는둥, 가장 방문자가 많은 싸이트를 우대한다는둥 여러가지 이론들이 난무하는 가운데, 구글이 혜성같이 등장했습니다.
링크를 따라가자!
이게 다였죠.
이미 yundreamm님이 설명하신대로 crawler를 사용하여 keyword들을 인덱싱 해놓고, 그 keyword를 이용하여 이 싸이트로 연결되있는 링크의 숫자를 셉니다.
즉 kldp.org에서 google에 대해서 설명하는 페이지가 있는데 그 페이지에 www.foo.com으로의 링크가 있다면 (www.foo.com/google)++ 이런식인거죠. (www.foo.com 에도 google이 언급되야되는지는 잘 모르겠습니다.)
이게 무지하게 단순하면서도 상당히 실용적인 방법이에요.
물론 이외에도 몇십가지의 로직을 사용하고 또 그때 (97년쯤이었죠 아마?) 이 후로 알고리즘이 계속 발전하고있긴했지만, 이 링크 아이디어는 적어도 제가 알기론 획기적이었습니다.
같은 내용은 아니지만 http://www.googleguide.com/google_works.html 여기에 현재 구글서치방법에 대해 약간의 설명이 있네요^^
검색엔진
검색엔진은 크게 웹에서 정보를 수집하고 URL 서버로 보내는 과정 , 즉 크롤링과
크롤러가 보내온 정보를 분석하고 분류하여 인덱스를 제작하는 과정 , 인덱싱 그리고
마지막으로 인덱스에서 정보를 추출해 사용자에게 보여주는 검색 단계로 나눈눌 수 있습니다.
우선 c 언어를 알고 계신다면 네트워크 소켓 프로그래밍을 조금 공부하셔서
크롤러를 만들면 우선 반은 하신 겁니다.
참고로 루씬, 너치 등에 대해서
알아보세요. 초보자라면 쉽게 검색엔진을 개발하실 수 있으실 겁니다.
검색에 대한 허접답변
작년에 대학원 수업으로 정보검색 시스템(Information Retrieval)이란 수업을 들은적이 있습니다.
실제로 웹검색 시스템에서는 이 IR기술이 쓰이는것 같더군요.
IR에 대해서 검색하시면 여러가지로 좋은 정보를 얻을수 있을것 같습니다.
간단히 소개하면,
IR은 어떻게 모델화 하느냐에 따라서 몇가지로 나눌수 있는데,
1. Boolean 모델
2. 벡터공간모델
3. 확률모델
이런식으로 나눌수 있습니다.
결국엔 쿼리가 있고, DB를 검색해서 가장 랭크가 높은것들( 가장 사용자를 원하는것 )을 탐색해서 사용자에게 보여줍니다.
이 랭크된 후보들을 어떤 방식으로 찾느냐에 따라서 모델을 나누는거지요.
벡터공간모델로 보자면, 문서를 단어의 빈도로 근사표현 합니다.( bag of word라고 부름 )
왜 빈도로 표현하나면, 데이터양을 줄이고 싶기 때문입니다.
데이터양이 줄어든다는 말은 메모리 코스트가 줄어든다는 이야기고, 이건 벡터간 매칭 연산의 코스트도 줄어든다는걸 의미하므로 매우 중요합니다.
실제로 IR에 대해서는 이 부분이 연구가 많이 진행되는것 같더군요.( 정확한건 아니지만 그냥 느낌이... )
그럼 매칭은 어떻게 이루어지느냐? 결론적으로 코사인계산을 이용하는데( 유클리드거리계산? ), 무작정 그냥 계산은 안합니다. 속도가 느려서...
bag of word로 표현되는 벡터들은 단어의 빈도로 표현되기 때문에 벡터의 요소값이 0이 많습니다.
예를들어 BMW를 소개하는 웹페이지에서 스타벅스란 단어가 나오기는 전무하겠지요.
이에 착안해서 DB인덱스를 전치해서 매칭을 하는걸로 알고있습니다. 물론 0인 요소는 기록 안합니다.
확률모델은, 말그대로 확률을 구함으로써 랭크된 문서를 찾는거지요. 우도추정입니다.
결과는 벡터공간모델과 같게 나오는걸로 알고있습니다.
그냥 생각나는데로 썼는데 쓰고보니 별로 도움은 안되겠네요..; 그리고 제가 알고있는게 정확한지도 모르겠고요..;
그냥 이런게 있다는것만 알아두세요.
댓글 달기