[Algorithm] 문자열 알고리즘

TOC

• 패턴 매칭
• 고지식한 알고리즘(Brute Force)
  • 코드로 표현
• KMP 알고리즘
  • 로직
• 보이어-무어 알고리즘
• 문자열 매칭 알고리즘 비교
  • 보이어-무어 알고리즘
  • 추가 기호
• 문자열 암호화
  • 시저 암호(Caesar cipher)
  • 단일 치환 암호
  • bit열의 암호화
• 문자열 압축
  • BMP 파일 포맷 방식

패턴 매칭

• 텍스트(text)에서 패턴(pattern)이 포함된 모든 위치를 찾는 문제
• 텍스트는 긴 문자열, 패턴은 짧은 문자열

고지식한 알고리즘(Brute Force)

• 문자열을 처음부터 끝까지 차례로 순회
• 패턴 내의 문자들을 일일이 비교
• 최악의 경우 두 비교군의 모든 패턴을 비교. O(MN)

코드로 표현

p = "is"                       # 찾을 패턴
t = "This is a book~!"         # 전체 텍스트
M = len(p)                     # 찾을 패턴 길이
N = len(t)                     # 전체 텍스트 길이

def BruteForce(p, t):
    i = 0                      # t의 인덱스
    j = 0                      # p의 인덱스
    while j < M and i < N:     # j가 M보다 작고 i가 N보다 작은동안
        if t[i] != p[j]:       # 어떤 포인트와 포인트가 같지 않다면
            i = i - j          # 텍스트의 참조 위치 초기화(바로 뒤에서 i-j+1이 됨, 이전 조회 시작 위치+1)
            j = -1             # 패턴의 참조위치 -1으로 초기화(바로 뒤에서 0 됨)
        i = i + 1              # 일치하고 있었다면 조회 위치를 다음으로 넘김, 아니었다면 i=i-j+1, j=0
        j = j + 1
    if j == M:                 # j가 M, 즉 패턴이 전부 텍스트 내에 있으면
        return i - M           # 검색 성공; (시작 인덱스+패턴길이)에서 패턴길이 뺀, 즉 시작 인덱스 반환
    else:
        return -1              # 검색 실패

KMP 알고리즘

• 불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있다.
• 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭 수행
• 패턴을 전처리(배열 next[M]) → 잘못된 시작을 최소화
• 시간 복잡도 : O(M+N)

로직

생략

보이어-무어 알고리즘

• 오른쪽에서 왼쪽으로 비교
• 대부분의 상용 소프트웨어에서 채택하고 있는 알고리즘
• 오른쪽 끝에 있는 문자가 불일치 & 문자가 패턴 내에 존재 X 한다면, 패턴의 길이만큼 이동
• 오른쪽 끝에 있는 문자가 불일치 & 문자가 패턴 내에 존재 → 일치하는 패턴까지 단번에 이동

문자열 매칭 알고리즘 비교

• 찾고자하는 문자열 패턴의 길이 m, 총 문자열 길이 n일 때
• 고지식한 패턴 검색 알고리즘 : O(m*n)
• 카프 라빈 알고리즘 : O(n)
• KMP 알고리즘 : O(n)

보이어-무어 알고리즘

• 앞의 두 매칭 알고리즘들의 공통점 : 문저를 적어도 한 번씩 훑는다 → 최선의 경우에도 Ω(n)
• 보이어-무어 알고리즘은 텍스트 문자를 다 보지 않아도 된다.
• 발상의 전환 : 패턴의 오른쪽부터 비교
• 최악의 경우 수행시간 : Θ(mn)
• 입력에 따라 다르지만 일반적으로 Θ(n)보다 시간이 덜 든다.

추가 기호

O(n) : 최악의 경우 Θ(n) : 최악의 경우와 최선의 경우가 같은 증가율일 때 일반적으로 라는 의미 Ω(n) : 잘 해봐야 이정도라는 의미!

문자열 암호화

시저 암호(Caesar cipher)

• 줄리어스 시저가 사용했다는 암호
• 알파벳을 일정한 문자 수만큼 평행이동
• 모든 알파벳을 무차별적으로 밀어보는 전사공격에 취약

단일 치환 암호

• 문자 변환표를 이용한 암호화
• 시저 암호화보다 강력
• 알파벳마다 불규칙적인 다른 알파벳과 매칭
• 복호화를 위해서는 모든 키의 조합(key space)가 필요

bit열의 암호화

• 배타적 논리합(exclusive-or) 연산 사용
• 0과 1의 불규칙적인 나열로 된 암호키를 사용
• 평문도 비트로 변환하여 암호키와 exclusive-or 처리
• 복호화는 암호문을 다시 암호키와 exclusive-or 처리

문자열 압축

BMP 파일 포맷 방식

• 같은 값이 몇 번 반복되는가를 나타냄
• ABBBBBBBBA → A1B8A1
• Run-length encoding 알고리즘