해싱
해싱(hashing)
- 탐색 키값을 기반으로 데이터의 저장위치를 직접 계싼함으로써 상수시간내의 데이터를 탐색|추가|삭제할 수 있는 방법
- 실제로 데이터의 개수보다 저장공간이 작으므로 충돌이 발생한다
해쉬함수
-
해시함수(hash function): 실제 구현과정에서 키의 형태에 무관하게 키값을 해시테이블의 주소로 변환시키기 위한 수식함수
-
해시함수 개발의 상황:
a. 입력 키값의 분포를 모른다: 상위|하위|비트에 민감한 해시함수를 피하고 키 범위를 고르게 분포시키는 해시함수를 선택
b. 입력 키값의 분포에 대해 잘못 알고있다: 관련된 키값의 모임을 같은 해시테이블 슬롯으로 할당하는 것을 피하고 분포특성에 종속적인 해시함수를 선택
1) 제산 잔여(mod function): mod 연산
2) 비닝(binning, 통에 담기): 키값의 범위가 100개이고 해시테이블의 크기가 10일때 10개씩 나누어 담는 것
3) 중간 제곱(mid-square): 키값을 제곱한 후 그 결과의 중간에 있는 r비트를 취해서 0 ~ 2r-1 범위의 해시결과로 사용
4) 문자열을 위한 해시함수:
- 각 문자의 아스키 코드값을 모두 더하고 해시테이블 크기|M을 사용하여 모듈로 연산을 한다
- 4바이트씩 문자열을 처리하여 하나의 큰 정수값으로 해석한 뒤 (더 큰 범위를 갖는다), 이 정수값을 모두 더하고 모듈로 연산을 한다
5) 기수변환
6) 폴딩법
7) 자릿수추출
충돌 해결
- 충돌(collision): 해시함수를 사용하더라도 모든 키가 서로 다른 주소로 대응되는 것이 불가능하여 둘 이상의 다른 키가 값은 주소로 사상되는 현상, x != y에 대하여 h(x) = h(y)
1) 개방해싱(연쇄법):
- 테이블의 각 슬롯을 연결리스트의 헤드로 사용
- 충돌된 데이터가 테이블의 밖의 장소에 저장
2) 폐쇄해싱(개방주소법):
- 충돌된 데이터가 테이블내 다른 슬롯에 저장
a. 선형 탐사: p(K, i) = i,
빈 슬롯을 찾을 때까지 버킷의 아랫쪽으로 이동, 1차 쿨러스터링 (레코드들이 연속된 위치를 점유하여 클러스터를 형성하는 경향) 발생
b. 이차 탐사:(quadratic probing): p(K, i) = c1∙i2 + c2∙i + c3, 2차 클러스터링(탐사순서가 주어진 키값이 아닌 홈위치의 함수에 의해 정해짐) 발생
c. 이중 해싱(double hashing): p(K, i) = i * h2(K), 탐사순서가 원래 키값을 이용하도록 탐사함수에 대한 상수간격에 의한 선형탐사를 사용, 좋은 이중해싱은 모든 상수가 테이블 크기 M에 대해 소수여야 한다
d. 버킷 해싱: 해시테이블 슬롯을 버킷으로 묶는 것, 버킷의 빈 슬롯이 없으면 오버플로 버킷에 저장
삭제 연산
-
해시테이블에서 삭제된 빈 슬롯은 빈 것이 아닌 비석(tombstone)을 세워 삽입, 추가에 문제가 없도록 한다
-
비석은 탐색의 평균거리를 증가시키므로, 정기적으로 테이블을 재해시하는 것이 좋다
그래프
그래프의 표현
1) 인접행렬 (adjacency matrix): n x n 행렬을 이용한 표현방법으로
가중치 없는 경우, G[ i ][ j ] <- 0 또는 1
가중치 있는 경우, G[ i ][ j ] <- ∞ 또는 해당 간선의 가중치
2) 인접리스트(adjacency list): n개의 연결리스트의 첫번째 노드를 가리키기 위한 포인터 배열 head와 가중치
그래프 순회
####1. 너비/깊이 우선 탐색
2. 그래프 순회의 응용
1 위상정렬(topological sort): 사이클이 없는 방향그래프의 정점을 한 줄로 나열하는 것
2 그래프의 연결성
3. 최소신장 트리
-
신장트리(spanning tree): 연결된 가중치 무방향 그래프에서 주어진 정점을 모두 포함하는 연결된 부분그래프 중 트리인 것
-
최소신장트리(minimum spanning tree): 연결된 가중치 무방향 그래프에서 가중치의 합이 가장 작은 신장트리
1) 크루스칼(Kruskal)
2) 프림(Prim)
4. 최단 경로(shortest path): 가중치 방향그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치 합이 가장 작은 경로
스트링 알고리즘
1. 스트링 매칭
-
텍스트(text)에서 패턴(pattern)이 나타나는 곳을 찾는 것
-
접근 방식에 따라, 패턴 전처리 방식(에디터), 텍스트 전처리 방식(DNA 문자열)
1) 브루트-포스(Brute-force) / Native / 무차별 대입 공격
-
텍스트의 모든 위치에서 패턴이 나타나는지 찾는 방법, 수행시간 O(mn)
-
텍스트와 패턴의 첫위치를 맞추어 정렬 후, 패턴의 끝문자까지 불일치가 일어나지 않으면 성공, 불일치가 일어나면 다음 문자에서 첫위치를 다시 맞추어 비교한다
2) 라빈-카프(Rabin-Karp)
-
패턴의 해시(hash)값으로 매치의 후보를 찾아서 그 후보에 대해서만 문자별로 비교, 수행시간 최악 O(mn), 최선 O(m+n)
3) KMP(Knuth Morris Pratt)
-
패턴을 전처리하여(패턴의 모든 접두부에 대하여 접두부(prefix)와 접비무(suffix)가 일치하는 경우를 계산, 접미부와 일치하는 진접두부를 구하고 이 정보를 이용하여 매칭, 수행시간 O(m+n)
-
앞부분부터 매칭하여 일치하지 않는 부분의 왼쪽을 가지고, 패턴의 접두부(prefix)와 접미부(suffix)가 동일한 경우를 찾는다, 그 사이를 경계라 한다
4) 보이어_무어(Boyer-Moore)
-
KMP와 동일하게 비교할 필요가 없는 중복된 비교를 줄이며 패턴을 찾는 방법 (뒤부분부터 매칭, 수행시간: 최악 O(mn), 최선 O(n/m)
불일치 문자(bad character) 방법: 불일치가 발생할 경우, 패턴내 해당 불일치 문자가 가장 마지막에 나타나는 위치를 찾아, 패턴을 텍스트와 일치하도록 이동 일치 접미부(good suffix) 방법: 접두부와 접미부가 일치하는 부분을 사용하나, KMP와 반대로 패턴의 오른쪽 부분 문자열을 전처리한다
데이터 압축
-
무손실 압축 (RLE, 허프만 코딩, LZ77)
-
인코딩(encoding, 압축된 데이터로 변환), 디코딩(decoding, 원래의 데이터로 역변환)
1) RLE(Run Length Encoding)
-
스트링에서 동일 문자가 인접하게 반복되어 나타나는 것(run)을 그 문자와 반복횟수로 압축, 수행시간 O(n)
-
일반문서에 비해 영상데이터 압축에 효과적
예) aaabbbbbcaa -> (a,3) (b,5) (c,1) (a,2)
허프만 코딩(Huffman coding)
-
스트링에서 빈도가 높은 문자는 짧은 코드로, 빈도가 낮은 문자는 긴코드로 변환하여 압축, 수행시간 O( |∑| log|∑| + n )
-
빈도가 낮은 문자부터 이진트리를 만들어가며 접두부 코드를 구한 뒤, 압축
-
접두부 코드 작성:
빈도가 가장 낮은 두 개의 정점을 뽑아 이진트리의 부모(두 자녀의 값의 합)를 만들고, 이를 남은 정점에 추가한다
남은 정점들에서 빈도가 가장 낮은 두개의 정점을 뽑는 식으로 동일한 과정을 반복한다
LZ(Lempel-Ziv) 77
-
현재 문자열 대신 앞서 나온 반복되는 문자열의 위치와 길이로 변환하여 압축
-
슬라이딩 윈도(sliding window); 앞으로 나올 문자 Ls개(탐색버퍼, 현재의 사전)와 지나간 문자열 중 마지막 문자 LL개(전항버퍼)를 표시하여, 비교하기에 사용한다
(예) abcdeabcdfi -> (0,0,a) (0,0,b) (0,0,c) (0,0,d) (0,0,e) (5,4,f) (0,0,i)
3. 이미지 압축
-
손실 압축(JPEG, MPEG)
-
일반적으로 인접한 부분에서는 색상이 급격하게 변하지 않는다는 특성을 이용하여
-
2차원 데이터를 단위 블록으로 나눈 뒤 블록별로 압축
-
압축단계: b.cd.q.e
블록화(block): 데이터를 8x8 블록으로 만듦
DCT(discrete cosine transform)
양자화(quantization): 큰값을 작은값으로 표현해주는 과정
엔트로피 코딩
4. 동영상 압축
MPEG(Moving Picture Experts Group
- 일반적으로 연속된 시간의 2차원 이미지들이 급격하게 변하지 않는다는 특성을 이용하여
- 시간순으로 나열된 2차원 데이터를 연속된 시간의 특성을 이용하여 압축
- JPEG + 움직임 벡터(motion vector)
