문자열

문자의 표현

• 컴퓨터에서의 문자표현
  • 영어가 대소문자 합쳐서 52개 이므로 6비트(64가지)면 모두 표현할 수 있다. 이를 코드 체계라고 함
    • 000000 -> 'a', 000001 -> 'b'
• ASCII : 문자 인코딩 표준
• 유니코드 : 다국어 처리를 위한 표준

문자열비교

• c strcmp() 함수 제공
• 자바 equals() 메소드 제공
  • == 연산은 메모리 참조가 같은지 묻는 것
• 파이썬 ==연산자와 is연산자 제공
  • == 연산자는 내부적으로 특수 메서드 eq()를 호출

문자열 정수로 변환

• c atoi() 함수 제공 / 역은 itoa()
• 자바 숫자 클래스의 parse 메소드 제공
  • 예 : inetget.parselnt(string)
  • 역함수로는 toString() 메소드를 제공
• 파이썬 숫자와 문자 변환 함수 제공
  • int() / float() / str() / repr()

패턴 매칭

• 패턴 매칭에 사용되는 알고리즘들
  • 고지식한 패턴 검색 알고리즘
  • 카프 - 라인 알고리즘
  • KMP 알고리즘
  • 보이어 - 무어 알고리즘

고지식한 알고리즘

• 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작

p = 'ab'
t = 'aaaabaaaabaaaab'
M = len(p)
N = len(t)

def bf(p,t):
    i = 0
    j = 0
    while i < N and j < M:
        if t[i] != p[j]:
            i -= j
            j = -1
        i += 1
        j += 1
    if j == M : return i - M # 검색 성공
    else: # 검색 실패
        return 'Fail' 

print(bf(p,t)) # 3

def bf2(p,t,N,M):
    for i in range(N-M+1):
        for j in range(M):
            if t[i+j] != p[j]:
                break
        else: 
            return i

    return 'fail'

print(bf2(p,t,N,M)) # 3

• 고지식한 패턴 검색 알고리즘의 시간 복잡도
  • 최악의 경우 시간 복잡도는 텍스트의 모든 위치에서 패턴을 비교해야 하므로 O(MN)이 됨

KMP 알고리즘

• 불일치가 발생한 텍스트 스트링 앞부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행

• 패턴을 전처리하여 배열 next[M]을 구해서 잘못된 시작을 최소화함

  • next[M] : 불일치가 발생했을 경우 이동할 다음 위치

보이어-무어 알고리즘

• 오른쪽에서 왼쪽으로 비교
• 대부분의 상용 소프트웨어에서 채택하고 있는 알고리즘
• 보이어-무어 알고리즘은 패턴에 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우, 이동거리는 무려 패턴의 길이 만큼이 됨
• 시간 복잡도 : O(M+N)

문자열 암호화

시저암호

• 줄리어스 시저가 사용했다고 하는 암호이다
• 시저는 기원전 100년경에 로마에서 활약한 장군
• 시저 암호에서는 평문에서 사용되고 있는 알파벳을 일정한 문자 수 만큼 평행이동 시킴으로써 암호화

문자열 압축

• 저장소의 크기를 줄이며 정확한 정보를 저장하는 방법
  • Run-length encoding 알고리즘
  • 같은 값이 몇 번 반복되는가를 나타냄으로써 압축

    [A B B B B B B B B A] -> [A 1 B 8 A 1]

  • 이 방법은 이미지 파일 포맥 중 BMP 파일 포맥의 압축 방법
  • 많이 사용하는 압축 알고리즘으로 허프만 코딩 알고리즘이 있음