[알고리즘] Week 6: Suffix Array and Suffix Tree와 Burrows-Wheeler Transform

Day 1: Suffix Array

• 강의 내용:
  • Suffix Array의 개념
    • Suffix Array란 무엇인가?
    • Suffix Array의 특성과 응용 사례
  • Suffix Array의 기본 원리
    • 접미사 배열 (Suffix Array)의 생성 방법
    • 접미사 배열을 이용한 문자열 검색
  • 시간 복잡도 분석
    • Suffix Array의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 Suffix Array 생성 및 검색 예제

# Suffix Array 생성
def build_suffix_array(text):
    suffixes = [(text[i:], i) for i in range(len(text))]
    suffixes.sort()
    suffix_array = [suffix[1] for suffix in suffixes]
    return suffix_array

# 문자열 검색
def search(pattern, text, suffix_array):
    n = len(text)
    m = len(pattern)
    l, r = 0, n - 1
    while l <= r:
        mid = (l + r) // 2
        suffix = text[suffix_array[mid]:]
        if suffix.startswith(pattern):
            return suffix_array[mid]
        elif suffix > pattern:
            r = mid - 1
        else:
            l = mid + 1
    return -1

# 예제 실행
text = "banana"
pattern = "ana"
suffix_array = build_suffix_array(text)
print("Suffix Array:", suffix_array)
index = search(pattern, text, suffix_array)
print(f"패턴 '{pattern}'은(는) 인덱스 {index}에서 시작합니다.")  # Output: 1

 

Day 2: Suffix Tree

• 강의 내용:
  • Suffix Tree의 개념
    • Suffix Tree란 무엇인가?
    • Suffix Tree의 특성과 응용 사례
  • Suffix Tree의 기본 원리
    • 접미사 트리 (Suffix Tree)의 생성 방법
    • 접미사 트리를 이용한 문자열 검색
  • 시간 복잡도 분석
    • Suffix Tree의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 Suffix Tree 생성 및 검색 예제

# Suffix Tree 노드 정의
class SuffixTreeNode:
    def __init__(self):
        self.children = {}
        self.start = -1
        self.end = -1
        self.suffix_link = None

# Suffix Tree 생성
class SuffixTree:
    def __init__(self, text):
        self.text = text
        self.root = SuffixTreeNode()
        self.build_suffix_tree()

    def build_suffix_tree(self):
        n = len(self.text)
        active_node = self.root
        active_edge = -1
        active_length = 0
        remaining_suffix_count = 0
        leaf_end = -1

        for i in range(n):
            leaf_end = i
            remaining_suffix_count += 1
            last_new_node = None

            while remaining_suffix_count > 0:
                if active_length == 0:
                    active_edge = i

                if self.text[active_edge] not in active_node.children:
                    new_leaf_node = SuffixTreeNode()
                    active_node.children[self.text[active_edge]] = new_leaf_node
                    new_leaf_node.start = i
                    new_leaf_node.end = leaf_end

                    if last_new_node:
                        last_new_node.suffix_link = active_node
                        last_new_node = None
                else:
                    next_node = active_node.children[self.text[active_edge]]
                    edge_length = next_node.end - next_node.start + 1
                    if active_length >= edge_length:
                        active_edge += edge_length
                        active_length -= edge_length
                        active_node = next_node
                        continue

                    if self.text[next_node.start + active_length] == self.text[i]:
                        if last_new_node and active_node != self.root:
                            last_new_node.suffix_link = active_node
                            last_new_node = None
                        active_length += 1
                        break

                    split_node = SuffixTreeNode()
                    active_node.children[self.text[active_edge]] = split_node
                    split_node.start = next_node.start
                    split_node.end = next_node.start + active_length - 1

                    new_leaf_node = SuffixTreeNode()
                    split_node.children[self.text[i]] = new_leaf_node
                    new_leaf_node.start = i
                    new_leaf_node.end = leaf_end

                    next_node.start += active_length
                    split_node.children[self.text[next_node.start]] = next_node

                    if last_new_node:
                        last_new_node.suffix_link = split_node

                    last_new_node = split_node

                remaining_suffix_count -= 1
                if active_node == self.root and active_length > 0:
                    active_length -= 1
                    active_edge = i - remaining_suffix_count + 1
                elif active_node != self.root:
                    active_node = active_node.suffix_link

    def search(self, pattern):
        current_node = self.root
        i = 0
        while i < len(pattern):
            if pattern[i] in current_node.children:
                edge = current_node.children[pattern[i]]
                length = min(len(pattern) - i, edge.end - edge.start + 1)
                if pattern[i:i + length] != self.text[edge.start:edge.start + length]:
                    return -1
                i += length
                current_node = edge
            else:
                return -1
        return current_node.start

# 예제 실행
text = "banana"
pattern = "ana"
suffix_tree = SuffixTree(text)
index = suffix_tree.search(pattern)
print(f"패턴 '{pattern}'은(는) 인덱스 {index}에서 시작합니다.")  # Output: 1

 

Day 3: Burrows-Wheeler Transform (BWT)

• 강의 내용:
  • Burrows-Wheeler Transform의 개념
    • BWT란 무엇인가?
    • BWT의 특성과 응용 사례
  • BWT의 기본 원리
    • 문자열 변환 및 압축
    • BWT 생성 방법 및 역변환
  • 시간 복잡도 분석
    • BWT의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 BWT 생성 및 역변환 예제

# BWT 생성
def bwt_transform(text):
    n = len(text)
    rotations = [text[i:] + text[:i] for i in range(n)]
    rotations.sort()
    last_column = [rotation[-1] for rotation in rotations]
    return ''.join(last_column)

# BWT 역변환
def bwt_inverse(bwt):
    n = len(bwt)
    table = [""] * n
    for _ in range(n):
        table = sorted([bwt[i] + table[i] for i in range(n)])
    return [row for row in table if row.endswith('$')][0][:-1]

# 예제 실행
text = "banana$"
bwt = bwt_transform(text)
print("BWT 변환 결과:", bwt)  # Output: "annb$aa"
original_text = bwt_inverse(bwt)
print("BWT 역변환 결과:", original_text)  # Output: "banana"

 

Day 4: BWT 심화

• 강의 내용:
  • BWT의 응용
    • 문자열 압축 및 검색
    • BWT를 이용한 데이터 압축 알고리즘 (예: Bzip2)
  • 고급 BWT 알고리즘
    • 고차원 문자열 변환 및 압축
  • 시간 복잡도 분석
    • 고급 알고리즘의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 고급 BWT 알고리즘 예제

# BWT 기반 압축 예제
import bz2

def bwt_compress(text):
    bwt = bwt_transform(text)
    compressed = bz2.compress(bwt.encode())
    return compressed

def bwt_decompress(compressed):
    decompressed = bz2.decompress(compressed).decode()
    return bwt_inverse(decompressed)

# 예제 실행
text = "banana$"
compressed = bwt_compress(text)
print("압축된 데이터:", compressed)
decompressed = bwt_decompress(compressed)
print("압축 해제된 데이터:", decompressed)  # Output: "banana"

 

Day 5: 고급 문자열 알고리즘 종합 연습

• 강의 내용:
  • 종합 연습 문제 풀이
    • Suffix Array, Suffix Tree, BWT 문제 해결
  • 고급 문자열 알고리즘의 응용
    • 다양한 실생활 문제에서의 응용 사례
• 실습:
  • 종합 연습 문제 해결 및 결과 분석

### 종합 연습 문제 예시
1. 주어진 문자열에서 Suffix Array를 생성하고 패턴을 검색하세요.
2. 주어진 문자열에서 Suffix Tree를 생성하고 패턴을 검색하세요.
3. 주어진 문자열을 BWT 변환하고 역변환을 수행하세요.

 

Day 6: 프로젝트 준비

• 강의 내용:
  • 프로젝트 주제 선정 및 요구사항 분석
    • 프로젝트 주제 및 요구사항 확정
    • 프로젝트 설계 및 계획 수립
  • 프로젝트 구현 준비
    • 데이터 구조 및 알고리즘 설계
    • 프로젝트 팀 구성 및 역할 분담
• 실습:
  • 프로젝트 주제 및 요구사항 분석
  • 프로젝트 설계 및 계획 수립

### 프로젝트 주제 예시
1. 대규모 텍스트 데이터 검색 및 압축 시스템 개발
2. 실시간 문자열 분석 및 변환 시스템

### 프로젝트 요구사항 예시
1. 대규모 텍스트 데이터 검색 및 압축 시스템:
   - 텍스트 데이터셋 입력 및 저장
   - Suffix Array, Suffix Tree, BWT를 통한 검색 및 압축
   - 검색 및 압축 결과 출력 및 성능 분석

2. 실시간 문자열 분석 및 변환 시스템:
   - 문자열 데이터 입력 및 저장
   - 고급 문자열 알고리즘을 통한 분석 및 변환
   - 분석 및 변환 결과 출력 및 성능 분석

### 프로젝트 설계 및 계획 예시
1. 데이터 입력 모듈 구현
2. 문자열 알고리즘 구현 (Suffix Array, Suffix Tree, BWT 등)
3. 데이터 출력 및 성능 분석 모듈 구현

 

이 강의는 파이썬의 고급 문자열 알고리즘, 특히 Suffix Array, Suffix Tree, Burrows-Wheeler Transform의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!