|
¡Ü ½ÃÀÛÇϱâ Àü¿¡... linux-2.0.30.tar 25108480 ÀÌ ±ÛÀº °£´ÜÈ÷ PCÅë½Å»ó¿¡ ¿Ã¸° ±ÛÀ̾ú´Ù. ±×·¡¼ À§ÀÇ ¿¹´Â ¿À·¡µÈ Ä¿³ÎÀÎ 2.0.30À» ½è¾ú´Ù.. Áö±ÝÀº 2.2.4¹öÀüÀÌ ³ª¿Í ÀÖ´Ù. 97³â ´ç½Ã¸¸Çصµ bzipÀº º°·Î ¾²ÀÌÁö ¾Ê¾Ò´Ù. ±×·¯³ª ¿äÁòÀº ±â°èÀÇ ¹ß´Þ·Î bzipÀº Á¡Â÷ °¢±¤¹Þ°í ÀÖÀ¸¸ç Ä¿³ÎÀÇ zImage ¸»°í bzipÀ¸·Î µÈ bzImageµµ ¾²ÀÌ°í ÀÖ´Ù. bzipÀº ¿äÁòÀº ¾²ÀÌÁö ¾Ê°í, bzip2¸¦ ¾²°í ÀÖ´Ù. ¾Ë°í¸®Áò»óÀÇ Â÷ÀÌ´Â ¾øÀ¸³ª bzipÀº ÃÖÁ¾ÀûÀ¸·Î »ê¼úÄÚµùÀ» ¾²°í ÀÖ°í, bzip2´Â ÇãÇÁ¸¸ Äڵ带 ¾²°í ÀÖ´Ù. µÎ ¹æ½Ä Áß¿¡¼´Â »ê¼úÄÚµùÀÌ Á» ´õ È¿°ú°¡ ÀÖÀ¸³ª ´À¸®´Ù. ¶ÇÇÑ »ê¼úÄÚµùÀº ƯÇã ¹®Á¦·Î »ç¿ëÇÏÁö ¾Ê´Â °ÍÀ¸·Î ¾Ë°í ÀÖ´Ù. ¾ÐÃà·üÀº bzipÀÌ bzip2º¸´Ù Á¶±Ý ÁÁ´Ù.
¡Ü ½ÃÀÛÇϸç... Áö±Ý °¡Àå ´ëÁßÀûÀ¸·Î ¾²ÀÌ´Â ºñ¼Õ½Ç(Lossless) ¾ÐÃà ¹æ½ÄÀº DBC¹æ½ÄÀÌ´Ù. ¿ì¸® ¸»·Î´Â »çÀü½Ä ¹æ½ÄÀ̶ó°íµµ ºÒ¸°´Ù. °¡Àå Å« Ư¡Àº ³ôÀº ¾ÐÃà·ü¿¡ ºÒ±¸ÇÏ°í ºü¸¥ ¼Óµµ¸¦ °¡Áö°í ÀÖ´Ù´Â °ÍÀÌ´Ù. óÀ½¿¡ ³ª¿Â »çÀü½Ä ¹æ½ÄÀº Æ®¸®¸¦ ã¾Æ°¡´Â ¹æ½ÄÀ¸·Î »çÀüÀ» ±¸ÃàÇßÁö¸¸, ¿äÁòÀº ÇؽÃ(hash)¹æ½ÄÀ» »ç¿ëÇÑ´Ù. hash¹æ½ÄÀ» ¾µ °æ¿ì °ÅÀÇ ¼±Çü¾Ë°í¸®ÁòÀÌ´Ù. »çÀü½Ä ¹æ½ÄÀ̶õ Çѹø ³ª¿Â ´Ü¾î(word)°¡ ¶Ç Çѹø ³ª¿ÔÀ»¶§ »çÀü¿¡ ÀÖ´Â À妽º¸¦ ´ë½Å ÀúÀåÇÏ´Â ÇüÅÂÀÌ´Ù. »çÀü±¸Ãà¹æ½Ä°ú °°Àº ´Ü¾î¸¦ ã¾Æ³»´Â ¹æ¹ýÀÌ ±â¼úÀÌ´Ù. ÀÌ ¹æ½ÄÀº ÇöÁ¸ÇÏ´Â ºñ¼Õ½Ç ¾ÐÃàÀÇ ´ëºÎºÐÀ» Â÷ÁöÇÏ°í ÀÖ°í, ¼ö¸¹Àº ƯÇã°¡ °É·Á ÀÖ´Ù. ±×·¯³ª ÀÌ ¹æ½ÄÀÌ °¡Àå ³ôÀº ¾ÐÃà·üÀ» ³ªÅ¸³»´Â °ÍÀÌ ¾Æ´Ï´Ù. ¿©±â¿¡ ´ëÇ×ÇÏ´Â ÇÑ ¾Ë°í¸®ÁòÀÌ ÀÖÀ¸´Ï, ±×°ÍÀÌ ¹Ù·Î bzip(bzip2)ÀÌ´Ù.
¡Ü BzipÀÇ °³¿ä BzipÀº GzipÀÇ À̸§À» ¸ð¹æÀûÀ¸·Î ÁöÀº °Í °°´Ù. Bzip¿¡¼ ¾²°í ÀÖ´Â ¹æ½ÄÀº Block-Sorting ¾Ë°í¸®ÁòÀÌ´Ù. ÀϹÝÀûÀ¸·Î ÀÌ ¹æ½ÄÀº Gzipº¸´Ù´Â ³ôÀº ¾ÐÃà·üÀ» ³ªÅ¸³½´Ù. ƯÈ÷ ÀϺκп¡¼´Â »ó´çÇÑ ¾ÐÃà·üÀ» ³ªÅ¸³½´Ù. ±×·±µ¥ ÀÌ ¹æ½ÄÀÌ ³Î¸® ¾²ÀÌÁö ¾Ê´Â ÀÌÀ¯´Â ¼Óµµ°¡ »ó´çÈ÷ ´À¸®´Ù´Â °ÍÀÌ´Ù. ÀÌ°ÍÀº ÀÎÄÚµù°ú µðÄÚµù µÎ °÷¿¡¼ ¸ðµÎ ³ªÅ¸³´Ù. GzipÀÇ °æ¿ì´Â Time complexity°¡ ´ëüÀûÀ¸·Î O(n)ÀÌ´Ù. ±×·¯³ª BzipÀÇ °æ¿ì¿¡´Â ÃÖ¾ÇÀÇ »óȲ(Worst case)¿¡¼´Â O(n^2 * log(n))ÀÌ ³ª¿Â´Ù. ¹°·Ð ÀÌ·± °æ¿ì´Â °ÅÀÇ ¾ø´Ù. ÀÌÁ¦ BzipÀÇ ¼¼°è·Î µé¾î°¡ º¸ÀÚ.
¡Ü Bzip ¾Ë°í¸®Áò BzipÀÇ ±âº» ¾Ë°í¸®ÁòÀº ¾ÐÃàÀÌ ¾Æ´Ï´Ù. ÀÌ°Ô ¹«½¼ ¼Ò¸®Àΰ¡ ÇÏ´Â »ç¶÷µµ ÀÖÀ» °ÍÀÌ´Ù. Bzip¿¡¼ ¾²´Â Block-sorting ¾Ë°í¸®ÁòÀº º¯È¯(Transform)ÀÌ´Ù. Áï ½º½º·Î´Â ¾ÐÃàÀ» ÇÏÁö ¸øÇÑ´Ù´Â °ÍÀÌ´Ù. ´Ü¼øÈ÷ ºí·°À» ´Ù¸¥ ÇüÅ·Πº¯È¯½ÃÅ°´Â °ÍÀÌ´Ù. ±×·¯¸é ±× º¯È¯µÈ ºí·°À» ±âº»ÀûÀÎ ¾ÐÃà¹æ½ÄÀ¸·Î ¾ÐÃàÇÑ´Ù. ¿©±â¼ ±âº»ÀûÀ̶ó´Â °ÍÀº Gzip°ú °°Àº Á» ¹ßÀü(?)µÈ ¹æ½ÄÀÌ ¾Æ´Ï¶ó ÇãÇÁ¸¸ ÄÚµå ¶Ç´Â »ê¼ú ÄÚµù¹æ½ÄÀ¸·Î ¾ÐÃàÇÑ´Ù´Â °ÍÀÌ´Ù. < ÃÊ±â ºí·° > --> <ºí·° ¼ÒÆà º¯È¯ > --> <Å¥¸¦ ÀÌ¿ëÇÑ º¯È¯> --> <¾ÐÃà> ¹°·Ð µðÄÚµùÀº À§ÀÇ ¿ª¼øÀÌ´Ù. (±º´ë½Ä °°±º¿ä... ^^) ÃÊ±â ºí·°¿¡¼ ºí·° ¼ÒÆà º¯È¯À» ÇÏ°Ô µÇ¸é Å©±â´Â
±×´ë·Î°¡ µÈ´Ù. ¾Æ´Ï´Ù. Á» ´Ã¾î³ª°Ô µÈ´Ù. ¿Ö³ÄÇÏ¸é ¿ªº¯È¯À» Çϸé
Á¦´ë·ÎµÈ ºí·°ÀÌ ³ª¿ÀÁö ¾Ê´Â´Ù. ºí·°ÀÌ ·ÎÅ×ÀÌÆ®µÈ »óÅ·Π³ªÅ¸³´Ù.
±×°ÍÀ» º¸Á¤Çϱâ À§ÇÑ Á¤¼öÇü Çì´õ°¡ ÇÊ¿äÇÏ´Ù. ÀÌ°Í¿¡ ´ëÇÑ °ÍÀº
¹Ø¿¡ ³»¿ëÀ» º¸¸é ÀÌÇØÇÒ ¼ö ÀÖÀ» °ÍÀÌ´Ù. ¡Ø ÁÖÀÇ : ¹Ø¿¡¼ ¼³¸íÇÏ´Â °Í Áß Á·Π¿Å±ä´ÙµçÁö ¿ì·Î ¿Å±ä´Ù´Â °ÍÀº rotate¸¦ ¶æÇÏ´Â °ÍÀÌ´Ù. ¿¹) 1234¸¦ Á·Π¿Å±è
=> 2341 ±×·¯¸é Block-Sorting¿¡´ëÇؼ ÀÚ¼¼È÷ ¾Ë¾Æº¸ÀÚ. ¿¹½Ã ¹®Àå) This is his dog. À§ÀÇ ¹®ÀåÀ» Çѹø º¸ÀÚ. ÀÌ ¹®ÀåÀ» Block-sorting ¾Ë°í¸®ÁòÀ¸·Î º¯È¯À» Çغ¸ÀÚ. ¿Ö ÀÌ·± À¯Ä¡ÇÑ ¹®ÀåÀ» ¾²´ÂÁö´Â ÇÊÀÚµµ ¸ð¸¥´Ù. ÇϳªÀÇ ÀÌÀ¯¸¦ µéÀÚ¸é ¡®is¡¯°¡ ¿©·¯¹ø ³ª¿Â´Ù´Â °Í ÀÌ´Ù. This is his dog. This is his dog. À̶ó´Â ¹®ÀåÀ» À§¿Í °°ÀÌ ¹ú·Á³õ´Â´Ù. ¹ú·Á ³õ´Â ¹æ¹ýÀº ¹®ÀåÀ» ÇÑľ¿ Á·Π¿Å±â´Â °ÍÀÌ´Ù. ÀÚ ±× ´ÙÀ½Àº °¡Àå ·Îµå°¡ ¸¹ÀÌ °É¸®´Â °ÍÀÌ´Ù. À§ÀÇ ¹®ÀåÀ» ¼ÒÆ®ÇÑ´Ù. (--;;) ÆíÀÇ»ó A-Z, a-z, ¡® ¡®, ¡®.¡¯ÀÇ ¼ø¼¶ó°í °¡Á¤ÇÏÀÚ... (^^) This
is his dog. À§ÀÇ °á°ú´Â ¼ÒÆÃÇÑ °á°úÀÌ´Ù. ¸Ó¸®·Î ÇÒ·Á´Ï »ó´çÈ÷ °ñÄ¡ ¾ÆÆâ´Ù. ±×·¯ÀÚ°í ÇÁ·Î±×·¥ Â¥±â´Â ±×·¸°í... ÀÌÁ¦ ÀÌ °á°ú¸¦ ºÐ¼®Çغ¸ÀÚ. Lossless ¾ÐÃà(º¯È¯)ÀÓÀ» ¿©±â¼ Áõ¸íÇÏ°íÀÚ ÇÑ´Ù. °¢ ¹®ÀåÀÇ ³¡ ¹®ÀÚ¸¸À» ÃëÇغ¸ÀÚ. ´ä(º¯È¯ÇÑ °á°ú) => ._o_Th_hdiiisssg ÀÌ ¹®À常 ÀÖÀ¸¸é ¡°This is his dog.¡±À̶õ ¹®ÀåÀ» Àç»ýÇÒ ¼ö ÀÖ´Ù. ¹°·Ð ¡°is his dog.This¡±¶ó´Â ¹®ÀåÀÌ ³ª¿Ã¼öµµ ÀÖÁö¸¸, Á¿ì·Î ¿Å±â¸é ¿ø·¡ ¹®ÀåÀÌ Àç»ýµÈ´Ù. ¡Ø ¿©±â¼ ¤°í ³Ñ¾î°¥ °ÍÀÌ ÀÖ´Ù. º¯È¯µÈ °á°úÀÇ °¢°¢ÀÇ ¹®ÀÚÀÇ °¹¼ö´Â º¯È¯µÇ±â ÀüÀÇ ¹®ÀÚÀÇ °¹¼ö¿Í °°´Ù´Â °ÍÀÌ´Ù. ÀÌ°ÍÀ» ÀÌÇØÇؾ߸¸ ´ÙÀ½À¸·Î ³Ñ¾î°¥ ¼ö ÀÖ´Ù. ÀǽÉÀÌ ³ª¸é Á÷Á¢ ¼¼¾î º¸±â ¹Ù¶õ´Ù. º¯È¯µÇ±â ÀüÀÇ ¹®Àå¿¡¼´Â ¡®i¡¯ÀÇ ¼ö´Â 3°³ÀÌ´Ù. º¯È¯µÈ ÈÄ¿¡µµ 3°³ÀÌ´Ù. Àç»ý¹æ¹ýÀ» ¾Ë¾Æº¸ÀÚ. ¹°·Ð ¡°This is his dog.¡±À̶õ ¹®ÀåÀº ÀÌÁ¦ ¸ð¸£´Â °ÍÀÌ´Ù. ´ÜÁö ¾Ë°í ÀÖ´Â °ÍÀº ¡°º¯È¯µÈ °á°ú¡±ÀÎ ¡°._o_Th_hdiiisssg¡± ÀÌ´Ù. <Ç¥ 1>¿¡ ³»¿ëÀ» ºô¸®¸é ¾Æ·¡¿Í °°´Ù. ¡®-¡¯ºÎºÐÀº ÇöÀç ¸ð¸£´Â °ÍÀÌ´Ù. --------. À§ÀÇ Ç¥¿Í °°ÀÌ ³ª¿Â´Ù´Â °ÍÀº ¾Õ¿¡¼
ÇÑ º¯È¯À» ºÃÀ»¶§ ½±°Ô ³ª¿Â´Ù. ¿ì¸®´Â ¼ÒÆÃÇÑ ½ºÆ®¸µµéÀÇ ³¡ºÎºÐ¸¸À»
ÃëÇß¾ú´Ù. ±×·¯¹Ç·Î À§ÀÇ Ç¥´Â <Ç¥ 1>¿¡¼ °¢ ÁÙÀÇ ³¡ÀÚ¸¸
³²±â°í Áö¿î °á°ú ÀÌ¸ç ¡°º¯È¯µÈ °á°ú¡±¸¦ ÀÌ¿ëÇØ ½±°Ô ¸¸µé ¼ö
ÀÖ´Ù. ÀÌ°ÍÀº ¹«¾ùÀ» ÀǹÌÇϴ°¡? À§ÀÇ Ç¥¿¡¼ ¾ÕºÎºÐÀ» ¸ðµÎ ä¿ï ¼ö ÀÖ´Ù´Â °ÍÀ» ÀǹÌÇÑ´Ù. À§ÀÇ <Ç¥ 2>ÀÇ ¹®ÀåµéÀº Á¤·ÄµÈ ¹®ÀåµéÀÌ´Ù. ¿Ö³ÄÇϸé Á¤·ÄÇÑ ´ÙÀ½ ³¡ÀÚ¸¸À» ÃëÇ߱⠶§¹®ÀÌ´Ù. °¢ ¹®ÀÚÀÇ °¹¼ö¸¦ ¾Ë°í Á¤·ÄÀÌ µÇ¾î ÀÖÀ¸¹Ç·Î ... T-------. <Ç¥ 3> ¾ÕºÎºÐÀº Á¤·ÄµÈ ¼ø¼°¡ µÈ´Ù. Áï <Ç¥ 3>°ú °°Àº °á°ú¸¦ ¾òÀ» ¼ö ÀÖ´Ù. ÀÌ ¹®ÀÚ¿µéÀ» ¿ì·Î ÇÑľ¿ ¿Å±â¸é, .T------- <Ç¥ 4> ÀÌ ºÎºÐÀÌ ¾î·Á¿î ºÎºÐÀÌ´Ù. Â÷±ÙÂ÷±Ù »ý°¢ÇØ º¸±æ ¹Ù¶õ´Ù. ¡®_¡¯À» º¸ÀÚ. ¡®_¡¯Àº ¹®ÀÚ¿¿¡ 3°³°¡ ÀÖ´Ù. À§¿¡¼ º¸¸é (1) (2) (3)ÀÌ _À¸·Î ½ÃÀ۵ȴÙ. (1) (2) (3)À» ³õ°í º¸¸é Á¤·ÄÀÌ µÇ¾îÀÖÀ¸¸ç ÀÌ°ÍÀº Ç×»ó ±×·¸´Ù´Â °ÍÀ» ¾Ë ¼öÀÖ´Ù. (¹Ø¿¡¼ ´õ »ý°´ÇØ º¸ÀÚ.) ¿Ö³ÄÇϸé 2¹øÀç Ä®·³ÀÌ Á¤·ÄµÇ¾î Àֱ⠶§¹®ÀÌ´Ù. (1) (2) (3)À» °¢°¢ (a) (b) (c)¿¡ ´ëÀÀ½ÃŲ´Ù. ±×·³ ÀÌÁ¦ ¿ªº¯È¯À» Çغ¸ÀÚ. ù ¶óÀÎÀ» ÀÌ¿ëÇؼ .T------°¡ ³ª¿Â´Ù. µÎ¹ø° Ä®·³ÀÇ T´Â ¹Ø¿¡ÀÖ´Â Th------¿¡ ´ëÀÀµÈ´Ù.
±×·¯¹Ç·Î .Th-----¶ó°í °áÁ¤ÇÒ ¼ö ÀÖ´Ù. ÀÌÁ¦ h´ÙÀ½À» °áÁ¤ÇØ¾ß ÇÑ´Ù. ¿ì¸®´Â (¤¡)À» º¸°í T´ÙÀ½¿¡ h°¡ ³ª¿Â´Ù´Â °ÍÀ» ¾Ë¾Ò´Ù. ±× ´ÙÀ½Àº hÀÌÈÄ¿¡ ¹«¾ùÀÌ ³ª¿À³Ä ÀÌ´Ù. (¤¡)ÀÇ h´Â °°Àº Ä®·³¿¡¼ µÎ¹ø°·Î À§Ä¡ÇÏ°í ÀÖ´Ù. ÀÌ ºí·°Àº Á¤·ÄµÇ¾î ÀÖ´Â »óÅÂÀ̹ǷΠ(A) (B)¿¡¼ (B)¸¦ ÅÃÇÏ°Ô µÈ´Ù. Àß »ý°¢ÇØ º¸¸é (A) (B)ÀÇ hµµ (2)¿Í (¤¡)ÀÇ ¼ø¼´ë·Î Á¤·ÄµÇ°Ô µÈ´Ù. Á» ´õ ÀÌÇظ¦ µ½±â À§ÇØ ¿¹Á¦¸¦ º¸¸é * his
dog.... => is dog..... Áï ¾ÕÀÇ ¹®ÀÚ°¡ °°±â ¶§¹®¿¡ ±×°ÍÀ» »©µµ °á°ú´Â °°´Ù.(ÀÌ ºÎºÐÀÌ ÇÙ½ÉÀÌ´Ù.) ±×·¯¹Ç·Î (2)¿Í (¤¡)¿¡¼ ¾ÕÀÇ ÇѱÛÀÚ¸¦ »« °á°ú°¡ (A),(B)°¡ µÈ´Ù. (Çò°¥¸®Áö ¸»ÀÚ, ¼ÒÆ®ÀÇ ±âÁØÀº 2¹ø° Ä®·³ ºÎÅÍÀÌ´Ù, 1¹ø° Ä®·³Àº ¿ì·Î ¿Å°Ü¼ ¾ÕÀ¸·Î ³ª¿À°Ô µÈ °ÍÀÏ »ÓÀÌ´Ù.) ±×·¯¹Ç·Î h ´ÙÀ½¿¡´Â i°¡ ³ª¿Â´Ù°í ÇÒ ¼ö ÀÖ´Ù. ÀÌ·±½ÄÀ¸·Î Çسª°¡¸é This is his dogÀ¸·Î µÈ´Ù. À̶§ Th°¡ óÀ½ ½ÃÀÛÀ̶ó´Â °ªÀ» Ãß°¡·Î ÁÖ¸é This is his dog. À̶ó´Â ¹®ÀåÀÌ Àç»ýµÈ´Ù. °á±¹ Losslessº¯È¯ÀÓÀ» Áõ¸íÇÏ´Â µ¿½Ã¿¡ ¿ªº¯È¯À» »ìÆ캸¾Ò´Ù.
¡Ü ÀÌÁ¦ ¾ÐÃàÀ» Çغ¸ÀÚ ._o_Th_hdiiisssg À§ÀÇ ÇüÅ·Πº¯È¯ÀÌ µÇ¾ú´Ù. °°Àº ¹®ÀÚ°¡ ÀÚÁÖ ¹Ýº¹µÊÀ» ¾Ë ¼ö ÀÖ´Ù. ÀÌ°ÍÀ» ÀÌ¿ëÇÒ ¼ö ÀÖ´Ù. ÀÌ º¯È¯ÀÇ Æ¯Â¡Àº °°Àº ¹®ÀÚ°¡ ¹Ýº¹ ¶Ç´Â Çѹø ³ª¿Â ±Ùó¿¡¼ ³ª¿Ã È®·üÀÌ ¸Å¿ì Å©´Ù´Â °ÍÀÌ´Ù. ±×·¯¹Ç·Î ´ÙÀ½°ú °°Àº ÀÏÁ¾ÀÇ Å¥(ÁøÂ¥ Å¥´Â ¾Æ´Ï´Ù.)¸¦ ¸¸µç´Ù. ÃʱâÄ¡´Â ¾Æ½ºÅ°Äڵ尡 ¼ø¼´ë·Î µé¾î°¡ ÀÖ´Ù. [A][B][C]....[a][b][c]....[.][_]¿Í °°ÀÌ µé¾î°¡ ÀÖ´Ù°í ÇÏÀÚ. óÀ½¿¡´Â ¡®.¡¯À» ÀÎÄÚµùÇÏÀÚ. ¡®.¡¯Àº 0ºÎÅÍ
½ÃÀÛÇÑ´Ù°í Çϸé Å¥ÀÇ 52¹ø°¿¡ ÀÖ´Ù. ±×·¯¹Ç·Î °ªÀº 52ÀÌ´Ù. [.][A][B][C]...[a][b][c]....[_] ´ÙÀ½Àº _ÀÌ°í ±×´ÙÀ½Àº oÀÌ´Ù. ´ÙÀ½¿¡ _ÀÌ ³ª¿À¸é
°ªÀÌ 1À̵ȴÙ. ÀÌ°ÍÀº ÇãÇÁ¸¸ ÄÚµùÀ̳ª »ê¼úÄÚµùÀ» ÀÌ¿ëÇÏ¸é µÈ´Ù. Áï ¼ýÀÚ°¡ ³·À»¼ö·Ï ªÀº ºñÆ®¼ö¸¦ ¹èÁ¤ÇÏ°í ³ôÀº ¼ýÀÚ´Â ±ä ºñÆ®¼ö¸¦ ÇÒ´çÇÑ´Ù. ±×·¯¸é ¾ÐÃàÀÌ µÈ´Ù. ¸¸¾à BAAAACCCCDDDD°¡ ÀÖ´Ù°í Çغ¸ÀÚ. óÀ½ B´Â 1ÀÌ µÇ°í ´ÙÀ½ A´Â 1ÀÌ´Ù. ±× ´ÙÀ½
AµéÀº 0ÀÌ°í, C´Â 2°¡ µÈ´Ù. ¹®ÀÚ
ÇöÀç Å¥ »óÅ °ª ÀÌ °á°ú¸¦ °ªÀ» ÇãÇÁ¸¸(bzip2)À̳ª »ê¼úÄÚµù(bzip)À¸·Î ÀÎÄÚµùÇÑ ´ÙÀ½ ÀúÀåÇÑ´Ù.
¡Ü Bzip... BzipÀÇ ¾ÐÃà °úÁ¤À» »ìÆ캸ÀÚ.(bzip2µµ ºñ½ÁÇÒ °ÍÀÌ´Ù.) 1. ºí·°À» ÀÐ¾î¼ ¹®ÀÚ¿À» ¸¸µç´Ù. (ºí·°¿¡ ´ëÇÑ Æ÷ÀÎÅÍ°¡ ¹®ÀÚ¿ÀÌ µÈ´Ù. <- ´ç¿¬ÇÏ´Ù. ¿Ö³ÄÇϸé ÀÏÀÏÀÌ ¸ðµç ¹®ÀÚ¸¦ ¸¸µç´Ù¸é ¸Þ¸ð¸®´Â ºÎÁ·ÇÒ °ÍÀÌ´Ù. ºí·°Å©±â°¡ 100k¶ó°í °¡Á¤ÇÏ°í °è»êÇØ º¸¶ó) ¨ç (a) Spotblock
(ºí·° ±ºµ¥±ºµ¥¸¶´Ù °ªÀ» º¯Çü½ÃŲ´Ù. ÀÌ°ÍÀº Ȥ½Ã ¸ð¸¦
¾öû³
¡á Techniques in bzip(ÀÚ¼¼ÇÑ °ÍÀº bzip ¼Ò½º¸¦ º¸±æ ¹Ù¶õ´Ù.) SpotBlock : ºí·°ÀÇ Áß°£Áß°£ °ªÀ» º¯Çü½ÃŲ´Ù. ±×·¡¾ß Ȥ½Ã ¸ð¸¦ ÇÁ·Î±×·¥ÀÌ Á×Àº »óÅÂ¿Í ºñ½ÁÇÑ »óȲÀ» ¹þ¾î³ª±â À§ÇؼÀÌ´Ù. ÇÑ°¡Áö ¿¹¸¦ µé¸é A·Î¸¸ µÈ ÆÄÀÏÀ» »ý°¢ÇØ º¸ÀÚ. ÀÌ ÆÄÀÏ¿¡ Block-Sorting¾Ë°í¸®ÁòÀ» Àû¿ëÇϸé, AAAAAAAAAAAAAAAAAA......A Áï °¢ ÁÙº°·Î ¼·Î ¿ìÀ§°¡ °áÁ¤µÇÁö ¾Ê´Â´Ù. ±×·¯³ª ÄÄÇ»ÅÍ´Â ¹Ùº¸À̹ǷÎ, ¿ì¿ÀÌ °¡Áú¶§ ±îÁö ºñ±³ÇÑ´Ù. Áï ÇÑ ¶óÀÎÀ» ºñ±³Çϴµ¥ ºí·°À» óÀ½ºÎÅÍ ³¡±îÁö °Ë»öÇÑ´Ù. ¿©±â¿¡ Quick sort¾Ë°í¸®ÁòÀÌ ´ëü·Î n*log(n)¹øÀ» ºñ±³ÇϹǷÎ, n*n*log(n)ÀÌ µÈ´Ù. ºí·°ÀÌ 100k¸¸ µÇµµ100k*100k*log(100k)=10000m*5=50 billion=¾à 500¾ïÀÇ ÀÌ·ÐÀûÀÎ ºñ±³È½¼ö°¡ ³ª¿Â´Ù. ±×·¯³ª ÀÌ¿Í °°À» °æ¿ì quick-sort°¡ worst case¿¡¼ µ¿ÀÛÇÒ ¼ö ÀÖÀ¸¹Ç·Î ´õ¿í ÃÖ¾ÇÀÇ »óȲÀÌ µÈ´Ù. Quicksort with shell sort : Radix-sort before quicksort : AB..... Áï AB·Î ½ÃÀÛÇÏ´Â °ÍÀ» ¹°í, BC·Î ½ÃÀÛÇÏ´Â °ÍÀ» ¹¾î ³õ´Â´Ù. ±×·± ´ÙÀ½ AB·Î ¹ÀÎ °Íµé³¢¸®, BC·Î ¹ÀÎ °Íµé³¢¸® °¢°¢ quick-sort¸¦ ÇÑ´Ù. Modify block after Radix-sort ÀÌ·±½ÄÀ¸·Î AB·Î ¹ÀÎ ºí·°ÀÌ ÀÖÀ¸¸é, ÀÌ°ÍÀ»
ÀÏ´Ü ¼ÒÆ®ÇÑ´Ù. ±×·±´ÙÀ½ AB´ÙÀ½ÀÇ ¹®ÀÚ 2°³¸¦ 0ºÎÅÍ 65535±îÁö
½á³Ö´Â´Ù. 65535¸¦ ³Ñ¾î¼¸é 65535¸¦ ½á³Ö´Â´Ù. ±×·¯¸é ´Ù¸¥
XX·Î ¹ÀÎ ºí·°À» ¼ÒÆ®ÇÒ ¶§ ºñ±³ ºñ¿ëÀÌ Àû°Ô µç´Ù. Small first, Large Last! : Array Alignment! : º¯ÇüµÈ »ê¼úÄÚµù »ê¼úÄÚµù¿¡ [OFF],[ON],1,2,3,4,...255ÀÇ ¼øÀ¸·Î
°¡ÁßÄ¡¸¦ µÐ´Ù. [OFF][1][2].....
=> 0 1 2 ...
¡Ü ¸¶Ä¡±âÀü »ç°úÀÇ ¸»¾¸ ½ÃÀÛÇϱâÀü¿¡¼ º¸¿©ÁØ ¾ÐÃà °á°ú´Â È£±â½É(?) À¯¹ßÀ» À§Çؼ º»ÀÎÀÌ ÀǵµÀûÀ¸·Î ³ÖÀº °ÍÀÌ´Ù. ¹°·Ð bzipÀ» ½áº¸½Å ºÐµéÀº ´À³¢°ÚÁö¸¸... ¾ÐÃà·üÀº ÁÁ¾Æµµ ¾ÐÃàÇϴµ¥ µå´Â ½Ã°£Àº gzip¿¡ ºñÇϸé Àå³ÀÌ ¾Æ´Ï´Ù. °É¸° ½Ã°£À» °°ÀÌ ½á¾ß µÇ³ª, Èï¹Ì À¯¹ßÀ» À§ÇØ ÀϺη¯ ¾²Áö ¾Ê¾ÒÀ½À» ¾çÇØÇϱ⠹ٶõ´Ù.
¡Ü ¸¶Ä¡¸ç.... ¼ö¹Ú °ÑÇӱ⠽ÄÀ¸·Î Çѹø »ìÆ캸¾Ò´Ù. ¹°·Ð ÀúÀÇ ÀÛ¹® ½Ç·Â ºÎÁ·À¸·Î ÀÌÇØ°¡ ¿Ïº®È÷ µÇÁö´Â ¾Ê¾ÒÀ» Å×Áö¸¸, ±×³É ÃÖ±Ù(?)¿¡ ³ª¿Â ¾Ë°í¸®ÁòÀ» ´Ü¼øÈ÷ ÀÌÇØÇÑ´Ù´Â Â÷¿øÀ¸·Î º¸¾ÒÀ¸¸é ÇÑ´Ù. ¹°·Ð ¿©±â¼ ¹àÈù °ÍÀ¸·Î bzipÀ» ±¸¼ºÇÒ ¼ö ÀÖ´Ù. ±×·¯³ª ±ºµ¥ ±ºµ¥ ¾ÐÃà·üÀ» ³ôÀ̱â À§ÇÑ Å×Å©´ÐÀÌ ÀÖ´Ù. ƯÈ÷ À§¿¡¼ ¹®ÀåµéÀ» Á¤·ÄÇÏ´Â °Í¿¡ ´ëÇÑ Å×Å©´ÐÀÌ Áß¿äÇÏ´Ù.. bzip¿¡¼ ºí·° Å©±â´Â ÃÖ´ë 900k±îÁö ÁöÁ¤ÇÒ ¼ö ÀÖ´Ù. Çѹø 900kÀÇ ±æÀÌÀÇ ¹®ÀÚ¿À» Á¤·ÄÇÑ´Ù°í Çغ¸ÀÚ. ¾Æ¸¶ ¾öû³ ½Ã°£ÀÌ °É¸± °ÍÀÌ´Ù. Á¦ ¾Æ¹«¸® ºü¸¥ Quick-Sort¸¦ ½áµµ n*log(n)¾Ë°í¸®ÁòÀÌ´Ù. °Å±â´Ù ¹®ÀÚ¿ÀÇ ±æÀÌ°¡ °öÇØÁø´Ù. ÀÌ°ÍÀ» Á» ´õ ºü¸£°Ô ÇÏ´Â ¹ýµµ ÀÖ´Ù. ±× ¹æ¹ýÀº Bzip¼Ò½º¿¡ ÀÖ´Ù. ±×·³ BzipÀ¸·Î ´õ ¸¹Àº °ø°£À» È®º¸Çϱ⠹ٶó¸ç.... Copyleft (c) 1997-1999 by Á¤¿ìÀç |