접미사 배열 & 맨버 마이어스 알고리즘

 

문자열 알고리즘 종류 

---

KMP 알고리즘

라빈카프 알고리즘

접미사 배열 - 맨버 마이어스 알고리즘

아호-고라식

Z 알고리즘

 

 

접미사 배열 suffix array

---

정의 : 문자열 H가 문자열 N을 포함한다면 N은 H의 어떤 접미사의 접두어라는 전재로 

전체 문자열 S 의 모든 접미사들을 사전순으로 정렬한 배열이다 

 

S 문자열 = banana 에 대한 정렬되지 않은 Suffixr이다 (한글자씩 지우면 배열이 나온다)

 

banana

anana

nana

ana

na

a

 

 

맨버-마이어스 알고리즘

---

Manber-Myers 알고리즘은 랭크 개념과 기수 정렬을 사용하여 시간 복잡도를 줄이는 알고리즘이다

 

(한글자씩 비교하면 오래걸리잖아. 그럼 2글짜씩 겹쳐지는 단어로 구분해서 정렬해보자 , 

2글짜씩 구분했는데도 또 겹쳐지는 단어가 있네 , 그럼 4글짜씩 구분해보자.. 그럼 최종적으로 중복없이 다 다른 구분이 가능하다)

ex) 제로베이스를 '제' 만 검색하면 너무 많이 나오고 '제로' 검색하면 제보다는 적지만 많이 검색되고...'제로베이스'검색하면 처음보다는 검색량의 수가 적지만 내가 검색하고 자하는 의미에 가까워지는 같은 느낌인것같다  (나만의 생각) 

 

d까지의 랭크를 이용해 앞 d*2글자까지 문자열을 정렬

d*2까지 정렬된 SA를 이용해 d*2에 대한 랭크 부여 

모든 접미사가 다른 랭크를 가질때까지 반복 

 

첫 1글자 기준으로 정렬한다     banana =   b.   a.   n.  -> 첫번째 배열 의 그룹을 구분한다

 

 

구분	Suffix	Rank
a	anana	0
	ana
	a
b	banana	1
n	nana	2
	na

 

 

첫 2글자 기준으로 정렬한다 banana = ba.  an.  na.  a -> 두번째 배열

첫번째 배열과 두번째 배열을 비교하여 서로를 구분하는 랭크를 구분한다 

 

 

구분	Suffix	Rank
ba	banana	1	1
an	anana	3	0랭크 였지만 다른 랭크로 변경
	ana	3	0랭크였지만 다른 랭크로 변경
a	a	0	0
na	nana	2	2랭크였지만 다른 랭크 변경
	na	2	2

 

만약 접미사의 그룹이 같다면 다음 비교할 4글자 기준에서 랭크를 변경해라 

첫 4글자 기준으로 정렬한다 banana = bana.  anan  nana  ana

 

구분	Suffix	Rank
bana	banana	1
anan	anana	5
nana	nana	4
ana	ana	3
na	na	2
a	a	0

최종적으로 각 접미사별 다 다른 랭크가 나오게끔 정렬한다 

 

 

접미사배열 시간복잡도

---

시간 복잡도 Big O 표기법 이란 

불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다 

 

Bio O 표기법	내용	시간복잡도 빠른순
O(1)	입력자료의 수에 관계없이 일정한 실행시간을 갖음	1
O(logn)	입력자료의 수에 따라 시간이 흐를수록 시간이 조금씩 증가	2
O(n)	입력 자료의 수에 따라 선형적인 실행 시간이 걸리는 경우 - 입력자료마다 일정 시간 할당	3
O(nlogn)	큰 문제를 일정 크기 갖는 문제로 쪼개고(logn+logn+ .. + logn) 다시 그것을 모으는 경우	4
O(n^2)	이중 루프내에서 입력 자료를 처리할 때	5
O(n^3)	삼중 루프 내에서 입력자료 처리할 때	6
O(2^n)		7
O(n!)		8

 

스택은 삽입과 삭제가 최상단 Top에서만 일어나기 때문에 O(1) 이 적용된다 

스택은 특정 데이터 값을 찾을때 까지 수행하기 떄문에 O(n)이 적용된다  

 

접미사 배열의 시간복잡도	알고리즘 없이 일반 정렬	O(N^2lgN)
	맨버-마이어스 알고리즘 사용시	O(Nlg^2N)

 

 

 

 

접미사 배열의 활용 

---

텍스트 검색

전문검색

접미사 배열을 이용한 데이터 경로 기반 검색