2.3 Data Symbolaidd

Yn y pen draw, adeiladwyd yr holl wrthrychau data cyfansawdd a ddefnyddiasom hyd yma o rifau. Yn yr adran hon estynnwn allu cynrychioliadol ein hiaith drwy gyflwyno’r gallu i weithio â symbolau mympwyol fel data.

2.3.1Dyfynnu

Os gallwn ffurfio data cyfansawdd drwy ddefnyddio symbolau, gallwn gael rhestrau megis

(a b c d)
(23 45 17)
((Norah 12) 
 (Molly 9) 
 (Anna 7) 
 (Lauren 6) 
 (Charlotte 4))

Gall rhestrau sy’n cynnwys symbolau edrych yn union fel mynegiadau ein hiaith:

(* (+ 23 45) (+ x 9))
(define (fact n) 
  (if (= n 1) 
      1 
      (* n (fact (- n 1)))))

Er mwyn trin symbolau mae angen elfen newydd yn ein hiaith: y gallu i ddyfynnu gwrthrych data. Tybiwch ein bod eisiau adeiladu’r rhestr (a b). Ni allwn gyflawni hyn ag (list a b), oherwydd mae’r mynegiad hwn yn adeiladu rhestr o werthoedd a ac b yn hytrach na’r symbolau eu hunain. Mae’r mater hwn yn adnabyddus yng nghyd-destun ieithoedd naturiol, lle gellir ystyried geiriau a brawddegau naill ai yn endidau semantig neu’n llinynnau nodau (endidau cystrawennol). Yr arfer cyffredin mewn ieithoedd naturiol yw defnyddio dyfynodau i ddynodi bod gair neu frawddeg i’w drin yn llythrennol fel llinyn o nodau. Er enghraifft, llythyren gyntaf “John” yn amlwg yw “J.” Os dywedwn wrth rywun “dywedwch eich enw’n uchel,” disgwyliwn glywed enw’r person hwnnw. Fodd bynnag, os dywedwn wrth rywun “dywedwch ‘eich enw’ yn uchel,” disgwyliwn glywed y geiriau “eich enw.” Sylwch ein bod yn cael ein gorfodi i nythu dyfynodau i ddisgrifio’r hyn y gallai rhywun arall ei ddweud.⁹⁸

Gallwn ddilyn yr un arfer hwn i adnabod rhestrau a symbolau sydd i’w trin fel gwrthrychau data yn hytrach na mynegiadau i’w gwerthuso. Fodd bynnag, mae ein ffurf ddyfynnu yn wahanol i’r un mewn ieithoedd naturiol gan ein bod yn gosod dyfynod (yn draddodiadol, y symbol dyfynod sengl ') ar ddechrau’r gwrthrych i’w ddyfynnu yn unig. Gallwn wneud hyn yng nghystrawen Scheme oherwydd ein bod yn dibynnu ar fylchau a chromfachau crwn i amffinio gwrthrychau. Felly, ystyr y nod dyfynod sengl yw dyfynnu’r gwrthrych nesaf.⁹⁹

Gallwn yn awr wahaniaethu rhwng symbolau a’u gwerthoedd:

(define a 1)
(define b 2)

(list a b)
(1 2)

(list 'a 'b)
(a b)

(list 'a b)
(a 2)

Mae dyfynnu hefyd yn caniatáu inni deipio gwrthrychau cyfansawdd, gan ddefnyddio’r cynrychioliad argraffedig confensiynol ar gyfer rhestrau:¹⁰⁰

(car '(a b c))
a

(cdr '(a b c))
(b c)

Yn unol â hyn, gallwn gael y rhestr wag drwy werthuso '(), ac felly peidio â defnyddio’r newidyn nil mwyach.

Un weithdrefn gyntefig ychwanegol a ddefnyddir wrth drin symbolau yw eq?, sy’n cymryd dau symbol fel argiau ac yn profi a ydynt yr un fath.¹⁰¹ Drwy ddefnyddio eq?, gallwn weithredu gweithdrefn ddefnyddiol o’r enw memq. Mae hon yn cymryd dau arg, symbol a rhestr. Os nad yw’r symbol yn y rhestr (h.y., os nad yw’n eq? ag unrhyw eitem yn y rhestr), yna mae memq yn dychwelyd anwir. Fel arall, mae’n dychwelyd isrestr y rhestr sy’n dechrau gydag ymddangosiad cyntaf y symbol:

(define (memq item x)
  (cond ((null? x) false)
        ((eq? item (car x)) x)
        (else (memq item (cdr x)))))

Er enghraifft, mae gwerth

(memq 'apple '(pear banana prune))

yn anwir, tra bo gwerth

(memq 'apple '(x (apple sauce) y apple pear))

yn (apple pear).

Ymarfer 2.53: Beth fyddai’r dehonglydd yn ei argraffu wrth werthuso pob un o’r mynegiadau canlynol?

(list 'a 'b 'c)
(list (list 'george))
(cdr '((x1 x2) (y1 y2)))
(cadr '((x1 x2) (y1 y2)))
(pair? (car '(a short list)))
(memq 'red '((red shoes) (blue socks)))
(memq 'red '(red shoes blue socks))

Ymarfer 2.54: Dywedir bod dwy restr yn equal? os ydynt yn cynnwys elfennau hafal wedi’u trefnu yn yr un drefn. Er enghraifft, mae

(equal? '(this is a list) 
        '(this is a list))

yn wir, ond mae

(equal? '(this is a list) 
        '(this (is a) list))

yn anwir. I fod yn fwy manwl gywir, gallwn ddiffinio equal? yn ddychweliadol yn nhermau hafaledd sylfaenol eq? symbolau drwy ddweud bod a ac b yn equal? os yw’r ddau’n symbolau a bod y symbolau’n eq?, neu os yw’r ddau’n restrau fel bod (car a) yn equal? ag (car b) ac (cdr a) yn equal? ag (cdr b). Gan ddefnyddio’r syniad hwn, gweithredwch equal? fel gweithdrefn.¹⁰²

Ymarfer 2.55: Mae Eva Lu Ator yn teipio’r mynegiad canlynol i’r dehonglydd

(car ''abracadabra)

Er mawr syndod iddi, mae’r dehonglydd yn argraffu quote yn ôl. Esboniwch.

2.3.2Enghraifft: Differu Symbolaidd

Fel darlun o drin symbolau ac fel darlun pellach o haniaethu data, ystyriwch ddylunio gweithdrefn sy’n cyflawni differu symbolaidd ar fynegiadau algebraidd. Hoffem i’r weithdrefn gymryd mynegiad algebraidd a newidyn fel argiau a dychwelyd deilliad y mynegiad mewn perthynas â’r newidyn. Er enghraifft, os mai $a{x}^2+bx+c$ ac $x$ yw’r argiau i’r weithdrefn, dylai’r weithdrefn ddychwelyd $2ax+b$. Mae gan ddifferu symbolaidd arwyddocâd hanesyddol arbennig yn Lisp. Roedd yn un o’r enghreifftiau a ysgogodd ddatblygu iaith gyfrifiadurol ar gyfer trin symbolau. Ymhellach, roedd yn nodi dechrau’r trywydd ymchwil a arweiniodd at ddatblygu systemau grymus ar gyfer gwaith mathemategol symbolaidd, sydd ar hyn o bryd yn cael eu defnyddio gan nifer cynyddol o fathemategwyr cymhwysol a ffisegwyr.

Wrth ddatblygu’r rhaglen differu symbolaidd, dilynwn yr un strategaeth haniaethu data ag a ddilynasom wrth ddatblygu system rhifau cymarebol 2.1.1. Hynny yw, diffiniwn yn gyntaf algorithm differu sy’n gweithredu ar wrthrychau haniaethol megis “symiau,” “lluosymiau,” a “newidynnau” heb boeni am sut y cynrychiolir y rhain. Dim ond wedyn yr awn i’r afael â’r broblem gynrychioli.

Y rhaglen ddifferu â data haniaethol

Er mwyn cadw pethau’n syml, byddwn yn ystyried rhaglen differu symbolaidd syml iawn sy’n trin mynegiadau a adeiladir drwy ddefnyddio dim ond gweithrediadau adio a lluosi â dau arg. Gellir differu unrhyw fynegiad o’r fath drwy gymhwyso’r rheolau lleihau canlynol: $$\frac{dc}{dx}=0,\text{lle mae }c\text{ yn gysonyn }\text{neu'n newidyn }\text{sy'n wahanol i }x,$$ $$\begin{array}{rcl}\frac{dx}{dx}& =& 1,\\ \frac{d(u+v)}{dx}& =& \frac{du}{dx}+\frac{dv}{dx},\\ \frac{d(uv)}{dx}& =& u\frac{dv}{dx}+v\frac{du}{dx}.\end{array}$$ Sylwch fod y ddwy reol olaf yn ddychweliadol eu natur. Hynny yw, i gael deilliad swm, canfyddwn ddeilliadau’r termau yn gyntaf a’u hadio. Gall pob un o’r termau yn ei dro fod yn fynegiad y mae angen ei ddadelfennu. Bydd dadelfennu’n ddarnau llai a llai yn y pen draw yn cynhyrchu darnau sydd naill ai’n gysonion neu’n newidynnau, y bydd eu deilliadau naill ai’n 0 neu’n 1.

I ymgorffori’r rheolau hyn mewn gweithdrefn, caniatawn ychydig o feddwl dymunol inni ein hunain, fel y gwnaethom wrth ddylunio’r gweithrediad rhifau cymarebol. Pe bai gennym fodd o gynrychioli mynegiadau algebraidd, dylem allu dweud a yw mynegiad yn swm, yn lluoswm, yn gysonyn, neu’n newidyn. Dylem allu echdynnu rhannau mynegiad. Ar gyfer swm, er enghraifft, rydym eisiau gallu echdynnu’r term adio cyntaf (addend) a’r ail derm adio (augend). Dylem hefyd allu adeiladu mynegiadau o rannau. Tybiwn fod gennym eisoes weithdrefnau i weithredu’r detholwyr, yr adeiladwyr, a’r traethiadau canlynol:

(variable? e)          Ai newidyn yw e?
(same-variable? v1 v2) Ai’r un newidyn yw v1 ac v2?
(sum? e)               Ai swm yw e?
(addend e)             Term cyntaf y swm e.
(augend e)             Ail derm y swm e.
(make-sum a1 a2)       Adeiladwch swm a1 ac a2.
(product? e)           Ai lluoswm yw e?
(multiplier e)         Ffactor cyntaf y lluoswm e.
(multiplicand e)       Ail ffactor y lluoswm e.
(make-product m1 m2)   Adeiladwch luoswm m1 ac m2.

Gan ddefnyddio’r rhain, a’r traethiad cyntefig number?, sy’n adnabod rhifau, gallwn fynegi’r rheolau differu fel y weithdrefn ganlynol:

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
          (make-product 
           (multiplier exp)
           (deriv (multiplicand exp) var))
          (make-product 
           (deriv (multiplier exp) var)
           (multiplicand exp))))
        (else (error "unknown expression 
                      type: DERIV" exp))))

Mae’r weithdrefn deriv hon yn cynnwys yr algorithm differu cyflawn. Gan ei bod wedi’i mynegi yn nhermau data haniaethol, bydd yn gweithio ni waeth sut y dewiswn gynrychioli mynegiadau algebraidd, cyn belled â’n bod yn dylunio set briodol o ddetholwyr ac adeiladwyr. Dyma’r mater y mae’n rhaid inni fynd i’r afael ag ef nesaf.

Cynrychioli mynegiadau algebraidd

Gallwn ddychmygu llawer o ffyrdd o ddefnyddio strwythur rhestr i gynrychioli mynegiadau algebraidd. Er enghraifft, gallem ddefnyddio rhestrau o symbolau sy’n adlewyrchu’r nodiant algebraidd arferol, gan gynrychioli $ax+b$ fel y rhestr (a * x + b). Fodd bynnag, un dewis arbennig o syml yw defnyddio’r un nodiant rhagddodiadol mewn cromfachau ag y mae Lisp yn ei ddefnyddio ar gyfer cyfuniadau; hynny yw, cynrychioli $ax+b$ fel (+ (* a x) b). Yna dyma ein cynrychioliad data ar gyfer y broblem ddifferu:

• Symbolau yw’r newidynnau. Cânt eu hadnabod gan y traethiad cyntefig symbol?:

  (define (variable? x) (symbol? x))

• Mae dau newidyn yr un fath os yw’r symbolau sy’n eu cynrychioli yn eq?:

  (define (same-variable? v1 v2)
    (and (variable? v1)
         (variable? v2)
         (eq? v1 v2)))

• Adeiladir symiau a lluosymiau fel rhestrau:

  (define (make-sum a1 a2) (list '+ a1 a2))
  (define (make-product m1 m2) (list '* m1 m2))

• Rhestr y mae ei helfen gyntaf yn symbol + yw swm:

  (define (sum? x)
    (and (pair? x) (eq? (car x) '+)))

• Y term adio cyntaf yw ail eitem y rhestr swm:

  (define (addend s) (cadr s))

• Yr ail derm adio yw trydedd eitem y rhestr swm:

  (define (augend s) (caddr s))

• Rhestr y mae ei helfen gyntaf yn symbol * yw lluoswm:

  (define (product? x)
    (and (pair? x) (eq? (car x) '*)))

• Y lluosydd yw ail eitem y rhestr lluoswm:

  (define (multiplier p) (cadr p))

• Y lluosyn yw trydedd eitem y rhestr lluoswm:

  (define (multiplicand p) (caddr p))

Felly, dim ond cyfuno’r rhain â’r algorithm a ymgorfforir yn deriv sydd ei angen er mwyn cael rhaglen differu symbolaidd sy’n gweithio. Gadewch inni edrych ar rai enghreifftiau o’i hymddygiad:

(deriv '(+ x 3) 'x)
(+ 1 0)

(deriv '(* x y) 'x)
(+ (* x 0) (* 1 y))

(deriv '(* (* x y) (+ x 3)) 'x)
(+ (* (* x y) (+ 1 0))
   (* (+ (* x 0) (* 1 y))
      (+  x 3)))

Mae’r rhaglen yn cynhyrchu atebion cywir; fodd bynnag, nid ydynt wedi’u symleiddio. Mae’n wir bod $$\frac{d(xy)}{dx}=x\cdot <!--\; \cdot \; -->0+1\cdot <!--\; \cdot \; -->y,$$, ond hoffem i’r rhaglen wybod bod $x\cdot <!--\; \cdot \; -->0=0$, $1\cdot <!--\; \cdot \; -->y=y$, ac $0+y=y$. Dylai ateb yr ail enghraifft fod wedi bod yn y yn syml. Fel y dengys y drydedd enghraifft, daw hyn yn fater difrifol pan fo’r mynegiadau’n gymhleth.

Mae ein hanhawster yn debyg iawn i’r un a gawsom wrth weithredu rhifau cymarebol: nid ydym wedi lleihau atebion i’w ffurf symlaf. Er mwyn cyflawni’r lleihau rhifau cymarebol, dim ond adeiladwyr a detholwyr y gweithrediad yr oedd angen inni eu newid. Gallwn fabwysiadu strategaeth debyg yma. Ni newidiwn deriv o gwbl. Yn hytrach, newidiwn make-sum fel y bydd make-sum yn adio’r ddau derm ac yn dychwelyd eu swm os yw’r ddau yn rhifau. Hefyd, os yw un o dermau’r swm yn 0, yna bydd make-sum yn dychwelyd y term arall:

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) 
         (+ a1 a2))
        (else (list '+ a1 a2))))

Mae hyn yn defnyddio’r weithdrefn =number?, sy’n gwirio a yw mynegiad yn hafal i rif penodol:

(define (=number? exp num)
  (and (number? exp) (= exp num)))

Yn yr un modd, newidiwn make-product i gynnwys y rheolau bod 0 wedi’i luosi ag unrhyw beth yn 0, ac 1 wedi’i luosi ag unrhyw beth yn beth hwnnw ei hun:

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) 
             (=number? m2 0)) 
         0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) 
         (* m1 m2))
        (else (list '* m1 m2))))

Dyma sut mae’r fersiwn hon yn gweithio ar ein tair enghraifft:

(deriv '(+ x 3) 'x)
1

(deriv '(* x y) 'x)
y

(deriv '(* (* x y) (+ x 3)) 'x)
(+ (* x y) (* y (+ x 3)))

Er bod hyn yn dipyn o welliant, mae’r drydedd enghraifft yn dangos bod cryn ffordd i fynd eto cyn inni gael rhaglen sy’n rhoi mynegiadau ar ffurf y gallem gytuno mai hi yw’r “symlaf.” Mae problem symleiddio algebraidd yn gymhleth oherwydd, ymhlith rhesymau eraill, efallai na fydd ffurf sydd symlaf at un diben yn symlaf at ddiben arall.

Ymarfer 2.56: Dangoswch sut i estyn y rhaglen ddifferu sylfaenol i drin mwy o fathau o fynegiadau. Er enghraifft, gweithredwch y rheol ddifferu $$\frac{d(u^n)}{dx}=n{u}^{n-<!--\; -\; -->1}\frac{du}{dx}$$ drwy ychwanegu cymal newydd at y rhaglen deriv a diffinio gweithdrefnau priodol exponentiation?, base, exponent, ac make-exponentiation. (Gallwch ddefnyddio’r symbol ** i ddynodi codi i bŵer.) Ymgorfforwch y rheolau bod unrhyw beth wedi’i godi i’r pŵer 0 yn 1, ac unrhyw beth wedi’i godi i’r pŵer 1 yn beth hwnnw ei hun.

Ymarfer 2.57: Estynnwch y rhaglen ddifferu i drin symiau a lluosymiau o nifer mympwyol o dermau (dau neu fwy). Yna gellid mynegi’r enghraifft olaf uchod fel

(deriv '(* x y (+ x 3)) 'x)

Ceisiwch wneud hyn drwy newid y cynrychioliad ar gyfer symiau a lluosymiau yn unig, heb newid y weithdrefn deriv o gwbl. Er enghraifft, addend swm fyddai’r term cyntaf, a’r augend fyddai swm gweddill y termau.

Ymarfer 2.58: Tybiwch ein bod eisiau addasu’r rhaglen ddifferu fel ei bod yn gweithio â nodiant mathemategol cyffredin, lle mae + ac * yn weithredyddion mewnosodol yn hytrach na rhagddodiadol. Gan fod y rhaglen ddifferu wedi’i diffinio yn nhermau data haniaethol, gallwn ei haddasu i weithio â chynrychioliadau gwahanol o fynegiadau drwy newid yn unig y traethiadau, y detholwyr, a’r adeiladwyr sy’n diffinio cynrychioliad y mynegiadau algebraidd y mae’r rhaglen ddifferu i weithredu arnynt.

1. Dangoswch sut i wneud hyn er mwyn differu mynegiadau algebraidd a gyflwynir ar ffurf fewnosodol, megis (x + (3 * (x + (y + 2)))). I symleiddio’r dasg, tybiwch fod + ac * bob amser yn cymryd dau arg a bod y mynegiadau wedi’u hamgáu’n llawn mewn cromfachau.
2. Mae’r broblem yn mynd yn sylweddol anos os caniateir nodiant algebraidd safonol, megis (x + 3 * (x + y + 2)), sy’n hepgor cromfachau diangen ac yn tybio bod lluosi’n digwydd cyn adio. A allwch ddylunio traethiadau, detholwyr ac adeiladyddion priodol ar gyfer y nodiant hwn fel bod ein rhaglen ddeilliadau’n dal i weithio?

2.3.3Enghraifft: Cynrychioli Setiau

Yn yr enghreifftiau blaenorol adeiladasom gynrychioliadau ar gyfer dau fath o wrthrych data cyfansawdd: rhifau cymarebol a mynegiadau algebraidd. Yn un o’r enghreifftiau hyn roedd gennym ddewis symleiddio (lleihau) y mynegiadau naill ai wrth eu hadeiladu neu wrth ddethol, ond heblaw am hynny roedd dewis cynrychioliad ar gyfer y strwythurau hyn yn nhermau rhestrau’n syml. Pan drown at gynrychioli setiau, nid yw’r dewis o gynrychioliad mor amlwg. Yn wir, mae nifer o gynrychioliadau posibl, ac maent yn wahanol iawn i’w gilydd mewn sawl ffordd.

Yn anffurfiol, casgliad o wrthrychau gwahanol yw set. I roi diffiniad mwy manwl gallwn ddefnyddio dull haniaethu data. Hynny yw, diffiniwn “set” drwy bennu’r gweithrediadau a ddefnyddir ar setiau. Y rhain yw union-set, intersection-set, element-of-set?, ac adjoin-set. Traethiad yw Element-of-set? sy’n penderfynu a yw elfen benodol yn aelod o set. Mae Adjoin-set yn cymryd gwrthrych a set yn argiau ac yn dychwelyd set sy’n cynnwys elfennau’r set wreiddiol a’r elfen a atodwyd hefyd. Mae Union-set yn cyfrifo uniad dwy set, sef y set sy’n cynnwys pob elfen sy’n ymddangos yn y naill arg neu’r llall. Mae Intersection-set yn cyfrifo croestoriad dwy set, sef y set sy’n cynnwys dim ond elfennau sy’n ymddangos yn y ddau arg. O safbwynt haniaethu data, rydym yn rhydd i ddylunio unrhyw gynrychioliad sy’n gweithredu’r gweithrediadau hyn mewn ffordd sy’n gyson â’r dehongliadau a roddwyd uchod.¹⁰³

Setiau fel rhestrau heb drefn

Un ffordd o gynrychioli set yw fel rhestr o’i helfennau lle nad oes unrhyw elfen yn ymddangos fwy nag unwaith. Cynrychiolir y set wag gan y rhestr wag. Yn y cynrychioliad hwn, mae element-of-set? yn debyg i’r weithdrefn memq yn 2.3.1. Mae’n defnyddio equal? yn lle eq? fel nad oes rhaid i elfennau’r set fod yn symbolau:

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))

Gan ddefnyddio hyn, gallwn ysgrifennu adjoin-set. Os yw’r gwrthrych sydd i’w atodi eisoes yn y set, dychwelwn y set yn unig. Fel arall, defnyddiwn cons i ychwanegu’r gwrthrych at y rhestr sy’n cynrychioli’r set:

(define (adjoin-set x set)
  (if (element-of-set? x set)
      set
      (cons x set)))

Ar gyfer intersection-set gallwn ddefnyddio strategaeth ddychweliadol. Os gwyddom sut i ffurfio croestoriad set2 a cdr set1, dim ond penderfynu a ddylid cynnwys car set1 ynddo sydd ei angen. Ond mae hyn yn dibynnu ar a yw (car set1) hefyd yn set2. Dyma’r weithdrefn sy’n deillio o hyn:

(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) 
         '())
        ((element-of-set? (car set1) set2)
         (cons (car set1)
               (intersection-set (cdr set1) 
                                 set2)))
        (else (intersection-set (cdr set1) 
                                set2))))

Wrth ddylunio cynrychioliad, effeithlonrwydd yw un o’r materion y dylem roi sylw iddo. Ystyriwch nifer y camau sydd eu hangen ar ein gweithrediadau ar setiau. Gan eu bod i gyd yn defnyddio element-of-set?, mae cyflymder y gweithrediad hwn yn effeithio’n fawr ar effeithlonrwydd gweithrediad y setiau yn ei gyfanrwydd. Yn awr, er mwyn gwirio a yw gwrthrych yn aelod o set, efallai y bydd rhaid i element-of-set? sganio’r set gyfan. (Yn yr achos gwaethaf, canfyddir nad yw’r gwrthrych yn y set.) Felly, os oes gan y set $n$ o elfennau, gallai element-of-set? gymryd hyd at $n$ o gamau. Felly, mae nifer y camau sydd eu hangen yn tyfu fel $\mathrm{\Theta <!--\; \Theta \; -->}(n)$. Mae nifer y camau sydd eu hangen ar adjoin-set, sy’n defnyddio’r gweithrediad hwn, hefyd yn tyfu fel $\mathrm{\Theta <!--\; \Theta \; -->}(n)$. Ar gyfer intersection-set, sy’n gwneud prawf element-of-set? ar bob elfen o set1, mae nifer y camau sydd eu hangen yn tyfu fel lluoswm meintiau’r setiau dan sylw, neu $\mathrm{\Theta <!--\; \Theta \; -->}(n^2)$ ar gyfer dwy set o faint $n$. Bydd yr un peth yn wir am union-set.

Ymarfer 2.59: Gweithredwch y gweithrediad union-set ar gyfer cynrychioli setiau â rhestrau heb drefn.

Ymarfer 2.60: Nodwyd y byddai set yn cael ei chynrychioli fel rhestr heb elfennau dyblyg. Tybiwch yn awr ein bod yn caniatáu dyblygu. Er enghraifft, gellid cynrychioli’r set $\{1,2,3\}$ fel y rhestr (2 3 2 1 3 2 2). Dyluniwch weithdrefnau element-of-set?, adjoin-set, union-set, ac intersection-set sy’n gweithredu ar y cynrychioliad hwn. Sut mae effeithlonrwydd pob un yn cymharu â’r weithdrefn gyfatebol ar gyfer y cynrychioliad heb ddyblygu? A oes cymwysiadau lle byddech yn dewis y cynrychioliad hwn yn hytrach na’r un heb ddyblygu?

Setiau fel rhestrau trefnedig

Un ffordd o gyflymu ein gweithrediadau ar setiau yw newid y cynrychioliad fel bod elfennau’r set wedi’u rhestru mewn trefn gynyddol. I wneud hyn, mae angen rhyw ffordd o gymharu dau wrthrych fel y gallwn ddweud pa un sydd fwyaf. Er enghraifft, gallem gymharu symbolau’n eiriadurol, neu gallem gytuno ar ryw ddull o neilltuo rhif unigryw i wrthrych ac yna gymharu’r elfennau drwy gymharu’r rhifau cyfatebol. Er mwyn cadw ein trafodaeth yn syml, byddwn yn ystyried dim ond yr achos lle mae elfennau’r set yn rhifau, fel y gallwn gymharu elfennau gan ddefnyddio > ac <. Byddwn yn cynrychioli set o rifau drwy restru ei helfennau mewn trefn gynyddol. Er bod ein cynrychioliad cyntaf uchod yn caniatáu inni gynrychioli’r set $\{1,3,6,10\}$ drwy restru’r elfennau mewn unrhyw drefn, dim ond y rhestr (1 3 6 10) a ganiateir gan ein cynrychioliad newydd.

Gwelir un o fanteision trefnu yn element-of-set?: Wrth wirio a oes eitem yn bresennol, nid oes rhaid inni sganio’r set gyfan mwyach. Os cyrhaeddwn elfen o’r set sy’n fwy na’r eitem yr ydym yn chwilio amdani, yna gwyddom nad yw’r eitem yn y set:

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (car set)) true)
        ((< x (car set)) false)
        (else (element-of-set? x (cdr set)))))

Sawl cam y mae hyn yn ei arbed? Yn yr achos gwaethaf, efallai mai’r eitem yr ydym yn chwilio amdani yw’r fwyaf yn y set, felly mae nifer y camau yr un fath ag ar gyfer y cynrychioliad heb drefn. Ar y llaw arall, os chwiliwn am eitemau o lawer o feintiau gwahanol gallwn ddisgwyl y byddwn weithiau’n gallu rhoi’r gorau i chwilio ger dechrau’r rhestr, ac y bydd angen inni archwilio’r rhan fwyaf o’r rhestr droeon eraill. Ar gyfartaledd, dylem ddisgwyl gorfod archwilio tua hanner yr eitemau yn y set. Felly, bydd nifer cyfartalog y camau sydd eu hangen tua $n/2$. Twf $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ yw hwn o hyd, ond mae’n arbed ffactor o 2 inni, ar gyfartaledd, yn nifer y camau o gymharu â’r gweithrediad blaenorol.

Cawn gyflymiad mwy trawiadol gyda intersection-set. Yn y cynrychioliad heb drefn roedd angen $\mathrm{\Theta <!--\; \Theta \; -->}(n^2)$ o gamau ar y gweithrediad hwn, gan inni sganio set2 yn gyfan ar gyfer pob elfen o set1. Ond gyda’r cynrychioliad trefnedig, gallwn ddefnyddio dull mwy clyfar. Dechreuwch drwy gymharu elfennau cyntaf y ddwy set, x1 ac x2. Os yw x1 yn hafal i x2, yna mae hynny’n rhoi elfen o’r croestoriad, ac mae gweddill y croestoriad yn groestoriad rhannau cdr y ddwy set. Tybiwch, fodd bynnag, fod x1 yn llai nag x2. Gan mai x2 yw’r elfen leiaf yn set2, gallwn gasglu ar unwaith na all x1 ymddangos yn unman yn set2 ac felly nad yw yn y croestoriad. Felly, mae’r croestoriad yn hafal i groestoriad set2 â cdr set1. Yn yr un modd, os yw x2 yn llai nag x1, yna rhoddir y croestoriad gan groestoriad set1 â cdr set2. Dyma’r weithdrefn:

(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set2))
      '()
      (let ((x1 (car set1)) (x2 (car set2)))
        (cond ((= x1 x2)
               (cons x1 (intersection-set 
                         (cdr set1)
                         (cdr set2))))
              ((< x1 x2) (intersection-set 
                          (cdr set1) 
                          set2))
              ((< x2 x1) (intersection-set 
                          set1 
                          (cdr set2)))))))

I amcangyfrif nifer y camau sydd eu hangen ar y broses hon, sylwch ein bod ym mhob cam yn lleihau problem y croestoriad i gyfrifo croestoriadau setiau llai—gan dynnu’r elfen gyntaf o set1 neu set2 neu’r ddau. Felly, nifer y camau sydd eu hangen yw swm meintiau set1 ac set2 ar y mwyaf, yn hytrach na lluoswm y meintiau fel yn y cynrychioliad heb drefn. Twf $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ yw hwn yn hytrach nag $\mathrm{\Theta <!--\; \Theta \; -->}(n^2)$—cyflymiad sylweddol, hyd yn oed ar gyfer setiau cymedrol eu maint.

Ymarfer 2.61: Rhowch weithrediad o adjoin-set gan ddefnyddio’r cynrychioliad trefnedig. Drwy gyfatebiaeth ag element-of-set? dangoswch sut i fanteisio ar y drefn i gynhyrchu gweithdrefn sydd angen, ar gyfartaledd, tua hanner nifer y camau sydd eu hangen gyda’r cynrychioliad heb drefn.

Ymarfer 2.62: Rhowch weithrediad $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ o union-set ar gyfer setiau a gynrychiolir fel rhestrau trefnedig.

Setiau fel coed deuaidd

Gallwn wneud yn well na’r cynrychioliad â rhestrau trefnedig drwy drefnu elfennau’r set ar ffurf coeden. Mae pob nod o’r goeden yn dal un elfen o’r set, a elwir yn “gofnod” y nod hwnnw, a dolen at bob un o ddau nod arall (a all fod yn wag). Mae’r ddolen “chwith” yn pwyntio at elfennau sy’n llai na’r un yn y nod, a’r ddolen “dde” at elfennau sy’n fwy na’r un yn y nod. Mae Ffigur 2.16 yn dangos rhai coed sy’n cynrychioli’r set $\{1,3,5,7,9,11\}$. Gellir cynrychioli’r un set â choeden mewn nifer o wahanol ffyrdd. Yr unig beth sydd ei angen arnom ar gyfer cynrychioliad dilys yw bod pob elfen yn yr isgoeden chwith yn llai na chofnod y nod a phob elfen yn yr isgoeden dde yn fwy.

Dyma fantais y cynrychioliad â choed: Tybiwch ein bod am wirio a yw rhif $x$ wedi’i gynnwys mewn set. Dechreuwn drwy gymharu $x$ â’r cofnod yn y nod uchaf. Os yw $x$ yn llai na hwn, gwyddom mai dim ond yr isgoeden chwith sydd angen ei chwilio; os yw $x$ yn fwy, dim ond yr isgoeden dde sydd angen ei chwilio. Yn awr, os yw’r goeden yn “gytbwys,” bydd pob un o’r isgoed hyn tua hanner maint y goeden wreiddiol. Felly, mewn un cam rydym wedi lleihau’r broblem o chwilio coeden o faint $n$ i chwilio coeden o faint $n/2$. Gan fod maint y goeden yn haneru ym mhob cam, dylem ddisgwyl bod nifer y camau sydd eu hangen i chwilio coeden o faint $n$ yn tyfu fel $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$.¹⁰⁴ Ar gyfer setiau mawr, bydd hyn yn gyflymiad sylweddol o gymharu â’r cynrychioliadau blaenorol.

Gallwn gynrychioli coed gan ddefnyddio rhestrau. Bydd pob nod yn rhestr o dair eitem: cofnod y nod, yr isgoeden chwith a’r isgoeden dde. Bydd isgoeden chwith neu dde sy’n rhestr wag yn dynodi nad oes isgoeden wedi’i chysylltu yno. Gallwn ddisgrifio’r cynrychioliad hwn drwy’r gweithdrefnau canlynol:¹⁰⁵

(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
  (list entry left right))

Yn awr gallwn ysgrifennu’r weithdrefn element-of-set? gan ddefnyddio’r strategaeth a ddisgrifiwyd uchod:

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (entry set)) true)
        ((< x (entry set))
         (element-of-set? 
          x 
          (left-branch set)))
        ((> x (entry set))
         (element-of-set? 
          x 
          (right-branch set)))))

Gweithredir atodi eitem at set mewn ffordd debyg ac mae arno hefyd angen $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$ o gamau. I atodi eitem x, cymharwn x â chofnod y nod i benderfynu a ddylid ychwanegu x at y gangen dde neu’r gangen chwith, ac ar ôl atodi x at y gangen briodol cysylltwn y gangen newydd hon â’r cofnod gwreiddiol a’r gangen arall. Os yw x yn hafal i’r cofnod, dychwelwn y nod yn unig. Os gofynnir inni atodi x at goeden wag, cynhyrchwn goeden sydd â x yn gofnod iddi a changhennau de a chwith gwag. Dyma’r weithdrefn:

(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set))
         (make-tree 
          (entry set)
          (adjoin-set x (left-branch set))
          (right-branch set)))
        ((> x (entry set))
         (make-tree
          (entry set)
          (left-branch set)
          (adjoin-set x (right-branch set))))))

Mae’r honiad uchod y gellir chwilio’r goeden mewn nifer logarithmig o gamau’n dibynnu ar y dybiaeth fod y goeden yn “gytbwys,” h.y., bod gan isgoeden chwith ac isgoeden dde pob coeden tua’r un nifer o elfennau, fel bod pob isgoeden yn cynnwys tua hanner elfennau ei rhiant. Ond sut y gallwn fod yn sicr y bydd y coed a adeiladwn yn gytbwys? Hyd yn oed os dechreuwn â choeden gytbwys, gall ychwanegu elfennau ag adjoin-set gynhyrchu canlyniad anghytbwys. Gan fod lleoliad elfen a atodwyd o’r newydd yn dibynnu ar sut mae’r elfen yn cymharu â’r eitemau sydd eisoes yn y set, gallwn ddisgwyl y bydd y goeden yn tueddu i fod yn gytbwys ar gyfartaledd os ychwanegwn elfennau “ar hap.” Ond nid yw hyn yn sicrwydd. Er enghraifft, os dechreuwn â set wag ac atodi’r rhifau 1 hyd 7 yn eu trefn, cawn y goeden anghytbwys iawn a ddangosir yn Ffigur 2.17. Yn y goeden hon mae’r holl isgoed chwith yn wag, felly nid oes ganddi fantais dros restr drefnedig syml. Un ffordd o ddatrys y broblem hon yw diffinio gweithrediad sy’n trawsffurfio coeden fympwyol yn goeden gytbwys â’r un elfennau. Yna gallwn gyflawni’r trawsffurfiad hwn ar ôl pob ychydig o weithrediadau adjoin-set i gadw ein set yn gytbwys. Mae ffyrdd eraill o ddatrys y broblem hon hefyd, ac mae’r rhan fwyaf ohonynt yn cynnwys dylunio strwythurau data newydd lle gellir chwilio a mewnosod mewn $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$ o gamau.¹⁰⁶

Ymarfer 2.63: Mae pob un o’r ddwy weithdrefn ganlynol yn trosi coeden ddeuaidd yn rhestr.

(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (append 
       (tree->list-1 
        (left-branch tree))
       (cons (entry tree)
             (tree->list-1 
              (right-branch tree))))))

(define (tree->list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree)
        result-list
        (copy-to-list 
         (left-branch tree)
         (cons (entry tree)
               (copy-to-list 
                (right-branch tree)
                result-list)))))
  (copy-to-list tree '()))

1. A yw’r ddwy weithdrefn yn cynhyrchu’r un canlyniad ar gyfer pob coeden? Os nad ydynt, sut mae’r canlyniadau’n wahanol? Pa restrau y mae’r ddwy weithdrefn yn eu cynhyrchu ar gyfer y coed yn Ffigur 2.16?
2. A oes gan y ddwy weithdrefn yr un drefn twf yn nifer y camau sydd eu hangen i drosi coeden gytbwys ag $n$ o elfennau yn rhestr? Os nad oes, pa un sy’n tyfu’n arafach?

Ymarfer 2.64: Mae’r weithdrefn ganlynol list->tree yn trosi rhestr drefnedig yn goeden ddeuaidd gytbwys. Mae’r weithdrefn ategol partial-tree yn cymryd cyfanrif $n$ a rhestr ag o leiaf $n$ o elfennau yn argiau ac yn adeiladu coeden gytbwys sy’n cynnwys $n$ elfen gyntaf y rhestr. Y canlyniad a ddychwelir gan partial-tree yw pâr (a ffurfiwyd ag cons) y mae ei car yn goeden a adeiladwyd a’i cdr yn rhestr yr elfennau na chynhwyswyd yn y goeden.

(define (list->tree elements)
  (car (partial-tree 
        elements (length elements))))

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size 
             (quotient (- n 1) 2)))
        (let ((left-result 
               (partial-tree 
                elts left-size)))
          (let ((left-tree 
                 (car left-result))
                (non-left-elts 
                 (cdr left-result))
                (right-size 
                 (- n (+ left-size 1))))
            (let ((this-entry 
                   (car non-left-elts))
                  (right-result 
                   (partial-tree 
                    (cdr non-left-elts)
                    right-size)))
              (let ((right-tree 
                     (car right-result))
                    (remaining-elts 
                     (cdr right-result)))
                (cons (make-tree this-entry 
                                 left-tree 
                                 right-tree)
                      remaining-elts))))))))

1. Ysgrifennwch baragraff byr yn esbonio mor glir ag y gallwch sut mae partial-tree yn gweithio. Lluniwch y goeden a gynhyrchir gan list->tree ar gyfer y rhestr (1 3 5 7 9 11).
2. Beth yw trefn twf nifer y camau sydd eu hangen ar list->tree i drosi rhestr ag $n$ o elfennau?

Ymarfer 2.65: Defnyddiwch ganlyniadau Ymarfer 2.63 ac Ymarfer 2.64 i roi gweithrediadau $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ o union-set ac intersection-set ar gyfer setiau a weithredir fel coed deuaidd (cytbwys).¹⁰⁷

Setiau ac adalw gwybodaeth

Rydym wedi archwilio dewisiadau ar gyfer defnyddio rhestrau i gynrychioli setiau ac wedi gweld sut y gall y dewis o gynrychioliad ar gyfer gwrthrych data effeithio’n fawr ar berfformiad y rhaglenni sy’n defnyddio’r data. Rheswm arall dros ganolbwyntio ar setiau yw bod y technegau a drafodir yma’n ymddangos dro ar ôl tro mewn cymwysiadau sy’n ymwneud ag adalw gwybodaeth.

Ystyriwch gronfa ddata sy’n cynnwys nifer fawr o gofnodion unigol, megis ffeiliau personél cwmni neu drafodion mewn system gyfrifyddu. Mae system rheoli data nodweddiadol yn treulio llawer o amser yn cyrchu neu’n addasu’r data yn y cofnodion ac felly mae arni angen dull effeithlon o gyrchu cofnodion. Gwneir hyn drwy nodi rhan o bob cofnod i wasanaethu fel allwedd adnabod. Gall allwedd fod yn unrhyw beth sy’n adnabod y cofnod yn unigryw. Ar gyfer ffeil bersonél, gallai fod yn rhif adnabod cyflogai. Ar gyfer system gyfrifyddu, gallai fod yn rhif trafodiad. Beth bynnag yw’r allwedd, pan ddiffiniwn y cofnod fel strwythur data dylem gynnwys gweithdrefn ddethol key sy’n adalw’r allwedd sy’n gysylltiedig â chofnod penodol.

Yn awr cynrychiolwn y gronfa ddata fel set o gofnodion. I ganfod y cofnod ag allwedd benodol defnyddiwn weithdrefn lookup, sy’n cymryd allwedd a chronfa ddata yn argiau ac yn dychwelyd y cofnod sydd â’r allwedd honno, neu anwir os nad oes cofnod o’r fath. Gweithredir Lookup bron yn yr un ffordd ag element-of-set?. Er enghraifft, os gweithredir y set o gofnodion fel rhestr heb drefn, gallem ddefnyddio

(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) false)
        ((equal? given-key 
                 (key (car set-of-records)))
         (car set-of-records))
        (else 
         (lookup given-key 
                 (cdr set-of-records)))))

Wrth gwrs, mae ffyrdd gwell o gynrychioli setiau mawr na rhestrau heb drefn. Fel arfer gweithredir systemau adalw gwybodaeth lle mae rhaid “cyrchu ar hap” at gofnodion drwy ddull sy’n seiliedig ar goed, megis y cynrychioliad â choed deuaidd a drafodwyd eisoes. Wrth ddylunio system o’r fath, gall methodoleg haniaethu data fod o gymorth mawr. Gall y dylunydd greu gweithrediad cychwynnol gan ddefnyddio cynrychioliad syml a hwylus megis rhestrau heb drefn. Bydd hwn yn anaddas ar gyfer y system derfynol, ond gall fod yn ddefnyddiol wrth ddarparu cronfa ddata “fras a chyflym” i brofi gweddill y system â hi. Yn ddiweddarach, gellir addasu’r cynrychioliad data i fod yn fwy soffistigedig. Os cyrchir y gronfa ddata drwy ddetholwyr ac adeiladyddion haniaethol, ni fydd y newid hwn yn y cynrychioliad yn gofyn am unrhyw newidiadau i weddill y system.

Ymarfer 2.66: Gweithredwch y weithdrefn lookup ar gyfer yr achos lle mae’r set o gofnodion wedi’i strwythuro fel coeden ddeuaidd, wedi’i threfnu yn ôl gwerthoedd rhifiadol yr allweddi.

2.3.4Enghraifft: Coed Amgodio Huffman

Mae’r adran hon yn cynnig ymarfer mewn defnyddio strwythur rhestrau a haniaethu data i drin setiau a choed. Y cymhwysiad yw dulliau o gynrychioli data fel dilyniannau o rifau un a sero (didau). Er enghraifft, mae cod safonol ASCII a ddefnyddir i gynrychioli testun mewn cyfrifiaduron yn amgodio pob nod fel dilyniant o saith did. Mae defnyddio saith did yn ein galluogi i wahaniaethu rhwng $2^7$, neu 128, o wahanol nodau posibl. Yn gyffredinol, os ydym am wahaniaethu rhwng $n$ o symbolau gwahanol, bydd angen defnyddio ${\log }_2<!--\; \; -->n$ o ddidau fesul symbol. Os yw ein holl negeseuon yn cynnwys yr wyth symbol A, B, C, D, E, F, G, a H, gallwn ddewis cod â thri did fesul nod, er enghraifft

A 000  C 010  E 100  G 110
B 001  D 011  F 101  H 111

Gyda’r cod hwn, mae’r neges

BACADAEAFABBAAAGAH

wedi’i hamgodio fel y llinyn o 54 did

001000010000011000100000101
000001001000000000110000111

Gelwir codau megis ASCII a’r cod A-hyd-H uchod yn godau hyd sefydlog, gan eu bod yn cynrychioli pob symbol yn y neges â’r un nifer o ddidau. Weithiau mae’n fanteisiol defnyddio codau hyd newidiol, lle gellir cynrychioli symbolau gwahanol â niferoedd gwahanol o ddidau. Er enghraifft, nid yw cod Morse yn defnyddio’r un nifer o ddotiau a llinellau ar gyfer pob llythyren o’r wyddor. Yn benodol, cynrychiolir E, y llythyren amlaf, gan un dot. Yn gyffredinol, os yw rhai symbolau’n ymddangos yn aml iawn yn ein negeseuon a rhai’n anaml iawn, gallwn amgodio data’n fwy effeithlon (h.y., gan ddefnyddio llai o ddidau fesul neges) os neilltuwn godau byrrach i’r symbolau aml. Ystyriwch y cod amgen canlynol ar gyfer y llythrennau A hyd H:

A 0    C 1010  E 1100  G 1110
B 100  D 1011  F 1101  H 1111

Gyda’r cod hwn, amgodir yr un neges ag uchod fel y llinyn

100010100101101100011
010100100000111001111

Mae’r llinyn hwn yn cynnwys 42 did, felly mae’n arbed mwy nag 20% o le o gymharu â’r cod hyd sefydlog a ddangoswyd uchod.

Un o anawsterau defnyddio cod hyd newidiol yw gwybod pryd rydych wedi cyrraedd diwedd symbol wrth ddarllen dilyniant o seroau ac unau. Mae cod Morse yn datrys y broblem hon drwy ddefnyddio cod gwahanu arbennig (saib yn yr achos hwn) ar ôl dilyniant dotiau a llinellau pob llythyren. Ateb arall yw dylunio’r cod fel nad yw cod cyflawn unrhyw symbol yn ddechrau (neu’n rhagddodiad) cod symbol arall. Gelwir cod o’r fath yn god rhagddodiadol. Yn yr enghraifft uchod, amgodir A gan 0 ac amgodir B gan 100, felly ni all unrhyw symbol arall gael cod sy’n dechrau â 0 neu â 100.

Yn gyffredinol, gallwn sicrhau arbedion sylweddol os defnyddiwn godau rhagddodiadol hyd newidiol sy’n manteisio ar amleddau cymharol y symbolau yn y negeseuon sydd i’w hamgodio. Gelwir un cynllun penodol ar gyfer gwneud hyn yn ddull amgodio Huffman, ar ôl ei ddarganfyddwr, David Huffman. Gellir cynrychioli cod Huffman fel coeden ddeuaidd y mae ei dail yn symbolau sy’n cael eu hamgodio. Ym mhob nod o’r goeden nad yw’n ddeilen mae set sy’n cynnwys yr holl symbolau yn y dail sy’n gorwedd o dan y nod. Yn ogystal, neilltuir pwysau i bob symbol mewn deilen (sef ei amledd cymharol), ac mae pob nod nad yw’n ddeilen yn cynnwys pwysau sy’n swm holl bwysau’r dail oddi tano. Ni ddefnyddir y pwysau yn y broses amgodio na’r broses ddatgodio. Gwelwn isod sut y’u defnyddir i helpu i adeiladu’r goeden.

Mae Ffigur 2.18 yn dangos coeden Huffman ar gyfer y cod A-hyd-H a roddwyd uchod. Mae’r pwysau yn y dail yn dynodi bod y goeden wedi’i dylunio ar gyfer negeseuon lle mae A yn ymddangos ag amledd cymharol o 8, B ag amledd cymharol o 3, a phob un o’r llythrennau eraill ag amledd cymharol o 1.

O gael coeden Huffman, gallwn ganfod amgodiad unrhyw symbol drwy ddechrau wrth y gwraidd a symud i lawr nes cyrraedd y ddeilen sy’n dal y symbol. Bob tro y symudwn i lawr cangen chwith ychwanegwn 0 at y cod, a phob tro y symudwn i lawr cangen dde ychwanegwn 1. (Penderfynwn pa gangen i’w dilyn drwy brofi pa gangen sydd naill ai’n nod deilen y symbol neu’n cynnwys y symbol yn ei set.) Er enghraifft, gan ddechrau wrth wraidd y goeden yn Ffigur 2.18, cyrhaeddwn y ddeilen ar gyfer D drwy ddilyn cangen dde, yna gangen chwith, yna gangen dde, yna gangen dde; felly, y cod ar gyfer D yw 1011.

I ddatgodio dilyniant didau gan ddefnyddio coeden Huffman, dechreuwn wrth y gwraidd a defnyddio seroau ac unau olynol y dilyniant didau i benderfynu a ddylem symud i lawr y gangen chwith neu’r gangen dde. Bob tro y cyrhaeddwn ddeilen, rydym wedi cynhyrchu symbol newydd yn y neges, ac ar y pwynt hwnnw dechreuwn eto o wraidd y goeden i ganfod y symbol nesaf. Er enghraifft, tybiwch ein bod yn cael y goeden uchod a’r dilyniant 10001010. Gan ddechrau wrth y gwraidd, symudwn i lawr y gangen dde (gan mai 1 yw did cyntaf y llinyn), yna i lawr y gangen chwith (gan mai 0 yw’r ail ddid), yna i lawr y gangen chwith (gan mai 0 yw’r trydydd did hefyd). Daw hyn â ni at y ddeilen ar gyfer B, felly B yw symbol cyntaf y neges a ddatgodiwyd. Yn awr dechreuwn eto wrth y gwraidd, a symudwn i’r chwith oherwydd mai 0 yw’r did nesaf yn y llinyn. Daw hyn â ni at y ddeilen ar gyfer A. Yna dechreuwn eto wrth y gwraidd gyda gweddill y llinyn, 1010, felly symudwn i’r dde, i’r chwith, i’r dde, i’r chwith a chyrraedd C. Felly, y neges gyfan yw BAC.

Cynhyrchu coed Huffman

O gael “gwyddor” o symbolau a’u hamleddau cymharol, sut mae adeiladu’r cod “gorau”? (Mewn geiriau eraill, pa goeden fydd yn amgodio negeseuon â’r nifer lleiaf o ddidau?) Rhoddodd Huffman algorithm ar gyfer gwneud hyn a dangosodd mai’r cod sy’n deillio ohono yn wir yw’r cod hyd newidiol gorau ar gyfer negeseuon lle mae amledd cymharol y symbolau’n cyfateb i’r amleddau a ddefnyddiwyd i adeiladu’r cod. Ni fyddwn yn profi yma mai codau Huffman yw’r rhai optimaidd, ond byddwn yn dangos sut y caiff coed Huffman eu hadeiladu.¹⁰⁸

Mae’r algorithm ar gyfer cynhyrchu coeden Huffman yn syml iawn. Y syniad yw trefnu’r goeden fel bod y symbolau â’r amledd isaf yn ymddangos bellaf oddi wrth y gwraidd. Dechreuwch â’r set o nodau dail, sy’n cynnwys symbolau a’u hamleddau, yn ôl y data cychwynnol y bwriedir adeiladu’r cod ohono. Yn awr dewch o hyd i ddwy ddeilen â’r pwysau lleiaf a’u cyfuno i gynhyrchu nod sydd â’r ddau nod hyn yn ganghennau chwith a dde iddo. Pwysau’r nod newydd yw swm y ddau bwysau. Tynnwch y ddwy ddeilen o’r set wreiddiol a rhoi’r nod newydd hwn yn eu lle. Yn awr parhewch â’r broses hon. Ym mhob cam, cyfunwch ddau nod â’r pwysau lleiaf, gan eu tynnu o’r set a rhoi yn eu lle nod sydd â’r ddau hyn yn ganghennau chwith a dde iddo. Mae’r broses yn dod i ben pan nad oes ond un nod ar ôl, sef gwraidd y goeden gyfan. Dyma sut y cynhyrchwyd coeden Huffman Ffigur 2.18:

Dail cychwynnol  {(A 8) (B 3) (C 1) (D 1)
                  (E 1) (F 1) (G 1) (H 1)}

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

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

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

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

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

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

Uno terfynol     {({A B C D E F G H} 17)}

Nid yw’r algorithm bob amser yn pennu coeden unigryw, oherwydd efallai nad oes nodau unigryw â’r pwysau lleiaf ym mhob cam. Hefyd, mympwyol yw’r dewis o drefn cyfuno’r ddau nod (h.y., pa un fydd y gangen dde a pha un fydd y gangen chwith).

Cynrychioli coed Huffman

Yn yr ymarferion isod byddwn yn gweithio gyda system sy’n defnyddio coed Huffman i amgodio a datgodio negeseuon ac yn cynhyrchu coed Huffman yn ôl yr algorithm a amlinellwyd uchod. Byddwn yn dechrau drwy drafod sut y cynrychiolir coed.

Cynrychiolir dail y goeden gan restr sy’n cynnwys y symbol leaf, y symbol yn y ddeilen, a’r pwysau:

(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))

Bydd coeden gyffredinol yn rhestr o gangen chwith, cangen dde, set o symbolau, a phwysau. Rhestr o’r symbolau fydd y set o symbolau, yn hytrach na rhyw gynrychioliad mwy soffistigedig o set. Pan wnawn goeden drwy gyfuno dau nod, cawn bwysau’r goeden fel swm pwysau’r nodau, a’r set o symbolau fel uniad setiau symbolau’r nodau. Gan fod ein setiau symbolau wedi’u cynrychioli fel rhestrau, gallwn ffurfio’r uniad gan ddefnyddio’r weithdrefn append a ddiffiniasom yn 2.2.1:

(define (make-code-tree left right)
  (list left
        right
        (append (symbols left) 
                (symbols right))
        (+ (weight left) (weight right))))

Os gwnawn goeden fel hyn, mae gennym y detholwyr canlynol:

(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)))

Rhaid i’r gweithdrefnau symbols ac weight wneud rhywbeth ychydig yn wahanol yn dibynnu ar a gânt eu galw â deilen neu â choeden gyffredinol. Mae’r rhain yn enghreifftiau syml o weithdrefnau generig (gweithdrefnau sy’n gallu trin mwy nag un math o ddata), y bydd gennym lawer mwy i’w ddweud amdanynt yn 2.4 ac 2.5.

Y weithdrefn ddatgodio

Mae’r weithdrefn ganlynol yn gweithredu’r algorithm datgodio. Mae’n cymryd yn argiau restr o seroau ac unau, ynghyd â choeden Huffman.

(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))))

Mae’r weithdrefn decode-1 yn cymryd dau arg: rhestr y didau sy’n weddill a’r lleoliad presennol yn y goeden. Mae’n parhau i symud “i lawr” y goeden, gan ddewis cangen chwith neu dde yn ôl a yw’r did nesaf yn y rhestr yn sero neu’n un. (Gwneir hyn â’r weithdrefn choose-branch.) Pan gyrhaedda ddeilen, mae’n dychwelyd y symbol yn y ddeilen honno fel y symbol nesaf yn y neges drwy ddefnyddio cons i’w atodi at ganlyniad datgodio gweddill y neges, gan ddechrau wrth wraidd y goeden. Sylwch ar y prawf gwall yng nghymal olaf choose-branch, sy’n cwyno os yw’r weithdrefn yn canfod rhywbeth heblaw sero neu un yn y data mewnbwn.

Setiau o elfennau â phwysau

Yn ein cynrychioliad o goed, mae pob nod nad yw’n ddeilen yn cynnwys set o symbolau, yr ydym wedi’i chynrychioli fel rhestr syml. Fodd bynnag, mae’r algorithm cynhyrchu coed a drafodwyd uchod yn gofyn inni weithio hefyd â setiau o ddail a choed, gan gyfuno’r ddwy eitem leiaf yn olynol. Gan y bydd angen inni ganfod yr eitem leiaf mewn set dro ar ôl tro, mae’n gyfleus defnyddio cynrychioliad trefnedig ar gyfer y math hwn o set.

Byddwn yn cynrychioli set o ddail a choed fel rhestr o elfennau, wedi’u trefnu yn nhrefn gynyddol eu pwysau. Mae’r weithdrefn ganlynol adjoin-set ar gyfer adeiladu setiau’n debyg i’r un a ddisgrifiwyd yn Ymarfer 2.61; fodd bynnag, cymherir eitemau yn ôl eu pwysau, ac nid yw’r elfen sy’n cael ei hychwanegu at y set byth ynddi eisoes.

(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))))))

Mae’r weithdrefn ganlynol yn cymryd rhestr o barau symbol-amledd megis ((A 4) (B 2) (C 1) (D 1)) ac yn adeiladu set drefnedig gychwynnol o ddail, yn barod i’w cyfuno yn ôl algorithm Huffman:

(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))))))

Ymarfer 2.67: Diffiniwch goeden amgodio a neges enghreifftiol:

(define sample-tree
  (make-code-tree 
   (make-leaf 'A 4)
   (make-code-tree
    (make-leaf 'B 2)
    (make-code-tree 
     (make-leaf 'D 1)
     (make-leaf 'C 1)))))

(define sample-message 
  '(0 1 1 0 0 1 0 1 0 1 1 1 0))

Defnyddiwch y weithdrefn decode i ddatgodio’r neges, a rhowch y canlyniad.

Ymarfer 2.68: Mae’r weithdrefn encode yn cymryd neges a choeden yn argiau ac yn cynhyrchu’r rhestr didau sy’n rhoi’r neges wedi’i hamgodio.

(define (encode message tree)
  (if (null? message)
      '()
      (append 
       (encode-symbol (car message) 
                      tree)
       (encode (cdr message) tree))))

Gweithdrefn y mae rhaid ichi ei hysgrifennu yw Encode-symbol, sy’n dychwelyd y rhestr didau sy’n amgodio symbol penodol yn ôl coeden benodol. Dylech ddylunio encode-symbol fel ei bod yn nodi gwall os nad yw’r symbol yn y goeden o gwbl. Profwch eich gweithdrefn drwy amgodio’r canlyniad a gawsoch yn Ymarfer 2.67 â’r goeden enghreifftiol a gweld a yw’r un fath â’r neges enghreifftiol wreiddiol.

Ymarfer 2.69: Mae’r weithdrefn ganlynol yn cymryd yn arg restr o barau symbol-amledd (lle nad oes symbol yn ymddangos mewn mwy nag un pâr) ac yn cynhyrchu coeden amgodio Huffman yn ôl algorithm Huffman.

(define (generate-huffman-tree pairs)
  (successive-merge 
   (make-leaf-set pairs)))

Make-leaf-set yw’r weithdrefn a roddwyd uchod sy’n trawsffurfio’r rhestr barau yn set drefnedig o ddail. Successive-merge yw’r weithdrefn y mae rhaid ichi ei hysgrifennu, gan ddefnyddio make-code-tree i gyfuno elfennau lleiaf eu pwysau’r set yn olynol nes nad oes ond un elfen ar ôl, sef y goeden Huffman a ddymunir. (Mae’r weithdrefn hon ychydig yn ddyrys, ond nid yw’n gymhleth mewn gwirionedd. Os byddwch yn dylunio gweithdrefn gymhleth, yna rydych bron yn sicr yn gwneud rhywbeth o’i le. Gallwch fanteisio’n sylweddol ar y ffaith ein bod yn defnyddio cynrychioliad trefnedig o set.)

Ymarfer 2.70: Dyluniwyd yr wyddor wyth symbol ganlynol, gyda’r amleddau cymharol cysylltiedig, i amgodio geiriau caneuon roc y 1950au’n effeithlon. (Sylwch nad oes rhaid i “symbolau” “gwyddor” fod yn llythrennau unigol.)

A    2    NA  16
BOOM 1    SHA  3
GET  2    YIP  9
JOB  2    WAH  1

Defnyddiwch generate-huffman-tree (Ymarfer 2.69) i gynhyrchu coeden Huffman gyfatebol, a defnyddiwch encode (Ymarfer 2.68) i amgodio’r neges ganlynol:

Get a job
Sha na na na na na na na na

Get a job
Sha na na na na na na na na

Wah yip yip yip yip 
yip yip yip yip yip
Sha boom

Sawl did sydd ei angen ar gyfer yr amgodiad? Beth yw’r nifer lleiaf o ddidau y byddai ei angen i amgodio’r gân hon pe baem yn defnyddio cod hyd sefydlog ar gyfer yr wyddor wyth symbol?

Ymarfer 2.71: Tybiwch fod gennym goeden Huffman ar gyfer gwyddor o $n$ o symbolau, ac mai amleddau cymharol y symbolau yw $1,2,4,\dots <!--\; \dots \; -->,2^{n-<!--\; -\; -->1}$. Brasluniwch y goeden ar gyfer $n=5$; ar gyfer $n=10$. Mewn coeden o’r fath (ar gyfer $n$ cyffredinol), sawl did sydd ei angen i amgodio’r symbol amlaf? Y symbol lleiaf aml?

Ymarfer 2.72: Ystyriwch y weithdrefn amgodio a ddyluniasoch yn Ymarfer 2.68. Beth yw trefn twf nifer y camau sydd eu hangen i amgodio symbol? Gwnewch yn siŵr eich bod yn cynnwys nifer y camau sydd eu hangen i chwilio’r rhestr symbolau ym mhob nod a gyrhaeddir. Mae ateb y cwestiwn hwn yn gyffredinol yn anodd. Ystyriwch yr achos arbennig lle mae amleddau cymharol y $n$ symbol fel y’u disgrifiwyd yn Ymarfer 2.71, a rhowch drefn twf (fel ffwythiant o $n$) nifer y camau sydd eu hangen i amgodio’r symbolau amlaf a lleiaf aml yn yr wyddor.