*********************************************************************
오토마타 이야기 1
*********************************************************************
이야기틀 : 오토마타 이야기
이야기꾼 : 한동훈 ddoch@hitel.kol.co.kr
ddoch@nownuri.nowcom.co.kr
저작권 : GPL
이야기날짜 : 1997.1.24
순 서 :
1. 들어가는 말
2. 오토마타란?
3. 간단한 예제 하나
4. 오토마타 문자열 검색법
5. 한글과 오토마타
6. 나오는 말
1. 들어가는 말
요즘들어서 본의 아니게 시간이 많아서 그동안 보지 못했던 알고리즘을 공부
하게 되었습니다. 그러든 중 항상 생각만 하고 있던 한글입력기를 만드는 작업에
착수하게 되었지요. 역시 오토마타라는 알고리즘을 이해를 하고 들어가니 한글
오토마타라는 것이 우리가 알고 있는 한글조립법의 상식을 표로 그려둔 것에
지나지 않았습니다. 그래서 몇일동안뚝딱거려서 예전에 만들어둔 한글출력기
와 합쳐서 한글라이브러리를 완성했습니다. 한글입력기가 제대로 돌아가는 순
간 정말 기분은 하늘로 날라가는 것만 같았습니다. 이제는 제가 그동안 만들어
둔 재사용가능한 루틴들을 포함시키면서 패키징 작업에 들어가고 있습니다.
(괜히 저 자랑같이 되어 버렸네요.. ^^;)
저번에 리눅스동호회 번개모임에 갔을 때, 어느분이 한글오토마타에 대해서 질
문을 하셨는데 제대로 답변을 못해서 미안할 따름이었는 데, 이제 이 강좌로
갈음 할 수 있었으면 좋겠습니다.
이 강좌는 한글입력기를 구현하시고자 하는 분이나, 오토마타라는 알고리즘을
이해하시고자 하는 분들을 위해서 쓰여졌습니다. 그리고 실제 예제는 저의 한
글라이브러리 안에 있는 루틴들과, "C로 배우는 알고리즘", "컴퓨터 속의 한글"
를 참조하였음을 밝혀두겠습니다.
2. 오토마타란?
저도 예전에 그랬지만 한글오토마타와 한글입력기를 구분하지 못하시는 분들이
많이 있습니다. 한글오토마타는 오토마타라는 알고리즘을 이용해서 한글입력의
기본원리를 구현한 것이고, 한글입력기는 말그대로 한글입력을 처리하는 루틴
입니다. 한글입력기는 얼마던지 오토마타라는 알고리름을 사용하지 않고도 구
현이 가능하지만 오토마타라는 알고리름을 이용하는 것이 현재로선 가장 효율
적입니다.
3. 간단한 예제 하나
먼저, 오토마타라를 이해하기 위해서 오토마타는 아니지만 그 비슷한 예를 하나
들겠습니다.
일반적으로 한글을 처리하는 데서 많이 쓰이는, 어떤 문자열 내에서 몇번째 문
자가 영문인가? 아니면 한글 첫째 바이트인가? 둘째 바이트인가 를 알아내는
함수를 예로 들겠습니다.
한글은 2바이트로 처리되며 첫바이트는 0x80(16진수) 이상이라는 것을 잘 알고
계실 겁니다. 한글완성형은 첫바이트던 둘째 바이트던 모두 0x80이상으로 맞춰
져 있습니다만 우리가 가꿔야 할 조합형은 아쉽게도 둘째 바이트가 0x80이하인
것이 더러 있습니다. 조합형으로 "가"는 16진수로 "88 61" 로 되는 데 0x61은
소문자 'a'입니다. 즉, 어느 문자열 중에서 a가 나온다고 해서 무조건 영문자
라고만 볼 수 없다는 이야기입니다. 조합형 한글 둘째 바이트가 될 수 있다는
이야기죠.
한글이 포함된 문자열이 있다고 했을 때, 어느 위치의 바이트가 종류가 어떻게
되는 지 오토마타적 알고리즘으로 생각해봅시다. 단 문자열의 처음에는 한글둘
째 바이트로 시작해서는 안된다는 전제가 있어야 합니다.
영문자면 0, 한글 첫째바이트이면 1, 한글 둘째 바이트이면 2로 가정하겠습니다.
문자열 : char str[8] = "a각b한z"
위의 문자열에서 배열의 첨자형식으로 인덱스를 따지면, 0번째 'a'는 당연히
0이고, 1번째는 '1', 2번째는 '2', 3번째는 '0', 4번째는 '1', 5번째는 '2'...
이런 식으로 될것입니다. 즉, 상태 0은 영문자, 상태 1은 한글 첫째 바이트,
상태2는 한글둘째바이트로 하겠습니다.
128 이상 무조건
+-> 상태0 ------------------> 상태1 -----------------> 상태2
| ^ | ^ | |
| | | 128 미만 +------------------------+ |
| +---+ |
| |
+------------------------------------------------------------+
간단히 그려본 상태변화도 입니다. 문자열을 검사하기전에 상태0로
초기화를 하고나서 문자열을 처음부터 하나씩 검사를 해서 그 문자값이 128
(0x80)이상일 경우와 128미만 일 경우로 나누어 집니다.
즉, 처음의 상태0에서 128미만의 글자가 처음으로 나오면 당연히 상태0
이 되고, 128이상의 글자가 나오면 한글첫째바이트 이므로 상태1로, 다음
바이트는 안보고도 한글두째바이트로 간주해서 상태2로 넘어갑니다. 상태2
에서 128미만의 글자가 나오면 영문자(128미만의 아스키문자)로 상태0이
되고 128이상의 글자가 나오면 상태1로 됩니다. 이상태로 원하는 인덱스의
문자열이 나올때까지 계속 검사를 하면 문자의 종류를 알수 있습니다.
사실 이정도는 그냥 간단하게 해도 되지만 일부러 오토마타적 사고방식으로
풀이를 했습니다. 그림을 못그렸지만 보시면 이해가 쉬울 겁니다.
그럼, 위의 그림을 보고 한글종류를 돌려주는 함수를 작성해 보겠습니다.
함수원형 : int ishangul(unsigned char *str, int index);
인 자 : str은 검사대상 문자열, index는 배열첨자식 str내의 위치
반환 값 : 0 : 영문자 , 1 : 한글첫째바이트, 2 : 한글둘째바이트
#include <stdio.h>
#include <string.h>
#define IS_LOW_ASC 0 /* 128 미만의 아스키코드 */
#define IS_HIGH_ASC 1 /* 128 이상의 아스키코드 */
#define IS_ENGLISH 0 /* 상태 0 */
#define IS_HANGUL_FIRST 1 /* 상태 1 */
#define IS_HANGUL_SECOND 2 /* 상태 2 */
typedef unsigned char byte;
int ishangul(byte *str, int index) {
int state;
int inMode;
int key;
int i = 0;
if (strlen(str) < index + 1) return -1; /* 문자열길이가 index보다 작다면 */
state = IS_ENGLISH; /* 상태0으로 초기화 */
while ((key = *(str + i)) != '\0') { /*문자열의 끝까지 */
if (key < 128) inMode = IS_LOW_ASC;
else inMode = IS_HIGH_ASC;
switch (state) {
case IS_ENGLISH : /* 상태0이고 128이상의 문자라면 한글 첫째 */
if (inMode) state = IS_HANGUL_FIRST;
else state = IS_ENGLISH; /* 그외에는 영문자 */
break;
case IS_HANGUL_FIRST : /* 한글첫째상태라면 한글둘째 */
state = IS_HANGUL_SECOND;
break;
case IS_HANGUL_SECOND : /* 한글 둘째 상태라면 */
if (inMode) state= IS_HANGUL_FIRST; /* 128이상이라면 한글첫째 */
else state = IS_ENGLISH; /* 128미만이라면 영문자 상태 */
break;
}
if (i++ == index) break; /* 찾는 인덱스까지 검사했다면 */
}
return state; /* 한글의 종류를 리턴 */
}
아주 이해하기가 쉬울 겁니다. 때로는 조금 복잡한 것도 오토마타적 알고리즘
으로 생각하면 쉬울 때가 종종 있을 겁니다. 정확히 작동하는 지 한번 테스트
해보시기 바랍니다.
다음 시간에는 오토마타 알고리즘을 사용한 문자열 검색법을 알아보겠습니다.
ddoch 한동훈
#1809 시삽 (김성대 )
[강좌] 오토마타 이야기 (2) 0 05/14 14:05 39
3. 오토마타 문자열 검색법
오토마타의 정확한 의미는 "이산적인 입력과 출력을 가지는 시스템의 수학적
모델" 입니다. 오토마타는 5개의 항목으로 구성됩니다.
(에디터로는 표현하기 곤란한 수학적인 기호가 들어가는 관계로, 기호대신
적절한 낱말로 표현하겠습니다. )
상태집합, 초기상태, 종료상태, 입력문자집합, 상태전이 함수가 그것입니다.
좀 엉뚱하지만 재미있는 예를 하나 들겠습니다.
아릿다운 공주가 5층짜리 건물의 5층에 갇혀 있습니다. 각 1층부터 4층까지
층마다 흉칙한 괴물이 지키고 서있고, 통과하려면 죽음의 "가위바위보"를 해
서 이겨야 통과할 수 있습니다. 만일 이기면 한층위로 올라갈 수 있고, 지면
한층을 내려와야 합니다. 그런데 주인공이 낼 수 있는 경우는 오로지 "바위"
뿐입니다. 무승부가 되면 다시 가위바위보를 해야 합니다.
자, 이제 입구에서 부터 시작해서 5층까지 괴물이 가위바위보를 내는 경우에
따라 주인공은 몇층에 있는 지 생각해 봅시다.
[표 1]
-------------------------------------------------------
주인공이 있는 층 \ 괴물이 내는 가위바위보의 경우
가위바위 보
-------------------------------------------------------
입구 1층 입구 입구
1층 2층 1층 입구
2층 3층 2층 1층
3층 4층 3층 2층
4층 5층 4층 3층
5층 . . .
--------------------------------------------------------
이해가 쉽게 될 겁니다. 왼쪽은 주인공이 있는 층이고 오른쪽은 괴물이 내는
경우에 따라 달라지는 주인공이 있게 되는 층입니다. 이렇게 표를 만들어 두
면 주인공의 상황과 각 경우에 따라 어떻게 주인공의 상태가 변하는 가하는
것을 쉽게 알 수 있습니다. (예가 유치하죠? ^^;)
여기서 상태집합은 주인공이 있게 되는 층인 {입구, 1층, 2층, 3층, 4층, 5층}
입니다. 초기상태는 당연히 "입구"가 됩니다. 종료상태는 "5층"이 되겠죠?
입력문자집합은 괴물이 내는 {가위, 바위, 보}가 됩니다. 상태전이함수는
위의 표입니다. 현재의 상태에서 각 경우를 만나면 어떤상태를 얻을 수 있
다는 것이 상태전이 함수입니다. 너무 쉽죠?
즉, 간단하게 말하면 "어떤 상태가 주가 되고 외부적인 경우에 따라 그 상태가
어떻게 변하는가를 표로 나타낸 것"이 "오토마타 표"가 됩니다.
이제 이러한 오토마타 알고리즘으로 간단한 문자열을 검색해봅시다. 예를 간단
히 하기 위해서 "01"로만 예를 들었습니다.
원본 문자열 : "001011010101" : DEST
찾는 문자열 : "110101" : SEARCH
위의 경우처럼 상태전이표를 그려보면 됩니다.
상태집합 = { 0, 1, 2, 3, 4, 5, 6}
초기상태 = 0
종료상태 = 6
입력문자집합 = {'0', '1'}
상태전이함수 =
[표 2]
------------------------------------
상태\입력 '0' '1'
------------------------------------
0 0 1
1 0 2
2 3 2
3 0 4
4 5 2
5 0 5
6 . .
------------------------------------
좀 더 알아보기 쉽게 상태전이도를 나타내면 다음과 같습니다.
+--------------------+
| 1 |
1 1 V 0 1 | 0 1
q0 ---> q1 ----> q2 ----> q3 -------> q4 ------> q5 ------> q6
^ |
| | 1
+-+
(각 상태에서 q0으로 가는 것은 부분적으로 생략..)
V는 화살표입니다. ^^;
q0, q1...등은 위의 상태0, 상태1등과 같습니다.
상태집합 : 여기서의 목적은 SEARCH를 DEST에서 찾는 것이 목적입니다.
0은 초기화상태 또는 하나도 맞지 않는 상태이고, 1은 하나
의 글자가 맞는 상태입니다. 이 상태의 갯수는 SEARCH의 길
이 + 1 입니다. 상태가 6이 되면 6개의 글자가 다 맞는 것이
되고 종료해야 겠지요?
초기상태 : 당연히 0으로 초기화됩니다.
종료상태 : 6개 글자가 다 맞으면 그 위치를 돌려주면 되겠죠?
입력문자집합 : 여기서는 '0', '1'로 2개로 단순화 했습니다.
상태전이 함수 :
"110101"을 찾는다고 했으니 검색하기 전에는 상태는 0이 된다고 했습니다.
대상문자열중에서 "1"이 나온다고 하면 찾는 문자열의 앞부분과 하나가 맞으
니 상태는 1로 진전됩니다. 다시 "1"이 나오면 2개가 맞으니 상태가 2로 됩
니다. 만일 "0" 이 나온다면 "10"이므로 찾는 문자열의 앞부분과 일치되지
않으므로 상태 0이 되는 것입니다. 상태2에서 "0"을 만나면 상태3이 되고 ,
다시 "1"을 만나면 상태4가 되겠죠? 이상태에서 다시 "0"을 만난다면 문제없
이 상태5로 되겠지만 "1"을 만난다면 그간 비교된 문자는 "11011" 이 되어서
뒤의 2개의 문자가 SEARCH의 "110101"의 앞의 두개문자와 같으므로 상태는 2
가 됩니다. 이런 식으로 검색하여 상태가 6이 된다면 "110101"이 다 맞는 것
이 되어서 리턴을 하는 것이 오토마타를 사용한 문자열 검색법입니다.
자세히 보시면, 오토마타는 순전히 SEARCH에 의존합니다. 오토마타가 완성될
상태를 0에서 N개 까지 만들어 놓고, 각 들어올 수 있는 경우(여기서는 0,1)
에 따라 SEARCH를 참조하여 상태를 전진시키거나 후퇴시키는 것입니다.
만일 아스키문자를 비교한다고 하면 입력문자집합은 256개가 되어서 거대한
표나 상태전이함수를 만들어 둬야 합니다. 같은 문자열을 계속 찾는 경우에
는 아주 유용한 알고리즘이지만 SEARCH가 자주 바뀌면 바뀔 때 마다 상태
전이함수를 만들어야 하기 때문에 리소스의 낭비가 심해지게 됩니다.
"오토마타를 이용한 문자열 검색 알고리즘"의 의사코드는 다음과 같이 됩
니다.
S = "001011010101"
P = "110101"
-----------------------------------------------------------------------
q = 0; /* 상태를 0으로 초기화 */
for(i = 0; i< strlen(S); i++) { /* 문자열의 끝까지 비교 */
q = (q, S[i]); ----------- (1)
if (q == strlen(P)) return i-strlen(P)+1; ------ (2)
}
return -1;
-----------------------------------------------------------------------
(1)에서 괄호안의 q는 현재 상태이고, S[i]는 S에서 현재 비교되는 문자입니
다. 이 두값을 가지고 [표 2]에서 작성한 상태전이함수에서 다음의 상태를
가져옵니다. (2)에서 상태가 P의 길이인 6이 되면 다 맞는 결과이므로 현재
위치(i--배열첨자식)에서 P의 길이를 빼서 1을 보내면 S에서 P의 문자열이 나
타나는 처음 위치입니다.
전이함수는 실제로는 2차원 배열입니다.
#define NSIGMA 2
char DELTA[6][NSIGMA];
앞의 6은 strlen(P)인 상태의 갯수인데, [표 2]와 비교해 보시면 제일 마지막
의 상태6은 실제로없어도 되는 부분이므로 배열 6개만 잡아도 충분합니다.
뒤의 NSIGMA는 입력문자의 갯수입니다. 여기서는 '0', '1'이 올 수 있기 때문
에 2로 정의하였습니다. 실제로 이 배열은 [표 2]를 배열로 표현한 것입니다.
즉, '0', '1'을 배열의 첨자로 사용하기 위해 0, 1로 순서를 매긴다고 보면,
"DELTA[3][1]"은 상태3에서 '1'을 만났을 때를 이야기 하며 그 값은 4가 되어
야 합니다.
이제 전이함수인 2차원 배열의 값을 어떻게 구할 것인가 생각해봅시다.
P = "110101"
char pq[50], pj[50];
int q,j;
1) q = 0에서 시작한다.
2) P에서 q의 길이만큼 pq에 복사한다. (pq = "")
3) pq에 입력문자집합에 있는 것을 하나씩 pq의 뒤에 추가한다.
(pq = "0")
4) j = strlen(pq); (j = 1)
5) P에서 j만큼 pj에 복사한다. (pj = "1")
6) pj가 pq의 접미어인가? 즉, pj의 문자열이 pq의 뒤에 나타나는가?
아니면 --j만큼 P에서 pj로 문자열을 복사해서 계속 검사한다.
("1"이 "0"의 접미어? 아니다. 따라서 pj 는 이번에는 ""이 된다. j = 0
이 되고..""은 "0"의 접미어? )
7) DELTA[q][i] = j; (DELTA[0][0] = 0)
8) 2)번으로 가서 다시 반복하고 q = 1로 해서 다시 반복한다.
이해가 되는가요?
원리는 간단합니다. P에서 0개부터 5개까지 문자열을 가져와서 나올 수 있는
입력문자를 하나씩 붙여서 이것이 P에서 1개에서 6개 까지의 문자가 접미어가
되는가를 검사하는 것입니다. 곰곰히 생각해 보시길..
-----------------------------------------------------------------------
int q; /* 상태 */
int i, j;
int pl; /* 문자열 P의 길이 */
char pq[50], pj[50]; /* 문자열을 저장할 임시공간 */
pl = strlen(P);
for (q = 0; q < strlen(P); q++) { /* strlen(P) 는 6 */
for (i = 0; i < NSIGMA; i++) { /* 2차원 배열에 값을 구함 */
substr(P, pq, q); -- (1)
pq[j = strlen(pq)] = table[i]; -- (2)
pq[++j] = '\0'; -- (3)
while (!is_suffix(substr(P, pj, j), pq)) j--; -- (4)
DELTA[q][i] = j; -- (5)
}
}
-----------------------------------------------------------------------
2차원 배열 DELTA에 값을 얻기 위해서 2중 루프를 돌린다는 것은 쉽게 이해가
갈 것입니다. 여기에서 substr(P, pq, q)함수는 간단히 만든, 문자열 P에서 pq로
q의 길이만큼 복사하는 함수입니다. is_suffix(a, b)는 a가 b의 접미어이면 1을
돌려주고 아니면 0을 돌려주며 나올때까지 j를 감소시킵니다.
------------------------------------------------------------------------
char *substr(char s[], char t[], int k) {
int i;
for (i = 0; i < k; i++)
t[i] = s[i];
t[i] = '\0';
return t;
}
int is_suffix(char p[], char s[]) {
int pl, sl, i, j;
pl= strlen(p);
sl= strlen(s);
if (pl > sl) return 0;
for (i = pl -1, j = sl -1; i >= 0; i--, j--)
if (p[i] != s[i]) return 0;
return 1;
}
------------------------------------------------------------------------
상당히 어설프게 설명을 한 것 같습니다. 하지만 잘 살펴보시면 이해가 가실
겁니다. 굳이 뒷부분은 이해가 안되신다 하더라도 오토마타 원리부분만 이해
를 하셨더라도 다음으로 넘어가실 수 있을 겁니다. 이 부분을 설명드린 것은
어디까지나 오토마타라는 알고리즘에 대해서 말씀드리기 위한 것입니다.
이제 위의 풀 소스를 보도록 합시다.
------------------------------------------------------------------------
/*
automata.c --
오토마타를 사용한 문자열 검색
검색대상 문자열에서 하나의 문자를 검색해 나갈때 마다 미리 만들어진
오토마타 테이블의 값을 참조하면서 비교
modified by Han donghun . 1997.1.16.
*/
#include <stdio.h>
#include <string.h>
#define MAX_LEN 50
#define NSIGMA 2
char DELTA[6][NSIGMA];
char table[NSIGMA] = {'0','1'};
/* p[] 가 s[]의 뒷부분과 일치하면 1을 되돌리고, 아니면 0을 되돌린다.*/
int is_suffix(char p[], char s[]) {
int pl, sl;
int i, j;
pl = strlen(p);
sl = strlen(s);
if (pl > sl) return 0;
for (i = pl - 1, j = sl - 1; i >= 0; i--, j--)
if (p[i] != s[j]) return 0;
return 1;
}
/* 문자열 s[]의 처음부터 k개를 t[]로 복사함 */
char *substr(char s[], char t[], int k) {
int i;
for (i = 0; i < k; i++)
t[i] = s[i];
t[i] = '\0';
return t;
}
/* 전이 함수를 만드는 함수 */
void make_transition(char p[], char delta[][NSIGMA]) {
int q; /* 상태 */
int i, j;
int pl; /* p 문자열의 길이 */
char pq[MAX_LEN], pj[MAX_LEN]; /* 부분 문자열을 저장할 임시공간 */
pl = strlen(p);
for (q = 0; q < pl; q++)
for (i = 0; i < NSIGMA; i++) {
substr(p, pq, q); /* p[0..q]a 를 만드는 과정 */
pq[j = strlen(pq)] = table[i];
pq[++j] = '\0';
/* 최대의 접미어가 되는 j+1을 찾음 */
while (!is_suffix(substr(p, pj, j), pq)) j--;
delta[q][i] = j; /* 전이 함수 설정 */
}
}
int automata_strsch(char s[], char p[]) {
int pl, sl;
int i;
int q = 0;
pl = strlen(p);
sl = strlen(s);
make_transition(p, DELTA);
for (i = 0; i < sl; i++) {
q = DELTA[q][s[i] - '0'];
if (q == pl) return i-pl+1;
}
return -1;
}
void main() {
char *search = "110010";
char *src = "11000110011010110010";
int index;
index = automata_strsch(src, search);
printf("string : %s\nsearch string : %s\nfind index = %d\n",
src, search, index);
printf("answer string : %s\n", src + index);
}
----------------------------------------------------------------------
테스트 해보시면 잘 동작하는 것을 볼 수 있을 겁니다.
다음 시간에는 오토마타를 사용한 한글입력기를 간략히 살펴보겠습니다.
그럼.
ddoch 한동훈
#1810 시삽 (김성대 )
[강좌] 오토마타 이야기 (3) 0 05/14 14:05 39
5. 한글과 오토마타
어설픈 설명이지만 저번 강좌까지 어느 정도 이해를 하셨다면 한글입력에 사용
되는 오토마타를 이해한다는 것은 이제 식은 죽 먹기라는 것을 먼저 말씀드립
니다. 한글입력 방법에는 2벌식과 3벌식이 있는 데, 주로 많이 쓰이는 2벌식
을 위주로 말씀드리겠습니다. 2벌식을 이해하면 3벌식도 무척이나 쉽습니다.
하지만 진보적 기능을 추가하려면 조금 복잡해진다는 것을 염두에 두시길..
지금 부터는 "컴퓨터 속의 한글"에 나오는 방식을 사용하겠습니다. 비교적
기본적이고 괜찮은 것 같습니다.
3벌식은 입력되는 글쇠가 자판에 초성, 중성, 종성이 구별되어 있으나, 2벌식
은 구별되어 있지 않고, 'ㄱ'이라도 초성도 될 수 있고, 종성도 될 수 있습니
다. 따라서 2벌식에서는 입력되는 글쇠가 자음인지 모음인지가 중요해집니다.
그래도 일단 최종적으로는 초성, 중성, 종성을 조합하여야 하는 관계로 일단
가상 한글 낱자모 코드를 만들어 두는 것이 편리합니다.
[표 3]
-----------------------------------------------------------------------
초 성 중 성 종 성
-----------------------------------------------------------------------
82 ㄱ A3 ㅏ C2 ㄱ
83 ㄲ A4 ㅐ C3 ㄲ
84 ㄴ A5 ㅑ C4 ㄱㅅ
85 ㄷ A6 ㅒ C5 ㄴ
86 ㄸ A7 ㅓ C6 ㄴㅈ
87 ㄹ AA ㅔ C7 ㄴㅎ
............. ............... ...............
----------------------------------------------------------------------
[출전 : 컴퓨터속의 한글 317쪽] 16진수 표기
(위에서 중성인 경우에는 A7에서 AA로 뛰어버리는 데 아래의 "상용 조합형
한글 코드표" 에서 해당 글자가 없기 때문입니다. )
구체적인 상세한 내용은 직접 다 적어두지는 않겠습니다. 강좌의 목적은 모든
것을 다 설명하자는 것이 아니라 핵심적이고 이해가 잘 되지 않는 부분들만
해설하자는 것이므로 자세한 사항은 해당 자료를 보시기 바랍니다.
아마도 한글출력기를 완성해 보신 분이라면 "상용 조합형 한글 코드표"를 마르
고 닮도록 보셨을 겁니다. 아래처럼 생긴 것입니다. 위의 가상코드표는 편의
적으로 만들어 진 것이지만, 아래의 코드표는 규약입니다.
[표 4]
-----------------------------------------------------------------------
코 드 초 성 중 성 종 성
-----------------------------------------------------------------------
0 / 00000b . . .
1 / 00001b 채움 . 채움
2 / 00010b ㄱ 채움 ㄱ
3 / 00011b ㄲ ㅏ ㄲ
4 / 00100b ㄴ ㅐ ㄱㅅ
........... ........... .......... ...........
-----------------------------------------------------------------------
[출전 : 컴퓨터속의 한글 123쪽]
위와 마찬가지로 "ㄱㅅ" 같은 것은 쌍종성인데, 글자 입력이 곤란한 관계로
띄워져 있습니다.
예전에 SVGAlib 강좌를 하면서 한글출력의 기본적인 사항만 말씀드린 적이
있는 데, 다시 한번 말씀드리겠습니다. 한글은 기본적으로 2바이트로 이루어
지며 첫바이트는 0x80이상입니다. 0x80, 즉 아스키코드 128 미만은 일반적인
영문자를 표현하는 데 사용됩니다. 비교적 쓰이지 않는 128 이상을 한글의
첫바이트로 하고 둘째바이트는 무조건 한글 둘째바이트로 취급을 합니다.
앞서도 말씀드렸지만 참고로, 완성형은 둘째바이트도 128 이상이나 조합형은
둘째바이트가 128미만으로 'a'와 같은 영문자 일수도 있습니다. 이것은 조합
형의 원리에서 야기되는 문제로 조금 골치아픈 문제를 야기시킬 수도 있습니
다. '각'이라는 글자를 조합형으로 쳐놓고 바이너리 에디터로 살펴보면,
88 62 (16진수)
일반적으로 한글에디터에서 한글임을 인식하는 방법은 처음부터 읽어나가다
가 0x80 이상 되면 한글로 취급하고 다음 바이트는 검사 할 필요도 없이 둘
째 바이트로 취급합니다. 완성형은 그냥 이 값을 가지고 코드표에서 찾아오
면 그만이지만 조합형은 초성값, 중성값, 종성값으로 분리를 해서 각각의
글자모양을 찾아와서 조립을 해야 합니다.
0x88 <<8 + 0x62 = 0x8862
일단 먼저 이렇게 앞바이트를 8비트 위로 밀어버리고 뒤의 바이트를 보내서
코드 조립을 합니다. 다음 분리를 합니다.
0x8862 = 1000 1000 0110 0010 b
최상위 비트는 0x80값이므로 한글임을 구별하는 비트입니다. 일단 이것은 제
외하고 나머지 15개 비트를 다섯개씩 쪼개서 초성, 중성, 종성 코드로 삼는
것입니다.
최상위 초성 중성 종성
비트
1 00010 00011 00010 = 0x8862
ㄱ ㅏ ㄱ = 각
방금 위에서 예를 들은 "상용 조합형 한글코드표"에서찾아보시면 쉽게 답이
나옵니다.
그럼, [표 3]과 [표 4]의 차이점은 무엇인가에 대해서 잠시 이야기를 하겠습
니다. [표 3]은 임의적으로 만든 표이긴 하지만 나름대로의 깊은 뜻이 있습
니다. [표 3]의 "한글 낱자모 코드"는 [표 4]의 "상용 조합형 한글 코드표"
에 초성은 0x80, 중성은 0xA0, 종성은 0xC0을 각각 더한 것입니다. 이렇게
[표 3]을 만든 것은 2가지 이유가 있어 보입니다.
첫째는, 한글입력에서의 문제입니다. 애시당초 컴퓨터에서는 다중 바이트
언어권을 위한 배려가 없는 관계로 소프트웨어 적인 측면이나 한글카드를
사용할 경우를 제외한다면, 한글입력 이라는 것은 개념적인 이야기 일 뿐
입니다. 어떤 이야기냐 하면, 'a'를 키보드에서 누를 때, 키보드는 'a'에
해당하는 스캔코드와 아스키코드를 발생시킬 뿐이지 'ㅁ'으로 인식하는 것
은 해당 한글 입력기의 역할이라는 것입니다. 즉, 프로그램 내부적으로 설
정하거나 사용자가 변경할 수 있는 [영문],[한글] 상태에 따라 입력기에서
는 영문자로 처리하느냐 한글낱자로 처리하느냐를 결정하는 것입니다. 따라
서 입력기에서는 'a', 'Z'등과 같은 128미만의 영문자 아스키코드와 한글낱
자를 구분하기 위해서 한글낱자에게도 128이상의 값들을 부여해주는 것이 편
리합니다. [표 3] 에 보시면 모든 한글낱자의 가상코드값이 128이상인 것을
볼 수 있습니다.
둘째는, 초성, 중성, 종성 이나 자음, 모음 임을 가리기 위한 비트연산에서
구별을 편리하게 하고자는 의도도 있는 것으로 보입니다.
초성 : 0x82 1000 0010b
.... .......
0x94 1001 0100b
중성 : 0xA3 1010 0011b
.... .......
0xBD 1011 1101b
종성 : 0xC2 1100 0010b
.... .......
0xDD 1101 1101b
초성, 중성, 종성의 6, 5번째 비트값이 각각 00, 01, 10으로 다 다르기 때문에
0x60 ( 0110 0000b)로 &연산을 하면 6, 5번째 비트는 00, 01, 10으로 나오는데,
그 값은 0x00, 0x20, 0x40으로 되어 초성, 중성, 종성임을 아주 편리하게 알아
낼 수 있다는 것입니다.
이제 글쇠입력에서 한글을 처리하는 방법을 알아보도록 하겠습니다.
테이블이 하나 필요합니다. 이부분은 소스파일에 들어가는 일반적인 배열입니
다. 일단 한번 보시죠..
/* ---------------------------------------------------------------------
두벌식 한글 자판 배열 표
한글입력상태라도 영어대문자에 해당하는 글쇠를 누를 경우 대응하는
한글글쇠가 없을 경우 그냥 영문코드를 돌려준다.
0x20(공백글쇠) 부터 인덱스를 시작한다.
--------------------------------------------------------------------- */
static byte hanKbdTable2[] = {
0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, /* !"#$%&' */
0x28, 0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x2E, 0x2F, /* ()*+,-./ */
0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, /* 01234567 */
0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F, /* 89:;<=>? */
0x40, 0x41, 0x42, 0x43, 0x44, 0x86, 0x46, 0x47, /* @ABCDEFG */
0x48, 0x49, 0x4A, 0x4B, 0x4C, 0x4D, 0x4E, 0xA6, /* HIJKLMNO */
0xAC, 0x8A, 0x83, 0x53, 0x8C, 0x55, 0x56, 0x8F, /* PQRSTUVW */
0x58, 0x59, 0x5A, 0x5B, 0x5C, 0x5D, 0x5E, 0x5F, /* XYZ[\]^_ */
0x60, 0x88, 0xBA, 0x90, 0x8D, 0x85, 0x87, 0x94, /* `abcdefg */
0xAD, 0xA5,0xA7, 0xA3, 0xBD, 0xBB, 0xB4, 0xA4, /* hijklmno */
0xAA, 0x89, 0x82, 0x84, 0x8B, 0xAB, 0x93, 0x8E, /* pqrstuvw */
0x92, 0xB3, 0x91, 0x7B, 0x7C, 0x7D, 0x7E, 0x7F /* xyz{|}~ */
};
-----------------------------------------------------------------------
유심히 쳐다보면 알듯알듯 하면서도 잘 이해가 안되실 겁니다. 저는 이것을
이해하는 데 20분이 걸리더군요. 여러분들은 2분만으로 충분하실 겁니다.
일단 배열크기는 8x12 = 96개 입니다. 즉, 일반적으로 128 미만의 아스키문자
중 키보드로 타이핑 할수있는 것은 다 나왔다고 보시면 됩니다. 인덱스는
아스키코드대로 순서대로 되어 있으며 공백글쇠부터 시작합니다. 자, 이제
아스키코드표를 어디서 구해서 맞춰봅시다. 눈동작만으로도 이해하실 수 있
으신 분은 그냥 보셔도 되겠습니다.
일단은 글쇠가 들어오면 [한글], [영문] 입력상태를 채크합니다. 한글영문
상태는 전역변수로서 보통 선언하며 0은 영문, 1은 한글로 정의하며 영문으로
초기화를 많이 합니다. 자, 이제 영문입력모드라고 가정합니다. 그래서
"linux"라고 타이핑하고 싶어서 글쇠를 하나씩 쳤습니다. 사용자 함수에서는
현재 영문입력모드므로 한글로 변환할 필요없이 그냥 아스키코드를 반환해서
출력루틴을 불러서 찍어버리면 그만입니다. 그런데 이제는 마음이 변해서
"리눅스"라고 타이핑을 하겠다고 한글입력모드로 바꾼뒤 입력한다고 가정
합시다. 일단 'f'글쇠를 쳐서 'ㄹ'을 입력할 것입니다. 사용자함수에서는
현재 입력모드가 한글모드이므로 입력받은 영문글쇠값을 가지고 위의 표에
서 검사를 합니다. 'f'에 해당하는 것을 한번 찾아봅시다. 0x87값임을 금
방 찾을 수 있습니다. 이 값을 가지고 표3에서 한번 찾아봅시다. 'ㄹ'임을
알 수 있습니다. 이제 이값을 가지고 2벌식에서는 자음인지, 모음인지..
3벌식에서는 초성, 중성, 종성 중 어느것인지 판별하기 위해서 글쇠값에다
0x60을 &연산합니다. 이제 자음인지 모음인지도 알아내었으니 오타마타를
불러서 조립만 하면 됩니다.
(즉, 위의 테이블은 한글입력모드일때의 영문키에 해당하는 한글 낱자입니
다. 물론 2벌식에서 말입니다. 나중에 원코드를 찾기위해서 [표 4]로 달려
가기전에 글쇠값에서 초성은 0x80을 뺍니다. 중성, 종성도 마찬가지로 앞
에서 더한 값을 뺍니다. )
잠깐 키를 받아들이는 부분을소스로 볼까요? 제가 부분적으로 "컴퓨터속의
한글"에 나오는 소스를 수정한 것입니다.
-------------------------------------------------------------------------
#include <stdio.h>
#include "hangul.h"
static int pushedKey = 0; /* 읽어온 키나 끄집어낸 키를 저장하는 곳 */
/* ---------------------------------------------------------------------
두벌식 한글 자판 배열 표
한글입력상태라도 영어대문자에 해당하는 글쇠를 누를 경우 대응하는
한글글쇠가 없을 경우 그냥 영문코드를 돌려준다.
0x20(공백글쇠) 부터 인덱스를 시작한다.
--------------------------------------------------------------------- */
static byte hanKbdTable2[] = {
0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, /* !"#$%&' */
0x28, 0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x2E, 0x2F, /* ()*+,-./ */
0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, /* 01234567 */
0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F, /* 89:;<=>? */
0x40, 0x41, 0x42, 0x43, 0x44, 0x86, 0x46, 0x47, /* @ABCDEFG */
0x48, 0x49, 0x4A, 0x4B,0x4C, 0x4D, 0x4E, 0xA6, /* HIJKLMNO */
0xAC, 0x8A, 0x83, 0x53, 0x8C, 0x55, 0x56, 0x8F, /* PQRSTUVW */
0x58, 0x59, 0x5A, 0x5B, 0x5C, 0x5D, 0x5E, 0x5F, /* XYZ[\]^_ */
0x60, 0x88, 0xBA, 0x90, 0x8D, 0x85, 0x87, 0x94, /* `abcdefg */
0xAD, 0xA5, 0xA7, 0xA3, 0xBD, 0xBB, 0xB4, 0xA4, /* hijklmno */
0xAA, 0x89, 0x82, 0x84, 0x8B, 0xAB, 0x93, 0x8E, /* pqrstuvw */
0x92, 0xB3, 0x91, 0x7B, 0x7C, 0x7D, 0x7E, 0x7F /* xyz{|}~ */
};
/* ---------------------------------------------------------------------
세벌식 한글 자판 배열 표
초성, 종성이 서로 독립적인 코드를 가진다.
--------------------------------------------------------------------- */
static byte hanKbdTable3[] = {
0x20, 0xD8, 0x22, 0x23, 0x24, 0x25, 0x26, 0x92, /* !"#$%&' */
0x28, 0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x2E, 0xAD, /* ()*+,-./ */
0x91, 0xDD, 0xD6, 0xD3, 0xB3, 0xBA, 0xA5, 0xAC, /* 01234567 */
0xBC, 0xB4, 0x3A, 0x89, 0x32, 0x3D, 0x33, 0x3F, /* 89:;<=>? */
0x40, 0xC8, 0x21, 0xCB, 0xCA, 0xDA,0xC3, 0x3B, /* @ABCDEFG */
0x27, 0x38, 0x34, 0x35, 0x36, 0x31, 0x30, 0x39, /* HIJKLMNO */
0x3E, 0xDC, 0xA6, 0xC7, 0x3A, 0x37, 0xD0, 0xDB, /* PQRSTUVW */
0xD4, 0x3C, 0xD9, 0x5B, 0x5C, 0x5D, 0x5E, 0x5F, /* XYZ[\]^_ */
0x60, 0xD7, 0xB4, 0xAA, 0xBD, 0xAB, 0xA3, 0xBB, /* `abcdefg */
0x84, 0x88, 0x8D, 0x82, 0x8E, 0x94, 0x8B, 0x90, /* hijklmno */
0x93, 0xD5, 0xA4, 0xC5, 0xA7, 0x85, 0xAD, 0xC9, /* pqrstuvw */
0xC2, 0x87, 0xD1, 0x7B, 0x7C, 0x7D, 0x7E, 0x7F /* xyz{|}~ */
};
/*버퍼에 입력된 키가 있으면 그 값을 돌려주고 없으면 0을 돌려준다. */
int hinkeybuf(void) {
return pushedKey ? pushedKey : 0;
}
/* 중간 저장고에 키를 밀어넣는다. */
void hputkey(int key) {
pushedKey = key;
}
/* 입력된 값으로 한글값이나 여타의 키로 변환한다. */
int hconvertkey(int key) {
byte *hanKbdTable; /* 두벌식 또는 세벌식 한글 자판 배열표를 가르킬 포인터 */
/* 한글입력상태가 아니거나 특수제어키나 확장키일 경우 그냥 반환 */
if (hanMode[HAN_ENG_MODE] == ENG_INPUT || key <= 32 || key > 127)
return key;
/* 두벌식, 세벌식 테이블을 참조하여 해당인덱스의 코드를 반환 */
hanKbdTable = (hanMode[HAN_JAPAN] == DUBEL_TYPE) ? hanKbdTable2 : hanKbdTabl
e3;
return hanKbdTable[key-32];
}
/* 키 입력을 받는다. */
int hgetkey() {
int key;
if (pushedKey) { /* 중간 저장고에 키가 있다면 */
key = pushedKey; /* 그 값을 가져오고 0으로 설정한다. */
pushedKey = 0;
} else {
key = hgetch(); /* 저장고에 키가 없다면 새로 입력을 받는다. */
/* 한글입력을 받는다면키값을 그에 맞게 변환하고 아니면 그냥 반환한다. */
key = hconvertkey(key);
}
return key;
}
-----------------------------------------------------------------------------
주석이 있으니 쉽게 이해가 갈것입니다. 그러니까 hgetkey()가 여기서는 제일
아래에서 글을 입력받습니다. hgetch()는 제가 SVGAlib에서 통일적으로 글쇠
를 받고자 만든 함수입니다. hputkey(key)는 key를 저장고에 밀어놓기 위한
것인데, 이유는 한글조립시 '갑'이라는 글자가 들어올때 여기까지도 완성된
글이라 보기 어려운데, 'ㅅ'이 하나 더 들어와서 쌍종성을 이룰 수 도 있기
때문이며 'ㅡ'가 들어올경우 '갑'의 'ㅂ'을 빼서 다음 글자로 'ㅡ'와 같이
넘겨주기 위해서 필요한 저장고 입니다. hanMode[3]은 제가 만들어둔 일상
적인 '영문 한글 토글', '2벌 3벌토글', '조합완성토글'을 담는 상태배열
입니다. 그리고 2벌식인지 3벌식인지도 참조해서 해당 테이블에서 값을 가
져와야 합니다. key에서 32를 뺀것은 위에서도 설명했듯이 hanKbdTable배
열이 공백글쇠(32)를 0으로 인덱스화 했기 때문입니다.
여기까지가 한글낱자를 입력받는 부분입니다. 이제부터 간단하게 한글낱자를
조립하는 오토마타를 선을 보이겠습니다. 미리 양해를 구해야 할 사항은
텍스트환경이라 그림을 잘 그릴 수 없는 관계로 미려한 그림은 해당 자료를
참조하시기 바랍니다. 앞강좌에서 오토마타를 어느정도 이해를 하셨다면
한글오토마타에서 어떻게 활용되는지 쉽게 이해하실 수 있습니다.
2벌식의 한글조립상태
enum HAN_STATUS {
HS_START,
HS_CHOSUNG,
HS_JOONGSUNG, HS_DJOONGSUNG,
HS_JONGSUNG, HS_DJONGSUNG,
HS_END1, HS_END2
};
2벌식에서 왜 상태가 8개가 되는 지 간단히 먼저 보죠.
실제로 조립되는 예만 한두어개 생각해보면 간단합니다.
'왔' -- 초성('ㅇ')하나, 중성('ㅗ','ㅏ')2개, 종성('ㅅ','ㅅ')2개
최대로 많이 조합될 수 있는 경우입니다. 2벌식에서는 보편적으로 초성을
두번으로 나누어 입력할 수 없습니다. 표준적인 경우에는 그렇지만 아래아
한글 같은 경우는 오토마타를 초성을 두단계로 쪼개기도 하죠. 즉, 'ㄱ',
다음에 'ㄱ'을 또 입력시키면 'ㄲ'으로 인식하기도 합니다.
그런데 왜 END가 붙은 게 두개인가.. 이문제는 2벌식의 특성때문에 그렇
습니다. 앞서 예를 든 글자 "갑"을 현재 조립하고 있다고 했을때 'ㅎ'이
들어올지 'ㅡ'가 들어올지 모르는 상태입니다. 'ㅎ'이 들어오면 이것은 '갑'
글자의 종성에 추가가 될수 없는 글자입니다. 따라서 스택을 통하여 'ㅎ'하
나를 다음 글자조립을 위해서 넘겨줍니다. 'ㅡ'가 들어올경우에는 문제가 달
라집니다. 즉, '가브'가 형성됩니다. 즉, '갑'에서 'ㅂ'을 빼오고 'ㅡ'까지
하나 더 스택에 넘겨주게 됩니다. 즉, 2개를 넘겨줍니다. 이렇게 다음글자로
넘겨주는 글자갯수가 2벌식에서는 다르기 때문에 종료상태가 2개로 되는 것
입니다. 잠깐 3벌식의 경우를 살펴보면 초성, 중성, 종성이 명확히 분리가
되어 있는 관계로 '갑'다음에 'ㅡ'가 오더라도 '갑'의 'ㅂ'을 빼가지 않습
니다. 'ㅂ'은 종성이지 초성이 아니기 때문이죠. 따라서 3벌식에서는 종료
상태가 하나만으로도 충분합니다.
이제 몇가지 대표적인 글자를 입력받을 경우에 한글조합상태가 어떻게 변
하는 지 살펴보겠습니다.
'리눅스'
------------------------------------------------
입력된 낱자 조합된 글자 한글조합상태
------------------------------------------------
HS_START
'ㄹ' 'ㄹ' HS_CHOSUNG
'ㅣ' '리' HS_JOONGSUNG
'ㄴ' 'ㄴ' HS_CHOSUNG
'ㅜ' '누' HS_JOONGSUNG
'ㄱ' '눅' HS_JONGSUNG
'ㅅ' 'ㅅ' HS_CHOSUNG
'ㅡ' '스' HS_JOONGSUNG
------------------------------------------------
한글낱자입력에 따른 한글조합상태의 변화를 너무나도 쉽게 알수 있을 것
입니다. 한글오토마타는 저번강좌에서 설명한 것과 같은 2차원 상태변이
함수로 처리하는 것보다는 간단히 각경우에 따른 CASE문을 사용하면 쉽
게 처리할 수 있습니다.
(하이텔이 500라인이 한계인데 소스를 올릴려니 안되겠네요. 다음편으로
넘겨야 할 것 같습니다. ^^)
#1811 시삽 (김성대 )
[강좌] 오토마타 이야기 (4) 마지막 0 05/14 14:05 39
--------------------------------------------------------------------------
2 벌 식 한글 오토마타
--------------------------------------------------------------------------
#include <stdio.h>
#include "hangul.h"
#define CONSONANT 0
#define VOWEL 1
enum HAN_STATE {
HS_START,
HS_CHOSUNG,
HS_JOONGSUNG, HS_DJOONGSUNG,
HS_JONGSUNG, HS_DJONGSUNG,
HS_END1, HS_END2
};
/* ---------------------------------------------------------------------
HS_END1과 HS_END2가 다른 점은 HS_END2는 한글낱자가 조합되고 있는 과
정에 모음이 들어왔을 때는 이전에 들어온 것 중에서 제일 마지막에 입력
된 것이 자음이라면 자음을 하나빼내서 다음 글자로 넘겨줘야 하기 때문
에 현재 입력된 글자와 빼낸 글자 2개를 넘겨줘야한다.
반면에 HS_END1은 글자가 조합되고 있는 과정에서 이전에 입력된 것이
모음일 경우 모음이 다시 들어 오더라도 이전 모음을 빼낼 이유가 없으
니 새로 들어온 모음 하나만 다음글자로 넘기면 된다. 그리고 더이상 조
합될 수 없는 자음이 들어올 경우에는 그 자음 하나만 다음글자로 넘기
면 된다. 따라서 HS_END2는 글자2개를 출력스택에 넘기고 HS_END1은 하나
만 출력스택에 넘기는 점에서 다르게 작동한다.
--------------------------------------------------------------------- */
static int tempUnionCode;
static int oldKey;
static int keyCode;
/* 겹모음을 이루는 지를 검사한다. 찾았으면 해당하는 코드를 돌려주고
아니면 0을 돌려준다. */
static int joongsungPair(void) {
static byte dJoongTable[7][3] = {
{ 0xad, 0xa3, 0xae }, /* ㅗ, ㅏ, ㅘ */
{ 0xad, 0xa4, 0xaf }, /* ㅗ, ㅐ, ㅙ */
{ 0xad, 0xbd, 0xb2 }, /* ㅗ, ㅣ, ㅚ */
{ 0xb4, 0xa7, 0xb5 }, /* ㅜ, ㅓ, ㅝ */
{ 0xb4, 0xaa, 0xb6 }, /* ㅜ, ㅔ, ㅞ */
{ 0xb4, 0xbd, 0xb7 }, /* ㅜ, ㅣ, ㅟ */
{ 0xbb, 0xbd, 0xbc } /* ㅡ, ㅣ, ㅢ */
};
int i;
/* 이전에 입력된 키와 현재 입력된 키를 겹모음 테이블에서 */
/* 검색한다. */
for (i = 0; i < 7; i++) {
if (dJoongTable[i][0] == oldKey && dJoongTable[i][1] == keyCode)
return ((keyCode = dJoongTable[i][2]));
}
return 0;
}
/* 겹받침을 이루는 지 검사한다. 찾았으면 해당하는 키를 돌려주고
아니면 0을 돌려준다. */
static int jongsungPair(void) {
static byte dJongTable[11][3] = {
{ 0x82, 0x8b, 0xc4 }, /* ㄱ, ㅅ*/
{ 0x84, 0x8e, 0xc6 }, /* ㄴ, ㅈ*/
{ 0x84, 0x94, 0xc7 }, /* ㄴ, ㅎ*/
{ 0x87, 0x82, 0xca }, /* ㄹ, ㄱ*/
{ 0x87, 0x88, 0xcb }, /* ㄹ, ㅁ*/
{ 0x87, 0x89, 0xcc }, /* ㄹ, ㅂ*/
{ 0x87, 0x8b, 0xcd }, /* ㄹ, ㅅ*/
{ 0x87, 0x92, 0xce }, /* ㄹ, ㅌ*/
{ 0x87, 0x93, 0xcf }, /* ㄹ, ㅍ*/
{ 0x87, 0x94, 0xd0 }, /* ㄹ, ㅎ*/
{ 0x89, 0x8b, 0xd4 } /* ㅂ, ㅅ*/
};
int i;
/* 이전에 입력된 키와 현재 입력된 키를 겹받침 테이블에서 찾아서
있는지를 검사한다. */
for (i = 0; i < 11; i++) {
if (dJongTable[i][0] == oldKey && dJongTable[i][1] == keyCode)
return (keyCode = dJongTable[i][2]);
}
return 0;
}
/********************************************************************
두벌식 오토마타
********************************************************************/
int hanAutomata2(int key) {
/*--------------------------------------------------------------------
인 수 : key = 입력된 키 코드
반환값 : 한 글자의 조합이 끝나면 1을, 계속 조합중이면 0을,
완성된 글자의 코드는 입력 스택의 가장 마지막에서
구할 수 있다.
동작 :
--------------------------------------------------------------------*/
int chKind, canBeJongsung = FALSE;
/* 초성코드에 대응하는 종성 코드 */
static byte Cho2Jong[] = {
0xc2, /* 기역 */
0xc3, /* 쌍기역 */
0xc5, /* 니은 */
0xc8, /* 디귿 */
0x00, /* 쌍디귿 (해당 없음) */
0xc9, /* 리을 */
0xd1, /* 미음 */
0xd3, /* 비읍 */
0x00, /* 상비읍 (해당 없음) */
0xd5, /* 시옷 */
0xd6, /* 쌍시옷 */
0xd7, /* 이응 */
0xd8, /* 지읒 */
0x00, /* 쌍지읒 (해당 없음) */
0xd9, /* 치읓 */
0xda, /* 키읔 */
0xdb, /* 티읕 */
0xdc, /* 피읖區 */
0xdd /* 히읗 */
};
/* ---------------------------------------------------------------------
입력된 낱자가 어떤 형태인가를 규정하고 이전의 한글입력상태와 조합된
코드를 얻어오는 오토마타의 작업준비 부분
--------------------------------------------------------------------- */
/* 글쇠가 모음일 경우에는 01100000b 로 &연산을 하면 00100000b가 된다. */
if ((key & 0x60) == 0x20) {
chKind = VOWEL; /* 모음 */
} else {
chKind = CONSONANT; /* 그 이외에는 자음 */
/* 쌍디귿, 쌍비읍, 쌍지읒은 받침으로 올 수 없다. */
if (!(key == 0x86 || key == 0x8A || key == 0x8F))
canBeJongsung = TRUE;
}
/* 만일 한글이 입력되고 있다면 이전에 저장된 스택에서 조합된
코드와 입력된 글쇠를 가져온다. */
if (tempHanState) {
tempUnionCode = inStack[inSP - 1].unionCode;
oldKey = inStack[inSP - 1].key;
} else {
/* 처음이라면..*/
/* 0x8441은 각 초성, 중성, 종성의 채움문자의 OR연산결과임 */
tempUnionCode = 0x8441;
oldKey = 0;
}
keyCode = key; /* 작업할 keyCode로 복사 */
/* ---------------------------------------------------------------------
이전의 한글이 조합된 상태 (unionCode 또는 tempUnionCode)와 현재 입력된
글자가 어떤 형태인가에 따라 조합상태를 다시 결정짓는 오타마타 주요부분
--------------------------------------------------------------------- */
switch (tempHanState) {
case HS_START : /* 한글입력이 처음이고 */
if (chKind == CONSONANT) /* 자음이 들어왔다면 초성상태로 */
tempHanState = HS_CHOSUNG;
else /* 모음이라면 중성상태로 */
tempHanState = HS_JOONGSUNG;
break;
case HS_CHOSUNG : /* 초성이 이미 입력이 되었고 */
if (chKind == VOWEL) /* 모음이 들어왔다면 */
tempHanState = HS_JOONGSUNG; /* 중성상태로 돌진!! */
else
/* 2벌식에는 복초성을 두번으로 나누어 입력할 수 없다. */
/* 따라서 초성이 들어온 상태에서 초성이 다시 들어온다면 */
/* 당연히 글자조합을 끝을 낸다. */
tempHanState = HS_END1;
break;
case HS_JOONGSUNG : /* 중성이 이미 들어와 있고 */
if (canBeJongsung) /* 종성이 될 수 있는 놈이라면 */
tempHanState = HS_JONGSUNG; /* 종성상태로 발전한다. */
/* 중성이 들어왔다면 겹모음을 이룰 수 있는 지를 검사해서
겹모음이 될 수 있으면 복중성상태로 간다. 이도 저도 아니
면 끝으로 간다. */
else if (joongsungPair())
tempHanState = HS_DJOONGSUNG;
else
tempHanState = HS_END1;
break;
case HS_DJOONGSUNG : /* 겹모음을 이루었고 */
if (canBeJongsung) /* 종성이 될 수 있는 놈이라면 */
tempHanState = HS_JONGSUNG; /* 종성상태로 ... */
else
/* 모음이나 종성이 될 수 없는 자음은 겹모음상태에서 받아들일 */
/* 수 없다. */
tempHanState = HS_END1;
break;
case HS_JONGSUNG : /* 종성을 이루고 있고 */
/* 자음이 들어와서 겹자음을 이룰 수 있는 놈이라면 */
/* 복종성상태로 간다. */
if (chKind == CONSONANT && jongsungPair())
tempHanState = HS_DJONGSUNG;
/* 만일 모음이 들어온다면 끝2로 간다. */
else if (chKind == VOWEL)
tempHanState = HS_END2;
/* 복종성을 이룰 수 없는 자음이라면 끝으로 간다. */
else
tempHanState = HS_END1;
break;
case HS_DJONGSUNG : /* 복종성을 이루고 있고 */
if (chKind == VOWEL) /* 모음이 들어왔다면 당연히 끝2로 */
tempHanState = HS_END2;
else
tempHanState = HS_END1; /* 그외에는 안보고도 끝1로 */
break;
}
/* ---------------------------------------------------------------------
한글낱자를 조합해서 코드를 얻는 곳이다. 부분적으로 뒤에서는 스택조정
도 한다.
초성코드에서 0x80을 빼면 순수한 조합형 초성코드가 나오는 데
여기서 10비트를 왼쪽으로 밀어버리면 조합할 수 있는 상태가 된다.
이전의 조합된 코드에서 1000 0011 1111 1111 을 &연산을 하면 초성
부분을 깨끗이 지울 수 있다. 이 둘을 OR연산하면 원하는 조합된
코드를 얻을 수 있다.
마찬가지로 중성에서 0xA0을 빼면 순수한 중성코드를 얻을 수 있는 데,
여기서 왼쪽으로 5비트를 밀어버리면 당연히 조합가능한 중성코드가
나온다. 원래의 코드에 0xFC1F를 &연산한다는 것은 1111 1100 0001 1111
로 중성부분을 깨끗이 지운다는 것이고 이 둘을 OR 연산하면 원하는
코드를 얻는다.
종성에서는 조금 다르다. 2벌식에서는 초성, 종성이 따로 없으므로
자음은 모조리 초성으로 가정하고 종성에는 쌍디귿, 씽비읍, 쌍지읒
만이 올 수 없다. 따라서 처음에 초성으로 들어왔으므로 초성에 대응
하는 종성코드가 기술되어 있는 테이블에서 인덱스로 찾아야 한다.
keyCode에서 0X82를 뺀다는 것은 순수한 초성코드에서 채움문자를 제외
한 곳에서부터 인덱스를 메기겠다는 것이고 이것으로 테이블에 가서 똑
같은 모양글자의 종성코드를 가져온다.
복종성은 이미 앞의 dJongTable에서 알맞는 종성코드로 변환되었으므로
이런 과정이 필요없다. 그러고 난 다음에 0xC0을 빼서 순수 종성코드를
얻고 원래의 조합된 코드에서 1111 1111 1110 0000 을 & 연산해서 종성
코드부분을 깨끗이 해서 이둘을 OR연산한다.
--------------------------------------------------------------------- */
switch (tempHanState) { /* 한글 낱자가 입력이 되어 있을 경우에만 */
case HS_CHOSUNG : /* 초성코드 처리 */
tempUnionCode = (tempUnionCode & 0x83FF) | ((keyCode - 0x80) << 10);
break;
case HS_JOONGSUNG : /* 중성코드는 복중성과 같이 처리된다. */
case HS_DJOONGSUNG : /* 복중성 코드 처리 */
tempUnionCode = (tempUnionCode & 0xFC1F) | ((keyCode - 0xA0) << 5);
break;
case HS_JONGSUNG : /* 종성코드는 초성2종성테이블에서 변환되어야 한다. *
/
keyCode = Cho2Jong[keyCode - 0x82];
case HS_DJONGSUNG : /* 복종성 및 종성 코드 처리 */
tempUnionCode = (tempUnionCode & 0xFFE0) | (keyCode - 0xC0);
break;
case HS_END1 :
outStack[outSP++] = key; /* 현재낱자 하나만 다음으로 넘긴다. */
return TRUE;
case HS_END2 :
/* 현재 낱자를 먼저 출력스택에 넣고 이전 글쇠를 꺼집어 내서 출력
스택에 집어넣는다. 스택은 먼저 들어간 것이 나중에 나온다. */
outStack[outSP++] = key;
outStack[outSP++] = oldKey;
inSP--; /* 입력스택에서 하나를 빼같으므로 스택포인터 조정 */
return TRUE; /* 1은 완료되었음을 의미 */
}
inStack[inSP].currentHanState = tempHanState;
inStack[inSP].unionCode = tempUnionCode;
inStack[inSP++].key = key;
return FALSE; /* 아직 한글 조합중 */
}
------------------------------------------------------------------------
주석이 너무 많아서 오히려 어지러울 수도 있겠지만 잘 읽어보시면 이해가
빨리 될 것입니다. 주석에서 너무 상세히 설명이 된 것 같아 부연 설명은
하지 않아도 될 것같습니다. 처음의 상태는 HS_START에서 시작해서 입력
되는 글쇠에 따라서 상태가 변화하며 조립을 다했으면 1을, 조립중이면
0을 반환합니다. 그리고 조립이 완료되었다면 출력스택에 HS_END1, HS_END2
에 따라서 1개 내지 2개의 낱자를 밀어넣습니다.
7. 나오는 말
이상으로 부족한 설명이지만 오토마타에 대한 이야기를 마치도록 하겠습니다.
자세한 풀소스나 기능은 조만간에 정리하여 발표될 한글라이브러리 "달래"
를 참조하시기 바랍니다.
(한글라이브러리를 만들고 나서는 C++과 본래의 과제인 시스템 프로그래밍을
좀더 심도깊게 공부해 볼 계획입니다. )
힘든 강좌를 따라오신다고 수고하신 분들께 리눅스에서 한글의 완전한 처리를
위한 첫걸음이 승리하기를 빌며 이만 인사에 갈음할까 합니다.
안녕히 계시길...
ddoch 한동훈
http://imhangul.kldp.net/automata/automata.html
오토마타 이야기 1
*********************************************************************
이야기틀 : 오토마타 이야기
이야기꾼 : 한동훈 ddoch@hitel.kol.co.kr
ddoch@nownuri.nowcom.co.kr
저작권 : GPL
이야기날짜 : 1997.1.24
순 서 :
1. 들어가는 말
2. 오토마타란?
3. 간단한 예제 하나
4. 오토마타 문자열 검색법
5. 한글과 오토마타
6. 나오는 말
1. 들어가는 말...
1. 들어가는 말
요즘들어서 본의 아니게 시간이 많아서 그동안 보지 못했던 알고리즘을 공부
하게 되었습니다. 그러든 중 항상 생각만 하고 있던 한글입력기를 만드는 작업에
착수하게 되었지요. 역시 오토마타라는 알고리즘을 이해를 하고 들어가니 한글
오토마타라는 것이 우리가 알고 있는 한글조립법의 상식을 표로 그려둔 것에
지나지 않았습니다. 그래서 몇일동안뚝딱거려서 예전에 만들어둔 한글출력기
와 합쳐서 한글라이브러리를 완성했습니다. 한글입력기가 제대로 돌아가는 순
간 정말 기분은 하늘로 날라가는 것만 같았습니다. 이제는 제가 그동안 만들어
둔 재사용가능한 루틴들을 포함시키면서 패키징 작업에 들어가고 있습니다.
(괜히 저 자랑같이 되어 버렸네요.. ^^;)
저번에 리눅스동호회 번개모임에 갔을 때, 어느분이 한글오토마타에 대해서 질
문을 하셨는데 제대로 답변을 못해서 미안할 따름이었는 데, 이제 이 강좌로
갈음 할 수 있었으면 좋겠습니다.
이 강좌는 한글입력기를 구현하시고자 하는 분이나, 오토마타라는 알고리즘을
이해하시고자 하는 분들을 위해서 쓰여졌습니다. 그리고 실제 예제는 저의 한
글라이브러리 안에 있는 루틴들과, "C로 배우는 알고리즘", "컴퓨터 속의 한글"
를 참조하였음을 밝혀두겠습니다.
2. 오토마타란?
저도 예전에 그랬지만 한글오토마타와 한글입력기를 구분하지 못하시는 분들이
많이 있습니다. 한글오토마타는 오토마타라는 알고리즘을 이용해서 한글입력의
기본원리를 구현한 것이고, 한글입력기는 말그대로 한글입력을 처리하는 루틴
입니다. 한글입력기는 얼마던지 오토마타라는 알고리름을 사용하지 않고도 구
현이 가능하지만 오토마타라는 알고리름을 이용하는 것이 현재로선 가장 효율
적입니다.
3. 간단한 예제 하나
먼저, 오토마타라를 이해하기 위해서 오토마타는 아니지만 그 비슷한 예를 하나
들겠습니다.
일반적으로 한글을 처리하는 데서 많이 쓰이는, 어떤 문자열 내에서 몇번째 문
자가 영문인가? 아니면 한글 첫째 바이트인가? 둘째 바이트인가 를 알아내는
함수를 예로 들겠습니다.
한글은 2바이트로 처리되며 첫바이트는 0x80(16진수) 이상이라는 것을 잘 알고
계실 겁니다. 한글완성형은 첫바이트던 둘째 바이트던 모두 0x80이상으로 맞춰
져 있습니다만 우리가 가꿔야 할 조합형은 아쉽게도 둘째 바이트가 0x80이하인
것이 더러 있습니다. 조합형으로 "가"는 16진수로 "88 61" 로 되는 데 0x61은
소문자 'a'입니다. 즉, 어느 문자열 중에서 a가 나온다고 해서 무조건 영문자
라고만 볼 수 없다는 이야기입니다. 조합형 한글 둘째 바이트가 될 수 있다는
이야기죠.
한글이 포함된 문자열이 있다고 했을 때, 어느 위치의 바이트가 종류가 어떻게
되는 지 오토마타적 알고리즘으로 생각해봅시다. 단 문자열의 처음에는 한글둘
째 바이트로 시작해서는 안된다는 전제가 있어야 합니다.
영문자면 0, 한글 첫째바이트이면 1, 한글 둘째 바이트이면 2로 가정하겠습니다.
문자열 : char str[8] = "a각b한z"
위의 문자열에서 배열의 첨자형식으로 인덱스를 따지면, 0번째 'a'는 당연히
0이고, 1번째는 '1', 2번째는 '2', 3번째는 '0', 4번째는 '1', 5번째는 '2'...
이런 식으로 될것입니다. 즉, 상태 0은 영문자, 상태 1은 한글 첫째 바이트,
상태2는 한글둘째바이트로 하겠습니다.
128 이상 무조건
+-> 상태0 ------------------> 상태1 -----------------> 상태2
| ^ | ^ | |
| | | 128 미만 +------------------------+ |
| +---+ |
| |
+------------------------------------------------------------+
간단히 그려본 상태변화도 입니다. 문자열을 검사하기전에 상태0로
초기화를 하고나서 문자열을 처음부터 하나씩 검사를 해서 그 문자값이 128
(0x80)이상일 경우와 128미만 일 경우로 나누어 집니다.
즉, 처음의 상태0에서 128미만의 글자가 처음으로 나오면 당연히 상태0
이 되고, 128이상의 글자가 나오면 한글첫째바이트 이므로 상태1로, 다음
바이트는 안보고도 한글두째바이트로 간주해서 상태2로 넘어갑니다. 상태2
에서 128미만의 글자가 나오면 영문자(128미만의 아스키문자)로 상태0이
되고 128이상의 글자가 나오면 상태1로 됩니다. 이상태로 원하는 인덱스의
문자열이 나올때까지 계속 검사를 하면 문자의 종류를 알수 있습니다.
사실 이정도는 그냥 간단하게 해도 되지만 일부러 오토마타적 사고방식으로
풀이를 했습니다. 그림을 못그렸지만 보시면 이해가 쉬울 겁니다.
그럼, 위의 그림을 보고 한글종류를 돌려주는 함수를 작성해 보겠습니다.
함수원형 : int ishangul(unsigned char *str, int index);
인 자 : str은 검사대상 문자열, index는 배열첨자식 str내의 위치
반환 값 : 0 : 영문자 , 1 : 한글첫째바이트, 2 : 한글둘째바이트
#include <stdio.h>
#include <string.h>
#define IS_LOW_ASC 0 /* 128 미만의 아스키코드 */
#define IS_HIGH_ASC 1 /* 128 이상의 아스키코드 */
#define IS_ENGLISH 0 /* 상태 0 */
#define IS_HANGUL_FIRST 1 /* 상태 1 */
#define IS_HANGUL_SECOND 2 /* 상태 2 */
typedef unsigned char byte;
int ishangul(byte *str, int index) {
int state;
int inMode;
int key;
int i = 0;
if (strlen(str) < index + 1) return -1; /* 문자열길이가 index보다 작다면 */
state = IS_ENGLISH; /* 상태0으로 초기화 */
while ((key = *(str + i)) != '\0') { /*문자열의 끝까지 */
if (key < 128) inMode = IS_LOW_ASC;
else inMode = IS_HIGH_ASC;
switch (state) {
case IS_ENGLISH : /* 상태0이고 128이상의 문자라면 한글 첫째 */
if (inMode) state = IS_HANGUL_FIRST;
else state = IS_ENGLISH; /* 그외에는 영문자 */
break;
case IS_HANGUL_FIRST : /* 한글첫째상태라면 한글둘째 */
state = IS_HANGUL_SECOND;
break;
case IS_HANGUL_SECOND : /* 한글 둘째 상태라면 */
if (inMode) state= IS_HANGUL_FIRST; /* 128이상이라면 한글첫째 */
else state = IS_ENGLISH; /* 128미만이라면 영문자 상태 */
break;
}
if (i++ == index) break; /* 찾는 인덱스까지 검사했다면 */
}
return state; /* 한글의 종류를 리턴 */
}
아주 이해하기가 쉬울 겁니다. 때로는 조금 복잡한 것도 오토마타적 알고리즘
으로 생각하면 쉬울 때가 종종 있을 겁니다. 정확히 작동하는 지 한번 테스트
해보시기 바랍니다.
다음 시간에는 오토마타 알고리즘을 사용한 문자열 검색법을 알아보겠습니다.
ddoch 한동훈
#1809 시삽 (김성대 )
[강좌] 오토마타 이야기 (2) 0 05/14 14:05 39
3. 오토마타 문자열 검색법
오토마타의 정확한 의미는 "이산적인 입력과 출력을 가지는 시스템의 수학적
모델" 입니다. 오토마타는 5개의 항목으로 구성됩니다.
(에디터로는 표현하기 곤란한 수학적인 기호가 들어가는 관계로, 기호대신
적절한 낱말로 표현하겠습니다. )
상태집합, 초기상태, 종료상태, 입력문자집합, 상태전이 함수가 그것입니다.
좀 엉뚱하지만 재미있는 예를 하나 들겠습니다.
아릿다운 공주가 5층짜리 건물의 5층에 갇혀 있습니다. 각 1층부터 4층까지
층마다 흉칙한 괴물이 지키고 서있고, 통과하려면 죽음의 "가위바위보"를 해
서 이겨야 통과할 수 있습니다. 만일 이기면 한층위로 올라갈 수 있고, 지면
한층을 내려와야 합니다. 그런데 주인공이 낼 수 있는 경우는 오로지 "바위"
뿐입니다. 무승부가 되면 다시 가위바위보를 해야 합니다.
자, 이제 입구에서 부터 시작해서 5층까지 괴물이 가위바위보를 내는 경우에
따라 주인공은 몇층에 있는 지 생각해 봅시다.
[표 1]
-------------------------------------------------------
주인공이 있는 층 \ 괴물이 내는 가위바위보의 경우
가위바위 보
-------------------------------------------------------
입구 1층 입구 입구
1층 2층 1층 입구
2층 3층 2층 1층
3층 4층 3층 2층
4층 5층 4층 3층
5층 . . .
--------------------------------------------------------
이해가 쉽게 될 겁니다. 왼쪽은 주인공이 있는 층이고 오른쪽은 괴물이 내는
경우에 따라 달라지는 주인공이 있게 되는 층입니다. 이렇게 표를 만들어 두
면 주인공의 상황과 각 경우에 따라 어떻게 주인공의 상태가 변하는 가하는
것을 쉽게 알 수 있습니다. (예가 유치하죠? ^^;)
여기서 상태집합은 주인공이 있게 되는 층인 {입구, 1층, 2층, 3층, 4층, 5층}
입니다. 초기상태는 당연히 "입구"가 됩니다. 종료상태는 "5층"이 되겠죠?
입력문자집합은 괴물이 내는 {가위, 바위, 보}가 됩니다. 상태전이함수는
위의 표입니다. 현재의 상태에서 각 경우를 만나면 어떤상태를 얻을 수 있
다는 것이 상태전이 함수입니다. 너무 쉽죠?
즉, 간단하게 말하면 "어떤 상태가 주가 되고 외부적인 경우에 따라 그 상태가
어떻게 변하는가를 표로 나타낸 것"이 "오토마타 표"가 됩니다.
이제 이러한 오토마타 알고리즘으로 간단한 문자열을 검색해봅시다. 예를 간단
히 하기 위해서 "01"로만 예를 들었습니다.
원본 문자열 : "001011010101" : DEST
찾는 문자열 : "110101" : SEARCH
위의 경우처럼 상태전이표를 그려보면 됩니다.
상태집합 = { 0, 1, 2, 3, 4, 5, 6}
초기상태 = 0
종료상태 = 6
입력문자집합 = {'0', '1'}
상태전이함수 =
[표 2]
------------------------------------
상태\입력 '0' '1'
------------------------------------
0 0 1
1 0 2
2 3 2
3 0 4
4 5 2
5 0 5
6 . .
------------------------------------
좀 더 알아보기 쉽게 상태전이도를 나타내면 다음과 같습니다.
+--------------------+
| 1 |
1 1 V 0 1 | 0 1
q0 ---> q1 ----> q2 ----> q3 -------> q4 ------> q5 ------> q6
^ |
| | 1
+-+
(각 상태에서 q0으로 가는 것은 부분적으로 생략..)
V는 화살표입니다. ^^;
q0, q1...등은 위의 상태0, 상태1등과 같습니다.
상태집합 : 여기서의 목적은 SEARCH를 DEST에서 찾는 것이 목적입니다.
0은 초기화상태 또는 하나도 맞지 않는 상태이고, 1은 하나
의 글자가 맞는 상태입니다. 이 상태의 갯수는 SEARCH의 길
이 + 1 입니다. 상태가 6이 되면 6개의 글자가 다 맞는 것이
되고 종료해야 겠지요?
초기상태 : 당연히 0으로 초기화됩니다.
종료상태 : 6개 글자가 다 맞으면 그 위치를 돌려주면 되겠죠?
입력문자집합 : 여기서는 '0', '1'로 2개로 단순화 했습니다.
상태전이 함수 :
"110101"을 찾는다고 했으니 검색하기 전에는 상태는 0이 된다고 했습니다.
대상문자열중에서 "1"이 나온다고 하면 찾는 문자열의 앞부분과 하나가 맞으
니 상태는 1로 진전됩니다. 다시 "1"이 나오면 2개가 맞으니 상태가 2로 됩
니다. 만일 "0" 이 나온다면 "10"이므로 찾는 문자열의 앞부분과 일치되지
않으므로 상태 0이 되는 것입니다. 상태2에서 "0"을 만나면 상태3이 되고 ,
다시 "1"을 만나면 상태4가 되겠죠? 이상태에서 다시 "0"을 만난다면 문제없
이 상태5로 되겠지만 "1"을 만난다면 그간 비교된 문자는 "11011" 이 되어서
뒤의 2개의 문자가 SEARCH의 "110101"의 앞의 두개문자와 같으므로 상태는 2
가 됩니다. 이런 식으로 검색하여 상태가 6이 된다면 "110101"이 다 맞는 것
이 되어서 리턴을 하는 것이 오토마타를 사용한 문자열 검색법입니다.
자세히 보시면, 오토마타는 순전히 SEARCH에 의존합니다. 오토마타가 완성될
상태를 0에서 N개 까지 만들어 놓고, 각 들어올 수 있는 경우(여기서는 0,1)
에 따라 SEARCH를 참조하여 상태를 전진시키거나 후퇴시키는 것입니다.
만일 아스키문자를 비교한다고 하면 입력문자집합은 256개가 되어서 거대한
표나 상태전이함수를 만들어 둬야 합니다. 같은 문자열을 계속 찾는 경우에
는 아주 유용한 알고리즘이지만 SEARCH가 자주 바뀌면 바뀔 때 마다 상태
전이함수를 만들어야 하기 때문에 리소스의 낭비가 심해지게 됩니다.
"오토마타를 이용한 문자열 검색 알고리즘"의 의사코드는 다음과 같이 됩
니다.
S = "001011010101"
P = "110101"
-----------------------------------------------------------------------
q = 0; /* 상태를 0으로 초기화 */
for(i = 0; i< strlen(S); i++) { /* 문자열의 끝까지 비교 */
q = (q, S[i]); ----------- (1)
if (q == strlen(P)) return i-strlen(P)+1; ------ (2)
}
return -1;
-----------------------------------------------------------------------
(1)에서 괄호안의 q는 현재 상태이고, S[i]는 S에서 현재 비교되는 문자입니
다. 이 두값을 가지고 [표 2]에서 작성한 상태전이함수에서 다음의 상태를
가져옵니다. (2)에서 상태가 P의 길이인 6이 되면 다 맞는 결과이므로 현재
위치(i--배열첨자식)에서 P의 길이를 빼서 1을 보내면 S에서 P의 문자열이 나
타나는 처음 위치입니다.
전이함수는 실제로는 2차원 배열입니다.
#define NSIGMA 2
char DELTA[6][NSIGMA];
앞의 6은 strlen(P)인 상태의 갯수인데, [표 2]와 비교해 보시면 제일 마지막
의 상태6은 실제로없어도 되는 부분이므로 배열 6개만 잡아도 충분합니다.
뒤의 NSIGMA는 입력문자의 갯수입니다. 여기서는 '0', '1'이 올 수 있기 때문
에 2로 정의하였습니다. 실제로 이 배열은 [표 2]를 배열로 표현한 것입니다.
즉, '0', '1'을 배열의 첨자로 사용하기 위해 0, 1로 순서를 매긴다고 보면,
"DELTA[3][1]"은 상태3에서 '1'을 만났을 때를 이야기 하며 그 값은 4가 되어
야 합니다.
이제 전이함수인 2차원 배열의 값을 어떻게 구할 것인가 생각해봅시다.
P = "110101"
char pq[50], pj[50];
int q,j;
1) q = 0에서 시작한다.
2) P에서 q의 길이만큼 pq에 복사한다. (pq = "")
3) pq에 입력문자집합에 있는 것을 하나씩 pq의 뒤에 추가한다.
(pq = "0")
4) j = strlen(pq); (j = 1)
5) P에서 j만큼 pj에 복사한다. (pj = "1")
6) pj가 pq의 접미어인가? 즉, pj의 문자열이 pq의 뒤에 나타나는가?
아니면 --j만큼 P에서 pj로 문자열을 복사해서 계속 검사한다.
("1"이 "0"의 접미어? 아니다. 따라서 pj 는 이번에는 ""이 된다. j = 0
이 되고..""은 "0"의 접미어? )
7) DELTA[q][i] = j; (DELTA[0][0] = 0)
8) 2)번으로 가서 다시 반복하고 q = 1로 해서 다시 반복한다.
이해가 되는가요?
원리는 간단합니다. P에서 0개부터 5개까지 문자열을 가져와서 나올 수 있는
입력문자를 하나씩 붙여서 이것이 P에서 1개에서 6개 까지의 문자가 접미어가
되는가를 검사하는 것입니다. 곰곰히 생각해 보시길..
-----------------------------------------------------------------------
int q; /* 상태 */
int i, j;
int pl; /* 문자열 P의 길이 */
char pq[50], pj[50]; /* 문자열을 저장할 임시공간 */
pl = strlen(P);
for (q = 0; q < strlen(P); q++) { /* strlen(P) 는 6 */
for (i = 0; i < NSIGMA; i++) { /* 2차원 배열에 값을 구함 */
substr(P, pq, q); -- (1)
pq[j = strlen(pq)] = table[i]; -- (2)
pq[++j] = '\0'; -- (3)
while (!is_suffix(substr(P, pj, j), pq)) j--; -- (4)
DELTA[q][i] = j; -- (5)
}
}
-----------------------------------------------------------------------
2차원 배열 DELTA에 값을 얻기 위해서 2중 루프를 돌린다는 것은 쉽게 이해가
갈 것입니다. 여기에서 substr(P, pq, q)함수는 간단히 만든, 문자열 P에서 pq로
q의 길이만큼 복사하는 함수입니다. is_suffix(a, b)는 a가 b의 접미어이면 1을
돌려주고 아니면 0을 돌려주며 나올때까지 j를 감소시킵니다.
------------------------------------------------------------------------
char *substr(char s[], char t[], int k) {
int i;
for (i = 0; i < k; i++)
t[i] = s[i];
t[i] = '\0';
return t;
}
int is_suffix(char p[], char s[]) {
int pl, sl, i, j;
pl= strlen(p);
sl= strlen(s);
if (pl > sl) return 0;
for (i = pl -1, j = sl -1; i >= 0; i--, j--)
if (p[i] != s[i]) return 0;
return 1;
}
------------------------------------------------------------------------
상당히 어설프게 설명을 한 것 같습니다. 하지만 잘 살펴보시면 이해가 가실
겁니다. 굳이 뒷부분은 이해가 안되신다 하더라도 오토마타 원리부분만 이해
를 하셨더라도 다음으로 넘어가실 수 있을 겁니다. 이 부분을 설명드린 것은
어디까지나 오토마타라는 알고리즘에 대해서 말씀드리기 위한 것입니다.
이제 위의 풀 소스를 보도록 합시다.
------------------------------------------------------------------------
/*
automata.c --
오토마타를 사용한 문자열 검색
검색대상 문자열에서 하나의 문자를 검색해 나갈때 마다 미리 만들어진
오토마타 테이블의 값을 참조하면서 비교
modified by Han donghun . 1997.1.16.
*/
#include <stdio.h>
#include <string.h>
#define MAX_LEN 50
#define NSIGMA 2
char DELTA[6][NSIGMA];
char table[NSIGMA] = {'0','1'};
/* p[] 가 s[]의 뒷부분과 일치하면 1을 되돌리고, 아니면 0을 되돌린다.*/
int is_suffix(char p[], char s[]) {
int pl, sl;
int i, j;
pl = strlen(p);
sl = strlen(s);
if (pl > sl) return 0;
for (i = pl - 1, j = sl - 1; i >= 0; i--, j--)
if (p[i] != s[j]) return 0;
return 1;
}
/* 문자열 s[]의 처음부터 k개를 t[]로 복사함 */
char *substr(char s[], char t[], int k) {
int i;
for (i = 0; i < k; i++)
t[i] = s[i];
t[i] = '\0';
return t;
}
/* 전이 함수를 만드는 함수 */
void make_transition(char p[], char delta[][NSIGMA]) {
int q; /* 상태 */
int i, j;
int pl; /* p 문자열의 길이 */
char pq[MAX_LEN], pj[MAX_LEN]; /* 부분 문자열을 저장할 임시공간 */
pl = strlen(p);
for (q = 0; q < pl; q++)
for (i = 0; i < NSIGMA; i++) {
substr(p, pq, q); /* p[0..q]a 를 만드는 과정 */
pq[j = strlen(pq)] = table[i];
pq[++j] = '\0';
/* 최대의 접미어가 되는 j+1을 찾음 */
while (!is_suffix(substr(p, pj, j), pq)) j--;
delta[q][i] = j; /* 전이 함수 설정 */
}
}
int automata_strsch(char s[], char p[]) {
int pl, sl;
int i;
int q = 0;
pl = strlen(p);
sl = strlen(s);
make_transition(p, DELTA);
for (i = 0; i < sl; i++) {
q = DELTA[q][s[i] - '0'];
if (q == pl) return i-pl+1;
}
return -1;
}
void main() {
char *search = "110010";
char *src = "11000110011010110010";
int index;
index = automata_strsch(src, search);
printf("string : %s\nsearch string : %s\nfind index = %d\n",
src, search, index);
printf("answer string : %s\n", src + index);
}
----------------------------------------------------------------------
테스트 해보시면 잘 동작하는 것을 볼 수 있을 겁니다.
다음 시간에는 오토마타를 사용한 한글입력기를 간략히 살펴보겠습니다.
그럼.
ddoch 한동훈
#1810 시삽 (김성대 )
[강좌] 오토마타 이야기 (3) 0 05/14 14:05 39
5. 한글과 오토마타
어설픈 설명이지만 저번 강좌까지 어느 정도 이해를 하셨다면 한글입력에 사용
되는 오토마타를 이해한다는 것은 이제 식은 죽 먹기라는 것을 먼저 말씀드립
니다. 한글입력 방법에는 2벌식과 3벌식이 있는 데, 주로 많이 쓰이는 2벌식
을 위주로 말씀드리겠습니다. 2벌식을 이해하면 3벌식도 무척이나 쉽습니다.
하지만 진보적 기능을 추가하려면 조금 복잡해진다는 것을 염두에 두시길..
지금 부터는 "컴퓨터 속의 한글"에 나오는 방식을 사용하겠습니다. 비교적
기본적이고 괜찮은 것 같습니다.
3벌식은 입력되는 글쇠가 자판에 초성, 중성, 종성이 구별되어 있으나, 2벌식
은 구별되어 있지 않고, 'ㄱ'이라도 초성도 될 수 있고, 종성도 될 수 있습니
다. 따라서 2벌식에서는 입력되는 글쇠가 자음인지 모음인지가 중요해집니다.
그래도 일단 최종적으로는 초성, 중성, 종성을 조합하여야 하는 관계로 일단
가상 한글 낱자모 코드를 만들어 두는 것이 편리합니다.
[표 3]
-----------------------------------------------------------------------
초 성 중 성 종 성
-----------------------------------------------------------------------
82 ㄱ A3 ㅏ C2 ㄱ
83 ㄲ A4 ㅐ C3 ㄲ
84 ㄴ A5 ㅑ C4 ㄱㅅ
85 ㄷ A6 ㅒ C5 ㄴ
86 ㄸ A7 ㅓ C6 ㄴㅈ
87 ㄹ AA ㅔ C7 ㄴㅎ
............. ............... ...............
----------------------------------------------------------------------
[출전 : 컴퓨터속의 한글 317쪽] 16진수 표기
(위에서 중성인 경우에는 A7에서 AA로 뛰어버리는 데 아래의 "상용 조합형
한글 코드표" 에서 해당 글자가 없기 때문입니다. )
구체적인 상세한 내용은 직접 다 적어두지는 않겠습니다. 강좌의 목적은 모든
것을 다 설명하자는 것이 아니라 핵심적이고 이해가 잘 되지 않는 부분들만
해설하자는 것이므로 자세한 사항은 해당 자료를 보시기 바랍니다.
아마도 한글출력기를 완성해 보신 분이라면 "상용 조합형 한글 코드표"를 마르
고 닮도록 보셨을 겁니다. 아래처럼 생긴 것입니다. 위의 가상코드표는 편의
적으로 만들어 진 것이지만, 아래의 코드표는 규약입니다.
[표 4]
-----------------------------------------------------------------------
코 드 초 성 중 성 종 성
-----------------------------------------------------------------------
0 / 00000b . . .
1 / 00001b 채움 . 채움
2 / 00010b ㄱ 채움 ㄱ
3 / 00011b ㄲ ㅏ ㄲ
4 / 00100b ㄴ ㅐ ㄱㅅ
........... ........... .......... ...........
-----------------------------------------------------------------------
[출전 : 컴퓨터속의 한글 123쪽]
위와 마찬가지로 "ㄱㅅ" 같은 것은 쌍종성인데, 글자 입력이 곤란한 관계로
띄워져 있습니다.
예전에 SVGAlib 강좌를 하면서 한글출력의 기본적인 사항만 말씀드린 적이
있는 데, 다시 한번 말씀드리겠습니다. 한글은 기본적으로 2바이트로 이루어
지며 첫바이트는 0x80이상입니다. 0x80, 즉 아스키코드 128 미만은 일반적인
영문자를 표현하는 데 사용됩니다. 비교적 쓰이지 않는 128 이상을 한글의
첫바이트로 하고 둘째바이트는 무조건 한글 둘째바이트로 취급을 합니다.
앞서도 말씀드렸지만 참고로, 완성형은 둘째바이트도 128 이상이나 조합형은
둘째바이트가 128미만으로 'a'와 같은 영문자 일수도 있습니다. 이것은 조합
형의 원리에서 야기되는 문제로 조금 골치아픈 문제를 야기시킬 수도 있습니
다. '각'이라는 글자를 조합형으로 쳐놓고 바이너리 에디터로 살펴보면,
88 62 (16진수)
일반적으로 한글에디터에서 한글임을 인식하는 방법은 처음부터 읽어나가다
가 0x80 이상 되면 한글로 취급하고 다음 바이트는 검사 할 필요도 없이 둘
째 바이트로 취급합니다. 완성형은 그냥 이 값을 가지고 코드표에서 찾아오
면 그만이지만 조합형은 초성값, 중성값, 종성값으로 분리를 해서 각각의
글자모양을 찾아와서 조립을 해야 합니다.
0x88 <<8 + 0x62 = 0x8862
일단 먼저 이렇게 앞바이트를 8비트 위로 밀어버리고 뒤의 바이트를 보내서
코드 조립을 합니다. 다음 분리를 합니다.
0x8862 = 1000 1000 0110 0010 b
최상위 비트는 0x80값이므로 한글임을 구별하는 비트입니다. 일단 이것은 제
외하고 나머지 15개 비트를 다섯개씩 쪼개서 초성, 중성, 종성 코드로 삼는
것입니다.
최상위 초성 중성 종성
비트
1 00010 00011 00010 = 0x8862
ㄱ ㅏ ㄱ = 각
방금 위에서 예를 들은 "상용 조합형 한글코드표"에서찾아보시면 쉽게 답이
나옵니다.
그럼, [표 3]과 [표 4]의 차이점은 무엇인가에 대해서 잠시 이야기를 하겠습
니다. [표 3]은 임의적으로 만든 표이긴 하지만 나름대로의 깊은 뜻이 있습
니다. [표 3]의 "한글 낱자모 코드"는 [표 4]의 "상용 조합형 한글 코드표"
에 초성은 0x80, 중성은 0xA0, 종성은 0xC0을 각각 더한 것입니다. 이렇게
[표 3]을 만든 것은 2가지 이유가 있어 보입니다.
첫째는, 한글입력에서의 문제입니다. 애시당초 컴퓨터에서는 다중 바이트
언어권을 위한 배려가 없는 관계로 소프트웨어 적인 측면이나 한글카드를
사용할 경우를 제외한다면, 한글입력 이라는 것은 개념적인 이야기 일 뿐
입니다. 어떤 이야기냐 하면, 'a'를 키보드에서 누를 때, 키보드는 'a'에
해당하는 스캔코드와 아스키코드를 발생시킬 뿐이지 'ㅁ'으로 인식하는 것
은 해당 한글 입력기의 역할이라는 것입니다. 즉, 프로그램 내부적으로 설
정하거나 사용자가 변경할 수 있는 [영문],[한글] 상태에 따라 입력기에서
는 영문자로 처리하느냐 한글낱자로 처리하느냐를 결정하는 것입니다. 따라
서 입력기에서는 'a', 'Z'등과 같은 128미만의 영문자 아스키코드와 한글낱
자를 구분하기 위해서 한글낱자에게도 128이상의 값들을 부여해주는 것이 편
리합니다. [표 3] 에 보시면 모든 한글낱자의 가상코드값이 128이상인 것을
볼 수 있습니다.
둘째는, 초성, 중성, 종성 이나 자음, 모음 임을 가리기 위한 비트연산에서
구별을 편리하게 하고자는 의도도 있는 것으로 보입니다.
초성 : 0x82 1000 0010b
.... .......
0x94 1001 0100b
중성 : 0xA3 1010 0011b
.... .......
0xBD 1011 1101b
종성 : 0xC2 1100 0010b
.... .......
0xDD 1101 1101b
초성, 중성, 종성의 6, 5번째 비트값이 각각 00, 01, 10으로 다 다르기 때문에
0x60 ( 0110 0000b)로 &연산을 하면 6, 5번째 비트는 00, 01, 10으로 나오는데,
그 값은 0x00, 0x20, 0x40으로 되어 초성, 중성, 종성임을 아주 편리하게 알아
낼 수 있다는 것입니다.
이제 글쇠입력에서 한글을 처리하는 방법을 알아보도록 하겠습니다.
테이블이 하나 필요합니다. 이부분은 소스파일에 들어가는 일반적인 배열입니
다. 일단 한번 보시죠..
/* ---------------------------------------------------------------------
두벌식 한글 자판 배열 표
한글입력상태라도 영어대문자에 해당하는 글쇠를 누를 경우 대응하는
한글글쇠가 없을 경우 그냥 영문코드를 돌려준다.
0x20(공백글쇠) 부터 인덱스를 시작한다.
--------------------------------------------------------------------- */
static byte hanKbdTable2[] = {
0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, /* !"#$%&' */
0x28, 0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x2E, 0x2F, /* ()*+,-./ */
0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, /* 01234567 */
0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F, /* 89:;<=>? */
0x40, 0x41, 0x42, 0x43, 0x44, 0x86, 0x46, 0x47, /* @ABCDEFG */
0x48, 0x49, 0x4A, 0x4B, 0x4C, 0x4D, 0x4E, 0xA6, /* HIJKLMNO */
0xAC, 0x8A, 0x83, 0x53, 0x8C, 0x55, 0x56, 0x8F, /* PQRSTUVW */
0x58, 0x59, 0x5A, 0x5B, 0x5C, 0x5D, 0x5E, 0x5F, /* XYZ[\]^_ */
0x60, 0x88, 0xBA, 0x90, 0x8D, 0x85, 0x87, 0x94, /* `abcdefg */
0xAD, 0xA5,0xA7, 0xA3, 0xBD, 0xBB, 0xB4, 0xA4, /* hijklmno */
0xAA, 0x89, 0x82, 0x84, 0x8B, 0xAB, 0x93, 0x8E, /* pqrstuvw */
0x92, 0xB3, 0x91, 0x7B, 0x7C, 0x7D, 0x7E, 0x7F /* xyz{|}~ */
};
-----------------------------------------------------------------------
유심히 쳐다보면 알듯알듯 하면서도 잘 이해가 안되실 겁니다. 저는 이것을
이해하는 데 20분이 걸리더군요. 여러분들은 2분만으로 충분하실 겁니다.
일단 배열크기는 8x12 = 96개 입니다. 즉, 일반적으로 128 미만의 아스키문자
중 키보드로 타이핑 할수있는 것은 다 나왔다고 보시면 됩니다. 인덱스는
아스키코드대로 순서대로 되어 있으며 공백글쇠부터 시작합니다. 자, 이제
아스키코드표를 어디서 구해서 맞춰봅시다. 눈동작만으로도 이해하실 수 있
으신 분은 그냥 보셔도 되겠습니다.
일단은 글쇠가 들어오면 [한글], [영문] 입력상태를 채크합니다. 한글영문
상태는 전역변수로서 보통 선언하며 0은 영문, 1은 한글로 정의하며 영문으로
초기화를 많이 합니다. 자, 이제 영문입력모드라고 가정합니다. 그래서
"linux"라고 타이핑하고 싶어서 글쇠를 하나씩 쳤습니다. 사용자 함수에서는
현재 영문입력모드므로 한글로 변환할 필요없이 그냥 아스키코드를 반환해서
출력루틴을 불러서 찍어버리면 그만입니다. 그런데 이제는 마음이 변해서
"리눅스"라고 타이핑을 하겠다고 한글입력모드로 바꾼뒤 입력한다고 가정
합시다. 일단 'f'글쇠를 쳐서 'ㄹ'을 입력할 것입니다. 사용자함수에서는
현재 입력모드가 한글모드이므로 입력받은 영문글쇠값을 가지고 위의 표에
서 검사를 합니다. 'f'에 해당하는 것을 한번 찾아봅시다. 0x87값임을 금
방 찾을 수 있습니다. 이 값을 가지고 표3에서 한번 찾아봅시다. 'ㄹ'임을
알 수 있습니다. 이제 이값을 가지고 2벌식에서는 자음인지, 모음인지..
3벌식에서는 초성, 중성, 종성 중 어느것인지 판별하기 위해서 글쇠값에다
0x60을 &연산합니다. 이제 자음인지 모음인지도 알아내었으니 오타마타를
불러서 조립만 하면 됩니다.
(즉, 위의 테이블은 한글입력모드일때의 영문키에 해당하는 한글 낱자입니
다. 물론 2벌식에서 말입니다. 나중에 원코드를 찾기위해서 [표 4]로 달려
가기전에 글쇠값에서 초성은 0x80을 뺍니다. 중성, 종성도 마찬가지로 앞
에서 더한 값을 뺍니다. )
잠깐 키를 받아들이는 부분을소스로 볼까요? 제가 부분적으로 "컴퓨터속의
한글"에 나오는 소스를 수정한 것입니다.
-------------------------------------------------------------------------
#include <stdio.h>
#include "hangul.h"
static int pushedKey = 0; /* 읽어온 키나 끄집어낸 키를 저장하는 곳 */
/* ---------------------------------------------------------------------
두벌식 한글 자판 배열 표
한글입력상태라도 영어대문자에 해당하는 글쇠를 누를 경우 대응하는
한글글쇠가 없을 경우 그냥 영문코드를 돌려준다.
0x20(공백글쇠) 부터 인덱스를 시작한다.
--------------------------------------------------------------------- */
static byte hanKbdTable2[] = {
0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, /* !"#$%&' */
0x28, 0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x2E, 0x2F, /* ()*+,-./ */
0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, /* 01234567 */
0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F, /* 89:;<=>? */
0x40, 0x41, 0x42, 0x43, 0x44, 0x86, 0x46, 0x47, /* @ABCDEFG */
0x48, 0x49, 0x4A, 0x4B,0x4C, 0x4D, 0x4E, 0xA6, /* HIJKLMNO */
0xAC, 0x8A, 0x83, 0x53, 0x8C, 0x55, 0x56, 0x8F, /* PQRSTUVW */
0x58, 0x59, 0x5A, 0x5B, 0x5C, 0x5D, 0x5E, 0x5F, /* XYZ[\]^_ */
0x60, 0x88, 0xBA, 0x90, 0x8D, 0x85, 0x87, 0x94, /* `abcdefg */
0xAD, 0xA5, 0xA7, 0xA3, 0xBD, 0xBB, 0xB4, 0xA4, /* hijklmno */
0xAA, 0x89, 0x82, 0x84, 0x8B, 0xAB, 0x93, 0x8E, /* pqrstuvw */
0x92, 0xB3, 0x91, 0x7B, 0x7C, 0x7D, 0x7E, 0x7F /* xyz{|}~ */
};
/* ---------------------------------------------------------------------
세벌식 한글 자판 배열 표
초성, 종성이 서로 독립적인 코드를 가진다.
--------------------------------------------------------------------- */
static byte hanKbdTable3[] = {
0x20, 0xD8, 0x22, 0x23, 0x24, 0x25, 0x26, 0x92, /* !"#$%&' */
0x28, 0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x2E, 0xAD, /* ()*+,-./ */
0x91, 0xDD, 0xD6, 0xD3, 0xB3, 0xBA, 0xA5, 0xAC, /* 01234567 */
0xBC, 0xB4, 0x3A, 0x89, 0x32, 0x3D, 0x33, 0x3F, /* 89:;<=>? */
0x40, 0xC8, 0x21, 0xCB, 0xCA, 0xDA,0xC3, 0x3B, /* @ABCDEFG */
0x27, 0x38, 0x34, 0x35, 0x36, 0x31, 0x30, 0x39, /* HIJKLMNO */
0x3E, 0xDC, 0xA6, 0xC7, 0x3A, 0x37, 0xD0, 0xDB, /* PQRSTUVW */
0xD4, 0x3C, 0xD9, 0x5B, 0x5C, 0x5D, 0x5E, 0x5F, /* XYZ[\]^_ */
0x60, 0xD7, 0xB4, 0xAA, 0xBD, 0xAB, 0xA3, 0xBB, /* `abcdefg */
0x84, 0x88, 0x8D, 0x82, 0x8E, 0x94, 0x8B, 0x90, /* hijklmno */
0x93, 0xD5, 0xA4, 0xC5, 0xA7, 0x85, 0xAD, 0xC9, /* pqrstuvw */
0xC2, 0x87, 0xD1, 0x7B, 0x7C, 0x7D, 0x7E, 0x7F /* xyz{|}~ */
};
/*버퍼에 입력된 키가 있으면 그 값을 돌려주고 없으면 0을 돌려준다. */
int hinkeybuf(void) {
return pushedKey ? pushedKey : 0;
}
/* 중간 저장고에 키를 밀어넣는다. */
void hputkey(int key) {
pushedKey = key;
}
/* 입력된 값으로 한글값이나 여타의 키로 변환한다. */
int hconvertkey(int key) {
byte *hanKbdTable; /* 두벌식 또는 세벌식 한글 자판 배열표를 가르킬 포인터 */
/* 한글입력상태가 아니거나 특수제어키나 확장키일 경우 그냥 반환 */
if (hanMode[HAN_ENG_MODE] == ENG_INPUT || key <= 32 || key > 127)
return key;
/* 두벌식, 세벌식 테이블을 참조하여 해당인덱스의 코드를 반환 */
hanKbdTable = (hanMode[HAN_JAPAN] == DUBEL_TYPE) ? hanKbdTable2 : hanKbdTabl
e3;
return hanKbdTable[key-32];
}
/* 키 입력을 받는다. */
int hgetkey() {
int key;
if (pushedKey) { /* 중간 저장고에 키가 있다면 */
key = pushedKey; /* 그 값을 가져오고 0으로 설정한다. */
pushedKey = 0;
} else {
key = hgetch(); /* 저장고에 키가 없다면 새로 입력을 받는다. */
/* 한글입력을 받는다면키값을 그에 맞게 변환하고 아니면 그냥 반환한다. */
key = hconvertkey(key);
}
return key;
}
-----------------------------------------------------------------------------
주석이 있으니 쉽게 이해가 갈것입니다. 그러니까 hgetkey()가 여기서는 제일
아래에서 글을 입력받습니다. hgetch()는 제가 SVGAlib에서 통일적으로 글쇠
를 받고자 만든 함수입니다. hputkey(key)는 key를 저장고에 밀어놓기 위한
것인데, 이유는 한글조립시 '갑'이라는 글자가 들어올때 여기까지도 완성된
글이라 보기 어려운데, 'ㅅ'이 하나 더 들어와서 쌍종성을 이룰 수 도 있기
때문이며 'ㅡ'가 들어올경우 '갑'의 'ㅂ'을 빼서 다음 글자로 'ㅡ'와 같이
넘겨주기 위해서 필요한 저장고 입니다. hanMode[3]은 제가 만들어둔 일상
적인 '영문 한글 토글', '2벌 3벌토글', '조합완성토글'을 담는 상태배열
입니다. 그리고 2벌식인지 3벌식인지도 참조해서 해당 테이블에서 값을 가
져와야 합니다. key에서 32를 뺀것은 위에서도 설명했듯이 hanKbdTable배
열이 공백글쇠(32)를 0으로 인덱스화 했기 때문입니다.
여기까지가 한글낱자를 입력받는 부분입니다. 이제부터 간단하게 한글낱자를
조립하는 오토마타를 선을 보이겠습니다. 미리 양해를 구해야 할 사항은
텍스트환경이라 그림을 잘 그릴 수 없는 관계로 미려한 그림은 해당 자료를
참조하시기 바랍니다. 앞강좌에서 오토마타를 어느정도 이해를 하셨다면
한글오토마타에서 어떻게 활용되는지 쉽게 이해하실 수 있습니다.
2벌식의 한글조립상태
enum HAN_STATUS {
HS_START,
HS_CHOSUNG,
HS_JOONGSUNG, HS_DJOONGSUNG,
HS_JONGSUNG, HS_DJONGSUNG,
HS_END1, HS_END2
};
2벌식에서 왜 상태가 8개가 되는 지 간단히 먼저 보죠.
실제로 조립되는 예만 한두어개 생각해보면 간단합니다.
'왔' -- 초성('ㅇ')하나, 중성('ㅗ','ㅏ')2개, 종성('ㅅ','ㅅ')2개
최대로 많이 조합될 수 있는 경우입니다. 2벌식에서는 보편적으로 초성을
두번으로 나누어 입력할 수 없습니다. 표준적인 경우에는 그렇지만 아래아
한글 같은 경우는 오토마타를 초성을 두단계로 쪼개기도 하죠. 즉, 'ㄱ',
다음에 'ㄱ'을 또 입력시키면 'ㄲ'으로 인식하기도 합니다.
그런데 왜 END가 붙은 게 두개인가.. 이문제는 2벌식의 특성때문에 그렇
습니다. 앞서 예를 든 글자 "갑"을 현재 조립하고 있다고 했을때 'ㅎ'이
들어올지 'ㅡ'가 들어올지 모르는 상태입니다. 'ㅎ'이 들어오면 이것은 '갑'
글자의 종성에 추가가 될수 없는 글자입니다. 따라서 스택을 통하여 'ㅎ'하
나를 다음 글자조립을 위해서 넘겨줍니다. 'ㅡ'가 들어올경우에는 문제가 달
라집니다. 즉, '가브'가 형성됩니다. 즉, '갑'에서 'ㅂ'을 빼오고 'ㅡ'까지
하나 더 스택에 넘겨주게 됩니다. 즉, 2개를 넘겨줍니다. 이렇게 다음글자로
넘겨주는 글자갯수가 2벌식에서는 다르기 때문에 종료상태가 2개로 되는 것
입니다. 잠깐 3벌식의 경우를 살펴보면 초성, 중성, 종성이 명확히 분리가
되어 있는 관계로 '갑'다음에 'ㅡ'가 오더라도 '갑'의 'ㅂ'을 빼가지 않습
니다. 'ㅂ'은 종성이지 초성이 아니기 때문이죠. 따라서 3벌식에서는 종료
상태가 하나만으로도 충분합니다.
이제 몇가지 대표적인 글자를 입력받을 경우에 한글조합상태가 어떻게 변
하는 지 살펴보겠습니다.
'리눅스'
------------------------------------------------
입력된 낱자 조합된 글자 한글조합상태
------------------------------------------------
HS_START
'ㄹ' 'ㄹ' HS_CHOSUNG
'ㅣ' '리' HS_JOONGSUNG
'ㄴ' 'ㄴ' HS_CHOSUNG
'ㅜ' '누' HS_JOONGSUNG
'ㄱ' '눅' HS_JONGSUNG
'ㅅ' 'ㅅ' HS_CHOSUNG
'ㅡ' '스' HS_JOONGSUNG
------------------------------------------------
한글낱자입력에 따른 한글조합상태의 변화를 너무나도 쉽게 알수 있을 것
입니다. 한글오토마타는 저번강좌에서 설명한 것과 같은 2차원 상태변이
함수로 처리하는 것보다는 간단히 각경우에 따른 CASE문을 사용하면 쉽
게 처리할 수 있습니다.
(하이텔이 500라인이 한계인데 소스를 올릴려니 안되겠네요. 다음편으로
넘겨야 할 것 같습니다. ^^)
#1811 시삽 (김성대 )
[강좌] 오토마타 이야기 (4) 마지막 0 05/14 14:05 39
--------------------------------------------------------------------------
2 벌 식 한글 오토마타
--------------------------------------------------------------------------
#include <stdio.h>
#include "hangul.h"
#define CONSONANT 0
#define VOWEL 1
enum HAN_STATE {
HS_START,
HS_CHOSUNG,
HS_JOONGSUNG, HS_DJOONGSUNG,
HS_JONGSUNG, HS_DJONGSUNG,
HS_END1, HS_END2
};
/* ---------------------------------------------------------------------
HS_END1과 HS_END2가 다른 점은 HS_END2는 한글낱자가 조합되고 있는 과
정에 모음이 들어왔을 때는 이전에 들어온 것 중에서 제일 마지막에 입력
된 것이 자음이라면 자음을 하나빼내서 다음 글자로 넘겨줘야 하기 때문
에 현재 입력된 글자와 빼낸 글자 2개를 넘겨줘야한다.
반면에 HS_END1은 글자가 조합되고 있는 과정에서 이전에 입력된 것이
모음일 경우 모음이 다시 들어 오더라도 이전 모음을 빼낼 이유가 없으
니 새로 들어온 모음 하나만 다음글자로 넘기면 된다. 그리고 더이상 조
합될 수 없는 자음이 들어올 경우에는 그 자음 하나만 다음글자로 넘기
면 된다. 따라서 HS_END2는 글자2개를 출력스택에 넘기고 HS_END1은 하나
만 출력스택에 넘기는 점에서 다르게 작동한다.
--------------------------------------------------------------------- */
static int tempUnionCode;
static int oldKey;
static int keyCode;
/* 겹모음을 이루는 지를 검사한다. 찾았으면 해당하는 코드를 돌려주고
아니면 0을 돌려준다. */
static int joongsungPair(void) {
static byte dJoongTable[7][3] = {
{ 0xad, 0xa3, 0xae }, /* ㅗ, ㅏ, ㅘ */
{ 0xad, 0xa4, 0xaf }, /* ㅗ, ㅐ, ㅙ */
{ 0xad, 0xbd, 0xb2 }, /* ㅗ, ㅣ, ㅚ */
{ 0xb4, 0xa7, 0xb5 }, /* ㅜ, ㅓ, ㅝ */
{ 0xb4, 0xaa, 0xb6 }, /* ㅜ, ㅔ, ㅞ */
{ 0xb4, 0xbd, 0xb7 }, /* ㅜ, ㅣ, ㅟ */
{ 0xbb, 0xbd, 0xbc } /* ㅡ, ㅣ, ㅢ */
};
int i;
/* 이전에 입력된 키와 현재 입력된 키를 겹모음 테이블에서 */
/* 검색한다. */
for (i = 0; i < 7; i++) {
if (dJoongTable[i][0] == oldKey && dJoongTable[i][1] == keyCode)
return ((keyCode = dJoongTable[i][2]));
}
return 0;
}
/* 겹받침을 이루는 지 검사한다. 찾았으면 해당하는 키를 돌려주고
아니면 0을 돌려준다. */
static int jongsungPair(void) {
static byte dJongTable[11][3] = {
{ 0x82, 0x8b, 0xc4 }, /* ㄱ, ㅅ*/
{ 0x84, 0x8e, 0xc6 }, /* ㄴ, ㅈ*/
{ 0x84, 0x94, 0xc7 }, /* ㄴ, ㅎ*/
{ 0x87, 0x82, 0xca }, /* ㄹ, ㄱ*/
{ 0x87, 0x88, 0xcb }, /* ㄹ, ㅁ*/
{ 0x87, 0x89, 0xcc }, /* ㄹ, ㅂ*/
{ 0x87, 0x8b, 0xcd }, /* ㄹ, ㅅ*/
{ 0x87, 0x92, 0xce }, /* ㄹ, ㅌ*/
{ 0x87, 0x93, 0xcf }, /* ㄹ, ㅍ*/
{ 0x87, 0x94, 0xd0 }, /* ㄹ, ㅎ*/
{ 0x89, 0x8b, 0xd4 } /* ㅂ, ㅅ*/
};
int i;
/* 이전에 입력된 키와 현재 입력된 키를 겹받침 테이블에서 찾아서
있는지를 검사한다. */
for (i = 0; i < 11; i++) {
if (dJongTable[i][0] == oldKey && dJongTable[i][1] == keyCode)
return (keyCode = dJongTable[i][2]);
}
return 0;
}
/********************************************************************
두벌식 오토마타
********************************************************************/
int hanAutomata2(int key) {
/*--------------------------------------------------------------------
인 수 : key = 입력된 키 코드
반환값 : 한 글자의 조합이 끝나면 1을, 계속 조합중이면 0을,
완성된 글자의 코드는 입력 스택의 가장 마지막에서
구할 수 있다.
동작 :
--------------------------------------------------------------------*/
int chKind, canBeJongsung = FALSE;
/* 초성코드에 대응하는 종성 코드 */
static byte Cho2Jong[] = {
0xc2, /* 기역 */
0xc3, /* 쌍기역 */
0xc5, /* 니은 */
0xc8, /* 디귿 */
0x00, /* 쌍디귿 (해당 없음) */
0xc9, /* 리을 */
0xd1, /* 미음 */
0xd3, /* 비읍 */
0x00, /* 상비읍 (해당 없음) */
0xd5, /* 시옷 */
0xd6, /* 쌍시옷 */
0xd7, /* 이응 */
0xd8, /* 지읒 */
0x00, /* 쌍지읒 (해당 없음) */
0xd9, /* 치읓 */
0xda, /* 키읔 */
0xdb, /* 티읕 */
0xdc, /* 피읖區 */
0xdd /* 히읗 */
};
/* ---------------------------------------------------------------------
입력된 낱자가 어떤 형태인가를 규정하고 이전의 한글입력상태와 조합된
코드를 얻어오는 오토마타의 작업준비 부분
--------------------------------------------------------------------- */
/* 글쇠가 모음일 경우에는 01100000b 로 &연산을 하면 00100000b가 된다. */
if ((key & 0x60) == 0x20) {
chKind = VOWEL; /* 모음 */
} else {
chKind = CONSONANT; /* 그 이외에는 자음 */
/* 쌍디귿, 쌍비읍, 쌍지읒은 받침으로 올 수 없다. */
if (!(key == 0x86 || key == 0x8A || key == 0x8F))
canBeJongsung = TRUE;
}
/* 만일 한글이 입력되고 있다면 이전에 저장된 스택에서 조합된
코드와 입력된 글쇠를 가져온다. */
if (tempHanState) {
tempUnionCode = inStack[inSP - 1].unionCode;
oldKey = inStack[inSP - 1].key;
} else {
/* 처음이라면..*/
/* 0x8441은 각 초성, 중성, 종성의 채움문자의 OR연산결과임 */
tempUnionCode = 0x8441;
oldKey = 0;
}
keyCode = key; /* 작업할 keyCode로 복사 */
/* ---------------------------------------------------------------------
이전의 한글이 조합된 상태 (unionCode 또는 tempUnionCode)와 현재 입력된
글자가 어떤 형태인가에 따라 조합상태를 다시 결정짓는 오타마타 주요부분
--------------------------------------------------------------------- */
switch (tempHanState) {
case HS_START : /* 한글입력이 처음이고 */
if (chKind == CONSONANT) /* 자음이 들어왔다면 초성상태로 */
tempHanState = HS_CHOSUNG;
else /* 모음이라면 중성상태로 */
tempHanState = HS_JOONGSUNG;
break;
case HS_CHOSUNG : /* 초성이 이미 입력이 되었고 */
if (chKind == VOWEL) /* 모음이 들어왔다면 */
tempHanState = HS_JOONGSUNG; /* 중성상태로 돌진!! */
else
/* 2벌식에는 복초성을 두번으로 나누어 입력할 수 없다. */
/* 따라서 초성이 들어온 상태에서 초성이 다시 들어온다면 */
/* 당연히 글자조합을 끝을 낸다. */
tempHanState = HS_END1;
break;
case HS_JOONGSUNG : /* 중성이 이미 들어와 있고 */
if (canBeJongsung) /* 종성이 될 수 있는 놈이라면 */
tempHanState = HS_JONGSUNG; /* 종성상태로 발전한다. */
/* 중성이 들어왔다면 겹모음을 이룰 수 있는 지를 검사해서
겹모음이 될 수 있으면 복중성상태로 간다. 이도 저도 아니
면 끝으로 간다. */
else if (joongsungPair())
tempHanState = HS_DJOONGSUNG;
else
tempHanState = HS_END1;
break;
case HS_DJOONGSUNG : /* 겹모음을 이루었고 */
if (canBeJongsung) /* 종성이 될 수 있는 놈이라면 */
tempHanState = HS_JONGSUNG; /* 종성상태로 ... */
else
/* 모음이나 종성이 될 수 없는 자음은 겹모음상태에서 받아들일 */
/* 수 없다. */
tempHanState = HS_END1;
break;
case HS_JONGSUNG : /* 종성을 이루고 있고 */
/* 자음이 들어와서 겹자음을 이룰 수 있는 놈이라면 */
/* 복종성상태로 간다. */
if (chKind == CONSONANT && jongsungPair())
tempHanState = HS_DJONGSUNG;
/* 만일 모음이 들어온다면 끝2로 간다. */
else if (chKind == VOWEL)
tempHanState = HS_END2;
/* 복종성을 이룰 수 없는 자음이라면 끝으로 간다. */
else
tempHanState = HS_END1;
break;
case HS_DJONGSUNG : /* 복종성을 이루고 있고 */
if (chKind == VOWEL) /* 모음이 들어왔다면 당연히 끝2로 */
tempHanState = HS_END2;
else
tempHanState = HS_END1; /* 그외에는 안보고도 끝1로 */
break;
}
/* ---------------------------------------------------------------------
한글낱자를 조합해서 코드를 얻는 곳이다. 부분적으로 뒤에서는 스택조정
도 한다.
초성코드에서 0x80을 빼면 순수한 조합형 초성코드가 나오는 데
여기서 10비트를 왼쪽으로 밀어버리면 조합할 수 있는 상태가 된다.
이전의 조합된 코드에서 1000 0011 1111 1111 을 &연산을 하면 초성
부분을 깨끗이 지울 수 있다. 이 둘을 OR연산하면 원하는 조합된
코드를 얻을 수 있다.
마찬가지로 중성에서 0xA0을 빼면 순수한 중성코드를 얻을 수 있는 데,
여기서 왼쪽으로 5비트를 밀어버리면 당연히 조합가능한 중성코드가
나온다. 원래의 코드에 0xFC1F를 &연산한다는 것은 1111 1100 0001 1111
로 중성부분을 깨끗이 지운다는 것이고 이 둘을 OR 연산하면 원하는
코드를 얻는다.
종성에서는 조금 다르다. 2벌식에서는 초성, 종성이 따로 없으므로
자음은 모조리 초성으로 가정하고 종성에는 쌍디귿, 씽비읍, 쌍지읒
만이 올 수 없다. 따라서 처음에 초성으로 들어왔으므로 초성에 대응
하는 종성코드가 기술되어 있는 테이블에서 인덱스로 찾아야 한다.
keyCode에서 0X82를 뺀다는 것은 순수한 초성코드에서 채움문자를 제외
한 곳에서부터 인덱스를 메기겠다는 것이고 이것으로 테이블에 가서 똑
같은 모양글자의 종성코드를 가져온다.
복종성은 이미 앞의 dJongTable에서 알맞는 종성코드로 변환되었으므로
이런 과정이 필요없다. 그러고 난 다음에 0xC0을 빼서 순수 종성코드를
얻고 원래의 조합된 코드에서 1111 1111 1110 0000 을 & 연산해서 종성
코드부분을 깨끗이 해서 이둘을 OR연산한다.
--------------------------------------------------------------------- */
switch (tempHanState) { /* 한글 낱자가 입력이 되어 있을 경우에만 */
case HS_CHOSUNG : /* 초성코드 처리 */
tempUnionCode = (tempUnionCode & 0x83FF) | ((keyCode - 0x80) << 10);
break;
case HS_JOONGSUNG : /* 중성코드는 복중성과 같이 처리된다. */
case HS_DJOONGSUNG : /* 복중성 코드 처리 */
tempUnionCode = (tempUnionCode & 0xFC1F) | ((keyCode - 0xA0) << 5);
break;
case HS_JONGSUNG : /* 종성코드는 초성2종성테이블에서 변환되어야 한다. *
/
keyCode = Cho2Jong[keyCode - 0x82];
case HS_DJONGSUNG : /* 복종성 및 종성 코드 처리 */
tempUnionCode = (tempUnionCode & 0xFFE0) | (keyCode - 0xC0);
break;
case HS_END1 :
outStack[outSP++] = key; /* 현재낱자 하나만 다음으로 넘긴다. */
return TRUE;
case HS_END2 :
/* 현재 낱자를 먼저 출력스택에 넣고 이전 글쇠를 꺼집어 내서 출력
스택에 집어넣는다. 스택은 먼저 들어간 것이 나중에 나온다. */
outStack[outSP++] = key;
outStack[outSP++] = oldKey;
inSP--; /* 입력스택에서 하나를 빼같으므로 스택포인터 조정 */
return TRUE; /* 1은 완료되었음을 의미 */
}
inStack[inSP].currentHanState = tempHanState;
inStack[inSP].unionCode = tempUnionCode;
inStack[inSP++].key = key;
return FALSE; /* 아직 한글 조합중 */
}
------------------------------------------------------------------------
주석이 너무 많아서 오히려 어지러울 수도 있겠지만 잘 읽어보시면 이해가
빨리 될 것입니다. 주석에서 너무 상세히 설명이 된 것 같아 부연 설명은
하지 않아도 될 것같습니다. 처음의 상태는 HS_START에서 시작해서 입력
되는 글쇠에 따라서 상태가 변화하며 조립을 다했으면 1을, 조립중이면
0을 반환합니다. 그리고 조립이 완료되었다면 출력스택에 HS_END1, HS_END2
에 따라서 1개 내지 2개의 낱자를 밀어넣습니다.
7. 나오는 말
이상으로 부족한 설명이지만 오토마타에 대한 이야기를 마치도록 하겠습니다.
자세한 풀소스나 기능은 조만간에 정리하여 발표될 한글라이브러리 "달래"
를 참조하시기 바랍니다.
(한글라이브러리를 만들고 나서는 C++과 본래의 과제인 시스템 프로그래밍을
좀더 심도깊게 공부해 볼 계획입니다. )
힘든 강좌를 따라오신다고 수고하신 분들께 리눅스에서 한글의 완전한 처리를
위한 첫걸음이 승리하기를 빌며 이만 인사에 갈음할까 합니다.
안녕히 계시길...
ddoch 한동훈
http://imhangul.kldp.net/automata/automata.html
'프로그래밍' 카테고리의 다른 글
| 프로젝트중 (0) | 2006/07/30 |
|---|---|
| Impression 백업 (0) | 2006/07/30 |
| 한글 오토마타 (2) | 2006/07/29 |
| 유니코드 한글 조합법 (0) | 2006/06/06 |
| 기본에 충실하자. (0) | 2006/05/15 |
| 키보드 샀다. (1) | 2006/04/12 |
Posted by 당근세푸대
