Algorithm. 문자열 - 트라이

1. 트라이

• 정보 검색에 사용된 자료구조
• 문자열의 집합을 표현하는 트리

다음 5개의 문자를 하나의 트라이로 표현.

• 각 간선은 하나의 문자에 대응
• 같은 노드에 나오는 간선들은 같은 레벨을 갖지않는다.
• 각 문자열을 단말 노드에 대응하고 문자열의 개수만큼 단말 노드가 존재한다.

2. 접미어 트라이

• 문자열의 모든 접미어를 Trie로 표현
• 길이가 n인 문자열 A = a0 a1 a2 ... an-1
• ai ai+1 ai+2 an-1인 n개의 접미어

 

접미어 트라이를 이용한 문자열 연산

• 부분 문자열 검사
• 두 접미어의 최장 공통 접두어 찾기
• 사전적 순서로 정렬된 k번째 접미어 찾기

부분 문자열 검사

'abac' 문자열 접미어 트라이가 있을 때, 어떤 문자열이 부분 문자열인지 검사하는 방법은 한 문자씩 루트에서 대응되는 간선을 따라가는 것이다.

 

두 접미어의 최장 공통 접두어

• 두 접미어의 끝 글자에 대응하는 노드 선택
• 가장 가까운 공통 조상(Logest Common Ancestor)를 찾는다.
• 공통 접두어를 만든다.

사전적 순서로 정렬된 k번째 접미어 찾기

• 깊이 우선 탐색으로 문자열을 생성하면 사전적 순서로 정렬
• 생성된 문자열들을 메모리에 모두 저장하지 않고 인덱스 값만 저장한다.

압축된 트라이(Compressed Trie)

• 노드들과 간선들을 부분 문자열로 압축
• 자식인 하나만 있는 노드들을 하나의 간선으로 묶어서 표현한 형태