메뉴 건너뛰기


Projects > Code Processing

Linguistic Sorting의 구현

2013.12.28 03:20

푸우 조회 수:4989

■ Linguistic Sorting의 구현
 
 
1. Linguistic Sorting이란?
 
아시다 시피 Sorting이라는 것은 대상을 어떠한 순서로 정렬하는 것을 의미합니다. Linguistic Sorting이란 Sorting에 Linguistic 이라는 용어를 덧붙여 "언어학의 정렬"라고 해석할 수 있습니다. 언어학적인 정렬이라고 했으니 당연히 숫자값에 대한 정렬이 아닌 문자열에 대한 정렬에서의 이야기 입니다.
 
그럼 Linguistic Sorting이란 구체적으로 무엇을 의미하는 것인가를 알아보도록 하겠습니다.
 
전산에서 정렬이라는 것은 문자코드 값에 의해 정렬하는 것이 일반적입니다.
이렇게 정렬한 데이터로도 큰 불편이 없을 수 있습니다. 적어도 검색이나 통계용도로 정렬한 경우는 말이죠. 하지만 정렬된 결과를 사용자에게 보여줘야 하고 데이터 자체가 대소문자 섞여 있거나 같은 값이 중복되어 있는 경우에서는 예상하지 못한(?) 문제가 존재합니다.
 
예로 "rain", "Rain", "RAIN", "raiN", "rain",  "Rain", "RAIN", "raiN",  "Sa", "rai" 이라는 10개의 문자열 배열을 코드값에 의해 정렬하게 되면 다음과 같이 됩니다.
 
"RAIN", "RAIN", "Rain", "Rain", "Sa", "raiN", "raiN", "rai", "rain", "rain"
 
보면 나름 코드값에 의해 정렬이 된 것은 사실이지만 이것이 영어 사전의 표제어들을 정렬한 것이라고 생각하면 좀 이상합니다. 대문자보다 소문자가 코드값이 더 작으므로 대문자로 시작하는 문자열이 다 나타난 다음에야 소문자로 시작하는 문자열이 나타납니다. 거기다가 "Rain" 다음에 "Sa"가 나타나고 다음으로 "raiN"이 나타납니다. 이건 문자코드값에 의한 정렬은 맞지만 사람이 언어학적으로 생각하는 정렬 관점에서는 문제가 있습니다.
 
그럼 일괄적으로 대문자로 소문자로 변환해서 정렬하면 되지 않겠는가 하는 생각을 할 수 있습니다.
실제로 구현해 보면 다음과 같은 결과가 나타납니다.
 
"rai", "RAIN", "raiN", "rain", "rain", "RAIN", "raiN", "Rain", "Rain", "Sa"
 
아까보다는 사람의 생각에 가까와 보이긴 하지만... 역시 문제가 있습니다.
"RAIN", "raiN', "rain", "Rain"이 모두 같은 코드 값을 갖으므로 이들이 서로 뒤죽 박죽으로 나타납니다.
물론 소팅 방법에 따라 아니면 초기 배열의 순서에 따라 이들은 달라질 수는 있습니다.
 
이것이 사전의 표제어로써의 정렬을 해야 한다면 사람들은 다음과 같은 결과를 바랄 것 입니다.
 
"rai", "RAIN", "RAIN", "Rain", "Rain", "raiN", "raiN", "rain", "rain", "Sa"
 
여기서는 대문자가 소문자보다는 우선된다고 하였지만... 어떤 이는 소문자가 우선되어야 한다고 생각하는 이도 될 수 있습니다. 어찌되었건 일관된 형태로 배열이 정렬되면 되는 것이죠.
이렇게 정렬하는 거을 Linguistic Sorting이라하며 특별히 신경써서 구현하지 않으면 안됩니다.
 
영문을 예로 들었지만... 한글도 마찬가지 입니다..
 
예를 들어 "국수", "國民", "국가", "國土"와 같은 문자열 배열이 있다면 일반 정렬에 의해서는 다음과 같은 결과가 나타납니다.
 
"국가", "국수", "國民", "國土"
 
즉, 한글이 모두 출력된 후에 한자가 나타납니다.
이런 식이라면 어떤 단어가 있는지를 사전에서 찾을 때 한글쪽에서 한번 찾고 한자쪽에서 또 한번 찾아봐야 겠죠? 사람들은 위의 문자열 배열이 언어적으로 다음과 같이 정렬되어지기를 바랍니다.
 
"국가", "國民", "국수", "國土"
 
이러한 것들은 영문과 한글뿐 아니라 각나라 마다 독특한 언어적 순서를 요구합니다. (예로 일어에서는 히라가나와 가타가나가 적절히 섞여야 한다는 식으로...)
 
 
2. 구현하기
 
Linguistic Sorting이라는 의미를 설명하는데 한참이 걸렸네요.
자 이제 실제로 Linguistic Sorting을 프로그램으로 어떻게 구현하는지 알아보도록 하겠습니다.
여기서는 영문에 대한 Linguistic Sorting에 대해서만 구현해 보도록 하죠. (그나마 좀 쉬우므로...)
 
아시다 시피 대부분의 정렬 알고리즘은 각 요소 값들의 비교에 의해 정렬합니다. (삽입, 선택, 버블, 퀵정렬 등)
각 알고리즘을 이용할 때 비교함수를 제공하여야 하는데 Linguistic Sorting의 주요키는 이 비교 함수가 쥐고 있습니다.
예로 ANSI C에서 제공하는 quick sort 인 qsort()함수의 원형은 다음과 같습니다.
 
void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );
 
qsort()함수에서 compare 매개변수가 비교함수입니다.
다음과 같이 사용할 수 있습니다.
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

static int StdStrCmp(const void *str1, const void *str2)
{
  unsigned char *s1, *s2;

  s1 = *(unsigned char**)str1;
  s2 = *(unsigned char**)str2;

  return strcmp(s1, s2);
}

static int StdStrICmp(const void *str1, const void *str2)
{
  unsigned char *s1, *s2;

  s1 = *(unsigned char**)str1;
  s2 = *(unsigned char**)str2;
  
  return stricmp(s1, s2);
}

int main(int argc, char *argv[])
{
  unsigned char *array[10= {"rain""Rain""RAIN""raiN""rain",  "Rain""RAIN""raiN",  "Sa""rai"};
  unsigned int i;

  qsort(array, 10sizeof(unsigned char*), StdStrICmp);
  printf("======================================\n");
  for(i=0; i<10; i++) {
    printf("%s\n", array[i]);
  }
  printf("======================================\n");
  
  return 0;
}
 
물론 위의 함수는 코드값에 의한 정렬입니다. strcmp()함수나 stricmp()함수가 문자 코드값에 의존적이니깐요. 실행결과는 다음과 같습니다. 
 
====================================== rai RAIN raiN rain rain RAIN raiN Rain Rain Sa ======================================
 
그럼 비교함수가 우리가 원하는 순서대로 비교를 하게 만들어 보겠습니다.
 
방법 자체는 비교함수가 코드값이 아닌 우리가 원하는 순서의 값으로 비교해 주는 함수를 만드는 것입니다. 이때 우리가 원하는 순서의 값을 알아낼 수 있는 ASCII코드와 매핑되어 sort값을 저장한 mapping테이블을 만들어 사용하는 것입니다.
실제 소스는 다음과 같습니다.  
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

static const unsigned char sortmap[] = {
  0x000x940x950x960x970x980x990x9A0x9B0x9C0x9D0x9E0x9F0xA00xA10xA2
  0xA30xA40xA50xA60xA70xA80xA90xAA0xAB0xAC0xAD0xAE0xAF0xB00xB10xB2
  0x010x020x030x040x050x060x070x080x090x0A0x0B0x0C0x0D0x0E0x0F0x10
  0x110x120x130x140x150x160x170x180x190x1A0x1B0x1C0x1D0x1E0x1F0x20
  0x210x220x2C0x2E0x320x340x3E0x400x420x440x4E0x500x520x540x560x5A
  0x640x660x680x6A0x6D0x6F0x790x7B0x7D0x7F0x840xB30xB40xB50xB60xB7
  0xB80x230x2D0x2F0x330x350x3F0x410x430x450x4F0x510x530x550x570x5B
  0x650x670x690x6B0x6E0x700x7A0x7C0x7E0x800x850xB90xBA0xBB0xBC0xBD
  0xBE0xBD0xC00xC10xC20xC30xC40xC50xC60xC70xC80xC90xCA0xCB0xCC0xCD
  0xCE0xCF0xD00xD10xD20xD30xD40xD50xD60xD70xD80xD90xDA0xDB0xDC0xDD
  0xDE0xDF0xE00xE10xE20xE30xE40xE50xE60xE70xE80xE90xEA0xEB0xEC0xED
  0xEE0xEF0xF00xF10xF20xF30xF40xF50xF60xF70xF80xF90xFA0xFB0xFC0xFD
  0x280x240x260x2A0x880x860x8A0x300x3C0x360x3A0x380x4C0x460x4A0x48
  0x900x580x600x5C0x5E0x620x8C0xFE0x8E0x770x710x750x730x810x920x6C
  0x290x250x270x2B0x890x870x8B0x310x3D0x370x3B0x390x4D0x470x4B0x49
  0x910x590x610x5D0x5F0x630x8D0xFF0x8F0x780x720x760x740x820x930x83
};

static int MyStrCmp(const void *str1, const void *str2)
{
  unsigned int c1, c2;
  signed int tiebreaker = 0;
  unsigned int n = 0;
  signed int ret = 0;
  unsigned char *s1, *s2;

  s1 = *(unsigned char**)str1;
  s2 = *(unsigned char**)str2;
  tiebreaker = sortmap[s1[n]] - sortmap[s2[n]];
  while (s1[n] && s2[n]) {
    if ( s1[n] != s2[n] ) {
      c1 = toupper(s1[n]);
      c2 = toupper(s2[n]);

      if ( c1 != c2 ) {
        return (sortmap[c1] - sortmap[c2]);
      }
      if ( !tiebreaker ) {
        tiebreaker = sortmap[s1[n]] - sortmap[s2[n]];
      }
    }
    n++;
  }
  
  ret = s1[n] - s2[n];
  return (ret ? ret : tiebreaker);
}

static int MyStrICmp(const void *str1, const void *str2)
{
  unsigned int n;
  unsigned char *s1, *s2;

  s1 = *(unsigned char**)str1;
  s2 = *(unsigned char**)str2;
  
  for ( n = 0; s1[n] && s2[n]; n++ ) {
    if ( s1[n] != s2[n] ) {
      unsigned char c1 = toupper(s1[n]);
      unsigned char c2 = toupper(s2[n]);
      
      if ( c1 != c2 ) {
        return (sortmap[c1] - sortmap[c2]);
      }
    }
  }
  
  return (s1[n] - s2[n]);
}

int main(int argc, char *argv[])
{
  unsigned char *array[10= {"rain""Rain""RAIN""raiN""rain",  "Rain""RAIN""raiN",  "Sa""rai"};
  unsigned int i;

  printf("======================================\n");
  qsort(array, 10sizeof(unsigned char*), MyStrCmp);
  for(i=0; i<10; i++) {
    printf("%s\n", array[i]);
  }
  printf("======================================\n");
  
  return 0;
}
 
 
위의 코드를 실행한 결과는 다음과 같습니다.
====================================== rai RAIN RAIN Rain Rain raiN raiN rain rain Sa ======================================
 
sortmap 테이블은 순서값을 아스키 코드 순서대로 저장하고 있습니다.
NUL문자를 순서값 0을 갖게 하고...
Space문자를 순서값 1을 갖게 하고... 뭐 이런식입니다.
Space문자부터 순서값 순으로 적으면 다음과 같습니다.
 
 !"#$%&'()*+,-.0123456789:;<=>@AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz......
 
소문자 z 다음의 순서는 발음기호 순으로 되어 있는데... 타이핑하기가 힘듦므로 이후는 생략하겠습니다. 직접 아래의 ASCII표에서 찾아보시길... 
 28591.gif
 
▲ 참고로 위의 ASCII 8859 Latin1 코드 페이지 표로서 http://www.microsoft.com/globaldev/reference/iso/28591.mspx에서 퍼왔습니다.
 
 보시면 아시겠지만... 대문자와 소문자를 순서대로 조합하여 정렬값을 갖게 했다는 것을 아실 수 있을 것입니다.
 
MyStrCmp()함수와 MyStrICmp()는는 sortmap테이블을 이용하여 문자열을 비교하는 코드입니다. 이 코드는 싱글 바이트 코드를 사용하는 언어는 모두 같이 사용할 수 있습니다. 단, sortmap 테이블을 각 언어에 따라 달라져야 겠죠?
 
한국어, 일본어, 중국어는 멀티바이트 코드를 사용하므로 위의 함수를 그대로 사용할 수는 없습니다.
또한 멀티바이트 코드가 특별한 규칙에 의해 구성되어 있을 수도 있고 되어 있지 않을 수도 있어서...
보편된 코드를 만들기는 어렵습니다.
 
아무튼 위의 코드를 한번 분석해 보시고.... 멀티바이트 코드에서의 Linguistic Sorting에 대해서 한번 생각해 보시길 바랍니다.
 
이번 강좌에 여러분들의 관심이 많다면 뭐 한국어에 대해서는 글을 한번 더 작성해 보도록 하겠습니다.
 
그럼 이번 강좌는 여기까지입니다... ^^;
 
 
 
 
 
 
 
Creative Commons License
Creative Commons License이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
Copyright 조희창(Nicholas Jo). Some rights reserved. http://bbs.nicklib.com
 
 
번호 제목 글쓴이 날짜 조회 수
» Linguistic Sorting의 구현 file 푸우 2013.12.28 4989