String
2019. 01. 28 (Mon)
I. 컴퓨터 문자표현
bit map : 너무 메모리 낭비가 심하다.
1. Code system
코드지정 : bit level에서 글자마다 숫자 지정
컴퓨터 마다 코드 시스템이 다름
ASCII : 7bit열을 이용해 128개 문자를 지정한 표준
확장 ASCII : 8bit열 사용. 맨 앞 문자가 0이면 그냥 ASCII. 1에는 지역마다 정해서 사용
Unicode
unicode : 다국어 처리 표준. 4Byte
big-endian : 큰 자리수가 앞에. 일반적으로 생각하는 bit열
little-endian : 작은 자리수가 앞에. 일반 bit열의 역순
UTF
utf-8 : web. min: 8bit, max: 32bit
utf-16 : windows, java, min:16bit, max: 32bit
utf-32 : unix, min:32bit, max:32bit
II. 문자열
문자의 모임
가변 길이 문자열
지정한 문자열 길이 만큼 문자를 저장하자
- delimeter : C방식. 문자열 마지막에 ‘null문자 \0’ 사용해서 문자열 종료를 알림
- length기반 : Java 방식. String 클래스에 길이 등의 정보를 담고있음
- 문자열 처리 필요 연산을 제공
1. 문자열 to 정수형
‘1’ - ‘0’ = 1
‘2’ - ‘0’ = 2…
앞에서 부터 하나씩 문자를 가져와서 ‘0’과의 차이 구하고 10곱하는 연산 진행
2. 정수형 to 문자열
12345 % 10 = 5
5 + ‘0’ = ‘5’
III. 패턴 매칭 알고리즘
본문 : t, 패턴 : p
1. 고지식한 알고리즘
O(t*p)
본문과, 패턴을 하나하나 비교하며 탐색
2. 카프 - 라빈 알고리즘
Hash 방법 사용하여 문자를 비교
본문의 모든 부분에 패턴 길이 만큼의 문자열 마다 해시값을 계산
본문을 처음부터 탐색하며, 패턴과 hash값이 일치하는 부분에서만 매칭을 비교
Hash
Key-Value로 이루어진 자료구조
Key값을 해시 함수에 대입하여 value에 매칭
Key값을 bucket 수 만큼 범위 내의 주소값에 사상
Hash Collision : 한 주소값에 다른 값이 존재할 경우
- Chaining : 동적으로 메모리 추가 할당하여 리스트로 연결
- 단점 : 메모리 비효율, 탐색 시간 증가
- 개방 주소법 : 비어있는 다른 메모리 공간에 할당
- 단점 : 연쇄 충돌 발생, 클러스팅.
3. KMP 알고리즘
꼭 한 칸씩 옳겨갈 필요가 있나?
틀린 지점으로 건너 뛰면서 탐색을 진행한다
O(t+p)
failure 함수
배열p에 탐색에 실패한 위치에 따라 이동할 거리를 저장
앞에 문자열의 접두어, 접미어를 생성하면서 겹치는 위치 조사
탐색에 실패했을 경우 그만큼 앞으로 이동
접두어를 생성
- abbabb => a, ab, abb, abba, abbab, abbabb
접미어를 생성
- abbabb => b, bb, abb ,babb, bbabb, abbabb
비교를 진행하다 틀린 부분이 나왔을 경우, 패턴의 접두어와 본문의 접미어중 가장 많이 일치하는 부분으로 이동하여 다시 탐색을 진행
4. 보이어 - 무어 알고리즘
뒤에서 부터 계산
틀린 문자가 패턴 내에 존재할 경우 그 문자에 초점을 맞춰 다시 비교
틀린 문자가 패턴 내에 없을 경우 패턴 길이 만큼 이동
O(t+p), KMP보다 평균적으로 빠르다
5. 사용 예
암호화
대칭키 암호화
압축