이번 글에서는 순서통계량(order statistic)을 구현하는 알고리즘을 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 참고해 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.

concepts

순서통계량이란 $n$개 표본의 측정값들을 그 크기 순으로 작은 쪽부터 배열한 것을 가리킵니다. 최소값, 최대값, 중앙값(median), 4분위수(quantile) 등이 대표적인 순서통계량입니다. $i$번째 순서통계량은 $n$개 요소 가운데 $i$번째로 작은 값을 가리킵니다. 따라서 최소값은 $i$가 1, 최대값은 $i$가 $n$이 됩니다. $n$이 홀수인 경우에 중앙값의 $i$는 $(n+1)/2$, 짝수인 경우 $n/2$입니다.

순서통계량을 가장 확실하게 구하는 방법은 모든 요소를 정렬하는 것입니다. 카운팅 정렬(counting sort) 같은 일부 특이한 알고리즘을 제외하면, 대부분의 정렬 알고리즘은 두 값을 반복적으로 비교해 정렬 작업을 수행하는 comparison sort입니다. comparison sort 계산복잡성의 하한은 $O(n\log{n})$입니다. (자세한 내용은 이곳 참고) 다시 말해 힙 정렬이나 합병 정렬 같은 $O(n\log{n})$의 알고리즘으로 전체 요소를 정렬해 놓으면 순서통계량 또한 구할 수 있다는 이야기입니다.

하지만 최소값, 최대값, 중앙값만을 알고자 할 때 요소 전체를 정렬할 필요까지는 없습니다. 바꿔 말해 순서통계량을 구하는 알고리즘이 목표로 하는 계산복잡성은 $O(n)$이라는 것입니다.

최대값(최소값)

최대값을 구하는 가장 간단한 알고리즘은 이렇습니다. 우선 max라는 변수를 만들고, 이 변수에 첫번째 표본의 값을 집어 넣습니다. 그리고 나머지 $n-1$개 표본과 max 변수값을 반복적으로 비교해 큰 값을 다시 max에 저장합니다. 따라서 $n-1$회 비교하게 되면 $n$개 표본 가운데 최대값을 뽑아낼 수 있습니다. 따라서 이 알고리즘의 계산복잡성은 $O(n)$이 됩니다. 최소값은 여기에서 작은 값을 취하는 것 말고는 동일한 과정을 거칩니다.

파이썬으로 구현한 코드는 다음과 같습니다.

def maximum(list):
    max = list[0]
    for i in list:
        if max < i:
            max = i
    return max

최대값과 최소값 동시에 구하기

최대값을 구하는 데 $n-1$회, 최소값을 구하는 데에도 $n-1$회 비교 연산을 수행해야 합니다. 따라서 최대값과 최소값을 동시에 구하려면 $2n-2$회 비교를 해야 합니다. 이보다 더 낮출 수는 없을까요? 방법이 있습니다. 예컨대 다음과 같은 리스트를 정렬한다고 칩시다.

[1, 4, 10, 6, 3, 2]

우선 출력변수 result를 초기화합니다. result 첫번째 요소엔 최소값, 두번째 요소엔 최대값을 저장할 예정입니다.

result=(False, False)

정렬 대상 숫자를 순서대로 두 개씩 묶어 소그룹으로 만든 다음 두 개 숫자를 비교합니다. 큰 값을 왼쪽에, 작은 값을 오른쪽에 둡니다.

compare [1, 4] ==> [1, 4]

compare [10, 6] ==> [6, 10]

compare [3, 2] ==> [2, 3]

첫번째 소그룹의 왼쪽 값을 result 첫번째 요소, 오른쪽 값을 두번째 요소에 저장합니다.

result=(1, 4)

두번째 소그룹의 왼쪽 값(6), result의 기존 왼쪽 값(1)을 비교합니다. 작은 값을 result의 왼쪽에 저장합니다. 두번째 소그룹의 오른쪽 값(10), result의 기존 오른쪽 값(4)을 비교합니다. 큰 값을 result의 오른쪽에 저장합니다.

$\min(1,6)$, $max(4,10)$

result=(1,10)

마지막으로 세번째 소그룹의 왼쪽 값(2), result의 기존 왼쪽 값(1)을 비교합니다. 작은 값을 result의 왼쪽에 저장합니다. 세번째 소그룹의 오른쪽 값(3), result의 기존 오른쪽 값(4)을 비교합니다. 큰 값을 result의 오른쪽에 저장합니다.

$\min(1,2)$, $max(10,3)$

result=(1,10)

위 방법의 계산복잡성은 다음과 같은 세 가지 단계로 나누어 생각해볼 수 있습니다.

1. 두 개 숫자씩 소그룹으로 나누고 두 숫자 비교
2. 최소값 찾기 : 소그룹의 왼쪽값과 result의 왼쪽값 비교
3. 최대값 찾기 : 소그룹의 오른쪽값과 result의 오른쪽값 비교

데이터가 $n$개 있을 때 1번 과정에서 비교 연산의 횟수는 $n/2$회입니다. 2번 과정과 3번 과정도 각각 $n/2$회가 됩니다. 따라서 전체적으로는 $1.5n$회 비교 연산을 수행하면 됩니다. 기존 $2n-2$회에서 그 연산의 횟수를 줄인 셈입니다. (물론 Big-O notation 상으로는 둘 모두 $O(n)$으로 같습니다)

i번째 작은 값 구하기

$n$개의 숫자 가운데 $i$번째 작은 값은 퀵 정렬(quick sort)을 활용해 효과적으로 구할 수 있습니다. 퀵 정렬은 분기의 기준이 되는 피봇(pivot)값 $k$를 기준으로 작은 값들은 왼쪽, 큰 값들은 오른쪽 리스트로 분기합니다. 이후 분기된 두 리스트 각각에 퀵 정렬을 재귀적으로 수행해 정렬을 완료하는 구조입니다.

그러면 분석 대상 리스트가 $n$개 숫자로 구성돼 있고 피봇보다 큰 값들이 $a$개, 작은 값들이 $b$개라고 칩시다. 우리는 정렬이 아니라 $i$번째 작은 값을 찾는 데에만 관심이 있으므로, $a$가 $i$보다 크다면 $b$개에 대해선 계산할 필요가 전혀 없습니다. 다시 말해 피봇값 $k$보다 작은 값들의 개수($a$)가 $i$개 이상이라면 우리가 찾는 $i$번째 작은 값은 이들 중 하나일 것입니다. 따라서 $k$보다 큰 $b$개의 숫자에 대해선 계산하지 않아도 됩니다.

이를 파이썬으로 구현한 코드는 다음과 같습니다.

# i번째(query) 작은 숫자 찾기
def select(ARRAY, query):
    # query가 ARRAY의 수보다 크면 에러 출력
    if query > len(ARRAY):
        print('query error')
    else:
        ARRAY_LENGTH = len(ARRAY)
        if ARRAY_LENGTH <= 1:
            return ARRAY[0]
        else:
            # 피봇을 기준으로 기존 리스트 분리
            LESSOR, PIVOT, GREATER = partition(ARRAY)
            # query가 LESSOR 다음 index와 일치하면
            # i번째 작은 숫자는 바로 피봇값
            if query == len(LESSOR):
                return PIVOT
            # query가 LESSOR 개수보다 작으면
            # GREATER는 버리고 LESSOR 안에서만 탐색
            elif query < len(LESSOR):
                return select(LESSOR, query)
            # query가 LESSOR 개수보다 크면
            # LESSOR는 버리고 GREATER 안에서만 탐색
            else:
                return select(GREATER, query)

# quick_sort algorithm 일부 변경
def partition(ARRAY):
    ARRAY_LENGTH = len(ARRAY)
    if ARRAY_LENGTH <= 1:
        return ARRAY
    else:
        # 피봇은 입력데이터의 마지막 요소
        PIVOT = ARRAY[-1]
        GREATER = [ element for element in ARRAY[:-1] if element > PIVOT ]
        LESSER = [ element for element in ARRAY[:-1] if element <= PIVOT ]
        return LESSER, PIVOT, GREATER

정렬 대상 리스트가 $n$개 숫자이고 피봇보다 큰 값들이 $a$개, 작은 값들이 $b$개라면 퀵 정렬의 계산복잡성은 다음과 같이 쓸 수 있습니다.

[T\left( n \right) =T\left( a \right) +T\left( b \right) +O\left( n \right)]

위 식 우변 마지막 항이 $O(n)$이 되는 이유는 피봇값 $k$와 리스트의 나머지 $n-1$개 요소 간 비교 연산을 수행해야 하기 때문입니다. 그런데 우리는 정렬이 목표가 아니므로 $k$보다 큰 $b$개의 숫자에 대해선 계산하지 않아도 됩니다. 따라서 $i$번째 작은 값을 구하는 알고리즘의 계산복잡성은 다음과 같이 쓸 수 있습니다.

[T\left( n \right) =T\left( a \right) +O\left( n \right)]

이 알고리즘의 계산복잡성은 피봇을 어떻게 선택하느냐에 따라 달라집니다. 피봇값을 잘못 선택해 매 분기 때마다 아래 그림처럼 이뤄질 경우 각 층에서 피봇값과 리스트의 나머지 요소($k$번 분기시 $n-k$번) 간 비교연산을 수행하고, 이를 높이($n$)만큼 반복 수행해야 하므로 $O(n^2)$의 계산복잡성을 가지게 됩니다.

반대로 피봇을 잘 선택해 매번 분기 때마다 절반씩 나눌 수 있게 되면 $i$번째 작은 값을 구하는 알고리즘의 계산복잡성은 $O(n)$이 됩니다. 아래 점화식 형태의 계산복잡성 식이 $O(n)$이 되는 이유에 대해서는 이곳을 참고하시면 좋을 것 같습니다.

[T\left( n \right) =T\left( n/2 \right) +O\left( n \right) \ \Rightarrow O\left( n \right)]

pivot을 적절히 선택하기

따라서 $i$번째 작은 값을 찾는 문제를 선형 시간 내에 풀려면 피봇을 적절히 선택해 주어야 합니다. 이와 관련해 아래 그림 같은 아이디어도 있습니다. 방법은 이렇습니다. 전체 데이터를 몇 개 그룹으로 나눕니다. 해당 그룹에서 중앙값을 찾습니다. 여기서 다시 중앙값을 택합니다. 이를 피봇 삼아 분기를 수행하는 것입니다.

이번 글에서는 요소값을 명시적으로 비교하지 않아도 정렬할 수 있는 기법인 카운팅 정렬(counting sort)과 래딕스 정렬(Radix sort)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아, 그리고 이곳을 참고해 정리하였음을 먼저 밝힙니다. 파이썬 코드는 이곳을 참고로 하였습니다. 그럼 시작하겠습니다.

comparison sort

두 개 요소값을 반복적으로 비교하여 정렬을 수행하는 알고리즘을 comparison sort라고 합니다. 이는 Decision tree 모델로도 불립니다. 정렬 대상 숫자가 세 개인 경우를 예로 들어보겠습니다. 아래 그림과 같습니다.

위 트리를 보면 3개 숫자를 정렬하는 데 가능한 경우의 수는 6개($3!$)입니다. 각 경우의 수가 트리의 말단노드(leaf)가 됩니다. 트리의 루트노드에서 말단노드까지의 엣지의 수를 해당 트리의 높이(height)라고 하고 일반적으로 $h$라고 표기합니다. 위 트리에서 $h$는 최종 정렬 결과를 산출하기까지의 비교 횟수를 가리키는데요. 위 그림에서는 3입니다. 이 $h$가 바로 comparison sort의 계산복잡성을 나타냅니다.

이진트리의 높이가 $h$일 때 최대 $2^h$개의 말단노드를 가집니다. 그런데 데이터 수가 $n$개일 때 정렬 가능한 모든 경우의 수($n!$)보다 말단노드의 수가 커야 최악의 경우에도 데이터의 모든 요소값들을 정렬할 수 있을 것입니다. 다시 말해 $2^h≥n!$이 성립해야 한다는 말입니다. 이 부등식 양변에 밑이 2인 로그를 취하면 $h≥\log{n!}$이 됩니다. 한편 팩토리얼 연산의 성질에 의해 $n!>\sqrt{2πn}(n/e)^n$이라고 합니다. $n$이 1 이상일 때 $\sqrt{2πn}$ 역시 1보다 큰 값을 가지므로 여태까지 말씀드린 내용을 모두 종합해 식으로 표현하면 다음과 같습니다.

[h\ge \log { n! } >\log { \left{ \sqrt { 2\pi n } { \left( \frac { n }{ e } \right) }^{ n } \right} } >\log { { \left( \frac { n }{ e } \right) }^{ n } } \ \Rightarrow h>\log { { \left( \frac { n }{ e } \right) }^{ n } } \ \Rightarrow h>O\left( n\log { n } \right)]

최종 도출된 부등식의 의미는 이렇습니다. 두 값을 반복적으로 비교해 정렬하는 기법인 comparison sort는 아무리 알고리즘을 잘 짜도 계산복잡성이 $O(n\log{n})$보다 크다는 말입니다. 바꿔 말해 comparison sort 계산복잡성의 하한은 $O(n\log{n})$입니다. 예컨대 퀵 정렬(quick sort)의 계산복잡성이 $O(n^2)$이고, 힙 정렬(heap sort)이 $O(n\log{n})$이라는 점을 감안하면 이같은 내용이 들어맞음을 확인할 수 있습니다.

이 글에서 설명할 counting sort는 non-comparison sort 기법으로 정렬에 드는 계산복잡성을 $O(n)$으로 낮추려는 알고리즘입니다.

counting sort

다음과 같은 입력어레이(input array) $A$에 대해 counting sort를 수행한다고 칩시다.

$A=[2,0,2,0,4,1,5,5,2,0,2,4,0,4,0,3]$

$A$의 모든 요소값의 빈도를 세어 카운팅어레이(counting array) $C$에 저장해 둡니다. $C$의 첫번째 요소 $c_1$이 3라는 5은 $A$ 가운데 0이 다섯 개 있다는 뜻입니다. 마찬가지로 $c_2$가 1이라는 말은 $A$에 1이 하나 있다는 말이 됩니다.

$C=[5,1,4,1,3,2]$

$C$의 각 요소값에 직전 요소값을 더해서 업데이트해 줍니다. 예컨대 $c_2$는 $c_1$(5)에 기존 $c_2$(1)를 더해서 만듭니다.

$C=[5,6,10,11,14,16]$

입력어레이와 같은 크기를 갖는 출력어레이(output) $B$를 만듭니다. 처음에는 비어 있습니다. 여기에서 바로 위의 $C$의 의미는 이렇습니다.

• $c_1=5$ : 0은 $b_1$에서 $b_5$까지 다섯 개 자리를 차지한다.
• $c_2=6$ : 1은 $b_6$ 한 개 자리를 차지한다.
• $c_3=10$ : 2는 $b_7$에서 $b_{10}$까지 네 개 자리를 차지한다.
• $c_4=11$ : 3은 $b_{11}$ 한 개 자리를 차지한다.
• $c_5=14$ : 4는 $b_{12}$에서 $b_{14}$까지 두 개 자리를 차지한다.
• $c_6=16$ : 5는 $b_{15}$에서 $b_{16}$까지 두 개 자리를 차지한다.

이제 $A$ 요소값의 역순으로 $B$에 채워 넣습니다. 3은 $b_{11}$ 한 개 자리를 차지하므로 여기에 넣습니다. 아래와 같습니다. 이제 $b_{11}$의 자리가 채워졌으므로 $c_3$의 현재값(11)에서 1을 뺍니다.

다음은 0을 넣을 차례입니다. 0은 $b_1$에서 $b_5$까지 다섯 개 자리를 차지하므로 $b_5$에 넣습니다. 아래와 같습니다. 이제 $b_{5}$의 자리가 채워졌으므로 $c_1$의 현재값(5)에서 1을 뺍니다.

이러한 방식으로 $A$의 모든 요소값을 $B$에 넣으면 다음과 같이 정렬이 종료됩니다.

두 값을 비교하는 과정 없이 정렬이 수행됐음을 확인할 수 있습니다.

파이썬 구현

카운팅 정렬을 파이썬으로 구현한 코드는 다음과 같습니다.

# A: input array
# k: maximum value of A
def counting_sort(A, k):
    
    # B: output array
    # init with -1
    B = [-1] * len(A)
    
    # C: counting array
    # init with zeros
    C = [0] * (k + 1)
    
    # count occurences
    for a in A:
        C[a] += 1
    
    # update C
    for i in range(k):
        C[i+1] += C[i]
    
    # update B
    for j in reversed(range(len(A))):
    	B[C[A[j]] - 1] = A[j]
    	C[A[j]] -= 1

    return B

counting sort의 복잡성

데이터 개수가 $n$일 때 $A$의 빈도를 세는 계산복잡성은 $O(n)$입니다. 데이터 전체를 한번씩 훑어야 하기 때문입니다. 출력어레이 $B$를 만들 때도 $O(n)$입니다. $A$의 요소값들을 역순으로 모두 훑어야 하기 때문입니다.

한편 $k$는 $A$의 요소값 가운데 최댓값을 가리킵니다. 위 예시에서는 $k=5$였습니다. 카운팅어레이 $C$를 만들 때 $k+1$개의 요소값을 0으로 초기화하게 되므로 공간복잡성은 $O(k)$가 됩니다. 또한 $C$를 업데이트할 때 반복문이 $k$번 돌게 되므로 계산복잡성 또한 $O(k)$가 됩니다. 그런데 $A$가 만약 다음과 같다면 카운팅어레이 $C$의 크기가 10000+1이 되고, 반복문 또한 10000회를 돌게 되어 대단히 비효율적이게 됩니다.

$A=[0, 10000]$

요컨대 counting sort의 전체적인 계산복잡성은 $O(n+k)$가 되는데요. $k$가 충분히 작을 경우 $O(n)$이 되겠지만, $k$값이 커질 경우 $k$가 counting sort의 복잡성을 지배하게 됩니다.

Radix sort

입력데이터 $A$의 최대값인 $k$가 커지면 counting sort의 효율성은 크게 떨어집니다. 하지만 각각의 자릿수를 기준으로 정렬을 하게 되면 계산복잡성을 낮출 수 있습니다. 예컨대 10진법으로 표기된 숫자를 정렬한다면 $k$는 9가 됩니다. 이러한 정렬 방식을 Radix sort라고 합니다.

단 여기에서 주의할 것은 각 자릿수를 기준으로 정렬할 때 정렬 대상 숫자들의 위치가 뒤바뀌지 않는 stable sort 알고리즘을 적용해야 한다는 것입니다. 특정 자릿수를 놓고 정렬할 때 그 위치가 바뀌게 되면 해당 숫자가 아예 다른 숫자가 되어버리기 때문입니다. 예컨대 unstable sort를 적용하면 다음과 같은 엉뚱한 결과가 나올 수 있습니다.

14, 21 ==> 11, 24

radix sort를 연결리스트(linked list)로 구현할 수도 있습니다. 10진수 첫번째 자리를 기준으로 정렬한 뒤, 두번째 자리를 기준으로 정렬합니다. 정렬 순서를 유지하기 위해 연결리스트 삽입시 head에 넣지 않고 tail에 삽입하는 것이 특징입니다. 예컨대 아래 그림과 같이 12가 이미 있는 2번 버킷에, 22를 삽입하는 경우 12 앞이 아니라 뒤에 넣습니다. 다음 그림과 같습니다.

counting sort를 바탕으로 raddix sort를 구현한 파이썬 코드는 다음과 같습니다. counting sort도 대표적인 stable sort입니다.

# 현재 자릿수(d)와 진법(base)에 맞는 숫자 변환
# ex) 102, d = 1, base = 10, : 2
def get_digit(number, d, base):
  return (number // base ** d) % base

# 자릿수 기준으로 counting sort
# A : input array
# position : 현재 자릿수, ex) 102, d = 1 : 2
# base : 10진수라면 base = 10
def counting_sort_with_digit(A, d, base):
    # k : ex) 10진수의 최대값 = 9
    k = base - 1
    B = [-1] * len(A)
    C = [0] * (k + 1)
    # 현재 자릿수를 기준으로 빈도수 세기
    for a in A:
        C[get_digit(a, d, base)] += 1
    # C 업데이트
    for i in range(k):
        C[i + 1] += C[i]
    # 현재 자릿수를 기준으로 정렬
    for j in reversed(range(len(A))):
        B[C[get_digit(A[j], d, base)] - 1] = A[j]
        C[get_digit(A[j], d, base)] -= 1
    return B

다음은 Radix sort 코드입니다.

from math import log
def radix_sort(list, base=10):
    # 입력된 리스트 가운데 최대값의 자릿수 확인
    digit = int(log(max(list), base) + 1)
    # 자릿수 별로 counting sort
    for d in range(digit):
        list = counting_sort_with_digit(list, d, base)
    return list

Radix sort의 계산복잡성을 따져보겠습니다. counting sort이 $O(n+k)$이고 10진수를 예로 들 때 $k$는 9에 불과하므로, 특정 하나의 자릿수를 기준으로 counting sort하는 데 드는 비용은 $O(n)$이 될 것입니다. 그런데 전체 자릿수가 $d$라면 이를 $d$번 수행해야할 것입니다. 따라서 전체적인 복잡성은 $d×O(n)$이 됩니다. 1조($=10^{12}$)가 넘는 큰 숫자가 끼어 있어도 $d$는 12에 불과하기 때문에 선형시간에 가깝게 정렬을 수행할 수 있습니다.

이번 글에서는 큐(Queue)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 파이썬 코드는 이곳을 참고로 하였습니다. 그럼 시작하겠습니다.

concept

큐란 목록 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 자료구조의 일종입니다. 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 가리킵니다. 사람들이 표를 사거나 순서를 기다리려고 일렬로 늘어선 줄(queue)을 연상하면 이해가 쉽습니다. 다시 말해 먼저 줄을 선 사람(데이터)이 먼저 나갈 수 있다는 것이지요. 다음 그림과 같습니다.

큐에 새로운 데이터가 들어오면 큐의 끝 위치(tail)에 저장이 됩니다. 반대로 삭제할 때는 첫번째 위치(head)의 요소가 지워지게 됩니다. 전자를 enqueue, 후자를 dequeue라고 합니다.

operation

큐의 핵심 연산은 enqueue와 dequeue입니다. 연결리스트(linked list) 형태로 큐를 구현했을 때 예시는 다음과 같습니다.

enqueue 5, enqueue 3, enqueue 1, dequeue, dequeue, enqueue 7

연결리스트로 큐를 구현했을 때 enqueue와 dequeue의 계산복잡성은 모두 $O(1)$입니다. 추가, 삭제 연산이 각각 큐의 시작(head)과 끝(tail)에서만 일어나기 때문입니다.

큐를 array로 구현할 수도 있습니다. 다음과 같습니다.

array로 큐를 구현했을 때 enqueue의 계산복잡성은 $O(1)$입니다. 추가 연산이 큐의 끝(tail)에서만 일어나기 때문입니다. 그러나 dequeue의 계산복잡성은 $O(n)$이 됩니다. 큐의 시작(head) 요소를 지우게 되면 두번째 요소부터 끝에 이르는 모든 요소들의 위치를 왼쪽으로 한 칸씩 옮겨주어야 하기 때문입니다.

Circular Array로 큐를 구현하면 이러한 문제를 해결할 수 있습니다. 그 개념도는 다음과 같습니다. Circular Array를 쓰면 enqueue, dequeue가 각각 큐의 시작(head)과 끝(tail)에서만 일어나게 돼 둘 모두 계산복잡성이 $O(1)$이 됩니다.

파이썬 구현

파이썬에서 Circular Array로 구현한 큐는 다음과 같습니다.

class CircularQueue():

    # Constructor
    def __init__(self):
        self.queue = list()
        self.head = 0
        self.tail = 0
        self.maxSize = 8

    # Adding elements to the queue
    def enqueue(self,data):
        if self.size() == self.maxSize-1:
            return ("Queue Full!")
        self.queue.append(data)
        self.tail = (self.tail + 1) % self.maxSize
        return True

    # Removing elements from the queue
    def dequeue(self):
        if self.size()==0:
            return ("Queue Empty!") 
        data = self.queue[self.head]
        self.head = (self.head + 1) % self.maxSize
        return data

    # Calculating the size of the queue
    def size(self):
        if self.tail>=self.head:
            return (self.tail-self.head)
        return (self.maxSize - (self.head-self.tail))

이번 글에선 은닉마코프모델(Hidden Markov Models, HMMs)의 계산과정과 구현을 다루어 보도록 하겠습니다. 순차적인 데이터를 다루는 데 강점을 지녀 개체명 인식, 포스태깅 등 단어의 연쇄로 나타나는 언어구조 처리에 과거 많은 주목을 받았던 기법입니다. 이 글은 고려대 강필성 교수님 강의와 역시 같은 대학의 정순영 교수님 강의, 서울대 언어학과 신효필 교수님 저서, 위키피디아, Speech and Language Processing 3rd edition draft를 정리했고, jason2506님의 코드(BSD-licensed)를 이해하기 쉽게 정리했음을 먼저 밝힙니다. 모델 자체에 대해서는 이곳을 참고하시면 좋을 것 같습니다. 그럼 시작하겠습니다.

example

날씨를 은닉마코프모델로 구축한 예시는 다음 그림과 같습니다.

위 그림에 나타난 전이확률 $A$를 행렬 형태로 나타내면 다음과 같습니다.

방출확률 $B$는 다음과 같습니다.

아이스크림 관측치 $O$가 [3, 1, 3, 3, 1]으로 나타났다고 가정해 보겠습니다. 위 표와 같은 $A$, $B$, 즉 $θ$가 주어졌을 때 $O$가 나타날 확률(우도) $P(O$|$θ)$는 다음과 같이 32가지 경우의 수에 해당하는 모든 확률들의 합입니다.

위 32가지 경우의 수에 해당하는 결합확률의 합, 즉 우도는 0.001566021입니다. 이번엔 최적상태열을 구해보겠습니다.

위 표를 실제 계산하면 다음과 같습니다.

계산된 위 표를 토대로 backtrace를 하면 다음과 같은 최적상태열을 구할 수 있습니다.

HOT, HOT, HOT, COLD, COLD

Define Vars

전이확률 $A$, 방출확률 $B$, 상태집합 $Q$를 정의합니다. 초기 시작확률(start_prob) 또한 정의했습니다.

class Model(object):
	
    # 변수 초기화
    def __init__(self, states, symbols, start_prob=None, trans_prob=None, emit_prob=None):
        # 상태(states) : hot, cold
        self._states = set(states)
        # 관측치(observation) : 아이스크림 개수 1, 2, 3
        # 포스태깅 등에선 품사 태그(symbol)
        self._symbols = set(symbols)
        # 시작확률 : p(hot\|start), p(cold\|start)
        self._start_prob = _normalize_prob(start_prob, self._states)
        # 전이확률 : p(hot\|hot), p(cold\|hot), etc
        self._trans_prob = _normalize_prob_two_dim(trans_prob, self._states, self._states)
        # 방출확률 : p(3\|hot), etc
        self._emit_prob = _normalize_prob_two_dim(emit_prob, self._states, self._symbols)

Forward Algorithm

Forward Algorith은 $j$번째 상태에서 $o_1,…,o_t$가 나타날 전방확률 $α$를 구하는 기법입니다. 다음과 같이 정의됩니다.

[{ \alpha }{ t }(j)=\sum _{ i=1 }^{ n }{ { \alpha }{ t-1 }(i)\times { a }{ ij } } \times { b }{ j }({ o }_{ t })]

Forward Algorithm을 파이썬 코드로 구현한 결과는 다음과 같습니다.

    def _forward(self, sequence):
        # sequence : O
        # 아이스크림 소비 기록 시퀀스 [3, 1, 3]
        sequence_length = len(sequence)
        if sequence_length == 0:
            return []
	    
        # Dynamic Programming
        # 앞으로 중간 계산된 값들은 alpha라는 변수에 저장
        alpha = [{}]
        
        # 시작 지점의 alpha값 계산 후 alpha[0]에 저장
        # alpha[0] = {'hot' : p(hot\|start) * p(3\|hot), 
        #             'cold' : p(cold\|start) * p(3\|cold)}
        # p(3\|cold) : emit_prob('cold', 3)
        # sequence[0] : 3
        for state in self._states:
            alpha[0][state] = self.start_prob(state) * self.emit_prob(state, sequence[0])
	    
        # sequence의 두번째 값부터 마지막까지 likelihood 모두 계산
        # index : 위 수식에서 t
        for index in range(1, sequence_length):
            alpha.append({})
            for state_to in self._states:
                prob = 0
                for state_from in self._states:
                    # += : 위 수식에서 Σ
                    # alpha[index-1] : 위 수식에서 α_t-1
                    # state_from : 위 수식에서 i
                    # state_to : 위 수식에서 j
                    # trans_prob : 위 수식에서 a_ij
                    prob += alpha[index - 1][state_from] * \
                        self.trans_prob(state_from, state_to)
                # emit_prob : 위 수식에서 b
                # sequence[index] : 위 수식에서 o_t 
                alpha[index][state_to] = prob * self.emit_prob(state_to, sequence[index])

        return alpha

Backward Probability

전방확률 $α$와 반대 방향으로 계산한 것이 후방확률 $β$입니다. 다음과 같이 정의됩니다.

[{ \beta }{ t }(i)=\sum _{ j=1 }^{ n }{ { a }{ ij } } \times { b }{ j }({ o }{ t+1 })\times { \beta }_{ t+1 }(j)]

다음은 $β$를 구하는 파이썬 코드입니다.

    def _backward(self, sequence):
        sequence_length = len(sequence)
        if sequence_length == 0:
            return []

        beta = [{}]
        for state in self._states:
            beta[0][state] = 1

        for index in range(sequence_length - 1, 0, -1):
            beta.insert(0, {})
            for state_from in self._states:
                prob = 0
                for state_to in self._states:
                    prob += beta[1][state_to] * \
                        self.trans_prob(state_from, state_to) * \
                        self.emit_prob(state_to, sequence[index])
                beta[0][state_from] = prob

        return beta

Viterbi algorithm

$v_t(j)$는 $t$번째 시점의 $j$번째 은닉상태의 비터비 확률을 가리킵니다. $t$번째 시점 $j$번째 상태의 backtrace $b_{t_t}(j)$는 다음과 같이 정의됩니다.

[{ v }{ t }(j)=\max _{ i } ^{n}{ \left[ { v }{ t-1 }(i)\times { a }{ ij }\times { b }{ j }({ o }{ t }) \right] }\{ b }{ { t }{ t } }(j)=arg\max _{ i=1 }^n{ \left[ { v }{ t-1 }(i)\times { a }{ ij }\times { b }{ j }({ o }_{ t }) \right] }]

파이썬 코드로 구현한 결과는 다음과 같습니다.

    def decode(self, sequence):
        # sequence : O
        # sequence_length : T
        sequence_length = len(sequence)
        if sequence_length == 0:
            return []
	   
        # delta : 비터비 확률 v
        # Dynamic Programming : 중간 계산값 저장해 활용
        delta = {}
        
        # 시작 지점의 delta값 계산
        for state in self._states:
            # start_prob(state) : p(cold\|start) or p(hot\|start)
            # sequence[0] : 관측 시퀀스의 첫번째 요소, o_1, '3'
            # emit_prob(state, sequence[0]) : p(3\|cold) or p(3\|hot)
            delta[state] = self.start_prob(state) * self.emit_prob(state, sequence[0])
            
        # pre : backtrace
        pre = []
        
        # sequence의 두번째 값부터 마지막까지 delta, backtrace 모두 계산
        # index : 위 수식에서 t
        for index in range(1, sequence_length):
            # delta_bar : t번째 관측치의 비터비 확률들
            # index가 거듭될수록 그 요소가 늘어남
            # 다 돌면 sequence_length 길이
            delta_bar = {}
            # pre_state : t번째 관측치의 backtrace들
            # index가 거듭될수록 그 요소가 늘어남
            # 다 돌면 sequence_length 길이
            pre_state = {}
            for state_to in self._states:
                max_prob = 0
                max_state = None # backtrace 변수
                for state_from in self._states:
                    # state_from : 위 수식에서 i
                    # state_to : 위 수식에서 j
                    # delta[state_from] : 직전 상태의 비터비 확률(저장된 값 불러와 계산량 줄임)
                    # trans_prob : 위 수식에서 a
                    prob = delta[state_from] * self.trans_prob(state_from, state_to)
                    # 비터비 확률 수식에서 i에 대해 최대값을 구하는데,
                    # 방출확률 b는 i에 대해 무관하므로 최대값 연산에서 제외
                    if prob > max_prob:
                        # 최대값 저장 : 현재 상태의 비터비 확률
                        max_prob = prob 
                        # 최대값의 위치 저장 : 현재 상태의 backtrace
                        max_state = state_from 
                delta_bar[state_to] = max_prob * self.emit_prob(state_to, sequence[index])
                pre_state[state_to] = max_state
            # o_2까지의 비터비 확률을 구했다면 o_1 이전의 비터비 확률은 불필요
            # o_2의 비터비 확률들의 모음인 delta_bar를 전체 delta에 덮어씌움
            delta = delta_bar
            # o_2까지의 backtrace를 구했다 하더라도 o_3은 달라질 수 있음
            # pre에 pre_state를 append
            pre.append(pre_state)
	    
        # 전체 시퀀스를 대상으로 최대 비터비확률과
        # 최대 비터비 확률을 내는 state 찾기
        # 현재 delta에는 시퀀스의 마지막 요소(O_T)에 
        # 해당하는 비터비 확률들이 저장돼 있기 때문
        # (state로만 구분되어 있음)
        max_state = None
        max_prob = 0
        for state in self._states:
            if delta[state] > max_prob:
                max_prob = delta[state]
                max_state = state

        if max_state is None:
            return []
	   
        # 최대 비터비 확률을 내는 state가 backtrace의 첫번째 요소
        result = [max_state]
        # index를 시퀀스의 역방향으로 후진하면서
        for index in range(sequence_length - 1, 0, -1):
            # index에 해당하는 max_state들을 뽑아내기
            # 이는 저 위쪽에서 이미 max_state들을 저장해두었기 때문에 가능
            max_state = pre[index - 1][max_state]
            # 뽑아낸 max_state들을 result의 첫번째 위치에 저장
            result.insert(0, max_state)

        return result

Training

은닉마코프모델의 학습 의사코드는 다음과 같습니다.

파이썬으로 구현한 결과는 다음과 같습니다.

   def learn(self, sequence, smoothing=0):

        length = len(sequence)
        alpha = self._forward(sequence)
        beta = self._backward(sequence)

        gamma = []
        for index in range(length):
            prob_sum = 0
            gamma.append({})
            for state in self._states:
                prob = alpha[index][state] * beta[index][state]
                gamma[index][state] = prob
                prob_sum += prob

            if prob_sum == 0:
                continue

            for state in self._states:
                gamma[index][state] /= prob_sum

        xi = []
        for index in range(length - 1):
            prob_sum = 0
            xi.append({})
            for state_from in self._states:
                xi[index][state_from] = {}
                for state_to in self._states:
                    prob = alpha[index][state_from] * beta[index + 1][state_to] * \
                        self.trans_prob(state_from, state_to) * \
                        self.emit_prob(state_to, sequence[index + 1])
                    xi[index][state_from][state_to] = prob
                    prob_sum += prob

            if prob_sum == 0:
                continue

            for state_from in self._states:
                for state_to in self._states:
                    xi[index][state_from][state_to] /= prob_sum

        states_number = len(self._states)
        symbols_number = len(self._symbols)
        for state in self._states:
            # update start probability
            self._start_prob[state] = \
                (smoothing + gamma[0][state]) / (1 + states_number * smoothing)

            # update transition probability
            gamma_sum = 0
            for index in range(length - 1):
                gamma_sum += gamma[index][state]

            if gamma_sum > 0:
                denominator = gamma_sum + states_number * smoothing
                for state_to in self._states:
                    xi_sum = 0
                    for index in range(length - 1):
                        xi_sum += xi[index][state][state_to]
                    self._trans_prob[state][state_to] = (smoothing + xi_sum) / denominator
            else:
                for state_to in self._states:
                    self._trans_prob[state][state_to] = 0

            # update emission probability
            gamma_sum += gamma[length - 1][state]
            emit_gamma_sum = {}
            for symbol in self._symbols:
                emit_gamma_sum[symbol] = 0

            for index in range(length):
                emit_gamma_sum[sequence[index]] += gamma[index][state]

            if gamma_sum > 0:
                denominator = gamma_sum + symbols_number * smoothing
                for symbol in self._symbols:
                    self._emit_prob[state][symbol] = \
                        (smoothing + emit_gamma_sum[symbol]) / denominator
            else:
                for symbol in self._symbols:
                    self._emit_prob[state][symbol] = 0        

코드 실행

원저자의 코드는 이곳, 백업용으로 올려놓은 코드는 이곳에 있습니다. 은닉마코프모델을 수동으로 구성(모델이 이미 있는 것으로 전제)해 그 작동을 확인해보고자 한다면 아래와 같이 실행하면 됩니다. (위의 그림 예시와 같으나 end state는 없는 걸로 가정)

import hmm
states = ('hot', 'cold')
symbols = ('1', '2', '3')

start_prob = {
    'hot' : 0.8,
    'cold' : 0.2
}

trans_prob = {
    'hot': { 'hot' : 0.6, 'cold' : 0.4 },
    'cold': { 'hot' : 0.4, 'cold' : 0.6 }
}

emit_prob = {
    'hot': { '1' : 0.2, '2' : 0.4, '3' : 0.4 },
    'cold': { '1' : 0.5, '2' : 0.4, '3' : 0.1 }
}

model = hmm.Model(states, symbols, start_prob, trans_prob, emit_prob)
sequence = ['3', '1', '3']
print(model.evaluate(sequence)) # Likelihood 계산
print(model.decode(sequence)) # 최적상태열 추정

EM 알고리즘을 통한 학습은 다음과 같이 합니다.

import hmm
sequences = [
    (state_list1, symbol_list1),
    (state_list2, symbol_list2),
    ...
    (state_listN, symbol_listN)]
model = hmm.train(sequences)

이번 글에서는 한국어의 격조사에 대해 살펴보도록 하겠습니다. 이번 글은 고려대 정연주 선생님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

조사

조사란 주로 명사구 뒤에 나타나서 선행하는 명사구가 다른 말과 맺는 문법적 관계를 나타내거나, 선행하는 명사구에 일정한 의미를 더하는 기능을 하는 말입니다. 예문을 보겠습니다.

아이들이 마당에서 공놀이만 한다.

조사에는 다른 말과의 문법적 관계를 표시하는 격조사, 둘 이상의 말을 같은 자격으로 이어주는 접속조사, 특수한 뜻(의미)을 더해주는 보조사로 나누어 생각해볼 수 있습니다. 위 예문에서 이, 에서가 격조사, 만이 보조사에 해당합니다. 이 글에서는 격조사를 중심으로 살펴보겠습니다.

격조사

격이란 핵이 있는 구성에서 핵에 의존적인 명사(구)가 핵에 대해 가지는 문법적, 의미적 관계의 유형을 가리킵니다. 다시 말해 명사구가 문장 내에서 갖는 자격이 바로 격입니다.

격조사란 격을 나타내는 조사입니다. 격조사는 조사의 형태만으로도 선행 명사구가 문장 내에서 수행하는 기능을 짐작할 수 있습니다. 예문을 보겠습니다.

(1) 진이가 집에서 밥을 먹었다.

(2) 진이의 집

(1)에 해당하는 절(節)의 핵은 ‘먹었다’라는 서술어입니다. (1)에 속한 명사구들이 서술어 핵과 어떤 문법적 관계를 맺고 있는지 분석해 보겠습니다. 서술어의 주체(주어)는 진이, 서술어가 가리키는 행위가 일어나는 공간은 집, 서술어의 대상(목적어)는 밥입니다. 이번엔 격조사가 격을 어떻게 나타내고 있는지 살펴보겠습니다. (1)에서 ‘가’는 앞말이 주어임을 표시하고 있습니다. ‘에서’ 앞의 집은 부사어(장소), ‘을’ 앞의 밥은 목적어라는 사실을 나타내고 있습니다.

(2)에 해당하는 명사구의 핵은 ‘집’이라는 명사입니다. ‘진이의’라는 명사구는 명사 핵 ‘집’과 의존(수식) 관계를 맺고 있습니다. 여기에서 격조사 ‘의’는 앞말이 관형어임을 표시하고 있습니다.

한편 격조사는 크게 문법격 조사와 의미격 조사 둘로 나뉩니다. 문법격 조사는 문장 내에서 선행 명사구의 문법적 자격을 나타내는 조사로, 그 예로 ‘가(앞말이 주어임을 나타냄)’ ‘를(목적어)’ ‘의(관형어)’ 등이 있습니다. 의미격 조사는 문장 내에서 명사구의 의미적 자격을 나타내는 조사로, ‘에(장소)’ ‘로(장소/도구)’ ‘와(동반자)’ 등이 있습니다.

주격조사

주격조사란 앞의 말이 그 문장의 주어임을 나타내는 것을 주된 기능으로 하는 조사입니다. ‘이/가’가 대표적입니다. 다음 예문과 같습니다.

학생들이 노래를 부르고 있다.

다만 주어로 해석할 수 없는 명사(구)에 ‘이/가’가 결합하는 경우도 있어서 분석에 주의를 기울여야 합니다. 아래 예문의 경우 전체 문장의 주어는 ‘진이’이지 ‘반장’이 아닙니다(‘반장’은 보어). 그런데도 반장이라는 명사에 ‘이’가 붙었습니다.

진이가 반장이 되었다.

진이가 반장이 아니지?

아래와 같은 ‘장형 부정 구문’에서도 이러한 현상을 발견할 수 있습니다. 아래 예문의 경우 ‘춥다’는 서술어(본용언)에 해당하는 데 ‘가’가 붙었습니다.

날씨가 춥지가 않다.

한편 ‘께서’는 존칭명사, ‘서’는 사람의 수를 나타내는 명사 뒤에 쓰이는 주격조사입니다. 다음 예문과 같습니다.

선생님께서 진이를 칭찬하셨다.

셋이서 길을 나섰다.

목적격조사

목적격조사란 앞의 말이 그 문장의 목적어임을 나타내는 것을 주된 기능으로 하는 조사입니다. 어떤 행위가 미치는 ‘대상’을 가리키는 격조사라는 취지로 대격조사라고 부르기도 합니다. 다음 예문과 같습니다.

아이들이 매미를 잡는구나.

목적격조사 ‘을/를’ 역시 목적어로 해석할 수 없는 명사구에 ‘을/를’이 결합하는 경우도 있습니다.

진이는 밥을 먹지를 않았다.

관형격조사

앞의 말이 후행하는 체언의 관형어임을 나타내는 조사를 관형격조사라고 합니다. 명사와 명사 사이에 나타나 두 명사를 더 큰 명사구로 묶어줍니다. 한 명사가 다른 명사에 소속되는 관계에 있음을 나타내 주는 기능에 주목해 속격조사라고도 부릅니다.

소유 : 언니의 모자

주체 : 나의 연구

대상 : 향가의 연구

소속 : 한국의 사찰

속성 : 평화의 종소리

부사격조사

앞의 말이 그 문장의 부사어임을 나타내는 것을 주된 기능을 하는 격조사를 부사격조사라고 합니다. 하지만 부사격조사에는 다양한 종류가 있고, 문법적 기능보다는 이들이 표시하는 여러 의미 관계가 중요할 때가 많습니다. 부사격조사의 종류를 차례로 살펴보겠습니다.

처격조사

장소(처소)를 나타내는 것을 주된 임무로 하는 부사격조사입니다. 대표적으로 ‘에’, ‘에게’, ‘에서’ 등이 있습니다.

‘에’는 다음과 같이 쓰입니다. 아래 유형로 갈 수록 장소의 본래적 의미가 추상화돼 확장되고 있는 경향을 나타냅니다. ‘태풍에 나무가 쓰러졌다’ 문장에서 나무가 쓰러진 배경(공간)에 태풍이 있었다, 는 정도로 해석할 수도 있다는 것입니다.

‘에게’는 ‘에’와 기능상 밀접합니다만 ‘에게’는 유정명사, ‘에’는 무정명사에 사용합니다. 아울러 ‘에게’는 ‘주다’ 류의 동사와 어울려서 주는 일과 관련되어 쓰이는 일이 잦아서 여격조사라고 부르기도 합니다. 다음 예문과 같습니다.

‘에서’는 이동성 및 방향성이 있는 서술어와 결합하는 경우 출발점을 가리킵니다.

선수단이 부산(출발점)에서 왔다

선수단이 부산(도착점)에 왔다

‘에서’는 ‘에’와 마찬가지로 기본적으로 처소를 나타내나 그 분포가 서로 다릅니다.

{거실에서, *거실에} 뛰었다.

{*거실에서, 거실에} 화분이 있다.

그렇다면 위 예문의 ‘에’와 ‘에서’는 어떤 의미적 차이를 지니길래 분포가 달라지는 걸까요? 대체로 ‘에’는 위치나 존재를 나타내는 정적인 서술어와 결합하여 사람이나 물건이 존재하거나 위치하는 곳을 나타냅니다. ‘에서’는 동적인 서술어와 결합하여 활동이 일어나는 곳을 나타냅니다. 각 유형에 해당하는 서술어의 예시는 다음과 같습니다.

있다, 없다, 살다, 남다 : 에

놀다, 공부하다, 회의하다, 연설하다, 일하다, 근무하다, 싸우다, 자라다, 죽다, 만나다, 기다리다, 헤어지다 : 에서

하지만 ‘에’와 ‘에서’가 별 차이 없이 같이 쓰이는 경우도 많습니다. 역사적으로 ‘에’와 ‘에서’가 한 말에서 분화돼 현대에서는 둘이 공존하고 있다는 해석도 제기됩니다.

구격조사

구격조사는 무엇을 만들 때 쓰이는 도구나 재료 및 어떤 일을 하는 수단을 나타내는 것을 주된 임무로 하는 조사를 가리킵니다. 구격조사엔 ‘으로/로’가 있습니다. 다음 예문과 같습니다. 구격조사 역시 아래 유형으로 갈수록 본래의 도구, 재료, 수단에서 그 의미가 추상화, 확장되고 있는 경향을 확인할 수 있습니다.

예컨대 이유(=다른 사태를 유발하는 수단)와 경로(=다른 장소로 이동하는 수단)는 수단의 확장으로 볼 여지가 있습니다. 처소(=물리적으로 이동한 장소), 결과(=추상적으로 이동한 장소), 자격(=추상적으로 이동한 장소)은 경로의 의미에서 도출된 장소의 확장으로도 해석할 수 있을 것 같습니다.

위 표에서 처소(지향점)로 쓰인 ‘로’가 처격조사 ‘에’와 쓰임이 유사한 걸 확인할 수 있습니다. 둘 모두 목적지를 나타내는 조사이기 때문입니다. 다음 예문과 같습니다.

수업이 끝나면 {식당에, 식당으로} 오세요.

그런데 둘은 분명 쓰임이 다릅니다. ‘에’는 도착점을 가리키는 반면 ‘로’는 방향을 가리킵니다.

나는 {서울에, *서울로} 도착했다.

화장실에 가려면 {*아래에, 아래로} 내려가세요.

공동격조사

두 명사가 서로 짝이 되어 어떤 일에 관여할 때 동반자를 표시하는 조사를 공동격조사라고 합니다. 대표적으로 ‘와/과’가 있습니다.

영희가 철수와 결혼했다.

진이는 동생과 사이좋게 지냈다.

‘와/과’는 주로 문어에서 쓰이고, ‘하고’는 대개 구어에서 쓰입니다.

비교격조사

두 명사의 상태를 비교할 때 비교의 대상을 표시하는 조사를 비교격조사라고 합니다. ‘보다’와 ‘처럼, 만큼, 같이’가 대표적입니다. 전자는 두 명사의 상태에 차이가 있음을 전제로 하여 쓰이고, 후자는 두 명사의 상태에 우열의 차이가 없을 때 사용됩니다. 다음 예문과 같습니다.

오늘이 어제보다 덥다

호수가 거울처럼 맑다

키가 형만큼 컸다

곰같이 미련하다

‘처럼, 만큼, 같이’ 가운데 성격이 나머지와 다른 하나가 바로 ‘만큼’입니다. 앞말과 비교대상이 실제로 비슷해야 쓸 수 있고, 비유적인 상황에는 사용할 수 없습니다.

(키가 190cm인 형과 180cm인 동생을 비교하며) 키가 {형처럼, 형같이, ?형만큼} 크네.

번개{처럼, 같이, *만큼} 빠르다.

인용격조사

인용격조사에는 ‘라고/이라고’, ‘고’ 두 가지 종류가 있습니다. 전자는 직접 인용, 후자는 간접 인용의 부사격조사입니다.

“어서 오너라”라고 선생님께서 말씀하신다.

어서 오라고 선생님께서 말씀하신다.

호격조사

앞의 말이 부름말임을 나타내는 격조사로, 누구를 부를 때 이름이나 호칭 다음에 쓰는 조사입니다. ‘아/야’는 해라체를 쓸 상대에게만 쓰여 경어법 면에서 큰 제약을 받습니다. 손윗사람에게는 ‘아버님’, ‘형’처럼 호격조사를 생략한 채 호칭만 씁니다. ‘여/이여’, ‘시여/이시여’는 존대 의미를 나타내는 호격조사로 기도문이나 시적표현 등에 자주 쓰입니다.

서술격조사

학교문법에서는 ‘이다’를 서술격조사로 분류하고 있습니다. 하지만 ‘이다’의 문법적 특성은 매우 복잡해서 어느 하나의 범주로 분류하기 어렵다는 견해가 주류입니다. ‘이다’의 특성에 관련해서는 이곳을 참고하시면 좋을 것 같습니다.