허프만 인코딩 트리

이 절에서는 리스트 구조와 set 과 tree 를 다루기 위한 데이터 추상화를 연습해 보았다.

컴퓨터에서는 데이터를 나타내기 위해 0, 1 의 연속된 값을 사용하는데, 

아스키코드가 각각의 문자를 7개 비트를 활용하여 표현하는 것이 그 예라 할 수 있다.

7 비트를 사용하면 2^7 개의 데이터를 구분할 수 있다, 

일반적으로 n 개를 표현하기 위해 개의 비트가 필요하다

고정길이 인코딩 방식

예를 들면 문자를 표현하기 위해

A 000 C 010 E 100 G 110

B 001 D 011 F 101 H 111

와 같이 표현할 수 있다.

이를 따를때, 

BACADAEAFABBAAAGAH

는 다음과 같이 인코딩 된다 

001000010000011000100000101000001001000000000110000111 (54비트)

이런 코드방식을 각각의 심볼이 같은 개수의 비트로 구성되어 있으므로, fixed-length (고정길이) 코드라고 부른다.

고정 길이 대신 가변 방식의 코딩도 쓸모 있을때가 있다. 

가변길이 인코딩 방식

빈도가 월등히 높은 문자에 대해 좀더 적은 비트수를 할당하여, 데이터를 좀더 효율적으로 메시지를 인코딩 할 수 있다.

위 고정길이 인코딩방식의 예를 variable-length (가변길이) 인코딩 방식으로 다음과 같이 재정의해보자.

A 0 C 1010 E 1100 G 1110

B 100 D 1011 F 1101 H 1111

이제, 같은 문자를 다음과 같이 인코딩한다.

100010100101101100011010100100000111001111 (42비트)

고정 길이 인코딩 방식과 비교했을때 20% 가량의 공간절약 효과를 얻을 수 있다.

이런 가변길이 인코딩방식에도 문제가 있는데, 바로 어떤 지점에서 하나의 심볼이 종료된 것인지 알기가 어렵다는 것이다. 

모스코드는 이런문제를 특별한 구분자(seperator code) 를 두는 것으로 해결 했다. 또 다른 해결책은, 

어떤 심볼도 다른 문자의 인코딩 값을 시작 코드값으로 가질 수 없도록 디자인 하는 것이다.

A를 0 이라고 정한 위 예의 경우, 어떤 문자도 0으로 시작할 수 없다. 

일반적으로 가변길이 prefix 인코딩 방식을 적절히 사용하면 상당한 이점을 볼수있다. 

이런 인코딩의 한 scheme 이 huffman 인코딩 방식이며, 허프만인코딩은 바이너리 트리로 표현되어 심볼을 인코드 할 수 있다.

허프만 인코딩

허프만트리에서 각 리프는 상대빈도와 나타내고자하는 문자가 함께 표시되어 있다. 

어떤 심볼이든 root 에서 시작하여 리프로 도달하여야 문자가 있음을 확인할 수 있다. 

아래로 내려갈때, 왼쪽 가지로 가는경우 0을 추가하고, 반대로 오른쪽으로 이동하면 1을 추가한다. 

D 의 경우 1011 이 된다.

비트열을 허프만 트리를 통해 decode 하고자 하면, root 에서 시작하여 비트열의 숫자를 보고 트리를 쫗아가면 된다.

리프에 도달할때마다 심볼을 알아낸 것이되고, 다시 다음 심볼을 알아내기위해 root 로 돌아가면 된다. 

허프만 트리의 생성

알파벳과 상대빈도가 주어져있으면, 어떻게 코드를 만드는게 최선일까? 

다음 예제를 살펴보자. 

알고리즘은 간단하다. 

가장 적은 상대빈도를 지닌 심볼이 가장 멀리 위치하는 것이다.

리프노드의 집합으로부터 시작하여 가장 빈도수가 낮은 두개의 노드를 찾아 이를 왼쪽노드, 오른쪽노드로 갖는 

부모노드를 만들며, 이 노드가 두 가중치의 합을 갖게끔한다.

두 노드를 set 에서 제거하고, 대신 이 새 노드로 대체한다. 이제 이 과정을 반복한다. 

노드가 단 하나만 남을때까지 이 과정을 반복한다. 

다음과 같은 과정으로 진행된다 .

Initial leaves {(A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)}

Merge {(A 8) (B 3) ({C D} 2) (E 1) (F 1) (G 1) (H 1)}

Merge {(A 8) (B 3) ({C D} 2) ({E F} 2) (G 1) (H 1)}

Merge {(A 8) (B 3) ({C D} 2) ({E F} 2) ({G H} 2)}

Merge {(A 8) (B 3) ({C D} 2) ({E F G H} 4)}

Merge {(A 8) ({B C D} 5) ({E F G H} 4)}

Merge {(A 8) ({B C D E F G H} 9)}

Final merge {({A B C D E F G H} 17)}

이 알고리즘은 항상 유일한 트리를 만드는 것이 아닌데, 여러 노드가 가장 작은 가중치를 가질 수도 있기때문에다. 또한, 어떤 두 노드가 먼저 merge 될지 결정하는 것도 임의기 때문이기도 하다. 

허프만 트리의 표현

이제 허프만트리를 메시지를 인코드/디코드하는데 사용하고, 허프만트리를 생성하는 시스템을 살펴보자.

각 리프들은 leaf 라는 심볼을 포함한 리스트로 표현한다.

(define (make-leaf symbol weight)

(list 'leaf symbol weight))

(define (leaf? object)

(eq? (car object) 'leaf))

(define (symbol-leaf x) (cadr x))

(define (weight-leaf x) (caddr x))

두 노드를 merge 하게 되면, 두 노드의 union 을 한 심볼의 집합이 된다.

우리의 심볼집합은 리스트로 표현했기 때문에, union 을 위해 append 프로시져를 사용한다.

(define (make-code-tree left right)

(list left

right

(append (symbols left) (symbols right))

(+ (weight left) (weight right))))

- (left right (symbol-l symbol-r) sum-wgt-lr) 와 같은 리스트 구조가 되겠다.

이제 selector 를 정의한다. 

(define (left-branch tree) (car tree))

(define (right-branch tree) (cadr tree))

(define (symbols tree)

(if (leaf? tree)

   (list (symbol-leaf tree))

   (caddr tree)))

(define (weight tree)

(if (leaf? tree)

(weight-leaf tree)

(cadddr tree)))

- 위에서 설명한 리스트 형태와 컬러링으로 매칭시켜보면 (left right (symbol-l symbol-r) sum-wgt-lr)

여기서보면 symbols 와 weight selector 들은 leaf 여부에 따라 그 동작이 다르다.

이를 잘 다루기 위해 친숙한 개념인 generic 을 scheme 에서도 사용할 수 있는데, 이는 2.4 절과 2.5절에서 살펴보도록 한다. 

디코딩 프로시저

(define (decode bits tree)

(define (decode-1 bits current-branch)

(if (null? bits)

   '()

   (let ((next-branch

   (choose-branch (car bits) current-branch)))

   (if (leaf? next-branch)

 (cons (symbol-leaf next-branch)

     (decode-1 (cdr bits) tree))

 (decode-1 (cdr bits) next-branch)))))

(decode-1 bits tree))

(define (choose-branch bit branch)

(cond ((= bit 0) (left-branch branch))

  ((= bit 1) (right-branch branch))

           (else (error "bad bit -- CHOOSE-BRANCH" bit))))

- leaf 까지 내려왔으면 그때의 심볼을 다음 디코딩대상 비트들의 결과에 붙인다.

각 요소에 가중치가 있는 set

방금의 트리표현에서, leaf 가 아닌 트리 노드의 경우 리스트로 표현한 심볼의 set 을 구성했었다. (symbol-l symbol-r)

하지만 요전에 알고리즘을 설명했을때 두 가장 작은 아이템을 merge 함으로써 얻어진 leaf 들과 tree 의 집합에 대해 동작할 필요가 있었다.

반복해서 set 에서 가장 작은 아이템들을 찾을 필요가 있었으므로, 순서가 있는 표현 방식을 사용하는것이 좋겠다.

가중치의 순서에 따라 정렬한 리프와 노드의 리스트의 집합을 구성할것이다. 

아래의 adjoin-set 프로시져는 예제 2.61 에 묘사된 것과 비슷하나, weight 를 통해서 비교가 되고 이미 존재하는 요소는 추가되지 않는 다는 점이 다르다.

(define (adjoin-set x set)

(cond ((null? set) (list x))

  ((< (weight x) (weight (car set))) (cons x set))

 (else (cons (car set)

  (adjoin-set x (cdr set))))))

아래의 프로시져는 심볼-빈도 페어리스트를 받아 최초의 leaf 들에 대한 ordered set 을 구성한다. 

(define (make-leaf-set pairs)

(if (null? pairs)

   '()

   (let ((pair (car pairs)))

       (adjoin-set (make-leaf (car pair) ; symbol

      (cadr pair)) ; frequency

  (make-leaf-set (cdr pairs))))))

IO

Introduction to IO

IO a 

사이드 이펙트를 수행하고, 그 결과로 type a 의 value 를 리턴하는 abstract 타입을 고려할 수 있다.

statements 는 보통 사이드 이펙트를 통해 대부분 communicate 된다. I/O 모나드를 소개함으로써 하스켈에서 statement/action 의 개념을 소개한다. 그러나 이 개념 또한 expression 의 일환이라, 결합이 가능하다. (composition)

IO Char 

어떤 사이드이펙트를 수행하고 결과로 some character 를 리턴

IO ()

이 imperative type 에서도 가장 imperative 한 것이 IO () side effect 만 수행함

getChar :: IO Char
getChar :: () -> Char -- () -> something means trying to simulate laziness
putChar :: Char -> IO ()
return :: a -> IO a  -- 어떤것도 하지 않고 즉시 리턴 

a :: IO (Char, Char)
a = do x <- getChar
        getChar
        y <- getChar
        return (x,y)

standard input 으로 부터 3 문자를 읽어 첫번째, 세번째를 페어로 리턴

오른쪽에는 t 의 IO 가 위치하고 왼쪽에는 t 가 위치하여 두 타입이 다르므로, assign 연산자 대신 <- 를 사용하는 것.

getLine :: IO String
getLine = do x <- getChar
            if x == '\n' then
                return []
            else
                do xs <- getLine
                   return (x:xs)

이번엔 standard output 에 string 을 print 하는 IO 메서드

putStr :: String -> IO ()
putStr [] = return ()
putStr (x:xs) = do putChar x
                   pubStr xs

putStrLn :: String -> IO ()
putStrLn xs = do putStr xs
                 putChar '\n'

imperative code 나 I/O 코드를 다른 함수들과 사용할 수 있다는 데 그 강점이 있다. 특히 String 은 그 자체로 리스트이기때문에, 리스트에 사용되는 함수는 위와같은 방식으로의 활용도가 높다.

strlen :: IO ()
strlen = do putStr "Enter a string: "
            xs <- getLine
            putStr "The string has "
            putStr (show (length xs))
            putStrLn " characters"

pure code 를 작성하여 impure code 에 embeded 한 예라 할 수 있음.

1.What is a Parser ?

a + b * c 가 있을때 a , b , c 를 leaf 로 하고 연산자 (+, *) 를 parent 로 하는 트리 구조와 같이 나타낼 수 있는, 흔히 알고 있는 문자열을 구분할 수 있는 parser.

The Parser Type

type Parser = String -> Tree
type Parser = String -> (Tree, String) --not complete
type Parser = String -> [(Tree, String)] --list of result 
    can be empty - 하스켈에서는 리스트를 주로 이용. 다른 언어에서 많이 사용하는 Maybe 와 같이 비어 있는 타입과 값이 있는 경우를 구분하는 타입을 사용해도. 리스트 연산자들을 사용하기 편하므로 리스트를 쓰는게 관용 (idiom)
type Parser a = String -> [(a, String)] --We don't care Tree or not

문제를 간단하게 하기 위해, 성공한 경우에는 singleton list 를 ex. ['a', "hello"], 실패한 경우에는 빈 리스트를 리턴하는 경우만을 고려.

Basic Parsers

더 복잡한 Parser 구현을 위해 먼저 단순한 부분부터. 단일 문자 추출

item :: Parser Char
item = \inp -> case inp of
                []     ->  []
                (x:xs) ->  [(x, xs)]
-- 문자열 inp 를 받아 비어있는 경우는 빈리스트를, 데이터가 있는 경우는 첫번째 문자열과 나머지 문자열을 pair 로
-- 좌변에 패턴매칭을 사용하지 않아 두개 절을 사용하는 대신, 하나의 람다 표현식에 case 표현식을 사용하여 내부에서 패턴매칭을 사용함 -> 저자는 싱글 톤을 리턴하거나 빈 리스트를 리턴하는 함수임이 잘 나타나 있어 이런 형태를 좋아한다함

항상 실패하는 parser

failure :: Parser a
failure = \inp -> []

항상 성공하는 parser

return :: a -> Parser a
return v = \inp -> [(v, inp)]

parser p 가 성공한다면 parser p 와 같이 동작하고, 그렇지 않다면 parser q 와 같이 동작하는 parser (두 parser 를 받아 모두 시도해보는 parser)

-- 같은 타입을 parsing 하는 parser
(+++) :: Parser a -> Parser a -> Parser a     
p +++ q = \inp -> case p inp of
                    [] -> parse q inp
                    [(v, out)] -> [(v, out)]

parse :: Parser a -> String -> [(a, String)]
parse p inp = p inp

monads 그냥 특정 operation 이 있는 타입이라고 생각하라 함

2. Sequencing

parser 가 monad 이게 하는 다른 연산자 - (parser 의 sequence라 한다) - 를 살펴본다.

하나가 실패하면 다음을 시도하는것이 아니라 순차적으로 결합하고자 함.

이를 위해 do - syntax 라고 불리는 문법을 활용한다. (do 문법을 사용할 수 있는것은 모나드를 사용하는 장점 중에 하나이다.)

p :: Parser (Char, Char)
p = do x <- item
       item
       y <- item
       return (x, y)

parser 의 sequence 중 어느 하나라도 실패하면, 모두 실패한다.

Derived Primitives

predicate 를 만족하는 문자를 parsing 함

sat :: (Char -> Bool) -> Parser Char
-- 어떤 타입을 다른 타입을 통해 그 타입이 내포한 타입 시그니쳐를 표현 할 수 있다. 
-- sat :: (Char -> Bool) -> String -> [(a, String)]
sat p = do x <- item
           if p x then return x
           else failure

digit parsers

digit :: Parser Char
digit = sat isDigit

specific character parser

char :: Char -> Parser Char
char x = sat (x ==)
-- haskell 에서 sectioning (아마도 partial applying 을 지칭하는 것인듯) 을 하는 좋은 예
-- x 가 두군데 있으니 pointfree 스타일로 구성해 볼 수도 있다. 

parser 를 0 번 이상 적용하는 함수

many :: Parser a -> Parser [a]
-- String -> [(a, String)] -> String -> [([a], String)]
-- a 타입 파서를 받아서 a 의 리스트의 파서를 뱉는다 ?
many p = many1 p +++ return []
-- 먼저 최소한 한번의 Parser, p 를 적용해 보고 만약 실패하면 빈리스트를 리턴한다. 

many1 :: Parser a -> Parser [a]
many1 p = do v  <- p
             vs <- many p
             return (v:vs)
-- p 가 성공하면 다시 many 를 호출, 다시 parsing 을 시도한다. 
-- 성공한 파싱 결과들은 모두 v:vs 로 인해 append 된다.
-- 실패하는 순간 빈리스트가 append 되는것으로 종료. 
-- 왜, [a] 가 아니라 Parser [a] 인가 ? 
-- v <- p 이기 때문에..(결국 이녀석은 [a] 를 parsing 하는 함수를 리턴한다.)

parsing a specific string of characters

string :: String -> Parser String
string [] = return []
string (x:xs) = do char x
                   string xs
                   return (x:xs)
-- do sequence 에서 실패하면 이 함수 전체가 실패하므로, char 문자열에 반복적으로 적용하는 것으로 문자열을 파싱할 수 있다. 
-- 착각할 수 있는 부분이, 여기서 x 와 xs 는 파싱하고자하는 specific 문자열이지, 파싱 대상이 되는 문자열 ( input ) 이 아니다. 
-- Prefix 만을 파싱한다.

Example

1. parser that consumes a list of one or more digits from a string

p :: Parser String
p = do char '['
        d <- digit
        ds <- many (do char ','
                       digit)
        char ']'
        return (d:ds)
-- '[' 와 첫 번째 숫자를 파싱하고난 후에는 ',' 와 숫자로 이루어진 한개 이상의 문자를 파싱해야한다. 
-- 여기서 주목해야할 것은, many 의 인자 Parser a 에 다시 do 로 sequence parser 를 넣었다는 것이다. (익숙치 않아 어려웠다.)

> parse p "[1,2,3,4]"
[("1234"), ""]
> parse p "[1,2,3,4"
[]

3. Arithmetic Expressions

괄호를 사용한 수학식을 생각해보자.

표현식 문법 정의

expr -> term '+' expr | term
term -> factor '*' term | factor
factor -> digit | '(' expr ')'
digit -> '0' | '1' | ... | '9'

• expr : term + expr 혹은 term - 즉, 0개 이상의 + 로 엮은 식
• term : factor * term 혹은 factor - 즉, 0 개 이상의 * 로 엮은 식
• factor : 숫자 혹은 (expr) - 단일 숫자 혹은 괄호로 엮은 식
• digit : 0 ~ 9 - 수

massage to simpler definition

expr -> term ('+' expr | ɛ)
term -> factor ('*' term | ɛ)

여기서 엡실론 (ɛ) 은 어떤 것도 parsing 못하는 empty parser

expr :: Parser Int
expr = do t <- term
          do char '+'
             e <- expr
             return (t + e)
          +++ return t

term :: Parser Int
term = do f <- factor
          do char '*'
             t <- term
             return (f * t)
          +++ return f

factor :: Parser Int
factor = do d <- digit
            return (digitToInt d)
         +++ do char '('
                e <- expr
                char ')'
                return e

eval :: String -> Int
eval xs = fst (head (parse expr xs))

> eval "2*3+4"
10
> eval "2*(3+4)"
14