uuuouuo.log
로그인
uuuouuo.log
로그인
Trie
uuuouuo
·
2022년 8월 4일
팔로우
0
LCP
문자열
문자열매칭
알고리즘
트라이
0
ALGORITHM
목록 보기
5/8
📖 트라이
정의
문자열의 집합을 표현하는 트리
특징
시간복잡도 측면에선 효율적이지만, 공간복잡도 측면에선 효율적이지 않음
트라이의
생성 시간 복잡도는 O(MxL)
,
탐색 시간 복잡도는 O(L)
(제일 긴 문자열의 길이 : L, 총 문자열들의 수 : M)
트라이의 각 간선은 하나의 문자에 대응
같은 노드에서 나오는 간선은 다 다른 문자
루트에서 단말 노드까지 이른 경로는 하나의 문자열
💬 접미어 트라이
문자열의 모든 접미어를 Trie로 표현
하나의 문자열의 모든 접미어를 포함하는 트라이의 압축된 표현
공간 복잡도를 줄이기 위해 접미어 배열이 알려짐
문자열 연산에 필요한 알고리즘을 빠르게 구현 가능
루트를 제외한 내부 노드들은 최소 2개의 자식 가짐
접미어 트라이를 이용한 연산
부분 문자열 검사
ex) ba가 abac의 부분 문자열인가
두 접미어의 최장 공통 접두어 찾기
ex) abac와 ac의 최장 공통 접두어는 무엇인가
사전적 순서로 정렬된 k번째 접미어 찾기
ex) abac에서 사전적 순서로 3번째 접미어는 무엇인가
문자열 매칭
1. 접미어 Trie를 통한 부분 문자열 검사
한 문자식 루트에서 대응되는 간선 따라가기
2. 두 접미어의 최장 공통 접두어
두 접미어의 끝 글자에 대응하는 노드 선택
가장 가까운 공통조상 찾기
루트에서 공통조상까지가 최장 공통 접두어가 됨
3. 사전적 순서로 정렬된 k번째 접미어 찾기
◾ Compressed 트라이
노드들과 간선들을 부분 문자열로 압축
하나의 간선이 있을 경우만 압축
S = { x a b x a }의 접두어
1 =
xabxa
, 2 =
abxa
, 3 =
bxa
, 4 =
xa
, 5 =
a
일 때
종료 문자($) 추가 : S = { x a b x a $ }의 접두어
하나의 접미어가 다른 접미어의 접두어가 되는 경우를 표현하기 위해 문자열 끝에 특수 문자($) 추가
간선 라벨을 효과적으로 저장하기 위해 부분 문자열의 인덱스 시작과 끝(i, j) 저장 가능
◾ 접미어 트리 생성 알고리즘 - Trivial
시간 복잡도 : O(n^2)
예시
a b a b $
1. 가장 긴 접미어 삽입 후 그 다음 긴 접미어 삽입
가장 긴 순서로 삽입
2. 접미어인 ab$ 삽입
이때
abab$
와 접두어가 공통되어 문자 분리
3. b$ 삽입
이때 bab$와 접두어가 공통되어 문자 분리
4. 마지막 $(터미널 문자) 삽입
종료 문자 삽입
5. 단말 노드 접미어 위치 삽입
문자열 순 인덱스 삽입
💬 접미어 배열
텍스트의 접미어들을 사전순으로 나열한 배열
접미어 트리보다 메모리 효율성 높지만 다소 느림
텍스트의 인덱싱, 데이터 압축등에 사용
공간 복잡도 : O(n)
시간 복잡도 : O(패턴 P + log n)
◾ 접미어 배열 생성
예시
b a n a n a &
💬 LCP 배열
접미어 배열의 보조적인 자료 구조
로 최장 공통 접두어(LCP) 배열
정렬된 접미어 배열
에서
연속적인 2개의 접미어들 사이의 최장 공통 접두어의 길이 저장
접미어 배열의 순회나 패턴 매칭
을 효율적으로 수행
예시
LCP[4]에서 ana$ 와 anana$ 의 공통 접두어는 ana가 됨
uuuouuo
팔로우
이전 포스트
Two Pointer
다음 포스트
Segment Tree
0개의 댓글
댓글 작성