ISSN: 1693-6 930                                                                11 7                                 Algoritm a  Untuk Mat c hing  Pada…… … ..(Slam et Santosa )   ALGORITMA UNTUK MATCHING PADA SISTEM  PENULI S AN ULANG EKSPRESI      Slamet Santosa 1 ,  Anton Setia w a n   Ho nggo w i bo w o  2   1 Staff Peneliti P3TM – BATAN, Jl. Babarsari Po Box 1 008 Yogya k a r ta, Telp. (02 74) 48 843 5   2 Jurusan Te knik Inform atika Sekola h Tin ggi Te knolo g i  Adisutjipto (STTA), Jl. Ja nti Blok-R  Lanu d. Adisut jipto Yogyaka r ta, Telp. (02 74) 45 126 2 F a x. (0274 ) 45 1265       A b st r a ct  Matchin g  pro c e ss in tre e  is finding su btree in a gi ven tree whi c h to be repl ace d  to  variable s  tho s e o c cu r in  pattern tree.  It is an  im portant  pro b l e m that o c curs a s  a  cru c ial  operation in  function al an d equ ational  prog ra m m in g su ch a s  T e rm  Re writin g System. We   pre s ent  an  al gorithm  for m a tchin g  p r o c e s s on   su ch te rm in  tre e   ba sed  on  p a ttern mat c hin g .  We  lineari z e  both  given t r ee  an d patte rn tree  into  st rin g  re pre s entatio n  by usi ng E u le r te chniq u e  a nd  and apply prefix-sum to compute r s the  rank of  all lineari z e d  edg e. And then we do matci n g on  string seq uen tial.    Kata kunci :   term  Rewritin g System , m a tching p r o c e s s, tree       1. PEN DA HU LU AN  Di dal am t e kni k  p e mrogra m an  ko mputasi  logi ka  ( com putational lo gic )  d an  pemrograma n  si stem  p e rsama an  ( equatio nal system   p r og ram m i ng ) ba nyak  dijum p ai  penyed erh a n aan  eksp re si  persa maan  den gan  be rt urut -turut mengg anti sub-sub   e k sp resi,  misalnya p a d a  spe s ifika s i  tipe data abstrak ( ab stra ct data type specifi c ation ) dan atau pa da   impleme n tasi  pemro grama n  fungsi onal  ( function al pro g ram m i ng ). Pada ba nyak li teratur te ntan g   model  komp utasi Siste m  Penulisan  Ulan g Ekspresi ( Term  Rewriting Sytem ,  TRS  [1][ 2])  komp utasi   de ngan ca ra pe nyederhan aa n  pe rsamaa n   eksp re si terseb ut adal ah  su atu ga ga san  penyed erh a n aan be rda s a r  pada him p u nan ( set ) tet apan  ( rul e s )  bertu rut-tu rut  hingga di ca pai  bentu k  palin g  sede rha na ( norm a l form ).   Subs titus i     adala h  pem etaan d a ri e k sp resi  ke  eksp resi yan g  me menuhi  ( F ( t 1 ,…, t n )) =  F ( ( t 1 ),…,  ( t n )) untu k  setiap sim pul fun g si  F ,  t  adala h  eksp re si atau su b e k spresi da n n   0.  Conto h  se de rhan a mod e l  komp utasi T R S dap at dipelaja r i den g an memp erh a tikan hi mpu nan  tetapan ( s e t of rules ) se bag ai beri k ut:    r 1  :  A (x ,0)   x    r 2  :  A (x , S (y )    S ( A (x ,y ))     r 3  :  M (x ,0)   0    r 4  :  M (x , S (y )    A ( M (x ,y ),x )     ( A=p enjum la han(A ddition ),M=pe rkalian ( Multiplicatio n) )    dan di be rika n sebua h e k spresi  M(S ( S ( 0),S(S (0 ))); S(0)  =  1. Pe mbaca d apat  deng an m u dah   memeri ksa,  ekspresi  tersebut d apat  di sed e rh ana ka n be rturut-turut den gan  su bstitusi   i  unt uk  setiap la ng ka h penyed erh a naan  sehi ngg a M( S(S(0),S (S(0 ))) ; S(S(S(S(0)))).     Pada ha ke ka tnya model  komputa s i terseb ut adal ah  operasi  pen yederh ana an  stru ktur  data tree  ( tree ) me ngg u nakan sub - sub tree  seb agai sub s titusi, deng an h i mpuna n teta pan  adala h  pola - p o la ( patterns ) tree.    Dalam  pe neli t ian ini  kami  memp elaja r i  tekni k   m a tching   suatu  e k spre si ya ng  mana  muncul be rul ang-ulan g pa da mod e l ko mputasi T R S.  Dibe rikan du a buah  eksp resi, dala m  si mbul  Evaluation Warning : The document was created with Spire.PDF for Python.
                                    ISSN: 1 693-693 0   TELKOM NIKA   Vol. 3, No. 2, Agustus 2 006 :  117 - 1 2 1   118 fungsi - fung si  f 1 ,  f 2, …,   f n,  dan variabel -vari abel  x 1 , x 2,…,  x n  dan dal am  hanya  simb u l  fungsi - fung si.  Matching  su atu eksp re si  adalah m e mberi k a n  ha rga- h a rga su bstitusi p ada  variabel -vari abel  sehi ngg a kedua b uah  ekspresi  ekivale n . Dua bua h ekspresi  f 1 ( f 2 ( f 3 ,x 1 ),x 2 ) dan   f 1 ( f 2 ( f 3 ,a), f 4 ( f 5 ( a ,b))) e k ivale n  bila da n ha nya b ila dida patka n su bsti tusi-sub stitusi   1  =   a  da n  2  =  f 4 ( f 5 (a,b)) d a n  masi ng-m a sin g  disub s titusi kan  se hingg a x 1  =  1  da n x 1  =  1 . Pada   penyed erh a n aan stru ktur data  tree ke d ua  e k spre si  d i atas a dalah  masin g -m asi ng pola t r ee  dan   obyek tre e .    Pada pe neliti an ini kami  berh a sil m e rancang al go ritma yang op timal untuk  m a tching   pola pad a ob yek tree, yan g  merup a kan  bagian pe nting pada te kni k  kom puta s i berb a si s teta pan  deng an mod e l kom puta s i  TRS. Algorit ma tersebut  menga dop si  tekni k  Euler  ( Euleri an circuit )  dan men ggu n a ka n uruta n   str i ng  yang terbentu k  untu k  melakukan p r ose s   ma tc h i ng .      2.  REPRESENTASI TEKNI K EULER  Euleria n  grap h  adal ah m e rupa kan  ran g kaian te rarah  ( dire cted circu i t ) yang me ru pakan   hasil j e ja kan  ( trav ers a l ) p a da st rukt ur d a ta tree.  Dibe rika n sebu ah  tree  T  =  ( V ,  E ), deng an  v     V   adala h  him p unan  nod e-n ode  ( no de s ) dan  e     E  adala h  hi mpuna n e d g e -ed ge  ( e dge s ).  Ran g kaian te rarah  T  ‘= ( V ,  E’ )  didapat deng an men gganti ma sin g -ma s in g ed ge ( u ,  v )  de ng a n   dua bu ah b u sur ( arc ) < u ,  v > da n < v ,  u >.  Seca ra seku ensi a l telah d i peri k sa ole h  Jaja [3] ba hwa,   Euleria n  grap h  dap at didef inisi k an  den g an menyata k an fung si p e ngga nti ( succes o r  func tion )  s   dan mem e takan tiap-tiap b u su r  e     E   k e   s ( e )    E ’ se hingg a  e  ko ntinyu pada  T  ‘=  ( V ,  E’ ).  Untu k men d a patka n fung si  pengg anti, p ada  setiap n o de  v     V  d a ri  tree, adal ah  deng an   menentu k a n   node -no de ya ng b e rseb ela han  den gan    v   d eng an me mbuat uruta n   ( o r de ring ) pa da  himpun an n o de-n ode, m e nggu na kan f ung si  adj ( v ) =  < u 0 ,  u 1 ,…, u d-1 >, deng an   d  adal ah d e rajat  dari nod e  v .  Pengga nti da ri ma sin g -m a s ing  bu su r  e  = ( u i , v ) a dala h   s (< u i , v> ) = < v, u (j+1)   mod  d >,  untuk tiap -tia p 0   i     d  -1. Un tuk lebih jel a snya, perhati k an co ntoh se bagai b e ri kut.  Con t oh:  Dibe rikan se buah  t r ee   T  =  ( V ,  E ) sep e rti ga mba r   1(a ) . Urutan   node -no de y ang b e rse bel ahan  deng an ma si ng-m a si ng n ode  v  d an fu ngsi p eng ga nti yang diha silkan ad a p ada gam ba r 1(b )   dan 1(c). dan   ran g kaian   te rarah  T  ‘= ( V ,  E’ ) ada pada  gamb a r 1(d).  Catata n: tre e  pa da g a mb ar  1(a )  menyata k an e k spresi  f ( f ( a , b ), f ( f ( a , a ), c )) .    f a a c f b a f f 9 8 7 6 5 4 3 2 1     1(a )   V ad j( v ) 1 2,3   2  4, 5, 1  3  6, 7, 1  4 2  5 2  6  8, 9, 3  7 3  8 6  9 6    1(b )   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA  ISSN:  1693-6 930                       Algoritm a  Untuk Mat c hing  Pada…… … ..(Slam et Santosa )   119   arc  2,1  3,1  4,2   5,2  1,2  6,3   7,3  1,3   2,4   2,5  8,6  9,6   3,6  3,7  6,8   6,9  su cc  1,3  1,2  2,5   2,1  2,4  3,7   3,1  3, 6  4,2   5,2  6,9  6,3   6,8  7,3  8,6   9,6    1(c)    1,2   2,4   4,2   2,5   5,2   2,1   1,3   3,6    6,8   8,6   6,9   6,3   3,7   7,3   3,1    1(d )     Gamba r  1. Rang kaia n Euler da ri se bua h  tree .    Salah satu  ca ra efisie n unt uk menyel esaika n masala h peng ord e ra n node -no de  dari tre e   adala h  den ga n meng ope ra sikan  linked-li st . Dibe rikan  T  = ( V ,  E ), un tuk setiap no de  v     V  no de - node ya ng  berseb e lah a n  deng an  v   adala h  ele m en da ri  linked-li st  L[ v ]=  < u 0 ,  u 1 ,…, u d-1 >.  Sehingg a  T  ‘=  ( V ,  E’ ),  L [ v ] dapat dia k se s untu k  meny ataka n  se mu a busur d a ri  v , yaitu < v , u 0 >,  < v , u 1 >,…,< v , u d-1 >. Deng a n  demiki an L [ v ] menyatakan se ca ra un ik sem ua bu sur  T  ‘= ( V ,  E’ ).  untuk men d a patka n b u su r < u i , v > dap a t  dilakukan d enga n me na mbah  pointe r  pad a tiap -tiap  node  u . Kem udian d eng a n  pro s e s   root ing  dida patka n kelu aran st ring b e ru ruta n mulai da ri root  ( ro ot ) dan  ke mbali ke  root.       3. PROSES  M A TCHI NG  PADA EKSP RE SI  Untu k memu dah kan pe mb aha san kami aka n  mempe r guna ka n seb uah obye k  tre e   s  dan   pola tree  p  sede rha n a  sepe rti pada gamb a r 2. Pada  aplikasi lanj ut memung kinka n   mengg una ka n pola-pola  tree seb a n yak jumla h  ekspre si t e tapan yan g  dipa kai u n tuk  menyele s ai ka n  m a tching  pada obye k  tree yang be sa r dan ru mit. Pada bab ini kami menyajikan   bebe rap a  de finisi yang berkaitan d e ngan p r o s e s   m a tching  pada  suatu  ekspre si yang  berm anfaat u n tuk pem bah asa n  pad a aspek p e ra ncan gan alg o ritma .     f c a c b f a f f f x a y f O b y e k  t r ee s P o l a  tre e  p     G a mb ar  2 .  Ob ye k  tr e e  da n Po la   tree .    Pada set variabel  V  dan  set sim bul fu ngsi F  kami  menga mbil a s um si  V     F  =  .  Masin g -m asi ng sim bul fu ngsi  f  me rup a ka n ariti  a f ,  intejer p o sit i f dan uni k. Ariti nol adal ah   kon s tanta. Se hingg a su atu ekspresi d a p a t didefinisi k a n  seb agai b e rikut.    Definisi 1 :   1.  Sebuah va ria bel dan ata u  seb uah  kon s t a ta adala h  ekspresi, da n   2. Jika  f     F  dan  t 1 ,  t 2 ,…,  t af   adala h  eksp resi demi k ia n juga  f ( t 1 ,  t 2 ,…,   t af )  3.  E ksp re si  f 1 ( f 2 ( a , b ), b ) d an  f 1 (b, f 2 ( a , b )) a dal ah dua b uah  ekspresi yan g  berb eda.   Evaluation Warning : The document was created with Spire.PDF for Python.
                                    ISSN: 1 693-693 0   TELKOM NIKA   Vol. 3, No. 2, Agustus 2 006 :  117 - 1 2 1   120 Matching  p o l a  tree  pa da  obyek  tr e e  di definisi k a n  sebag ai be ri kut. Dibe rikan  se buah  obyek tre e   s   berla bel da n tanpa vari abel  dan pola tre e   p  berlab e l da n mempu n yai   k  variabel.     Definisi 2 :   p m a tching  s  pad a nod e   x i  adala h  bi la dan ha nya bila terd ap at sub - sub tree menyata k an   ek spr e si   t 1 ,  t 2 ,…,  t n  dan de ngan  men g g anti  t i  untu k  v a riab el-va r iab e l yang  mun c ul pa da  p  a k an  didap atka n tree baru yang  identik d eng a n  subtree da ri  s deng an ro o t   x i .    Pada gamb a r 2,  p m a tching  s  adala h  p ada sa at did apatkan  t 1  =  f ( a , c ) d an  t 2  =  f ( b , c )  yang masi ng -masin g adal a h  sub s titusi u n tuk varia bel -variabel  x  da n  y .    Dalam  men d e sai n  alg o rit m a untu k   m a tching  ka mi mempe r gu na kan pen de kat an  p r o s es   m a tching  stri ng yang man a  adala h  ha si l dari [4], yang kami defini s ikan ul ang  se bagai b e ri kut.    Definisi 3 :   String  p m a tching  stri ng  s   pada p o si si string ke  i  ad a l ah bila da n hanya bila  string  s 1 ,  s 2 ,…,  s k   dan d enga n  mensub stitusi   s i  untu k  vari a bel-va r iabel  p ada  string  p  a k an  dida patkan stri ng b a ru   x   yang identi k  deng an sub s tring  s  p ada p o si si ke  i  da n  i  + | x | -1.    Pada gam b a r 2, didap at string ra ngkaian Eul e r  Ep  =  f , f , a , f , x , f , f , y , f  dan  E s =  f , f , a , f , a , f , c , f , f , f , f b , f , c , f , f . dapat diperi k sa b ahwa  Ep mat c hes  Es  untu k  x =  f , a , f , c , f  dan  y  =  f , b , f , c , f .   Pada  alg o rit m a  m a tching  string  dipe rl uka n  ma su kan obye k  st ring dan  pola  string  masin g -m asi ng p ada  arra y | Es | dan  | Ep | se bagai   kelu ara n  p r o s e s  lin eari s a s i me ngg una ka n   tekni k  Euler.  Kemudia n  un tuk verifikasi  pada al gorit ma kami m e manfaatkan  sifat-sifat  Es | dan  | Ep | sebagai  beri k ut.  1.  Tiap-tia p  dau n ( lead ) da ri tree ha nya mu ncul  satu kali pada rang kai an Euler.   2.  Nod e  yang m e mpunyai a r it i  af  muncul sebanya k   af  +  1 kali.   3.  Substri ng p a da rang kai a n  Eu ler  pad a  antara mu n c ulnya  nod e   x  p e rtam a  dan te ra khir   adala h  juga rang kaia n Euler den gan  ro ot  x .    Step-ste p  dari algoritma u n t uk  m a tching   ekspresi a dal ah se bag ai b e rikut:  1.  Linea risasi p ada obye k  da n pola tree ya ng dibe rikan  mengg una ka n tekni k  Euler.  2. Proses  rootin g  mengg una kan  prefi x -sum  pada tiap ed ge yang terb e n tuk.   3.  Partisi pol a string  untu k  memb e n t u k  st ru kt ur p o la  st ring:   1 v 1 2 v 2 … k v k k v k-1 ,  v  adalah   variabel strin g .  4.  Akse s tabel u n tuk men data  kompa r a s i st ring pa da tiap -tiap su bst r in g.      4.    ALGORI T MA  MA TCHIN G  EKSPRESI   Linearisasi tree:  Input:  Seb u a h  tree be rlab el, tiap node  mempu n yai 2  buah poi nter  Outpu t :  Li st  stru ktur n ode,  pointer ed ge  menyatakan rang kaia n tera rah Eule r  Begin   1.  Lakukan jeja kan ( tr av er sa l ) denga n  De pt-Fir st-Se a r c h  oder  2.  Pada tiap no de, ce k strukt ur point e r  da n tentuka n  ad jace nt node s,   Ak tifk an  linked-list .  Up date  stru ktur poi nter be rda s a r   ad j ( v ) =  <  u 0 ,  u 1 ,…, u d-1  >  3.  Den gan fun g s i pen gga nti  s (<   u i , v  >) =  <   v , u ( i+1 ) mod  d  > set ed ge  variabel,   Upd a te stru kt ur nod e point er. Simpan variab el adja c ent edge p a d a  array.  End.    Proses roo t i ng:  Input:  Li st struktur n ode, p o inter ed ge u n tuk ra ng kaia n terarah Eul e r  Outpu t :  Li st  stru ktur n ode.  Elemen pert a ma adal ah root.  Begin   1.  Berikan ha rg a 1 pada tiap -tiap edge  < x , y > u n tuk x >  y dan harg a  0  untuk x < y  2.  Aktifkan p r o s edur p r efix-su m  untuk me n ghilan g ka n h a rga p r efi k  tiap edge   3. For  j = 1 to all  edge , simp a n  stru ktur n o d e  ke array mu lai dari yang  harg a  Prefik-sum =0.   4.  Verifika si stru ktur no de.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA  ISSN:  1693-6 930                       Algoritm a  Untuk Mat c hing  Pada…… … ..(Slam et Santosa )   121 End.  Partisi pola string :  Input:  Ar ray  string  | Ep |  Outpu t :  Arra y hasil parti si pola stri ng  p    Begin   1. Set  k  = jumla h  variabel p a da | Ep |. Poto ng input array  string | Ep | menjadi  k +1.  2.  For j  =  1 to l ength  (| Ep |),  s e t  s t ring pada pos i s i  1..[v2 – 1]  k e   1 ,  posi s i  [v1 + 1] …[v2-1]  ke  2  da n set e ru snya, se hi ngga | Ep | =   1 v 1 2 v 2 … k v k k-1 …  3.  Simpan  ha sil  parti si p ada   array. Untu k  pola tree  pad a gam ba r2,  1 =  f , f , a , f    2 =  f , f  dan   1 =  f .  End.     Untu k  algo ritma  m a tching  secara  ke seluru han a d a l ah mempe r g una kan ketig a  buah  algoritm a  di a t as de ngan  m enamb ah p r o s ed ur  komp ar asi  string  unt uk tiap -tiap p a rtisi p o la st ri ng   dan m e mbu a t  tabel untu k  t i ap-tiap  komp ara s i d eng an  sub s trin g. Sel anjutnya a dal ah mel a kuka n   m a tching  u n tuk tia p -tiap  variab el yan g   muncul p ada   pola  strin g . Proses ini  den gan m uda h d apat   dilaksa n a k an  den gan  men j ejaki  obye k   string  | Es |, un tu k  tiap - t ia p p a r t is i  s t r i ng d a r i  po la   s t r i n g ,   baca po sisi  string |Ep| pad a tabel ke mu dian mela ku kan ko mpa r a s i  pada po si si variabel -vari a bel  pada |Es|.       5. KESIMPULAN     Untu k kepe rl uan a p likasi,  algo ritma y ang  kami  ra nca ng a dala h  sa ngat  bermanfaat,  karena  dap at dimanfaat kan  untuk me ng komputa s i ha mpir segal a  masal ah. Aka n  tetapi pema k ai   dituntut untu k  d apat m e nyusu n  tetap an ( rul e s ), sedetail m ung kin, b a h k an   kala u mu ng kin  samp ai de ng an level a k sio n  dan m e rum u skan m a sal ah yang  akan  disel e saikan  ked a lam b ent uk   fungsi - fung si untuk  p e mrog rama n stru ktu r  data tree.       DAF TA R PU STAK A   [1]  N.De rsho witz, JP. Joua nn aud,  JW. Kl o p ,  “ M ode Pr oblems in  Rewriting  Tec hnique ” ,,  Re sea r ch re p o rt of Comp uter  Scie nce, Report CS -R03 32, 1993.   [2]  N.De rsho witz, JP. Jouann aud,  “ Rewriti ng System ” , Handb oo k of Theoreti c al  Comp uter  Scien c e, No rt h-Hollan d , ch apter 6, pag e s  243 -32 0 , 19 90.  [3] J o s e ph  Jaja,   “ An Intr od uction  to P a rallel Algor ithms ” , Ad di son - Wesl ey  Publicin g   Comp any, USA, 1992.  [4] Herbert  Sc hildt,  “ The  Co mplete C Refer e nce ” ,  Osb o rn e M c .  Graw-Hill  3 d  Edition,  California, USA, 1995.  [5] Z.Galil,  “ Op timal Parallel Algorithms  for String  M a tching ” ,  Jurnal Inform ation and  Control, pp. 144-1 57, 198 5 .     Evaluation Warning : The document was created with Spire.PDF for Python.