탐색 알고리즘 - 1

탐색의 효율

• 삽입, 삭제에 우선하여 탐색의 효율을 높이기 위한 알고리즘

키, 레코드, 탐색

레코드, 키

• 개인별 폴더를 하나의 레코드로 간주
• 해당 폴더를 찾기 위한 이름은 일종의 키 필드
• 레코드의 집합에서 주어진 키를 지닌 레코드를 찾는 작업을 탐색
• 주어진 키 값을 목표 키(Target Key), 또는 탐색 키(Search Key)

외부 탐색, 내부 탐색

• 모든 레코드가 메인 메모리 내부에 들어와 있는 상태에서 이루어지는 탐색
• 레코드가 보조 기억장치, 메인 메모리를 오가며 이루어지는 탐색

이진 탐색

void BinarySearch(int A[ ], int First,  int Last,  int Key,  int& Index)

{ if (First > Last)                      탐색 키를 가진 레코드가 없을 때 

         index = -1;                      에일리어스 변수 Index를 -1로 표시 

  else

  {     int Mid = (First+Last)/2;        가운데 인덱스 계산 

         if (Key = = A[Mid])              탐색 키가 가운데 키와 같으면 

            Index = Mid;                 에일리어스 변수 Index를 해당 인덱스로 

         else if (Key < A[Mid])          탐색 키가 가운데 키보다 작으면 

            BinarySearch(int A[], First, Mid-1, Value, Index);  왼쪽에서 찾음 

         else                              탐색 키가 가운데 키보다 크면 

            BinarySearch(int A[], Mid+1, Last, Value, Index);   오른쪽에서 찾음 

   }

}

 

이진탐색의 효율

트리모습에 좌우

• 비교적 균형 잡힌 트리의 높이는 lgN, 검색효율은 O(lgN)이다.
• 최악의 경우 연결 리스트에 가까운 트리라면 검색효율은 O(N)
• 확률적으로 분석한 이진 탐색트리의 평균 효율은 O(1.38 lgN)

평균 효율

• 트리의 내부경로 길이에 의해 근사적으로 표시
• 키 3인 노드의 내부경로 길이는 3. 이를 대략적인 비교의 횟수로 간주
• (Level 0:0)+(Level 1:1)+(Level 2:2)+(Level 3:3) = 9.
• 평균적인 비교 횟수는 대략 9/6 = 1.5회가 된다.

내부 경로

 

게으른 삭제

이진 탐색트리 삭제

• 중위 후속자 또는 선행자를 삭제된 노드로 옮김으로 인해 트리 모습이 변함.
• 삭제가 빈번할수록 트리의 균형이 무너질 확률이 높아짐

게으른 삭제(Lazy Deletion)

• 실제로 삭제하지 말고 해당 노드에 "삭제됨" 표시만 함.
• 나중에 몰아서 한꺼번에(Batchwise) 삭제
• 삭제 전까지는 이전의 트리 모습, 이전의 효율을 계속 유지

간접 이진트리

레코드는 배열에, 트리는 키 또는 인덱스 정보만 함유

삽입, 삭제시간이 감소

Index	1	2	3	...
Key	25	16	12
Data	Kim	Cho	Park

간접 이진트리

 

기수 탐색 - 디지털 탐색트리

디지털 탐색트리(Digital Search Tree)

• 비트 값을 기준으로 자식 노드를 분기
• 5비트 키 필드를 가정하고 알파벳 순서를 비트 값으로 할당
• A는 첫 문자이므로 00001

입력 순서

• A = 00001, S = 10011, E = 00101, R = 10010, C = 00011, H = 01000, X = 11000

탐색트리에 의한 우선순위 큐

 

디지털 탐색트리

효율

• O(lgN)
• 어떤 키 내부의 비트 값이 0이 될 확률이나 1이 될 확률이 1/2로 동일
• 새로 삽입되는 노드가 왼쪽으로 삽입될 확률이나 오른쪽으로 삽입될 확률이 거의 동일하므로 균형트리. 트리 높이는 lgN에 근접
• 최악의 경우에는 비트 수 만큼 O(N)

기수탐색 트리

일명 트라이(TRIE)

• 탐색 또는 검색을 의미하는 ReTRIEval의 가운데 스펠
• 디지털 탐색트리의 레코드가 내부노드 또는 외부노드 모두에 분포
• 트라이의 레코드는 모두 외부노드에 분포

트라이

균형 잡힌 트라이

• 효율은 O(lgN)
• 이 경우의 효율은 키 비교 횟수가 아님.
• 키 자체의 비트 열 중 처음 lgN 개의 비트 값을 검사

트라이의 모습

• 레코드의 키 값의 입력 순서와 무관
• A,R,E,S 순으로 레코드가 들어와도 최종 결과는 동일
• 키 내부의 비트 패턴 자체가 삽입위치를 결정
• S와 R처럼 여러 비트에 걸쳐 비트 패턴이 같아지면 트리가 한쪽으로만 분기(One-Way Branch) 되어 균형이 무너짐. 빈 외부 노드가 다수 발생하여 공간적 효율이 저하됨.

다중링크 트라이

• 하나의 노드에서 뻗어나가는 링크의 숫자를 M으로 늘림으로써 높이를 줄임
• 예를 들어, 링크를 4개로 놓고 비트 패턴이 00이면 가장 왼쪽, 01이면 그 오른쪽
• 해시보다 더 좋은 효율을 보일 수도 있음. 해시에서 키를 구성하는 모든 요소를 검사. 트라이는 키 일부만 검사하고도 원하는 레코드를 찾아갈 수도 있음.

다중링크 트라이

 

공간낭비의 우려

• 레벨 1에서 1개, 레벨 2에서 4개의 노드가 존재하면 레벨 3에서 4^2 = 16
• 리프노드 근처에 지나치게 많은 외부노드, 미사용으로 인한 공간 낭비
• 루트 근처에서는 M을 크게하고, 리프 근처에서 M을 작게하여 효율을 개선

해시 - 해시 함수의 필요성

탐색의 효율

• O(lgN)의 탐색 효율이라면 100,000 개의 레코드 중 하나를 찾는데 필요한 비교의 횟수는 lg100,000 = 17
• 매우 빠른 알고리즘. 그러나 이 속도도 느릴 수 있음
• 119 데이터베이스라면 비상 시 전화접속 즉시 주소확인.

해시

• 효율 면에서 근본적인 차이를 지향한다. O(logN)이 아니라 O(1)을 지향
• 데이터 개수 N과 무관하게 단번에 찾아내겠다는 것
• 주어진 키를 사용해서 실제 레코드의 주소를 직접적으로 계산해 내는 것을 해시라고 함. 배열을 사용한다면 이 주소는 배열의 인덱스를 의미
• 해시함수를 가하여 채운 도표를 해시 테이블(Hash Table)이라 함.

해시함수 = 인덱스 계산기

인덱스 계산기

충돌

전화번호 키

• 445-3800 이라는 전화번호를 키로 하는 레코드
• 키 자체를 인덱스로 하여 이 레코드를 T[4453800]에 저장
• 이 경우의 해시 함수는 자체 매핑(Identity Mapping)
• 메모리 크기는 제한적이므로 배열 인덱스의 범위를 줄일 필요가 있음. 같은 동네라면 국을 생략
• T[3800]에 저장. 이 경우 해시함수는 4453800에서 3800으로 가는 매핑.

스트리핑(Stripping)

• 메모리 크기 인덱스 0...999로 매핑.
• 전화번호의 처음 네 자리를 떼어버리면 T[800]에
• 445-3800 이나 445-7800이나 모두 동일한 인덱스로 매핑
• 충돌(Collision)
  - 서로 다른 키에 해시 함수를 가한 결과 동일한 인덱스로 매핑 되는 현상
  - 메모리에 여유 공간이 있음에도 불구하고, 해시 함수 자체의 특성으로 인해 발생

해시함수

자릿수 선택(Digit Selection)

• 일부 자릿수만 골라냄.
• 13자리 주민등록번호 중 홀수 자릿수만 선택. h(8812152051218) = 8112528
• 만약 처음 네 자리를 선택하면 출생 년 월이 같은 사람들은 모조리 충돌

자릿수 접기(Digit Folding)

• 각각의 자릿수를 더해버리는 방식. h(8812152051218) = 8+8+1+...+8 = 44
• 메모리 인덱스의 범위는 0<=h(KEY) 0<=9*13 = 117 의 사이에 존재
• 메모리가 더 크면  h(8812152051218) = 88+12+15+...+8 방식도 가능

모듈로 함수(Modulo Function)

• h(KEY) = KEY mod TableSize. Key를 해시 테이블 크기로 나눈 나머지를 인덱스로. 해시 테이블 크기로 나눈 나머지는 항상 그 보다 작으므로 반드시 인덱스 0...(TableSize-1) 안으로 매핑됨.
• 1236 % 100이나, 3636 % 100이나 모두 동일한 인덱스로 매핑
• 충돌을 최소화하기 위해서 TableSize 숫자의 선택에 유의. 통계에 의하면 이 숫자는 소수(Prime Number)로 하는 것이 유리함.

<<

• 비트 쉬프트 연산자(Bitwise Left Shift Operator)
• 비트열을 왼쪽으로 3비트 이동
• 이전 HashVal에다가 8을 곱한 다음에 그 다음 문자 값을 더함.
• 문자마다 8진법 형태의 자릿수가 있다고 전제
• ABC라는 문자열을 'A' * 8^2 + 'B'*8+'C'로 간주
• 이 방식으로 KIM이라는 문자열을 10진수로 나타내면 'K' *10^2 + 'I'*10 + 'M'이 됨.