이 모델은 집합이론에 근거한 불리언 로직을 이용해서 질의어와 문서를 색인어의 집합으로 표현하는 모델이다.

불리언 모델은 사용자 쿼리로부터 주어진 Term을 포함한 문서를 찾는다고 하면,
해당 문서가 Term을 포함하고 있는지(true), 아닌지(false)에 대한 정보만을 가지고 문서를 찾아낸다.
매우 단순하고 효율적이며 빠른 구현이 가능하나, 사용자의 의도를 정확하게 파악하지 못하는 단점도 있다.

자세한 내용은 파일 다운 받아 보시길...

1. Definition
2. Query
3. Extension of Query
4. Limitations

블로그 이미지

쩐의시대

나답게 살아가고 나답게 살아가자

,

정보검색 개요를 작성한지 한참 만에 벡터 스페이스 모델에 대해서 정리를 했습니다.

벡터 스페이스 모델은 불리언 모델, 확률 모델과 더불어 검색 모델에 있어서 아주 중요한 부분입니다.

Term vector model이라고도 불리우며 정보 필터링, 정보검색, 색인과 유사도를 계산하기 위한 대수 모델입니다.
이 모델은 SMART Information Retrieval System에서 가장 먼저 언급이 되었으며,
무료 검색엔진인 루씬에서 이 모델을 기본적으로 사용하고 있습니다.


벡터공간 모델 상에서 각 도큐먼트들과 질문자들은 n차원 공간 속의 벡터들로 취급되며,
이때 각 차원들은 색인용어들로 표현된다.
이 기법에 의한 검색 절차는 다음과 같다.
1) 용어의 가중치는 정규화된 도큐먼트내의 빈도(TF)와 이의 역빈도수(IDF)를 조합하여 게산
2) "낮은 식별치(poor discrimination value)의 값을 지닌 용어들은 시소러스내의 저 빈도용어들로 대치되며
   구의 경우 고빈도 용어들로 대체된다.
3) 각 도큐먼트들은 이용자 질문에 대해서 그 유사성의 순위별로 출력되며, 이러한 과정은 코사인 상관도에
   의해 계산된다. (벡터 공간 내에서 이용자의 질의에 가장 근접해 있는 도큐먼트들을 직관적으로 검색해낸다.)


자세한 내용은 다운받아 보시길...

1. Definition
2. Applications
3. Examples
4. Limitations
5. Reference
6. Models based on and extending the vector space model

블로그 이미지

쩐의시대

나답게 살아가고 나답게 살아가자

,

검색엔진의 주로 벡터 스페이스 모델에 사용되는 용어입니다.

1. TF (Term Frequency) : 하나의 문서 안에서의 Term의 출현 횟수
2. CF (Collection Frequency) : 하나의 콜렉션 안에서의 Term의 총 출현 횟수
3. DF (Document Frequency) : 하나의 콜렉션 안에서 Term이 출현한 문서의 개수
4. IDF (Inverse Document Frequency) : DF의 역수
5. TF * IDF : TF가 크고, DF가 작을수록 가중치는 커진다,
                  이것은 전체 문서에서 공통적으로 등장하는 단어들은 걸러지게 된다.
                 특정 문서에서 어떤 단어의 중요도를 평가하기 위해 사용되는 통계적인 수치.

예) 만약, 100개의 단어로 이루어진 어떤 문서에 단어 search가 3번 등장한다면,
     단어 search의 TF는 0.03 (= 3 / 100)이고,
     또한, 전체 10,000,000개의 문서 중에서 단어 search가 들어 있는 문서들의 숫자가 1,000개라면,
     DF는 0.0001 (= 1,000/10,000,000)이며 최종 TF*IDF 가중치는 300 ( = 0.03 * 1/0.0001)이 된다.

     이러한 것이 가장 기본적인 것이며, DF에 로그를 취하는 방법도 있으며, 여러가지 방법이 있을 것이다.
     만약 자연로그를 취한다면 IDF는 9.21 ( log(10,000,000/1,000))가 되고,
     TF*IDF 가중치는 0.27 (= 0.03 * 9.21)이 된다.

블로그 이미지

쩐의시대

나답게 살아가고 나답게 살아가자

,
1. mmap이란?
   메모리의 내용을 파일이나 디바이스에 대응하기 위해서 사용하는 시스템 호출이다.

2. 메모리 관리
   프로세스 메모리는 기본적으로 다른 프로세스 메모리와 공유되지 않는다. 이것은 프로세스의 데이터를
   보호하기 위해서 반드시 필요한 기능이긴 하지만 다른 프로세스와 특정 데이터를 공유하기 위해서는
   귀찮은 기능이 되기도 한다.
   이 때문에 IPC를 사용하게 된다.
   mmap은 메모리의 특정영역을 파일로 대응시킬 수 있도록 도아준다.
   파일은 시스템 전역적인 개체이므로 다른 프로세스에서 접근가능하도록 할 수 있으면,
   이러한 mmap의 특징 때문에 IPC용도로 사용가능하다.
   (mmap이 IPC용도로 사용가능하지만 IPC 설비는 아니다.)

   ==> mmap은 프로세스의 주소공간을 파일에 대응시킨다.
        파일은 운영체제 전역적인 자원이므로 당연히 어렵잖게 다른 프로세스와 공유해서 사용할 수 있을 것이다.

3. 활용용도
   1. 메모리의 내용을 파일에 대응시킬 수 있다면 프로세스간 데이터의 교환을 위한 용도로 사용가능 할 것이다.
      접근 제어를 통해 프로세스간 공유하고자 하는 데이터를 파일에 대응시키고 이것을 읽고 쓰면 된다.
   2. 성능향상.
      고전적인 방법은 파일지정자를 얻어서 직접 입출력하는 방식으로 open, read, write, lseek와 같은 함수를
      이용하나, 상당한 비용을 지불.

4. 사용방법
   void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);
   int munmap(void *start, size_t length);

   1. start
      메모리 영역에 파일을 대응시킬 시작 offset
   2. length
      start부터 length만큼 대응
   3. prot
      a. PROT_EXEC  : 페이지에 실행될 수 있다.
      b. PROT_READ  : 페이지는 읽혀질 수 있다.
      c. PROT_WIRTE : 페이지는 쓸 수 있다.
      d. PROT_NONE : 페이지를 접근할 수 없다.
   4. flags
     a. MAP_FIXED
     b. MAP_SHARED
        대응되는 객체를 다른 프로세스도 공유할 수 있게 만들어준다.
        프로세스들은 객체에 대해서 동등한 권한을 가지게 되고 이로 인해 동기화가 필요하며, 이를 위해
        msync(), munmap()가 사용
     c. MAP_PRIVATE
        --> MAP_SHARED와 MAP_PRIVATE 둘 중 하나는 반드시 사용해야 한다.
   5. fd
      file descriptor
   6. offset
      대응할 때 파일의 위치를 지정..
      파일의 처음이라면 0
    
5. 성능 비교
   http://developers.sun.com/solaris/articles/read_mmap.html
블로그 이미지

쩐의시대

나답게 살아가고 나답게 살아가자

,

1. 개념
   이 수열은 기본적으로 자연의 황금비율을 설명할 때 가장 많이
   쓰이는 수열입니다.
   수열이 커지면 커질수록 황금비율(1.618)에 근접하게 됩니다.

   한 쌍의 토끼가 매월 한 쌍의 토끼를 낳고, 태어난 한 쌍의 토끼가
   다음 달부터 한 쌍의 토끼를 매월 낳기 시작한다면, 처음 한 쌍의
   토끼로부터 1년간 합계 몇 쌍의 토끼가 태어날 것인가?

2. 특징
   "해당 수와 전의 수를 더한 수를 다음 수로 나타낸 것"
   ex) 데이지 꽃, 코스모스/나뭇가지의 성장

3. 복잡도
   a. 루프를 이용한 구현 : O(n)
   b. 재귀를 이용한 구현 : O(n^2)

4. 구현
   a. 루프를 이용한 구현
      int forfibo(int n)
      {
           int i, tmpe = 0;
           int firstnumber = 0;
           int secondnumber = 1;

           if( n <= 1)
               return n;
          else {
               for( i = 2; i <= n; i++) {
                    temp = firstnumber + secondnumber;
                    firstnumber = secondenumber;
                    secondnumber = temp;
              }
              return secondnumber;
         }
    
}

    b. 재귀를 이용한 구현
       int refibo(int n)
      {
          
if( n <= 1)
               return ;
           else
               return  refibo(n - 1) + refibo(n - 2);
     
}

'IT > 알고리즘' 카테고리의 다른 글

스트링에 대한 permutation을 구하는 알고리즘  (0) 2008.07.15
mmap (메모리맵)  (0) 2008.07.08
문자열을 뒤집는 프로그램  (0) 2008.07.08
call by value vs. call by reference  (0) 2008.07.08
C 프로그램에서 데이터형  (0) 2008.07.08
블로그 이미지

쩐의시대

나답게 살아가고 나답게 살아가자

,
문자열을 뒤집는 프로그램의 알고리즘은 많다.
그 중 대표적인 것을 살펴보자~~

1. 메모리를 사용한 변환
   int rev()
   {
       char string[20] = "this is test";
       char reverse[20];
       int i, j = 0;

       for( i = strlen(string); i >= 0; i--)
          reverse[j++] = string[i];

      reverse[j] = '\0'; // 이 부분을 잘 빠뜨리는데 주의할 것!!

   }

2. 별도의 메모리를 사용하지 않고 변환
   int rev()
   {
       char s[20] = "this is test";
       char temp;
       int len = strlen(s);
       int i;

       for( i = 0; i < len/2 ; i++) {
          temp = s[i];
          s[i] = s[len - 1 - i];
          s[len - 1 - i] = temp;
       }

   }

   문자가 2byte를 기본으로 하는 한국어일 경우는 힘들겠죠??

3. 재귀함수 이용
   char *s = "this is test";

   void rec(void)
  {
      if( *p == NULL) // 종결조건
         return;

      p++; // 전진방법
      rec();
      p--; // 수행방법
      putchar(*p);

      return;
   }

   * recursive(재귀함수) 코딩하는 방법에서 꼭 갖추어야 할 요건
     1. 전진방법
     2. 종결조건
     3. 수행방법

4. 스택 이용
    void rev(char string[])
    {
       int i;
       int top = 0;

       for( i = 0; s[i] != '\0'; i++)
          PUSH(&top, s[i]);

       for( i = 0; s[i] != '\0'; i++)
          s[i] = POP(&top);

    }

'IT > 알고리즘' 카테고리의 다른 글

mmap (메모리맵)  (0) 2008.07.08
피보나치 수열  (2) 2008.07.08
call by value vs. call by reference  (0) 2008.07.08
C 프로그램에서 데이터형  (0) 2008.07.08
프로세스의 메모리 구조  (4) 2008.07.08
블로그 이미지

쩐의시대

나답게 살아가고 나답게 살아가자

,
1. call by value
   쉽게 말해서 값에 의한 전달입니다.
   흔히 함수의 반환 값이나 함수 전달 인자로 값을 넘겨 줍니다.
   단순히 값만 복사되어서 해당 함수로 넘어갑니다.
   작은 값이라면 상관없지만, 큰 정보를 넘길 경우 오버헤드가 발생할 수 있습니다.

   ex)  swap_value(int a, int b)
         {
               int temp = a;
               a = b;
               b = temp;
         }

         호출자에게는 전혀 영향을 미치지 않고 호출 당한 함수 내에서만 유효.

2. call by pointer(address)
   포인터에 의한 전달, 주소에 의한 전달입니다.
   즉, 해당 함수나 변수의 주소를 이용해서 전달하는 방식입니다.
   값을 복사하지 않기 때문에 오버헤드는 적지만, 포인터를 사용하기가 좀 까다롭다는 단점이 ㅇㅆ습니다.

   ex) swap_address(int *a, int *b)
        {
             int *temp = &a;
             a = &b;
             b = &temp;
         }


3. call by reference
   레퍼런스에 의한 전달. 참조에 의한 전달이라고 합니다.
   즉 참조를 사용하기 때문에 포인터 방식보다 간편하고 쉽습니다.
   단, 값전달 방식과 구분이 모호하다는 단점이 있습니다.

   ex) swap_ref(int &a, int &b)
        {
            int temp = a;
            a = b;
            b = temp;
         }


좀 정리를 하자면,
인자로 념겨받은 뒤 그 함수 내에서 끝나고 값을 넘겨준 함수에서의 값에 영향을 미치지 못한다면
그것은 call by value이며 그렇지 않은 경우는 call by reference입니다.

'IT > 알고리즘' 카테고리의 다른 글

피보나치 수열  (2) 2008.07.08
문자열을 뒤집는 프로그램  (0) 2008.07.08
C 프로그램에서 데이터형  (0) 2008.07.08
프로세스의 메모리 구조  (4) 2008.07.08
기억류 auto, register, static, extern에 대한 설명.  (0) 2008.07.08
블로그 이미지

쩐의시대

나답게 살아가고 나답게 살아가자

,
data형을 낮은 형에서 높은 형으로 나열하면 char < int < long < float < double이 된다.

이 경우의 Rule을 정리하면,

1. 부동 소수점 연산은 모두 double형이 된다.
2. float형 + double형에서 float형이 double형으로 격상이 되어 계산된다.
3. char나 short은 모두 int로 변환된다.
4. 어느 한 쪽의 피 연산수가 double이면 다른 한 쪽도 double로 변환되어 결과도 double이다.
5. 최고 rank의 operand가 long이면 다른 한 쪽도 long으로 변환되어 결과는 long이 된다.
6. 부호 없는 정수와 단순한 정수의 경우는 정수가 부호 없는 정수로 변환되어 결과는 부호 없음(unsigned)이 된다.


그렇다면, 다음과 같은 문제에 대한 답은??

"32비트 인티저와 64비트 인티저 변수에 각각 값을 할당하고 연산 후에 각각의 사이즈가 어떻게 될까?"

둘 다 64비트가 되겠죠...
큰 데이터형에 사이즈도 격상이 되어 연산 처리가 될 터이니..
블로그 이미지

쩐의시대

나답게 살아가고 나답게 살아가자

,
프로그램을 작성해 컴파일하고 링크하면 실행 가능한 파일이 생성된다.
쉘을 통해 사용자가 프로그램을 수행시키면, 커널은 이 프로그램을
제어에 적합한 자료구조로 만들어 메모리로 읽어낸 후, 커널의
프로세스 테이블에 등록하고, 메모리, 파일, 입출력 장치 같은
자원을 할당하는데, 이때부터 프로그램은 커널의 한
프로세스로서 실행 상태가 된다.

아래 그림에서 위쪽이 낮은 주소 번지가 된다.
그림에서 보이는 네 개의 범위(텍스트, 데이터, 힙, 스택)을 각각
세크먼트라고 한다.

운영체제는 프로그램의 텍스트 부분에 메모리를 읽기 전용으로만
사용하고, 프로세스간에는 메모리 영역을 침범하지 못하도록 한다.
따라서, 프로그램의 텍스트로 되어 있는 메모리 영역을 침범해 기록하면
버스 에러나 세그먼트 결함이 일어나서 프로그램이 종료된다.

사용자 삽입 이미지

1. 텍스트
   - 프로그램의 실행 코드인 기계어 코드와 읽기 전용 데이터 등을 가진다.
     (CPU가 읽어들여 수행한다고 해서 텍스트라고 부르며, 코드 영역이라고 한다.)
   - 프로그래머가 작성한 소스를 컴파일 후 링크 과정을 거쳐서 만들어진 프로그램의 기계어 코드.
   - 디버깅과 같은 제한된 환경에서 크기의 변경이 가능

2. 데이터
   - C 언어에서 전역변수, 정적변수, 초기화된 배열과 구조 등으로 선언된 변수 영역 (읽기 / 쓰기 가능)
   - 프로그램이 실행될 때 생성되고 프로그램이 종료될 때 시스템에 반환
   - malloc 계열의 시스템콜을 이용해서 확장하는 것이 가능

3. 힙
   - 프로그램 수행 중 malloc(), free() 등의 시스템 콜로 할당되고, 해지되는 메모리 영역

4. 스택
   - C 언어의 함수 호출 시 지역 변수와 인수, 함수의 수행이 끝났을 때 리턴할 주소(return address)를 푸시한다.
     (함수가 끝나면 이 값을 팝하고 리턴하게 된다.)
   - 자동 변수 (auto variable) 저장
   - 함수로 인수를 보내기
      ( 함수로 인수를 보낼 때는 인수를 역순으로 보낸 뒤 복귀 번지를 저장.)
   - 복귀 번지(return address) 저장의 용도로 사용
   - 스택 프레임 단위로 적재
     ( 함수 역시 호출 시에 스택 영역에 생성되고 사용된 후 시스템에 사용영역이 반환)
   - 프로세스의 실행과 함께 커널에 의해서 스택 세그먼트가 자동으로 확장

※ - 텍스트(코드), 데이터, 힙 영역은 하위 메모리로부터 할당되며, 스택 영역은 상위 메모리로부터 할당
    - 데이터와 스택 세그먼트는 읽기, 쓰기가 모두 가능한 영역
       - 단, 차이점은 데이터 세그먼트는 초기화된 데이터와 그렇지 않은 데이터가 함께 존재
         스택 세그먼트는 실행시간에 초기화된 값들을 보관
  

참고로, 자바의 메모리 모델은 메소드 영역과 스택, 힙으로 나뉜다.
데이터 영역과 텍스트(코드) 영역이 메소드 영역 하나로 관리가 된다.

사용자 삽입 이미지


블로그 이미지

쩐의시대

나답게 살아가고 나답게 살아가자

,
C 프로그램에서 변수 선언시 일반적으로 그 변수의 타입을 작성하는 거 외에 그 변수 타입 앞에 작성해 주는 키워드이다.

1. auto 기억류
   a. 함수 안이나 블럭 안에서 선언할 수 있으며 해당 함수나 블럭을 벗어나게 되면 해당 변수가 소멸된다.
   b. 실행시에 기억 장소가 준비된다.
   c. 변수를 선언하면 쓰레기 값을 기억하게 된다.
   d. 대부분의 지역변수들이 여기에 속한다.

2. register 기억류
   a. 기억장소가 CPU 내의 register에 확보되는 것만 다르고 대부분의 사항이 auto 기억류와 동일하다.
   b. 많은 수의 변수를 register로 선언할 수 없다. (register 개수의 한계 때문)
   c. &(주소연산자) 연산자를 사용할 수 없다.
   d. 작고 빠른 프로그램 제작시 종종 사용한다.

3. static 기억류
   a. 컴파일시에 기억 장소가 확보된다.
   b. 전역 또는 지역 변수로도 사용이 가능하다.
   c. 함수 밖에서 선언하면 선언 이후 언제나 사용 가능한 전역 변수가 된다.
   d. 함수나 블럭 내에서 선언하면 선언된 함수나 블럭 내에서만 사용 가능하다.
      하지만 함수나 블럭을 벗어나더라도 auto, register와는 달리 기억장소는 소멸되지 않는다.

4. extern 기억류
   a. 프로그램간에 변수를 공유할 목적으로 선언한다.
   b. 프로그램을 묶어 프로젝트로 만들어야 의미가 있다.
   c. 단일 프로그램에서만 사용하면 static 기억류와 별로 다를 게 없다.
   d. 선언시 초기화를 해야 하며 단일 프로그램에서 사용시에는 함수 밖에서만 선언이 가능하다.


※ 1. register는 CPU 구조를 보면 register라는게 있는데, 아주 작은 저장장치지만 속도는 엄청 빠르다.
    2. static은 메모리의 static 이라는 영역에 선언 ( 한 번 할당되어 프로그램이 종료될 때까지 존재하는 변수)

※ 메모리의 구조를 좀 더 알아보는 것이 도움이 ...
블로그 이미지

쩐의시대

나답게 살아가고 나답게 살아가자

,