2.5.3 Example: Symbolic Algebra

수학 대수식을 다루는 과정에서 큰 시스템을 디자인 할때 발생하는 많은 어려움들이 발생한다.

일반적으로 수학 대수식은 피연산자들에 적용 되는 연산자들의 트리 계층구조로 생각 할 수 있다. 


수학 대수식을 만들기위해 기본 객체의 집합으로부터(constants, variables, 더하기나 곱하기와 같은 대수 연산자를 활용하여 엮기) 시작해보자. 


다른 언어들에서처럼 추상화를 통해 결합 객체를 단순한 용어로 다룰 수가 있다. 심볼 대수학에서의 전형적인 추상화 아이디어는 linear comblination, polynomial, rational function, trigonometric function 등이 있다. 


typical abstractions in sybolic algebra

* linear combination (일차 결합)

* polynomial (다항식)

* rational function (유리함수)

* trigonometric function (삼각함수)


x2 sin(y2 + 1) + x cos 2y + cos(y3 ¡ 2y2)


식을 x 에 대해 계수를 가진 polynomial 하다고 얘기할 수 있으며 이 계수는 y 에 대해 trigonometric function 이라고 할 수 있다. 

여기에서 완벽한 대수 조작 시스템을 만들진 않을 것인데, 그러기 위해서는 대수에 대한, 우아한 알고리즘에 대한 깊지식을 요하기 때문이다. 우리가 여기서 보고 시도할 것은 단순하지만 중요한 부분이다: polynomial 의 산술 연산.

이런 시스템에 직면했을 때의 결정사항들, 어떻게 추상데이터의 아이디어들, 제네릭 연산들을 적용하는지를 살펴보면 되겠다.


Arithmetic on polynomials

다항식이 무엇인지 정하는 것으로부터 시작해보자. 

문제의 단순화를 위해 하나의 변수를 가진 식으로 이야기해보자. 

우리는 다항식을 term 들의 합으로 정의하여, 각각의 term 은 계수이다. 


5x^2 + 3x + 7 과 5y^2 + 3y + 7 은 수학적인 관점에만 보면 같은 식이지만, 문법적인 관점에서 보면 같은 식이 아니다.


(y^2 + 1) x^3 + (2y)x + 1

대수학 적으로 이 식은 x 에 대한 다항식을계수로 갖는 y 에 대한 다항식과 동일하다.

이를 시스템적으로 인지가 가능해야할까 ? 그렇지 않을까 ? 

게다가, 다항식을 표현하는 다른 방법들도 있다. factor 들의 곱이라거나, 루트의 집합으로 표현하는 것이나, 점들의 집합에 대한 특정 다항식들의 값들을 나열하는 방법 등. 

우리는 이런 질문들을 우리의 대수조작 시스템에 정의하여 수학적 의미만에 기반하지 않고, 특정 문법화하게 될 것이다.


단순한 식에서는 더하기와 곱하기만 생각하면 되지만, 더 나아가 두 다항식이 결합되어 같은 indeterminate 가 되어야한다. (?)

poly 라는 이름으로 데이터 구조를 표현하였다. poly 는 term 들의 집합과 변수로 구성되어 있다. 

우리는 variable 과  term-list 라는 셀렉터를 이 파트들을 구분하는 용도로 사용한다. 

생성자는 make-poly 인데, 주어진 variable 과 term-list 를 묶는다.

variable 은 단순한 symbol 이므로, same-variable? 함수를 동일하게 사용할 수 있다.


(define (add-poly p1 p2)

(if (same-variable? (variable p1) (variable p2))

(make-poly (variable p1)

(add-terms (term-list p1)

(term-list p2)))

(error "Polys not in same var: ADD-POLY"

(list p1 p2))))

(define (mul-poly p1 p2)

(if (same-variable? (variable p1) (variable p2))

(make-poly (variable p1)

(mul-terms (term-list p1)

(term-list p2)))

(error "Polys not in same var: MUL-POLY"

(list p1 p2))))


다항식을 우리의 제네릭 산술 연산 시스템에 추가하기 위해, 타입 태그를 제공할 필요가 있다. polynomial 을 사용하자.


(define (install-polynomial-package)

;; internal procedures

;; representation of poly

(define (make-poly variable term-list)

(cons variable term-list))

(define (variable p) (car p))

(define (term-list p) (cdr p))

;;<procedures same-variable?

;;and variable? from section 2.3.2>


;; representation of terms and termlists

;;<procedures adjoin-term ... coeff from text below>

(define (add-poly p1 p2) ...)

;;<procedures used by add-poly>

(define (mul-poly p1 p2) ...)

;;<procedures used by mul-poly>

;; interface to rest of the system

(define (tag p) (attach-tag ’polynomial p))

(put ’add ’(polynomial polynomial)

(lambda (p1 p2) (tag (add-poly p1 p2))))

(put ’mul ’(polynomial polynomial)

(lambda (p1 p2) (tag (mul-poly p1 p2))))

(put ’make ’polynomial

(lambda (var terms)

(tag (make-poly var terms))))

’done)


다항덧셈은 텀 단위로 이뤄진다. 같은 차수의 텀들은 묶여야한다. 

같은 차수의 term 이 없는 경우 더해진 다항식이 생성될때 뒤에 덧붙여진다.

conetruct 를 위해 비어있는 term 목록을 반환하는 term-list 가 있고,

adjoin-term 을 위해 term 을 추가할 수 있도록 한다.

term 을 다루기위해 make-term 이라는 생성자를 통해 order 와 coeff 를 전달하여 엮어내는 생성자가,

두 부분을 리턴하는 selector가 있다고 가정한다.


(define (add-terms L1 L2)

(cond ((empty-termlist? L1) L2)

  ((empty-termlist? L2) L1)

 (else

(let ((t1 (first-term L1))

(t2 (first-term L2)))

(cond ((> (order t1) (order t2))

(adjoin-term

t1 (add-terms (rest-terms L1) L2)))

((< (order t1) (order t2))

(adjoin-term

t2 (add-terms L1 (rest-terms L2))))

(else

(adjoin-term

(make-term (order t1)

(add (coeff t1) (coeff t2)))

(add-terms (rest-terms L1)

(rest-terms L2)))))))))


generic 프로시져 add 를 계수들을 합치는데 사용했음을 주목하자.

다음에 이것이 큰 강점을 보인다.


두 term 목록을 곱하기위해 첫번째 리스트의 가각의 term 을 다른 리스트의 모두에 곱하는데 

mul-term-by-all-terms 를 사용하도록 한다. 

결과 리스트는 sum 에 누적된다.

두 term 의 곱은 피연사자의 차수들의 합이 되며, 계수는 곱셈연산자의 계수들의 곱이 된다. (?)


(define (mul-terms L1 L2)

(if (empty-termlist? L1)

(the-empty-termlist)

(add-terms (mul-term-by-all-terms (first-term L1) L2)

(mul-terms (rest-terms L1) L2))))

(define (mul-term-by-all-terms t1 L)

(if (empty-termlist? L)

(the-empty-termlist)

(let ((t2 (first-term L)))

(adjoin-term

(make-term (+ (order t1) (order t2))

(mul (coeff t1) (coeff t2)))

(mul-term-by-all-terms t1 (rest-terms L))))))


이제 다항식의 덧셈과 곱셈을 할 수 있게되었다. 여기서 add 와 mul 을 generic 프로시져를 활용하였기 때문에, 

제네릭 산술패키지에서 제공하는 어떤 타입이든 다룰 수 있게 된다.

2.5.2 절에서 사용하였던 coercion 메커니즘을 사용하면 자동적으로 다른 계수 타입의 다항식을 다루룰 수 있게된다. 


계수를 결합하기 위해 시스템은 add 와 mul 에 대해 dispatch 를 수행한다. 

계수들 자체가 다항식(y에 대해) 이기 때문에, add-poly 와 mul-poly 로 결합되게 된다. 


데이터 기반 재귀가 이뤄지게 된 것이다. (mul-poly 를 호출하였는데 계수를 곱하기 위해 다시 mul-poly) 


저작자 표시 비영리 변경 금지
신고

'SICP > 2. Building Abstractions with Data' 카테고리의 다른 글

2.5.3 Example: Symbolic Algebra  (0) 2015.11.01
2.5 System with Generic Operations  (0) 2015.09.13
2.3.4 Huffman Encoding Trees  (2) 2015.08.05
2.1.3 데이터란 무엇인가 ?  (0) 2015.02.07

2.5 System with Generic Operations

제네릭 연산의 체계


하나의 데이터 객체를 다른 방법으로 표현하여 디자인하는 시스템을 살펴보았다. 

중요한 아이디어는, 제네릭 인터페이스 프로시저들을 통해, 데이터 연산들을 몇몇의 표현에 연결하는 것이었다. 

이제 우리는 이러한 아이디어를 다른 표현에 이용하는데 그치지 않고 다른 인자들에도 접목하도록 한다.

우린 산술 연산들의 다양한 패키지를 이미 살펴보았다: 기본 산술 연산자들, (+, -, *, /) 

유리수 산술 연산 (add-rat, sub-rat, mul-rat, div-rat), 복소수 산술 연산들이 바로 그 것.


우리는 이제 데이터기반 테크닉을 산술연산의 패키지를 생성하는데 사용할 것이다.


누군가 "숫자"를 산다는 관점에서, add 연산이 제공된다. ADD 는 제네릭인터페이스의 일부인데, 별개의 일반적인 산술, 유리수 산술, 복소수 산술 패키지들이 일관된 형태로 접근 된다. 

어떤 별개의 산술연산 패키지는 제네릭 프로시져를 통해 접근되며, 이 프로시져는 패키지를 다른 표현으로 디자인된 패키지에 결합 (retangluar / polar ) 한다. 더 나아가, 이 시스템은 추가가 간편해서, 개별의 산술 패키지를 추가하고 제네릭 산술 시스템을 생성하도록 결합하는 것이 가능하다. 


2.5.1 제네릭 산술연산 

제네릭 산술 연산을 디자인 하는것은 제네릭 복소수 연산을 만드는 것과 유사하다. 예를 들면, 제네릭 프로시저 add 는 일반적인 수에는 + 를 적용하고, 유리수에는 add-rat 을 동작케하는 것과 같다. 다른 제네릭 산술 연산을 추가하기위해 2.4.3 에서 보았던 복소수를 위한 제네릭 선택자를 구현하는 것과 같은  전략을 사용하면 된다.

tag 를 추가하고 제네릭 프로시져가 적절한 패키지를 그것의 인자에 따라 디스패치하도록 한다.



제네릭 산술 연산은 다음과 같이 정의 된다.


(define (add x y) (apply-generic 'add x y))

(define (sub x y) (apply-generic 'sub x y))

(define (mul x y) (apply-generic 'mul x y))

(define (div x y) (apply-generic 'div x y))


일반 수에 대해서부터 시작해보자. tag 는 scheme-number


(define (install-scheme-number-package)

(define (tag x)

(attach-tag 'scheme-number x))

(put 'add '(scheme-number scheme-number)

(lambda (x y) (tag (+ x y))))

(put 'sub '(scheme-number scheme-number)

(lambda (x y) (tag (- x y))))

(put 'mul '(scheme-number scheme-number)

(lambda (x y) (tag (* x y))))

(put 'div '(scheme-number scheme-number)

(lambda (x y) (tag (/ x y))))

(put 'make 'scheme-number

(lambda (x) (tag x)))

'done)


scheme-number 패키지의 사용자는 다음 프로시져를 통해 숫자를 생성한다.


(define (make-scheme-number n)

((get 'make 'scheme-number) n))


제네릭산술체계의 틀이 잡혔으므로, 쉽게 새로운 종류의 수를 추가할 수 있다. 

추가가 손쉽다는 이점을 살려, 2.1.1 의 유리수 코드의 교체 없이 추가할수 있다.


(define (install-rational-package)

;; internal procedures

(define (numer x) (car x))

(define (denom x) (cdr x))

(define (make-rat n d)

(let ((g (gcd n d)))

(cons (/ n g) (/ d g))))

(define (add-rat x y)

(make-rat (+ (* (numer x) (denom y))

 (* (numer y) (denom x)))

   (* (denom x) (denom y))))

(define (sub-rat x y)

(make-rat (- (* (numer x) (denom y))

 (* (numer y) (denom x)))

   (* (denom x) (denom y))))

(define (mul-rat x y)

(make-rat (* (numer x) (numer y))

   (* (denom x) (denom y))))

(define (div-rat x y)

(make-rat (* (numer x) (denom y))

   (* (denom x) (numer y))))

;; interface to rest of the system

(define (tag x) (attach-tag 'rational x))

(put 'add '(rational rational)

(lambda (x y) (tag (add-rat x y))))

(put 'sub '(rational rational)

(lambda (x y) (tag (sub-rat x y))))

(put 'mul '(rational rational)

(lambda (x y) (tag (mul-rat x y))))

(put 'div '(rational rational)

(lambda (x y) (tag (div-rat x y))))

(put 'make 'rational

(lambda (n d) (tag (make-rat n d))))

'done)

(define (make-rational n d)

((get 'make 'rational) n d))


유사한 패키지를 complex 태그를 사용하여 복소수를 다루는데 추가할 수 있다. 


(define (install-complex-package)

;; imported procedures from rectangular and polar packages

(define (make-from-real-imag x y)

((get 'make-from-real-imag 'rectangular) x y))

(define (make-from-mag-ang r a)

((get 'make-from-mag-ang 'polar) r a))

;; internal procedures

(define (add-complex z1 z2)

(make-from-real-imag (+ (real-part z1) (real-part z2))

   (+ (imag-part z1) (imag-part z2))))

(define (sub-complex z1 z2)

(make-from-real-imag (- (real-part z1) (real-part z2))

   (- (imag-part z1) (imag-part z2))))

(define (mul-complex z1 z2)

(make-from-mag-ang (* (magnitude z1) (magnitude z2))

  (+ (angle z1) (angle z2))))

(define (div-complex z1 z2)

(make-from-mag-ang (/ (magnitude z1) (magnitude z2))

(- (angle z1) (angle z2))))

;; interface to rest of the system

(define (tag z) (attach-tag 'complex z))

(put 'add '(complex complex)

(lambda (z1 z2) (tag (add-complex z1 z2))))

(put 'sub '(complex complex)

(lambda (z1 z2) (tag (sub-complex z1 z2))))

(put 'mul '(complex complex)

(lambda (z1 z2) (tag (mul-complex z1 z2))))

(put 'div '(complex complex)

(lambda (z1 z2) (tag (div-complex z1 z2))))

(put 'make-from-real-imag 'complex

(lambda (x y) (tag (make-from-real-imag x y))))

(put 'make-from-mag-ang 'complex

(lambda (r a) (tag (make-from-mag-ang r a))))

'done)


이 패키지 외부의 프로그램은 복소수를 rectangluar form / ploarform 모두를 사용할 수 있다. 

바탕이 되는 프로시져가 (실제로는 어느한쪽의 패키지에 정의되어있는) 복소수 패키지 바깥으로 보여지고 있으며, 외부세계로 exported 하고 있다. 


(define (make-complex-from-real-imag x y)

((get 'make-from-real-imag 'complex) x y))

(define (make-complex-from-mag-ang r a)

((get 'make-from-mag-ang 'complex) r a))


여기서는 2단계의 태그 시스템을 가지고 있다. 어떤 표현방식 ( rec / pol ) 인지, 어떤 수인지 ( complex ) .

크고 복잡한 시스템에서는 많은 단계를 가지고 있을수 있으며, 다음을 위한 인터페이스들은 제네릭연산으로 인터페이스를 갖게 된다. 데이터 객체들이 "하위로" 전달됨에 따라, 바깥의 태그는 적절한 패키지로 방향을 잡고 contents 를 정요하여  이를 떼어내어 다음 단계의 태그가 앞으로의 dispatch 대상이 되도록 한다.


위의 패키지에서 add-rat / add-complex 를 완전히 예전에 썼던 코드를 그대로 사용하였다. 일단 각 인스톨 프로시져의 내부로 들어가게되면, 더이상 각각을 구분하기위한 이름은 필요없으므로, 단순한 이름을 사용하여도 된다. 




저작자 표시 비영리 변경 금지
신고

'SICP > 2. Building Abstractions with Data' 카테고리의 다른 글

2.5.3 Example: Symbolic Algebra  (0) 2015.11.01
2.5 System with Generic Operations  (0) 2015.09.13
2.3.4 Huffman Encoding Trees  (2) 2015.08.05
2.1.3 데이터란 무엇인가 ?  (0) 2015.02.07

2.3.4 Huffman Encoding Trees

허프만 인코딩 트리





이 절에서는 리스트 구조와 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으로 시작할 수 없다. 


가변길이 인코딩 방식의 문제점

* 특정 심볼 종료 지점을 알기가 어렵다


solution

1. separator code

각각의 구분자를 심볼종료시점에 넣는 인코딩 방식

2. prefix code

어떤 문자도 다른 문자를 시작코드 값으로 가질 수 없는 인코딩 방식 


일반적으로 가변길이 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))))))


저작자 표시 비영리 변경 금지
신고

'SICP > 2. Building Abstractions with Data' 카테고리의 다른 글

2.5.3 Example: Symbolic Algebra  (0) 2015.11.01
2.5 System with Generic Operations  (0) 2015.09.13
2.3.4 Huffman Encoding Trees  (2) 2015.08.05
2.1.3 데이터란 무엇인가 ?  (0) 2015.02.07


티스토리 툴바