[Advanced] 8. 문자열 탐색 - 이론편(3)

트라이 (trie)

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

• 각 간선은 하나의 문자에 대응
• 같은 노드에 나오는 간선들은 같은 라벨을 갖지 않음
• 각 문자열은 단말 노드에 대응

 

접미어 트라이

문자열의 모든 접미어를 트라이로 표현

길이가 n인 문자열의 접미어는 n개

 

접미어 트라이의 장점

• 부분 문자열 검사 - "ba"가 "abac"의 부분 문자열인가?
  

  

• 두 접미어의 최장 공통 접두어 찾기 - "abac"와 "ac"의 최장 공통 접두어는 무엇인가?
  
  • 두 접미어의 끝 글자에 해당하는 노드 선택
  • 가장 가까운 공통 조상 찾음
    

    

• 사전적 순서로 정렬된 k번째 접미어 찾기 - "abac"에서 사전적 순서로 3번째 접미어는 무엇인가?
  • 깊이 우선 탐색으로 문자열들을 생성하면 사전적 순서로 정렬
  • 생성된 문자열들을 메모리에 모두 저장하지 않고 인덱스 값만 저장
    

    

 

압축된 트라이

자식이 하나만 있는 노드들을 하나의 간선으로 묶어서 표현한 형태

 

 

접미어 트리

하나의 문자열의 모든 접미어들을 포함하는 트라이의 압축된 표현

문자열 연산에 필요한 알고리즘을 빠르게 구현 가능

접미어 트리의 응용

• 문자열 매칭
• 부분 문자열 매칭
• 최장 공통 부분 문자열

 

길이 s인 문자열 S의 접미어 트리의 속성

• 1부터 s까지 번호가 부여된 s개의 단말 노드를 가짐
• 루트를 제외한 내부 노드들은 최소 2개의 자식을 가짐
• 각 간선은 문자열 S의 부분 문자열 라벨이 부여됨
• 한 노드에서 나가는 두 개의 간선이 동일한 문자로 시작하는 문자열 라벨을 가질 수 없음
• 루트에서 단말 노드 i까지 경로에서 존재하는 문자열 라벨들을 연결한 문자열은 접미어 S[i ... s]

 

접미어 배열

텍스트의 접미어들을 사전식으로 나열한 배열(파이썬에서는 리스트)

접미어 트리보다 메모리를 좀 더 효율적으로 사용하지만 다소 느림

ex) s = abab / 접미어 사전순 정렬 : ab, abab, b, bab

 

접미어 배열의 복잡도

메모리 크기 O(n), 시간 복잡도 O(nlogn), 텍스트에 패턴 존재를 O(|P|+logn)시간에 계산 

 

접미어 배열의 생성

LCP 배열

접미어 배열의 보조적인 자료 구조로 최장 공통 접두어 배열(Longest Common Prefix) 생성

정렬된 접미어 배열에서 연속적인 2개의 접미어들 사이의 최장 공통 접두어의 길이 저장

접미어 배열의 순회나 패턴 매칭을 효율적으로 수행하는데 사용

 

데이터 압축

중복을 줄여 저장 공간을 절약하고 데이터 전송 시간을 절약하기 위함

 

데이터 압축 관련 용어들

인코딩 : 데이터 압축

디코딩 : 데이터 복구

압축률 : 원본 비트수 / 디코딩 후 비트수

 

RLE(Run Length Encoding)

동일한 값이 몇 번 반복되는가를 나타내는 방식
BMP 파일의 압축 방법으로 사용됨

Run = 반복되는 문자, Length = 반복 횟수

알고리즘

# MAXCOUNT = 255
def RLEncoding(data):
    if len(data) < 1:
        return ""
    elif len(data) == 1:
        return data[0] + "1"
        
    encode = ""
    count = 1
    for i in range(1, len(data)):
        if data[i-1] == data[i] and count<MAXCOUNT:
            count+=1
        else:
            encode += data[i-1] + str(count)
            count = 1
        if i == len(data)-1:
            return encode + data[i] + str(count)
            
def RLDecoding(data):
    for i in range(0, len(data), 2):
        for _ in range(int(data[i+1])):
            print(data[i], end="")

 

 

허프만 코드(Huffman Code)

기호의 빈도 : 전체 데이터 안에서 차지하는 기호의 비율

허프만 트리 : 각 기호에 이진 코드를 부여하기 위해 생성하는 이진 트리

 

고정길이코드 vs 접두어 코드

빈도수가 큰 'a'의 가변길이코드가 제일 짧다. 

 

허프만 코드의 생성

탐욕 기법에 의해 허프만 트리 생성

노드 규칙 - 단말노드 : 기호와 빈도를 저장 / 부모노드 : 빈도만 저장