ENAVI 검색시스템!!!

검색엔진 개발하는게 일하면서 만들기가 쉽지 않네요...


대신 firewolf.egloos.com 블로그를 오픈했습니다. (링크참조)

MS 개발에 대한 공유 블로그입니다. 지금 열심히 업데이트 하고 있습니다.

^^

C#을 이용하여 TRIE 구조를 제작하기로 한다.

앞 포스트에서 형태소 분석시에 사전DB를 단순히 이분검색으로 제작할려고 했으나..

좀더 완성도 높은 시스템으로 구현하기위 TRIE 구조로 제작하도록 한다.

우선 TRIE 제작에 앞서 TRIE에 대해 설명하도록 한다.

TRIE를 왜 사용해야 하는가?
많은 양의 텍스트정보를 빠르고 효율적으로 검색하기위해!!!



TRIE란 무엇인가?
앞서 간단한게 구현해본 TREE구조와 유사하다. 다른점은 TRIE란 명칭도 TREE RETRIEVE 에서
나왔다고 한다.
가장 대표적인 특성은 키워드 정보는 마지막 노드만 가지고 있고 나머지 노드들은 정보는 없고
링크만가지게 된다.
그림을 보면 대략 이런형태이다.

-그림삽입-

-계속-

 

TREE.zip
지난 포스트(선형 연결리스트)에 이어
색인 파일 구축을 위해 TREE알고리즘을 C#을 이용하여 만들어봤습니다.

이소스는 트리검색의 효율을 높이기 위해 트리 균형을 잡아주는 부분은 빠져있습니다.
다음 포스트에 완벽하게 트리균형을 잡아가는 TREE를 만들고 파일에 기록하는 부분까지 하겠습니다.
그렇게 되면 색인파일 DB의 기본을 만들 수 있습니다.

1. 노드 추가
public void Add(int key,string content)
  {
   Node parentNode  , inputNode;
   parentNode = head;
   inputNode = head.Left;

   while (inputNode != null)
   {
    parentNode = inputNode;
    if (key < inputNode.Key)
     inputNode = inputNode.Left;
    else
     inputNode = inputNode.Right;
   }
   inputNode = new Node();
   inputNode.Key = key;
   inputNode.Content = content;
   inputNode.Left = null;
   inputNode.Right = null;
   if (key < parentNode.Key || parentNode == head)
    parentNode.Left = inputNode;
   else
    parentNode.Right =inputNode;

  }

2. 노드검색
public Node Search(int key)
  {
   Node searchNode;
   searchNode = head.Left;
   while (searchNode != null && key != searchNode.Key)
   {
    if (key < searchNode.Key)
     searchNode = searchNode.Left;
    else
     searchNode = searchNode.Right;
   }
   if (searchNode == null) return null;
   else return searchNode;
  }

3. 노드삭제
   노드 삭제는 개선이 가능함... 다음 포스트의 트리에서는 개선한 삭제 방법을 사용하겠습니다.
public void Del(int key)
  {
   Node parentNode  //삭제할 노드의 부모노드
    , sonNode   //삭제할 노드 대신 부모의 자손으로 갈 노드
    , delNode   //삭제 대상 노드
    , sonparentNode; //sonNode 의 부모노
   parentNode = head;
   delNode = head.Left;
   while (key != delNode.Key && delNode != null)
   {
    parentNode = delNode;
    if (key < delNode.Key)
     delNode = delNode.Left;
    else
     delNode = delNode.Right;
   }
   if (delNode == null) return; //못찾았다면 null 리턴

   //////유형1 자식노드가 모두 없을때
   if (delNode.Left == null && delNode.Right == null)
   {
    sonNode = null;
   }
    //////유형3 오른쪽 왼쪽 자식이 모두 있을때
   else if (delNode.Left != null && delNode.Right != null)
   {
    sonparentNode = delNode.Right;
    //// 유형 3-2 삭제노드의 오른쪽 자식의 왼쪽자식이 존재할때
    if (sonparentNode.Left != null)
    {
     while (sonparentNode.Left.Left != null)
      sonparentNode = sonparentNode.Left;
     sonNode = sonparentNode.Left; //가장왼쪽 노드
     sonparentNode.Left = sonNode.Right;
     sonNode.Left = delNode.Left;
     sonNode.Right = delNode.Right;
    }
     //// 유형 3-2 삭제노드의 오른쪽 자식의  오른쪽자식이 존재할때
    else
    {
     sonNode = sonparentNode;
     sonNode.Left = delNode.Left;
    }
   }
    ////유형2 오른쪽 왼쪽 자식이 하나만 있을때
   else
   {
    //// 유형 2-2 삭제노드의 왼쪽이 존재할때
    if (delNode.Left != null) sonNode = delNode.Left;
    ////유형 2-1 삭제노드의 오른쪽이 존재할때
    else sonNode = delNode.Right;
   }

   /*이제 새로운 자식을 삭제 노드의 부모노드에 연결*/
   if (key < parentNode.Key || parentNode == head)
    parentNode.Left = sonNode;
   else
    parentNode.Right = sonNode;
  }

* C로 배우는 알고리즘 참고 했음

 

* 첨부소스에 관해서

visual studio .net 2003으로 제작

첨부소스의 저작권은 sun77.egloos.com에 있으며
Copyright 만 붙혀주시면 어디서든 자유롭게 이용할수있습니다. ^^

LinkedList.zip
스택기반 단순 연결리스트를 C#을 이용하여 만들어 보았다.
연결리스트란 쉽게 말해서 정적인 배열이 아닌 동적인 배열이라 할수있다.
C#에서의 Array라고 생각하면 되겠다.
연결리스트는 노드와 링크로 이루어져있으며 시작노드로 시작해서 끝노드로 종료된다.

예) head(시작)->노드->노드->노드->tail(끝) *끝의 링크는 끝을 가르킨다


1. 노드자료형은 노드클래스로 만든다.
심플하게 만들기위해 데이터와 링크(next)로 구성했다. next는 Node클래스를 가르킨다.
class Node
 {
  public int nKey;
  public Node next;
 }

2. 연결리스트 초기화
노드의 시작과 끝을 전역변수로 선언
노드의 시작점과 끝점을 초기화시켜준다

Node _head;
Node _tail;
public void Init_Link()
  {
   _head = new Node();
   _tail = new Node();
   _head.next = _tail;
   _tail.next = _tail;   *링크끝의 링크는 끝을 가르킨다
  }

3.노드 삽입
임시 노드를 생성하고 임시노드의 링크를 시작링크 다음에 연결된 링크로 바꾼후
시작노드의 다음노드에 임시노드를 넣는다(스택기반 연결리스트이기때문)
이렇게 되면 아래부터 Node클래스의 메모리가 차곡차곡 쌓이게 된다
public int InsertNode(int nKey)
  {
   Node tempNode;
   if ((tempNode = new Node()) == null)
   {
    Console.WriteLine("경고 : 메모리 부족");
    return -1;
   }
   try
   {
    tempNode.nKey = nKey;
    tempNode.next = _head.next;
    _head.next = tempNode;
    return nKey;
   }
   catch (Exception ex)
   {
    Console.WriteLine(ex.Message);
    return -1;
   }
  }

4.노드삭제
임시 노드를 생성하고 헤드다음노드를 임시노드에 넣구 헤드 다음노드를 임시노드 다음으로 연결하면
헤드 다음의 노드는 떨어져 나가서 닷넷 가비지컬렉터에 의해서 정리될것이다.
public int DeleteNode()
  {
   Node tempNode;
   int i;
   if (_head.next==_tail)
   {
    Console.WriteLine("경고 : 삭제할 메모리가 없습니다.");
    return -1;
   }

   try
   {
    tempNode = _head.next;
    i = tempNode.nKey;
    _head.next = tempNode.next;

    return i;
   }
   catch(Exception ex)
   {
    Console.WriteLine(ex.Message);
    return -1;
   }

  }

5. 출력
시작노드를 출발점으로 루프를 돌면 끝노드에 도달할때까지 화면에 뿌려준다

public void PrintNode()
  {
   Node tempNode;
   tempNode = _head.next;
   while (tempNode != _tail)
   {
    Console.WriteLine("{0}",tempNode.nKey);
    tempNode = tempNode.next;
   }
  }

이상으로 단순한 스택기반의 연결리스트를 구현해보았다.
다음 강좌에서 단순 스택기반연결리스트를 가지고 좀 복잡한 형태의 중간삽입, 검색 ,이중연결 디스크 출력등
을 만들어보기로 한다.




* C로 배우는 알고리즘 참고 했음

 

* 첨부소스에 관해서

visual studio .net 2003으로 제작

첨부소스의 저작권은 sun77.egloos.com에 있으며
Copyright 만 붙혀주시면 어디서든 자유롭게 이용할수있습니다. ^^




 

검섹엔진의 섹인DB는 크기는 고정되어있지 않다.

대용량 검색시스템이라면 기가바이트까지 색인DB가 커질수있다고 한다.

단순.. 파일순차검색이나 단순 선형이진검색으로는 최상의 성능을 기대하기는

불가능할것이다.

그래서 대중적이고 검증된 알고리즘(자료구조)

B-TREE(balanced search tree),해쉬(Hash) , 트라이(Trie)  등을 염두할수있다.

이블로그에서는 B-TREE로 개발 하도록 한다.

또하나 생각해야할것은 기가바이트까지 커져버린 색인DB파일의 데이터들을 메모리로 올리는건 불가능하다

외부검색(검색의 장소가 메모리가 아니라 외부기억장치)이 필요하다.

C로 구현된 검색알고리즘은 많이 접할수있지만 C#코드로 작성된 검색알고리즘 코드는 구하기 힘들것이다.

C#의 비관리코드로 포인터를 구현하는 대신 클래스를 이용하여 자료구조를 만들도록 한다.

다음 블로그글에서 이해를 돕기위해 C#으로 자료구조의 기본인

선형연결리스트를 먼저 구현해보도록 하기로한다.
 

색인어 추출기를 통해서 추출된 색인어를
물리적인 파일에 저장하게 되는데 빠른 색인을 위하여 특별한 구조를 가져야 한다.
색인어 기준의 역파일 구조이다.

현재 전세계에 뿌려진 하드웨어 , 메모리 , 트렌지스터등의 뿌려진 양은 엄청나다.

이들 기기 안에 들어있는 데이터들은 말할필요도 없이 광범위하고 깊다.

심지어는 냉장고나 전기밥솥에도 데이터들이 들어있다.

더욱 놀라운건 이들정보들이 통신매개체를 통해서 무한 정보의 바다에서 필요한 정보를 추출할수있다는 것이다.

기술혁명 이전에는 정보를 찾기위해 발로 뛰어야했다.

지금은 구글사이트를 열고 검색만 하면 원하는 정보를 얻을수있다.

지금은 정보의시대 , 지식의시대이다. 엄청난 정보의 바다에서 누가더 검증된 정보,필요한정보 등을

추출해서 이용할수있는지가 경쟁력이고 돈이 되는 시대이다.

그래서 나는 지금 시대가 가장 필요로하는 정확하고 빠르게 원하는 데이터를 추출하는 검색시스템을 만들려고 한다.

예전 산업혁명 때에도 생산된 생산품보다 공장의 기계들이 더큰의미가 있다고 생각한다.


 

usecase.ppt

구글 검색을 통해 몇개의 사전파일을 구했는데

전부 완벽하지 못하더군요...

그래서 사전파일을 직접 제작을 하였습니다.

실질단어갯수는 150012 개

조사는 512개

어미는 823개

나왔습니다.

색인기 추출기가 완성되면 사전파일들을 공개하도록 하겠습니다.
 

명사 색인어 추출 시스템을 만드는 과정에서

또하나의 난코스가 있다

불규칙용언이다.

불규칙 용언은
"활용활 때에 어간이나 어미의 기본 형태가 달라지는 불규칙 활용을 하는 용언"
이렇게 정의되었다.

* 예로는 두산세계대백과엔싸이버라는 사이트에 설명이 잘되었다


활용할 때 어간은 변하지 않는 것이며, 어간과 어미는 모음조화의 규칙에 따라 어간의 끝이 양성모음이면 ' -아, -오' 계의 어미가 쓰이고, 음성모음이면 '-어, -우' 계의 어미가 쓰이는 것이 규칙활용이다. 이와 같은 기본형태에서 달라지는 것을 불규칙활용이라 하며, 이러한 용언을 불규칙용언이라 한다.
 1) 불규칙용언 중에서 어간이 바뀌는 것
    ㄷ불규칙용언: 그 문제는 선생님께 물어 보자 (묻다)
    ㅂ불규칙용언: 외로운 이웃을 도와 주자 (돕다)
    ㅅ불규칙용언: 우리 마을에는 새로 지은 집이 많다 (짓다)
    르불규칙용언: 강물이 흘러 바다로 간다 (흐르다)
 2) 불규칙용언 중에서 어미가 바뀌는 것
    여불규칙 용언: 꾸준히 노력하여 왔다 (노력하 - 어)
    러불규칙용언: 20세기에 이르러 영화가 발달했다(이르 -어)
    거라불규칙용언: 너 혼자 가거라 (가 - 아라)
    너라불규칙용언: 곧장 집으로 오너라 (오 - 아라)
 3) 불규칙용언 중에서 어간과 어미가 모두 바뀌는 것
   ㅎ불규칙용언: 가을 하늘은 쪽빛같이 파래 (파랗 - 애)
불규칙용언은 불규칙동사와 불규칙형용사를 아울러 일컫는 말이다.


앞서 후절어 분석을 통해 명사를 추출하는 방법을 소개하였다.
그과정에서 실패한 어절들에 대해서 이러한 정보를 가지고 최종 음운현상복원(불규칙용언에 의한)을 통해서
완성도 높은 결과값을 출력해야 할것이다.

본인도 공부하면서 만들고있기때문에
자료를 많이보고 상세 구현 방법에 대해 설명하겠다