ࡱ>  nWE*Lgb)PNG  IHDRg/sRGB pHYs+IDATx^lG zΌF$@$@$@$1JIyVZ1i(dcYQ)-J,YFtd4m|vB2+ƎBDq]~J}t|'fD$@$ p_.6 B hC L,%U.݋-5KU cP7_}&vN2ev +~` IHHH]؉Z*S["m[ezA;qtیGl0 %m G4e={ʒ]MvIHHH.zQKjw?{J5iAoN?.٪KC0uQ~lOY$@$@$@$e=jN|5I+?M^Z6o{̜Z|OWY>UU!k6)c{ΥhlDM +jԡmbj  p`F#vԙ UKV'T 3+OUʚKYKȻOVk15 }rD,2(l[O+py{6ԉsɟ j+F_Ũ\fdLV4bjԫآ'~)#p 6a?NZ݂xؽ#~lH5zsݝ`n3%|S(˛Ϭ!jxvW ؓU'T  ؚيZK2WM:N5U咥HlOԉ"y՘x->Y7qS:O݂oEuE) bXF~K}]>&d:-ScA#ڮ<2O٣~&fʜfvkRΌ( @Ac?|B8  /"Tg_=\n I$0䶗&-* yOA_'K \3?. ǫ;ViI2K@3tf\ pqW`<=QS $_3QK5k^{i/WJg Va%F/P7H%#6VҶb!G WO_OrDt,,䡁А8̜+'M&O+X'jqaknZ[l~T=׶]sa2_;hzC=\;aYx}=J@:EhDK|3 O%#gKZ7xqO/KGTi]}Ur?6qESi{yGwaS:#o܇ ۍ ouϲ\NW|ϲxYP@[^>Lk?Κ5;6% ۉ:FB+ψjrxͱ1bcdzj.bt݈O7eq4fFYW'1(^z\q6ǎފ} >sY:D=e惢{(8~EҰ>Dܖễ#Ǘ<muqSU'Q:Od.#q g[m=aU5~8¸D2#u:{1archNc.bu̶:Fэ\@7W*sKH+D,;uѹKwL[|Î#bƠ屮%VCH }C]CcPRj>S*?Ld ط a:7#7Jeyc^!dE̿Pb8uq]GcOCB3;o|KD)N_:B&[xm6ʍ`oE} X|͉(,]B6{FQjy\qW̟9="OS# &V&ڏ_18ܧ"a1.5PMO5#Z`5JcSeY򂃣Mlatw}7m3ÀJ ê:YmTA g_qeZz˵?ØAshE'9o4 $2܈3 .>@M?b!f^ܖ'jqDk'jrQlʊDS)Wj{9ڑ(<ۉU 75OQ<':- ~T\6 кF<64ڭFY}nBy~b8RF<`jFӈa Bbro)9T}\Y$vR¾jrE4BAc`CE< ~qyC253zG¦- 7b`>nvDyȰ"oPZudMCj?qt Sx8 GM$v@DLg j9`8ɧ 4ZsϿS5CU,+pe Ev=XtK}ų'.2gSr ֣MEF(K}OP'Ή1n(}j=p?U07k'-:B\G_@ $L۱˧s ml:8e/8K{0KE` /vN щ?Aݮu 8!Qc׏2yT~=2zKvAd#y n2܈gholS`Yw,#1\$םz{Nڝ!kvdty|5wz67v"KhZ*kQō4yY ƾNضn s"(3;yξ[FZcY;{k8~xX%6Bo4{dq{䬍ޫiFdc3 P;T{ 1~V32oid~zU?v\]1b6F;f/ 'O܍gϼqlXrcoa50q}k;RGzBjk+ N ϣY."h"̃"(.T)v`EpCd$\ݭоn*_|11-3.r;$κ~.loCDgQ&Eǚ=:O}CHL0FC`kmGw3n7½s.v 7'8fvAf$gt{v;[ۊ KVwZ, µ8"VR??0ד@c7b'pbvhcaauyl]KQ-DpV^SX0p0F~PFNA2Aa-hu;8aUͬ`P Vƿ;kv^\s3:^.^N(ܧn %x8-vdQ͙-jkbǚ!&$%(2o<[nT>!xT;Z}kT^ hE'oX.=5A;BtZ=7~9#O%w5(nho6b,,C8oz_&5$QifNjt0YkĠT `M [& u[5X~Y8EϜ lCdbI- }lA6#z[/)-k#?Ȍԓr'*yc. wճtgC:ؤ=>$̢5#.;$6-j7z鸍m]Y \o8~o飌#:h<(&k^^HQuhlVz; 3cbdbOrrs=Zc2:Q֬LFv7UwWvNDPqq#FZZ,KWQk{+zzbsG>:Y-tz{j0tuzMq[/ZA㱇n:sG+ u5nc[GqǛ[T3+0kio)ܪ3~0Z'k|F0lTkv]20U~h~= mf$bzRD}B^a1Wp TxXghN457D/"4&yY=H=ZWc..+LpaBA;{go Wm#( 8'\uvm?+aEcC\Vi_ y [Ɵ0nX'QRM.feC!ZEе~֑'=b,\F5r׏9]Tǟn\5z:I| 2X kٗйie9Bm{;в6p\c2ܿ[Øq O(T0#DWяĸ1:|t+*4tuPjnhKX4܀lJ+vs13*5uGR76g Gl򗢮tip}yr7DEe[Rdva. Ms#R3N#~qAUG{ڌDgf{"~g>'FHŌЀ%^;2p58!I #YcLZC*5g}ǿ:/loPUxӘX>ViblQ˺wV( ]b#seBvY )Xz#7 `˫7_3ʯFdD֎֟](Q #30MЌj[mƮPa);X*yBz╉]h>Edl,'ɓfc~tzk lzN0˹عfTJfA[1"6.W,AĞ ]]gvߨœN ,RFּm\1/"u'l`.8Y3Rr>+( $n^K8'vSzݷDr9QuZ:>hݿ1A $5?QGT @:*'kz7CXj/dOKXcǓr@}Lj{%/YZW-aڤ^МY<|Aax.|=&XhӏY:6?^ڪLV8Dh?ȷ\gt$zkz;$}9X$ nυQ6=g褺*Mh9aݯ^zBE.̊nq]Y:g]U,.7|} <ٸOyF(c”~mJo7R2ho9E4%> ]h(#6~_{id۳pF)Qz4oڞKo;~ ~>{ơw}E0עq{qY4vgQ5X>n[5jWYo6v܂[g.X'>JM?k ҆bg!̲eM5ʋ   @gPK> ӢmGx TȶlآF1yQoܛj뇩RWu(듁UcVK+P5"E]>6LG:XicCƱ}Btjc|:m凌}#% *wST rm lnT~˯#/~<^>Nh9L_"X͘ꪱU#X#{\4)Fh'_cM-+C5F(c뒸\C,U^kg3TXum>2tV' Mgz`<{Qw rģ$jyԫ+\2'/]Z2r6j Y-ͿpYimZ+iԎrNLfFsEzNA+=.&hc' _|}uq<9~ΒQ.Yh<#Cx8'Y55ǨDeG~o 襬xC-(qeZh6}^]1GYu}s_`YؑZ=4}8}rtZYrzѨZ)JI @ @CcUzT]PfO$@$@$@>8mKT>:=1NTqh1- 8/ƬTP/+?<^yLeҊT$@$@$@$cn,jCJiPS{sԖkc\)TfnGYPb    J k$Յ{JKr񉅑ӿ$@$@$^lL ((TCE1-Hߋc}r܎ŋ SPE'b/hEVFd,Y~ (;+XC& f#fᶬ݁xa׳w$5TNѱEe"-~_K쎽5"uwL:Р pz?ݑH=0tFWiP>AU>=爧: H!e_RvHHEc{tj6{bzsַ4rF\8׼oj<ֳQJEw"8۲ű*qGn,ͩ][7߫u;E#pCF}CWأW2|MwF^LuA ٺ}$@$@[/lL /UsO.7Ϡc:=':MIE!-3mFGn&*Oʲ&gBegѭ]'kTL=\Kpzs֝tHɘxcA  &o[fzc0jJF_>;Щ\z\ͧ=գөŋ5\׏zDR)[A]jvIƓ:uA,r%WUHF V뻨ە&{Á1]qvpXkJX)WL'bՑXg hl.NdN;i<~?qVkԿGDժE*#aoO?J j;r\p8rCh?jGylRXf}"HP<@mtyaܕ3cL9[IFqh-cK msGx.q7Q YW:f}ӭV' HU{ya|a,W-V\&e./Z+Ԙ+֔i1Vg llmbi{aO-[B%}XX"(4kGۑ͉>hw# e!nkwA_Ϧmd7f ;iEsڝVq_  $Ԗ5/vf9t=ڲxm32ƮTj_BOIM-PnwG)t#`Yv.xwaU}}vbvF#ё>YǬ}6bHd[i\w)4إ>_Xt}ò ּf!x'ʁz5QYl$0G\ݲ} ZQVJGR]0l(f~Y~^F?F GW2ݘk>Tf~34mQ-Q+ň5Pϡ9Jߎ\bNn-緻zFD Pw™崞QT8s}'ΖIHbXFe( VFvFN\3U<7-F<] f5ƨN$e1ecb0֘J*R52Y5>ώeFnw*g~K<*3wdB 6k $@$@$@$@Bz$yh$0sx]k5T"C+ @D}foӕՉ?6O9 %gdvdEL+Ucsܸ l-isWʴg޹rik%   B3>밳4l):ո\]av$@$@$@$@=K@RfaY,'Miq𛣻5Y; R`: fg:y@*ܳ|׷}CkD|{9'qxFhN'^jƍPqHHHM5;B )3! 'oI6MQ, Uc< l TY   h36y   șw.ͼ3`j(ũ^+}j8KμN)bnڌ(DNS4_4Jsdίc< xe>I";ލ5WNgrCK ;?4DՖw)ibcZmeâ ׸tϨj^5>SI\L5RZ.2dұ[itҭHCD!Vrmee²ley%YxvUo9o6Q5c؄}0\B2^3\X9hGޘZ鶪ҭ.T\zG w+Fm*_)KQ]#1oљG_r_E"WX7n]U.{ә]opjZY2{B\\xB9:ھJsWr9ʉsWmܪ1\nWȣf1wcC鏢'/ grfnW qCs?\]2V?_;jZ\aI!#s􉣩&c0 JhA>9:=3-bX唱<͍dg`J`b(P.T*%T}Ƈ{q*Gg sJAp7GL/={TVA9}bG$k^욱4gO 9xSF!3?o<\ƨ2hnOΡ"|^;6*q՘<"b_ʲ,߲0Wn{]թU8{g1kZVpNtOSyAff&}HZX8aX%ci޴aڧ;i) hL.bm|~W KKFQƊQn Keg0Ъ{( sJ&cohVu鹥ku>@. ;|,i&.u]Hƫbn pf΍lGO|rfREjP/,%sQqddc݈by8xVmBl.^s8%27j-,^:֩s籞yg*y%<ͭ!NA2c #d!.? 8̱'ek9HlvKyRYYz$u3YYwJCsrT6#{hxIcyyڶZ5/~{ՓzAF_/߬cvku חʳ_ ;ҚǪDlhJ? r{RvsY+$#oW+8~mY뎿cPrl{ n}O,No\kc܉N/|zCVdpQձ콿Rq~/u_4u'/buZf,F2 B ecy9Ͻ;~>[UA*\F,Ϸsո^9!mcz|>g~jX{jn_KbnI͙mv{6mPsܵ[guwFr\.] kuۋS\B|iՐk0jYHrǸ-ʂ<ݹZܢ)oV*^1G?Zܶ~ظ`V­_x\'٧;ҥ[KTåvҐ.wUGw%׶^_q{yY*l0!ߺgϮVWW{W1uu8^߲_,(ν.u'~gh/{߿{UcGCsLrlL~Et4n,?:.@.8gGNJ_/F/?_"ʘ2Vc.^d罟>7WGբZ:_?3*W\߿/\]l_--k}IU92yqȬ~ɐ%^_d<O0Pj6$㝪"brI㱓N/'Z6*0}f60_ nSFvXQۛC{y)ߘ=![]Ӵl DǯWOZ|2ۍ,0>{LjȨ~: 9s{vazsvU/S'̽Fvwi͸;wbW|wCwPjW6 -G.[+Ksv͏gkE6ƲpuAKwRS17~Z]2;j5+B3eWE&sj06KT&^dz/1vL}䟝}c?K9͏XM|@T=vGH5cƗO5uZ[5Z5K ˩7srJN+MCq#1Ȥu^Z!<~,;F ᔆ<~k˧ߑ vd,~lx)t2̥Jhhb Cke@8.1pKϔNNC2Q5ݞ%M2>}O_"f7t3VFES-ݨZ'0/l*[+Phڠ-lyv0k71 @4{'xCB,Z40ˍȈ[/.#XN"+Աᅟ͕ey %M"ہX{LAGBkF$:@hLJjKrP>S.̽wtg05`,QA/y 7wvlyå{\WT6)t]BYfj\m9W[rZ,-/ uZ5jEDeO}f}1Oim?& @uTQ˰>qqhFBS/<{x$w +gB\,ⱘ:xCHtʲe׀1󑣹cC_;~ۇ> PܽPqNJEFCsxLmOYxLl6?_Xg?'_g>&1-U. ToVs*xA4/_n>Eu7wւ+ju\Z,(}~ll`X-+kTʡCb9z䩑͎6sOdJnWa B}E@$RdĖã0zhױCIaFD΅rH?<)>-U߮tL$aQbŊkxDxŽB,R8rMpu5$-EcKu(݀d,>>Ĉ5Ǿ m,>q7 Lpiϰ_0ƪA2>af<$,#ڛБ,ADD~SW<A m|6HSxnV)}*m C/KKGfU_Lc #n7byk4 nUZ.\6ffSON-J)تV YGh _KrޥT j, jQp{W{NL CJUСAmIgEJRq1_~:Ɉ(=5/?)Xw~4YPaVJtq+DOKLc*_^-'E!d9[nD:.UC{nxdwF .<ꑫ~^-hR6Ӹ7c5_ZaE|GV7U1>epkXC~ek%lbm wû2dq'6#/O[1ʐjɦvVvÙ3f}u7FfRs<$2ڒ/C2bh;(%-  ʹ3r[- Q[(Ԭ⥫-F0193Oyqk8@,"N V4U*gb;Nn1 s_מ +=q(k*=zq!jb(5W !ǿ{haZKCmV"rR{a$̏k+&3@=}g1Y]^)]/b^)և NW|,7T22?,],Xl+dыǎ28cPV[nO E0&Ｑ%ѷ#J5.hM(+WFy=^dN dPvDj3#^grIq"_= )#HFHoV8b?'Onp厅msk0?h5"8fW%ܳYʵR&/UD$Sne FyIk`9@gwމWex /q4bD?xM@IqW\oDZV_pOk3dCĹF=1<.;咺02ACŸ1Hm۰;a_?qzDY2;sg+=)>K(-#·/>œ;df<܁U~sZT,߶ҍj/qAdbh<]*,234\ϞkhbpagOӧNQ6g,j|q̰QcQ9QQb6-2RdA:p`|69!h܃ٱ#r:СW;q<87>.+ΗF"U $ܞJ%5uμz+=h7}5?r07g o:BX H0un"MFd"q 1Xީ⭭xB#Hdk E°uH/@ˡ' C,hy- 4[> q%WTrrfo@jX/lm7goEH_`uPudh@EOU3#/Y +$1=ɕgifJ'OL^?M-N>'B;>Jsh ܮ*%!WqHF*~E8x]TlJI>.-@Ssdd]2j}1iwB'.YӯpzQʏ~hni+Dž1gsgޟ_xULn,#ӵU jbqT?1w &pn &HOxʈ;ŴXX})2#ߚT<*$(UpDڢ0>քp,^iLw 9kPqd#19B% AZ>ޱʧպd.#W͟dJe2#Ov'ĢKVA~*wPR;v2{E+~,V۸\Ft?uQ_{ tb]GKsXr!a'իׯ"ZR"Y7 Ɉ!~|F#z1~V{Ȏ@PhR2$b="V%qݏ@c:W⪘CU܃xx#0' 1ctqkt乳N9%a.j U3W" GN<2G8{Bk,[C}Prg<{C1D1Ox1FLW/V%8G=u(~nha"OwXdʎ\wIX>xZylؘ}w7uC33W''\js;۾4_ģhdt-m ~m|lָ8m1cH\^Z87? ŋZUR8wQUv7ʭtC{vXwn55 LGwn׫P/V `rW:N}y:Տ;vAAP׌G@auO4GS  Oɨay@Wඬ>SC}"FIFАQ}:XTT'*/O_ ?X-%e7Ơu:[1Ю[g_2=ڈ(YTv wƴQCJ*^ЏIjveѡ,B\#{3CP>;2BĆݽ^vt;҆q/-dvg1_V!ts6+G ᘳJWS?T׋+d% 2^Q`ǔJ5؁#]q]XHXS8i#JͭK+xd#oJÀ :UʽZ ,bA̪(^~cPW?T T)˔OS?ŗU:AELF(X\JZÊ }X(]^(߮qk%,ehHJX\5cd1Y[𾑱kӯ Sj /,. 充g?Oig\O&{YkigР/ n||Qc7/=cZ<589Wxb:ʁ)"zx5Lc, W(^óʁtÔ(UbQ:=eu_孋N2ύriA_mP63}g:_(/z8b\ e꒱9'>p`y5b z 8Et/UVj5)C\qRp+f&Cp0#_G}ӈaV!J<<1 FWfS)^}ͭ^Yq=k-Jw]vm\--U#k'sHg2,=SJ/.~źP*|P(ޚ~i}KGkYۺ+0Fړ=WEFCT[ "r6o1Ji3q>WjcoGP!aUY :1iS󧞾%GPqD߮F\(ǔYj-QI<ͩ}sF{Ɋ^`<*V|$"V7^lN|fSߟ-\Spׅ٣Fv>9㣘{t xɁĜf9htSP7j>1J)j`fP#xc>xQLxy#ȑ@<;%$DO&ѯ9Q.X?-,r+:mO&2F+x)h_?w?;EՇE_MU|[Dg4L[*-ξ797Kpj!]*]+C8NG8Jྮwb3a褖F.Ⱦ3/43"ZE2˾f}?7?+ҿ{UThhgVחKb߮ c;S.z"PR.Ҏ}}}7kW޾>{ }pCGX x?Oh?TGپ鈒*,?^Z#Ք؃gKv"o=h,+OyϕPZMkz۫k܇ ­5~[|e>s#]8Qg]2eGs-jƵ8ԯjo~Jpfm!c’:;ojƯƗRnԲ98JT%~#-U5ߺ)e޽TF_-50|yYWZ(GK, X~f3}ݷ~9/nVwf?bm/_e ~vCK,rQ缕ʱ;<"Ym֯bM0k_˿W_0rq#%}vuafg_Wcv8V[;wS/]ƾSbP(\z垿}F:z{/&ebU \ׯ+|/`TZ\1h8 n*_#_] fgk+~Yc+M_ߗwڞ͚swm^ }kv>휝ٞlO>kOJ?Y}L{pYsg׫֯V[]3Vk˫Ł= l޵Bh;_#,|E32N? Q:vgX#;&̓}81+/wijf^Dt*""XcG1n|6Sk{ֱ79ʷJ?}"mq^v٣_2w Gi]!Ynxӓo;zn5 lDmn񴝀g{obt65V0J6B'reO;OiL"d4ُ:G~'pJ~r"U;gfxCkKW~tt3)<|[AxE ƈFDѩxN1##!98VՏs{ z*]".$#޿꿌\ݗb Wk#.lOc?P#/i!GzDUK7* ! 1X+L,%#슱g=[jC5FuϷՖ*a97n^ð_~5Z t([BM`fC Ŗ |>cJbZ~V,x;0ac?fPojD˵鋧g/ϖj%qosSUcO*LTcV*<2lr[mZEPi B誱S,,!(ECO8l\j:e޴?XpzkvԮ=uj啹"]>{EkfFK^5/~tM0Q }&B 19,X% z?jDNm5%&³b'+ՏV#/T4;v k,BPoG{༘LؓoM`r6t&v;e>Ď!DWs]蘌c;/RRc,.VW#brFuZ D-[ԣJiLiOՈbq|;:XG.0WYS[/ݞ2d)<[2bTQZ_ͤO5q;Fz!͎nF5l]-;1َ4$Sxc8ֲ5h!@47Q ո9InRy.#q\S5O(Rh}31Q55I՘4U#U=1;ZS lBTRY$   HUcHiHHH6!;!o݄X-A*~:Sţ7BHY MNσ?}Lj% n&D`S )^::~зݕ A>_#c68 tUca3@c 0gB`iH#=B\HHHHHi+?xod Q_=Խ4Ĺ6Y   8qVʹGjK\<=F&J[KzT5N|ch#   HZUFqlZgޞ|~{3ty % 4JU茶 \5FͦR\1Ve?r7?$˿bBׯ_ɱ\ŝ2ʾ!!O5R(=2NG k;xm9ݚry%vLu ȴjZ]IH .FB_QT4(bTc=Jwy]T'lbzTk"5(h:R?pThHƅFY)?F<ᩋ./.n܁μX4M1a/3iVAZd`qB HH 6!bWEϨ6x52.jy\x.-~m3,\QC]5c'/5 m?JFbkDQ2%2SϘ{ "0ګW $#/"xF\˸;׮Eҍ90_".%;ip;ZHU~)iKhzZIj&8҅j#$Уd2n]MOgR}yZjggrύҭ --23_Y|VaP:~}pV-ʚ1GY\< \π( 9PPn3AULD$@=E=ݓ/dc/ wa aNJi_W%.X%u:_R?}t4 ^* rJJA{1퐒ƥdYyytnuyƺ0Y>wZs~ևHzŰ#=21Τ( Y9bWPn8:l+#YZ ԽcT2 l2B6ƽX߯!ey:^xG0 (i)QvF-JFd rִ_p|k뙗Ռ<Ÿ,CP1w-\Jъ?|uk؞@2ZPn},S V dEpLDxԞtr=>|\;Ga??TdhȠcTS8H裟oZ%#(,VV/6|tlqA'*& 5c\㡁: P6q3rKLvlΓX{D$b$VH61)!=x~1PLh+O.JSj=#/-t`@[m6Ykk-D5ϵ-r ܌Qu)V.u_޸>'^w蓹ϙN!=`\c nIF$@$@$ JmKaGzn.#KZKj{T>R /oPۡ 3Eܞ~nz -7N;Ӆ=T]fI$@$@[5Bf0SJ $ Aoߘ%0azU5Ƭh&'  -Xco9 UcjrcޯLzH$@$@$@$wJε3 `gY)n$@$@$@$F-{E(>E;ܽ+N<+2So%Ņw՗dk) 6+sۮ~RE{_-+T+%{R5wq"6COunldiQZˆ# FOS5TQ5Tul:gj4M2a2T c3Uct1EءMfT՞gA6J9\\ƀj<3Btm t{`1oLƶTuzu$_So=Ucqj8S^'^ĭ=NI$Hƴix{i6eث.'n)t{ݜ_[.t:z;_[7ap,`Ќf%4OPy pqp߂.E}7KX簞>_O3[&BeTo#܋\5DasNLqo [F.ގp~~Vok>EF]sfH7pZ#ULFP]_(}u\63 c6 c"Ԏc)jfݨ~8z}2ڤTꥉ+gb I5B#<8){Ňjat|L3d ZO@Ǵ=],}_HVe@+-vde5(bF[1wxma5TJm0W`F'n vz펗-p8809ȩg@8B>nMKi![z-Zܽu R,J3cEx D ,zu*ćTX @vnI;R8,)ʠ@mn.dʻ ;aO7!㉀ksn7W|$"S/\n^-fݯśdx?ˡ2M^eZ3 F2a f3f:c+eǙsgOլۓRyP" Ku9rl)s҉XAa-}탥[~:NKgk6_:WE=O (/0=sE"?ؗ۬ 4b贾e-GU("LX5?A͈@g=Me,bŢ/B,zQxyQtR(w}*W_V\oJU졎Oa:ݻmu&؁l=Nj0(wQ)x;qYF?PjzaeshGR */5vclN]H|a+vu׸Rrߐk_r hk[u_M\1QWJ+puW 5F.4n\/^ƌ{)#=3{f0F [⢂##hX'̵YrJƃ9fߙ_lhKWE@Qmt ~zd44"">/rI-ؽZ-snhq ݷ]|d\\!nj㝧 h%rb9umC-4Pl" }ԏ܄dDQ5Η&/ ۩чā|أAGgdt.'Vg_(z4myNB8bAq-M\F?۽cj ]JLBA2ʔ9DvmXdl9G|d߱grGٍs=e}0{ giCkcc$MD&_@2oe|1bvq]QHF/Յjܤ &IW_1'K޽ cMHm۶!ܱ3ԋX'%LM+zw&o2}ɛruK+wKl~mF6Xkw@ `ů2qlڪ,׺>w#tbzԅ嵧jY+GߩB'1wq?̡{\ncoƙ'>_Ղ09K-jq^J$93όSCGӻ存4|\c8õ7J'"ׇBhcjC#86į*v}tW8%FwOJ}uɈ^8\bR(%#~bx9R5X{p'Ͳk숚˽}T_p~յK, *xccX JU[^|_Խpk_vsR;rX[ٮMHh$~3t )e{AM\knwjdS:?O{> `2'u۪5}m-:+T92`"5cr!3f[Dkِ?a+З][6N_O\C:O\G O?3בֿ>P)sQɑ)cT}b~P/=~&QcE3x$'xJep<+xK֋Sau݋ROO=UfiG㏖bYc1WprãgOU>Z8X񫟯+{5rnкI!hb>jjٟ>ӌh?[n Qg)OnoƍCQ g\5ʕqHƧ<)1#PֺMNe 98m&0qqz%i9'@9M 6P,,k\K}dbQmXkD* 7w#3@%[SDqJ:gxCr GiBCh2@]YvЮ>2CDt|smT-zdՖgN}=b1FpF܂=ԘvŠczI CǪ֞bd].Ʀ^M5Rx]JJjJآ+R2bji"< h\3ݳ ۺ>hO7Uߐ21NýVGH\}tRԋR>♤4:\W:͝ \5bG<挸)LX)TԈ Aj̕=pc`!蜒dB8"(S"?za6˻s.B-ڳqȮ|\Kkbho 0~LX;Zr jt{quQY{q1v,܀(p3r.TzݍJ 5Hda{<Q8Q:0ŠG~ɬU.谮; b3G^,^^SȊ7n}^y MicOOf^Oggg|盌i$U|k.5 QMERp bZ%"^=~vW$їKxES6fN=3L2`vR߉CBD7/bP#i;OΞyэ~1Q_1 ^!zĪIR,ĚT-5J<}4-yKcn\Z<\ZZ=-(ŲRׅ>őԷ}e++}@|McߨB4EnGE#J j'aEhD9MZp&i,].&jfJaj>Ly_;oF0\F|-Pc\ImIgGѶD2e@Ƿ3X{ؤYQ=`O糠 u A,os\0+t?}N\RXUPi@L=.z&VJG⵫x`SI%X8?i^/mf/yv#.TV+415ߵ=i kdlŸ(>w/MI3o)xYwT㉗&'s"x)qIsؚ{#gFL~S5jUM Q5ɈjVjE0Eɥ)S2*%٭Fk?Ɉq_*_BdjVNQƶhƷb D%HGN}#ΤL~a z3*o[ATvLQ5yqtFu&8irGYI.ֽ}56"IkE;n(w69 x/ 8Fd&bnEٝF32e[TG'wt0\U`uh%ljIڳ8wٖ.{V1r.*fw畐/~zǍaP%H%!w%ut9ӡP}bf kV".{NkJHHHH-5#HaMXfv3>l7SY--{-B$@$@$@$kUc+٫e[:ў>^;C$@$@$@#`ZB#J:R,!$ c*D$@$@$@]$j(LU2[UcY @ رƺL%a~Cu=HbV$@$@$@$E_bQ.넣Djb1k   A 8I3Us"   pX_:iǽװFkn1w   hXQ.}ƱgWv;Xc* @7 ?c#&_<)f 􎪱ǼIHHHyi&~;ZŠHHHH@μ#Y[~/Xq̚HHH:G``7fW2W]^E32Ru꩹K x7۶mHHHܽ{|H}jJb =/*#&c*m2[ rYF#JQ5F4$@$@$TJuPF_jZb-Zz>#A5RHV׸ZB$@$@$@*5x(0>:Ic5 kV"jd"   -AZ3mR\)3^),v5n ,$ lpzVv``=A#DOR|ٜxt(x > D& Ģco010T13! ldLTS| Hո+ @Gtwv]w#LH Uc8#  LS2nϲ P5U hn<0HAMHH@wE[wsdQA5 D"])#5&zkzu @N:%@ոu%' Om͝ jd  X#])y$@0F  :NÀB 4qxs!MO b4+ں;%i,H[ 4 ƞ:C$@$@$@=JG+n @Oj3$@$@$@$УWw У."  x̐HHu݁v}h@  St]otjΊ)IH`f}5&g#o"Bո*> @t]3uׁކIh;ƶ#f$@$Ѓ@ws@H (H6k:7UKbamی&-uTP罉B- D @dm=2$&$^$jLD(#M.Dhe#QDD$@$@$@kzX5njj&(je@RZ   ^U4(k֝ЊsۃdveV$@$@$yQq†~uغ|p*[&? ' 搌C#ƪ8=q$cܽZ6͊; ! Tc2"%7%ëeI]CMJ8RFO66ǜ]u݁v}h@B(]RT MDǴNK6c9W%Fpb/MD(`D7@EG`[#mnoI-PN7RW5η`*DiBw.>*HOh9+":i9$XnZ6,ں[:# #Ьje_6s%j=B]$J?w-Z\7i:Hi+JfV$fUcb ɋ7C>#ˉTkhh.P]!LIhn_́BYը.ωh-:kP97#GzBLcUY\a\Fs XEcbP+rYXGYH$""h%E[w˾a 'AHʦjg,f$@ոke" [Yul$ P5nJdHH ʦ{a"yT=_EtH E[w˞D U#B.$ aJ'H }cV=ڣ HifaU.&gռjL}Z! Hj1 5Tl $@$yP2ndIHP5^# hM i*Cߝ:ܓ%@k$&TmK$@$Q2vwBagBh:Ay< Љy@([F],[#мjl-_M$@$ Jd8v %cgy3dP5&ÑVHH+(L)[ݻE[/ JU؟ԙg2H+$@$aHv`n1`n|IHP2nAɸk>kd{   dl;bf~TgHH6Jƭ]T.Y CP; VΝϼJxiHHH6 MR, B xe38qLH(ܛp@P5v<% MH[9MؘX#@{uBHH`cʢeߘ^o<T1 ʦ{6Գ,xj{'b[HP5l1 0hn7LU㦨FHGw:s&.jtfI$@@wE[wsG%v݁MӐX AqCT$ ^$]){Eҧ6jl3`' MJS2nFbjd! MS2n.aj,5r @ WWG'DLfmʽ bzMTY/HHHzUco!   $@؛BHHHHP5V}   MTY/l۶ϛztHH ՈK{Im(3Y"Q7\vIS@-bL\IAU KT"Fy˭t*`slC`ǜ;p͝Mw?0n#ъ2j")ԝۓ.57Uꔡ˭dSf: ȡf5>uEK*zP)R+nWe-ֻGu~l(6QvI0MwsO 4En֭Rc~VtF{sn%뢡9H@x*r`catgҺ?2q,U^^,18ʮ ֝ʹNHi5_%#Ɓ=[$-}<-8[R4c%vϬFZR2JJ+ͭlE"/ԁ(ȻP2#FO׊ܣ`$װ4*sYBw 엣_ d^bO0&jxqhbXcD)J:Oʂ'XarEƺ.䪘A˪Ÿ(4CừF$ _ͪhJw{n"gDЫUoɞEln'}ȪHH/B@{gU}zEk@s1.)܄:Daގ4~yyBg2̥eb5 H]5KtZ]@;8.uwtx>L= W_ݔwKLǭY<;DM4T؄qD1wKp7`,~:gAh=[?!HzKЎQ$u='Vvoq߈Z%2&4K@cǧq{VvǎgPap XzK&F"gys0%߯ Q|8N^QDp &kQ~U;dYPgB 8f^'V[-퇞jsb5 8ty\"/WO,nAficRlIS/'?J]#:±NSxVzGїX6X >_{(XU )+(FZKBc|,;Al v9y8  }3tbJ6*5C=xuNrwyQ;r& Yrk$SR;(Mɭ.xs**P5y͈f0t/?EHg5y6BϖU[~՛r޳:H:tI0qATz6 GzVG \QjYFgrݲw̗%FyrT~7:ҸwqXHev>7i$JYU+"%'nܭWPq"l@:ѓXSni+޾:e0Ucgv$@$@$@$@!@̅H`m# =mm+&4K'@y̑"}V,ݾY tUc3?ؚ;o0d:u͒@ P5v9s$ u(bYqH4B!@̅HKQmucVI-6j k Ѹ7qӷNa-z^2L\Wap17J THQ J6D_.縻0} P2v @\D5c=Z\"=㦏gb}8G(1{_ļ `P͐6yg@YdŪdh[Oxo%쌵oT\6MS#%0nDu].(Oyפ-ϕѭj;a@IC]mRզJtRNĂs,$dLct1-B`F9q&vM b0p(i"6h)az_wxW#JFGl*h֯^׏~DCXgs$i-h֯uݯ%j j_w}Ж)7tmq7jt\t#*!OU]'Ԏna'y^?=~: rbje߈x2ǻ1tt^ow$d 跂#f縵WMELO*xzKIUc#>S{v"ݻ诡s*) n;O2:*z󛃒ۦ2HHH=)ݪF߮ԏL~r&Ozz%7yf')ih+ZLon܄?8^' l]TuCq*߰H_J%7>t?ɳ/ɽ1Ty?,Xغ%KN$@$@=I1^8y;+Id?yxe[Y( tb2 @s,j*b[gI$_lXDq 6HHHbj; $@ո+E&   c#$@$@$@$ P5nJgIHHH 6T6.$@$@$@I}$q-Ǝ{ IHHHC;ܙ+ l,T- t@K.   $tG0WC%'#%   7pu   ƎfF$@$@$@$ P5nʣ$@$@$@$1TC͌HHHH`jGIHHHc; &@ո+ @ta}!W6VHo1:j$   Kq=KN$@$@$@ l32f&eSsNn3&[gJ    8X@.Z%J]ȿb"~[FlN~T<:6SmqlZ0˱Ucmԁ3     R;r={ϔ$@$@$@$@@ X#5BU   uT^CHHHzUc/}    ^'@5DHHHHP5B-   uT^CHHHzUc/}    ^'@5DHHHHP5B-   uT^CHHHzUc/}    ^'@5DHHHH ږ_,}  Uc"@#$@$@$@$ P5n fHHHH T`   7yx$@$@$@$D0 lrTY<   HUc"iHHH69M^, $B14B$@$@$@U&`HHH!@՘F!   MNqW0G$@$@$@jL# &'@ո+#   DP5&FHHHH`j @"H#$@$@$@$ VۼzIAG̱;gtőƍ y9,ba "qVglÙ_9?4[%'s[)ݦ2_k9bzbRqEɢ4Hپlwl0ir>^FT)Z~i#OS-Zke0qlYWo;x3Y3 yϧ06g޽[V5uA 8OdH-?fX(Pg=_ay)`C#Go?9__?&WB65v$~4{ҫ쳾Wįg>,G,g(H/B@X1#O~wT~ef OduWDc*Աg#7 H2p+AA&͡d:ænDF='wxx6p&Sv28*n 8K~EÉCOQUR,>B# :rZ_W+r ޭ)Xcb=Ԟ/@5zu9N(G.8/S ܖop/]+FP"Yslq a0Y{ Bt\*sbrioV+5-<=>rlM ͏To$b-8z)VFJ&vd:ænDHݵPc3QwVy~'Pe#ܥ/(pB}I2J4K?hNQj/Qp8@G(o,yBz*'˭>^S DY?%N 9kг|+b^>PTnb\zYCӡASR;DcU{G2!jT9,$`*;"xxs`CdT'oDJ$4ReVQCN~aRG?gbTi1v(e8AVd #)rE22wAP)n5˫Xk߈Ћ_ h0n`VV*H:qa8b/-D9FˁQ?WDlEn-(FH#6{Ora6Q( iH :R2pqUH]C}LG'LNJ.t?:gWľ$"Ki'b8?-cQDY#E3~L g/\ =@}>l~L0 n~;EL\Xx6.cnM{#.URe^ 9DXډoDJ-ܝtM5ǑcL]䍚,[C%!VeiH @"q;2Ru꩹K x7a$07}TB羼&UzE$@$@@V1/ ŢoT̶Q˸S6n-f47ǿ}]蛣, @' P5vv:gqf@$@$@$P5n*=x-ʝw ´񐞐 xjT o>x؉&FT cu{7:C$@$@$@̓HHHH Uc8#    jd    '@Έ)HHHHHHHH P53b     F    pTጘHHHHmHHHH Uc8#    jd    '@Έ)HHHHHHHH P53b     F    pTጘHHHHmHHHH Uc8#    jd    '@Έ)HHHHHHHH P53b     TcR9qXًë s؈Mx[V|٧wδb ;nn%m܅HHHB .~8lM'&^ R?||3DV|gܝHHHVA ]ȣb`R威95y~'Shxs(#T`lXTS| $FLM |t[+bj$a1Q9X ٙp[,;~{$@$@$@$k|f[U?}u7K7i(0b;&Ċ*[@i]-^H&L!N&F*{bLBjՑ>7~aV# PH#a ;i_YE)Ӑ lejyNTWr[_5@"}U-nԩkLi1AbP-j&.0(`^ l>] 4J"8poۦwAzsi7#w$   v=ۓrt qB!tV־=bvK$@$@$@hu @\:n HHHHGtGL7HHHHjKIHHH`+j܊2 @\UfgK;E#oX{4@ ], We;Za0N\HCZj✀r!5RWeϸܮ'!rW k':$ .ت-(i9[5z&^.2?=ԘMJ*"^ (|I2;O$@$@1 y` UM&SDk~a/!t;JxME@rj'}P;|CBx7ɢ'hCZP{P;"T.ṲW)j׫{d|aD=@YNXA+E:=_}eq0@s`v/gweUqT#L@;ʟ2JFFRHՑLZ@7)Vϲ(خ$#z詒ѧJ;ꉞ~g*g2uCFA2,΁"ϲzfeJ6"6K=ehCcPeWd|ݣJB HHD jHT5T#pa;=.R.`q RrGd!'xJ]3J%w"#b* .oJ0 %ǣi"bD7؏/tOBT=ϊKJR9^JQ3hEm:, @tDqٓWh\ZzHUq2!aD_Fo<RbG^)]A*zD=1xqM#j9THkD7aNG#QO7+sWw2h2z,JULFi~Fd!YʙH:@TT6p_,eO>b!R~bɐFPcڂ_U|E^t=Uc՟ԈW(7P.ZzwME͏i h$Xu(:̍"Ryfddsm]5,pG[3X5iPΌ̂HHMk1ß}h* Ρ0k#=x4J :zH 2-9dblGEF52Xd *;ߣ.=ս9FՂrԦzs[s Tr1r[*3@9Fg3"B=^Jɠ, ,D# "$C};kEF=ox' "Fy QFwJE^xWP]d2W,YGp)eO* zqE3Q^v>^W&!D2 L^K?P"< (r[6 \nc<J: &BTQډ- wu*st LTu M~SMF6 t@"qx&2Ru꩹K x7LTv$>xMo"?|\/DnYo"3IAcMpO  jϬ[ÿ)>?_G RmqlZ0ˉטt鶢=5WۊSvZo#t7( &L>F(7aH$@$`T= /r]oOʩ!V ‰N0˺iuµl.gͰ w7  n`u73O    Pw6"   M=[Yz   F1'"   Mqk?KO$@$@$@P5FT$@$@$@$ P5ngIHHH hHHH6ƭ],= D#@S &@ո럥'   hqb*   j6HHHH cHHHHjd#    '@Έ)HHHHHHHH P53b     F    pTጘHHHHmHHHH Uc8#    jd    '@Έ)HHHHWO O?6{8v&ڙ $Фj#\ Τ4Ăk*S{L$|}GJ~L2qON"̉t T‚nG|7Ҡ)MDW2>eʙgd[O3fϦUPV9\lf2< OB$@$@$@$jă/jz G|@ l/Od 2]غ@D7%<4"SCa_7-#sDmT0{tS&n]]J܁  uZx jxGr x9)w?oW$ĭP &UrQL|Օb$·IHH6j&L=x`' DBב.|;c19.)#  D`#*e CSS#HHH6j,|RPt0؎:(ikŀOj\Ry٧1ѽOg97RxR*6kLR";qݟuUn;q*7x4j{K8DF7Ȕ$@$@$dGnU59w{LSg0~=3atۥ4;Vgm#rR&-~nz+ >ܖg36MƑU=FБLOyfŦLY|6&6gF/tHH$jrZ_W+r ޭ,Z'V?i2RPTj(m-Upw{Vv #fuq?; kܓߣNTpa3N*rU/EWߨgB% SOOFO, CїKOgYRrGS8 ~љ8R!OOߤԋM3$@$@&Q3`tT.duHW&`Aӱg G/TQDwS)يv++TZ)ہ6IH6 Մ'ߙGdUJ:lW%M@2.8wA8 b^~n_4lxnFQF XY]t~)| uiHHzQZi oh7~sӦiA Aب6>db3YxnY{}+eG1RwQgSkO!.W*utO+ՠFrX0(s u^)sYmQMno{W$@$@$&i6Q5\B^! c~X;c 0y7K7XIL3xN+^V @0=Խɷ'e/*&. '^:bII`#zbeqw  AT=X)^rMX| "^;irDiHH'@<;I$@$@$@[U֩kHHH'@<;I$@$@$@[U֩kHHH'T#޿Oˇ1!ڢ 6#==}P^cˣՒ#Fit\Q\ṵH({D >#QF86l+Z& E`FoyKP*K˜X|b8\V/^]ϻ_8wQ \3AOq;įM 1Q4MLCcKo=obwgRL$#.ngFBppL6ĘHH{7Yػ-)G:n#8HoXmZh1Y7hHH`H=Գ ՘۝_cz`A|*?=+3OHͷߜ|gx(ž{GusFi")w7? Un;:U U܋RFPsMG}G=Sς;.Jȯ˥R(!  ̢ԷS7o!H(iFba+>\8ePBJb,nSJLsSXFc,`C'gaEpW[TcUVvX6] )=B9g QQphȟbYQ\>7 $NZ-ܩוꊽBw뫖H_JxbƮ)#uj#kKv=_,`d)9z+J6UyEF]}$~1p!,˚zow8"GyB{XDn_UYrUϔz4^ ?#ҕԡڳ= (OPRzV]{63n$ h-7b(!ܗs&.G=r]%V3`g%?xZQzvTߨ;ynrGK搏ם3]fלqY;~G_s6C90 @lqzEtﶸ  >e qGHID#٢GPCyq97;xc=C( 8ӏ x/` @\ CrX$pVb $؋#rpA> QB֐C $X +`,@_OVUWW驙OӬz~>UnUuO@5 FY[CT n 9Q{_/{j5KX:/WbÍ||L+|뛌MShV(4sIAxgOJZ"uevHQYaei^m7rvqT#x;BdcrʔV)-g  0 )F_FQSScdhuVw)y Ly r j"@Y57) o^'2ڧoxϜ69lR䧪"UD.3ur㏏« whF|Eq\UuiN6-*`T^>$:xs lAԥ`(**"Vf@3YQbY5.NdEy@A)= 3/$WcB8!@ ] 4LMJ t#Oo' @ jlR|(Cq;@oMH Tc" E @SN $B՘HC& @S8 @HL5n?G@z?\DZΝ?綈gE6٤o44Ky*r:KuU$ҊʌaTMśN_j)9/p T,j&e\+putc7rRF'  !j2| t9|D?R:p'31jt-cM=?y-c~P3&5w9k=tEԕ|5+ڪYҹT ULeUZc PFc3뢞zb` dw=p;R%6kk4qU͗f@JQ `\NUyBE-gbdE:&2W,dPzzǐ~fK(ѵXc[V{7ƴR+3t9vi!J2>eJBXp)Fi*V?^$<#IVo^ē'D>|aEM-eP7ĴLO׀Vϣ5m1f3yM[z?ĘˆI2L 1(kR?eY*z3*%=IYVcza\0'*;UnAM+4o̕)wYfc\MS?`M_5c𶈗ITƢ< !jEX7_~4|pA) ?m@ap9PdFX }b*/8k[ز(S=lz<+Ww[@ Du/#o^ر\څ˜֚6Sé^ X]ܴ6z@iM[.T]sصVUִo47`4aEujMXlZkv*M{x5]KA$@lZ|xep+Wi'YI^H7XI Y-JIi7߲[UW7Tw{4[X˳hޓin*"J`e4 ZK]b||#u@(f6mDsm TO^꒵Q4eU2~5S*wrWLx'4souvVf䦰+]g(fI@3+ܶsnޣFbewul&6ֱ2r.6E jHz{:e_\G;jwT=y6*- hxuE;iӅc.Tj&*6p/jYmGY?-DF+.R3_Ӿlx6LhƬ $q&HtEjԷF}LU1C,^Sۤ5x%e?̷]Wd`r4Ⱦbd)]Sdl;mUནˁ,>R{anS"3 `Q~nGJ+Sc3V]~\Ɵwuo1|\"?{跢u<|pjb6Ȃ9YQ LJ#II1{kᬒn݀u_aބkp. Z)/z9h<2J-uX䢒Me$~="wEb]]E!шZi ^UVq7hFi]Z ]|@FP!! WMBWȑ&榮|hx'j<&;tP%UST~ nU [IF%4;ߚL4W ޔb0ekY{QRL LHjb Z{S>cQu2`@G3ou~xz#a*m5[u8Y7v)إU/j;w.i +*&MD9Ztw3ϢbGtY,03n] %Ƹ+mbn-1+Jw= ʪQϑeMOhs[̕A(2+j@Z8`o;|bRU:NQfIe*-XvL $ZC,tn0&hem~҅nP#׆o[`E_2oIKEzӕ,Vx4>kM[xᘋ[?MzMP c[ɍH+ZMloq `[FЦ'1>!ʪQ͑R |dL]{{M)e`nET-5uQ$Ӛ+ƂNJCvc+ebd٩vEl-Gq lm,ڎktQ{`zyMrc {8孓cײ.WN'l1lא\.`tXYfVvχ D6Mv30vfGoe1-I7NB` TV Ȉ!%\KR@CƆgz̒Yϡz|uuN)E5=b"7{OU hPsyM~1њE|b! qd!@@Mƚ@qd!@@Mƚ@qd!@@Mƚ@qd!@@MKluyvcWy.q+A Lٹ'ǽ`t;5?Kեcfvgjܹ5d @ P3kB5@ 2ȺƎZ @ )Ƥ`!@@GP- @H1"X@ TcGq @"jL tDxB j. @@5v @ )Ƥ`!@@GP- @H1"X@ TcGq @"jL tDxB j. @@5v @ )Ƥ`!@@GP- @H@{IEL @'X G՘^1 @>T G՘^1 @>T G՘^1 @>T G՘^1 @>T G ո]0[zĴ؉KF4Mxx@,ɨƏ>dM4uǴtV/2 @ 9ɨIU3f/c*#T/0]kt@f@bq1Ռ€ @` $2Es-ZinIu=Xdp|oZ:$ rH$%!@UxpxSHKY*WI~͓2AӚF!˻7G-vaTe76SC" +,^Ȫ6ujO@tE1nnfwQ1f qP @՘[ye狧i&/^wkٽrx싏$>aB L@h/' @I(wQ6ï '  @ @`_778] Զkev˞dz!g @M -Wt$ Mc;jz9k;(W}7qCj!9 Ǩ/2ۤ-@ /jz@Q P&czkOWWMIH{E4 @<H }QVX/P?_1moe3_Ԇ F`>wlVCj!wDPO|sW5n}2㯵~]9_P*qB|s7tD  @`A XT{vyW7d1Cވr@!@dD U o\x\޶;nlۗ~~=UQ (??}+V"Dې@jzh;G̑|lqٗO< ԏ6`><|$B &;W1;X\ʖ|Hqb}$GDzv~xF<#ڹ|~s͝;W[K|qY^3>2WV>9Tpd1v2 >#oŢHơX~]w-}?.KjyՎ~[>5F8 ,&hxRt%㙥 7zMsnQ27}bb*IDATݍˇk.~{W;+oo-xQ++voYn;{<YLEȋ[Ir?*/oE(|uz@m*.-;2F-e0=7-80"벻T;428},1pO8$ _8\^5.ez˽+ܯ">H;~xw}mJڿor7?do @@-yz쁬 WK7Hj @i8TofRQ#KINҖ;;0 9G[-B$/ȃƫHgE !UVu NURYUO@8*V]"-TyF5eOAt$t M=TI NKҭIjs*y ױ,y؆[Iխ=uJ۠K'#Eq 3((cSSߴ NEQk/-(c|VuXZ%1X˅ ]Kʅɭ=mh )%{XGjcȾhJl\m3S8H4wm<֣>)KO9#u4!/XſU8ZʓO9Ttq`os8UnH"ma dS^p*pF9e k]Px)Z} .k Ρsx`.#18 8h ^Y0_ ̸ ;j F0`[]0˅B{["5:E<+CM?Е2`]^(ą^y#B|n\0"!FT7@HjoB7,)Oe|R!p\Ň#ews}.OFA0/\qs?tYSܼP^g8-˜wq3fyc7|<~e5WOl龇/:9lvYNw'$ u߈~ku_M=->M/TwjDwjFEsI+(]Gau=uTp,#wgaE`>4g tS{F O<}\@~,4<Ξ`-ON-ߚooo ghଷ{ul<Vwe9z@|F+<hV jw` k*XR =/T%45OpNal ۓpxπϬKhi]|:0r{38w 8Pqn>[}r(8Kf |$b -M:嘳~n{tEcv2d:o)֣w֧׫/.Oqu\v}[OړI;yFA冞 :R̎#_XKTdr[ Yĉdn03-yfqAq`bKU>0ۆn'>/d$׷"Kw_~~up>Ŗ#JghM-NplzO„[b6vaK0T͠3Cd_ahf9옛2hߙW~Eްc'ۣdcƙsp>q~.c7IENDB`zaB]"I<9k_( E(x/ / 0DDArialngs 3sivattx: 0DTahomags 3sivattx: 0" DTimes New Romanttx: 00DWingdingsRomanttx: 0@DComic Sans MSnttx: 0BPDWingdings 2Snttx: 0`DCourier NewSnttx: 01pDSymbol NewSnttx: 0DMonotype Sortsttx: 0DMonotype Corsivatx: 0BDWingdings 3sivatx: 0 A0.  @n?" dd@  @@`` .<% C=: &%'(2)Cf A 3          8  -  2$ #6     )5  ' && 1E!   -    t P   rP ) )   (/,.+i{ !()$&\#' '-*#$= 21l ! > / /._$b$E*Lgb)_$b$mr xUA _r$B]"I<9k_i 0AA 33f3@8| ʚ;ʚ;g4BdBd$&x: 0Fppp@  <4dddd@ 0t<4BdBd@ 0t& 0___PPT10 ppj___PPT9LDR~P*T?Z% FPaolo Ferragina, Universit di PisaO  =*7On Compression and Indexing: two sides of the same coin 8$ ?Paolo Ferragina Dipartimento di Informatica, Universit di Pisa"@0-  ->What do we mean by  Indexing ? HDWhat do we mean by  Compression ?##"I6Compression and Indexing: Two sides of the same coin !*76JOur journey, today...0=The Suffix Array [BaezaYates-Gonnet, 87 and Manber-Myers, 90]>- =>Prop 1. All suffixes in SUF(T) having prefix P are contiguous:?Z63>1,Searching in Suffix Array [Manber-Myers, 90]- ,4&The Burrows-Wheeler Transform (1994)' &7)Why L is so interesting for compression ?**)8Suffix Array vs. BW-transform9:A compressed index [Ferragina-Manzini, IEEE Focs 2000](;$:5:A useful tool: L F mapping4 =*Substring search in T (Count occurrences)8+*CMany details are missing... ( M>What do we mean by  boosting ?  #>What do we mean by  boosting ? The emprirical entropy H0Hn *!"NThe empirical entropy Hk >n *!"Use BWT to approximate HkZn  (What are the pieces of BWT to compress ?:)n" (PFinding the  best pieces to compress...)))R2A compression booster [Ferragina-Manzini, SODA 04]3! xLet A be the compressor we wish to boost Let bwt(T)=t1, & , tr be the partition induced by the leaf cover L, and let us define cost(L,A)="j |A(tj)| Goal: Find the leaf cover L* of minimum cost It suffices a post-order visit of the suffix tree, hence linear time We have: Cost(L*, A) d" Cost(Lk, A) Hk(T), "k) xk . ZG0 40 C'3'CG3O3G3O3,CG3 #  C#G3G3G3G3G3G3'3/3'3'3'3'3/3'3        3  3V    f          3  3  3    3  3  3  3  3      ' . P^May we close  the mutual reinforcement cycle ? 0/0The Wavelet Tree [Grossi-Gupta-Vitter, Soda 03] Using the WT within each piece of the optimal BWT-partition, we get: A compressed index that scales well with the alphabet size Reduce the compression problem to achieve H0 on binary stringsL1 xE0 xU; <?0 xC CAAG 9-3*33330(A historical perspective:Shannon showed a  narrower result for a stationary ergodic S Idea: Compress groups of k chars in the string T Result: Compress ratio the entropy of S, for k Various limitations It works for a source S It must modify A s structure, because of the alphabet change For a given string T, the best k is found by trying k=0,1,& ,|T| W(|T|2) time slowdown k is eventually fixed and this is not an optimal choice !>15xU@:CGCE3E3AE3A E3A ACG3CG3 333G3 C  C  C ccc CcCC CCCC C C  C  K  C  C 9 C 4cZHow do we find the  best partition (i.e. k) 4.$.> Approximate via MTF [Burrows-Wheeler,  94] MTF is efficient in practice [bzip2] Theory and practice showed that we can aim for more ! Use Dynamic Programming [Giancarlo-Sciortino, CPM  03] It finds the optimal partition Very slow, the time complexity is cubic in |T|4x'Jxf7Lx3x=x Jxf0Lx3xC G3G3CCGCG37C C CG3G3G3OC [OExample: not one knEWord-based compressed indexF The WFM-index 6The BW-Trasform is invertibleS/The Wavelet Tree [Grossi-Gupta-Vitter, Soda 03]00B$   0` 3Wo+ff3̙` 33f33̙3` ! <yxG`wglZff` yE[AQpff3k` 31m̙3f` 3333̙3` O~̙Zƺ` ffff̙` ǵfZƺ` fff3fZ̙>?" dd@"?nZd@`K `7@d` n?" dd@   @@``PR    @ ` `(p>> @ B(    <."  H0Z }` # "<ij  6i."}` H0B  s *DjJ"`,$D  0  6,l. "7Wj . T Click to edit Master title style! !$  0Xn. " . RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S   0-. #" `qy  . ^* `B   s *D"  H  0޽h ? fff3fZ̙___PPT10i. 3l+D=' -= @B + Presentazione[   0   P[ (  T   "  6l|-"P  H0x\   "  <\-"p H0  <_- "0 `s H0hB  s *Dp" p \ Pp  "Pp   6e-"pPp H0B   s *D"p,$ 0   6h- "`@ - T Click to edit Master title style! !   6j- " `@  - W#Click to edit Master subtitle style$ $   0lo- #" `b? - \*   0V- #" ``Aa  - Z*   0L[- #" ``` - Z* H  0޽h ? fff3fZ̙80___PPT10. 3l 0 ,(    Ntt B   r* p88pp   NLtt  wB  t* p88ppd  c $ ?pU  8  N`~tt  K  RClick to edit Master text styles Second level Third level Fourth level Fifth level!    S  Ttt .   r* p88pp  Ttt  w.  t* p88ppH  0rllC ? 3380___PPT10.>pp `(     NՀtt B   v* p88pp  Ntt  wB  x* p88pp  TLtt .   v* p88pp  Ttt  w.  x* p88ppH  0rllC ? 3380___PPT10. 0  0(  x  c $p `@  x  c $r  `@  H  0޽h ? 33___PPT10i.bP+D=' -= @B +2/  0L0 (  ~  s *(   Hz P"    ,$@ 08  T 1?v"  BLinguistic or tokenizable text Raw sequence of characters or bytes00 x$0 CB~  N |?PP EF P`  M?  T 1?P`kG g Types of data 0 3   T, 1?P  hTypes of query 0 3z P     ,$@ 0    T 1?Pt  ~&Word-based query Character-based query'0 n'&~   N |?P %   TL 1?c  ] ,$ 0 mTwo indexing approaches :"0 3(   T 1?s KS ,$ 0 p Word-based indexes, here a notion of  word must be devised ! Inverted files, Signature files, Bitmaps.l?1 + x,*j  T 1? s,$ 0 6~ Full-text indexes, no constraint on text and queries ! Suffix Array, Suffix tree, String B-tree [Ferragina-Grossi, JACM 99].~81 G x&)~z 0p  _,$D 0  Z$G{HrQ1?0p J 0    TD 1?p`h +DNA sequences Audio-video files Executables",0 ,+kz      bx ,$D 0  ZxGH)1?   J 0    HlB 1? n  }!Arbitrary substring Complex match""0 "!2  N Ԕ?"`v ,$D  0H  0޽h ?/  fff___PPT10~+nD' K= @B Du' = @BA?%,( < +O%,( < +D' =%(D{' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BB7BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*D' =%(D{' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =4@BB7BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*D ' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*++0+ 0 ++0+ 0 ++0+0 +  0L0 ] U   (  ~  s * 7Wj   Q  HXgֳgֳ ?0 Compression has two positive effects: Space saving (or, double memory at the same cost) Performance improvement Better use of memory levels close to processor Increased disk and memory bandwidth Reduced (mechanical) seek time& Ji20 i ir0 i& %r  l E  7,$D 0  N(gֳgֳ ?) l RFrom March 2001 the Memory eXpansion Technology (MXT) is available on IBM eServers x330MXT Same performance of a PC with double memory but at half costp^0 Rix=0 ix]<3b  s 2AibmEIrz  p    ` ,$D 0T  Hgֳgֳ ? @  JMoral: More economical to store data in compressed form than uncompressedBK RiEK   N |?"` p    N( 1?q,$ 0 n CPU speed nowadays makes (de)compression  costless !!88 i3738H  0޽h ? fff  ___PPT10 +zDL ' = @B D ' = @BA?%,( < +O%,( < +D ' =%(D' =%(Dp' =A@BB BB0B%()))D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* D' =%(D' =%(Dc' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(DK' =4@BBB B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-6B+checkerboard(across)*<3<* +8+0+ 0 +   0L0 m e    (   ~   s *x7j      H؃gֳgֳ ?0 } Do we witness a paradoxical situation ? An index injects redundant data, in order to speed up the pattern searches Compression removes redundancy, in order to squeeze the space occupancyz) MiK0 iH0 ix)Mz  p     Y,$D 0/   H8ugֳgֳ ? @  Moral: CPM researchers must have a multidisciplinary background, ranging from Data structure design to Data compression, from Architectural Knowledge to Database principles, till Algoritmic Engineering and more... RiG0 Rin Ri3   N |?"` p B   B  ,$ 0 NO, new results proved a mutual reinforcement behaviour ! Better indexes can be designed by exploiting compression techniques Better compressors can be designed by exploiting indexing techniques : JiE0 iE0 ix :ED =z j w    pj ,$D 0   BTmGH "`j w  F0   <o   iIn terms of space occupancy06l j w    j ,$D 0   BzGH "`j w  F0   <  +  p"Also in terms of compression ratio#0##H   0޽h ?/    fff"___PPT10+ D' = @B Da' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(D' =%(DI' =4@BB5BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<* D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<* D' =-g6B fade*<3<* D2' =%(D' =%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<* %(D' =%(D' =%(DI' =4@BB5BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<* D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<* D' =-g6B fade*<3<* D' =%(D' =%(Dc' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* +8+0+ 0 +x  0L0  (  ~  s *.7Wj  . "   <"L"`]tP Suffix Array (1990)< 00x XB   0D;< V    <( ~ 2Index design (Weiner  73)(0 3    <~ ~ >Compressor design (Shannon  48)( 03 "  <L"`/ YP  Burrows-Wheeler Transform (1994)<00x!l y  PL( ,$D 0f"  <3fL"`%   FCompressed Index Space close to gzip, bzip Query time close to O(|P|)l06-Gt2  63f"`:z2  <73f"`y|l   PZY( ,$D 0t2  6"`Fz2  <1"` "  < fL"` %   ]Compression Booster Tool to transform a poor compressor into a better compression algorithm|0J-^Ql  d   J,$D 0@  p<  pb  NGZ$H'I|"`  "  BjJ"` p< !Improved Indexes and Compressors2 00x""  <|G)"` d Z Wavelet Tree 0  H  0޽h ? fff  ___PPT10 +D ' -= @B D ' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* +J#  0L0 c(  ~  s *!7W   x  c $"    <d$ 0  \P=si 033   Tp) 1?p xT = mississippi#.0 F 0   0 ?  <P71?   Y# i# ippi# issippi# ississippi# mississippi# pi# ppi# sippi# sissippi# ssippi# ssissippi#$Z00 _ ZY  @`  T09 1?0E \SUF(T)0    N 8c?"`0 p B  @  `Do? ` 0 Zz  V f    V f ,$D 0J   H> 1? c J  SA + T occupy Q(N log2 N) bitsr0  ~   N o? V f Iz 0  0,$D 0  ZG5.31?@0-  ZH 1?+  Q(N2) spaceR 0 3333  >z vp  pv,$@ 0N v0  v0`  08c   <LQv0 ZSA 0   <90 138H  0޽h ? fff ___PPT10 .+gD ' = @B Dr ' = @BA?%,( < +O%,( < +DG' =%(D' =%(D' =4@BB7BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*Do' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* +^  0L0 ~!& (  z       ,$@  0!  NL 1?"`   ppi# sippi# sissippi#0 6T   # J N  L      < L  fP=si 0f B B ZD38c? p   T$ 1? jq  Wfinal 0 f~  s *\7W     T, 1? xT = mississippi#.0 F v0  gn `  08c   <v0 ZSA 0   <1?  12 11 8 5 2 1 10 9 7 4 6 3(00 _ (  @`z  L   WT Q ,$@ 0   < L  fP=si 0f B  B ZD38c? p B    `DPPV?H ,$D 0   N1?"`S I ,$D 0z  L      ,$@ 0  < L  fP=si 0f B B ZD38c? p B   `DPPV?*z J ,$D 0  N31?"`S  ,$D  0z @ F     ,$D 0  T 1?h ]  RSuffix Array search O(log2 N) binary-search steps Each step takes O( |P| ) char cmp overall, O(|P| log2 N) time0 1 #1 n#0 x     ,V~  N o?@ F v&  TX1?"` *,$@ 0 `RSuffix permutation cannot be any of {1,...,N} # binary texts = 2N N! = # permutations on {1, 2, ..., N} N log2 N is not a lower bound to the bit space occupancy .0 ?0 x=0 . 4l  c =  %  Z ,$D  0t  Z  1?@ w  , O(|P| + log2 N) timet0    T o?"` c 9  # T 1?@ s Z  F O(|P|/B + logB N) I/Os [JACM 99]t$0  "v $ T& 1?@ V =  T Self-adjusting version on disk [FOCS 02]T+0  )H  0޽h ? fff@@___PPT10@+Z}xD0@' /= @B D?' = @BA?%,( < +O%,( < +D' =%(D*' =%(Dc' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*Dg' =4@BB7BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<* D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<* D' =-g6B fade*<3<* DG' =%(D' =%(D' =4@BB7BB%()))D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<* D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<* D' =-g6B fade*<3<* D ' =%(D ' =%(D' =4@BBBB%())))?D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%())))?D' =1:Bhidden*o3>+B#style.visibility<* %(Dc' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* Dg' =4@BB7BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*DG' =%(D' =%(D' =4@BB7BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*D ' =%(D3 ' =%(D' =4@BBBB%())))?D' =1:Bhidden*o3>+B#style.visibility<* %(D' =4@BBBB%())))?D' =1:Bhidden*o3>+B#style.visibility<*%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<* %(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(Dn' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*%D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*%D' =%(DT' =%(D' =A@BB7BB0B%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*D' =A@BB7BB0B%()))D' =1:Bvisible*o3>+B#style.visibility<*.%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*.D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*.D' =-g6B fade*<3<*.D' =A@BB7BB0B%()))D' =1:Bvisible*o3>+B#style.visibility<*.m%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*.mD' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*.mD' =-g6B fade*<3<*.mD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*m%(D' =-o6Bdissolve*<3<*m+8+0+0 + L  0L0 @%&~(  cz  )  ) ,$D  0  N9 1? `  ep i#mississi p p pi#mississ i s ippi#missi s s issippi#mi s s sippi#miss i s sissippi#m iL0 200 (2D00 22f@Z  NB 1? )# i ssippi#mis s 0 2@  N@H 1?   m ississippi # 0 2,  NpM 1?  i ssissippi# m 0 2,~  s *P7W     Zc 1?  $Let us given a text T = mississippi#.%0 #3$   Nh 1?],$ 0 H mississippi# 0 2    Nl 1?],$ 0 l ississippi#m 0 2  !   ND 1?`]Z,$ 0 o ssissippi#mi  0 2    N@ 1? ],$ 0 l sissippi#mis 0 2     N 1?W ] ,$ 0 Msippi#missis ippi#mississ ppi#mississi pi#mississip i#mississipp #mississippiL 0 2 00 (2400 22N2A  N 1?] ,$ 0 l ssippi#missi 0 2   Nd 1?],$ 0 l issippi#miss 0 2  z Y   Y ,$D  0~  N1?`    Z 1?Y  i Sort the rows"0  z 0@@  0@@,$D  0  N  1? @ # mississipp i 0 2, ~2  N 1?0 @B  ZD8c? z     ,$D  0  N,# 1?  i #mississip p 0 2@~2  N 1?` p B  ZD8c?p` z i   i ,$D  01  N) 1? ic i ppi#missis s  0 2V~2  N 1? p B  ZD8c?p    Z/ 1? ,$  0 [F"0    Z5 1?]),$  0 [L"0 'z 0@ " 0@,$D 0~ # NH& H&|?0P@ $ Z9 1? G  [T"0 f~ % N fV?0P R & # lH&\d @1? P H  0޽h ? fff++___PPT10++WDo)'  = @B D*)' = @BA?%,( < +O%,( < +D' =%(D)' =%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(D)' =%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(D)' =%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<* %(D ' =%(D ' =%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<* %(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<* %(D' =4@BBBB%())))?D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?\CB#ppt_xBCB#ppt_xB*Y3>B ppt_x<*D' =+4 8?dCB0-#ppt_h/2BCB#ppt_yB*Y3>B ppt_y<*D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?\CB#ppt_xBCB#ppt_xB*Y3>B ppt_x<* D' =+4 8?dCB0-#ppt_h/2BCB#ppt_yB*Y3>B ppt_y<* D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*"%(D' =-o6Bdissolve*<3<*"++0+ 0 ++0+ 0 ++0+ 0 ++0+ 0 ++0+ 0 ++0+0 ++0+0 ++0+0 ++0+ 0 +P  0L0 p!"?(    ZEffV?"`/G8  J 0 k  HHgֳgֳ ?"`T,$ 0 ABzip vs. Gzip: 20% vs. 33%, but it is slower in (de)compression !(B RiBB  H0Sgֳgֳ ?  T = m i s s i s s i p p i #* Ri2  N 8c?"` g,$D 0  N V?"` Z,$D 02  N 8c?"` B,$@ 0  N] 1?`@  i #mississip p 0 2BGF  )  0`    Nc 1? `  ep i#mississi p p pi#mississ i s ippi#missi s s issippi#mi s s sippi#miss i s sissippi#m iL0 200 (2D00 22fBZ$  N 1? )# i ssippi#mis s 0 2J   N( 1?   m ississippi # 0 2.   N  1?  i ssissippi# m 0 26~   s *m7W       N  1?`  # mississipp i 0 2: 5   N 1?p` j i ppi#missis s  0 2b  Z, 1?`5 [F"0   Z 1?  [L"0 {  T+gֳgֳ ? <,$ 0 +A key observation: L is locally homogeneousP lK0 lKx, @` `  # ` ,$D 0  N V?"``P  N V?"`  z       ,$D 0  T !gֳgֳ ?   YcAlgorithm Bzip : Move-to-Front coding of L Run-Length coding Statistical coder: Arithmetic, Huffman lK0 n0 s'0 n+d @`~  N 8c?  z  }    p ,$@ 0  N1?"` }3   T|2 1?T  lL is highly compressible"0 3  N V?"` M ,$@ 0  N |?"`s t9 ,$D 0  N V?"`s  ,$D 0   < !zN Yunknown 0f" " 6 !"` # ,$D 0 6Building the BWT SA construction Inverting the BWT array visit ...overall O(N) time...P#0802[H  0޽h ? fff00___PPT100+<_D/' !!= @B D/' = @BA?%,( < +O%,( < +D' =%(Dh' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(Do' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D ' =%(D ' =%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%())))?D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%())))?D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%())))?D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*DI ' =%(D' =%(Dp' =A@BB BB0B%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =4@BB7BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*%(Dz' =%(D"' =%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =%(DV' =A@BB5BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*"%(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*"D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<*"D' =-g6B fade*<3<*"++0+0 ++0+0 ++0+0 ++0+"0 +{7  0L0 !!!#N!(  7z  F   5 ,$D 0]N       T    #   lr  <ZjJ    <.!  h Rotated text 0   C  <4!1?   #mississipp i#mississip ippi#missis issippi#mis ississippi# mississippi pi#mississi ppi#mississ sippi#missi sissippi#mi ssippi#miss ssissippi#m"00 _               @`f  6 F    Z(G! 1?    H0 K   <p!1?@ ,$ 0 #mississipp i#mississip ippi#missis issippi#mis ississippi# mississippi pi#mississi ppi#mississ sippi#missi sissippi#mi ssippi#miss ssissippi#m00 _                    @`~   s *xP!7W-  ! z       E A ,$D 0)   <8R!31?"`   i p s s m # p i s s i iB00 _  3 3  @`t  638c"`    <DV!3"`   YL 03 z    ,$@ 0  <b!1? B12 11 8 5 2 1 10 9 7 4 6 300 _ 00 } 00 i 333333333333333333333333  @`N   n  0o"`  <X! ZSA 03   6EE ,$D 0! z p9     ,$D  0  <!&\ /L includes SA and T. Can we search within L ?000"+  T pp7  # p9   H!Gi HkV ppp H0 T T  + F  # p` 7 8  BCDEXFb u)j( G 20ym/m?0:*u\Q  u.0@`;  B  BlCDEF''e#0@c(ew0gylQlS6bl]9 p/%z*199/VyePT@`a +   xBIC"DEF$$I%87NPg~[FKt""% vbK?< Fty[ILI#IJL@` p 0  B5CDETF^ V~2 L( (1 d-~[n504 ,0@` W p  @BCDEtF~pBXkfpfN=LRaSz5!|z<@@`X y C F    XBC5DEF ~zt(G(u(B?`jji[LL` >5l lsy~~zBD@`W y / ! 6T!1?"`5  % ,$D 0  mississippi" 00 _     @`H  0޽h ? fff5-___PPT10 +jhCD' != @B D<' = @BA?%,( < +O%,( < +D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*!%(D' =%(Ds' =%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*!%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(Dh' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =%(Dg' =4@BB7BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*+p+0+ 0 ++0+!0 +u,  0L0 _(  ~  s *;.7W  .   Tgֳgֳ ?"`P $pBridging data-structure design and compression techniques: Suffix array data structure Burrows-Wheeler Transforml; lK0 Kx K;6q  TT gֳgֳ ?6 ! ,$ 0 KThe corollary is that: The Suffix Array is compressible It is a self-index` lK50 KZ(4L  TDgֳgֳ ?"`! T,$ 0 BIn practice, the index is much appealing: Space close to the best known compressors, ie. bzip Query time of few millisecs on hundreds of MBsn* lK40 Kn/0 KZ*cOz     "!& ,$D 0  T-gֳgֳ ?   7iThe theoretical result: Query complexity: O(p + occ loge N) time Space occupancy: O( N Hk(T)) + o(N) bits lK)0 Kx)0 KZ "   !T ` ` md  # ` m     Z 1?P md  xk-th order empirical entropy"0    T1?` ` P J   Z! 1?C* ,$ 0 0 o(N) if T compressible"0    T 1?j H0 2"   <$="` 3  ,$D 0 O(n) space: A plethora of papers Hk : Grossi-Gupta-Vitter (03), Sadakane (02),... Now, more than 20 papers with more than 20 authors on related subjects!020$08K$0x    - H il    ,$D 0  NBGHF "`  F0   BLp@ AIndex does not depend on k Bound holds for all k, simultaneouslyB0B BH  0޽h ? fff ___PPT10+oSjcD' T= @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*DT' =%(D' =%(D' =A@BB7BB0B%()))D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<* D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<* D' =-g6B fade*<3<* D' =%(D' =%(DI' =4@BB5BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =%(DV' =A@BB5BB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<* D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<* D' =-g6B fade*<3<* DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(++0+0 ++0+0 ++0+ 0 ++0+ 0 +aH  0L0 P ,(   $ T@dV?"`/8  J 0  & N V?"`  c ,$D 0+F  )  |t Z C  Ng 1? `  ep i#mississi p p pi#mississ i s ippi#missi s s issippi#mi s s sippi#miss i s sissippi#m i0 200 (2D00 22      @Z6  Ny 1? )# i ssippi#mis s<0 2 @"  Ǹ 1?   m ississippi #<0 2 ,"  N 1?  i ssissippi# m<0 2 ,~  s *7W     N 1?(` " # mississipp i<0 2 , .   N 1?`@  i #mississip p<0 2 @E   NP 1?`  i ppi#missis s <0 2 V   Zp 1?1`5+ [F"0    Z 1?1 + [L"0   @P  #  ,$D 02  N 8c?"` @ 2  N 8c?"`` @P F  `   `@ @ B  Tgֳgֳ ? ` DHow do we map L s onto F s chars ?*# lK##$  Tlgֳgֳ ? `  &... Need to distinguish equal chars...*' lK'' `A <  #  ` ,$D  0  N 338c?"``A    N 8c?"``| <   Z5GP:HGIG1?"`I2 ,$D  0  ZG<HHI?1?"` 3: ,$D  0 " TH V?"`/8  J 0  # Tk 1?z: ]unknown$0  % N V?"`  c ,$D 0" ' TOYjJ?"` ,$D 0" ( TjJ?"`{ ,$D 0" ) TjJ?"`= C, j ,$D 0" * TjJ?"` G ,$D 0H  0޽h ? fff++___PPT10++"D+' = @B Dg+' = @BA?%,( < +O%,( < +Dm' =%(D' =%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*$%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%%(D' =-o6Bdissolve*<3<*%D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*&%(D' =%(D' =%(D'' =4@BBBB%()?)?D{' =.C7 BBBBBUM 2.5E-6 1.11022E-16 L -0.24792 -0.22569 *3>*B ppt_xB ppt_y=@0BBAApBBB Y<*%D' =%(D' =%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*%%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*&%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*DG' =%(D' =%(D' =4@BB7BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*DG' =%(D' =%(D' =4@BB7BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*D' =%(Dz' =%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*'%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*(%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<**%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*)%(+ s  0L0 //;<.(  z `   + b _6 ,$D 0~ , N31?P`   - ZN 1?` S  ^fr"0 3z  B  1 b pA/,$D 0r 2 N f|?"` 0  3 NS 8c?` B  {occ=2 [lr-fr+1]20  *z ) t    t ,$D 0r  N f|?"`E) t    TX 1?) Jo  *rows prefixed by  si $0 3~  s *T\7W-   F   s   C  <H1?  s #mississipp i#mississip ippi#missis issippi#mis ississippi# mississippi pi#mississi ppi#mississ sippi#missi sissippi#mi ssippi#miss ssissippi#m"00 _               @`-  <S1?  ` i p s s m # p i s s i iT00 _ 00 U 00 _ f  @`t   63f8c"`  p   <L   YL 03    ZY 1?   _ mississippi 0   :z    ,$@ 0'   Nt] 1?  # 0 i 1 m 6 p 7 s 9(00 ZfB  N 8c?"`   Zc 1?' [C"0 3z  @  Z ,$D 0R  T^ff1? @   `ih 1?  lAvailable info$0 f z  0  ,$D 0  Zm 1?"`Pg bP = si"0   N o?"` 0z 0  0,$D 0B  N1?"`0`@  Tr 1?"`0 b First step 0   ~z    "_6 ,$@ 0~  N1? `~  N1?@   Z$x 1? ^fr"0   ZTt 1?u ^lr"0 Dz 0 0    % 0  ,$D 04  Tgֳgֳ ?0 0   (Inductive step: Given fr,lr for P[j+1,p]8) lK33) @`~   N 8c?0 0  vl d<  9<d ,$D  0 " Zgֳgֳ ?"`e   w Take P[j]& 0 n   @`T p- ## d<!~2 $ N1? % Z 1?p- _P[ j ] 0 N & Tgֳgֳ ? `  ,$  0 Find first P[j] in L[fr, lr]20 s @`r ' B1?R o r,$D  0M ( T!gֳgֳ ? `  ,$  0 Find last P[j] in L[fr, lr]20 s @`b ) H1? o ,$D 0O * T+gֳgֳ ? `  ,$ 0 L-to-F mapping of these chars20 s @`z `   . 9 t ,$D 0 / N1?"`P   0 Z6 1?"`` 5  ^lr"0 $z t  4 t ,$D 0~r 5 N 1?Gt  6 T<; 1?_L 2rows prefixed by char  i $0 3+ 7 Z 1?"` X ,$ 0 _s$0 3+ 8 Zl 1?"`~ Z x ,$ 0 _s$0 3 : Zx33V?"`" z  J 0  ; <m2 A Yunknown 0f < 6L"`2z c ,$D  0H  0޽h ? fffCwC___PPT10WC+آD#B' = @B DA' = @BA?%,( < +O%,( < +D' =%(D{' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =4@BB7BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*Dn' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*4%(D' =-o6Bdissolve*<3<*4D' =%(D' =%(Dc' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*9%(D' =-o6Bdissolve*<3<*9D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*<%(D' =-o6Bdissolve*<3<*<D+' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*&%(D' =-o6Bdissolve*<3<*&D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*'%(D' =-o6Bdissolve*<3<*'D|' =%(D$' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*(%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*)%(D' =-o6Bdissolve*<3<*)D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<**%(D' =-o6Bdissolve*<3<**DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*7%(DG' =%(D' =%(D' =4@BB7BB%()))D' =1:Bvisible*o3>+B#style.visibility<*+%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*+D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*+D' =-g6B fade*<3<*+DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(DG' =%(D' =%(D' =4@BB7BB%()))D' =1:Bvisible*o3>+B#style.visibility<*.%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*.D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*.D' =-g6B fade*<3<*.D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*1%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*1D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*1++0+&0 ++0+(0 ++0+*0 ++0+70 ++0+80 +/  0L0 tl0 (  ~  s *   J8 !) !)x  N 1?"`/) n Still guarantee O(p) time to count the P s occurrences*81 7(#  Tgֳgֳ ?"`!/ VJ The column L is actually kept compressed:J, lK),z  p    c,$D 0  Hgֳgֳ ? @   Interesting issues: What about arbitrary alphabets ? [Grossi et al., 03; Ferragina et al., 04] What about disk-aware, or cache-oblivious, or self-adjusting versions ? What about challenging applications: bio,db,data mining,handheld PC, ... RiK Ri<H0 RiP<I0 RiZ<33 *  N |?"` p   Tgֳgֳ ?"`%  J Efficient and succinct index construction [Hon et al., Focs 03]TC lK+C8  &  TL gֳgֳ ?"` VJ The Locate operation takes O(loge N) time, lK D+  T  1?"` - Some additional data structure, in o(n) bits*.1 --  Tgֳgֳ ?"`   LJ Bio-application: fit Human-genome index in a PC [Sadakane et al., 02]pK lKKH  0޽h ? fffKC___PPT10#+|3D' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(DI' =4@BB5BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*+ 0 9(  &  HD1Go33|"`6T,$@ 0 l2We investigated the reinforcement relation: Compression ideas Index design Let s now turn to the other direction Indexing ideas Compressor design,08}"0'0x%0,3  & 3  66 7W- ^Where we are ...B  <0EL"` # G ,$D 0 YBooster 0H  0޽h ? fff3fZ̙  ___PPT10 .:MP5+)-D: ' G= @B D ' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*Ou%(D' =-o6Bdissolve*<3<*OuD3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*u%(D' =-o6Bdissolve*<3<*uD' =%(D' =%(DV' =A@BB5BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*+8+0+0 +   0 `B0 >(  x  c $i7Wj   x  c $<-  - 8  P4  - Rectangle: Click to edit Master text styles Second level Third level Fourth level Fifth level Mw@ rIt is a technique that takes a poor compressor A and turns it into a compressor with better performance guaranteets3 3&t  6"` B 6- f ,$ 0 lA memoryless compressor is poor in that it assigns codewords to symbols according only to their frequencies (e.g. Huffman) It incurs in some obvious limitations: T = anbn T = random string of length 2n and same number of  a,b "|n(HxC GCG3MCC(CGfOf*GfOf*KC:GfP ( m9H  0޽h ? fff3fZ̙___PPT10b.c+duD' -= @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*B%(D' =-o6Bdissolve*<3<*B+8+0+B0 +(  0  'p(  p p 0N F ,$@ 0 X.Qualitatively, we would like to achieve c is shorter than c, if T is compressible Time(Aboost) = O(Time(A)), i.e. no slowdown A is used as a black-box(+,(#'3###'3##'3####333'3##'3,S .~ p s *PR   ~ p s *j7Wj   [z w  p 2   ,$@ 0T w6   p# w   p Tf1?"`w6 / N  6 0  p ] q k   p N1?"` }   p T8m 1? 6 0 fc 00  p T$s 1?w   [Booster"0  F *F  p B{  p ZLqq1?"`F   CA&0 '~ p N1? w)  p Tdu 1?*s ,m  PT 0 ~ p N1?] )  p T~ 1?# s m  Oc0  p <GT"`s  ,$D 0 ZThe more compressible is T, the shorter is c X.0x .F  #p P4 $p 8 Rectangle: Click to edit Master text styles Second level Third level Fourth level Fifth level Mw@ rIt is a technique that takes a poor compressor A and turns it into a compressor with better performance guaranteets 3&t %p 6"`;" 'p 6"`,i,$D 0 =Two Key Components: Burrows-Wheeler Transform and Suffix Tree$>0x>>H p 0޽h ? fff3fZ̙___PPT10.c+AӂD' = @B D' = @BA?%,( < +O%,( < +D/' =%(D' =%(Dg' =4@BB7BB%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*pD' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*pD' =-g6B fade*<3<*pD' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*p(%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*p(S%(D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =-o6Bdissolve*<3<*pD' =%(Dh' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*pS%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =%(D' =%(DF' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*'p%(D' =-u6Bdiamond(in)*<3<*'p+p+0+p0 ++0+'p0 +  0    '(P (  (r ( S 7Wj   8 " &(, ( H"*  @H0(T) = 6 "i (ni/n) log2 (ni/n)$!x'/'''"/"'/'/'/'!r ( HZG?HL"`  ( B&  q!Frequency in T of the i-th symbol"0""  ( 0l pw  >" ( 6"` 7,9 ,$D 0 {We get a better compression using a codeword that depends on the k symbols preceding the one to be compressed (context)V|(nZn|! %( Blh  { |T| H0(T) is the best you can hope for a memoryless compressor E.g. Huffman or Arithmetic coders come close to this bound|v##!#+#'4#!##'# '#'|H ( 0޽h ? fff3fZ̙___PPT10b.%+RD' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*(%(D' =-o6Bdissolve*<3<*(+8+0+(0 +GC  0 *""=  J(   x   c $t7Wj      B0 gi {Hk(T)D'/'   <sGz,$ 0 R= (1/|T|) "|w|=k | T[w] | H0(T[w])`* '' +"++/''''/'    ''**   0 6 )  RExample: Given T =  mississippi , we haveF*3 *   BlT` G- T[w] = string of symbols that precede w in T.v#'3'3'3/3#'3#'3###'3.l 6 "F  * 6 "F ,$D 0`B   0Dp  `B   0DpF y F `B   0Dp    `B   0Dp] F F    H="`p6 "0  s T[i]= mssp,(   Tl 6 0  = 6 0 ,$D 0`B   0Dp6 6 `B   0Dpc c    H@"`6 0  z T[is] = ms .   H"   <efL"` c,$D  0 xProblems with this approach: How to go from all T[w] back to the string T ? How do we choose efficiently the best k ? 0010F#,1'%/*y "  <x g5  N 0z m  +  ,$@ 0z" ,  <fV"`P  -  Nh 1?"`}  F Compress T up to Hk(T) @ compress all T[w] up to their H0 *  3'3/3%3 ' 3 ' 3 ' 3 '  '3/3B .  <"`z m  N$0nAz , /  t,$D 0 0  HGHV3 "`, F0 1  <̑tj> gUse Huffman or Arithmetic0.l  4 =,$D 0 2  BGMcH "` F0 3  <v hFor any k-long context 0l  8  8  8 ,$@  0 6  BGoH]} "` 8  F0 7  <|/   OBWT0)l v < v,$D  0 :  HGH^ "`v F0 ;  B@* W Suffix Tree 0  H   0޽h ?O@0 2 6 :  fff3fZ̙$$___PPT10$.%+'k6D$' = @B D#' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<** %(D' =-o6Bdissolve*<3<** D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*= %(DW ' =%(D' =%(DV' =A@BB5BB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<* D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<* D' =-g6B fade*<3<* DI' =4@BB5BB%(D' =1:Bvisible*o3>+B#style.visibility<*4 %(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*4 D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<*4 D' =-g6B fade*<3<*4 D ' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*+ %(DE' =4@BBB B%(D' =-6B'blinds(horizontal)*<3<*4 D' =1:Bhidden*o3>+B#style.visibility<*4 %(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*/ %(D' =%(D' =%(DV' =A@BB5BB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<* D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<* D' =-g6B fade*<3<* DJ ' =%(D' =%(DI' =4@BB5BB%(D' =1:Bvisible*o3>+B#style.visibility<*8 %(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*8 D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<*8 D' =-g6B fade*<3<*8 DI' =4@BB5BB%(D' =1:Bvisible*o3>+B#style.visibility<*< %(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*< D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<*< D' =-g6B fade*<3<*< +p+0+ 0 ++0+ 0 +9  0L0 G$?$P)h<PT c#(  < ,< Zd 1? [  yT = mississippi#.0 3-L  ) <# d  < N 1? `  Ypi#mississi p ppi#mississ i sippi#missi s sissippi#mi s ssippi#miss i ssissippi#m iL0 200 (2<00 22Z@P" < N 1? )# issippi#mis s 0 2J < N 1?   ~mississippi # 0 2, < Nh 1?  ~ississippi# m 0 2, !< TH& |?"`M-M  X< ZffV?"`zd  J 0 xl d=_ f<d=_,$D 0z +< <33"`-=_z *< <Ha"`dt_8 m  C<} 6 " << BfV "`P  ;<  `t8` 1? "`~ F Compress T up to Hk(T) @ compress all T[w] up to their H0 * n 3'3/3%3 ' 3 ' 3 ' 3 '  '3/3B A< B=` "`z m  N$0n~ < s *7W    < Z@-` 1?jQ `bwt(T) 0 3 < T-` 1?d ~ #mississipp i 0 2.  < TT` 1?FdD @ i#mississip p 0 2@7 < T( ` 1?k+  ippi#missis s  0 2` >< B8`"` ], ,$ 0 4J@ compress pieces of bwt(T) up to H0 &  33'3/3%S8 M Y@ N<M QT @& J<# M V K< B` {Hk(T)D'/'( L< Bx`@& B= (1/|T|) "|w|=k |T[w]| H0(T[w]):" ''++!++/''''/'''''"z" M< <m"`M MY@ O< <|S`zz ka `Remember that...0 Y< <$G`7 Uunknown0" \< <d[`ff"` # ,$D 0 ,T[w] is a permutation of a piece of bwt(T) z-0######'-R g< 6 <"`" 0 8 ,$@ 0Nl WV  e<V W ,$D 0<T   7<#  z -< <Ha"` z .< <Ha"`-  3< Be`"`   [w(3 4< Hj`"`    [w(3& [< No`GfHrQL "`V   T[is] = msV 0#!#!% `T - 6<# WzB /< <"`zB 0< <"`-H < 0޽h ?[< fff*"___PPT10+4D>' v`= @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*e<%(D' =-o6Bdissolve*<3<*e<D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*f<%(D' =-o6Bdissolve*<3<*f<DA' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*g<%(D' =-o6Bdissolve*<3<*g<DV' =A@BB5BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*\<%(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*\<D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<*\<D' =-g6B fade*<3<*\<D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*><%(D' =-o6Bdissolve*<3<*><D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*g<%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*\<%(++0+><0 ++0+\<0 ++0+\<0 +BK  0L0 ].U.`F@0  -(  @5l T  u@T ,$@ 0y@ T  Y@T `B  @ 0Dp  `B !@ 0Dp  `B "@ 0Dp D D`B #@ 0Dp   z T@ <L "`Q W@ H`T+r H1(T)P' / ' 8@ Q  t@Q t n@ 633"`Qt o@ 6L"`CQ t q@ 633"`QCt s@ 633"` Q 5 l T  @T ,$@ 0@ T F  e@T F @ T F  c@T F ^@  F  M@ F ZB <@ s *Dfp" "ZB ;@ s *Dfp@ @`B 7@ 0Dfp ZB =@ s *Dfp ZB >@ s *DfpC CZB ?@ s *Dfp%  % ZB @@ s *Dfp  ZB A@ s *DfpF  F  a@ H3` T+(  H2(T)P' / ' t d@ 63L"`"(@   @ t @ 6333"`t @ 63L"`@t @ 6333"`@#t @ 6333"`Ct @ 63L"`C& t @ 6333"`%  t @ 63L"` F t @ 6333"`F  f8 7f  f@ 7z" @ < "`7f  @  `Е` 1? "`7  x Compress T up to Hk @ compress pieces of bwt(T) up to H0 D '  3'3/3 33 ' 3 / 3< L   L@#  r 5T  ) @#   @ N` 1? `  Ypi#mississi p ppi#mississ i sippi#missi s sissippi#mi s ssippi#miss i ssissippi#m iL0 200 (2<00 22Z@P"  @ NȬ` 1? )# issippi#mis s 0 2J  @ Nز` 1?   ~mississippi # 0 2,  @ N` 1?  ~ississippi# m 0 2,   @ T` 1?`  #mississipp i 0 2.   @ T(` 1?u o i#mississip p 0 2@? @ T` 1?B< ippi#missis s  0 2`~ @ s *`7W  `  @  `X` 1? b ~ `Bwt(T) 0 3 @ TH& |?"`zz ~l ~   5@~  ,$@ 0 3@ B` z|  :Compressing those pieces up to their H0 , we achieve H1(T);0%%3-3-  % 3 - 3 % 3;t" 4@ 6Ԕ"`~  z ~   F@ ~  ,$D  0 G@ <P[ z|  :Compressing those pieces up to their H0 , we achieve H2(T);0%%3-3-  % 3 - 3 % 3;t" H@ 6Ԕ"`~  l   Z@s ,$D  0 I@ Bl[GHT; "`  D0: K@ <[ != *We have a workable way to approximate Hk j+0&'/+ @ Z[ffV?"`M  J 0  @ <t[@ Uunknown0 @ <["` *H  [ Recall that 0  l Gy @Gy,$D 0 @ B4[G? ]w*' @ BWG6H"`+iy:l P  @P ,$@ 0t" @ 6"`P  B @ B [ ? $T[w] s permutationr'''' 'H @ 0޽h ?I@ fffum___PPT10M+'D1' = @B D' = @BA?%,( < +O%,( < +D ' =%(D ' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*u@%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*5@%(D' =-o6Bdissolve*<3<*5@DI' =4@BB5BB%(D' =1:Bvisible*o3>+B#style.visibility<*@%(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*@D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<*@D' =-g6B fade*<3<*@DI' =4@BB5BB%(D' =1:Bvisible*o3>+B#style.visibility<*@%(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*@D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<*@D' =-g6B fade*<3<*@D ' =%(D' =%(DE' =4@BBB B%(D' =-6B'blinds(horizontal)*<3<*u@D' =1:Bhidden*o3>+B#style.visibility<*u@%(DE' =4@BBB B%(D' =-6B'blinds(horizontal)*<3<*5@D' =1:Bhidden*o3>+B#style.visibility<*5@%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*@%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*F@%(D' =-o6Bdissolve*<3<*F@D' =%(D' =%(DI' =4@BB5BB%(D' =1:Bvisible*o3>+B#style.visibility<*Z@%(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*Z@D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<*Z@D' =-g6B fade*<3<*Z@+}  0 ccL0 !c(  Lf" L 6["` Y,$@ 0 <Goal: find the best BWT-partition induced by a Leaf Cover !!P=0n) =|" L 6H["` Y,$D 0 RSome leaf covers are  related to Hk !!!P*0n$  * L Z [ffV?"`Z  J 0  8    LQ :  N   L  5T  ) L#   L N[ 1? `  Ypi#mississi p ppi#mississ i sippi#missi s sissippi#mi s ssippi#miss i ssissippi#m iL0 200 (2<00 22Z@P" L N[ 1? )# issippi#mis s 0 2J L N[ 1?   ~mississippi # 0 2, L N` [ 1?  ~ississippi# m 0 2, L N"[ 1?`  #mississipp i 0 2.  L N'[ 1?u o i#mississip p 0 2@9 L N@-[ 1?B< ippi#missis s  0 2` L Z3[ 1? \ ~ `bwt(T) 0 3 L NH& |?"` | $ L <8[33|"`  12 11 9 5 2 1 10 9 7 4 6 3^00n00nfx L c $@5[j  [ `8   0L> t (L 6fL"`pt ,L 6fL"` `s  @ C  /LC t #L 6fL"`t $L 6fL"`mt %L 6fL"`mPt &L 6fL"`Pt 'L 6fL"`Ct )L 6fL"`p@% t *L 6fL"`%  t +L 6fL"` P t -L 6fL"`s ) t .L 6fL"`)  *#8  0s  L E f2 1L 6 0 2 2L <C[   X12$0 f2 3L 6 P 2 4L <G[   W1$0 f2 5L 6df2 6L 6ZB 7LB s *D] ` ZB 9LB s *D ` ZB :L s *D` ` ZB ;L s *D` ZB L BQ[ .  Oi0  ?L BXP[C@ Op0  @L B S[ @  Om0  AL B\[cR Os0 2 CL <_[]   X11$0 2 DL <e[m #  W9$0 f2 EL 6 CZB GLB s *D  ZB HLB s *D  ZB IL s *D   JL Bh[  r O#0  KL Bm[ 3  Rppi#0  LL Btq["`P }  Qssi0 2 OL BPu[" c  c500  2 PL By[ Tc  W2$0 ZB QLB s *D}  ZB RL s *D   SL B,~[P h 8  Rppi#0  TL B[%   Ussippi#0 2 UL B[&p X10$0 2 VL B[Fp W9$0 ZB WLB s *DZB XL s *D YL B,[r Q i#0  ZL B[6;E R pi#0 f2 [L 6pf2 ]L 6pZB ^L s *DVVZB _L s *DVI `L BX[r Oi0  aL B[E Q si0 2 bL <$ [ c  W7$0 2 cL B[V c  W4$0 ZB dLB s *DsqV ZB eL s *DVq  gL B[  Rppi#0  hL B\[Ve  Ussippi#0 2 kL B8[g s  W6$0 2 lL B[ s  W3$0 ZB mLB s *DpI ZB nL s *DIp,  oL B(Y   Rppi#0  pL B*Ywe  Ussippi#0 8    tLs ~ t n rL 0f"` s   sL <'Y 8  Y Row order 0 f  l  p)  L}0  ,$D 0 vL <(+YE"`  ` Oi0 xL <8YE"`u  S  Op0 yL <X+B#style.visibility<*L%(D' =-6B+checkerboard(across)*<3<*LD{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*LD' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*LD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =-o6Bdissolve*<3<*LD0' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =-o6Bdissolve*<3<*LDE' =4@BBB B%(D' =-6B'blinds(horizontal)*<3<*LD' =1:Bhidden*o3>+B#style.visibility<*L%(D' =%(D6' =%(DE' =4@BBB B%(D' =-6B'blinds(horizontal)*<3<*LD' =1:Bhidden*o3>+B#style.visibility<*L%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =%(DI' =%(DK' =4@BBB B%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =-6B+checkerboard(across)*<3<*LD' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*0L%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*L%(DK' =4@BBB B%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =-6B+checkerboard(across)*<3<*LDV' =A@BB5BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*LD' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<*LD' =-g6B fade*<3<*LD@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =-o6Bdissolve*<3<*LD' =%(D=' =%(DE' =4@BBB B%(D' =-6B'blinds(horizontal)*<3<*LD' =1:Bhidden*o3>+B#style.visibility<*L%(DE' =4@BBB B%(D' =-6B'blinds(horizontal)*<3<*LD' =1:Bhidden*o3>+B#style.visibility<*L%(DR' =A@BBB B0B%(D' =-6B'blinds(horizontal)*<3<*LD' =1:Bhidden*o3>+B#style.visibility<*L%(DK' =4@BBB B%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =-6B+checkerboard(across)*<3<*LD' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*L%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*L%(DK' =4@BBB B%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =-6B+checkerboard(across)*<3<*LD' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*L%(DV' =A@BB5BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*LD' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<*LD' =-g6B fade*<3<*LD@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =-o6Bdissolve*<3<*LD' =%(D' =%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*L%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*L%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*L%(++0+L0 ++0+L0 ++0+L0 ++0+L0 ++0+L0 ++0+L0 ++0+L0 ++0+L0 ++0+L0 ++0+L0 ++0+L0 ++0+L0 +)  0 @.8`(  8 $8 s Y0e0e #" 0e <$@ 0 Y az J d9  8  ` ) ,$@ 0n 8 TY 1?J 2  : |c | d"  |s| H (s) +f(|s|) D0 '''''''''/%'%'%%3@  8 B4Yx  kTechnically, we show that0t 8 6m"`J d9  8 BY"`n $B ,$ 0 Q00 8 BY"`t "H ,$ 0 Sk 03~  8 s *\Y7Wj  Y   8 BF"` 7 ,$ 0 V"k 0fz  * % 8   3 ,$D  0H 8 BxS"`M *  + log2 |s| + gk ~03 333 333 8 <f >% T  03al 9 % +8 X,$D  0T V I '8# 9 J" (8 6S"`V I F0 )8 Bm`   $Researchers may now concentrate on the  apparently simpler task of designing 0-th order compressors(f8nZf!f *8 Hs % 1[further results joint with Giancarlo-Sciortino] .203'32H 8 0޽h ? fff3fZ̙ ___PPT10.c+8PD' = @B D' = @BA?%,( < +O%,( < +DL' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*$8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*$8 %(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*$8 =%(D' =%(Du' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D ' =%(Dg ' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =-o6Bdissolve*<3<*8D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =-o6Bdissolve*<3<*8DD' =A@BBBB0B%(D' =-u6Bdiamond(in)*<3<*8D' =1:Bhidden*o3>+B#style.visibility<*8%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =-o6Bdissolve*<3<*8D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*+8%(D' =-o6Bdissolve*<3<*+8++0+80 ++0+80 ++0+80 ++0+80 +   0  .,@y(  ,x , c $4F-7Wj  -  , s $0e0e #" 0ejC -   , H"`  '[joint with Manzini, Makinen, Navarro] .(x&%( +, B"` t *[joint with Giancarlo, Manzini,Sciortino] ,+)%+ -, N4gֳgֳ ?% 6 ,$@ 0 * Interesting issues: What about space construction of BWT ? What about these tools for  XML or  Images ? Other application contexts: bio,db,data mining, network, ... From Theory to Technology ! Libraries, Libraries,.... [e.g. LEDA] Ri Ri<E0 Rin<33&l 3 3   ., T |?"`% ,$D 0H , 0޽h ? fff3fZ̙___PPT10.[Pe+Ds' = @B D.' = @BA?%,( < +O%,( < +Dd' =%(D ' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*-,%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*-,>%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*-,>m%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*-,m%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*.,%(D' =%(D' =%(DI' =4@BB5BB%(D' =1:Bvisible*o3>+B#style.visibility<*-,%(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*-,D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<*-,D' =-g6B fade*<3<*-,+  0 `(  `X ` 0A?H ` 0޽h ? fff3fZ̙___PPT10i._i++D=' = @B +  0 p 0(  H  0޽h ? fff3fZ̙___PPT10i.a@A+D=' = @B +#  0  {(   r   S ě-7Wj  -    s -0e0e #" 0eYY<$@ 0 -    B̒ףV"`*% ,$D 0 \ Any string s 0      BLҒףV"`S T*c ,$D  0 Y Black-box 0     BXՒףV"`E TU ,$D  0 [ O(|s|) time 0     BڒףV"` T ,$D  0 hVariable length contexts0;"   6ޒ"`I,$D  0 =Two Key Components: Burrows-Wheeler Transform and Suffix Tree$>0x>>H   0޽h ? fff3fZ̙___PPT10v.[Pe+;D2' = @B D' = @BA?%,( < +O%,( < +D ' =%(D ' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*  %(D' =-o6Bdissolve*<3<*  D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*  M%(D' =-o6Bdissolve*<3<*  MD3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* Md%(D' =-o6Bdissolve*<3<* MdD3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* d%(D' =-o6Bdissolve*<3<* dD' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =%(D' =%(DF' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-u6Bdiamond(in)*<3<* ++0+ 0 ++0+ 0 ++0+ 0 ++0+ 0 ++0+ 0 +D  0 [SpD(  Dx D c $l7Wj    D s D0e0e #" 0eY  9" D 6"`) V _Surprisingly, full-text indexes help in finding the optimal partition in optimal linear time !!40000n``H D 0޽h ? fff3fZ̙___PPT10i.[Pe+D=' = @B +F   0 ] U ( (  (F 5  ( 5 t" ( 6Ԕ"`5 l ( <<   s = (bad)n (cad)n (xy)n (xz)n0 (/( / (/( ( <v WExample03x ( c $<7Wj    ( <ܳ B0F   (    ( <ඎd  a1-long contexts 03tr  ( 6"`F =   ( =   ( <=  a2-long contexts 03tr  ( 6"`j  ( <p j  8$xs= ynzn > yxs= yn-1 , zxs= zn-1%0((((%\F  @  (  @  ( <ώ @  as= d2n < bas= dn , cas= dn!0(((!tr ( 63f8c"`  H ( 0޽h ? fff3fZ̙___PPT10i.%+D=' = @B +A  0L0 P?(  ~  s *ݎ7Wj     NXߎ 1?q),$ 0 HT = & bzip& bzip2unbzip2unbzip & <%08 2 .   R  Ttgֳgֳ ?T@,$ 0 (What about word-based occurrences of P ?*) lK))8  Tgֳgֳ ? T ,$  0 The FM-index can be adapted to support word-based searches: Preprocess T and transform it into a  digested text DTR< lK80 Kx<8t2  N 3|?F  ,$D  0z pP @  e,$D 0~2  N 3V?PP @   Z. 1?p d `word"0 3z p @   eQ> ,$D 0~2   N 3V?PP @   Z. 1?p d bprefix"0 3z pQ @   e } ,$D 0~2  N 3V?PP @  Z̗. 1?pQ d e substring" 0  3 z p @  ea ,$D 0~2  N 3V?PP @  ZМ. 1?p d d suffix" 0  3   ZT. 1?B,$  0 bP=bzip"0 ffN  Z`. 1?CT= ,$  0 4...the post-processing phase can be time consuming !*5 K55r  T.gֳgֳ ? ,$   0 NUse the FM-index over the  digested DT$( K((z  N. 1?   ,$   0 RWord-search in T Substring-search in DTD*0 333*H  0޽h ? fff,,___PPT10b,+/{wD*' .= @B Dy*' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?\CB#ppt_xBCB#ppt_xB*Y3>B ppt_x<*D' =+4 8?dCB1+#ppt_h/2BCB#ppt_yB*Y3>B ppt_y<*D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?\CB#ppt_xBCB#ppt_xB*Y3>B ppt_x<*D' =+4 8?dCB1+#ppt_h/2BCB#ppt_yB*Y3>B ppt_y<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*++0+0 ++0+0 ++0+0 ++0+0 ++0+0 ++0+0 ++0+0 +  0L0 PP`kkpP(  ~  s *(.7W     <`.1?u Variant of Huffman algorithm: Symbols of the huffman tree are the words of T The Huffman tree has fan-out 128 Codewords are byte-aligned and tagged0 | #%#"   z 0 P   P0  ,$D 0nN ` 0 0p      H.A5% ` @  N$0 7 r  BA5%` P r  BA5%` 0    <.` `  S1 0   <P.p`   S0 0   <|.`   S0 0fr   6` P 0    <.` p  ~ Byte-aligned codeword0"    <X.1? 0   Wa0    <o1?00   Ww0    <s1?0   Wr0  N     0 Pypl  <1?P 0   HXw1?  `  atagging"0 3 z `   p @0 ,$D  0~2  N 3m?p   Z| 1?` $5  _yes"0 3z 0 0 p  p : ,$D  0~2  N 3m?0 p  Z@p 1?0   ^no"0 3z P p+w   e ,$D  0~2  N 3m?P p   Z 1? +w ^no"0 3  H1?P7,$D 0 fAny word 0   1 z P    P  ,$D 0N jo    jo     H1?jo: \7 bits0   N  0 ` _  !    " <* _  w Codeword0"  r # BA5% `  r $ BA5%`  r % BA5%` ` fr & 6 P `  ' <\1?0 p  Wa0   ( <1?`0   Ww0   ) <@1?@0 0   Wr0  T    *# P pl + <1?P 0  , H1?  `  ghuffman"0 3 gz ` ` -  ,$D  0 . T಺gֳgֳ ?` 0   WFM-index8 lK   @`~ / N 8c?` `: 0 T,gֳgֳ ?`p  >1. Dictionary of words 2. Huffman tree 3. FM-index built on DT(?0 -n?? @`9#z  < 1  <,$D 0  v M 2  <,$D 0 3 H1?v   L"0 7  4 <pº~   db00 5 <XO~   S0 0 6 <ĺ { dg00 7 <DɺX  { Vg"0 8 <8ͺ X { S0 0  9 <Ѻ  { L"0 : <ٺ  { S0 0  ; <,պX ~  db00 < < ݺ~ %  S1 0  = < ~ X  S1 0  > <{ S1 0  ? < ~ A  dg00 @ < ~  L"0 A <|A ~  S0 0  B <\~ *  db00 C <@ ~   S0 0  D <+B#style.visibility<*%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*1%(Dn' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*-%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*-D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*-D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*`%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*`D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*`DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*d%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*e%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*k%(D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*a%(D' =-o6Bdissolve*<3<*aDn' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*]%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*]D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*]++0+0 ++0+`0 ++0+d0 ++0+k0 +lS  0L0 ##`()p#(  z Z   Z ,$D  02  N V?"`   Z 1? Z  Up"0 3z `    `  ,$D 0~2  N V?`   T 1?    T = .... #<0   TV?"` ,$@ 0 J 0 .  Nd 1?`@  i #mississip p<0 2 @+F  )  2t C  No 1? `  ep i#mississi p p pi#mississ i s ippi#missi s s issippi#mi s s sippi#miss i s sissippi#m i0 200 (2D00 22      @Z6   N 1? )# i ssippi#mis s<0 2 @"   N 1?   m ississippi #<0 2 ,"   N 1?  i ssissippi# m<0 2 ,~   s *܊7W      N 1?`  # mississipp i<0 2 , E  N蒲 1?`` Z i ppi#missis s <0 2 V  Z 1?`5 WF0   Zt 1?  WL0   TT V?"`  J 0   TT 1?0 ]unknown$0 z 0 ]@  0 ,$D 08  TLgֳgֳ ? @0 <1. We can map L s to F s chars(0 lKx  Tgֳgֳ ? P)@ 2. T = .... L[ i ] F[ i ] ... & lK    Z, 1?0 ]v1 gTwo key properties:"0 1  ZL 1?C]  ,$ 0 sReconstruct T backward:* lK2  N V?"`a!,$D  0z     ,$D 02  N V?"`   ZƲ 1?   Ui"0 2  N 3V?"` t4p ,$D  0z   p     p ,$D  02 ! N V?"` p  " Z<̲ 1?3   Up"0 f2 # N V?"`6 t4& ,$D  0z   &  $  & ,$D 0 % Zв 1?"`   Ui"0 32 & N fV?"` 6 & v ' N1?G " ( <ղL"`  ,,,$D 0 *Building the BWT SA construction Inverting BWT array visit ...overall O(N) time...L#040.WH  0޽h ? fff//___PPT10.+V0D-' = @B D-' = @BA?%,( < +O%,( < +D2' =%(D' =%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*'%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D?' =%(D' =%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(Dg' =4@BB7BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(Dg' =4@BB7BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*D' =-g6B fade*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* D' =%(D' =%(Dg' =4@BB7BB%(D' =1:Bvisible*o3>+B#style.visibility<*#%(D' =+4 8?fCB#ppt_w*0.70BCB#ppt_wB*Y3>B ppt_w<*#D' =+4 8?\CB#ppt_hBCB#ppt_hB*Y3>B ppt_h<*#D' =-g6B fade*<3<*#D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*$%(D' =%(D' =%(DV' =A@BB5BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*(%(D' =+4 8?RCBBCB#ppt_wB*Y3>B ppt_w<*(D' =+4 8?RCBBCB#ppt_hB*Y3>B ppt_h<*(D' =-g6B fade*<3<*(++0+0 ++0+0 ++0+0 ++0+(0 +   0 P'-<$(  <l   +<d0 ,$D 0;@ S  *<S q@  S  (< S N " <  S t" < 6ff"`" < <|"`"  Qmiiii0lB !<B <D>> r@  S  )< S N  "  <  S t" < 6ff"` "  < <"` "'  Rsssspp0lB "< <D> 4 lB #< <D>a R  lB $<B <D> R a  lB %<B <D>[R = lB &< <D>>R N  x < c $57Wj     < BA9 3 A[collaboration: Giancarlo, Manzini, Makinen, Navarro, Sciortino] ,B@'BF    < jt"  < 6ff"`   < <4G  W mississippi 0  F gJ  <  dG  < <K*  Mi0t" < 6ff"`gJ F   <  )  < <DP  Mm0t" < 6ff"` F  n  <    < <TM O  Mp0t" < 6ff"` n F    <    < <+B#style.visibility<* <%(D' =-o6Bdissolve*<3<* <D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*+<%(D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*'<%(D' =-o6Bdissolve*<3<*'<+8+0+ <0 +rP EPhJP =c\M0q"]ZJ]KLFk `ll EM@3D( o 0$@{>!v22 E1Oh+'0@ `h    ,84Boosting Textual Compression in Optimal Linear TimePaolo Ferragina tp1393[1]Paolo Ferragina989Microsoft PowerPoint@"D@@ @-X ՜.+,0`    $ On-screen ShowUniversità di Pisa, Italy9! -ArialTahomaTimes New Roman WingdingsComic Sans MS Wingdings 2 Courier NewSymbolMonotype SortsMonotype Corsiva Wingdings 3Presentazione8On Compression and Indexing: two sides of the same coin$What do we mean by “Indexing” ?'What do we mean by “Compression” ?7Compression and Indexing: Two sides of the same coin !Our journey, today...>The Suffix Array [BaezaYates-Gonnet, 87 and Manber-Myers, 90]-Searching in Suffix Array [Manber-Myers, 90]'The Burrows-Wheeler Transform (1994)*Why L is so interesting for compression ?Suffix Array vs. BW-transform;A compressed index [Ferragina-Manzini, IEEE Focs 2000] A useful tool: L  F mapping+Substring search in T (Count occurrences)Many details are missing... Slide 15$What do we mean by “boosting” ?$What do we mean by “boosting” ?The emprirical entropy H0The empirical entropy Hk Use BWT to approximate Hk)What are the pieces of BWT to compress ?-Finding the “best pieces” to compress...3A compression booster [Ferragina-Manzini, SODA 04]4May we close “the mutual reinforcement cycle” ? Slide 25 Slide 26A historical perspective2How do we find the “best” partition (i.e. k) Example: not one kWord-based compressed indexThe WFM-indexThe BW-Trasform is invertible0The Wavelet Tree [Grossi-Gupta-Vitter, Soda 03]  Fonts Used Design Template Slide Titles!'_-0Paolo FerraginaPaolo Ferragina  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root EntrydO)PicturesCurrent UserSummaryInformation(PowerPoint Document(QDocumentSummaryInformation8