Algorithm. 문자열 - 접미어 배열

1. 접미어 배열

• 텍스트의 접미어들을 사전식으로 나열한 배열
• 파이썬에서는 리스트로 구현한다.
• 접미어 트리보다 메모리를 효율적으로 사용하지만 다소 느리다.
• 텍스트 인덱싱, 데이터 압축, bio-informatics등의 다양한 분야에서 사용한다.

예시) s = abab

b, ab, bab,b abab

=> 접미어 사전순 정렬 : ab, abab, b, bab

=> 접비어 배열 : [3, 1, 4, 2]

 

2. 접미어 배열 복잡도

• O(n)의 메모리 크기
• O(nlogn) 시잔에 생성
• 텍스트 T에 패턴 P의 존재를 O(|P| + logn) 시간에 계산

3. 접미어 배열 장점

• 생성 방법이 접미어 트리에 간단하다.
• 적은 메모리로 구현 가능
  • 2개의 선형 크기의 리스트로 구성
  • 전형적으로 접미어 트리에 비해 1/4크기의 메모리를 사용한다고 알려져있다.

예시

LCP 배열

• 접미어 배열의 보조적인 자료 구조로 최장 공통 접두어(Longest Common Prefix) 배열을 생성한다.
• 사전 순 정렬된 접미어 배열에서 연속적인 2개의 접미어들 사이의 최장 공통 접두어의 길이를 저장한다.
• 접미어 배열의 순회나 패턴 매칭을 효율적으로 수행하는데 사용