[알고리즘] 문자열 심화

문자열을 어떻게 핸들링할 것인가.

C: delimited

Java: length controll 방식

 

C의 장점은 문자열의 sub string을 핸들링할때 발현된다! (특히, Suffix array)

 

컴퓨터에서의 문자표현: 정수화해서 저장하고 사람이 원할때 화면에 표현해주는 것이다.

2차 대전 당시에 컴퓨터는 덩치가 크고 연산속돡 느리고 가격이 고가, 각 지역마다 영어를 표현하는 코드값이 다 다랐다.

국방성에서 네트워크라는 것을 보급해서 컴퓨터가 연결되었는데 지역 컴퓨터가 연결되었다.

이때 코드체계가 달라서 해석이 안된다.

 

그래서 나온게 1967년에 표준 ASCII코드를 만들었다.

총 7bit 인코딩으로 0~32의 출력 불가능한 제어문자와 33~ 126까지의 ASCII문자들로 구성된다.

최소한 프로그래머라면 아래 3가지 아스키 코드는 기억하자.

'0':48

'A': 65

'a': 97

 

영국에서 확장아스키코드를 만들었다.

총 8bit ,인코딩으로 특수문자, 특수기호들을 추가로 사용할 수 있게 할 수 있는 아스키 코드이다.

표준 아스키 코드는 하드웨어및 소프트웨어에서 세계적으로 통용되는데 비해

확장아스키는 프로그램이나 컴퓨터 또는 프린터가 그것을 해독하는 걸 지원해야 사용할 수 있다.

 

즉 표준 아스키코드가 대부분의 형식에 사용된다. 

오늘날 대부분의 컴퓨터는 문자를 읽고 쓰는데 ASCII형식을 사용한다.

 

우리나라의 경우는 어떨까?

Korean Alphabet은 조합형이다.

1:한글, 5bit: 초성, 5bit: 중성, 5bit: 종성

 

그런데!

중국: 완성형, 일본: 완성형 -> 아시아권이 모두 완성형이기 때문에

->한국을 위해서 마이크로소프트가 조합형으로 바꿔줄까?->강제로 한국 시장을 바꾸는 작업을 한다.

=> 무료로 MS를 뿌리고, 조합형이 처리 효율성에서 좋지가 않다고 홍보했고 완성형을 강요한다.

 

KSC5601 -> euc-kr 한국 2350자 완성형

CP949-> MS의 기본 인코딩, 한국 여전히 완성형으로 밀어붙이고 있다(euc-kr보다 확장된 완성형)

Unicode->전세계 언어가 현재는 이 방식을 사용한다.

Unicode는 독특하게 한글에 있어서 조합형과 완성형을 모두 표현할 수 있다 예를 들어서

유니코드 한글자가 'ㄱ'을 의미하게 할 수도 있고, '가'를 의미하게 할 수도 있다.

 

유니코드에 인코딩이 필요한 이유

UCS-2 

UCS-4(더 많은것) : endian을 어떤방식으로 표현할 것인지에 대해서는 통일하지 못했다.

 

encoding:유니코드를 인코딩하는 방법

UTF-8(한바이트로 시작해서 2byte, 4byte까지 늘어난다.)  -> Web에서 제일많이쓴다.

->한글 아시아 문자는 3바이트 

UTF_16 : window, java

UTF-32: unix

---

문자열의 패턴 탐색 알고리즘

 

1. 고지식한 패턴알고리즘: 본문 문자열을 처음부터 끝가지 차례대로 수뇌하면서 패턴 내의 문자들을 일일히 검사하는것

 

: j가 패턴의 길이만큼 이동했거나, i가 대상 문자열 길이만큼 이동했다면 종료한다.

 

 

2. Karp-Rabin Algorithm(해싱을 이용한 패턴 탐색)

: 평균적으로 선형 O(N+M)에 가까운 빠른 속도를 가지는 알고리즘

a-e사이의 문자만 있다면 eeaab -> 4*5^4 + 4*5^3 + 0*5^2 + 0* 5^1 + 1 = 3001

해싱할 때 곱하는 수는 소수로 둔다. (어떤 소수든 상관없는듯?) by 연구결과

 

단점: 비교하고자 하는 문자열길이가 크면 해싱할때 컴퓨터 레지스터의 용량이 초과될 수도 있다. (적절한 mod연산으로 레지스터 용량이 초과하지 않도록 주의해야한다.)

-> 해결책: prime number로 mod연산을 사용하여 크기를 제한하는것. mod할 prime number는 충분히 큰 소수로 잡되  레지스터에 수용될 수 있도록 잡아야한다. (64bit)

-> 이렇게 해싱을 하면 실제 패턴이 일치하지 않아도 해싱값이 같을 수 있다는 문제가 있기 때문에

해싱 값을 찾았다면 문자열이 정확히 일치하는지 다시 검사해줘야한다. (다른 해싱 기법도 마찬가지이다)

 

3. KMP알고리즘:

매칭이 실패했을 때 돌아갈 곳 준비해서 불일치가 발생했을 때 돌아갈 위치값만큼 성큼 이동한다.

 

접두사에 대한 접미사(해당 글자까지 일치하는 접두사를 구한다.)

 

next배열(Pi 배열)설정

: i번째 인덱스까지 일치하는 접미사 == 접두사 크기

이동거리 = 일치하는 패턴의 길이 - 최대 경계너비

현재 위치에서 접두부와 Reverse접미부(현재위치 기준)가 몇개가 일치하는지를 의미한다.

예시)

ABACABA

i=0 A  => 최대 공통 접사 "" (약간 예외적이긴 한데 길이가 pi[0] 항상 0이다.)

i=1 AB => 최대 공통 접사 ""

i=2 ABA => 최대 공통 접사 "A" => pi[2] = 1;

i=3 ABAC => 최대 공통 접사 "" => pi[3] = 0;

i=4 ABACA => 최대 공통 접사 "A" => pi[4] = 1;

i=5 ABACAB => 최대 공통접사 "AB" => pi[5] = 2; (주의해야 할점은 접미사를 B, BA, BAC ... 이렇게 reverse한 상태로 생각하면 안된다. B, AB , CAB, ACAB이런 형태로 접두사랑 비교해야한다.)

i=6 ABACABA => 최대 공통접사 "ABA" => pi[6] = 3;

 

빠르게 next배열(pi배열)을 코드뿐만 아니라 머리속으로 설정할 수 있게 연습하자. 생각보다 어렵다.

 

패턴 검사할때 next배열을 어떻게 활용할까?

만약 매칭 실패시 [매칭실패한 위치의 -1만큼 이전 위치의 next배열값 위치의 문자]랑 ["검색 대상이 되는 문자열의 다음 위치의 문자]랑 비교한다.

 

---

보이어 무어(Boyer-Moore 알고리즘)

: 생각의 전환으로 패턴의 오른쪽부터 비교한다. 아무리 앞에 문자가 같아도 마지막 문자가 다르면 안되잖아?

-> 대부분의 상용 소프트웨어에서 채택하고 있는 알고리즘

1. 오른쪽 끝에 있는 문자가 불일치

2.. 이 문자가 패턴내에 존재하는지 확인하고! 이동거리는 무려 패턴의 길이만큼 이동한다.

 =>생각의 전환 : 비교를 마지막부터 함으로 일반적이지 않지만 단순한 생각의 전환으로 효율이 상승한다.

3. 불일치가 발생했는데 문자가 패턴내에 존재하면 점프한다.

 

점프 정보 배열 준비

1. 배열크기는 a[128]  패턴에 해당하는 문자는 

    => 

2. 패턴에 해당하지 않는 문자는 문자열의 길이만큼

 

BC, GS를 Heuristic하게 비교해서 jump하는게 맞다.

그런데 보통 문자열 검색시에 보조 알고리즘이기때문에 BC만 사용해서 구현하는것이 좋고 극한의 효율을 위해선 GS도 추가하면 좋다.

성능 안좋은 경우 -> 패턴의 전체문자가똑같을때!!!!!!

ex) "aaaaaaa"

---

Trie( retriver에서 따온것이다) 트라이

트라이는 문자아ㅕㄹ의 집합을 표현하는 트리이다.( 모든 문자열은 다른 문자열의 접두어가 아니라고 가정한다)

1. 이 Trie에 포함된 문다열집합인지 확인하기 쉽다.

2. 공통 접두어를 구하기 쉽다.

3. 특정 단어가 문자열에 포함되어있는지 판단도 쉽다.

각 문자열은 Leaf 노드에 대응된다.(문자열을 어디서 자른 접미사인지 index를 마지막 leaf노드에 기록해둔다)

 

 

메모리 낭비가 심하다. 

 

한 문자열의  접미사Tri를 만들면

1. 부분 문자열 검사가 쉽다. -> 모든 부분 문자열을 찾기쉽다. 

최장 공통 접두어 찾기-> 가장 가까운 공통 조상찾기 알고리즘을 적용하면 찾을 수 있다.

사전적 순서로 정렬된 접미사 찾기 쉽다.-> DFS하면 사전순서대로 나옴 (출력할 접미사를 저장할때 0,1,2,3 잘리기 시작하는 인덱스를 저장하면 메모리낭비를 좀 줄일 수 있다)

 

메모리 낭비 해결방법 -> Compressed Trie: 노드들과 간서들ㅇ를 부분 문자열로 압축

-> Suffix trees(접미어 트리) = Compressed Trie => 한노드에 STringd을 다 넣어버리고 만약 공통되는 부분이 있다면 공통되는 부분이 있다면 그것만 포함하는 노드를 구축하고 나머지는 자식노드로 내린다.

 

위 방법의 문제점

"x a b x a" a가 접미사면서 접두어여서 표현이 잘 안된다..

S5 = a

S2 = abxa

-> 접미사 접두사 겹침...

 

해결: 문자열의 S의 끝에 특수한 문자 $를 추가한다.  그러면 S5에 해당하는 a$로 빠짐없이 잘 표현가능하다.

 

접미어 트리 시간복잡도

1. O(n^2)

2. O(nlonN) -> 1995 발견 알고리즘

3. O(n) -> 1997발견 알고리즘

 

결론적으로는 접미어 트리는 잘 안쓴다!

 

=>Suffix array가 있다 ( 공간복잡도 효율 높고 Tree보다 약간 느리다.)

 

Tree처럼 문자열을 실제로 저장하는게 아니라 Suffix array는 자르기 시작할 index만 가지고 문자열 사전순으로 정렬한 배열을 의미한다.