02. 문자열 (string)

문자열 (string)

  • 문자열

  • 패턴 매칭

  • 문자열 암호화

  • 문자열 압축

2.1 문자의 표현

컴퓨터에서의 문자 표현

  • 글자 A를 메모리에 저장하는 방법에 대해서 생각해보자.

  • 물론 칼로 A라는 글자를 새기는 방식은 아닐 것이다. 메모리는 숫자만을 저장할 수 있기 때문에 A라는 글자의 모양 그대로 비트맵으로 저장하는 방법을 사용하지 않는 한 (이 방법은 메모리 낭비가 심하다.) 각 문자에 대해서 대응되는 숫자를 정해 놓고 이것을 메모리에 저장하는 방법이 사용될 것이다.

  • 영어가 대소문자 합쳐서 52이므로 6(64가지)비트면 모두 표현할 수 있다. 이를 코드체계라고 한다.

    • 000000 → 'a', 000001 → 'b'

  • 그런데 네트워크가 발전되기 전 미국의 각 지역 별로 코드체계를 정해 놓고 사용했지만

  • 네트워크(인터넷: 인터넷은 미국에서 발전했다.)가 발전하면서 서로 간에 정보를 주고 받을 때 정보를 달리 해석한다는 문제가 생겼다.

    image-20210813090721360

  • 그래서 혼동을 피하기 위해 표준안을 만들기로 했다.

  • 바로 이러한 목적으로 1967년, 미국에서 ASCII(American Standard Code for Information Interchange)라는 문자 인코딩 표준이 제정되었다.

  • ASCII는 7bit 인코딩으로 128문자를 표현하며 33개의 출력 불가능한 제어 문자들과 공백을 비롯한 95개의 출력 가능한 문자들로 이루어져 있다.

  • 출력 가능 아스키 문자 (32 ~ 126)

    image-20210813091009601

  • 확장 아스키는 표준 문자 이외의 악센트 문자, 도형 문자, 특수 문자, 특수 기호 등 부가적인 문자를 128개 추가할 수 있게 하는 부호이다.

    • 표준 아스키는 7bit를 사용하여 문자를 표현하는 데 비해 확장 아스키는 1B 내의 8bit를 모두 사용함으로써 추가적인 문자를 표현할 수 있다.

    • 컴퓨터 생산자와 소프트웨어 개발자가 여러 가지 다양한 문자에 할당할 수 있도록 하고 있다. 이렇게 할당한 확장 부호는 표준 아스키와 같이 서로 다른 프로그램이나 컴퓨터 사이에 교환되지 못한다.

    • 그러므로 표준 아스키는 마이크로컴퓨터 하드웨어 및 소프트웨어 사이에서 세계적으로 통용되는 데 비해, 확장 아스키는 픙로그램이나 컴퓨터 또는 프린터가 그것을 해독할 수 있도록 설계되어 있어야만 올바로 해독될 수 있다.

  • 확장 아스키 예

    img

  • 오늘날 대부분의 컴퓨터는 문자를 읽고 쓰는데 ASCII 형식을 사용한다.

  • 그런데 컴퓨터가 발전하면서 미국 뿐 아니라 각 나라에서도 컴퓨터가 발전했으며 각 국가들은 자국의 문자를 표현하기 위하여 코드체계를 만들어서 사용하게 되었다.

    • 우리나라도 아주 오래된 이야기지만 한글 코드체계를 만들어 사용했고 조합형, 완성형 두 종류를 가지고 있었다.

  • 인터넷이 전 세계로 발전하면서 ASCII를 만들었을 때의 문제와 같은 문제가 국가간에 정보를 주고 받을 때 발생했다.

  • 자국의 코드체계를 타 국가가 가지고 있지 않으면 정보를 잘못 해석할 수 밖에 없었다.

  • 그래서 다국어 처리를 위해 표준을 마련했다. 이를 유니코드라고 한다.

img

  • 유니코드도 다시 Character Set으로 분류된다.

    • UCS-2 (Universal Character Set 2)

    • UCS-4 (Universal Character Set 4)

    • 유니코드를 저장하는 변수의 크기를 정의

    • 그러나, 바이트 순서에 대해서 표준화하지 못했음.

    • 다시 말해 파일을 인식 시 이 파일이 UCS-2, UCS-4인지 인식하고 각 경우를 구분해서 모두 다르게 구현해야 하는 문제 발생

    • 그래서 유니 코드의 적당한 외부 인코딩이 필요하게 되었다.

  • big-endian, little-endian

    • 바이트 순서가 표준화되지 않아 서로 해석이 되지 않음.

    image-20210813100941329

  • 유니코드 인코딩 (UTF: Unicode Transformation Format)

    • UTF-8 (in web)

      • MIN : 8bit, MAX: 32bit (1 Byte * 4)

    • UTF-16 (in windows, java)

      • MIN : 16bit, MAX: 32bit(2 Byte * 2)

    • UTF-32 (in unix)

      • MIN : 32bit, MAX: 32bit(4 Byte * 1)

  • Python 인코딩

    • 2.x 버전 - ASCII → #-*- coding: utf-8 -*- (첫 줄에 명시)

    • 3.x 버전 - 유니코드 UTF-8 → 생략 가능

    • 다른 인코딩 방식으로 처리 시 첫 줄에 작성하는 위 항목에 원하는 인코딩 방식을 지정해주면 됨.

2.2 문자열

  • 문자열의 문류

    image-20210813101323100

  • java에서 String 클래스에 대한 메모리 배치 예

    • 그림에서 보이듯, java.lang.String 클래스에는 기본적인 객체 메타 데이터 외에도 네 가지 필드들이 포함되어 있는데, hash값(hash), 문자열의 길이(count), 문자열 데이터의 시작점(offset), 그리고 실제 문자열 배열에 대한 참조(value)이다.

    image-20210813101440154

  • C언어에서 문자열 처리

    • 문자열은 문자들의 배열 형태로 구현된 응용 자료형

    • 문자배열에 문자열을 저장할 때는 항상 마지막에 끝을 표시하는 널문자(\0)를 넣어줘야 한다.

      char ary[]={'a', 'b', 'c', '\0'}; // 또는 char ary[]="abc";
      
    • 문자열 처리에 필요한 연산을 함수 형태로 제공한다.

      strlen(), strcpy(), strcmp(), ...
      
  • Java(객체지향 언어)에서의 문자열 처리

    • 문자열 데이터를 저장, 처리해주는 클래스를 제공한다.

    • String 클래스를 사용한다.

      String str="abc"; // 또는 String str = new String("abc")
      
    • 문자열 처리에 필요한 연산을 연산자, 메소드 형태로 제공한다.

      • +, length(), replace(), split(), substring(), …

      • 보다 풍부한 연산을 제공한다.

  • Python에서의 문자열 처리

    • char 타입 없음

    • 텍스트 데이터의 취급방법이 통일되어 있음

    • 문자열 기호

      • '(홑따옴표), "(쌍따옴표), '''(홑따옴표 3개), """(쌍따옴표 3개)

      • + 연결 (Concatenation) : 문자열 + 문자열 (이어 붙여주는 역할)

      • * 반복 : 문자열 * 수 (수 만큼 문자열이 반복)

    • 문자열은 시퀀스 자료형으로 분류되고, 시퀀스 자료형에서 사용할 수 있는 인덱싱, 슬리이싱 연산들을 사용할 수 있음

    • 문자열 클래스에서 제공되는 메서드

      replace(), split(), isalpha(), find()
      
    • 문자열은 튜플과 같이 요소값을 변경할 수 없음 (immutable)

      • replace()는 지정한 문자열을 대체한 새로운 문자열을 만들어 리턴해주는 메서드

  • C와 Java의 String 처리의 기본적인 차이점

    • C는 아스키 코드로 저장한다.

    • java는 유니코드(UTF-16, 2byte)로 저장한다.

    • 파이썬은 유니코드(UTF-8)로 저장

    // C
    char * name = "홍길동";
    int count = strlen(name);
    printf("%d", count);  // 6이 출력된다. (메모리 상에서 사용한 바이트 수)
    
    // java
    String name = "홍길동";
    System.out.pringln(name.length());  // 3이 출력된다.
    
    # python
    name = "홍길동"
    print(len(name))  # 3이 출력된다.
    

2.3 문자열 뒤집기

  • 자기 문자열에서 뒤집는 방법이 있고 새로운 빈 문자열을 만들어 소스의 뒤에서부터 읽어서 타겟에 쓰는 방법이 있겠다.

  • 자기 문자열을 이용할 경우는 swap을 위한 임시 변수가 필요하며 반복 수행을 문자열 길이의 반만을 수행해야 한다.

    image-20210813102820623

연습문제 1

  • C에서는 앞의 알고리즘 대로 구현해야 한다.

  • java에서는 StringBuffer 클래스의 reverse() 메소드를 이용하면 된다.

  • Python은 Reverse 함수 혹은 slice notation을 이용하여 구현하면 된다.

    s = 'Reverse this strings'
    s = s[::-1]
    print(s)
    
  • 구현해봅시다.

    s = list(input())
    n = len(s)  # 글자수
    for i in range(n//2):
        s[i], s[n-1-i] = s[n-1-i], s[i]
    print(s)
    

2.4 문자열 비교

  • C : strcmp() 함수를 제공한다.

    int my_strcmp(const char *str1, const char *str2)
    {
        int i = 0;
        while(str1[i] != '\0')
        {
            if(str1[i] != str2[i]) break;
            i++;
        }
        return (str1[i] - str2[i]);
    }
    
  • Java에서는 equals() 메소드를 제공한다.

    • 문자열 비교에서 == 연산은 메모리 참조가 같은지를 묻는 것

  • 파이썬에서는 == 연산자와 is 연산자를 제공한다.

    • == 연산자는 내부적으로 특수 메서드 __eq__()를 호출

문자열 숫자를 정수로 변환하기

  • C 언어에서는 atoi() 함수를 제공한다. 역 함수로는 itoa()가 있다.

    int atoi(const char *string)
    {
        int value = 0, digit, c;
        
        while ((c = *string++) != '\0') {
          	if (c >= '0' && c <= '9')
                digit = c - '0';
            else
                break;
            
            value = (value * 10) + digit;
        }
        return value
    }
    
  • java에서는 숫자 클래스의 parse 메서드를 제공한다.

    • Integer.parseInt(String)

    • 역함수로는 toString() 메서드를 제공한다.

  • 파이썬에서는 숫자와 문자변환 함수를 제공한다.

    • int('123'), float('3.14'), str(123), repr(123)

연습문제 2

  • str() 함수를 사용하지 않고, itoa()를 구현해 봅시다.

    • 양의 정수를 입력 받아 문자열로 변환하는 함수

    • 입력 값 : 변환할 정수 값, 변환될 문자열을 저장할 문자 배열

    • 반환 값 : 없음

  • 음수를 변환할 때는 어떤 고려 사항이 필요한가요?

2.5 패턴 매칭

패턴 매칭에 사용되는 알고리즘들

  • 고지식한 패턴 검색 알고리즘

  • 카프-라빈 알고리즘

  • KMP 알고리즘

  • 보이어-무어 알고리즘

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

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

    image-20210813140601176

    p = 'is'  # 찾을 패턴
    t = 'Tis 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:
            if t[i] != p[j]:
                i -= j
                j = -1
            i += 1
            j += 1
        if j == M:
            return i - M
        else:
            return -1
    
    def BruteForce(p, t):
        i = 0  # t의 인덱스
        j = 0  # p의 인덱스
        for i in range(N-M):
            for j in range(M):
                if p[j] != t[i+j]:
                    break
                if j = M-1
                    return i
            return -1
    
  • 고지식한 패턴 검색 알고리즘의 시간 복잡도

    • 최악의 경우 시간 복잡도는 텍스트의 모든 위치에서 패턴을 비교해야 하므로 \(O(MN)\)이 됨

    • 예에서는 최악의 경우 약 \(10,000 \times 80 = 800,000\) 번의 비교가 일어난다.

    • 비교 횟수를 줄일 수 있는 방법은 없는가?

KMP 알고리즘

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

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

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

  • 시간 복잡도 : O(M+N)

  • 아이디어 설명

    • 텍스트에서 abcdabc까지는 매치되고, e에서 실패한 상황 패턴의 맨 앞의 abc와 실패 직전의 abc는 동일함을 이용할 수 있다.

    • 실패한 텍스트 문자와 P[4]를 비교한다.

    image-20210813141621313

    • 매칭이 실패했을 때 돌아갈 곳을 계산한다.

      image-20210813141649511

next = [0] * M
cnt = 0  # 일치한 개수
i = 1

while i < M:
    if p[i] == p[cnt]:
        cnt += 1
        next[i] = cnt
        i += 1
    else:
        if cnt != 0:
            cnt = next[cnt-1]
        else:
            next[i] = 0
            i += 1

보이어-무어 알고리즘

  • 오른쪽에서 왼쪽으로 비교

  • 대부분의 상용 소프트웨어에서 채택하고 있는 알고리즘

  • 보이어-무어 알고리즘은 패턴에 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우, 이동 거리는 무려 패턴의 길이 만큼이 된다.

image-20210813142653969

  • 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재할 경우

image-20210813142835238

  • 보이어-무어 알고리즘을 이용한 예

image-20210813142903560

  • rithm 문자열의 skip 배열

m

h

t

i

r

다른 모든 문자

0

1

2

3

4

5

  • 문자열 매칭 알고리즘 비교

    • 찾고자 하는 문자열 패턴의 길이 m, 총 문자열 길이 n

    • 고지식한 패턴 검색 알고리즘 : \(O(mn)\)

    • 카프-라빈 알고리즘 : \(\theta(n)\)

    • KMP 알고리즘 : \(\theta(n)\)

    • 보이어-무어 알고리즘

      • 앞의 두 매칭 알고리즘들의 공통점은 텍스트 문자열의 문자를 적어도 한번씩 훑는다는 것이다. 따라서 최선의 경우에도 \(\Omega(n)\)​​

      • 보이어-무어 알고리즘은 텍스트 문자를 다 보지 않아도 된다.

      • 발상의 전환 : 패턴의 오른쪽부터 비교한다.

      • 최악의 경우 수행시간 : \(\theta(mn)\)

      • 입력에 따라 다르지만 일반적으로 \(\theta(n)\)​보다 시간이 덜 든다.

연습문제 3

  • 고지식한 방법을 이용하여 패턴을 찾아 봅시다.

  • 임의의 본문 문자열과 찾을 패턴 문자열을 만듭니다.

  • 결과 값으로 찾은 위치 값을 결과로 출력합니다.

참고: 문자열 암호화

시저 암호 (Caesar cipher)

  • 줄리어스 시저가 사용했다고 하는 암호이다.

  • 시저는 기원전 100년경에 로마에서 활약했던 장군이었다.

  • 시저 암호에서는 평문에서 사용되고 있는 알파벳을 일정한 문자 수만큼 [평행이동] 시킴으로써 암호화를 행한다.

    Caesar cipher - Wikipedia

  • 1만큼 평행했다는 카이사르 암호화의 예

    평문

    S

    A

    V

    E

    P

    R

    I

    V

    A

    T

    E

    R

    Y

    A

    N

    암호문

    T

    B

    W

    F

    A

    Q

    S

    J

    W

    B

    U

    F

    A

    S

    Z

    B

    O

  • 1만큼 평행했을 때 1을 키값이라 한다.

  • 수신자 이외의 사람 (키가 1이라는 사실을 모르는 사람)이 암호문 TBWFAQSJWBUFASZBO을 보고 다른 정보 없이도 SAVE PRIVATE RYAN 라는 메시지를 맞출 수는 없을까?

  • 다시 말해, 시저 암호를 해독할 수 있을까?

  • 시저 암호문에 대한 전사 공격

    image-20210813151901685

  • 문자 변환표를 이용한 암호화 (단일 치환 암호)

    • 단순한 카이사르 암호화보다 훨씬 강력한 암호화 기법

    image-20210813152003097

  • 단일 치환 암호의 복호화

    • 복호화 하기 위해서는 모든 키의 조합 (key space)가 필요하다.

  • 단일 치환 암호의 키의 총수는

    • \(26 \times 25 \times 24 \times 23 \times \dots \times 1 = 26! = 403291461126605635584000000\)

  • 1초에 10억 개의 키를 적용하는 속도로 조사한다고 해도, 모든 키를 조사하는데 120억년 이상의 시간이 걸린다. 방법이 없을까?

    • 있다! 관심 있으면 찾아보길…

  • bit열의 암호화

    • 배타적 논리합(exclusive-or) 연산 사용

    image-20210813152350170

참고 : 문자열 압축

  • 다음과 같은 문자열이 있다. 저장소의 크기를 줄이며 정확한 정보를 저장하는 방법은?

    • Run-length encoding 알고리즘

    • 같은 값이 몇 번 반복되는가를 나타냄으로써 압축

    image-20210813152500022

    • 이 방법은 이미지 파일포맷 중 BMP 파일포맷의 압축 방법이다.

    • 좀 더 효율적이고 일반적인 압축 방법은 없는가?

      • 있다. 많이 사용하는 알고리즘으로 허프만 코딩 알고리즘이 있다.