자료구조 & 알고리즘2010. 3. 27. 19:47
  • minimal perfect hash function(MPHF, 최소 완전 해쉬 함수)

    • m개의 키를 m개의 버킷에 충돌없이 해싱하는 완전 해쉬함수

      • 즉, 키와 버킷이 일대일 대응이며, 100% 적재율을 가진 해쉬 함수
    • perfect hash function(완전 해쉬 함수)

      • 모든 키들이 구별되는 다른 위치(버킷)로 대응되는 함수
      • 해쉬함수 정의 전에 키의 집합을 알고 있어야 함.
      • 키값 자체를 버킷번호로 사용하면, 완전해싱 함수는 구현이 가능하다. 단, 저장공간이 매우 커서 매우 비효율적이다.
      • 완전 해쉬 함수를 만들 수 있다면, 폐쇄 주소법보다 개방 주소법이 더 좋다.

 

  • MOS(Mapping, Ordering, Searching)방식의 완전 해쉬 함수

    • Cichelli, Cerone 이 제안
    • 완전 해쉬함수 생성 방법

      1. mapping: 키를 새로운 유니버스(모집단)로 변환

        • 모집단: 통계적인 관찰의 대상이 되는 집단 전체
      2. ordering: 키를 순서화(정렬)
      3. searching: 각 단계의 키에 해쉬값을 할당, 수용불가능한 단계가 발생하면, 이전 단계로 역추적(backtracking)하여 새로운 해쉬값 찾음.

 

  • Cichelli가 제안한 완전 해쉬 함수 (키가 문자열일 때)
    • h(s) = ( s.length() + g( first(s) ) + g( last(s) ) ) % m

      • s.length() = 문자열의 길이
      • first(s) = s.charAt(0) = 문자열의 첫 문자
      • last(s) = s.charAt(s.length()-1) = 문자열의 끝 문자
    • 완전 해쉬함수 생성 방법

      1. 키 집합의 모든 키에 대하여 첫 문자와 끝 문자를 뽑아 중복없이 나열하고, 각 문자에 대한 빈도수를 계산하여 문자 빈도수 테이블을 만든다.

      2. 각 키에 대하여 첫 문자와, 마지막 문자에 대한 빈도수의 합을 계산한다.

      3. 키 빈도수합 테이블을 빈도수합 내림차순으로 정렬한다.

      4. 정렬된 키 빈도수합 테이블에서 해쉬값 집합의 원소가 중복되지 않도록, g(문자) 함수를 정의한다. 중복될 경우에는 백트래킹(backtracking)을 이용하여, g(문자) 함수를 재정의 한다. 해쉬값은 아래 공식을 이용하여 구한다.

        • h(s) = ( s.length() + g( first(s) ) + g( last(s) ) ) % m
      5. 4를 반복하여 해쉬테이블과 g()함수를 완성한다.

    • 완전 해쉬함수 생성 방법의 예

 

  • Sager가 제안한 완전 해쉬 함수 알고리즘 (키가 문자열일 때)

    • Sager가 Cichelli의 방법을 정형화

    • 완전 해쉬함수 생성 방법

      • 3개의 보조함수
      •  

        • r<= m/2
        • g()는 탐색중에 선택됨
Posted by 바게 BAGE

댓글을 달아 주세요

  1. 마징카

    글 잘 보고 갑니다^^
    혹시 g(문자) 함수를 계산하는 과정을 좀더 자세히 알 수 있을까요? 예제를 봐도 잘 이해가 안가서요~

    2011.09.06 13:04 [ ADDR : EDIT/ DEL : REPLY ]
    • 페이지에 포함된 "[박혜웅] 완전해싱 예제.pdf" 파일을 다운로드 받으시고, 직접 계산해 보시면 이해되실 것 같습니다. 온라인으로 더 자세히 설명해 드리기는 어렵네요.

      2011.09.11 02:03 신고 [ ADDR : EDIT/ DEL ]
  2. 해보리

    흠... 제가 잘못 이해한건진 모르겠지만;;;
    결국 IN 이라는 문자열로 탐색을 시키고자 할 때 IN이란 문자로 해당 위치를 찾는데 6번의 비교가 들어가는 구조가 되는것 아닌가요? 즉, 해당 버킷에서 충돌 키들의 리스트 돌며 찾는 거랑 버킷 자체를 여러개 두고 찾는 거나.. ;;;; 같은거 아닌가 하는 생각이 들어서요 ^^;;;
    최악의 경우를 생각해 보면... 흠
    이 방법의 이점이 뭔지 궁금하네요 ^^;

    2012.04.24 16:27 [ ADDR : EDIT/ DEL : REPLY ]
    • 일반적인 해시는 버킷이 있지만, 완전 해시는 그 버킷의 크기를 1로 하려는 거에요. 그래야, 본래의 목적처럼 해시의 O(n)=1로 할 수 있는거죠. 그래서 일반적으로 충돌을 고려하고 버킷을 잡는게 아니라, 키 집합을 알고 있을 경우에, 버킷의 크기가 1이 되도록 하여, 한번에 찾으려고 하는 거에요.
      한마디로 O(n)=1이 되기 위하여, 미리 자료 구조를 만들기 위한 과정이 최소 완전 해시 함수를 만드는 과정입니다.

      2012.06.01 03:03 신고 [ ADDR : EDIT/ DEL ]