gnuykob_sw

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "자료구조", 유석종 교수님

1. 탐색

- 다수의 레코드 집합에서 특정 키 값과 일치하는 레코드를 찾는 작업이다.

- 레코드는 객체의 속성에 해당하는 필드들의 집합으로 표현된다.

2. 순차 탐색

- 정렬되지 않은 레코드들에 대해 조건에 맞는 목표 키를 찾을 때까지 순차적으로 비교를 반복하는 작업이다.

- 정렬과 같은 요구 조건이 없어서 알고리즘은 단순하지만, 최상의 경우(1)와 최악의 경우(n) 탐색 성능에 큰 편차가 발생할 수 있다.

- 레코드 수(n)가 클수록 탐색 시간이 많이 걸린다

- 순차 탐색 알고리즘의 평균 비교 횟수 : (n + 1) / 2

#include <stdio.h>

int seq_search(int num[], int key, int n);

void main()
{
    int pos;
    int num[] = {12, 5, 6, 19, 23, 3, 7, 34, 89, 45, 22};
    
    pos = seq_search(num, 89, 11);
    printf("position = %d\n", pos);
    
    pos = seq_search(num, 43, 11);
    printf("position = %d\n", pos);
}

int seq_search(int num[], int key, int n)
{
    int i;
    for (i = 0; i < n; i++)
        if (num [i] == key) return i;
        
    return -1;
}

3. 이진 탐색

- 항목들을 정렬한 후 탐색을 적용한다.

- 겹치는 값이 없어야 한다.

- 오름차순으로 정렬된 항목들에 대해 중간값을 찾아 탐색 키와 비교한다.

- 탐색 키와 중간 값이 같으면 중간 값의 위치(인덱스)를 반환하고 탐색을 종료한다.

- 탐색 키가 중간 값보다 작으면 중간 값의 왼쪽에 있는 항목들로, 중간 값보다 크면 중간 값 오른쪽에 있는 항목들로 탐색 범위를 변경한다.

- 변경된 범위 항목에 대해 위의 과정을 반복한다.

- 탐색 대상 항목 수가 0이면 탐색 키를 찾지 못한 경우로 탐색을 종료한다.

- 시간 복잡도는 O(log₂ⁿ ) 이므로 순차 탐색에 비해 속도가 빠르다.

#include <stdio.h>

int binary_search(int mylist[], key, left, right);

void main() 
{
    int pos, size = 9;
    int mylist[] = {0, 1, 5, 9, 13, 17, 23, 32, 45};
    
    pos = binary_search(mylist, 45, 0, size-1);
    print("position = %d\n", pos);
    
    pos = binary_search(mylist, 8, 0, size-1);
    print("position = %d\n", pos);
}

int binary_search(int mylist[], key, left, right)
{
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (key == mylist[mid]
            return mid;
        else if (key < mylist[mid])
            right = mid - 1;
        else if (key > mylist[mid])
            left = mid + 1;
    }
    return -1
}

4. 보간 탐색

- 항목들이 정렬되어 있을 때 키 값의 차이와 위치의 차이가 비례한다는 가정을 바탕으로 한다.

- 탐색 키와 탐색 경계 값과의 차이를 고려하여 비교 키의 위치를 결정한다. 

- (list[right] - list[left]) : (key - list[left]) = (right - left) : (탐색 위치 - left)

- (양쪽 경계 값들의 차이) : (키 값과 왼쪽 경계 값의 차이) = (양쪽 범위의 거리) : (탐색 위치와 왼쪽 경계의 거리 차이)

#include <stdio.h>

int interpolate_serarch (int list[], int size, int key);

void main()
{
    int size = 12;
    int key = 39;
    int pos;
    int list[] = {2, 3, 5, 7, 8, 10, 13, 20, 25, 39, 45, 55};
    
    pos = interpolate_search(list, size, key);
    printf("%d is in %d\n", key, pos);
    key = 2;
    
    pos = interpolate_search(list, size, key);
    printf("%d is in %d\n", key, pos);
    key = 55;
    
    pos = interpolate_search(list, size, key);
    printf("%d is in %d\n", key, pos);
}

int interpolate_search(int list[], int size, int key)
{
    int pos;
    int left = 0;
    int right = size - 1;
    
    while (left <= right) {
        pos = left + (key - list[left]) * (right - left) / (list[right] - list[left]);
        if (list[pos] < key)
            left = pos + 1;
        else if (list[pos] > key)
            right = pos - 1;
        else return pos;
    }
    return -1;
}

5. 해싱 탐색

- 탐색 키에 직접 산술적인 연산을 적용하여 탐색 키의 정보가 저장되어 있는 테이블 상의 위치를 계산하고 이 주소를 통해서 정보에 접근하는 방식이다.

- 즉, 반복적인 비교를 수행하는 것이 아니라, 키 자체에 있는 해답을 해시 함수를 통해 찾아내는 것이다.

- 시간 복잡도는 이론적으로 O(1)로 입력의 수 n에 상관없이 일정한 상수 시간을 갖는다.

- (ex) Dictionary

    - Entry (key, value)  // (word, definition)

    - Applications

        - Word / Thesaurus references

        - Spelling checker in word processor or editor

        - Electronic signature encoding/decoding

    - Operations

        - determine if a particular symbol(key) exists in the table (단순조회)

        - retrieve the attributes of a key (키의 속성값을 참조하는 연산)

        - modify the attributes of a key (키의 속성값 변경)

        - insert a new entry with a key and value (새로운 entry 추가)

        - delete an entry (entry 삭제)

5-1. Terms

- 해시 테이블 : 명칭(identifier)들이 저장된 고정된 크기의 표

- 명칭 밀도(ID) : 전체 명칭의 개수(T) 중 해시 테이블에 적재된 명칭 개수(n)의 비율 = n / T

- 적재 밀도(LD) : 해시 테이블의 크기에 대해 적재된 명칭 개수의 비율 = n / N

- 동의어(synonym) : 해시 테이블의 동일한 버켓 주소로 매핑된 서로 다른 명칭들, f(i₁) = f(i₂) 이면 i₁와 i₂는 동의어이다.

- 오버플로우 (overflow) : 명칭 i가 이미 꽉 찬 버켓으로 해싱(매핑)되는 경우 오버플로우가 발생한다고 말한다.

- 충돌 (collision) : 두 개의 서로 다른 명칭이 해시 테이블의 같은 버켓 주소로 매핑되면 충돌이 발생한다고 한다. 버켓의 크기가 1이면 충돌과 오버플로우가 동시에 발생한다.

- 해시 함수 : 해시 함수는 계산이 쉬워야 하고 명칭 간의 충돌을 최소화하여야 한다. 또한, 비대칭 편중분포를 막아야 한다.

    - 균등 해시 함수 : 각 버켓에 적재될 확률이 1/b 인 해시 함수 (P[f(x) = i] = 1 / b

    - 중간 제곱 해시 함수 : 명칭을 2진수로 변환한 후 제곱한 결과값에서 중간의 일부분을 해시 테이블 주소로 활용하는 함수, 테이블에 2ⁿ개의 버켓이 존재한다면 n개의 비트를 추출한다. collision을 최소화하기 위해 사용된다. 

    - 나눗셈 해시 함수 : 명칭을 특정 수로 나눈 나머지를 해시 테이블 주소로 사용하는 방법,예를 들어 해시 테이블 크기가 D라면 명칭 x를 D로 나눈 나머지 (0 ~ D-1)을 주소 값으로 사용한다. 이때 D는 분포에 영향을 주기 때문에 "소수"를 사용하는 것이 가장 좋고, 짝수는 사용하지 않는다. 나누는 수로 짝수를 사용하면 편중분포가 나타나기 때문이다.

    - 폴딩 해시 함수 : 명칭에 해당하는 비트 열을 해시 테이블 크기만큼 여러번 접어서 주소값으로 사용하는 것이다.

        - 이동 폴딩 : 명칭을 k 자리수로 분할한 뒤 순서대로 더한 결과값을 오른쪽에서 k자리 만큼 추출하여 주소 값으로 사용

        - 경계 폴딩 : 분할한 문자열에서 짝수 번째 문자열을 뒤집어서 덧셈을 수행한 후 k 자리의 문자열을 추출하여 사용

    - 키 분석 해시 함수 : 명칭의 구성과 내용을 미리 예측할 수 있는 경우에는 명칭을 분석하여 해시 테이블 주소로 사용할 키 값을 추출하는 방법을 사용할 수 있다. 예를 들어서 명칭이 학번일 경우, 앞의 두 자리는 입학년도임을 알고 그 부분은 배제하고 생각할 수 있다.

5-2. Static Hashing

- 해시 테이블의 크기가 고정되어있어 프로그램을 변경하지 않는 한 크기가 변경되지 않는 해싱 탐색 방법이다.

cf) Dynamic Hashing - 키 충돌 빈도에 따라 유연하게 해시 테이블 크기를 재구성하는 방법이다.

5-3. Hash Table 생성

// 해시 테이블 선언문

#define TABLE_SIZE 13

struct bucket
{
    int flag;
    char key[10];
};

struct bucket hash_table[TABLE_SIZE];

// 해시 테이블 초기화

void init_table()
{
    int i;
    for (i = 0; i < TABLE_SIZE; i++)
        hash_table[i].flag = 0;
}

5-4. Overflow 처리 방법

- Linear Probing 선형 탐색

    - static hashing 인 경우에 적용 가능하다.

    - overflow가 발생했을 때 선형적으로(순차적으로) 다른 비어있는 slot을 찾아가는 방법이다.

    - 이 결과 다른 home bucket으로 값이 저장될 수 있다.

    - HT[f(x) + j] % TABLE_SIZE, where 0 ≤ j ≤ TABLE_SIZE

    - 선형탐색에 의한 명칭 삽입 처리시 다음의 4가지 겨우 중 한 가지가 발생한다.

    1) 탐색된 버켓에 삽입하려는 명칭이 이미 저장되어 있는 경우 : 중복된 명칭으로 보고하고 오류 처리 or 특정 필드 값 갱신

    2) 탐색된 버켓이 비어 있는 경우 : 해당 버켓에 명칭 저장

    3) 탐색된 버켓이 x가 아닌 다른 명칭을 포함하고 있는 경우 : 다음 버켓 탐색 지속

    4) 탐색 결과 홈 버켓ㅇ로 다시 돌아온 경우 : 전체 버켓이 모두 꽉 찬 상태 → 오류 보고 후 종료

    - 문제점 : 명칭들이 서로 모여서 클러스터를 형성한다. 충돌 횟수가 증가할수록 탐색 속도도 느려진다. 

- 해시 함수 정의 

    - 키 (명칭)들을 ASCII 숫자값으로 변환한 뒤 해시 주소를 계산하는 방법이다.

// sum of ASCII codes of string chars

int transform (char *key)
{
    int number = 0;
    while (*key)                // NULL 값이 아니면
        number += *(key++);     // 정수 + 문자 -> 문자가 ASCII 코드로 변환됨
    return number;
}

int hash (char *key)
{
    return (transform(key) % TABLE_SIZE);
}

    - (ex)

이 경우 number는 F, O, R 의 ASCII 코드의 합이 된다. 그리고 그 합을 table size로 나눈 나머지가 주소가 된다.

5-5. Overflow 해결방법

- Linear probing 선형탐색법

    - ht[(f(x) +i) % b], 0 ≤ i ≤ b-1

- Quadratic probing 이차조사법

    - ht[f(x)], ht[f(x) + i²) % b], ht[f(x) - i²) % b], ..., 

    - 선형탐색법을 양방향으로 번갈아 탐색하는 방법이라고 볼 수 있다.

    - 선형탐색법은 한 방향으로 계속 탐색하기 때문에 cluster를 형성하기 쉬웠고, 이 방법은 그것을 해결할 수 있다.

- Rehashing 재해싱

    - overflow가 발생할 때마다 또 다른 해시 함수를 통해서 새로운 버켓을 탐색하는 방법이다.

    - 준비한 모든 해시 함수를 적용해도 빈 버켓 주소를 찾지 못하면 오류를 보고하거나 준비된 처리를 시행한다.

- Chaining 해시 체인

    - 각 버켓을 연결 리스트로 구현하여 특정 버켓에 충돌되는 명칭들을 연결 리스트로 관리하는 방법이다.

    - 근본적으로 overflow를 방지할 수 있다.

    - 하지만, 버켓 수에 비례하는 연결 리스트가 필요하며 원래 해싱 탐색 시간인 O(1)에 연결 리스트 탐색 시간 O(n)이 추가적으로 ㅣㄹ요하다. 

    - 각 연결 리스트에는 버켓의 헤드 노드가 존재한다.