'2016/01'에 해당되는 글 23건

  1. 2016.01.29 덱(deque)
  2. 2016.01.29 쿠키(cookie)와 세션(Session) (2)
  3. 2016.01.28 ASP(Active Server Page)
  4. 2016.01.28 압축
  5. 2016.01.27 statement란? (1)
  6. 2016.01.27 DAO / VO / DTO란? (2)
  7. 2016.01.26 RDBS,DB모델링,파일시스템 표현 차이
  8. 2016.01.25 샤딩(Sharding)이란?
  9. 2016.01.25 IIS란?
  10. 2016.01.22 C#의 where


deque에 대해서 검색해보았다.


원문 출처 : http://mayple.tistory.com/entry/CSTL-7%EC%9E%A5-deque


deck과는 다르다! deck과는!


7.1 deque 데이터 추상(data abstraction)

 
deque`double-ended queue'의 약자이고, `덱(deck)'이라고 발음한다. 전통적으로, 이 용어는 콜렉션의 앞과 뒤 어느 곳에서나 삽입과 삭제가 가능한 데이터 구조들을 지칭하는데 사용되었는데, deque 컨테이너 클래스는 이것뿐만 아니라 더 많은 것을 할 수 있다. 실제로, deque 데이터 구조의 능력은 vector 클래스와 list 클래스가 제공하는 것들을 모두 포함한다.
  • vector와 같이 deque은 인덱싱이 가능하다. 콜렉션 내에서의 위치를 키로 사용함으로써, 첨자로 값들을 접근할 수 있다. (물론 list 클래스에서는 제공하지 않는 기능이다.)
  • list와 같이 deque의 앞과 뒤에 값을 효율적으로 추가할 수 있다. (vector 클래스에서는 vector의 맨뒤에서 값을 추가하는데 있어 효율적이다.)
  • list와 vector 클래스에서와 같이, deque가 관리하는 시퀀스의 중간에서 값들을 삽입할 수 있다. 이러한 삽입 연산은 list에서도 효율적인 연산이지만, vector에서는 조금 더 비용이 드는 연산이다.
간단히 말해서, deque은 vector와 list를 필요로 하는 곳에서 모두 사용할 수 있다. vector와 list 대신에 deque를 사용하게 되면, 종종 프로그램의 성능이 더 나아진다. 어느 데이터 구조를 선택할지에 관해서는 4.2절을 참고하기 바란다. 

7.1.1 Include 화일

deque 데이터 타입을 사용하는 프로그램은 모두 deque 헤더 화일을 사용해야 한다.
    #include <deque>
 
 

7.2 deque 연산

deque는 vector와 같은 방식으로 선언하고, 클래스 내부에는 vector와 동일한 타입 정의를 가지고 있다.
begin()과 end() 멤버 함수는 양방향 반복자를 제공하는 리스트와는 달리, 임의접근 반복자를 리턴한다.
삽입(insert()push_front()push_back())은 deque의 원소를 가리키는 반복자나 레퍼런스들을 무효화시킬 수도 있다. 이는 vector 데이터 타입과 같이 list에서의 삽입보다 더 제한적이다.
deque내의 원소 타입에 소멸자가 정의되어 있다면, deque로부터 원소를 삭제할 때, 이 소멸자가 호출될 것이다.
deque 데이터 타입이 임의접근 반복자를 제공하기 때문에, vector에 적용되는 모든 generic 알고리듬은 deque에도 사용될 수 있다.
vector는 커다란 하나의 메모리 블럭에 원소들을 가지고 있는 반면, deque은 많은 수의 좀더 작은 블럭들을 사용한다. 메모리 블럭의 사이즈에 제한을 두고 있는 시스템에서 이는 매우 중요한 사항이며, 이러한 이유때문에 deque은 vector보다 더 많은 원소들을 포함할 수 있다.
값들을 삽입할 때는, 콜렉션내의 원소와 연결되어 있던 인덱스가 바뀌게 된다. 예를 들어, 3번 위치에 값을 삽입하면, 원래 3번 자리에 있던 값은 4번자리를 차지하게 되고, 4번 자리에 있던 값은 5번자리로 차례로 옮겨지게 된다. 
 
 
 

7.3 예제 프로그램 - Radix Sort

 
The radix sort algorithm is a good illustration of how lists and deques can be combined with other containers. In the case of radix sort, a vector of deques is manipulated, much like a hash table.
Radix sorting is a technique for ordering a list of positive integer values. The values are successively ordered on digit positions, from right to left. This is accomplished by copying the values into "buckets," where the index for the bucket is given by the position of the digit being sorted. Once all digit positions have been examined, the list must be sorted.
The following table shows the sequences of values found in each bucket during the four steps involved in sorting the list 624 852 426 987 269 146 415 301 730 78 593. During pass 1 the ones place digits are ordered. During pass 2 the tens place digits are ordered, retaining the relative positions of values set by the earlier pass. On pass 3 the hundreds place digits are ordered, again retaining the previous relative ordering. After three passes the result is an ordered list. 
 
bucketpass 1pass 2pass 3
073030178
1301415146
2852624, 426269
3593730301
4624146415, 426
5415852593
6426, 146269624
798778730
878987852
9269593987
The radix sorting algorithm is simple. A while loop is used to cycle through the various passes. The value of the variable divisor indicates which digit is currently being examined. A boolean flag is used to determine when execution should halt. Each time the while loop is executed a vector of deques is declared. By placing the declaration of this structure inside the while loop, it is reinitialized to empty each step. Each time the loop is executed, the values in the list are copied into the appropriate bucket by executing the function copyIntoBuckets() on each value. Once distributed into the buckets, the values are gathered back into the list by means of an accumulation.
    void radixSort(list<unsigned int> & values)
    {
       bool flag = true;
       int divisor = 1;
       
       while (flag) {
          vector< deque<unsigned int> > buckets(10);
          flag = false;
          for_each(values.begin(), values.end(), 
                copyIntoBuckets(...));
          accumulate(buckets.begin(), buckets.end(), 
                values.begin(), listCopy);
          divisor *= 10;
          }
    }
The use of the function accumulate() here is slightly unusual. The "scalar" value being constructed is the list itself. The initial value for the accumulation is the iterator denoting the beginning of the list. Each bucket is processed by the following binary function:
    list<unsigned int>::iterator 
          listCopy(list<unsigned int>::iterator c, 
             deque<unsigned int> & lst)
    {
       // copy list back into original list, returning end
       return copy(lst.begin(), lst.end(), c);
    }
The only difficulty remaining is defining the function copyIntoBuckets(). The problem here is that the function must take as its argument only the element being inserted, but it must also have access to the three valuesbuckets, divisor and flag. In languages that permit functions to be defined within other functions the solution would be to define copyIntoBuckets() as a local function within the while loop. But C++ has no such facilities. Instead, we must create a class definition, which can be initialized with references to the appropriate values. The parenthesis operator for this class is then used as the function for the for_each() invocation in the radix sort program.
    class copyIntoBuckets {
    public:
       copyIntoBuckets
          (int d, vector< deque<unsigned int> > & b, bool & f) 
             : divisor(d), buckets(b), flag(f) {}
    
       int divisor;
       vector<deque<unsigned int> > & buckets;
       bool & flag;
    
       void operator () (unsigned int v)
       {   int index = (v / divisor) % 10;
           // flag is set to true if any bucket 
           // other than zeroth is used
           if (index) flag = true; 
           buckets[index].push_back(v);
       }
    };


'프로그래밍 > 자료구조, 알고리즘' 카테고리의 다른 글

덱(deque)  (0) 2016.01.29
빨간 눈의 승려 문제.  (0) 2015.04.12
자료구조 / 알고리즘  (0) 2015.04.02
Posted by GENESIS8

댓글을 달아 주세요

출처 : 위키백과
쿠키(cookie)란 하이퍼 텍스트의 기록서(HTTP)의 일종으로서 인터넷 사용자가 어떠한 웹사이트를 방문할 경우 그 사이트가 사용하고 있는 서버에서터넷 사용자의 컴퓨터에 설치하는 작은 기록 정보 파일을 일컫는다. '쿠키'라는 이름은 그림 동화 '헨젤과 그레텔'에서 가져온 것이다. 헨젤과 그레텔이 지나온 길을 표시하기 위해 쿠키 조각을 떨어뜨리며 표시했다는 이야기에서 따온 것이다. HTTP 쿠키, 웹 쿠키, 브라우저 쿠키라고도 한다. 이 기록 파일에 담긴 정보는 인터넷 사용자가 같은 웹사이트를 방문할 때마다 읽히고 수시로 새로운 정보로 바뀐다. 이 수단은 넷스케이프의 프로그램 개발자였던 루 몬툴리(Lou Montulli)가 고안한 뒤로 오늘날 많은 서버 및 웹사이트들이 브라우저의 신속성을 위해 즐겨 쓰고 있다. 쿠키는 소프트웨어가 아니다. 쿠키는 컴퓨터내에서 프로그램처럼 실행될 수 없으며 바이러스를 옮길 수도, 악성코드를 설치할 수도 없다. 하지만 스파이웨어를 통해 유저의 브라우징 행동을 추적하는데에 사용될 수 있고, 누군가의 쿠키를 훔쳐서 해당 사용자의 웹 계정 접근권한을 획득할 수도 있다.





출처 : http://crynut84.tistory.com/74

#1. 웹 서버 동작 원리

웹 사이트 상태관리의 필요성을 알기 위해 웹 서버와 클라이언트(웹 브라우저)가 어떠한 방식으로 동작 하는지를 먼저 알아 보겠습니다.


 

Fig1을 보면 아주 간단한 원리로 동작 하는 것을 알 수 있는데요. 클라이언트가 HTTP 프로토콜을 사용하여 웹 서버로 요청(Request)을 하게 되면 웹 서버는 해당 하는 HTML을 웹 브라우저로 전송 해 주고 웹 브라우저는 응답(Response) 받은 HTML을 파싱하여 사용자에게 보여주게 됩니다. 여기서 ‘요청’이란 우리가 웹 브라우저의 주소 표시줄에 http://crynut84.tistory.com이라고 입력 하는 행위나 웹 사이트의 링크를 마우스로 클릭하는 행위 등을 말합니다.

 

웹 사이트는 다시 정적인 웹 사이트와 동적인 웹사이트로 나눌 수 있습니다. 정적인 웹 사이트는 웹 서버에서 .HTML 파일을 완성된 .HTML 파일을 가지고 있다가 클라이언트의 요청이 있을 시 해당하는 .HTML 파일을 돌려 주는 형태입니다. 당연히 HTML 페이지의 내용들은 이미 결정 되어있어 있으므로 클라이언트의 상태, 방문정보, 시각등의 내용에 관계없이 항상 동일한 HTML 페이지를 보여줍니다. 요즘은 이런 웹사이트는 거의 없을 듯 합니다.

 

동적인 웹 사이트는 사용자의 액션에 따라 웹 사이트가 다르게 동작 하는 것을 말합니다. 예를들어 요즘 웹 사이트는 거의 로그인이라는 인증 과정을 거치게 되고, 로그인을 하면 ‘전호진님 환영합니다’라고 환영 인사도 해줍니다. 또한 게시판은 검색어에 따라 다른 결과를 보여주게 되고, 사용자 입맛에 맛게 정렬도 할 수 있습니다. 이와같이 요즘 일반적으로 볼 수 있는 사용자와 웹사이트가 서로 상호작용을 하는 웹 사이트를 동적인 웹사이트라고 합니다.

 

동적인 웹사이트를 만드는 기술은 ASP.NET, JSP, ASP, PHP, CGI등 여러 가지가 있습니다. 마이크로소프트의 동적인 웹사이트를 만드는 기술인 ASP.NET의 동작 원리(Fig2)를 보면 정적 웹사이트와 조금 다른 것을 알 수 있는데요.

 

클라이언트가 요청하게 되면 웹 서버는 요청에 대한 적절한  HTML을 새롭게 생성 합니다. 요청에 대한 일련의 처리(로직 수행)를 수행하게 되고 처리 결과를 다시 클라이언트에 돌려 주게 되는데 동적인 웹 사이트라고 해도 클라이언트가 받는 최종 응답은 정적인 HTML 페이지입니다. 예를들어 게시판에 여러 게시글이 있는데 사용자가 ASP.NET을 검색어로 입력하고 검색 버튼을 누르게 되면 이 요청을 웹서버가 받아서 게시글 중 ASP.NET이 들어간 결과만 찾아서 형식에 맞는 HTML을 구성하게 되고 클라이언트에 응답하주게 되는 것입니다. 이렇게 동적인 처리를 위해 ASP.NET과 같은 웹 기술이 필요하게 되고, 모든 처리는 웹 서버에서 수행되며, 클라이언트의 입장에서는 정적인 웹 사이트와 동일하게 웹 서버에 요청을 하고 응답받은 결과를 파싱하여 보여 주게 됩니다.

 

#2. 상태 관리(State Management)

웹 사이트를 사용하는 사용자는 HTTP GET방식이나 HTTP POST방식을 사용하여 웹 서버로 페이지를 요청하게 되고, 웹 브라우저는 웹 서버에서 응답받은 HTML을 파싱하여 렌더링하게 됩니다. 이러한 일련의 주기를 ‘라운드트립(Round Trip)’ 이라고 합니다.그런데 HTTP 프로토콜은 상태를 저장 할 수 없는 프로토콜입니다. 이 말은 클라이언트의 요청이 왔을 때 웹 서버는 해당 요청에 대한 응답인 HTML을 보내주고 연결을 끊어버린다는 것입니다. 그렇기 때문에 라운드트립 시 페이지에 있는 컨트롤의 사용자 입력정보나 페이지의 정보들이 모두 손실 되게 됩니다.  예전에 사용하던 정적인 웹사이트(일방적으로 보기만 하는 웹사이트)에서는 문제가 되지 않지만 동적인 웹사이트에서는 사용자의 요청이나 컨트롤의 입력정보를 유지할 필요가 있기 때문에 ASP.NET은 상태 관리를 할 수 있는 여러가지 기능을 제공합니다.

 

상태관리의 정보를 저장하는 장소에 따라 두가지로 분류 할 수 있는데, 웹 서버에 저장하는 경우와, 클라이언트에 저장하는 경우가 있습니다.

▶ 상태 정보를 클라이언트에 저장하는 방식

  • 뷰 상태(View State)
  • 컨트롤 상태(Control State)
  • 숨겨진 필드(Hidden Field)
  • 쿠키(Cookie)
  • 쿼리 문자열(Query String)

▶ 상태 정보를 웹 서버에 저장하는 방식

  • 응용 프로그램 상태(Application State)
  • 세션(Session)
  • 프로필 속성(Profile Property)
  • 데이터베이스(Database)

두가지 방식은 장단점이 존재 하는데요. 일반적으로 데이터가 작고, 중요하지 않은(보안 등의 이유)정보는 클라이언트 측에서 관리하고, 나머지는 웹 서버에서 관리 하는 것이 좋습니다. 여러가지 상태관리 기능 중 Cookie와 Session에 관해 자세히 알아보겠습니다.

 

#3. 쿠키(Cookie)

 

쿠키는 요청 및 응답하는 과정에 포함되는 텍스트 정보이고 쉽게 구현하여 사용 할 수 있는 방법중에 하나입니다. 일반적인 브라우저에서 최대 4KB의 텍스트 정보를 담을 수 있으며 하나의 사이트는 20개만 허용되며, 모든 사이트를 통틀어서 300개로 제한 됩니다. 만약 이 범위를 넘어 더 많이 저장 하려고 할 경우에는 가장 오래된 쿠키부터 삭제되므로 사용의 주의해야하고, 4KB로 비교적 작은 크기만을 저장하기 때문에 적은 양의 데이터나 ID, 최근 읽은 글, 최근 본 상품과 같은 식별자를 저장할 때 사용하는 것이 적합합니다.

 

1. 쿠키의 동작 방식

쿠키는 서버에서 생성하여 클라이언트의 브라우저에서 관리하기 때문에 요청시 쿠키를 생성하고 브라우저를 닫을때 쿠키를 파괴합니다. 응답을 통해 얻어온 쿠키는 만료시간 여부에 따라 클라이언트의 PC에 파일로 저장하게 됩니다.

 

쿠키의 생성 주기를 살펴보면 처음으로 페이지를 요청 할 경우 웹 서버에서는 쿠키를 생성하게 되고, 페이지를 돌려 줄때 HTTP 헤더에 쿠키를 포함하여 돌려 주게 됩니다. 이렇게 넘겨 받은 쿠키는 클라이언트에서 관리 하고 있다가, 다음번 요청때 쿠키를 함께 전송하게 되고, 서버에서는 쿠키 정보를 읽어 이전 상태 정보를 알 수 있게 됩니다. 이때 웹 서버는 정보를 변경 할 필요가 있을때 쿠키를 업데이트하여 다시 변경된 쿠키와 함께 응답하게 됩니다.


2. ASP.NET에서 쿠키 사용

쿠키는 서버로 부터 응답받은 사항이기 때문에 HttpResponse 객체를 통해 클라이언트로 전송 됩니다. 쿠키에 정보를 저장하는 방법은 두가지가 있습니다. Page클래스의 Response 객체를 사용하는 것과 HttpCookie 클래스를 사용하는 방법입니다.

//Response 사용 
Response.Cookies["쿠키명1"].Value = "쿠키 예제;
Response.Cookies["쿠키명1"].Expires = DateTime.Now.AddMinutes(30); 

//HttpCookie 클래스 사용 HttpCookie cookie = new HttpCookie("쿠키명2");
cookie.Value = "쿠키 예제";
cookie.Expires = DateTime.Now.AddSeconds(30); 
Response.Cookies.Add(cookie);

-Code1. 쿠키 저장-

쿠키명1과 쿠키명2라는 이름을 사용하는 쿠키를 생성 하였고 각각 Value 속성을 통해 상태유지에 필요한 값을 넣어 주었습니다. Expires 속성은 만료 기간인데, 이 속성을 설정하면 쿠키가 클라이언트의 컴퓨터의 파일의 형태로 저장됩니다.  만료기간을 설정하지 않은 쿠키는 브라우저의 메모리에서 관리됩니다. Code1에서 쿠키명1은 30분후에 쿠키를 지우며, 쿠키명2는 30초 후에 쿠키를 지우도록 설정 하였습니다. 만료시간이 지난 쿠키는 클라이언트가 쿠키를 생성한 웹 사이트에 다시 요청을 보낼때 삭제됩니다.




출처 : http://88240.tistory.com/entry/Session-%EC%9D%B4%EB%9E%80


세션이란 일정 시간동안 같은 사용자(정확하게 브라우저를 말한다)로 부터 들어오는

일련의 요구를 하나의 상태로 보고 그 상태를 일정하게 유지시키는 기술이라고 한다.

또한 여기서 일정 시간이란 방문자가 웹 브라우저를 통해 웹 서버에 접속한 시점으로부터 웹 브라우저를 종료함으로써 연결을 끝내는 시점을 말하며

즉, 방문가자가 웹서버에 접속해 있는 상태를 하나의 단위로 보고 세션이라고 칭한다는 것.


- 쿠키의 경우는 방문자의 정보를 방문자 컴퓨터의 메모리에 저장하는 것을 말한다

예를 들자면 ID나 비밀번호를 저장하거나 방문한 사이트를 저장하는데에 사용한다.

(IE 인터넷 옵션에서 검색 기록 삭제할때 임시 파일, 열어본 페이지 목룍, 쿠키, 저장된 암호 및 웹 양식 정보 삭제라고 되어있지 아니한가)

- 세션은 방문자의 요청에 따른 정보를 방문자 메모리에 저장하는 것이 아닌 웹 서버가 세션 아이디 파일을 만들어 서비스가 돌아가고 있는 서버에 저장을 하는것을 말한다.


프로세스들 사이에서 통신을 하기 위해 메시지 교환을 통해 서로를 인식한 이후부터 통신을 마칠 때까지의 기간동안 서버에 잠시 방문자 정보를 저장한다는 것.


그래서 쿠키와 달리 세션은 사용자들의 로그인 정보에 대한 보안을 한층 업그레이드 할 수 있어 웹사이트에 방문하여 계속 접속을 유지할 때 이전의 접속 정보를 이용할 수 있는 방법으로 많이들 사용하는 것이다.




1. HTTP Session이란?

1) session이란 서버가 해당 서버(웹)로 접근(request)한 클라이언트(사용자)를 식별하는 방법

2) 서버(웹)는 접근한 클라이언트(사용자)에게 response-header field인 set-cookie 값으로 클라이언트 식별자인 session-id(임의의 긴 문자열)를 발행(응답)한다.

3) 서버로부터 발행(응답)된 session-id는 해당 서버(웹)와 클라이언트(브라우저) 메모리에 저장된다. 이때 클라이언트 메모리에 사용되는 cookie 타입은 세션 종료 시 같이 소멸되는 "Memory cookie"가 사용된다.

4) 서버로부터 발행된 session(데이터)을 통해 개인화(사용자)를 위한 데이터(userInfo 등..)로 활용할 수 있다.


2. HTTP Session 동작 순서

1) 클라이언트(사용자)가 서버로 접속(http 요청)을 시도한다.

2) 서버(웹)는 접근한 클라이언트의 request-header field인 cookie를 확인해 클라이언트가 해당 session-id를 보내왔는지 확인한다.

3) 만약 클라이언트로 부터 발송된 session-id가 없다면, 서버는 session-id를 생성해 클라이언트에게 response-header field인 set-cookie 값으로 session-id(임의의 긴 문자열)를 발행(응답)한다.


방문자가 서버에 접속 시도 후 서버 접근한 클라이언트(방문자)가 seesion id를 보내왔는지 확인 했는데 없다면 서버는 session id를 생성하는 부분을

우리가 많이들 쓰고 있는 session_start()함수인듯 하다.


다른 블로그에서 세션을 등록하기 위해서는 가장먼저 세션을 초기화 하여 세션을 생성하고, 현재의 세션 아이디를 활성화시키기 위해 session_start 함수를 사용한다 했으니...


또한 세션을 등록할때 $_SESSION['변수명'] 이렇게 쓰며


위에 설명중 세션 종료시 같이 소멸된다라고 써있는데 물론 브라우저를 끄며서 종료된다는 개념이지만 우리는

unset($_SESSION['변수명']);와 session_destory();이라는 걸 알고 있지요

(혹시나 하여 간단한 설명을 하자면 좌측은 세션 소멸과 우측은 세션 종료때 사용한다)



'프로그래밍 > 서버 프로그래밍' 카테고리의 다른 글

WAN과 LAN. MAN  (0) 2016.02.21
쿠키(cookie)와 세션(Session)  (2) 2016.01.29
redis란?  (0) 2016.01.21
Posted by GENESIS8

댓글을 달아 주세요

  1. 지나가는 행인 2016.08.12 04:57  댓글주소  수정/삭제  댓글쓰기

    정말 잘 봤습니다!!!이해가 명확히 돼요!

  2. 좋은설명 감사합니다 2017.12.27 09:18  댓글주소  수정/삭제  댓글쓰기

    좋은설명 감사합니다 잘읽다가 갔습니다!


출처 : 위키백과 



액티브 서버 페이지(Active Server Page, 줄여서 ASP)는 마이크로소프트사에서 동적으로 웹 페이지들을 생성하기 위해 개발한 서버 측 스크립트 엔진이다. 최초 버전은 Windows NT 4.0 옵션 팩(1998 상반기)에 포함하여 인터넷 정보 서비스(IIS)에 추가되는 식으로 출시되었고, 나중에 윈도 서버(윈도 2000 서버의 최초 버전 이후로)의 무료 구성 요소로 포함되었다. ASP.NET이 ASP를 대체하고 있다.


ASP 2.0은 6개의 내장 객체들을 제공한다: Application, ASPError, Request, Response, Server, Session. 예를 들어, Session은 페이지 간의 변수의 상태를 유지하는 쿠키 기반의 세션을 나타낸다. 동적 스크립팅 엔진의 컴포넌트 객체 모델(COM) 지원은 ASP 웹사이트들이 DLL들 같은 컴파일 된 라이브러리들을 함수처럼 접근 가능하게 해 준다.


.asp 파일 확장자를 가진 웹페이지는 ASP를 사용하지만, 몇개의 웹 사이트들은 보안 목적으로 스크립팅 언어를 숨기는 경우도 있다 (예를들면 더 일반적인 .htm 또는 .html 확장자를 사용하기). .aspx 확장자를 가진 페이지들은, ASP에서 서버측 스크립팅 보다 더 빠르고 강력하게 해주는, ( 마이크로소프트의 .NET 프레임워크 기반의) ASP.NET으로 컴파일되었고, 구동 시에 해석되지만; ASP.NET 페이지들은 여전히 일부 ASP 스크립팅을 포함하고 있을 것이다. ASP.NET의 도입은 원천 기술에 대해서는 오랜 ASP용어를 사용하였다. 프로그래머들은 대부분의 ASP페이지를 VBScript를 사용하여 작성하였지만, 그 외에도 동적 스크립팅 엔진은 @Language 지시문이나 <script language="language" runat="server"> 구문으로 선택하여 사용 할 수 있다. JScript(마이크로소프트가 구현한 ECMAScript)가 보통 사용가능한 다른 언어이다. PerlScript(Perl의 파생언어)와 다른 것들도 타사 제공 형태로 동적 스크립팅 엔진에 설치해서 사용 가능하다.


마이크로소프트의 액티브 스크립팅 표준과 호환되는 어떠한 스크립팅 언어라도 ASP에서 사용할 수 있다. 기본 스크립팅 언어(고전 ASP에서)는 VB스크립트이다.: 브라우저가 웹 서버에서 ASP 파일을 요청하면 서버는 프로세서를 호출하고, 프로세서는 요청된 파일을 읽고 스크립트 명령을 실행하여 결과를 웹페이지 형태로 브라우저에 전송한다. 


1 <html>
2 <body>
3 <% Response.Write "Hello World!" %>
4 </body>
5 </html>

더 단순한 형태로는 다음과 같다.

1 <html>
2 <body>
3 <%= "Hello World!" %>
4 </body>
5 </html>

이 예는 "Hello World!"를 HTML 문서의 body로 출력한다.

여기에는 액세스 데이터베이스로 연결하는 방법에 대한 한 예가 있다.

<%
	Set oConn = Server.CreateObject("ADODB.Connection")
	oConn.Open "DRIVER={Microsoft Access Driver (*.mdb)}; DBQ=" & Server.MapPath("DB.mdb")
	Set rsUsers = Server.CreateObject("ADODB.Recordset")
	rsUsers.Open "SELECT UserID FROM Users", oConn,1,3
%>


ASP.NET

ASP.NET은 마이크로소프트사가 개발하여 판매하는 웹 애플리케이션 프레임워크이며 프로그래머들이 동적인 웹 사이트, 웹 애플리케이션, 웹 서비스를 만들 수 있게 도와 준다. 2002년 1월에 닷넷 프레임워크 버전 1.0과 함께 처음 출시되었으며 마이크로소프트의 액티브 서버 페이지 (ASP) 기술의 뒤를 잇는다. ASP.NET은 공통 언어 런타임 (CLR)을 기반으로 작성되며 프로그래머들이 닷넷 언어가 사용된 ASP.NET 코드를 기록할 수 있게 도와 준다. ASP.NET SOAP 확장 프레임워크는 ASP.NET 구성 요소가 SOAP 메시지를 처리할 수 있게 도와 준다.


http://www.taeyo.pe.kr/lecture/Dukyoung/DYsASP02.asp


1. ASP 란 무엇인가?

ASP 란 'Active Server Pages' 의 약자이며, 우리 말로 번역하자면
'동적으로 서버에서 작동하는 페이지' 정도로 해석될 수 있을 것 같습니다.
동적(動的, Active) 이라.. 그렇다면 반대로 '정적(靜的, static)' 인 페이지도 있다는 뜻일까요?
맞습니다. 정적인 페이지도 있습니다. 우리가 알고 있는 HTML 이 바로 그것입니다.
'다 좋은데.. 정적인건 뭐고 동적인건 뭔지 말을 해줘야 할거 아냐!!' 
라고 외치시는 분들을 위해(한문 공부를 하십셔~) 잠시 그 개념의 차이를 말씀 드리겠습니다.

아주 간단하지만 의미 있는 예를 하나 들어보도록 하지요.
페이지를 하나 만들어서.. 이 페이지를 보고 있는 '현재 시간' 을 보여주려고 합니다.
이것을 HTML 과 ASP 페이지로 하나씩 만들어 보도록 하겠습니다.
// 링크가 죽었지만 내용으로 충분하다

위에 보이는 두개의 페이지는.. 얼핏 보기에 똑같아 보입니다만 중대한 차이가 있습니다.
두 페이지의 '새로고침' 링크를 살포~시 클릭하시면 그 차이를 발견하실 수가 있습니다.
어때요? 발견하셨나요?
그렇습니다. HTML 페이지에서는 새로고침을 아무리 눌러도 현재 시간이 변하지 않습니다만,
ASP 페이지에서는 새로고침을 누를때마다 현재 시간이 바뀌는 것을 보실 수가 있습니다.

이유는 간단합니다.
HTML 은 언제 어느곳에서 보더라도 우리가 작성한 모습 그대로일 수 밖에 없습니다.
다시 말해, HTML 페이지 안에는 시간을 '2003-04-15 오전 10:08:07 입니다.'
라고 직접 입력할 수밖에 없다는 말씀입니다.
이렇게 하면 화면에 보여지는 시간이 현재 시간인 것처럼 보여지지만,
실제로는 미리 입력되어 있는 '이미 작성된 문자열' 에 불과하다는 것을 알 수 있습니다.
그렇기 때문에 HTML 을 변하지 않는, '정적(靜的, static)' 이라고 표현하는 것이지요.

좋습니다.. 그렇다면 ASP 는 과연 무언가 다른걸까요?
그렇습니다. ASP 는 HTML 과는 확실히 다릅니다. (두둥~~)

ASP 는 어떤 특별한 과정을 거쳐서, 작성자의 의도대로 HTML 을 바꿀 수 있는 것입니다.
우리는 지난 시간에 '서버' 와 '클라이언트' 를 공부하면서 HTML 의 작동 원리에 대해서 잠시 생각해 보았습니다. 기억이 나시는지요? (안나신다굽쇼? -_-a)
좋습니다. 친절한 설명을 위해서 HTML 의 실행 과정 그림을 한번 보도록 하겠습니다.

'클라이언트가 서버로 HTML 페이지를 요구하면 서버에서는 별다른 처리 없이 HTML 을 클라이언트의 웹브라우저로 보내준다' 는 것이 바로 HTML 의 처리 과정이었습니다.



ASP 도 HTML 과 비슷한 과정을 거칩니다만.. 중요한 하나의 과정이 중간에 추가됩니다.
다음 그림을 보면서 말씀드리도록 하겠습니다.



클라이언트가 서버로 페이지를 요구하는 것은 똑같습니다.
그런데 HTML 이 아닌 ASP 페이지를 요구하는 경우, 서버에서는 이것을 HTML 처럼 바로 돌려보내 주는 것이 아니라 ASP.DLL 이라는 특이한 친구를 실행시키고 나서,
그 결과물(그 결과로 작성된 HTML)을 클라이언트에게 돌려보내 준다는 것입니다.
이 한 가지의 과정의 추가로 인해서 HTML 과 ASP 는 엄청난 차이를 가지게 됩니다.

음.. 아직 잘 이해가 안가시나요...? 좋습니다.
그렇다면 앞에서 예를 들었던 '현재 시간' 을 표시하는 두 페이지의 소스를 비교해 보겠습니다.
다음의 내용을 유심히 보시기 바랍니다.

HTML
현재 시간은

2003-04-15 오전 10:08:07 입니다.
ASP
현재 시간은

<%=now%> 입니다.

전체 소스가 아닌 일부분의 소스만 올려놓았습니다. 그 이유는 HTML 과 ASP 의 차이를 말씀드리려는 데에는 이 소스만으로도 충분할 것 같네요. (사..사실은 귀찮아서... -_-a)

HTML 페이지에서는 보시다시피 시간을 직접 입력 해버렸습니다.
그러므로 위에서 말씀드렸던 것처럼 백날~ 새로고침을 해도 시간은 바뀌지 않습니다.

하지만 ASP 는 <%=now%> 라는 약간 낯선 형태의 무언가가 등장했습니다.
자세한 설명은 다음에 드릴 예정입니다만 이것의 의미를 간략하게 말씀드리자면,
'ASP 안에서 현재 시간을 의미하는 now 라는 함수를 호출하여 출력하세요' 라는 뜻이 됩니다.
(모든 HTML 태그가 '<' 로 열고 '>' 로 닫는 것과 마찬가지로, ASP 는 '<%' 로 열고 '%>' 로 닫아야 합니다. 이것은 ASP 문법의 기본이므로 반드시 알아두시기 바랍니다.)

때문에 페이지를 '새로 고침' 하면, HTML 페이지는 단순히 입력된 내용만을 전달해 주지만,
ASP 페이지는 페이지 안에 있는 ASP 소스(<%=now>)를 'ASP.DLL' 에 통과시킨 다음,
그 결과(현재 시간)를 HTML 형식으로 받아서 클라이언트에게 출력해 주게 되는 것입니다.

이 과정을 그림으로 표현하자면 다음과 같습니다.

어떻습니까? 이제 ASP 라는 친구가 조금은 친숙해 지셨나요?

그렇다면.. 이제 ASP 의 탄생 배경에 대해서 잠시 살펴보도록 하겠습니다.
(솔직히 이런 역사 시간 같은 이야기는 지루한 게 사실이지만, 그래도 언제, 누가, 어떻게 만들었는지 정도는 상식으로 알아두시는 것도 좋지 않을까요? ^^)

ASP는 마이크로소프트(Microsoft) 사에 의해서 1996년 7월 16일에 데날리(Denali) 라는 코드명으로 공식적으로 발표되었습니다. 이것의 베타 버전은 1996년 11월에 배포되었고, ASP 정식 버전 1.0 이 세상에 선보이게 된 것은 1996년 12월 12일이었습니다.
마이크로소프트 사에서 1997년 3월에 IIS 웹서버를 제공하면서부터 ASP 는 더욱 많이 알려지게 되었으며, 98년에는 IIS 4.0 과 퍼스널 웹 서버 4.0 (PWS 4.0)을 발표하게 됩니다.
이 둘은 ASP 버전 2.0을 지원했으며, ASP 1.0 에 비해 많은 성능 향상을 가져오게 됩니다.
(실제로 우리 나라에서 많은 개발자들이 ASP 에 관심을 가지게 된 때가 바로 이때였습니다.)
Windows 2000 이 배포되면서 마이크로소프트 사는 그 안에 IIS 5.0 과 ASP 3.0 을 포함하였습니다. 또한 IIS 5.0 은 Windows 2000 운영체제 안에 자연스럽게 통합 되었습니다.
(그래서 Windows 2000 을 설치하셨다면 좀 더 편하게 ASP 를 공부하실 수가 있습니다.) 

2. ASP 는 어디에 쓰이는 물건인가?

도대체 이 ASP 를 가지고 무엇을 할 수가 있을까요?
'이 홈페이지 너무 멋진데요' 라고 한마디 써주고 싶은데, HTML 로 만든 페이지에서는 아쉽게도 그것이 불가능한 것이지요. ASP 의 필요성은 바로 여기서 나타납니다.

ASP 페이지에서는 방문한 사람들(클라이언트)에게 글을 입력받아서 그것을 저장소 - 이것을 '데이터베이스' 라고 합니다 - 에 차곡차곡 저장한 후에, 클라이언트들이 그 페이지를 보여달라고 요청할때 그 저장소(데이터베이스)에 저장되어 있는 내용을 꺼내와서 보여주게 됩니다.
그렇기 때문에 ASP 로 만든 페이지에서는 새로운(최근에 작성된) 글을 보는 것이 가능합니다.

이런 '게시판' 기능 뿐 아니라.. ASP 가 할 수 있는 일은 상당히 다양합니다.
다음이나 세이클럽 같은 사이트에 가서 여러분은 아이디와 비밀번호를 입력하고,
그것이 맞을 때에는 사이트 안으로 로그인 해서 들어갈 수가 있습니다.
이런 회원 인증을 담당하는 페이지 역시 ASP 로 작성 가능합니다.


http://blog.daum.net/ssc1978/13852608



Active Server에서 제공하는 Web Page라는 뜻인데 여기서 Active Server란 마이크로소프트 웹 서버인 IIS(InternetInformation Server)안에 존재하는 Active Server Framework를 나타내는 것으로 주로 ActiveX Script를 처리하거나 DataBase와 연동하는 역할을 합니다. ASP는 하나 이상의 스크립트를 담은 일종의 HTML 페이지로서 사용자에게 보내지기 전에 일단 웹 서버에서 처리 과정을 거치게 됩니다. ASP파일은 일반 text파일로서 메모장 등에서 생성되는 파일과 같은 성질을 가지며 확장자는 asp입니다. 따라서 메모장에서 작성한 다음 확장자 .asp로 저장을 하면 됩니다. asp파일에는 HTML 태그와 JavaScript나 VBScript등의 스크립트 코드, 그리고 ASP 코드 등을 섞어 사용할 수 있습니다. JavaScript나 VBScript 등의 스크립트 코드는 <SCRIPT>,</SCRIPT>태그 사이에 놓입니다. ASP 코드는 <% ~ %>사이에 놓입니다. 왜 ASP를 사용하나요 나모나 HTML로 홈페이지를 만들어 본 사람들은 어느 정도 시간이 지나면 자기의 생각을 홈페이지에서 마음대로 구현할 수 없다는 것에 실망을 하게 될 것입니다. 자바스크립트도 해 보고 플래쉬도 해 보지만 역시 만족스럽지 못합니다. 이 때 눈을 돌리게 되는 것이 ASP라고 할 수 있지요. 물론 대신에 CGI나 PHP라는 말도 많이 듣게 되겠지만.....그러면 사람들은 왜 ASP를 사용하고 있을까요? 

1) 사용자와의 동적인 상호작용을 원하기 때문입니다. HTML은 기본적으로 정보를 보여주기만 합니다. 하이퍼링크를 통해 사용자가 요청을 하면 웹서버가 그 요청에 응답하여 원하는 웹 페이지를 보여주는 방식으로 작업이 진행되지요. 그것도 일종의 상호작용이라고 할 수는 있겠지만 웹 서버를 운영하는 사람과 사용자가 서로 어떤 정보를 주고 받는다든지 아니면 사용자들간에 서로 정보를 주고 받는다든지 하는 일은 기본적으로 불가능합니다. ASP는 HTML로 불가능한 이런 일들을 가능하게 해 줍니다.

 2) 서버측 자원을 사용해야 하는 경우입니다. 사용자로부터 어떤 내용을 입력받아 데이터베이스에 저장해야 할 경우와 같은 건데 이럴 경우는 반드시 ASP를 사용해야만 합니다. 예를 들어 게시판 작성, 파일 업로드, ID 인증 등과 같이 서버에 어떤 정보를 저장하거나 저장된 정보를 이용해 일을 하는 경우에는 ASP를 사용해야만 합니다. 왜냐하면 HTML은 원칙적으로 클라이언트에서 번역되는 문서이기 때문에 서버의 다른 자원에 접근할 수가 없기 때문입니다.

 3) 스크립트의 안정적인 실행을 위해서입니다. 자바스크립트를 예를 들어 볼까요? 자바스크립트도 날이 갈수록 버전이 높아지고 있습니다. v1.0, v1.1, v1.2, v1.3... 그러다보면 상위 버전의 자바스크립트를 삽입한 HTML문서가 어떤 웹 브라우저에서는 의도하는대로 번역이 되지 않는 사태가 벌어질 수도 있습니다. 이럴 경우 서버에서 실행되는 스크립트라면 서버에서 HTML형태로 번역된 후 넘겨지게 되니까 어떤 웹 브라우저에서라도 잘못될 염려가 없을 것입니다. 

4) 스크립트 소스를 감추기 위해서입니다. 클라이언트측 스크립트들은 HTML 속에 포함되어 서버에서 클라이언트로 전송된 다음 클라이언트의 웹 브라우저에서 번역됩니다. 따라서 사용자들은 소스보기를 통해 스크립트의 내용을 볼 수가 있습니다. 그러나, 서버측 스크립트를 사용함으로써 개발자는 자신의 독특한 알고리즘을 감출 수가 있습니다. 물론 이런 목적을 위해 ASP를 사용한다는 것을 좋다고 할 수는 없겠지만 이런 기술로 밥먹고 사는 사람들에게는 꼭 필요한 것이 아닐까요?
















'프로그래밍 > 웹 프로그래밍' 카테고리의 다른 글

HTML 기초  (0) 2016.02.21
비즈니스 로직(Business logic)?  (0) 2016.02.14
웹서버(Web Server) / 웹 서버 어플리케이션(WSA)  (0) 2016.02.14
웹 프로그래밍 기초  (0) 2016.02.14
ASP(Active Server Page)  (0) 2016.01.28
IIS란?  (0) 2016.01.25
Posted by GENESIS8

댓글을 달아 주세요


패킷이건 데이터건 압축하면 용량이 줄어든다. 어떻게 한 것일까?

압축의 원리에 대해서 조사해보자.



데이터 압축은 데이터를 더 적은 저장 공간에 효율적으로 기록하기 위한 기술, 또는 그 기술의 실제 적용을 가리킨다. 크게 데이터를 더 작은 크기로 변환시키는 인코딩 과정저장된 데이터를 다시 불러와 원래 데이터 형태로 복원시키는 디코딩 과정으로 이루어진다. 

이때 인코딩하기 전의 데이터 크기와 인코딩하고 나서의 데이터 크기의 비율을 압축률이라고 한다. 압축 기술의 종류에 따라 데이터의 내용을 바꾸지 않고 원래 내용 그대로 디코딩할 수 있는 무손실 압축과 더 높은 압축률을 얻을 수 있지만 디코딩한 데이터의 세부적인 디테일을 일부 희생시키는 손실 압축이 존재한다. 대표적인 무손실 압축 알고리즘에는 반복 길이 부호화와 허프만 부호화 , 산술 부호화 등이 있다. 손실 압축 알고리즘은 인간의 감각 기관의 특성을 역이용하여 압축률을 높이므로, 음성, 정지화상, 동영상 등 데이터의 종류에 따라 각각 다른 알고리즘이 사용된다. MPEG 표준 압축기술이 많이 쓰인다.



압축의 원리

방식에 따라 다르지만 대체적으로 파일 내에서 일정한 디지털 코드 패턴이 여러번 나오는 지점에 그런게 있다는 것만 표시해 두고, 그 표시된 것과 원본을 그대로 복구하기 위해서 그에 관련된 사전을 저장한 후, 압축 파일을 만든다.


이로 인해 압축률은 대부분의 경우 손실 압축보다 떨어지며, 이미 다른 압축 포맷을 적용하였다면, 또 다른 압축 포맷을 적용해도 별로 효용성이 없다. 또는 원래부터 압축된 데이터(이미 압축 한 파일, mp3, 동영상 등)는 또 압축해 봐야 소용 없다. 일부러 보관의 편의를 위해 다중압축파일을 만들고 또 통 압축 파일을 만들거나 하는 경우는 있다. 이런 경우에는 압축이라기 보다 그냥 무압축 컨테이너 개념으로 사용한다.


1) 데이타 압축기법 분류 데이타 압축기법은 크게 다음과 같이 나눌 수 있다. 복원가능(reversible)한 방법 복원 가능한 방식은 압축된 형태의 데이타로부터 본래의 데이타를 손실없이 얻을 수 있음을 의미한다. 

복원가능한 방식을 noiseless coding 또는 용장성 감소(redundancy reduction)방식이라 한다. 정보통신에 있어서 취급되는 대부분의 데이타 압축기법은 용장성 감소방식을 그 대상으로 하고 있다.


용장성 감소 기법은 먼저 정보원 데이타와 압축 후 부호어 길이에 따라 FF(Fixed to Fixed)부호 FV(Fixed to Variable)부호 VF(Variable to Fixed)부호 VV(Variable to Variable)부호 복원 불가능(irreversible)한 방법 


복원 불가능한 방식은 압축된 형태로부터 원래의 데이타를 재생시킬 수 없음을 의미하는 것으로, 이 방식은 fidelity reducing coding 혹은 엔트로피 감소(entropy reduction) 방식이라 한다. 엔트로피 감소방식은 데이타가 포함하고 있는 유효한 정보와 불필요한 용장성 가운데 정보부분을 줄이는 방법으로서 일반적으로 음성, 화상 등과 같이 복원된 데이타가 어느정도 애매모호하더라도 상관없는 아날로그 데이타의 압축기법으로서 널리 사용되고 있다. 

용장성 감소 방식에 비해 비교적 높은 압축률을 얻을 수 있으나 화상전송 등과 같이 특정 응용분야와 관련되어 데이타의 의미나 전후 문맥을 고려해 압축을 수행한다. 



일반적으로 자주 이용되는 압축기법은 다음과 같다.


Run-length코딩 방식 - 입력데이타 내에서 연속적으로 반복되는 문자를 물리적으로 압축 Difference Mapping - 서로 인접하는 데이타값의 차를 이용 패턴대치(Pattern Sudstitution) - 자주 출현하는 패턴, 즉 문자 블럭을 하나의 압축부호어로 할당 

허프만 압축 - 원 데이타의 출현빈도에 따라 자주 나타나는 문자에는 짧은 부호를, 자주 나타나지 않는 부호에는 긴 부호어를 할당 수정 

허프만압축기법 - 팩시밀리 통신에 있어서 표준압축기법으로서 채용되고 있음

LZW(Lempel-Ziv-Welch) 압축기법 - 정보원 데이타의 통계적 성질을 이용하지 않고 데이터로부터 패턴을 생성함으로써 압축을 수행


일반 포맷 - 일반적으로 사용하는 '무손실' 포맷방식

음악 포맷 - mp3,Ogg Vorbis(손실 압축 포맷) / Apple Lossless (무손실)

이미지 포맷 - PCX,GIF,PNG 등이 이에 속한다. GIF도 무 손실이지만 최대 256색이기 때문에, 256색을 넘는 경우 디더링을 통해서 손실 발생.

raw 포맷 - 디지털 카메라에 주로 쓰이는 raw 이미지 포맷을 의미.

동영상 포맷 - 보통 무손실 영상 포맷의 용량이 상상을 초월하므로 일반인은 쓸 일이 없다.





그래서 종류나 개요는 대충 알겠지만 무슨 원리고 어떤 건지는 모르겠다.

아래의 글들이 원리나 동작을 이해하는 데 도움이 됬다.


출처

http://huniv.hongik.ac.kr/~ginnie/communication/%C1%A4%BA%B8%C5%EB%BD%C507_%BE%D0%C3%E0.htm


  • Run -length 압축기법

이 압축기법은 정보원 데이타 내에 계속하여 반복되는 문자열에 대해서 그림(a)와 같은 압축형식을 이용, 데이타 크기를 물리적으로 축소할 수 있는 기법이다. 그 압축 예를 그림(b)에 나타냈다.




반복되는 문자를 치환해서 줄여버린다.

  • 허프만(Huffman) 압축기법

허프만 압축기법은 1954년 허프만에 의해 제안된 압축 방식으로 오늘날에도 널리 이용되고 있다. 이 기법은 정보원 데이타내의 각 문자에 대한 발생빈도를 조사해 자주 나타나는 문자에는 보다 짧은 부호어를, 그리고 잘 나타나지 않는 문자에는 더 긴 부호어를 할당함으로써, 전체 압축후 부호어의 길이를 원래의 정보원 길이보다 더 축소시킬 수 있통계적 특성을 이용한 압축기법이다. 허프만 압축 기법의 일례를 다음 그림에 나타내었다.

 

앞의 그림의 경우에 있어서는 원래의 정보원 데이타 내의 각 문자들은 3비트의 고정된 길이로서 표현되지만 허프만 압축기법에 의해 가장 자주 나타나는 A라는 문자에는‘0’, 즉 1비트의 부호어가, 그리고 가장 자주 나타나지 않는 문자인 H에는‘111111’이라는 6비트의 부호어가 할당되어 있다. 따라서 압축전과 압축후의 전체 데이타 길이의 비율을 계산한 결과 압축에 의해 20%의 축소효과를 가져왔음을 알 수 있다.

허프만 압축기법을 적용한 압축 방식으로는 현재 팩시밀리 통신의 표준으로서 권고되고 있는 수정 허프만부호가 있다. 팩시밀리 통신은 앞에서도 언급한 바와 같이 이미지정보이므로 서류의 한 줄당 최소 1728비트의 데이타가 필요하게 된다. 수정 허프만 기법은 각 줄당 1728개에 달하는 데이타가 모두 흑(‘1’인비트)과 백(‘0’인비트)으로 이루어져 있으며 또 이미지정보의 경우 흑과 백의 분포가 상호연관되어 있는 점에 착안, 각 줄당 흑과 백의 반복갯수마다 앞의 허프만 기법을 적용해 압축부호어를 구함으로써 데이타를 축소시킬수 있게 된다. 현재 통계에 의하면 이 기법에 의해 원래 팩시밀리 통신의 이미지정보를 평균 약1/8이하로 축소해 전송할 수 있다고 한다.

허프만 압축기법의 또다른 변형으로는 상용 압축파일 가운데서 가장 압축률이 우수한 LHARC라는 압축파일이 채용하고 있는‘적응적 허프만부호’를 들 수 있다. 허프만 압축기법이 미리 조사된 정보원 데이타의 통계적 성질을 이용해 압축을 수행하는 반면, 이 기법은 원래 데이타의 각 문자 입력시마다 적응적으로 발생문자의 빈도수를 계산이 확률값에 따라 허프만부호를 할당하는 압축방식이다.동적 압축기법은 압축수행에 소요되는 시간 때문에 정보통신분야 에서는 잘 이용하지 않는다. 

-> 통계를 통해서 허프만 방식을 쓰는 게 아니라, 데이터 자체를 동적으로 분석해서 그 데이터에 대한 허프만 방식을 구성해서 압축.

  • LZW 압축기법

CCITT의 V.42vis에 채용되어 있는 LZW 압축기법은 1978년 이스라엘 Lempel과 Ziv가 처음으로 제안한 것을 1985년 현재 유니시스사의 전신인 스페리사의 Welch가 수정구현한 압축기법이다. 이 기법은 입력 데이타 길이를 가변으로 하고 출력부호의 길이를 고정한 기법으로서 데이타압축률이 높으며 내부 연산량이 작기 때문이 압축수행속도 측면에서는 현재까지 가장 빠른 것으로 평가되고 있어 CCITT의 표준권고를 기점으로 정보통신에 널리 이용될 것으로 보인다

처음 제안된 LZW 알고리즘은 가변길이의 입력문자열을 모두 12비트의 고정길이로 2진 부호화했으나 그후 초기 압축효율의 개선을 위해 9비트부터 시작해 문자열 테이블내에 할당된 부호어의 범위에 따라 12비트까지 2진 부호화하도록 개선된 LZW알고리즘이 주로 사용되고 있음으로 여기에서는 이 후자의 알고리즘을 대상으로 하였다.

또 LZW알고리즘을 채용하고 있는 상용 압축파일에는 국내에서 자주 쓰이고 있는 PKARC, PKZIP 등이 있다. LZW알고리즘에 있어서 문자열 테이블내에 생성되는 문자열의 개수는 사용시스템의 허용능력에 따라 확장할 수 있다. 상용 압축파일인 PKARC는 테이블내 최대 문자열 엔트리를 4096으로 제한하고 있으며 PKZIP은 이를 8192로 제한하고 있다. 일반적으로 허용가능한 문자열 엔트리를 늘릴수록 압축률은 향상된다. CSLIP(Compressed Serial Line Interface Protocol, CSLIP은 SLIP(Serial Line Interface Protocol)의 변형된 프로토콜로 IP패켓을 전화선과 같은 직렬회선(Serial line)에 전송하는데 이용된다. SLIP과 CSLIP은 같은 용도로 사용되나 CSLIP은 압축된 패켓헤더를 사용하므로서 SLIP보다 효율적이다. 압축은 Van Jacobson 방법이 이용되는데 연속되는 패켓의 차이만을 전송하므로서 압축기능을 수행한다.




출처 : http://sonhy1.tistory.com/36


< 목   차 >
1 Prologue 3
2 Introduction 4
3 Run-Length 6
3.1 Run-Length 압축 알고리즘 6
3.2 Run-Length 압축 복원 알고리즘 10
3.3 Run-Length 압축 알고리즘 전체 구현 11
4 Lempel-Ziv 19
4.1 Lempel-Ziv 압축 알고리즘 19
4.2 Lempel-Ziv 압축 복원 알고리즘 26
4.3 Sliding Window를 이용한 Lempel-Ziv 알고리즘의 구현 27
5 Variable Length 39
6 Huffman Tree 43
6.1 Huffman 압축 알고리즘 51
6.2 Huffman 압축 복원 알고리즘 56
6.3 Huffman 압축 알고리즘 구현 60
7 JPEG (Joint Photographic Experts Group) 72
7.1 JPEG이란 72
7.2 다른 기술과의 비교 72
7.3 압축 방법 73
7.4 Baseline 압축 알고리즘 75
7.5 JPEG의 실제 압축 / 복원 과정 76
7.6 확장 JPEG 79
8 MPEG (Moving Picture Expert Group) 80
8.1 MPEG의 개념 80
8.2 MPEG의 표준 81
8.2.1 MPEG 1 81
8.2.2 MPEG 2 82
8.2.3 MPEG 4 83
8.3 MPEG의 기본적인 압축 원리 84
8.3.1 시간,공간의 중복성 제거 84
8.3.2 I,P,B영상 86
9 Conclusion 87


< 그 림 목 차 >

<그림 3‑1> Run-Length 압축 알고리즘 10
<그림 3‑2> 압축 파일 헤더 구조 12
<그림 4‑1> 슬라이딩 윈도우와 해시테이블 22
<그림 5‑1> 8비트에서 7비트로 줄이는 압축 알고리즘 39
<그림 5‑2> 문자 코드의 재구성 40
<그림 5‑3> <그림 5‑2>코드의 기수 나무 41
<그림 5‑4> 문자 코드의 재구성 41
<그림 6‑1> 빈도수 계산 44
<그림 6‑2> 허프만 나무 구성과정 48
<그림 6‑3> 허프만 나무에서 얻어진 코드 51
<그림 6‑4> code[]와 len[]의 저장 55
<그림 7‑1> JPEG Encoding / Decoding 단계 76
<그림 7‑2> RGB의 YIQ 변환식 77

1 Prologue 
지금 생각하면 우스운 일이지만 몇 년 전만 하더라도 28800bps의 모뎀을 굉장히 빠른 통신 장비로 알고 있었다. 그러다가 56600bps의 모뎀이 발표되었을 때는 전화선의 한계를 뛰어 넘은 대단한 물건이라고 다들 놀라와 했다. 내 경우에도 56600bps 모뎀을 구입해서 처음 사용하던 날 감격의 눈물을 흘렸을 정도였으니..
전화로 통신을 하던 그 당시 사람들의 생각은 다들 비슷했을 것이다. 어떻게 하면 같은 내용의 자료를 더 짧은 시간에 전송할 수 있을까. 통신속도가 점차 빨라지면서(처음에 사용하던 2400bps에 비하면 거의 20배 이상의 속도 향상이었다.) 이런 고민은 줄어들 것이라 생각했지만, 그런 고민은 오히려 더 커져 만 갔다. 속도가 빨라지는 것보다 사람들이 주고받는 자료의 전송 량이 더 크게 증가한 것이다. 이럴 수록 더 강조되던 것이 바로 [압축] 이었다. 
파일 압축이라고 하면 winzip, alzip 등을 생각할 것이다. 이런 종류의 프로그램들은 임의의 파일을 원래의 크기보다 작은 크기로 압축시켰다가 필요할 때 다시 원래대로 한치의 오차도 없이 복구 시켜 준다. 
하지만 압축이란 것이 모두 앞에서 언급한 프로그램들처럼 원본을 그대로 복원해줄 수 있는 것이 아니다. 때에 따라서는 원본으로의 복원이 불가능한 압축 방법들이 유용하게 사용될 상황도 존재한다. 
전자의 경우를 ‘비손실 압축’, 후자의 경우를 ‘손실 압축’ 이라고 하는데, 이 자료에서는 모든 압축의 근간이 되는 간단한 압축 알고리즘들을 살펴볼 것이고 뒤에 손실 압축의 대표적인 MPEG에 대해서 다룰 것이다. 
이제 우리는 압축의 세계로 들어간다.

2 Introduction
우리가 보통 살펴보는 알고리즘들은 대부분이 시간을 절약하기 위한 목적을 가지고 개발된 것 들이다. 하지만, 우리가 지금부터 살펴볼 알고리즘들은 공간을 절약하기 위한 목적을 가진 알고리즘이다. 
압축알고리즘이 처음으로 대두되기 시작한 것은 컴퓨터 통신 때문이었다. 컴퓨터 통신에서는 시간이 곧바로 돈으로 연결된다(적어도 model을 사용하던 시절에는 그랬다). 예를 들어 1MByte의 파일을 다운로드 받으려면 28,800bps 모뎀을 사용하면 약 6분, 56,600bps 모뎀을 사용하더라도 약 3분 이상의 시간이 소요됐었다. 하지만 이 파일을 전송 전에 미리 1/2로만 압축할 수 있다면 전송시간 역시 1/2로 줄어들 것이다. 즉, 통신 비용 역시 1/2로 줄어든다는 것이다.
압축 알고리즘은 크게 두 부류로 나뉜다. 비손실 압축(Non-lossy Compression)과 손실 압축(Lossy Compression)이 그것인데 말 그대로 비손실 압축은 압축했다가 다시 복원할 때 원래대로 파일이 복구된다는 뜻이고, 손실 압축은 복원할 때 100% 원래대로 복구되지 않는다는 뜻이다. 
일반적으로 PC사용자들이 사용하는 압축프로그램들은 모두 비손실 압축을 지원한 프로그램들이다. 그렇다면 손실 압축은 어떤 경우에 사용하는 것일까?
확장자가 exe나 com으로 끝나는 실행파일이나, 기타 한 바이트만 바뀌더라도 프로그램 실행에 지장을 주는 파일들은 반드시 비손실 압축을 해야 한다. 그러나 그림 파일이나 동화상처럼 눈으로 보는 것에 지나지 않는 파일의 경우 약간의 손실이 있어도 무방하다. 
일반적으로 손실 압축이 비손실 압축에 비해서 압축률이 훨씬 좋기 때문에 손실 압축도 또한 큰 중요성을 가지고 있다. 요즘 화제가 되고 있는 JPEG(정지 화상 압축 기술, Joint Photographic Expert Group), MPEG(동화상 압축 기술, Moving Picture Expert Group) 등도 대표적인 손실 압축법으로 주목 받고 있는 것들이다.


압축 알고리즘은 그 중요성으로 인해 오랫동안 연구되어 왔고, 많은 알고리즘이 있다. 가장 대표적인 압축 알고리즘은 Run-Length 압축법으로 동일한 바이트가 연속해 있을 경우 이를 그 바이트와 몇 번 반복되는지 수치를 기록하는 방법이다. 그러나 Run-Length 압축법은 간단함에 대한 대가로 압축률이 그다지 좋지 않아서 다른 방법들이 연구되어 왔다. 
그래서 실제로 구현되는 압축 방법은 이 절에서 소개하는 Huffman 압축법과 Lempel-Ziv 압축법이다. 가변길이 압축법은 한 바이트가 8비트라는 고정 관념을 깨고, 각각을 다른 비트로 압축하는 방법이고, 그 중에서도 Huffman 압축법은 빈도가 높은 바이트는 적은 비트수로, 빈도가 낮은 바이트는 많은 비트수로 그 표현을 재정의하여 파일을 압축한다. 
반면에 Lempel-Ziv법은 그 변종이 여러 개 있지만 가장 효율적인 동적 사전(Dynamic Dictionary)을 이용한 방법을 주로 사용한다. 동적 사전법은 파일에서 출현하는 단어(Word)들을 2진 나무(Binary Tree)나 해시를 이용한 검색 구조에 삽입하여 동적 사전을 구성한 다음, 이어서 읽어진 단어가 동적 사전에 수록되어 있으면 그에 대한 포인터를 그 내용으로 대체하는 방법으로 압축을 행한다. 주로 사용하는 ZIP 등도 Huffman 압축법이나 Lempel-Ziv 압축법 중 하나를 사용하거나 또는 둘 다 사용하거나, 혹은 그 응용을 사용한다.

3 Run-Length
3.1 Run-Length Encoding
Run-Length 압축법은 동일한 문자가 이어서 반복되는 경우 그것을 문자와 개수의 쌍으로 치환하는 방법이다. 예를 들어 다음의 문자열은 Run-Length 압축법으로 쉽게 압축될 수 있다. 

원래 문자열 : ABAAAAABCBDDDDDDDABC
압축 문자열 : ABA5BCBD7ABC 

개념적으로는 위와 같이 간단하지만 개수로 사용된 5나 7이라는 문자가 개수의 의미인지 아니면 그냥 문자인지를 판별하는 방법이 없다. 만일 압축할 파일이 알파벳 문자만을 사용한다면 위와 같은 압축이 그대로 사용 가능할 것이다. 그러나 일반적으로 0부터 255까지의 모든 문자가 사용된 파일을 압축한다면 단순한 위의 방법으로는 압축이 불가능하다. 
그래서 탈출 문자(Escape Code)라는 것을 사용한다. 문자가 반복되는 모양을 압축할 때 <탈출 문자, 반복 문자, 개수>와 같이 표현한다. 예를 들어 탈출 문자를 ‘*’라고 한다면 위의 문자열은 다음처럼 압축 될 수 있다. 

원래 문자열 : ABAAAAABCBDDDDDDDABC
압축 문자열 : AB*A5BCB*D7ABC 

탈출 문자에서 탈출의 의미는 보통의 경우에서 벗어남을 말한다. 즉 탈출 문자 ‘*’가 나오기 전에는 단순한 문자열이지만 이 탈출 문자가 나오면 그 다음의 반복 문자와 그 다음의 개수를 읽어 들여서 반복 문자를 개수만큼 늘여 해석하면 된다. 
또 한가지 남은 문제가 있다. 그것은 탈출 문자가 탈출의 의미로 해석되는 것이 아니라 문자로서 해석되어야 할 경우도 있다는 점이다. 이것은 마치 printf() 함수의 서식 문자열에서 ‘%’와 유사하다. %d나 %f는 그 문자를 의미하는 것이 아니라 정수나 실수형으로 대치될 부분이라는 표시이다. 즉 %가 탈출의 의미를 가지고 있다는 뜻이다. 그러나 정작 ‘%’라는 문자를 출력하기 위해서는 어떻게 해야 하는가?
C에서는 ‘%’를 출력하기 위해서 ‘%%’를 사용한다. 마찬가지로 Run-Length 압축법에서도 탈출 문자 ‘*’를 문자로 해석하기 위해서 ‘**’를 사용하면 될 것이다. 
그렇다면 ‘*’ 문자가 계속해서 반복되는 경우는 어떻게 해야 하는가? 이 문제는 상당히 복잡하다. 만일 ‘*****’와 같은 문자열의 일부분이 있다면 ‘**5’와 같이 압축할 수 있는가? 아니면 ‘***5’와 같이 압축하는가? 둘 다 문제가 있다. 전자의 경우 ‘*5’와 같이 해석할 수 있으며, 후자의 경우는 ‘*’문자와 5 다음의 문자가 있다면 이를 개수로 해석해서 5를 반복하는 것으로 해석할 수 있다. 
이렇게 탈출 문자가 반복되는 경우 그것을 <탈출 문자 반복 문자 개수>의 표현으로 나타내면 모호하게 되므로 탈출 문자자의 경우는 아무리 반복 횟수가 많더라도 단순하게 <탈출 문자, 탈출 문자>와 같이 압축한다(실제로는 더 길어지지만). 

원래 문자열 : ABCAAAAABCDEBBBBBFG*****ABC
압축 문자열 : ABC*A5BCDE*B5FB**********ABC 

이러한 이유로 탈출 문자 ‘*’는 가장 출현 빈도수가 적은 문자를 택해야 한다. 왜냐하면 탈출 문자가 문자로 해석되는 경우에는 그 길이가 두 배로 늘어나기 때문이다. 이 출현 빈도수라는 것이 사실 모호하기 짝이 없지만 일단은 영어의 알파벳이나 기호, 탭 문자(0x09), 라인 피드(0x0A), 캐리지 리턴(0x0D) 그리고 널문자(0x00)와 같은 코드들은 매우 많이 사용되기 때문에 피해야 한다. 따라서, 압축하는 파일에 따라 탈출 문자를 적절히 조정해 주면 압축 효율을 높일 수 있을 것이다. 
그렇다면 과연 몇 개의 문자가 반복되었을 때 <탈출 문자, 반복 문자, 개수>로 치환할 것인가 하는 문제를 결정하자. ‘AA’처럼 두 문자가 반복되었다면 ‘*A2’로 하는 것은 두 바이트가 3바이트로 늘어나게 되므로 치환하지 말아야 할 것이다. 그렇다면 ‘AAA’와 같이 세 문자가 반복된다면 ‘*A3’으로 하는 것은 똑같이 세 바이트가 소요되므로 치환을 하든 하지 않든 변화가 없다. 따라서 같은 문자가 최소 3번 이상 반복되는 경우에만 치환을 하도록 한다. 
그리고 개수를 나타내는 것 또한 1Byte를 사용하기 때문에 반복되는 문자의 개수는 255 이상이 될 수 없다. 만약 255개를 넘어버린다면 254에서 한번 잘라주고, 그 다음은 문자가 처음 나온 것으로 생각하면 된다.
위와 같은 방법으로 구현된 Run-Length 알고리즘은 다음과 같다.

<Run-Length 압축 알고리즘(FILE *src)
{
  char code[10];      /* 버퍼 */
  cur = getc(src);        /* 입력 파일에서 한 바이트 읽음 */
  code_len = length = 0;
  
  while(!feof(src))
  {
       if (length == 0)    /* code[]에 아무 내용이 없으면 */
       {
           if (cur != ESCAPE)
           {
               code[code_len++] = cur;
               length++;
           }
           else        /* 탈출 문자이면 <탈출문자 탈출문자>로 대체 */
           {
               code[code_len++] = ESCAPE;
               code[code_len++] = ESCAPE;
               flush(code);        /* 출력 파일에 써넣음 */
               length = code_len = 0;
           }
           
           cur = getc(src);
       }
       else if (length == 1)   /* 반복 횟수가 1 이었으면 */
       {
           if (cur != code[0])     /* 읽은 문자가 버퍼의 문자와 다르면 */
           {
               flush(code);    /* 버퍼의 내용을 출력 */
               length = code_len = 0;
           }
           else    /* 읽은 문자가 버퍼의 문자와 같으면 */
           {
               length++;
               code[code_len++] = cur;     /* 'A' -> 'AA' */
               cur = getc(src);
           }
       }
       else if (length == 2)       /* 반복 횟수가 2 이면 */
       {
           if (cur != code[1])     /* 읽은 문자가 버퍼의 문자와 다를 경우 */
           {
               flush(code);    /* 버퍼의 내용을 출력 */
               length = code_len = 0;
           }
           else    /* 읽은 문자가 버퍼의 문자와 같으면 */
           {
               length++;
               code_len = 0;
               code[code_len++] = ESCAPE;      /* 'AA' -> '*A3' */
               code[code_len++] = cur;
               code[code_len++] = length;
               cur = getc(src);        /* 다음 문자를 읽음 */
           }
       }
       else if (length > 2)        /* 반복 횟수가 3 이상이면 */
       {
           if (cur != code[1] || length > 254)    
           {       /* 읽은 문자 != 버퍼의 문자 or 반복 횟수 > 255 */
               flush(code);        /* 버퍼의 내용 출력 */
               length = code_len = 0;
           }
           else    /* 읽은 문자가 버퍼의 문자와 같으면 */
           {
               code[code_len-1]++;     /* 반복 횟수만 증가 */
               length++;
               cur = getc(src);        /* 다음 문자를 읽음 */
           }
       }
  }
  
  flush(code);        /* 버퍼의 내용을 출력 */

<그림 3‑1> Run-Length 압축 알고리즘

3.2 Run-Length Decoding
압축을 하고 나면 다시 복원을 하는 알고리즘도 있어야 할 것이다. Run-Length 압축법의 복원은 상당히 단순하다. 파일을 읽으면서 탈출 문자가 없으면 그대로 두면 되고, 탈출 문자를 만난다면, 다음 글자를 하나 더 읽어봐서 다시 탈출 문자가 나오면 탈출 문자를 그대로 기록하고, 숫자가 나오면 탈출 문자 전의 문자를 그 숫자만큼 반복해서 적으면 된다. 
위와 같은 방법으로 구현된 Run-Length 압축 복원 알고리즘은 다음과 같다.

<Run-Length 압축 풀기 알고리즘(FILE *src)>
{
  int cur;
  FILE *dst;
  int j;
  int length;
  
  dst = fopen(출력파일);
  cur = getc(src);
  while (!feof(src))
  {
       if (cur != ESCAPE)      /* 탈출 문자가 아니면 */
           putc(cur, dst);
       
       else    /* 탈출 문자이면 */
       {
           cur = getc(src);
           if (cur == ESCAPE)      /* 그 다음 문자도 탈출 문자이면 */
               putc(ESCAPE, dst);
           
           else        /* 길이만큼 반복 */
           {
               length = getc(src);
               for (j = 0; j < length; j++)
                   putc(cur, dst);
               
           }
       }
       
       cur = getc(src);
  }
  
  fclose(dst);

3.3 Run-Length 압축 알고리즘 전체 구현
실제로 압축된 파일의 복원을 위해서는 몇 가지 추가적인 정보가 필요하다. 그것은 복원하려는 파일이 과연 Run-Length 압축 알고리즘에 의한 것인지를 판별하는 식별 코드와 복원할 파일의 원래 이름이다. 이 두 정보는 압축할 때 압축 파일의 선두(헤더)에 기록되어 있어야 한다. 
Run-Length 압축 알고리즘의 식별 코드는 편의상 0x11과 0x22로 했고, 이어서 원래 파일의 이름이 나오고, 끝을 나타내는 NULL문자가 이어진다. 다음은 이 헤더의 구조를 나타낸 그림이다.

<그림 3‑2> 압축 파일 헤더 구조

이상으로 Run-Length 압축 알고리즘에 대한 설명을 마친다. Run-Length 알고리즘은 알고리즘이 단순할 뿐만 아니라 이미지 파일이나 exe 파일처럼 똑같은 문자가 반복되는 경우 매우 좋은 압축률을 보여준다. 그러나 똑같은 문자가 이어져 있지 않은 경우에는 압축률이 매우 떨어지는 단점이 있다. 
위와 같은 방법으로 구현된 전체 Run-Length 알고리즘은 다음과 같다.

/*                                                                  */
/*   RUNLEN.C  :  Compression by Run-Length Encoding                */
/*                                                                  */

#include <stdio.h>
#include <string.h>
#include <dir.h>
#include <time.h>
#include <stdlib.h>

/* 탈출 문자 */
#define ESCAPE  0xB4

/* Run-Length 압축법에 의한 것임을 나타내는 식별 코드 */
#define IDENT1  0x11
#define IDENT2  0x22


/* srcname[]에서 파일 이름만 뽑아내어서 그것의 확장자를 rle로 바꿈 */
void make_dstname(char dstname[], char srcname[])
{
  char temp[256];
  
  fnsplit(srcname, temp, temp, dstname, temp);
  strcat(dstname, ".rle");
}

/* 파일의 이름을 받아 그 파일의 길이를 되돌림 */
long file_length(char filename[])
{
  FILE *fp;
  long l;

  if ((fp = fopen(filename, "rb")) == NULL)
       return 0L;

  fseek(fp, 0, SEEK_END);
  l = ftell(fp);
  fclose(fp);
  
  return l;
}

/* code[] 배열의 내용을 출력함 */
void flush(char code[], int len, FILE *fp)
{
  int i;
  for (i = 0; i < len; i++)
  putc(code[i], fp); 
}

/* Run-Length 압축 함수 */
void run_length_comp(FILE *src, char *srcname)
{
  int cur;
  int code_len;
  int length;
  unsigned char code[10];
  char dstname[13];
  FILE *dst;

  make_dstname(dstname, srcname);

  if ((dst = fopen(dstname, "wb")) == NULL)   /* 출력 파일 오픈 */
  {
       printf("\n Error : Can't create file.");
       fcloseall();
       exit(1);
  }

  /*  압축 파일의 헤더 작성 */
  putc(IDENT1, dst);      /* 출력 파일에 식별자 삽입 */
  putc(IDENT2, dst); 
  fputs(srcname, dst);    /* 출력 파일에 파일 이름 삽입 */
  putc(NULL, dst);        /* NULL 문자 삽입 */

  cur = getc(src);
  code_len = length = 0;

  while (!feof(src))
  {
       if (length == 0)
       {
           if (cur != ESCAPE)
           {
               code[code_len++] = cur;
               length++;
           }
           else
           {
               code[code_len++] = ESCAPE;
               code[code_len++] = ESCAPE;
               flush(code, code_len, dst);
               length = code_len = 0;
           }
           
           cur = getc(src);
       }
       else if (length == 1)
       {
           if (cur != code[0])
           {
               flush(code, code_len, dst);
               length = code_len = 0;
           }
           else
           {
               length++;
               code[code_len++] = cur;
               cur = getc(src);
           }
       }
       else if (length == 2)
       {
           if (cur != code[1])
           {
               flush(code, code_len, dst);
               length = code_len = 0;
           }
           else
           {
               length++;
               code_len = 0;
               code[code_len++] = ESCAPE;
               code[code_len++] = cur;
               code[code_len++] = length;
               cur = getc(src);
           }
       }
       else if (length > 2)
       {
           if (cur != code[1] || length > 254)
           {
               flush(code, code_len, dst);
               length = code_len = 0;
           }
           else
           {
               code[code_len-1]++;
               length++;
               cur = getc(src);
           }
       }
  }

  flush(code, code_len, dst);
  fclose(dst);
}

/* Run-Length 압축을 복원 */
void run_length_decomp(FILE *src)
{
  int cur;
  char srcname[13];
  FILE *dst;
  int i = 0, j;
  int length;

  cur = getc(src);
  if (cur != IDENT1 || getc(src) != IDENT2)   /* Run-Length 압축 파일이 맞는지 확인 */
  {
       printf("\n Error : That file is not Run-Length Encoding file");
       fcloseall();
       exit(1);
  }

  while ((cur = getc(src)) != NULL)       /* 헤더에서 파일 이름을 얻음 */
       srcname[i++] = cur;
  
  srcname[i] = NULL;
  if ((dst = fopen(srcname, "wb")) == NULL)
  {
       printf("\n Error : Disk full? ");
       fcloseall();
       exit(1);
  }

  cur = getc(src);
  while (!feof(src))
  {
       if (cur != ESCAPE)
           putc(cur, dst);
       else
       {
           cur = getc(src);
           if (cur == ESCAPE)
               putc(ESCAPE, dst);
       
           else
           {
               length = getc(src);
               for (j = 0; j < length; j++)
                   putc(cur, dst);
           }
       }
       
       cur = getc(src);
       
  }

  fclose(dst);
}

void main(int argc, char *argv[])
{
  FILE *src;
  long s, d;
  char dstname[13];
  clock_t tstart, tend;

  /* 사용법 출력 */
  if (argc < 3)
  {
       printf("\n Usage : RUNLEN <a or x> <filename>");
       exit(1);
  }

  tstart = clock();       /* 시작 시각 기록 */
  
  s = file_length(argv[2]);   /* 원래 파일의 크기를 구함 */

  if ((src = fopen(argv[2], "rb")) == NULL)
  {
       printf("\n Error : That file does not exist.");
       exit(1);
  }
  
  
  if (strcmp(argv[1], "a") == 0)      /* 압축 */
  {
       run_length_comp(src, argv[2]);
       make_dstname(dstname, argv[2]);
       d = file_length(dstname);       /* 압축 파일의 크기를 구함 */
       printf("\nFile compressed to %d%%", (int)((double)d/s*100.));
  }
  else if (strcmp(argv[1], "x") == 0)     /* 압축의 해제 */
  {
       run_length_decomp(src);
       printf("\nFile decompressed & created.");
  }
  
  fclose(src);
  
  
  tend = clock();     /* 종료 시각 기록 */
  printf("\nTime elapsed %d ticks", tend - tstart);   /* 수행 시간 출력 : 단위 tick */
}
 

3.4 실행 결과


filetype Run-Length    
random-bin 100.59    
random-txt 100.24    
wave 98.20    
pdf 99.03    
text(big) 85.04    
text(small) 98.71    
sql 96.78 

Run-Length 알고리즘의 특성 때문에 Random 파일에 대해서는 오히려 파일 크기가 증가하는 결과가 나타났다. 다른 경우에는 조금씩 압축이 되었으며, 크기가 큰 텍스트 파일에 대해서는 상당히 많은 압축이 되었다. 이것은 텍스트 파일에 들어있는 연속된 Space나 Enter 등을 압축 한 것으로 해석된다. SQL 역시 Space가 많아서 압축이 되었을 것이라 생각한다.

4 Lempel-Ziv
4.1 Lempel-Ziv Encoding
Run-Length 압축 알고리즘도 실제로 많이 사용되지만, 이 절에서 소개하는 Lempel-Ziv 알고리즘 또한 실제에서 가장 많이 사용되는 매우 우수한 압축 알고리즘이다. 
Run-Length 알고리즘은 똑같은 문자가 반복되는 경우 그것을 <탈출 문자, 반복 문자, 반복 횟수>로 치환하는 방법이었다. 이와 유사하게 Lempel-Ziv 압축법은 현재의 패턴이 가까운 거리에 존재한다면 그것에 대한 상재적 위치와 그 패턴의 길이를 구해서 <탈출 문자, 상대 위치, 길이>로 패턴을 대치하는 방법이다. 

원래 문자열 : ABCDEFGHIJKBCDEFJKLDM
압축 문자열 : ABCDEFGHIJK<10,5>JKLDM 

위의 그림을 보면, 원래 문자열에서 ‘BCDEF’라는 패턴이 뒤에 다시 반복된다. 이 때 뒤의 패턴을 <10,5>와 같이 10문자 앞에서 5문자를 취하라는 코드를 삽입함으로써 압축할 수 있고, 그 반대로 복원 할 수도 있다.
이렇게 떨어진 두 패턴뿐만 아니라 서로 겹쳐있는 패턴에 대해서도 이런 표현이 가능하다.

원래 문자열 : CDEFABABABABABAJKL
압축 문자열 : CDEFAB<2,9>JKL  
  
원래 문자열 : CDEFAAAAAAAJKL
압축 문자열 : CDEFA<1,7>JKL 

두 번째 예를 보면 Lempel-Ziv 압축법은 Run-Length 압축법과 마찬가지로 동일한 문자의 반복에 대해서도 Run-Length 압축법과 비슷한 압축률을 보임을 알 수 있다. 게다가 첫 번째와 같이 동일한 패턴이 반복되는 경우 Run-Length로는 압축하기 곤란하지만 Lempel-Ziv 압축법에서는 간단하게 압축된다. 
이렇게 간단한 원리는 Lempel-Ziv 압축법은 그 실제 구현에서 여러 가지 다양한 방법이 있다. 가장 대표적인 방법은 정적 사전(Static Dictionary)법과 동적 사전(Dynamic Dictionary)법이다. 
정적 사전법은 출현될 것으로 예상되는 패턴에 대한 정적 테이블을 미리 만들어 두었다가 그 패턴이 나올 경우 정적 테이블에 대한 참조를 하도록 하여 압축하는 방법이다. 
이 방법은 압축하고자 하는 파일의 내용이 예상 가능한 경우에 매우 좋은 방법이다. 예를 들어 C의 소스 파일만을 압축하고자 할 경우 C의 예약어와 출현 빈도가 높은 식별자(Identifier)에 대해 테이블을 미리 만들어 둔다면 매우 높은 효율과 빠른 속도의 압축을 할 수 있을 것이다. 그러나 임의의 파일을 압축하고자 할 때에는 그 효율을 장담하지 못한다.
동적 사전법은 파일을 읽어들이는 과정에서 패턴에 대한 사전을 만든다. 즉 동적 사전법에서 패턴에 대한 참조는 이미 그전에 파일 내에서 출현한 패턴에 한한다. 동적 사전법은 파일을 읽어들이면서 사전을 구성해야 하는 부담이 생기기 때문에 속도가 느리다는 단점이 있으나, 임의의 파일에 대해 압축률이 좋은 경우가 많다. 
우리는 정적 사전법은 동적 사전법과 별로 다를 것이 없으므로 동적 사전법만 다루기로 한다. 
동적 사전법을 실제로 구현하는데 있어 가장 중요한 자료 구조는 Sliding Window이다. Sliding Window는 전체 파일의 일부분을 FIFO(First In First Out) 구조의 메모리에 유지하고 있는 것을 의미한다. 그리고 이 Sliding Window는 파일에서 문자를 읽을 때마다 파일 내에서의 상대 위치가 끝 쪽으로 전진하게 된다. 
그리고 Sliding Window는 윈도우 내의 어떤 부분에 원하는 패턴이 있는지 찾아낼 수 있는 검색 구조까지 갖추고 있어야 한다.

Sliding Window의 FIFO 구조 때문에 가장 적절하게 사용될 수 있는 구조는 원형 큐(Circular Queue)이다. 그리고 Sliding Window의 검색 구조는 주로 해쉬(Hash)나 2진 나무(Binary Tree)를 사용한다. 
일반적으로 FIFO 구조(Sliding Window)의 크기는 압축률에 상당한 영향을 미치며, 검색 구조는 압축 속도에 큰 영향을 미친다. 즉 Sliding Window가 크면 동적 사전이 그만큼 더 방대하게 구성되어서 패턴을 찾아낼 확률이 크게 되고, 검색 구조가 효율적일수록 패턴을 빨리 찾아내기 때문이다. 
이 자료에서 작성할 Lempel-Ziv 압축법은 원형 큐와 한 문자에 대한 해시(연결법)로 패턴을 찾아낸다.
설명을 위해 다음 그림을 보자


<그림 4‑1> Sliding Window와 해시테이블

<그림 4‑1> (가) 그림은 큐 queue[]의 모양을 보여준다. 큐에는 압축할 파일에서 문자를 하나씩 읽어서 저장해 놓는다. front는 큐의 get() 명령 시 빠져나올 원소의 위치이고, rear는 큐의 put() 명령 시 새 원소가 들어갈 위치를 의미한다. 그리고 cp는 찾고자 하는 패턴이고, sp는 cp위치에 있는 패턴과 일치하는 앞쪽의 패턴 위치를 저장하고 있다. 그리고 length는 일치한 패턴의 길이를 의미하고 (가) 그림에서는 5가 된다. 
(나) 그림은 해시 테이블 jump_table[]의 모습이다. jump_table[]은 큐에 있는 문자가 어느 위치에 있는지 바로 찾을 수 있도록 큐에서의 위치들을 연결 리스트로 구성하고 있다. 예를 들어 ‘G’라는 문자를 큐 내에서 찾으려면 선형 검색처럼 처음부터 끝까지 검색해야 하는 것이 아니라, jump_table[‘G’]로서 연결 리스트의 시작 위치를 찾은 다음 연결 리스트를 타고 가면 14의 위치와 9의 위치에 ‘G’라는 문자가 있음을 알 수 있다. 
참고로 Lempel-Ziv 압축법에서는 패턴을 <탈출문자 상대위치 패턴길이>로 나타내는데 이 자료에서는 상대 위치와 패턴 길이 모두 1바이트를 사용한다. 즉 상대 위치는 앞으로 255만큼, 패턴의 길이도 255만큼이 가능하다는 이야기다. 패턴을 찾는 장소가 바로 큐이기 때문에 큐의 길이도 255보다 큰 것은 아무 의미가 없다. 이렇게 상대 위치와 패턴의 길이를 몇 비트로 나타낼 것인가에 따라 큐의 크기를 정해 준다.
Sliding Window에서 가장 핵심적인 부분은 원하는 패턴을 찾아내는 함수이다. 이 부분은 다음의 qmatch() 함수에 구현되어 있다. 이 qmatch() 함수는 Lempel-Ziv 압축법에서 압축 시에 가장 많이 호출되고 가장 많이 시간이 소요되는 부분이므로 충분히 최적화되어 있어야 한다.

int qmatch(int length)
  {
  int i;
  jump *t, *p;
  int cp, sp;
  cp = qx(rear - length);     // cp의 설정
  p = jump_table + queue[cp];
  t = p->next;

  while (t != NULL)
       {
       sp = t->index;          // sp의 설정, 해시 테이블에서 바로 읽어온다
       for (i = 1; i < length && queue[qx(sp+i)] == queue[qx(cp+i)]; i++);
       if (i == length) return sp;
                               // 패턴을 찾았으면 sp를 되돌림
       t = t->next;            // 패턴 검색에 실패했으면 다음 위치로 이동
       }
  return FAIL;                // 패턴이 큐 내에 없음
  }
 

qmatch() 함수는 결국 cp와 length로 주어지는 패턴을 큐 내에서 찾아서 그 위치 sp를 되돌려주는 기능을 한다. 

<Sliding Window를 이용한 LZ 압축 알고리즘(FILE *src, char *srcname)>
  {
  FILE *dst = 출력파일;
  jump_table[] 초기화;
  init_queue();
  put(getc(src));
  length = 0;
  
  while (!feof(src))
{
       if (queue_full())
    {
       if (sp == front)   /* 현재 추정된 패턴이 큐에서 벗어나려 하면 */
           {                  /* 현재까지의 정보로 출력 파일에 쓴다 */
               if (length > 3)    /* 패턴의 길이가 4 이상이면 압축 */
                   encode(sp, cp, length, dst);
               else               /* 아니면 그냥 씀 */
                   for (i = 0; i < length; i++)
                   {
                       put_jump(queue[qx(cp+i)], qx(cp+i));
                                  /* 다음을 위해 jump_table[]에 문자들의 */
                                  /* 위치를 기록 */
                       putc1(queue[qx(cp+i)], dst);
                   }
               length = 0;
           }
           del_jump(queue[front], front);
                          /* 큐에서 빠져 나온 문자는 jump_table[]에서 제거 */
           get();         /* 큐에서 문자 하나를 뺀다 */
    }
       if (length == 0)
       {
           cp = qx(rear-1);  /* cp의 설정, 가장 최근에 들어온 문자 */
           sp = qmatch(length+1); /* 패턴을 찾아 sp에 줌, 길이는 1 */
           if (sp == FAIL)   /* 패턴 검색에 실패했으면 */
           {
               putc1(queue[cp], dst);  /* 출력 파일에 기록 */
               put_jump(queue[cp], cp);
           }
           else
               length++;
           put(getc(src)); /* 다음 문자를 입력 파일에서 읽어 큐에 집어넣음 */
       }
       else if (length > 0)     /* 패턴의 길이가 1 이상이면 */
    {
           if (queue[qx(cp+length)] != queue[qx(sp+length)])
               j = qmatch(length+1);  /* 새로 들어온 문자까지 포함해서 */
                                      /* 패턴의 위치를 다시 검색 */
           else j = sp;
           if (j == FAIL || length > SIZE - 3)
           {                    /* 실패했으면 현재까지의 정보로 압축을 함 */
               if (length > 3)
               {
                   encode(sp, cp, length, dst);
                   length = 0;
               }
               else
               {
                   for (i = 0; i < length; i++)
                       {
                       put_jump(queue[qx(cp+i)], qx(cp+i));
                       putc1(queue[qx(cp+i)], dst);
                       }
                   length = 0;
               }
           }
           else                  /* 패턴 검색에 성공했으면 */
           {
               sp = j;
               length++;         /* 길이를 1증가 */
               put(getc(src));   /* 큐에 새 문자를 집어넣음 */
           }
    }
  }
                                 /* 큐에 남아있는 문자들을 모두 출력
  if (length > 3) encode(sp, cp, length, dst);
  else
       for (i = 0; i < length; i++)
           putc1(queue[qx(cp+i)], dst);
           
  delete_all_jump();                  /* jump_table[] 소거 */
  fclose(dst);

이 알고리즘을 자세히 살펴보면 알겠지만 그 기본적인 틀은 Run-Length 압축법과 유사함을 알 수 있을 것이다. length 변수가 상태를 표시하고 있음이 특히 그렇다.
그리고 주의할 점은 jump_table[]에 위치를 기록하는 시점이다. 쉽게 생각하면 큐에 입력할 때 집어넣은 것으로 착각할 수 있기 때문이다. jump_tablel[]에 문자의 위치를 집어넣는 정확한 시점은 파일에 그 문자를 출력할 때이다.
그리고 큐 내에 일치하는 패턴이 두 개 이상 있을 때 어느 것이 우선적으로 선택되어야 하는가 하는 문제 또한 중요하다. 이 때 적절한 기준은 cp 쪽에 가까운 패턴을 취하는 것이다. 이렇게 하는 이유는 패턴이 cp에서 멀 경우 패턴의 다음 문자들까지도 일치할 수 있으나 sp의 앞부분이 큐에서 벗어나는 경우가 있기 때문에 압축을 중단해야 하는 경우가 생기기 때문이다. 
이러한 점은 put_jump() 함수에서 자연스럽게 구현된다. put_jump() 함수는 항상 최근에 들어온 그 문자의 위치를 가장 앞에 두기 때문에 jump_table[]에서 검색할 때 퇴근에 들어온 문자의 위치가 선택된다. 
마지막으로 Run-Length 압축법과 마찬가지로 Lempel-Ziv 압축법에서도 압축 정보의 표시를 위해 탈출 문자(Escape Character)를 사용한다. 그런데 이 탈출 문자가 문자 자체의 의미로 사용될 때 Run-Length에서는 <ESCAPE ESCAPE>쌍을 사용했지만, Lempel_Ziv 법은 <ESCAPE 0x00>쌍을 사용한다. 
왜냐하면 탈출 문자가 사용되는 두 가지 용도는 문자 자체를 의미하는 것과 <탈출문자 상대위치 패턴길이> 정보의 시작을 표시하기 위함이다. 그런데 <상대위치>는 항상 0보다 큰 값이어야 하기 때문에(0이면 자기 자신을 의미한다) 압축 정보에서 <ESCAPE 0x00>쌍이 나타날 경우는 없다. 그러므로 충분히 압축 정보와 문자 자체의 의미를 구분할 수 있다.

4.2 Lempel-Ziv Decoding
그렇다면 앞 절의 알고리즘으로 압축된 파일을 원래대로 복원하는 알고리즘을 생각해보자. 복원 알고리즘은 매우 간단하다. 
복원 알고리즘의 개요는 입력 파일에서 문자를 차례대로 읽어 큐에 저장하는 것이다. 어느 정도 큐에 넣다 보면 큐가 차게 되는데 이 때 큐에서 빠져 나오는 문자들을 출력 파일에 쓰면 된다. 큐에 집어넣을 때 압축 정보가 들어올 때는 그 의미를 해석하여 다시 원 상태로 만든 다음에 큐에 한꺼번에 집어넣으면 아무 문제가 없다. 이런 알고리즘을 구현하기 위한 가장 핵심적인 함수는 put_byte() 함수이다. put_byte()함수는 매우 짧은 함수인데 인자로 주어진 문자를 큐에 집어넣되 큐가 꽉 차 있으면 출력 파일로 출력하는 기능을 한다. 이렇게 put_byte() 함수가 만들어지면 복원 알고리즘 또한 매우 간단하다.

<Sliding Window를 이용한 LZ압축 복원 알고리즘 (FILE *src)>
{
  FILE *dst = 출력 파일;
  init_queue();
  c = getc(src);
  while (!feof(src))
{
       if (c == ESCAPE)         /* 읽은 문자가 탈출 문자이면 */
       {
           if ((c = getc(src)) == 0) /* 그 다음이 0x00이면 탈출문자 자체 */
               put_byte(ESCAPE, dst);
           else                 /* 아니면 <탈출 문자 상대위치 패턴길이> 임 */
           {
               length = getc(src);
               sp = qx(rear - c);
               for (i = 0; i < length; i++) put_byte(queue[qx(sp+i)], dst);
                                /* 정보에 의해서 압축된 정보를 복원함 */
           }
       }
       else                     /* 일반 문자의 경우 */
           put_byte(c, dst);
       c = getc(src);
  }
  while (!queue_empty()) putc(get(), dst);
                                /* 큐에 남아 있는 문자들을 모두 출력 */
  fclose(dst);

4.3 Sliding Window를 이용한 Lempel-Ziv 알고리즘의 구현
이제 까지 설명한 것을 실제로 구현한 소스이다. 

/*                                                                  */
/*   LZWIN.C  :  Lempel-Ziv compression using Sliding Window        */
/*                                                                  */

#include <stdio.h>
#include <dir.h>
#include <string.h>
#include <alloc.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 255

int queue[SIZE];
int front, rear;

/* 해시 테이블의 구조 */
typedef struct _jump
{
  int index;
  struct _jump *next;
} jump;

jump jump_table[256];

/* 탈출 문자 */
#define ESCAPE  0xB4

/* Lempel-Ziv 압축법에 의한 것임을 나타내는 식별 코드 */
#define IDENT1  0x33
#define IDENT2  0x44

#define FAIL    0xff

/* 큐를 초기화 */
void init_queue(void)
{
  front = rear = 0;
}

/* 큐가 꽉 찼으면 1을 되돌림 */
int queue_full(void)
{
  return (rear + 1) % SIZE == front;
}

/* 큐가 비었으면 1을 되돌림 */
int queue_empty(void)
{
  return front == rear;
}

/* 큐에 문자를 집어 넣음 */
int put(int k)
{
  queue[rear] = k;
  rear = ++rear % SIZE;

  return k;
}

/* 큐에서 문자를 꺼냄 */
int get(void)
{
  int i;

  i = queue[front];
  queue[front] = 0;
  front = ++front % SIZE;

  return i;
}

/* k를 큐의 첨자로 변환, 범위에서 벗어나는 것을 범위 내로 조정 */
int qx(int k)
{
  return (k + SIZE) % SIZE;
}

/* srcname[]에서 파일 이름만 뽑아내어서 그것의 확장자를 lzw로 바꿈 */
void make_dstname(char dstname[], char srcname[])
{
  char temp[256];

  fnsplit(srcname, temp, temp, dstname, temp);
  strcat(dstname, ".lzw");
}

/* 파일의 이름을 받아 그 파일의 길이를 되돌림 */
long file_length(char filename[])
{
  FILE *fp;
  long l;

  if ((fp = fopen(filename, "rb")) == NULL)
   return 0L;
  
  fseek(fp, 0, SEEK_END);
  l = ftell(fp);
  fclose(fp);
  
  return l;
}

/* jump_table[]의 모든 노드를 제거 */
void delete_all_jump(void)
{
  int i;
  jump *j, *d;

  for (i = 0; i < 256; i++)
  {
       j = jump_table[i].next;
       while (j != NULL)
       {
           d = j;
           j = j->next;
           free(d);
       }
       jump_table[i].next = NULL;
  }
}

/* jump_table[]에 새로운 문자의 위치를 삽입 */
void put_jump(int c, int ptr)
{
  jump *j;

  if ((j = (jump*)malloc(sizeof(jump))) == NULL)
  {
       printf("\nError : Out of memory.");
       exit(1);
  }

  j->next = jump_table[c].next;       /* 선두에 삽입 */
  jump_table[c].next = j;
  j->index = ptr;
}

/* ptr 위치를 가지는 노드를 삭제 */
void del_jump(int c, int ptr)
{
  jump *j, *p;

  p = jump_table + c;
  j = p->next;

  while (j && j->index != ptr)    /* 노드 검색 */
  {
       p = j;
       j = j->next;
  }

  p->next = j->next;
  free(j);
}

/* cp와 length로 주어진 패턴을 해시법으로 찾아서 되돌림 */
int qmatch(int length)
{
  int i;
  jump *t, *p;
  int cp, sp;
  
  cp = qx(rear - length);     /* cp의 위치를 얻음 */
  p = jump_table + queue[cp];
  t = p->next;
  while (t != NULL)
  {
       sp = t->index;
  
       /*  첫 문자는 비교할 필요 없음. -> i =1; */
       for (i = 1; i < length && queue[qx(sp+i)] == queue[qx(cp+i)]; i++);
           if (i == length) return sp;     /* 패턴을 찾았음 */
  
       t = t->next;
  }

  return FAIL;
}

/* 문자 c를 출력 파일에 씀 */
int putc1(int c, FILE *dst)
{
  if (c == ESCAPE)        /* 탈출 문자이면 <탈출문자 0x00>쌍으로 치환 */
{
   putc(ESCAPE, dst);
   putc(0x00, dst);
}
  else
    putc(c, dst);

  return c;
}

/* 패턴을 압축해서 출력 파일에 씀 */
void encode(int sp, int cp, int length, FILE *dst)
{
  int i;
  
  for (i = 0; i < length; i++)        /* jump_table[]에 패턴의 문자들을 기록 */
       put_jump(queue[qx(cp+i)], qx(cp+i));
  
  putc(ESCAPE, dst);      /* 탈출 문자 */
  putc(qx(cp-sp), dst);   /* 상대 위치 */
  putc(length, dst);      /* 패턴 길이 */
}

/* Sliding Window를 이용한 LZ 압축 함수 */
void lzwin_comp(FILE *src, char *srcname)
{
  int length;
  char dstname[13];
  FILE *dst;
  int sp, cp;
  int i, j;
  int written;

  make_dstname(dstname, srcname);     /* 출력 파일 이름을 만듬 */
  if ((dst = fopen(dstname, "wb")) == NULL)
{
   printf("\n Error : Can't create file.");
   fcloseall();
   exit(1);
}

  /* 압축 파일의 헤더 작성 */
  putc(IDENT1, dst);    /* 출력 파일에 식별자 삽입 */
  putc(IDENT2, dst); 
  fputs(srcname, dst);    /* 출력 파일에 파일 이름 삽입 */
  putc(NULL, dst);        /* NULL 문자 삽입 */

  for (i = 0; i < 256; i++)       /* jump_table[] 초기화 */
       jump_table[i].next = NULL;
  
  rewind(src);
  init_queue();

  put(getc(src));

  length = 0;
  while (!feof(src))
{
       if (queue_full())       /* 큐가 꽉 찼으면 */
    {
        if (sp == front)    /* sp의 패턴이 넘어가려고 하면 현재의 정보로 출력 파일에 씀*/
           {
               if (length > 3)
             encode(sp, cp, length, dst);
               else
                   for (i = 0; i < length; i++)
                   {
                       put_jump(queue[qx(cp+i)], qx(cp+i));
                       putc1(queue[qx(cp+i)], dst);
                   }
               
               length = 0;
           }
           
           /* 큐에서 빠져나가는 문자의 위치를 jump_table[]에서 삭제 */
           del_jump(queue[front], front);
           
           get();  /* 큐에서 한 문자 삭제 */
    }
    
       if (length == 0)
       {
           cp = qx(rear-1);
           sp = qmatch(length+1);
           
           if (sp == FAIL)
           {
               putc1(queue[cp], dst);
               put_jump(queue[cp], cp);
           }
           else
               length++;
           
           put(getc(src));
       }
       else if (length > 0)
    {
           if (queue[qx(cp+length)] != queue[qx(sp+length)])
               j = qmatch(length+1);
           else j = sp;
           if (j == FAIL || length > SIZE - 3)
           {
               if (length > 3)
               {
                   encode(sp, cp, length, dst);
                   length = 0;
               }
               else
               {
                   for (i = 0; i < length; i++)
                   {
                       put_jump(queue[qx(cp+i)], qx(cp+i));
                       putc1(queue[qx(cp+i)], dst);
                   }
                   length = 0;
               }
           }
        else
           {
               sp = j;
               length++;
               put(getc(src));
           }
    }
  }
  
  /* 큐에 남은 문자 출력 */
  if (length > 3) 
       encode(sp, cp, length, dst);
  else
       for (i = 0; i < length; i++)
           putc1(queue[qx(cp+i)], dst);
  
  delete_all_jump();
  fclose(dst);
}

/* 큐에 문자를 넣고, 만일 꽉 찼다면 큐에서 빠져나온 문자를 출력 */
void put_byte(int c, FILE *dst)
{
  if (queue_full()) putc(get(), dst);
  put(c);
}

/* Sliding Window를 이용한 LZ 압축법의 복원 함수 */
void lzwin_decomp(FILE *src)
{
  int c;
  char srcname[13];
  FILE *dst;
  int length;
  int i = 0, j;
  int sp;

  rewind(src);
  c = getc(src);
  if (c != IDENT1 || getc(src) != IDENT2) /* 헤더 확인 */
{
   printf("\n Error : That file is not Lempel-Ziv Encoding file");
   fcloseall();
   exit(1);
}

  while ((c = getc(src)) != NULL)     /* 파일 이름을 얻음 */
   srcname[i++] = c;
  
  srcname[i] = NULL;
  if ((dst = fopen(srcname, "wb")) == NULL)
{
   printf("\n Error : Disk full? ");
   fcloseall();
   exit(1);
}

  init_queue();
  c = getc(src);

  while (!feof(src))
{
       if (c == ESCAPE)        /* 탈출 문자이면 */
       {
           if ((c = getc(src)) == 0)   /* <탈출 문자 0x00> 이면 */
               put_byte(ESCAPE, dst);
           else        /* <탈출문자 상대위치 패턴길이> 이면 */
           {
               length = getc(src);
               sp = qx(rear - c);
               for (i = 0; i < length; i++) 
                   put_byte(queue[qx(sp+i)], dst);
           }
       }
       else    /* 일반적인 문자의 경우 */
           put_byte(c, dst);
       
       c = getc(src);
}

  
  while (!queue_empty())  /* 큐에 남아 있는 모든 문자를 출력 */
       putc(get(), dst);
  
  fclose(dst);
}

void main(int argc, char *argv[])
  {
  FILE *src;
  long s, d;
  char dstname[13];
  clock_t tstart, tend;
 

  /* 사용법 출력 */
  if (argc < 3)
  {
   printf("\n Usage : LZWIN <a or x> <filename>");
   exit(1);
}

  tstart = clock();       /* 시작 시간 기록 */
  s = file_length(argv[2]);   /* 원래 파일의 크기를 구함 */

  if ((src = fopen(argv[2], "rb")) == NULL)
  {
       printf("\n Error : That file does not exist.");
       exit(1);
  
  }
  if (strcmp(argv[1], "a") == 0)  /* 압축 */
{
    lzwin_comp(src, argv[2]);
       make_dstname(dstname, argv[2]); 
   d = file_length(dstname);       /* 압축 파일의 크기를 구함 */
   printf("\nFile compressed to %d%%.", (int)((double)d/s*100.));
}
  else if (strcmp(argv[1], "x") == 0)     /* 압축의 해제 */
  {
   lzwin_decomp(src);
       printf("\nFile decompressed & created.");
  }
  
  fclose(src);
  
  tend = clock(); /* 종료 시간 기록 */
  printf("\nTime elapsed %d ticks", tend - tstart);   /* 수행 시간 출력 : 단위 tick */

이 프로그램을 실행시켜 보면 우선 속도가 매우 느리다는 점에 실망할 수도 있다. 그러나 압축률은 상용 프로그램에는 못 미치지만 상당히 좋음을 알 수 있을 것이다. 일반적으로 <상대위치>의 비트 수를 늘리면 압축률은 좋아진다. 대신 패턴 검색 시간이 길어지는 단점이 있다. 
<상대위치>와 <패턴길이>를 모두 8비트로 표현했지만, 이 둘을 적절히 조절하면 실행 시간을 빨리 하거나 압축률을 좋게 하는 변화를 줄 수 있다. 하지만 이럴 경우 비트 조작이 필요하므로 코딩 시 주의해야 한다.

4.4 실행 결과


filetype Lempel-Zip    
random-bin 100.59    
random-txt 100.24    
wave 92.34    
pdf 83.54    
text(big) 66.64    
text(small) 89.69    
sql 55.18 

Run-Length의 경우와 마찬가지로 Random File에 대해서는 압축을 하지 못했다. 하지만 그 외의 경우는 Run-Length에 비해 상당히 높은 압축률을 보여주고 있다. 이는 조금 떨어진 곳이라도 같은 패턴이 있으면 압축을 할 수 있기 때문에 가능한 결과라 생각한다.

5 Variable Length 
영문 텍스트 파일의 경우 사용되는 문자는 영어 대.소문자와 기호, 공백 문자 등 100여 개 안팎이다. 그래서 원래 ASCII 코드는 7비트(128가지의 상태를 표현)로 설계되었으며 나머지 한 비트는 패리티 비트(Parity Bit)로 통신상에서 오류를 검출하는 데 사용하도록 되어 있었다. 
통신 에뮬레이터의 환경설정에서 ‘데이터 비트 8’, ‘패리티 None’ 이라고 설정하는 것은 이러한 ASCII코드의 에러 검출 기능을 무시하고 8비트를 모두 사용하겠다는 뜻이다. 이러한 설정 기능은 원래 영어권에서 텍스트에 기반을 둔 통신 환경에서 8비트를 모두 사용할 필요가 없었기 때문에 만들어진 선택 사항이다. 
그렇다면 패리티를 무시하고 7비트만으로 영문자를 표기하되, 남은 한 비트를 다음 문자를 위해 사용한다면 고정적으로 1/8의 압축률을 가지는 압축 방법이 될 것이다. 이를 ‘8비트에서 7비트로 줄이는 압축 알고리즘(Eight to Seven Encoding)’ 이라고 한다.

<그림 5‑1> 8비트에서 7비트로 줄이는 압축 알고리즘

위의 논의는 자연적으로 다음과 같은 생각을 유도한다. 즉 압축하고자 하는 파일이 단지 일부분의 문자 집합만을 사용한다면 이를 표현하기 위해 8비트 전부를 사용할 필요가 없다는 것이다. 예를 들어 ‘ABCDEFABBCDEBDD’라는 문자열을 압축한다고 하자. 이 문자열은 단 6 문자를 사용한다. 그렇다면 사용되는 각 문자에 대해서 다음과 같이 다시 비트를 재구성해보자.

<그림 5‑2> 문자 코드의 재구성

그렇다면 앞의 문자열은 다음과 같이 다시 쓸 수 있으며 결과적으로 압축된다. 

원래 문자열 : ABCDEFABBCDEBDD
압축 비트열 : 0 1 00 01 10 11 0 1 1 00 01 10 1 01 01 

하지만, 이렇게 표현을 하면 압축 비트열은 각 문자 코드마다 구분자(Delimiter)가 필요하게 된다. 만약 구분자가 없이 각 코드를 붙여 쓴다면 그 해석이 모호해져서 압축 알고리즘으로는 쓸모 없게 된다. 예를 들어 압축 비트열의 앞부분인 네 코드를 붙여 쓴다면 ‘010001’이 되는데 이는 ‘ABCD’로도 해석할 수 있지만 ‘DCD’로도 해석할 수 있고 ‘ABAAAB’로도 해석할 수 있다는 뜻이다. 
그렇다면 이 모호함을 해결하는 방법은 없을까? 문제 해결의 열쇠는 문자 코드들을 기수 나무(Radix Tree)로 구성해 보는 데서 얻어진다.


<그림 5‑3> <그림 5‑2>코드의 기수 나무
기수 나무는 뿌리 노드에서 원하는 노드를 찾아가는 과정에서 비트가 0이면 왼쪽 자식으로, 1이면 오른쪽 자식으로 가는 탐색 구조를 가지고 있다. 이 그림에서 보면 각 문자들은 외부 노드와 내부 노드 모두에 존재한다. 이러한 구조에서는 구분자가 반드시 필요하게 된다. 
그렇다면 이들을 기수 나무로 구성하지 않고 기수 트라이(Radix Trie)로 구성한다면 어떨까? 기수 트라이는 각 정보 노드들이 모두 외부 노드인 나무 구조를 의미한다. 이렇게 구성된다면 정보 노드를 찾아가는 과정에서 다른 정보 노드를 만나는 경우가 없어져서 구분자 없이도 비트들을 구성할 수 있다.
예를 들어 다음의 그림과 같이 기수 트라이를 만들고 코드를 재구성해 보도록 하자.

<그림 5‑4> 문자 코드의 재구성

<그림 5‑4>의 코드 표는 <그림 5‑2>에 비해서 코드의 길이가 길어졌지만 구분자가 필요 없다는 장점이 있다. 이 <그림 5‑4>를 이용하여 문제의 문자열을 압축하면 다음처럼 된다. 

원래 문자열 : ABCDEFABBCDEBDD
압축 비트열 : 01001011101110111101001001011101110100110110 

이렇게 어떤 파일에서 사용되는 문자 집합이 전체 집합의 극히 일부분이라면 상당한 압축률로 압축할 수 있음을 보았을 것이다. 이와 같이 문자 코드를 재구성하여 고정된 비트 길이의 코드가 아닌 가변 길이의 코드를 사용하여 압축하는 방법을 가변 길이 압축법(Variable Length Encoding)이라고 한다. 
가변 길이 압축법에서 유의할 점은 압축 파일 내에 각 문자에 대해서 어떤 코드로 압축되었는지 그 정보를 미리 기억시켜 두어야 한다는 점이다. 이는 Run-Length 압축법이나 Lempel-Ziv 압축법과 같이 헤더가 식별자와 파일 이름만으로 구성되는 것이 아니라 문자에 대한 코드 또한 기록해 두어야 한다는 것을 의미한다. 기록되는 코드는 코드 자체뿐 아니라, 가변 길이라는 특성 때문에 코드의 길이 또한 기록되어야 한다. 이렇게 되어서 가변길이 압축법은 헤더가 매우 길어지게 된다. 
뒤에 나올 Huffman Tree가 가변 길이 압축법의 한 종류이기 때문에 가변 길이 압축법 자체는 자세히 다루지 않겠다.

6 Huffman Tree
만일 압축하고자 하는 파일이 전체 문자 집합의 모든 원소를 사용한다면 가변길이 압축법은 여전히 유용할까? 답은 그렇다 이다. 그리고 그것을 가능케 하는 것은 이 절에서 소개하는 Huffman 나무(Huffman Tree)이다. 
앞 절에서 살펴본 것과 같이 기수 트라이로 코드를 구성하는 경우 각 정보를 포함하고 있는 외부 노드의 레벨(Level)이 얼마냐에 따라 코드의 길이가 결정되었다. 예를 들어 <그림 5‑4>의 ‘A’문자의 경우는 겨우 비트의 길이가 1이며, ‘F’의 경우는 4가 된다. 
그렇다면 압축하고자 파일이 비록 모든 문자를 사용한다 할지라도 그 출현 빈도수가 고르지 않다면 출현빈도가 큰 문자에 대해서는 짧은 길이의 코드를, 출현 빈도가 작은 문자에 대해서는 긴 길이의 코드를 할당하면 전체적으로 압축되는 효과를 가져올 것이다.
그렇다면 압축축하고자 하는 파일을 먼저 읽어서 각 문자에 대한 빈도를 계산해야 한다는 결론이 나오게 되는데, 이러한 빈도가 freq[]라는 배열에 저장되어 있다면 이 빈도를 이용하여 어떻게 빈도와 레벨이 반비례하는 기수 트라이를 만들 것인가 하는 것이 이 절의 문제이며, 그 해결 방법은 Huffman 나무이다.
우선 Huffman 나무의 노드를 다음의 huf 구조체와 같이 정의해 보자.

typedef struct _huf
{
  long count;     // 빈도
  int  data;      // 문자
  struct _huf *left, *right
} huf; 

huf 구조체는 Huffman 나무의 노드로서 그 멤버로 빈도를 저장하는 count, 어떤 문자의 노드인지 알려주는 data를 가진다. 이 huf 구조체의 멤버를 의미있는 정보로 채우기 위해서는 우선 문자열에서 각 문자에 대한 빈도를 계산해야 한다. <그림 6‑1> (가)와 같은 문자열이 있다고 할 때 그 빈도수를 나타내면 (나)와 같다.

<그림 6‑1> 빈도수 계산

이제 <그림 6‑1> (나)의 정보를 이용하여 각 노드를 생성하여 죽 배열한다. 그 다음 작은 빈도의 두 노드를 뽑아내어 그것을 자식으로 가지는 분기 노드(Branch Node, 정보를 저장하지 않는 트라이의 내부 노드)를 새로 생성하여 그것을 다시 노드의 배열에 집어넣는다. 이 때 분기 노드의 count에는 두 자식 노드의 count의 합이 저장된다. 이런 과정을 노드가 하나 남을 때까지 반복하면 Huffman 나무가 얻어진다. 이 과정을 <그림 6‑2>에 나타내었다.






















<그림 6‑2> Huffman Tree 구성과정

<그림 6‑2>를 차례로 따라가다 보면 그 방법을 자연히 느끼게 될 것이다. 최종적인 결과로 얻어지는 Huffman Tree는 (하) 그림과 같다. (하) 그림을 보면 빈도수가 적은 노드들은 상대적으로 레벨이 크고, 빈도수가 많은 노드들은 레벨이 작음을 알 수 있다. 
이제 이런 과정을 수행하는 함수를 작성해 보기로 하자. 우선 빈도와 문자를 저장하고 있는 노드들을 죽 배열하는 장소를 정의해야 할 것이다. 그것은 다음의 head[] 배열이며, nhead는 노드의 개수를 저장하고 있다.

huf *head[256];
int nhead; 

앞에서 설명한 바와 같이 문자 i의 빈도가 freq[i]에 저장되어 있다고 한다면 다음의 construct_trie() 함수가 Huffman 나무를 구성해 준다.


void construct_trie(void)
{
  int i;
  int m;
  hum *h, *h1, *h2;
  
  /* 초기 단계 */
  for ( i = nhead = 0; i < 256; i++)
  {
       if(freq[i] != 0)     /* 빈도가 0이 아닌 문자에 대해서만 노드를 생성 */
       {
           if((h = (huf*)malloc(sizeof(huf))) == NULL)
           {
               printf("\nError : Out of memory.");
               exit(1);
           }
           
           h->count = freq[i];
           h->data = i;
           h->left = h->right = NULL;
           head[nhead++] = h;
       }
  }
  
  
  /* Huffman Tree 생성 단계 */
  while (nhead > 1)   /* 노드의 개수가 1이면 종료 */
  {
       m = find_minimum();     /* 최소의 빈도를 가지는 노드를 찾음 */
       h1 = head[m];
       head[m] = head[--nhead];        /* 그 노드를 빼냄 */
       m = find_minimum();     /* 또 다른 최소의 빈도를 가지는 노드를 찾음 */
       h2 = head[m];
       if((h = (huf*)malloc(sizeof(huf))) == NULL) /* 분기 노드 생성 */
       {
           printf("\nError : Out of memory");
           exit(1);
       }
       
               /* 두 자식 노드의 count 합을 저장 */
       h->count = h1->count + h2->count;
       h->data = 0;
       h->left = h1;           /* h1, h2를 자식으로 둠 */
       h->right = h2;
       head[m] = h;            /* 생성된 분기 노드를 노드 배열 head[]에 삽입 */
  }
  
  
  huf_head = head[0];     /* Huffman Tree의 루트 노드를 저장 */
}
 

construct_trie() 함수는 앞에서 보인 Huffman 나무 생성 과정을 그대로 직관적으로 표현했다. 그리고 huf_head라는 전역 변수는 Huffman 나무의 뿌리 노드(Root)를 가리키도록 함수의 마지막에서 설정해 둔다.
이렇게 <그림 6‑2> (하) 그림과 같은 Huffman 나무에서 각 문자에 대한 코드의 길이를 뽑아내어 보면 <그림 6‑3>과 같다.

<그림 6‑3> Huffman Tree에서 얻어진 코드

6.1 Huffman Encoding
Huffman 압축 알고리즘은 한마디로 말해서 원래의 고정 길이 코드를 <그림 6‑3>의 가변 길이 코드로 변환하는 것이다. 그러므로 Huffman 나무에서 코드를 얻어내는 방법이 반드시 필요하다. 
다음의 _make_code() 함수와 make_code() 함수가 Huffman 나무에서 코드를 생성하는 함수이다. _make_code() 함수가 재귀 호출 형태이어서 그것의 입구 함수로 make_code() 함수를 준비해 둔 것이다. 얻어진 코드는 전역 배열인 code[]에 저장되며, 코드의 길이는 len[]배열에 저장된다.

void _make_code(huf *h, unsigned c, int l)
{
  if(h->left != NULL || h->right != NULL)     /* 내부 노드(분기 노드)이면 */
  {
       c <<= 1;        /* 코드를 시프트, 결과적으로 0을 LSB에 집어넣는다. */
       l++;            /* 길이 증가 */
       _make_code(h->left, c, l);      /* 오른쪽 자식으로 재귀 호출 */
       c >>= 1;        /* 부모로 돌아가기 위해 다시 원상 복구 */
       l--;
  }
  else    /* 외부 노드(정보 노드)이면 */
  {
       code[h->data] = c;      /* 코드와 코드의 길이를 기록 */
       len[h->data] = l;
  }
}

void make_code(void)
{
  /* _make_code()의 입구 함수 */
  int i;
  for (i = 0; i < 256; i++)       /* code[]와 len[]의 초기화 */
       code[i] = len[i] = 0;
  
  _make_code(huf_head, 0u, 0);

위의 make_code()함수를 이용하면 이제 가변 길이 레코드를 얻어낼 수 있다. 그렇다면 이제 실제로 압축 함수 제작에 들어가야 하는데, 약간의 문제가 있다. 그것은 가변 길이의 코드를 사용하기 때문에 한 바이트씩 디스크로 입출력하게 되어 있는 기존의 시스템과는 좀 다른 점을 어떻게 표현하는가 하는 것이다.

이럴 때 필요한 것이 문제를 추상화 하는 것이다. 즉 디스크 파일을 한 바이트씩 쓰는 것이 아니라 한 비트씩 쓰는 것으로 착각하게 만드는 것이다. 이것을 담당하는 함수가 바로 put_bitseq()함수이다. put_bitseq() 함수를 사용하면 입력 파일에서 읽은 문자에 해당하는 코드를 비트별로 차례로 put_bitseq()의 인자로 주면 put_bitseq() 함수 내에서 알아서 한 바이트를 채워 출력 파일로 출력한다.

#define NORMAL 0
#define FLUSH 1

void put_bitseq(unsigned i, FILE *dst, int flag)
{
  /* 한 비트씩 출력하도록 하는 함수 */
  static unsigned wbyte = 0;
  
  /* 한 바이트가 꽉 차거나 FLUSH 모드이면 */
  /* bitloc는 입력될 비트 위치를 지정하는 전역 변수 */
  if (bitloc < 0 || glag == FLUSH)        
  {
       putc(wbyte, dst);
       bitloc = 7;     /* bitloc 재설정 */
       wbyte = 0;
  }
  
  wbyte |= i << (bitloc--);       /* 비트를 채워넣음 */

put_bitseq() 함수는 두 가지 모드로 작동한다. NNORMAL은 일반적인 경우로서 한 바이트가 꽉 차면 파일로 출력하는 모드이고, FLUSH 모드는 한 바이트가 꽉 차 있지 않더라도 현재의 wbyte를 파일로 출력한다. 이 두 가지 모드를 둔 이유는 파일의 끝에서 가변 길이 코드라는 특성 때문에 한 바이트가 채워지지 않는 경우가 생기기 때문이다. 

<Huffman 압축 알고리즘(FILE *src, char *srcname)>
{
  FILE *dst = 출력 파일;
  
  length = src 파일의 길이;
  헤더를 출력;        /* 식별자, 파일 이름, 파일 길이 */
  
  get_freq(src);      /* 빈도를 구해 freq[] 배열에 저장 */
  construct_trie();   /* freq[]를 이용하여 Huffman Tree 구성 */
  make_code();        /* Huffman Tree를 이용하여 code[], len[] 배열 설정 */
  
  code[]와 len[] 배열을 출력;
  
  destruct_trie(huf_head);        /* Huffman Tree를 제거 */
  
  rewind(src);
  bitloc = 7;
  while(1)
  {
       cur = getc(src);
       if(feof(src)) break;
       for (b = len[cur] - 1; b >= 0; b--)
           put_bitseq(bits(code[cur], b, 1), dst, NORMAL);
               /* 비트별로 읽어서 put_bitseq() 수행 */
  }
  
  put_bitseq(0, dst, FLUSH);      /* 남은 비트열을 FLUSH 모드로 씀 */
  fclose(dst);

Huffman 압축 알고리즘의 본체는 매우 간단 명료하다. 
그런데 한 가지 살펴볼 것이 있다. 일반적으로 실제 파일을 이용하여 Huffman 나무를 구성하여 코드를 구현해 보면 그 길이가 대략 14를 넘지 않는다. 그렇다면 code[] 배열을 위해서는 여분을 생각해서 16비트를 할당하면 될 것이다. 그런데 코드의 길이인 len[] 배열을 위해서는 최대 0~14 까지만 표현 가능하면 되므로 한 바이트를 모두 사용하는 것보다 4비트만 사용하면 상당히 헤더의 길이를 줄일 수 있을 것이다. 이것을 <그림 6‑4>에 나타내었다.

<그림 6‑4> code[]와 len[]의 저장

<그림 6‑4>와 같이 저장하면 총 128 * 5 바이트 즉 640 바이트의 헤더가 덧붙게 된다. 이렇게 저장하는 방법은 소스의 huffman_comp() 함수에 구현되어 있으므로 참고하기 바란다.

또한 Huffman 압축법과 같은 가변 길이 압축법은 앞에서 설명한 바와 같이 원래 파일의 길이도 저장하고 있어야 복원이 제대로 이루어진다. 결국 다른 압축법에 비해서 Huffman 압축법은 헤더의 길이가 매우 긴 편이다.

6.2 Huffman Decoding
앞 절과 같은 방법으로 압축된 파일을 다시 원상태로 복원하는 방법을 생각해 보자. 압축된 파일의 헤더에는 code[]와 len[]에 대한 정보가 실려있다. 이 둘을 이용하면 원래의 Huffman 나무를 새로 구성할 수 있다. 우선 압축 파일의 헤더를 읽어 code[]와 len[]을 다시 설정했다고 하자. 
그렇다면 다음의 trie_insert() 함수와 restruct_trie() 함수를 이용하여 Huffman 나무를 재구성할 수 있다. trie_insert() 함수는 인자로 받은 data의 노드를 code[data]와 len[data]를 이용하여 적절한 위치에 삽입한다. 삽입하는 방법은 매우 간단하다. code[data]의 비트를 차례로 분석하여 트라이를 타고 내려가면서 노드가 생성되어 있지 않으면 노드를 생성한다. 그래서 제 위치인 외부 노드에 도착하면 노드의 data 멤버에 인자 data를 설정하면 된다.


void trie_insert(int data)
{
  int b = len[data] -1;       /* 비트의 최좌측 위치(MSB) */
  huf *p, *t;
  
  if (huf_head == NULL)       /* 뿌리 노드가 없으면 생성 */
  {
       if ((huf_head = (huf*)malloc(sizeof(huf)) == NULL)
       {
           printf("\nError : Out of memory.");
           exit(1);
       }
       
       huf_head->left = huf_head->right = NULL;
  }
  
  p = t = huf_head;
  
  while (b >= 0)
  {
       if (bits(code[data], b, 1) == 0) /* 현재 검사 비트가 0이면 왼쪽으로 */
       {  
           t = t->left;
           if (t == NULL)  /* 왼쪽 자식이 없으면 생성 */
           {
               if ((t = (huf*)malloc(sizeof(huf))) == NULL)
               {
                   printf("\nError : Out of memory.");
                   exit(1);
               }
               
               t->left = t->right = NULL;
               p->left = t;
           }
       }
       else        /* 현재 검사 비트가 1이면 오른쪽으로 */
       {
           t = t->right;
           if (t == NULL)  /* 오른쪽 자식이 없으면 생성 */
           {
               if ((t = (huf*)malloc(sizeof(huf))) == NULL)
               {
                   printf("\nError : Out of memory.");
                   exit(1);
               }
               
               t->left = t->right = NULL;

               p->right = t;
           }
       }
       
       p = t;
       b--;
  }
  t->data = data;     /* 외부 노드에 data 설정 */

다음의 restruct_trie()함수는 위의 trie_insert() 함수에 코드의 길이가 0이 아닌 문자에 대해서만 Huffman 나무를 재구성하도록 인자를 보급한다. 

void restruct_trie(void)
{
  int i;
  huf_head = NULL;
  for (i = 0; i < 256; i++)
       if (len[i] > 0) trie_insert(i);

압축을 푸는 과정도 압축을 하는 과정과 유사하게 매우 간단하다. 압축을 푸는 과정을 한마디로 말하면 압축 파일에서 한 비트씩 읽어와서 그 비트대로 Huffman 나무를 순회한다. 그러다가 외부 노드에 도착하면 외부 노드의 data 멤버에 실린 값을 복원 파일에 써넣으면 되는 것이다. 
여기서 문제가 되는 점은 압축 파일에서 한 비트씩 읽어내는 방법인데, 이것 또한 앞절에서 살펴본 바와 같이 파일에서 한 비트씩 읽어들이는 것처럼 착각할 수 있도록 다음의 get_bitseq() 함수를 작성하는 것으로 해결된다.

int get_bitseq(FILE *fp)
{
  static int cur = 0;
  if (bitloc < 0)     /* 비트가 소모되었으면 다음 문자를 읽음 */
  {
       cur = getc(fp);
       bitloc = 7;
  }
  
  return bits(cur, bitloc--, 1);      /* 다음 비트를 돌려 줌 */

위의 부함수들을 이용하여 다음과 같이 Huffman 압축의 복원 알고리즘을 정리할 수 있다

<Huffman 압축 복원 알고리즘(FILE *src)>
{
  FILE *dst = 복원 파일;
  huf *h;
  
  헤더를 읽어들임;        /* 식별자와 파일 이름, 파일 길이 */
  code[]와 len[]을 읽어들임;
  
  restruct_trie();        /* Huffman Tree를 재구성 */
  
  
  n = 0;
  bitloc = -1;
  while (n < length)      /* length 는 파일의 길이 */
  {
       h = huf_head;
       while (h->left && h->right)
       {
           if (get_bitseq(src) == 1)   /* 읽어들인 비트가 1이면 오른쪽으로 */
               h = h->right;
           else                        /* 0이면 왼쪽으로 */
               h = h->left;
       }
       
       putc(h->data, dst);
       n++;
  }
  
  destruct_trie(huf_head);        /* Huffman Tree 제거 */
  fclose(dst);

6.3 Huffman 압축 알고리즘 구현
이제까지의 논의를 바탕으로 Huffman 압축 알고리즘을 실제로 구현한 C 소스이다.

/*                                                                  */
/*   HUFFMAN.C  :  Compression by Huffman's algorithm                  */
/*                                                                  */

#include <stdio.h>
#include <string.h>
#include <alloc.h>
#include <dir.h>
#include <time.h>
#include <stdlib.h>

/* Huffman 압축에 의한 것임을 나타내는 식별 코드 */
#define IDENT1  0x55
#define IDENT2  0x66

long freq[256];

typedef struct _huf
{
  long count;
  int data;
  struct _huf *left, *right;
} huf;

huf *head[256];
int nhead;
huf *huf_head;
unsigned code[256];
int len[256];
int bitloc = -1;

/* 비트의 부분을 뽑아내는 함수 */
unsigned bits(unsigned x, int k, int j)
{
  return (x >> k) & ~(~0 << j);
}

/* 파일에 존재하는 문자들의 빈도를 구해서 freq[]에 저장 */
void get_freq(FILE *fp)
{
  int i;

  for (i = 0; i < 256; i++) 
       freq[i] = 0L;
  
  rewind(fp);
  
  while (!feof(fp)) 
       freq[getc(fp)]++;
}

/* 최소 빈도수를 찾는 함수 */
int find_minimum(void)
{
  int mindex;
  int i;

  mindex = 0;

  for (i = 1; i < nhead; i++)
       if (head[i]->count < head[mindex]->count)
           mindex = i;

  return mindex;
}

/* freq[]로 Huffman Tree를 구성하는 함수 */
void construct_trie(void)
{
  int i;
  int m;
  huf *h, *h1, *h2;

  /* 초기 단계 */
  for (i = nhead = 0; i < 256; i++)
  {
       if (freq[i] != 0)
       {
           if ((h = (huf*)malloc(sizeof(huf))) == NULL)
           {
               printf("\nError : Out of memory.");
               exit(1);
           }
           h->count = freq[i];
           h->data = i;
           h->left = h->right = NULL;
           head[nhead++] = h;
       }
  }

  /* 생성 단계 */
  while (nhead > 1)
  {
       m = find_minimum();
       h1 = head[m];
       head[m] = head[--nhead];
       m = find_minimum();
       h2 = head[m];
  
       if ((h = (huf*)malloc(sizeof(huf))) == NULL)
       {
           printf("\nError : Out of memory.");
           exit(1);
       }
       h->count = h1->count + h2->count;
       h->data = 0;
       h->left = h1;
       h->right = h2;
       head[m] = h;
  }
  
  huf_head = head[0];
}

/* Huffman Tree를 제거 */
void destruct_trie(huf *h)
{
  if (h != NULL)
  {
       destruct_trie(h->left);
       destruct_trie(h->right);
       free(h);
  }
}

/* Huffman Tree에서 코드를 얻어냄. code[]와 len[]의 설정 */
void _make_code(huf *h, unsigned c, int l)
{
  if (h->left != NULL || h->right != NULL)
  {
       c <<= 1;
       l++;
       _make_code(h->left, c, l);
       c |= 1u;
       _make_code(h->right, c, l);
       c >>= 1;
       l--;
  }
  else
  {
       code[h->data] = c;
       len[h->data] = l;
  }
}

/* _make_code()함수의 입구 함수 */
void make_code(void)
{
  int i;

  for (i = 0; i < 256; i++)
       code[i] = len[i] = 0;

  _make_code(huf_head, 0u, 0);
}

/* srcname[]에서 파일 이름만 뽑아내어서 그것의 확장자를 huf로 바꿈 */
void make_dstname(char dstname[], char srcname[])
{
  char temp[256];

  fnsplit(srcname, temp, temp, dstname, temp);
  strcat(dstname, ".huf");
}

/* 파일의 이름을 받아 그 파일의 길이를 되돌림 */
long file_length(char filename[])
{
  FILE *fp;
  long l;

  if ((fp = fopen(filename, "rb")) == NULL)
       return 0L;
  
  fseek(fp, 0, SEEK_END);
  l = ftell(fp);
  fclose(fp);
  
  return l;
}

#define NORMAL 0
#define FLUSH  1

/* 파일에 한 비트씩 출력하도록 캡슐화 한 함수 */
void put_bitseq(unsigned i, FILE *dst, int flag)
{
  static unsigned wbyte = 0;
  if (bitloc < 0 || flag == FLUSH)
  {
       putc(wbyte, dst);
       bitloc = 7;
       wbyte = 0;
  }
  wbyte |= i << (bitloc--);
}

/* Huffman 압축 함수 */
void huffman_comp(FILE *src, char *srcname)
{
  int cur;
  int i;
  int max;
  union { long lenl; int leni[2]; } length;
  char dstname[13];
  FILE *dst;
  char temp[20];
  int b;

  fseek(src, 0L, SEEK_END);
  length.lenl = ftell(src);
  rewind(src);

  make_dstname(dstname, srcname);     /* 출력 파일 이름 만듬 */
  if ((dst = fopen(dstname, "wb")) == NULL)
  {
       printf("\n Error : Can't create file.");
       fcloseall();
       exit(1);
  }

  /* 압축 파일의 헤더 작성 */
  putc(IDENT1, dst);    /* 출력 파일에 식별자 삽입 */
  putc(IDENT2, dst); 
  fputs(srcname, dst);    /* 출력 파일에 파일 이름 삽입 */
  putc(NULL, dst);        /* NULL 문자열 삽입 */
  putw(length.leni[0], dst);  /* 파일의 길이 출력 */
  putw(length.leni[1], dst);

  get_freq(src);
  construct_trie();
  make_code();

  /* code[]와 len[]을 출력 */
  for (i = 0; i < 128; i++)
  {
       putw(code[i*2], dst);
       cur = len[i*2] << 4;
       cur |= len[i*2+1];
       putc(cur, dst);
       putw(code[i*2+1], dst);
  }

  destruct_trie(huf_head);

  rewind(src);
  bitloc = 7;
  while (1)
  {
       cur = getc(src);
       
       if (feof(src)) 
           break;
       
       for (b = len[cur] - 1; b >= 0; b--)
           put_bitseq(bits(code[cur], b, 1), dst, NORMAL);
  }
  put_bitseq(0, dst, FLUSH);
  fclose(dst);
}

/* len[]와 code[]를 이용하여 Huffman Tree를 구성 */
void trie_insert(int data)
{
  int b = len[data] - 1;
  huf *p, *t;

  if (huf_head == NULL)
  {
       if ((huf_head = (huf*)malloc(sizeof(huf))) == NULL)
       {
           printf("\nError : Out of memory.");
           exit(1);
       }
       huf_head->left = huf_head->right = NULL;
  }

  p = t = huf_head;
  while (b >= 0)
  {
       if (bits(code[data], b, 1) == 0)
       {
           t = t->left;
           if (t == NULL)
           {
               if ((t = (huf*)malloc(sizeof(huf))) == NULL)
               {
                   printf("\nError : Out of memory.");
                   exit(1);
               }
               t->left = t->right = NULL;
               p->left = t;
           }
       }
       else
       {
           t = t->right;
           if (t == NULL)
           {
               if ((t = (huf*)malloc(sizeof(huf))) == NULL)
               {
                   printf("\nError : Out of memory.");
                   exit(1);
               }
               t->left = t->right = NULL;
               p->right = t;
           }
       }
       p = t;
       b--;
  }
  t->data = data;
}

/* trie_insert()의 입구 함수 */
void restruct_trie(void)
{
  int i;
  
  huf_head = NULL;
  for (i = 0; i < 256; i++)
       if (len[i] > 0) trie_insert(i);
}

/* 파일에서 한 비트씩 읽는 것처럼 캡슐화 한 함수 */
int get_bitseq(FILE *fp)
{
  static int cur = 0;

  if (bitloc < 0)
  {
       cur = getc(fp);
       bitloc = 7;
  }

  return bits(cur, bitloc--, 1);
}

/* Huffman 압축 복원 알고리즘 */
void huffman_decomp(FILE *src)
{
  int cur;
  char srcname[13];
  FILE *dst;
  union { long lenl; int leni[2]; } length;
  long n;
  huf *h;
  int i = 0;

  rewind(src);
  cur = getc(src);
  if (cur != IDENT1 || getc(src) != IDENT2)
  {
       printf("\n Error : That file is not Run-Length Encoding file");
       fcloseall();
       exit(1);
  }
  while ((cur = getc(src)) != NULL) 
       srcname[i++] = cur;
  
  srcname[i] = NULL;
  if ((dst = fopen(srcname, "wb")) == NULL)
  {
       printf("\n Error : Disk full? ");
       fcloseall();
       exit(1);
  }
  length.leni[0] = getw(src);
  length.leni[1] = getw(src);

  for (i = 0; i < 128; i++)       /* code[]와 len[]을 읽어들임 */
  {
       code[i*2] = getw(src);
       cur = getc(src);
       code[i*2+1] = getw(src);
       len[i*2] = bits(cur, 4, 4);
       len[i*2+1] = bits(cur, 0, 4);
  }
  restruct_trie();        /* 헤더를 읽어서 Huffman Tree 재구성 */

  n = 0;
  bitloc = -1;
  while (n < length.lenl)
  {
       h = huf_head;
       while (h->left && h->right)
       {
           if (get_bitseq(src) == 1)
               h = h->right;
           else
               h = h->left;
       }
       putc(h->data, dst);
       n++;
  }
  destruct_trie(huf_head);
  fclose(dst);
}

void main(int argc, char *argv[])
{
  FILE *src;
  long s, d;
  char dstname[13];
  clock_t tstart, tend;

  /* 사용법 출력 */
  if (argc < 3)
       {
       printf("\n Usage : HUFFMAN <a or x> <filename>");
       exit(1);
  }

  tstart = clock();   /* 시작 시각 기록 */
  s = file_length(argv[2]);   /* 원래 파일의 크기 구함 */

  if ((src = fopen(argv[2], "rb")) == NULL)
  {
       printf("\n Error : That file does not exist.");
       exit(1);
  }

  if (strcmp(argv[1], "a") == 0)      /* 압축 */
  {
       huffman_comp(src, argv[2]);
       make_dstname(dstname, argv[2]);
       d = file_length(dstname);       /* 압축 파일의 크기를 구함 */
       printf("\nFile compressed to %d%%.", (int)((double)d/s*100.));
  }
  else if (strcmp(argv[1], "x") == 0)     /* 압축의 해제 */
  {
       huffman_decomp(src);
       printf("\nFile decompressed & created.");
  }

  fclose(src);

  tend = clock();     /* 종료 시각 저장 */
  printf("\nTime elapsed %d ticks", tend - tstart);   /* 수행 시간 출력 : 단위 tick */
  } 

6.4 실행 결과


filetype Huffman    
random-bin 113.80    
random-txt 97.32    
wave 94.76    
pdf 92.34    
text(big) 63.18    
text(small) 572.88    
sql 60.08 

앞의 두 알고리즘과는 다르고 random-txt에서 압축이 되었다. 이는 전체 파일에 나타나는 문자가 몇 개 안되기 때문에 허프만 코드에 의해서 압축이 되었다고 생각할 수 있다. random-bin에서 압축이 안된 것은 상대적으로 많은 문자가 사용되었기 때문에 Trie의 Depth가 깊어져서 코드 값이 길어졌기 때문이다. 또한 text(small)의 경우 값이 커진 것은, 허프만 압축의 특성상 헤더가 추가 되는데, 원래 파일이 워낙 작았기 때문에 헤더의 크기에 영향을 받은 것이다. 

7 Compare


filetype Run-Length Lempel-Zip Huffman    
random-bin 100.59 100.59 113.80    
random-txt 100.24 100.24 97.32    
wave 98.20 92.34 94.76    
pdf 99.03 83.54 92.34    
text(big) 85.04 66.64 63.18    
text(small) 98.71 89.69 572.88    
sql 96.78 55.18 60.08 

주로 텍스트 파일을 이용한 테스트 였기 때문에, Lempel-Zip압축 방법이 대체로 우수한 압축률을 보여주고 있다. Huffman 압축 방식도 파일이 극히 작은 경우만 아니라면 어느정도의 압축률을 보여주고 있다. Run-Length는 text파일의 경우가 아니고선 거의 압축을 하지 못했다.

8 JPEG (Joint Photographic Experts Group)
8.1 JPEG이란
1982년, 국제 표준화 기구 ISO(International Standard Organization)는 정지 영상의 압축 표준을 만들기 위해 PEG(Photographic Exports Group:영상 전문가 그룹)을 만들었다. PEG의 목표는 ISDN을 이용하여 정지 영상을 전송하기 위한 고성능 압축 표준을 만들자는 것이 주 목적이 되어 이를 수행하게 된 것이다.
1986년 국제 전신 전화 위원회 CCITT(International Telegraph and Telephone Consultative Committee)에서는 팩스를 이용해 전송하기 위한 영상 압축 방법을 연구하기 시작하였다. CCITT의 연구 내용은 PEG의 그것과 거의 비슷하였기 때문에 1987년 이 두 국제 기구의 영상 전문가가 연합하여 공동 연구를 수행하게 되었고, 이 영상 전문가 연합을 Joint Photographic Expert Group이라고 하였으며, 이것의 약자를 따서 만든 말이 바로 JPEG이다. 1990년 JPEG에서는 픽셀당 6비트에서 24비트를 갖는 정지 영상을 압축할 수 있는 고성능 정지 영상 압축 방법에 대한 국제 표준을 만들어 내게 되었다. 후에 JPEG에서는 만든 압축 알고리즘을 이용한 파일 포맷이 만들어 지게 되고 이것이 오늘날까지 오게 된 것이다.

8.2 다른 기술과의 비교
다른 기술과 차별화 되는 JPEG의 압축기술 GIF파일 포맷에 대해서 먼저 알아보기로 한다. 이 영상이미지 데이터는 최대 256컬러 영상까지만 저장할 수 있었기 때문에 실 세계의 이미지와 같은 것들을 저장하는데 한계가 있다. 지금은 트루컬러까지 모니터에서 지원이 되는데 이를 다른 곳에 응용하기에는 무리가 있었던 것이다.
GIF파일에서 사용하는 알고리즘을 LZW라고 하는데 이는 이를 개발한 Abraham Lempel과 Jakob Ziv이고 이를 개선시킨 Terry Welch등 세 사람의 이름을 따서 만든 압축 알고리즘으로 press, zoo, lha, pkzip, arj등과 같은 우리가 잘 알고 있는 프로그램에서 널리 사용되는 것이다. 이 압축 방법의 특징은 잡음의 영향을 크게 받기 때문에 애니메이션이나 컴퓨터 그래픽 영상을 압축하는 데는 비교적 효과적이라고 할 수 있었지만, 스캐너로 입력한 사진이나 실 세계의 이미지 같은 경우에 이를 압축하는 데는 효과적이지 못하다고 평가되고 있다.
이에 비해 TIFF나 BMP등의 파일 포맷은 24비트 트루컬러까지 지원하여 시진 등의 이미지를 잘 표현해 낼 수 있지만 압축 알고리즘 자체가 LZW, RLE등의 방식을 사용하였으므로 압축률이 그렇게 좋지 않다는 단점이 있다.
이에 반해 현재의 JPEG기술은 사진과 같은 자연 영상을 약 20:1이상 압축할 수 있는 성능을 가지고 있어서 현재 사용되고 있는 정지 영상 파일 포맷 중에서는 최고의 압축률을 자랑하고 있다.
하지만 장점이 있으면 단점도 존재하기 마련이다. 단점이라면 기존의 영상 파일을 압축하는 시점에서 영상의 일부 정보를 손실 시키기 때문에 의료 영상이나 기타 중요한 영상 혹은 자연 영상 등에는 사용하는데 무리가 있다. 즉, GIF, TIFF등의 영상 파일은 영상을 압축한 후 복원하면 압축하기 전과 완전히 동일한 비손실 압축 방법이지만 JPEG이미지 포맷의 경우 손실 압축방법이라는 것이다. 하지만 손실이 된다고 해도 원래의 이미지와 그렇게 다르지 않은(거의 동일한) 이미지를 얻을 수 있기 때문에 영상 정보가 중요한 부분이 아니라면 효율적인 방법이라고 할 수 있다.

8.3 압축 방법
JPEG이 압축을 대상으로 삼는 사진과 같은 자연의 영상이 인접한 픽셀간에 픽셀 값이 급격하게 변하지 않는다는 속성을 이용하여 사람의 눈에 잘 띄지 않는 정보만 선택적으로 손실 시키는 기술을 사용하고 있기 때문이다.
이러한 압축 방법으로 인한 또 다른 단점이 있다. 인접한 픽셀간에 픽셀 값이 급격히 변하는 컴퓨터 영상이나 픽셀당 컬러 수가 아주 낮은 이진 영상이나, 16컬러 영상 등은 JPEG으로 압축하게 되면 오히려 압축 효율이 좋지 않을 뿐더러 손실된 부분이 상당히 거슬려 보인다는 것이다.
즉, 다른 이미지 압축 기술과 차별화 되는 신기술임에는 분명하지만 사용목적에 따라서 적절한 압축 알고리즘을 사용하는 것은 기본이라 하겠다.
JPEG의 압축방법 JPEG압축 알고리즘을 사용했다고 해서 이게 단 한가지의 압축 알고리즘만이 존재한다는 의미가 아님을 알고 있어야 한다. 다음과 같이 JPEG압축 알고리즘은 크게 네부분으로 나누어 볼 수 있다.
1. DCT(Discrete Cosine Transform) 압축 방법 :
일반적으로 JPEG영상이라고 하면 통용되는 압축 알고리즘이다.
2. 점진적 전송이 가능한 압축 방법 :
영상 파일을 읽어 오는 중에도 화면 출력을 할 수 있는 것을 의미하며 전송 속도가 낮은 네트워크를 통해 영상을 전송 받아 화면에 출력할 때 유용한 모드라고 할 수 있다. 즉, 영상의 일부를 전송 받아 저해상도의 영상을 출력할 수 있으며, 영상 데이터가 전송됨에 따라서 영상의 화질을 개선시키면서 화면에 출력이 가능하다는 것이다. 
3. 계층 구조적 압축 알고리즘 :
피라미드 코딩 방법이라고도 하며, 하나의 영상 파일에 여러 가지 해상도를 갖는 영상을 한번에 저장하는 방법이다. 
4. 비손실 압축 :
JPEG압축이라고 하여 손실 압축만 존재하는 것은 아니다. 이 경우에는 DCT압축 알고리즘을 사용하지 않고 2D-DPCM이라고 하는 압축방법을 이용하게 된다.

이처럼 JPEG표준에는 이와 같은 여러 가지 압축 방법이 규정되어 있지만, 일반적으로 JPEG로 영상을 압축하여 저장한다고 하면, DCT를 기반으로 한 압축 저장방법을 의미 한다.
이러한 방법을 또 다른 용어로 Baseline JPEG이라고 하며, JPEG영상 이미지를 지원하는 모든 어플리케이션은 이 이미지 데이터를 처리할 수 있는 알고리즘을 반드시 포함하고 있어야 한다. 즉, 나머지 3가지의 압축 방법을 꼭 지원하지 않아도 되는 선택사항이라는 의미이다.


8.4 Baseline 압축 알고리즘
이 방법은 손실 압축 방법이기 때문에 영상에 손실을 많이 주면 화질이 안 좋아지는 대신 압축이 많이 되고, 손실을 적게 주면 좋은 화질을 유지하기는 하지만 압축이 조금밖에 되지 않는다는 것이다. 이처럼 손실의 정도를 나타내는 값을 Q펙터라고 말하는데 이 값의 범위는 1부터 100까지의 값으로 나타나게 된다. Q펙터가 1이면 최대의 손실을 내면서 가장 많이 압축되는 방식이고 100이면 이미지 손실을 적개 주기는 하지만 압축은 적게 되는 방식이다. Q펙터가 100이라고 하여 비손실 압축이 이루어 지는 것은 아니라는데 주의할 필요가 있다.
베이스라인 JPEG은 JPEG압축 최소 사양으로, 모든 JPEG관련 애플리케이션은 적어도 이 방법을 반드시 지원해야 한다고 했다. 이러한 방식이 어떤 단계를 거치면서 수행되게 되는지 알아보도록 하자.
1. 영상의 컬러 모델(RGB)을 YIQ모델로 변환한다. 
2. 2*2 영상 블록에 대해 평균값을 취해 색차(Chrominance)신호 성분을 다운 샘플링 한다. 
3. 각 컬러 성분의 영상을 8*8크기의 블록으로 나누고, 각 블록에 대해 DCT알고리즘을 수행시킨다. 
4. 각 블록의 DCT계수를 시각에 미치는 영향에 따라 가중치를 두어 양자화 한다. 
5. 양자화된 DCT계수를 Huffman Coding방법에 의해 코딩하여 파일로 저장한다.

이렇게 압축된 파일을 다시 원 이미지로 복원할 때는 반대의 과정을 거치게 된다. 이러한 압축과 복원에 관해 어떤 식으로 처리가 되는지 그림으로 살펴보면 아래와 같다

<그림 7‑1> JPEG Encoding / Decoding 단계

8.5 JPEG의 실제 압축 / 복원 과정
1.  컬러모델 변환 :
컬러를 표현하는 방법에는 여러 가지가 있다. 가장 흔하게 사용하는 방법으로 RGB가 있다. 하지만 이러한 표현방법이 이것뿐이라면 좋겠지만 실제로는 그렇질 않다는 것이다.
RGB컬러는 모니터에서 사용하는 색상이고 빛의 3원색을 조합했을 때 나오는 색도 세 가지인데 이들은  하늘색(Cyan), 주황색(Magenta), 노랑색 (Yellow)이고, 이들의 조합으로도 모든 컬러를 표현 할 수 있게 된다. 이러한 방법을 CMY모델이라고 하며, 컬러 프린터가 이 모델을 이용해서 프린팅을 하게 된다.
우리가 논의 하려고 하는 YIQ라고 하는 모델은 밝기(Y : Luminance)와 색차(Chrominance : Inphase & Quadrature) 정보의 조합으로 컬러를 표현하는 방법이다.
다른 방법도 있다. 색상(Hue), 채도(Saturation), 명도(Intensity)의 색의 3요소로 색을 표현하는 HSI모델 등 여러 가지 컬러 모드가 있는 것이다.
RGB모델은 YIQ모델로 변환하는 방법이 있는데.. 이른 각각의 모델들도 서로 변환이 될 수 있다. RGB를 YIQ모델로 변환하는 식은 다음과 같다.

Y  0.299 0.587 0.114  R    
I = 0.596 -0.275 -0.321  G    
Q  0.212 -0.523 -0.311  B  
<그림 7‑2> RGB의 YIQ 변환 식

이와 같은 식을 이용해서 JPEG압축을 하기 위해서는 컬러 모델을 YIQ모델로 변환을 한다. 많은 모델 중에서 이 모델로 변환을 하는 이유는 이중에서 Y성분은 시각적으로 눈에 잘 띄는 성분이지만 I, Q성분은 시각적으로 잘 띄지 않는 정보를 담고 있는 성질이 있어서, Y값만을 살려두고 I, Q값을 손실시키면 사람이 봤을 때에는 화질의 차이를 별로 느끼지 않으면서 정보를 양을 줄일 수 있는 장점이 있기 때문이다.

2. 색차 신호 성분 다운샘플링 : 앞에서도 이야기 했던 바와 같이 I와 Q의 성분은 시각적으로 눈에 잘 띄지 않는 정보들이기 때문에 이정보는 손실을 시켜도 사람이 보는데 특별한 지장을 주지 않는다.
손실을 시킨다는 의미이지 지워버린다는 의미는 아니다. 즉, Y값은 기억시키고, I, Q값은 가로 세로 2x2혹은 2x1크기를 블록당 한 개 만을 기억시키는 방식으로 정보만을 줄인다는 개념이다.
즉, 두번째 단계인 지금은 컬러모델을 변환한 것을 ‘다운 샘플링’ 한다는 것이다.

3. DCT적용 : JPEG알고리즘을 적용할 이미지 영상 블록에 어떤 주파수 성분이 얼마만큼 포함되어 있는지를 나타내는 8x8크기의 계수를 얻을 수 있게 된다. 픽셀간의 값의 변화율이 작은 밋밋한 영상은 저주파 성분을 나타내는 계수가 크게 나오게 되고, 픽셀간의 변화율이 큰 복잡한 영상은 고주파 성분을 나타내는 계수가 크게 나온다.  컬러를 표시하기 위한 각각의 YIQ성분은 8x8크기의 블록으로 나뉘어지고, 각 블록에 대해 DCT가 수행이 된다.
DCT는 Discrete Cosine Transform의 약자로 영상 블록을 서로 다른 주파수 성분의 코사인 함수로 분해하는 과정을 일컷는다. 
이처럼 DCT를 수행하는 이유는 영상데이터의 경우 저주파 성분은 시각적으로 큰 정보를 가지고 있는 반면 고주파 성분의 경우는 시각적으로 별 의미가 없는 정보를 가지고 있기 때문에 시각적으로 적은 부분을 손실을 줌으로써 시각적인 손실을 최소화하면서 데이터 양을 줄이기 위한 것이다.

4. DCT 계수의 양자화 : 이론적으론 DCT자체만으로는 영상에 손실이 일어나지 않으며, DCT계수들을 기억하고 있으면 DCT역 변환을 통해 원 영상을 그대로 복원해 낼 수 있다. 실제로 영상에 손실을 주며, 데이터 량을 줄이는 부분은 DCT계수를 양자화 하는 바로 이 단계에서 이다.
계수 양자화란 여러 개의 값을 하나의 대표 값으로 대치시키는 과정을 말한다. 예를 들어 0에서 10까지의 값은 5로 대치시키고 10에서 20까지의 값은 15로 대치시키면 0부터 20까지의 값으로 분포되는 수많은 수들을 5와 15라는 두 개의 값으로 양자화 시킨 것이 된다. 이처럼 양자화 과정을 거치면 기억해야 할 수많은 경우의 수가 단지 몇 개의 경우의 수로 축소되기 때문에 데이터에 손실이 일어나지만 데이터 량을 크게 줄이는 장점이 있다.
양자화를 조밀하게 하면 데이터의 손실이 적어지는 대신 데이터 량은 그만큼 조금 줄게 되고, 양자화가 성기면 데이터의 손실은 많아지는 대신 데이터 량은 그만큼 많이 줄게 됩니다.
저주파 영역을 조밀하게 양자화하고 고주파 영역은 성기게 양자화하면 전체적으로 영상의 손실이 최소화 되면서 데이터 량의 감소를 극대화 시킬 수 있게 된다.
이처럼 주파수 성분 별로 어느 정도 간격으로 양자화를 하느냐에 따라 데이터 이미지의 질이 결정이 되는데 ISO에서는 실험적으로 결정한 양자화 테이블을 이용하여 양자화를 수행하는 것이 통상적이다.
영상의 화질과 압축률을 결정하는 변수인 Q펙터가 작용하는 부분도 바로 이 단계로. Q펙터를 크게 하면 전체적으로 양자화를 조밀하게 해서 손실을 줄임으로써 영상의 화질을 좋게 하고, Q펙터를 크게 하면 전체적으로 양자화 간격을 넓혀 화질에 손상을 많이 주어서 압축이 많이 되도록 하게 된다.

5. Huffman Coding : 양자화된 DCT계수는 자체로서 압축 효과를 갖지만 이를 더 효율적으로 압축하기 위해서 Huffman Coding으로 다시 한번 압축하여 파일에 저장을 한다. 
JPEG의 실제 압축과 복원과정 알아보기 지금까지 영상데이터가 인코딩되는 과정을 단계적으로 알아보았다.

8.6 확장 JPEG 
베이스라인 JPEG은 JPEG에 필요한 최소의 기능만을 규정한 것이라고 설명을 했다. 이 외에도 JPEG내에는 많은 압축 방법이 존재한다. 확장 JPEG의 기능은 반드시 지원할 필요는 없지만, JPEG파일 내에서 사용될 수 있으므로 확장 JPEG의 기능을 일단 인식은 할 수 있어야 하고, 지원되지 않는 기능이 파일에 들어 있을 경우 에는 에러메시지를 출력하도록 하여야 한다.

9 MPEG (Moving Picture Expert Group)

9.1 MPEG의 개념
MPEG은 동영상 압축 표준이다. MPEG 표준에는 MPEG1과 MPEG2, MPEG4, MPEG7 이 있다. 각각에 대해 비디오(동화상 압축), 오디오(음향 압축), 시스템(동화상과 음향 등이 잘 섞여있는 스트림)에 대한 명세가 존재한다.
MPEG1은 1배속 CD 롬 드라이버의 데이터 전송속도인 1.5 Mbps에 맞도록 설계되었다. 즉 VCR 화질의 동영상 데이터를 압축했을 때 최대비트율이 1.15 Mbps가 되도록 MPEG1-비디오 압축 알고리즘이 정해졌으며, 스테레오 CD 음질의 음향 데이터를 압축했을 때 최대비트율이 128 Kbps(채널당 64Kbps)가 되도록 MPEG1-오디오 압축 알고리즘이 정해졌다. MPEG1-시스템은 단순히 음향과 동화상의 동기화를 목적으로 잘 섞어놓은(interleave) 것이다.
MPEG2는 보다 압축 효율이 향상되고 용도가 넓어진 것으로서, 보다 고화질/고음질의 영화도 대상으로 할 수 있고 방송망이나 고속망 환경에 적합하다. 즉 방송 TV (스튜디오 TV, HDTV) 화질의 동영상 데이터를 압축했을 때 최대비트율이 4 ( 6, 40)Mbps가 되도록 MPEG2-비디오 압축 알고리즘이 정해졌으며, 여러 채널의 CD 음질 음향 데이터를 압축했을 때 최대 비트율이 채널당 64 Kbps 이하로 되도록 MPEG2 오디오 압축 알고리즘이 정해졌다.
MPEG2 -시스템은 여러 영화를 한데 묶어 전송하여주고 이때 전송시 있을 수 있는 에러도 복구시켜줄 수 있는 일종의 트랜스포트 프로토콜이다.
MPEG4는 매우 높은 압축 효율을 얻음으로써 매우 낮은 비트율로 전송하기 위한 것이다. 이를 사용함으로써 이동 멀티미디어 응용을 구현할 수 있다. MPEG4는 아직 표준이 완전히 만들어지지 않았으며, 매우 높은 압축 효율을 위해 내용기반(model-based) 압축 기법이 연구되고 있다.

9.2 MPEG의 표준

9.2.1 MPEG 1
MPEG 1의 표준은 4 부분으로 나누어져 있다.

1. 다중화 시스템부 : 동영상 및 음향 신호들의 비트열(Bit-stream) 구성 및 동기화 방식을 기술
2. 비디오부 : DCT와 움직임 추정(Motion Estimation)을 근간으로 하는 동영상 압축 알고리즘을 기술
3. 오디오부 : 서브밴드 코딩을 근간으로 하는 음향 압축 알고리즘을 기술
4. 적합성 검사부 : 비트열과 복호기의 적합성을 검사하는 방법

MPEG 1 영상 압축 알고리즘의 기본 골격은 움직임 추정과 움직임 보상을 이용하여 시간적인 중복 정보 제거한다.

1. 시간적인 중복성 - 수십 장의 정지 영상이 시간적으로 연속하여 움직일 때 앞의 영상과 현재의 영상은 서로 비슷한 특징을 보유
2. 제거방법 - DPCM(Differential PCM) 사용
3. DCT 방법을 이용하여 공간적인 중복 정보 제거
4. 공간 중복성 - 서로 인접한 화소끼리는 서로 비슷한 값을 소유
5. 제거방법 - DCT와 양자화를 이용


9.2.2 MPEG 2
MPEG 2의 표준화는 1990년 말부터 본격화 되었고 디지털 TV와 고선명 TV(HDTV) 방송에 대한 요구 사항이 추가되었고, 그 후 1995년 초 국제 표준으로 채택되었다.
MPEG 1과 마찬가지고 4 부분으로 나누어져 있지만 비디오부에서 디지털 TV와 고선명 TV 방송에 대한 사항이 첨가 되어있다.

1. 다중화 시스템부 : 음향, 영상, 다른 데이터 전송, 저장하기 위한 다중화 방법 정의
2. 비디오부 : 고화질 디지털 영상의 부호화를 목표로 MPEG-1에서 요구하는 순방 향 호환성을 만족, 격행 주사(Interlaced scan) 영상 형식과 HDTV 수준 의 해상도 지원 명시. 5개의 프로파일(Profile)과 4개의 레벨(Level)이 정 의
3. 오디오부 : 다중 채널 음향(샘플링 비율=16, 22.05, 24KHz)의 저전송율 부호화를 목표. 5개의 완전한 대역 채널(Left, Right, Center, 2 surround), 부가적 인 저주파수 강화 채널, 7개 해설 채널, 여러나라의 언어 지원 채널들 이 지원. 채널당 64Kbits/sec 정도의 고음질로 스테레오와 모노음을 부 호화
4. 적합성 검사부

MPEG 2 영상 압축 과정
1. 움직임 추정과 움직임 보상을 이용하여 시간적인 중복성을 제거
2. DCT와 양자화를 이용하여 공간적인 중복성을 제거

앞의 두 가지의 기본적인 압축 방법에 의하여 얻어진 데이타들의 발생 확률에 따라 엔트로피(Entrophy) 부호화 방법을 적용함으로써 최종적으로 압축 효율을 극대화

MPEG 2 표준은 멀티미디어 응용 서비스에 필수적인 디지털 저장 매체와 ISDN(Integrated Service Digital Network), B-ISDN(Broadband ISDN), LAN과 같은 디지털 통신 채널, 위성, 케이블, 지상파에 의한 디지털 방송매체 등을 응용 대상으로 삼고 있다.

9.2.3 MPEG 4
MPEG 4의 목적은 빠른 속도로 확산되고 있는 고성능 멀티미디어 통신 서비스 고려하여 기존의 방식과 새로운 기능들을 모두 지원할 수 있는 부호화 도구 제공를 제공하는 것이다. 그리고 양방향성, 높은 압축율 및 다양한 접속을 가능케 하는 AV(Audio/Video) 표준 부호화 방식을 지원한다. 또한 내용 기반 부호화(Content-based coding) 기술을 개발하고 초저속 전송에서부터 초고속 전송에 이르기까지 모든 영상 응용 분야에 융통성있게 대응할 수 있도록 한다.

주요 기능으로는 내용 기반 대화형 기능과 압축 기능, 광범위한 접근 기능을 갖고 있으며 내용 기반 대화형 기능은 멀티미디어 데이터 접근 도구, 처리 및 비트열 편집, 복합 영상 부호화, 향상된 시간 방향으로의 임의 접근을 할 수 있고 압축기능은 향상된 압축 효율, 복수개의 영상물을 동시에 부호화 할 수 있다. 그리고 광범위한 접근 기능은 내용 기반의 다단계 등급 부호화, 오류에 민감한 환경에서의 견고성을 갖도록 한다.


9.3 MPEG의 기본적인 압축 원리
처음에 MPEG-1은 352 * 240에 30을 기준으로 하는 낮은 해상도로 출발하였다. 그러나 음향 부분에서만은 CD수준인 16BIT 44.1Khz STEREO 수준으로 표준안이 제정되었다. MPEG에서 사용하는 동영상 압축원리는 두가지 기본 기술을 바탕으로 하고 있다.

9.3.1 시간,공간의 중복성 제거
동영상은 정지 영상과 달리 정지영상을 여러장 연속하여 저장하여 이루어지는 파일이다. 예를들어 AVI 파일을 동영상 편집 프로그램으로 풀어서 본다면 거의 비슷한 화면이 프레임수에 따라 여러장 있는 것을 알 수가 있다. MPEG은 이러한 시간에 따른 화면의 중복성을 제거하고 착시현상을 이용하여 실제와 비슷한 영상을 만들어내는 원리를 가지고 있다. 이러한 중복성은 시간적 중복성(TEMPORAL REDUDANCY)과 공간적 중복성(SPATIAL REDUDANCY)이 있는데 앞의 AVI화일의 예가 시간적 중복성이 되고 공간적 중복성은 예를 들어 카메라가 정지영상이나 한 인물을 집중적으로 촬영할 때 그 영상들의 공간 구성값의 위치는 비슷한 값들이 비슷한 위치에서 이동이 적어지는 확률이 높아지기 때문에 나타나는 중복성이라고 할 수 있다.

위에서 설명한 두가지 항목을 해결하기 위한 방법으로 시간의 중복성을 해결하기 위한 방법으로는 각 화면의 움직임 예상(Motion Estimation)의 개념을 응용하고 공간의 중복성을 해결하기 위한 방법으로는 DCT (Discreate Cosine Transforms)라는 개념과 양자화(quantigation)의 개념을 응용한다. vMotion Estimation은 16 * 16 크기의 블록으로 수행을 하며 DCT는 8 * 8 크기로 수행된다.

v DCT(Discreate Cosine Transforms)
영상에 있어서 고주파 부분을 버리고 저주파 부분에 집중시켜 공간적 중복성을 꾀하는 개념이다. 예를들어 에지(EDGE)가 많은 부분, 즉 얼굴의 윤곽이나, 머리카락이 흩날리는 부분 등은 화소 변화가 많으므로 이 부분을 제거하여 압축률을 높인다.

v 양자화(quantigation)
DCT로 구해진 화상정보의 계수값을 더 많은 '0'이 나오도록 일정한 값(quantizer value)으로 나오게 나누어 주다. 따라서 영상 데이터의 손실이 있더라도 사람의 눈에서 이를 시각적으로 감지하기 힘들게 된다면 어느 정도의 데이터에 손실을 가하여 압축률을 높이게 되는 것이다. 가장 단순한 양자화기는 스칼라(Scalar)양자화기로써 VLC(가변길이 부호기)와 병행하여 사용된다. 우선 입력 데이터가 가질 수 있는 값의 범위를 제한된 숫자의 구역으로 분할하여 각 구역의 대표 값을 지정한다. 스칼라 양자화기는 입력되는 화소값이 속하는 구역의 번호를 출력하고 구역의 번호로부터 이미 지정된 대표 값을 출력한다. 여기서 구역의 번호를 양자화 인덱스(quantigation index)라 하고 각 구역의 대표 값을 양자화 레벨(quantigation level)이라고 한다.
이 과정에서 최종적으로 나오는 이진 부호를 연속적으로 연결한 것을 비트 열이라 부르고 이보다 진보된 방법이 벡터 양자화기로서 전자의 스칼라 양자화기보다 압축률이 높다.
이 방법의 경우 입력이 인접한 화소의 블럭으로 이루어지며 양자화 코드에서 가장 유사한 코드 블록(양자화 레벨값에 해당)을 찾아 인덱스 부호값으로 결정한다. 간단하게 말하자면 스칼라(Scalar)양자화기는 2차원 적으로 압축하는 방식이며 벡터 양자화기는 3차원적으로 압축하는 방법이다.
MPEG-1에서는 버퍼의 상태에 따라서 이 값이 가변적으로 바뀌게 되어있고 MPEG-2에서는 이 방법에 화면의 복잡도를 미리 예측하여 양자화 값이 변하도록 미리 분석(forward analysys)하는 방법도 사용되어 화질을 향상시킬 수 있다..

v Motion Estimation
일반적인 실시간 동영상 압축방식에서는 아날로그 시그널(영상)을 이용해서 디지털 화하는데 일정한 움직임을 연산하여 추정할 수 있는 기능이 필요한데 이 기능을 수행해 주는 역할을 Motion Estimation이라고 한다.

9.3.2 I,P,B영상
이 세가지 영상은 MPEG 화상정보를 구성하고 있는 세가지 요소이다. 각 요소의 역할은 다음과 같다.

① I-FRAME (Intra-Frame) : 정지 영상을 압축하는 것과 동일한 방법을 사용하는 것으로 연속되는 화면의 기준을 이루는 화면이다.
② P-FRAME (Predict-Frame) : 이전에 재생된 영상을 기준으로 삼아 기준 영상 (I-PRAME)과의 차이점만을 보충하여 재생하는 화면이며 그 다음에 재생될 P-영상의 기준이 되기도 한다.
③ B-FRAME (Bidirectional-Frame) : I영상과 P영상 또는 P영상과 다음 P영상 사이에 들 어가는 재생된 영상인데 두 개의 기준영상을 양방향 에서 예측해서 붙여내는 영상이라서 이러한 이름을 갖는다.
④ 각 프레임의 배열 및 진행순서는 다음과 같다. (MPEG-1의 경우)

영상의 진행 방향
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
┃I┃B┃B┃P┃B┃B┃P┃B┃B┃I┃B┃B┃P┃B┃B┃P┃B┃B┃I┃B┃...
└── MPEG의 1프레임 ───┘

10 Conclusion
지금까지 세 가지의 압축 알고리즘을 살펴 보았다. Run-Length 압축법과 Lempel-Ziv 압축법은 고정 길이 압축법이고, Huffman 압축법은 가변 길이 압축법이라는 점에서 크게 구분된다. 그리고 그 프로그래밍도 판이하게 달랐다. 
일반적으로 압축 알고리즘의 속도 면에서 보면 Run-Length 압축법이 가장 빠르지만 압축률은 가장 낮다. Run-Length 압축법은 파일 내에 동일한 문자의 연속된 나열이 있어야만 압축이 가능하기 때문이다. 
이에 비해 Lempel-Ziv 압축법은 동일한 문자의 나열을 압축할 뿐 아니라, 동일한 패턴까지 압축하기 때문에 대부분의 경우에서 압축률이 가장 뛰어나다. 그러나 패턴 검색 방법이 최적화되지 않으면 속도면에서 불만을 안겨준다. 
Huffman 압축법은 텍스트 파일처럼 파일을 구성하는 문자의 종류가 적거나, 파일을 구성하는 문자의 빈도의 편차가 클수록 압축률이 좋아진다. Huffman 압축법은 많은 빈도수의 문자를 짧은 길이의 코드로, 적은 빈도수의 문자를 긴 길이의 코드로 대치하는 방법이어서 Huffman 나무가 한쪽으로 쏠려 있을수록 압축률이 좋다. 
그러나 빈도수가 고를 경우 Huffman 나무는 대체로 균형을 이루게 되어 압축률이 현저히 떨어진다. 또한 Huffman 압축법은 빈도수의 계산을 위해서 파일을 한번 미리 읽어야 하고, 다음에 실제 압축을 위해서 파일을 또 읽어야 하는 부담이 있어 실행 속도가 그리 빠르지는 않다.
실제 상용 압축 프로그램들은 주로 Huffman 압축법의 개량이나 Lempel-Ziv 압축법의 개량, 혹은 이 둘과 Run-Length 압축법까지 총동원해서 최대의 압축률과 최소의 실행시간을 보이도록 최적화되어 있다. 
MPEG에 대해서는 가볍게 알아본 수준이므로 따로 결론을 내리지 않는다.

10.1 테스트 실행 결과 표

Lempel-Ziv Huffman Run-Length    
  압축전 압축후 압축률 시간
(tick) 압축후 압축률 시간
(tick) 압축후 압축률 시간
(tick)   

10485760 10526665 100.39  519 10481196 99.96  333 10526667 100.39  63    
1048576 1052778 100.40  52 1048699 100.01  33 1052778 100.40  6    
102400 102837 100.43  4 103000 100.59  3 102837 100.43  0    
10240 10287 100.46  0 10888 106.33  0 10287 100.46  0    
1024 1037 101.27  0 1660 162.11  0 1037 101.27  0   

10485760 10485745 100.00  672 8755440 83.50  282 10485759 100.00  61    
1048576 1048586 100.00  68 875895 83.53  29 1048587 100.00  6    
102400 102413 100.01  6 86042 84.03  3 102413 100.01  0    
10240 10252 100.12  0 9162 89.47  0 10252 100.12  0    
1024 1035 101.07  0 1496 146.09  0 1035 101.07  0    
194166 186055 95.82  17 180201 92.81  5 189436 97.56  1    
23030 22474 97.59  2 19720 85.63  0 23024 99.97  0    
11140 9946 89.28  1 7094 63.68  0 10642 95.53  0    
4290 3876 90.35  0 3212 74.87  0 4212 98.18  0    
1837 1590 86.55  0 1628 88.62  0 1836 99.95  0    
616 582 94.48  0 1004 162.99  0 604 98.05  0    
10586696 8461305 79.92  1093 8588778 81.13  290 9952827 94.01  61    
2855505 1752182 61.36  218 2435711 85.30  80 2829020 99.07  18    
1578364 1314265 83.27  102 1519472 96.27  49 1574894 99.78  9    
1325260 949081 71.61  84 1196847 90.31  39 1314600 99.20  7    
1224317 874194 71.40  93 947260 77.37  31 1211083 98.92  8    
500156 455638 91.10  30 483908 96.75  15 498860 99.74  2    
319310 300707 94.17  20 313423 98.16  9 319376 100.02  2    
238011 234044 98.33  12 238312 100.13  7 238467 100.19  1    
132195 129917 98.28  7 132607 100.31  4 132438 100.18  1    
103552 98095 94.73  5 102657 99.14  3 103245 99.70  0    
122858 91968 74.86  9 111645 90.87  3 121114 98.58  1   

9506895 6618476 69.62  1278 5490732 57.76  188 8535883 89.79  53    
647976 470069 72.54  83 374771 57.84  12 596136 92.00  3    
598794 361639 60.39  93 328800 54.91  11 489528 81.75  3    
575805 375515 65.22  71 331114 57.50  11 525112 91.20  3    
556584 240776 43.26  111 272773 49.01  9 367820 66.09  2    
265104 144257 54.42  45 139221 52.52  5 196960 74.30  1    
103894 79976 76.98  12 61884 59.56  2 97805 94.14  0    
51266 39614 77.27  7 29175 56.91  1 47574 92.80  0    
20529 15489 75.45  2 12665 61.69  0 19418 94.59  0    
10304 7602 73.78  1 6800 65.99  0 9065 87.98  0    
5121 3166 61.82  1 3384 66.08  0 4069 79.46  0    
1021 704 68.95  0 1209 118.41  0 781 76.49  0   

4114 2919 70.95  1 2984 72.53  0 3542 86.10  0    
3081 1752 56.86  0 2350 76.27  0 2282 74.07  0    
2051 1592 77.62  0 1769 86.25  0 1762 85.91  0    
1541 1147 74.43  0 1543 100.13  0 1328 86.18  0    
118 130 110.17  0 728 616.95  0 132 111.86  0    
27 40 148.15  0 671 2485.19  0 40 148.15  0    
2121600 993817 46.84  441 922054 43.46  33 2121615 100.00  14    
980031 572607 58.43  93 623844 63.66  21 921999 94.08  5    
186032 100912 54.24  15 121494 65.31  3 173524 93.28  1    
56073 34332 61.23  4 38071 67.90  1 55945 99.77  0 

11  참고문헌
C언어로 설명한 알고리즘, 황종선 외 1인
C로 배우는 알고리즘, 이재규
http://java2u.wo.to/lectures/etc/ImageProcessing/image_processing0.html
http://viplab.hanyang.ac.kr/~hhlee/reference/ip/mpeg/intro-mpeg-kor.html






'프로그래밍 > 프로그래밍 공부' 카테고리의 다른 글

프로세스(Process) , 스케쥴링(Scheduling)  (0) 2016.02.15
스트림(Stream)이란  (0) 2016.02.05
압축  (0) 2016.01.28
statement란?  (1) 2016.01.27
DAO / VO / DTO란?  (2) 2016.01.27
RDBS,DB모델링,파일시스템 표현 차이  (0) 2016.01.26
Posted by GENESIS8

댓글을 달아 주세요


DB에 관련해서 statement가 나왔는데 무엇인지 의미 파악이 잘 되지 않아서 검색해보았다.


//statement의 영어 검색을 한국어로 보니 다음과 같이 나온다.


// 위키백과

문 (프로그래밍) 위키백과, 우리 모두의 백과사전. 컴퓨터 프로그래밍에서 문(文)은 명령형 프로그래밍 언어의 가장 작은 독립 요소이다. 프로그램은 하나 이상의 문이 연결되어 형성된다. 문은 식과 같은 내부 요소를 포함할 수 있다. C를 포함한 많은 프로그래밍 언어는 실행 코드와 정의를 포함하는 문과 더불어 문과 정의 사이에 구별을 둔다. 단순 문과 복합 문 사이에 구별을 둘 수 있다. 뒤에 나오는 것은 구성 요소로서의 문을 포함한다. 


영어 버전을 번역기로 돌려도 내용은 비슷하다.


문이 수행 될 몇몇 액션을 표현 명령형 프로그래밍 언어의 최소 독립형 요소이다. 그것은 특정 작업을 수행하기 위해 컴퓨터에 명령 고급 언어로 작성된 명령이다. 


결론내리자면 statement는 명령 문장이라고 얘기할 수도 있겠다.

DB에 작업을 지시하는 QUERY등, 명령 그 자체를 말하는 것이라 파악해도 되겠다.


그래서 statement는 무슨 역할인가 하니...


C와 다른 언어들로 찾아보려니 잘 안나오고, 주로 나오는 것은 JAVA의 Statement 객체였다.

Connection 객체로 연결을 한 후에, QUERY 작업을 수행하기 위해서 사용하고 있었다.


참조 출처 : https://blog.outsider.ne.kr/6


2. DB 연결 

Connection conn = null; conn = DriverManager.getConnection ("jdbc:oracle:thin:@localhost:1521:ORA92", "scott", "tiger");


Connection을 사용하기 위해서는 java.sql.Connection 을 임포트 해주어야 한다. conn이라는 커넥션을 만든 후에 DriverManager의 getConnection을 통해서 DB를 연결해 준다. 

첫 매개변수는 DB연결쪽이다. 

jdbc:oracle:thin:@부분은 동일하게 사용하고 localhost는 위치(자기자신)를 말한다. 다른PC이거나 할 경우는 IP를 입력해 주고 1521은 해당포트이며 ORA92는 오라클의 SID이다. 자신에 맞게 입력해준다. 두번째와 세번째는 오라클의 아이디와 패스워드이다. 

이 연결부는 SQLException예외처리로 Try-Catch로 감싸 주어야 한다. 


3. 쿼리 준비

PreparedStatement psmt = null; psmt = conn.prepareStatement("DB쿼리문"); 혹은 Statement stmt = null; stmt = conn.createStatement("DB쿼리문"); 를 사용한다. 


4. 쿼리 실행 

psmt.executeUpdate(); 로 쿼리를 실행한다. insert, update, delete 등 값을 받아 오지 않는 쿼리문은 executeUpdate를 이용해서 실행해 준다.


이런 설명도 있었다.

Statement 인터페이스 - Statement 인터페이스는 Connection 객체에 의해 프로그램에 리턴되는 객체에 의해 구현되 일종의 메소드 집합을 정의한다. Statement 객체는 Statement 인터페이스를 구현한 객체



정리해보자면 statement는 DB와 연결되는 connection 객체와의 의사 소통을 위해서, DB에게 명령을 내릴 때 그것을 던져주는 역할을 하는 interface로서, 사용자의 명령(文)에 대응하기 위한 객체인 것 같다.



'프로그래밍 > 프로그래밍 공부' 카테고리의 다른 글

스트림(Stream)이란  (0) 2016.02.05
압축  (0) 2016.01.28
statement란?  (1) 2016.01.27
DAO / VO / DTO란?  (2) 2016.01.27
RDBS,DB모델링,파일시스템 표현 차이  (0) 2016.01.26
연산자  (0) 2016.01.22
Posted by GENESIS8

댓글을 달아 주세요

  1. 공원상 2021.01.07 14:06  댓글주소  수정/삭제  댓글쓰기

    너무 잘 보고 있습니다. 감사합니다 ~ ^^

원본 출처 : http://lbass.tistory.com/entry/DAO-%EB%9E%80

http://choijaehyuk.com/128

http://everyit.tistory.com/4


DAO란 Data Access Object의 약어로서 실질적으로 DB에 접근하는 객체를 말한다.

DAO의 사용 이유는 효율적인 커넥션 관리와 보안성 때문이다.


정의

DAO란? 한마디로 Database의 data에 access하는 트랜잭션 객체이다. 일종의 객체라는 것을 잊지말도록 하자. DAO는 저수준의 Logic과 고급 비지니스 Logic을 분리하고, domain logic으로부터 persistence mechanism을 숨기기 위해 사용한다. (적절히 디자인을 하면 모든 domain logic을 바꾸는 대신에 DAO를 바꾸기만 하면 된다.)

persistence 계층 : Database(영구 저장소)에 data를 CRUD하는 계층

// Create , Read , Update , Drop의 줄임말


설명

웹서버는 DB와 연결하기 위해서 매번 커넥션 객체를 생성하는데, 이것을 해결하기 위해 나온것이 컨넥션 풀입니다. ConnectionPool 이란 connection 객체를 미리 만들어 놓고 그것을 가져다 쓰는것입니다. 또 다쓰고 난 후에는 반환해 놓는 것. 하지만 유저 한명이 접속해서 한번에 하나의 커넥션만 일으키지 않고 게시판 하나만 봐도 목록볼때 한번, 글읽을때마다 한번, 글쓸때 한번 등등... 엄청나게 많은 커넥션이 일어나기에, 커넥션풀은 커넥션을 또 만드는 오버헤드를 효율적으로 하기 위해 DB에 접속하는 객체를 전용으로 하나만 만들고, 모든 페이지에서 그 객체를 호출해다 사용한다면? 이렇게 커넥션을 하나만 가져오고 그 커넥션을 가져온 객체가 모든 DB와의 연결을 하는것이 바로 DAO객체입니다^^


DAO(Data Access Object)DB를 사용해 데이터를 조화하거나 조작하는 기능을 전담하도록 만든 오브젝트를 말한다.

 사용자는 자신이 필요한 Interface를 DAO에게 던지고 DAO는 이 인터페이스를
구현한 객체를 사용자에게 편리하게 사용 할 수 있도록 반환해줍니다.

 DB에 대한 접근을 DAO가 담당하도록 하여 데이터베이스 엑세스를 DAO에서만
하게 되면 다수의 원격호출을 통한 오버헤드를 VO나 DTO를 통해 줄일 수 있고
다수의 DB 호출문제를 해결할 수 있습니다. 또한 단순히 읽기만 하는 연산이므로
트랜잭션 간의 오버헤드를 감소할 수 있습니다.(?)


DTO(Data Transfer Object) VO(Value Object)로 바꿔 말할 수 있는데
계층간 데이터 교환을 위한 자바빈즈를 말한다. 여기서 말하는 계층간의
컨트롤러, 뷰, 비즈니스 계층, 퍼시스턴스 계층을 말하며 각 계층간 데이터 교환을
위한 객체를 DTO 또는 VO라고 부른다.
[그런데 VO는 DTO와 동일한 개념이지만 read only 속성을 가짐 ]


대표적인 DTO로는 폼데이터빈, 데이터베이스 테이블빈 등이 있으며, 각 폼요소나, 데이터베이스 레코드의 데이터를 매핑하기 위한 데이터 객체를 말한다. 즉 폼 필드들의 이름을 그대로 가지고 있는 자바빈 객체를 폼 필드와 그대로 매핑하여 비즈니스 계층으로 보낼 때 사용한다. 이런 객체를 DTO라고 부르며 VO(Value Object) 패턴이라고도 한다.
VO 패턴은 데이터 전달을 위한 가장 효율적인 방법이지만, 클래스 선언을 위해 많은 코드가 필요하다는 단점이 있다.

일반적인 DTO는 로직을 갖고 있지 않다. 순수한 데이터 객체이며 속성과 그 속성에 접근하기 위한 getter, setter 메소드만 가진 클래스를 말한다. 여기에 추가적으로 toString(), equals(), 등의 Object 클래스 메소드를 작성할 수 있다.

즉, 계층 간의 데이터 전달에 사용하는 데이터 객체들을 말한다.

1. DTO 클래스 예제

public class DTOBean {

private String name;

private int value;

private String data;

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public int getValue() {
return value;
}

public void setValue(int value) {
this.value = value;
}

public String getData() {
return data;
}

public void setData(String data) {
this.data = data;
}
}

2. DAO 클래스 예제



//DB와 연결할 Connection을 가져온다.
//어떤 DB를 사용할 것이며, 어떤 드라이브와 로그인 정보를 사용할 것인가.
//작업이 끝나면 사용한 리소스를 시스템에 돌려준다.
public class TestDao {

public void add(DTOBean dto) throws ClassNotFoundException, SQLException{
Class.forName("com.mysql.jdbc.Driver");
Connection c= DriverManager.getConnection("jdbc:mysql://localhost/springbook", "spring", "book");
PreparedStatement ps = c.prepareStatement("insert into users(id,name,password) value(?,?,?)");
ps.setString(1,  dto.getName());
ps.setInt(2,  dto.getValue());
ps.setString(3,  dto.getData());
ps.executeUpdate();
ps.close();
c.close();
}
}


'프로그래밍 > 프로그래밍 공부' 카테고리의 다른 글

압축  (0) 2016.01.28
statement란?  (1) 2016.01.27
DAO / VO / DTO란?  (2) 2016.01.27
RDBS,DB모델링,파일시스템 표현 차이  (0) 2016.01.26
연산자  (0) 2016.01.22
스테레오 타입(Stereotype)  (0) 2016.01.21
Posted by GENESIS8

댓글을 달아 주세요

  1. 2018.02.15 23:36  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

  2. 맛 밀 2018.10.25 20:46 신고  댓글주소  수정/삭제  댓글쓰기

    감사히 담아가겠습니다*^^*

원문 출처 : http://www.sqler.com/bSQLQA/476174

파일 시스템

데이터베이스 모델링

관계형 데이터베이스

파일(file)

엔터티(Entity)

테이블(table)

레코드(record)

튜플(Tuple)

행(row)

키(key)

유일값(identifier)

기본키(Primary key), unique

필드(field)

어트리뷰트(attribute)

컬럼(column)



'프로그래밍 > 프로그래밍 공부' 카테고리의 다른 글

statement란?  (1) 2016.01.27
DAO / VO / DTO란?  (2) 2016.01.27
RDBS,DB모델링,파일시스템 표현 차이  (0) 2016.01.26
연산자  (0) 2016.01.22
스테레오 타입(Stereotype)  (0) 2016.01.21
시퀀스 다이어그램(Sequence Diagram)  (1) 2016.01.21
Posted by GENESIS8

댓글을 달아 주세요

출처 : http://hanburn.tistory.com/106


[DB] DB Sharding은 무엇이고, 적용 전략은? ( 적용시 고려사항 )

개발 2012.02.15 17:44


작성자 : hanburn

작성일 : 2012-01-17

 

1. 샤딩 ( sharding ) 이란 무엇인가?

2. 샤딩 및 전략

 2.1 vertical partitioning

 2.2 Range Based Partitioning

 2.3 Key or Hash Based Partitioning

 2.4 Directory Based Partitioning

3. 샤딩 적용시 고려사항

  

 

 

1. 샤딩 ( sharding ) 이란 무엇인가?

관계형 데이터베이스에서 대량의 데이터를 처리하기 위해서 데이터를 파티셔닝하는 기술이다. (partitioning->분할함) 파티셔닝은 DBMS에서 지원하기도 하는데일부 DBMS ( MySQL 5.1 미만에서는 지원 안함에서는 지원안하기도 한다. 샤딩은 DBMS 레벨에서 데이터를 나누는 것이 아니고 데이터베이스 자체를 분할하는 방식이다따라서 어플리레이션 레벨에서 구현해야 한다.

간단하게 예를 들면전 세계의 고객 데이터를 저장하는 대형 데이터베이스를 분산한다고 할때미국 고객의 경우는 샤드A, 아시아 고객의 경우는 샤드B, 유럽 고객의 경우는 샤드C로 분할해서 저장할수 있다.  

 

 

2. 샤딩 및 전략

샤딩에서 데이터베이스를 분할하는 방법에 대해서 살펴본다각 방법마다 장단점과 주의할 점이 있으므로 서비스에 맞게 적절하게 선택하거나 조합하여 사용 한다.

 

2.1 Vertical Partitioning

    테이블 별로 서버를 분할하는 방식이다예를들면 사용자 프로필정보용 서버사용자 친구리스트용 서버사용자가 만든 컨텐츠사진같은것 ) 용 서버등으로 분할하는 방식이다.

    장점 : 구현이 간단하고전체 시스템에 큰변화가 필요 없다.

    단점 : 각 서버의 데이터가 점점 거대해지면 추가 샤딩이 필요해진다. ( 1천만명이 1000장의 사진을 생성한다면 컨텐츠 서버에 또 샤딩이 필요할 것이다. )

 

  2.2 Range Based Partitioning

    하나의 feature(또는 table)가 점점 거대해지는 경우 서버를 분리하는 방식이다. 예를들면 사용자가 많은경우 사용자의 지역정보를 이용해서 user 별로 서버를 분리하거나일정데이터라면 년도별로 분리거래정보라면 우편번호를 이용하는 방식이다.

    주의점 데이터를 분할하는 방법이 예측가능해야 한다.

 

  2.3 Key or Hash Based Partitioning

    이방식은 웹2.0 사이트에서 기본 파티셔닝 방식으로 알려져있다엔티티를 해쉬함수에 넣어서 나오는 값을 이용해서 서버를 정하는 방식이다사용자ID가 숫자일 경우 나머지연산( module operation)을 이용하는 방법이다.

    주의점 : 해쉬결과 데이터가 균등하게 분포되도록 해쉬함수를 정하는게 중요하다.

    단점 : 서버의 수를 늘리기 위해서 해쉬함수를 변경하는 작업이 무지무지 비싼 작업이다.

 

  2.4 Directory Based Partitioning

    파티셔닝 메커니즘을 제공하는 추상화된 서비스를 만드는 것이다.(데이터베이스 액세스 코드와는 떨어져 있는)  샤드키를 look-up 할수 있으면 되므로구현은 DB cach를 적절히 조합해서 만들수 있다.

 

 

3. 샤딩 적용시 문제점들 및 고려사항

 3.1 데이터 재분배 ( Rebalancing data )

  Sharding DB의 물리적인 용량한계나 성능한계에 다르면 shard의 수를 늘리는 scale-up 작업이 필요하다비스 정지 없이 scale-up 할수 있도록 설계방향을 잡아야 한다.

 

 3.2 샤딩으로부터 데이터 조인하기 ( Joining data from multiple shards )

   Sharding-db 간에 조인이 불가능 하기에 처음부터 역정규화를 어느정도 감수해야 한다. Shard의 목정이 대용량 데이터 처리이므로대용량처리시 수행성능을 위해서 데이터 중복은 trade-off 관계 ( 완전 고용과 물가 안정의 관계. 곧, 실업률(失業率)을 줄이면 물가가 상승하고, 물가를 안정시키면 실업률이 높아진다는 모순적 관계를 이르는 말임.) 임을 이미 알고 있다.

 

 3.3 샤드에 데이터를 파티션하는 방법 ( How do you partition your data in shards? )

  shard 해쉬함수를 잘 설계해야 한다.

 

 3.4 샤드간의 트랜잭션 문제

  Global Transaction을 사용하면 shard DB간의 트랜잭션도 가능하다그 유명한 XA인데성능저하의 문제가 있다.

 

 3.5 Global Unique Key

  DBMS 에서 제공하는 auto-increament를 사용하면 key가 중복될수 있기 때문에, application 레벨에서 Key 생성을 담당해야 한다.

 

 3.6 데이터는 작게

  Table의 단위를 가능한 작게 만들어야 한다.


'프로그래밍 > DB' 카테고리의 다른 글

샤딩(Sharding)이란?  (0) 2016.01.25
SP란? Stored Procedure [수정필요]  (1) 2016.01.21
Posted by GENESIS8

댓글을 달아 주세요


원문 출처 : 

http://www.terms.co.kr/IIS.htm

http://hackersstudy.tistory.com/16

http://w3svc.tistory.com/entry/IIS%EB%9E%80



IS[아이아이 에스]는 마이크로소프트의 윈도우NT용 인터넷 서버군(群)의 이름으로서, 여기에는 WebHTTPFTPGopher 등이 모두 포함되어 있다. IIS는 이미 넷스케이프나 마이크로시스템즈 등의 회사에서 선점하고 있는 인터넷 서버 시장을 마이크로소프트가 지배할 목적으로 내놓은 제품이다. 마이크로소프트는 IIS에 웹 사이트나 검색엔진을 만들고 관리하며, 데이터베이스를 이용한 웹기반의 응용프로그램 작성을 지원하는 일련의 프로그램들을 포함하였다. 마이크로소프트는, IIS가 윈도우NT 서버와 여러 가지 방법으로 밀접하게 통합되었으며, 그 결과 더 빠른 웹페이지 서비스가 가능해졌다고 주장하고 있다.

IIS를 구매하는 회사들은 웹페이지를 만드는데 마이크로소프트의 프론트페이지 제품을 사용할 수 있다. 웹 개발자들은 마이크로소프트의 ASP 기술을 이용할 수 있는데, 이는 액티브엑스 컨트롤을 내장하고 잇는 응용프로그램들이 웹페이지 내에 포함될 수 있다는 것을 의미한다. 개발자들은 또한 마이크로소프트의 ISAPI 인터페이스를 사용함으로써 서로 다른 사용자들을 위해 요구를 여과하여, 올바른 웹페이지를 받아볼 수 있도록 프로그램을 만들 수 있다. ASP와 ISAPI 프로그램들은 현재 많이 사용되고 있는 CGI 또는 SSI 프로그램들 보다 더욱 효율적으로 실행된다.

마이크로소프트는 인터넷 서비스 제공사업자의 마음을 끌만한 서버관리자용 특별 기능을 포함하였다. 그것은 단일 윈도우(또는 콘솔)로부터 모든 서비스들이나 사용자들을 관리할 수 있게된 것이다. 또한, 이 기능은 초기에 설치하지 않았어도 나중에 쉽게 그 요소를 추가할 수 있도록 설계되었으며, 관리용 윈도우는 개별 고객들의 사정에 맞게 조정될 수 있다.

IIS는 설치하기 쉽도록 설계된 보안기능을 제공하며, 이는 데이터베이스를 이용하고 트랜잭션 차원의 제어를 제공하는 마이크로소프트 트랜잭션 서버와 밀접하게 동작한다. IIS는 또한 오디오, 비디오 스트림을 전달하는 마이크로소프트의 NetShow도 지원한다.


IIS란 MS에서 Web Service를 목적으로 정의 한 서비스 모듈의 Windows방식 서비스의 명칭이다.

컴퓨터에 Web Service를 할수있는 통신포트를 개방해놓고 그 통신포트를 통하여 자신의 컴퓨터에 있는 정보, 자료, 파일등을 접근하는 사람으로 하여금 볼 수 있도록 하는 것을 Web Service라고 하는데, 이것을 하는 컴퓨터가 Web Server입니다.

 웹 서버란?

웹 서버는 클라이언트 컴퓨터의 요청을 받아들이고 이러한 요청에 대해 응답을 반환하는 특정 소프트웨어가 있는 컴퓨터입니다. 웹 서버를 사용하면 인터넷 또는 인트라넷 및 엑스트라넷을 통해 정보를 공유할 수 있습니다.


 IIS는 Internet Information Sevices(인터넷 정보 서비스) 의 약자 이며, 이크로소프트 원도우를 사용하는 서버들을 위한 인터넷 기반 서비스들의 모임

아파치 웹서버에 이어 세계에서 두번째로 가장 잘 알려진 웹서버입니다.

서버는 현재 FTP, SMTP, NNTP, HTTP/HTTPS를 포함하고 있습니다. 지금까지 IIS 8.0 버전이 나왔습니다.
(IIS 8.0 은 windwos server 2012, Windwos 8 부터 사용 가능합니다)

장점이자 단점인 마이크로소프트에서 제공하는 윈도우 OS에서만 사용이 가능하다는점.

IIS에서는 ASP 스크립트 언어를 사용 할 수 있다.

 

IIS 8.0 신규, 업데이트 기능

웹 서버 성능 비교
     (출처-http://www.gtcomm.net/blog/nginx-the-best-http-server/)

CPU Utilization // CPU 활용량
• IIS – 9 percent
• Nginx – 21 percent
• Apache – 26 percent

Peak Throughput // 단위시간 당 최대 정보 처리량
• IIS – 49,000 responses per second (r/s)
• Nginx – 23,000 r/s
• Apache – 14,000 r/s

Response Time // 응답 시간
• IIS – 2.8 milliseconds
• Nginx – 5.5 milliseconds
• Apache – 6.3 milliseconds


결론 : 짱 좋음


IIS 서버 Html 구축 하는법

OS : Windwos server 2012 R2 Datacenter

1.1 서버 관리자에서 역할 및 기능 추가

1.2 웹서버(IIS) 설치

 

2.IIS 관리자 실행

2.1 웹사이트 추가 클릭

2.2

(1)    사이트 이름 항목에는 추가 할 사이트에 원하는 이름을 적어준다. 
        관리자가 사이트들을 구별목적으로 사용되는 것이므로 별칭으로 적어두면 된다.

(2)    실제 경로 항목에서 웹사이트의 root로 설정할 디렉토리를 선택한다.

(3)    두 항목을 기재하였으면, 이제 확인을 누르고 대화상자를 닫는다. 
        웹 사이트 추가시에는 기본으로 “웹 사이트 즉시 시작” 항목에 체크가 되어 있어 확인을 누르면 웹사이트 추가와 동시에 서비스가 시작된다.

 

3.    사이트 추가가 완료 되었다면, 이제 IIS 관리자의 사이트 프레임 내에 방금 추가한 사이트가 등록된 것을 확인 할 수 있으며, "시작됨" 상태
        정상적으로서비스가 되고 있는 것을 확인 할 수 있다.

 

 

 

4.자, 그럼 이제 클라이언트에서 웹 브라우저로 접속하여 웹 서비스에 접속이 가능한지 확인을 해보자.root디렉토리에 만들어 놓은 Html 파일을 넣어놓고
브라우저를 열고 http://서버ip/change.html 이라고 주소를 입력해보면 만들어 놓은 html 파일이 열리는 것을 확인 할 수 있다.




'프로그래밍 > 웹 프로그래밍' 카테고리의 다른 글

HTML 기초  (0) 2016.02.21
비즈니스 로직(Business logic)?  (0) 2016.02.14
웹서버(Web Server) / 웹 서버 어플리케이션(WSA)  (0) 2016.02.14
웹 프로그래밍 기초  (0) 2016.02.14
ASP(Active Server Page)  (0) 2016.01.28
IIS란?  (0) 2016.01.25
Posted by GENESIS8

댓글을 달아 주세요

where(제네릭 형식 제약 조건)(C# 참조)


제네릭 형식 정의에서 where 절은 제네릭 선언에 정의된 형식 매개 변수의 인수로 사용할 수 있는 형식에 대해 제약 조건을 지정하는 데 사용됩니다. 


ex) 예를 들어, 다음과 같이 형식 매개 변수 T가 IComparable<T> 인터페이스를 구현하도록 제네릭 클래스 MyGenericClass를 선언할 수 있습니다.


public class MyGenericClass<T> where T:IComparable { }


where T : struct, IConvertible

ㄴ 이런 식으로 다수에 대해서 허용하는 것도 가능하니, 결론적으로 포지티브 방식인듯.

where의 영어적 의미가 '어디' 이니 어디에만 쓸 수 있다고 제약하는 식인듯 하다.


출처 : MSDN


'프로그래밍 > C++++ (C#)' 카테고리의 다른 글

도구 상자가 보이지 않는다!!!  (0) 2016.02.26
C#의 where  (0) 2016.01.22
delegate  (0) 2016.01.22
typeof  (0) 2016.01.22
c# using 키워드  (0) 2016.01.21
Posted by GENESIS8

댓글을 달아 주세요