Introdunction to Bzip

    Á¤¿ìÀç / E-mail:jwj95@nownuri.net

 

 

¡Ü ½ÃÀÛÇϱâ Àü¿¡...

    linux-2.0.30.tar     25108480
    linux-2.0.30.tar.gz   6199356 (24.6%)
    linux-2.0.30.tar.bz   4998035 (19.9%)

    ÀÌ ±ÛÀº °£´ÜÈ÷ 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
              1234¸¦ ¿ì·Î ¿Å±è =>  4123
              ¶ÇÇÑ °ø¹éÀº ¶§¿¡ µû¶ó ¡®_¡¯À¸·Î ´ëüÇؼ­ ¾´´Ù.

    ±×·¯¸é Block-Sorting¿¡´ëÇؼ­ ÀÚ¼¼È÷ ¾Ë¾Æº¸ÀÚ.

         ¿¹½Ã ¹®Àå) This is his dog.

    À§ÀÇ ¹®ÀåÀ» Çѹø º¸ÀÚ. ÀÌ ¹®ÀåÀ» Block-sorting ¾Ë°í¸®ÁòÀ¸·Î º¯È¯À» Çغ¸ÀÚ. ¿Ö ÀÌ·± À¯Ä¡ÇÑ ¹®ÀåÀ» ¾²´ÂÁö´Â ÇÊÀÚµµ ¸ð¸¥´Ù. ÇϳªÀÇ ÀÌÀ¯¸¦ µéÀÚ¸é ¡®is¡¯°¡ ¿©·¯¹ø ³ª¿Â´Ù´Â °Í ÀÌ´Ù.

        This is his dog.
        his is his dog.T
        is is his dog.Th
             .
             .
             .
        .This is his dog

    This is his dog. À̶ó´Â ¹®ÀåÀ» À§¿Í °°ÀÌ  ¹ú·Á³õ´Â´Ù. ¹ú·Á ³õ´Â ¹æ¹ýÀº ¹®ÀåÀ» ÇÑÄ­¾¿ Á·Π¿Å±â´Â °ÍÀÌ´Ù. ÀÚ  ±× ´ÙÀ½Àº °¡Àå ·Îµå°¡ ¸¹ÀÌ °É¸®´Â °ÍÀÌ´Ù. À§ÀÇ ¹®ÀåÀ» ¼ÒÆ®ÇÑ´Ù. (--;;)

    ÆíÀÇ»ó A-Z, a-z, ¡® ¡®, ¡®.¡¯ÀÇ ¼ø¼­¶ó°í °¡Á¤ÇÏÀÚ... (^^)

            This is his dog.
            dog.This is his_
            g.This is his do
            his dog.This is_
            his is his dog.T
            is dog.This is h
            is his dog.This_
            is is his dog.Th
            og.This is his d
            s dog.This is hi
            s his dog.This i
            s is his dog.Thi
            _dog.This is his
            _his dog.This is
            _is his dog.This
            .This is his dog
            <Ç¥ 1>

    À§ÀÇ °á°ú´Â ¼ÒÆÃÇÑ °á°úÀÌ´Ù. ¸Ó¸®·Î ÇÒ·Á´Ï »ó´çÈ÷ °ñÄ¡ ¾ÆÆâ´Ù. ±×·¯ÀÚ°í ÇÁ·Î±×·¥ Â¥±â´Â ±×·¸°í... ÀÌÁ¦ ÀÌ °á°ú¸¦ ºÐ¼®Çغ¸ÀÚ. Lossless ¾ÐÃà(º¯È¯)ÀÓÀ» ¿©±â¼­ Áõ¸íÇÏ°íÀÚ ÇÑ´Ù.

    °¢ ¹®ÀåÀÇ ³¡ ¹®ÀÚ¸¸À» ÃëÇغ¸ÀÚ.

          ´ä(º¯È¯ÇÑ °á°ú) => ._o_Th_hdiiisssg

    ÀÌ ¹®À常 ÀÖÀ¸¸é ¡°This is his dog.¡±À̶õ ¹®ÀåÀ» Àç»ýÇÒ ¼ö ÀÖ´Ù.  ¹°·Ð ¡°is his dog.This¡±¶ó´Â ¹®ÀåÀÌ ³ª¿Ã¼öµµ ÀÖÁö¸¸, Á¿ì·Î ¿Å±â¸é ¿ø·¡ ¹®ÀåÀÌ Àç»ýµÈ´Ù.

    ¡Ø ¿©±â¼­ ¤°í ³Ñ¾î°¥ °ÍÀÌ ÀÖ´Ù. º¯È¯µÈ °á°úÀÇ °¢°¢ÀÇ ¹®ÀÚÀÇ °¹¼ö´Â º¯È¯µÇ±â ÀüÀÇ ¹®ÀÚÀÇ °¹¼ö¿Í °°´Ù´Â °ÍÀÌ´Ù. ÀÌ°ÍÀ» ÀÌÇØÇؾ߸¸ ´ÙÀ½À¸·Î ³Ñ¾î°¥ ¼ö ÀÖ´Ù. ÀǽÉÀÌ ³ª¸é Á÷Á¢ ¼¼¾î º¸±â ¹Ù¶õ´Ù. º¯È¯µÇ±â ÀüÀÇ ¹®Àå¿¡¼­´Â ¡®i¡¯ÀÇ ¼ö´Â 3°³ÀÌ´Ù. º¯È¯µÈ ÈÄ¿¡µµ 3°³ÀÌ´Ù.

    Àç»ý¹æ¹ýÀ» ¾Ë¾Æº¸ÀÚ. ¹°·Ð ¡°This is his dog.¡±À̶õ ¹®ÀåÀº ÀÌÁ¦ ¸ð¸£´Â °ÍÀÌ´Ù. ´ÜÁö ¾Ë°í ÀÖ´Â °ÍÀº ¡°º¯È¯µÈ °á°ú¡±ÀÎ ¡°._o_Th_hdiiisssg¡± ÀÌ´Ù.

    <Ç¥ 1>¿¡ ³»¿ëÀ» ºô¸®¸é ¾Æ·¡¿Í °°´Ù. ¡®-¡¯ºÎºÐÀº ÇöÀç ¸ð¸£´Â °ÍÀÌ´Ù.

               --------.
               --------_
               --------o
                   .
                   .
               --------g
            <Ç¥ 2>

    À§ÀÇ Ç¥¿Í  °°ÀÌ ³ª¿Â´Ù´Â °ÍÀº ¾Õ¿¡¼­ ÇÑ º¯È¯À» ºÃÀ»¶§ ½±°Ô ³ª¿Â´Ù. ¿ì¸®´Â ¼ÒÆÃÇÑ ½ºÆ®¸µµéÀÇ ³¡ºÎºÐ¸¸À» ÃëÇß¾ú´Ù. ±×·¯¹Ç·Î À§ÀÇ Ç¥´Â <Ç¥ 1>¿¡¼­ °¢ ÁÙÀÇ ³¡ÀÚ¸¸ ³²±â°í Áö¿î °á°ú ÀÌ¸ç ¡°º¯È¯µÈ °á°ú¡±¸¦ ÀÌ¿ëÇØ ½±°Ô ¸¸µé ¼ö ÀÖ´Ù.
    ±×·¯³ª ¿ì¸®´Â ÀÚµ¿À¸·Î ÇϳªÀÇ Á¤º¸µéÀ» ¾òÀ» ¼ö ÀÖ´Ù. º¯È¯µÇ±â ÀüÀÇ ½ºÆ®¸µ¿¡¼­ °¢ ¹®ÀÚÀÇ °¹¼ö¸¦ ¾Ë ¼ö ÀÖ´Ù. ´ç¿¬ÇÏ´Ù. º¯È¯µÈ ¹®Àå³»¿¡¼­ÀÇ °¹¼ö¿Í °°´Ù. ÀÌ°ÍÀÌ ÀÌÇØ°¡ ¾ÈµÇ¸é ¾ÕºÎºÐÀ» ´Ù½Ã »ìÆ캸±â ¹Ù¶õ´Ù.

    ÀÌ°ÍÀº ¹«¾ùÀ» ÀǹÌÇϴ°¡? À§ÀÇ Ç¥¿¡¼­ ¾ÕºÎºÐÀ» ¸ðµÎ ä¿ï ¼ö ÀÖ´Ù´Â °ÍÀ» ÀǹÌÇÑ´Ù. À§ÀÇ <Ç¥ 2>ÀÇ ¹®ÀåµéÀº Á¤·ÄµÈ ¹®ÀåµéÀÌ´Ù. ¿Ö³ÄÇϸé Á¤·ÄÇÑ ´ÙÀ½ ³¡ÀÚ¸¸À» ÃëÇ߱⠶§¹®ÀÌ´Ù.

    °¢ ¹®ÀÚÀÇ °¹¼ö¸¦ ¾Ë°í Á¤·ÄÀÌ µÇ¾î ÀÖÀ¸¹Ç·Î ...

               T-------.
               d-------_
               g-------o
               h-------_
                    .
                    .
                    .
               .--------g

            <Ç¥ 3>

    ¾ÕºÎºÐÀº Á¤·ÄµÈ ¼ø¼­°¡ µÈ´Ù.             

    Áï <Ç¥ 3>°ú °°Àº °á°ú¸¦ ¾òÀ» ¼ö ÀÖ´Ù.  ÀÌ ¹®ÀÚ¿­µéÀ» ¿ì·Î ÇÑÄ­¾¿ ¿Å±â¸é,

              .T-------
      (1)     _d-------
              og-------
      (2)     _h-------
      (¤¡)    Th
      (A)     hi
      (3)     _i
      (B)     hi
               do
               is
               is
               is
      (a)     s_
      (b)     s_
      (c)     s_
               g.

            <Ç¥ 4>

    ÀÌ ºÎºÐÀÌ ¾î·Á¿î ºÎºÐÀÌ´Ù. Â÷±ÙÂ÷±Ù »ý°¢ÇØ º¸±æ ¹Ù¶õ´Ù.

    ¡®_¡¯À» º¸ÀÚ. ¡®_¡¯Àº ¹®ÀÚ¿­¿¡ 3°³°¡ ÀÖ´Ù.  À§¿¡¼­ º¸¸é  (1) (2) (3)ÀÌ _À¸·Î ½ÃÀ۵ȴÙ. (1) (2) (3)À» ³õ°í º¸¸é Á¤·ÄÀÌ µÇ¾îÀÖÀ¸¸ç ÀÌ°ÍÀº Ç×»ó ±×·¸´Ù´Â °ÍÀ» ¾Ë ¼öÀÖ´Ù. (¹Ø¿¡¼­ ´õ »ý°´ÇØ º¸ÀÚ.) ¿Ö³ÄÇϸé 2¹øÀç Ä®·³ÀÌ Á¤·ÄµÇ¾î ÀÖ±â  ¶§¹®ÀÌ´Ù. (1) (2) (3)À» °¢°¢ (a) (b) (c)¿¡ ´ëÀÀ½ÃŲ´Ù.

    ±×·³ ÀÌÁ¦ ¿ªº¯È¯À» Çغ¸ÀÚ. ù ¶óÀÎÀ» ÀÌ¿ëÇؼ­

          .T------°¡ ³ª¿Â´Ù.

    µÎ¹ø° Ä®·³ÀÇ T´Â ¹Ø¿¡ÀÖ´Â Th------¿¡ ´ëÀÀµÈ´Ù. ±×·¯¹Ç·Î .Th-----¶ó°í °áÁ¤ÇÒ ¼ö ÀÖ´Ù.
    (T´ÙÀ½¿¡ ³ª¿À´Â ¹®ÀÚ´Â <Ç¥ 4>¸¦ ºÃÀ»¶§ h¹Û¿¡ ¾ø´Ù. ±×·¯¹Ç·Î ¿ì¸®´Â T´ÙÀ½¿¡´Â h¹Û¿¡ ÀÖÀ» ¼ö ¾øÀ¸¹Ç·Î  h¶ó°í ÇÒ ¼ö ÀÖ´Â °ÍÀÌ´Ù.)

    ÀÌÁ¦ h´ÙÀ½À» °áÁ¤ÇØ¾ß ÇÑ´Ù. ¿ì¸®´Â (¤¡)À» º¸°í T´ÙÀ½¿¡ h°¡ ³ª¿Â´Ù´Â °ÍÀ» ¾Ë¾Ò´Ù. ±× ´ÙÀ½Àº hÀÌÈÄ¿¡ ¹«¾ùÀÌ ³ª¿À³Ä ÀÌ´Ù. (¤¡)ÀÇ h´Â °°Àº Ä®·³¿¡¼­ µÎ¹ø°·Î À§Ä¡ÇÏ°í ÀÖ´Ù. ÀÌ ºí·°Àº Á¤·ÄµÇ¾î ÀÖ´Â »óÅÂÀ̹ǷΠ(A) (B)¿¡¼­ (B)¸¦ ÅÃÇÏ°Ô µÈ´Ù. Àß »ý°¢ÇØ º¸¸é (A) (B)ÀÇ hµµ (2)¿Í (¤¡)ÀÇ ¼ø¼­´ë·Î Á¤·ÄµÇ°Ô µÈ´Ù.

    Á» ´õ ÀÌÇظ¦ µ½±â À§ÇØ ¿¹Á¦¸¦ º¸¸é

          * his dog....   =>   is dog.....
            his is his...      is is his....

    Áï ¾ÕÀÇ ¹®ÀÚ°¡ °°±â ¶§¹®¿¡ ±×°ÍÀ» »©µµ °á°ú´Â °°´Ù.(ÀÌ ºÎºÐÀÌ ÇÙ½ÉÀÌ´Ù.) ±×·¯¹Ç·Î (2)¿Í (¤¡)¿¡¼­ ¾ÕÀÇ ÇѱÛÀÚ¸¦ »« °á°ú°¡ (A),(B)°¡ µÈ´Ù. (Çò°¥¸®Áö ¸»ÀÚ, ¼ÒÆ®ÀÇ ±âÁØÀº 2¹ø° Ä®·³ ºÎÅÍÀÌ´Ù, 1¹ø° Ä®·³Àº ¿ì·Î ¿Å°Ü¼­ ¾ÕÀ¸·Î ³ª¿À°Ô µÈ °ÍÀÏ »ÓÀÌ´Ù.)

    ±×·¯¹Ç·Î h ´ÙÀ½¿¡´Â i°¡ ³ª¿Â´Ù°í ÇÒ ¼ö ÀÖ´Ù.
          .Thi-------°¡ µÇ´Â °ÍÀÌ´Ù.

    ÀÌ·±½ÄÀ¸·Î Çسª°¡¸é

    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À̵ȴÙ.
    ¸¶Âù°¡Áö·Î sssÀÇ °æ¿ì¿¡´Â ù¹ø°´Â  ÀÓÀÇÀÇ °ªÀÌ ³ª¿À°í ³ª¸ÓÁö 2°³´Â 0À̵ȴÙ.
    Áï ¼ýÀÚ°¡ ³·À»¼ö·Ï ÀÚÁÖ ³ª¿Ã ¼ö ÀÖ´Ù´Â °ÍÀÌ´Ù.

    ÀÌ°ÍÀº ÇãÇÁ¸¸ ÄÚµùÀ̳ª »ê¼úÄÚµùÀ» ÀÌ¿ëÇÏ¸é  µÈ´Ù. Áï ¼ýÀÚ°¡  ³·À»¼ö·Ï ªÀº ºñÆ®¼ö¸¦ ¹èÁ¤ÇÏ°í ³ôÀº ¼ýÀÚ´Â ±ä ºñÆ®¼ö¸¦ ÇÒ´çÇÑ´Ù. ±×·¯¸é ¾ÐÃàÀÌ µÈ´Ù.

    ¸¸¾à BAAAACCCCDDDD°¡ ÀÖ´Ù°í Çغ¸ÀÚ.
    ±×¸®°í Ãʱâ Å¥´Â [A][B][C][D]°¡ µÈ´Ù.

    óÀ½ B´Â 1ÀÌ µÇ°í ´ÙÀ½ A´Â 1ÀÌ´Ù. ±× ´ÙÀ½ AµéÀº 0ÀÌ°í, C´Â 2°¡ µÈ´Ù.
    ±×¸®°í ±×´ÙÀ½ C´Â 0À̵ȴÙ. ±×·± ´ÙÀ½ D´Â 3ÀÌµÇ°í ³ª¸ÓÁö D´Â 0ÀÌ´Ù.

            ¹®ÀÚ    ÇöÀç Å¥ »óÅ        °ª
             B      [A][B][C][D]    ==> 1
             A      [B][A][C][D]    ==> 1
             A      [A][B][C][D]    ==> 0
             A      [A][B][C][D]    ==> 0
             A      [A][B][C][D]    ==> 0
             C      [A][B][C][D]    ==> 2
             C      [C][A][B][D]    ==> 0
             C      [C][A][B][D]    ==> 0
             C      [C][A][B][D]    ==> 0
             D      [C][A][B][D]    ==> 3
             D      [D][C][A][B]    ==> 0
             D      [D][C][A][B]    ==> 0
             D      [D][C][A][B]    ==> 0

    ÀÌ °á°ú¸¦ °ªÀ» ÇãÇÁ¸¸(bzip2)À̳ª »ê¼úÄÚµù(bzip)À¸·Î ÀÎÄÚµùÇÑ ´ÙÀ½ ÀúÀåÇÑ´Ù.

 

¡Ü Bzip...

    BzipÀÇ ¾ÐÃà °úÁ¤À» »ìÆ캸ÀÚ.(bzip2µµ ºñ½ÁÇÒ °ÍÀÌ´Ù.)

    1. ºí·°À» Àо ¹®ÀÚ¿­À» ¸¸µç´Ù.

      (ºí·°¿¡ ´ëÇÑ Æ÷ÀÎÅÍ°¡ ¹®ÀÚ¿­ÀÌ µÈ´Ù. <- ´ç¿¬ÇÏ´Ù. ¿Ö³ÄÇϸé ÀÏÀÏÀÌ ¸ðµç ¹®ÀÚ¸¦ ¸¸µç´Ù¸é ¸Þ¸ð¸®´Â ºÎÁ·ÇÒ °ÍÀÌ´Ù. ºí·°Å©±â°¡ 100k¶ó°í °¡Á¤ÇÏ°í °è»êÇØ º¸¶ó)

      ¨ç (a) Spotblock (ºí·°  ±ºµ¥±ºµ¥¸¶´Ù °ªÀ» º¯Çü½ÃŲ´Ù. ÀÌ°ÍÀº Ȥ½Ã ¸ð¸¦ ¾öû³­
          ¼ÓµµÀúÇϸ¦ ¿¹¹æÇϱâ À§ÇÔÀÌ´Ù.)
      ¨è ¹®ÀÚ¿­À» Block-Sorting ¾Ë°í¸®ÁòÀ¸·Î º¯ÇüÇÑ´Ù. (Transform)
      ¨é À§¿¡¼­ ¾²´ø Å¥¸¦ ÀÌ¿ëÇؼ­ ¼ýÀÚ·Î ¹Ù²Û´Ù. (<- ÁÖ·Î ³·Àº ¼ýÀÚµéÀÌ Àç»ý)
      ¨ê »ê¼úÄÚµùÀ» ÀÌ¿ëÇؼ­ ¾ÐÃàÇÑ´Ù. (¼ýÀÚ°¡ ³·À»¼ö·Ï ÀúÀå°ø°£ÀÌ Àû°Ôµç´Ù.)
      ¨ë ÆÄÀÏÀÌ ³¡³¯¶§±îÁö °è¼Ó 1-4¸¦ ¹Ýº¹.

 

¡á Techniques in bzip(ÀÚ¼¼ÇÑ °ÍÀº bzip ¼Ò½º¸¦ º¸±æ ¹Ù¶õ´Ù.)

    SpotBlock : ºí·°ÀÇ Áß°£Áß°£ °ªÀ» º¯Çü½ÃŲ´Ù. ±×·¡¾ß Ȥ½Ã ¸ð¸¦ ÇÁ·Î±×·¥ÀÌ Á×Àº »óÅÂ¿Í ºñ½ÁÇÑ »óȲÀ» ¹þ¾î³ª±â À§Çؼ­ÀÌ´Ù.  ÇÑ°¡Áö ¿¹¸¦ µé¸é A·Î¸¸ µÈ ÆÄÀÏÀ» »ý°¢ÇØ º¸ÀÚ.

    ÀÌ ÆÄÀÏ¿¡ Block-Sorting¾Ë°í¸®ÁòÀ» Àû¿ëÇϸé,

              AAAAAAAAAAAAAAAAAA......A
              AAAAAAAAAAAAAAAAAA......A
              AAAAAAAAAAAAAAAAAA......A
                       .
                       .
                       .
              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 :
    quick-sort°¡ ÀϹÝÀûÀ¸·Î °¡Àå ºü¸¥ ¾Ë°í¸®ÁòÀ̶ó°í  »ý°¢Çϱ⠽±´Ù. ¹°·Ð Á¤¼ö Á¤·Ä¿¡¼­´Â quickÀÌ shell¿¡ ºñÇØ ´ëüÀûÀ¸·Î ºü¸£´Ù. Á¤·ÄÇÒ °¹¼ö°¡ ¾ÆÁÖ ÀÛÀ»¶§´Â shellÀÌ ´õ ºü¸£´Ù.  ¶ÇÇÑ ¿©±â¼­´Â ºñ±³¿¡ ´ëÇÑ ºñ¿ëÀÌ swapº¸´Ù ÈξÀ ¸¹ÀÌ µç´Ù.  ±×·¯¹Ç·Î ºñ±³È½¼ö¸¦ ÁÙ¿©¾ß Çϴµ¥ quick-sort¸¦ ÇÏ´Ù°¡ ¾ÆÀÌÅÛÀÇ ¼ö°¡ ÀÏÁ¤ÀÌ»ó Àû¾îÁö¸é shell-sort¸¦ ÇÑ´Ù.

    Radix-sort before quicksort :
    ¾ÆÀÌÅÛÀÇ ¼ö°¡ Å©°í, Çѹø ºñ±³¿¡ ºñ¿ëÀÌ ¸¹ÀÌ µå¹Ç·Î radix-sort¸¦ Çѹø ÇÑ´Ù.

             AB.....
             BC.....
             AB....
             BC....

    Áï AB·Î ½ÃÀÛÇÏ´Â °ÍÀ» ¹­°í, BC·Î ½ÃÀÛÇÏ´Â °ÍÀ» ¹­¾î ³õ´Â´Ù.  ±×·± ´ÙÀ½ AB·Î ¹­ÀÎ °Íµé³¢¸®, BC·Î ¹­ÀÎ °Íµé³¢¸® °¢°¢ quick-sort¸¦ ÇÑ´Ù.

    Modify block after Radix-sort
           AB...
           AB...
             .
             .
             .

    ÀÌ·±½ÄÀ¸·Î AB·Î ¹­ÀÎ ºí·°ÀÌ ÀÖÀ¸¸é, ÀÌ°ÍÀ» ÀÏ´Ü ¼ÒÆ®ÇÑ´Ù.  ±×·±´ÙÀ½ AB´ÙÀ½ÀÇ ¹®ÀÚ 2°³¸¦ 0ºÎÅÍ 65535±îÁö ½á³Ö´Â´Ù.  65535¸¦ ³Ñ¾î¼­¸é 65535¸¦ ½á³Ö´Â´Ù. ±×·¯¸é ´Ù¸¥ XX·Î ¹­ÀÎ ºí·°À» ¼ÒÆ®ÇÒ ¶§ ºñ±³ ºñ¿ëÀÌ Àû°Ô µç´Ù.
    (¿©±â¼­ ÀÚ¼¼ÇÑ °ÍÀº ¼³¸íÇÏÁö ¾Ê°Ú´Ù. ÀÌ°ÍÀ» Çϱâ À§Çؼ­´Â ´Ù¸¥ ±â¼úÀÌ ÇÊ¿äÇÏ´Ù.)

    Small first, Large Last! :
    À§¿Í ¿¬°üµÈ ±â¼ú·Î, AB... BC..µîÀ¸·Î ¹­ÀÎ ºí·°Áß Å©±â°¡ ÀÛÀº °Í ºÎÅÍ ÇÑ´Ù.

    Array Alignment! :
    À̰͵µ Modify block°ú ¿¬°üµÇ¸é¼­ 32bit CPU ¸Þ¸ð¸® ¾ï¼¼½º¸¦  ºü¸£°Ô Çϱâ À§ÇÑ °ÍÀÌ´Ù. 32bit·Î AlignµÇ¾î ÀÖÀ¸¸é 󸮼ӵµ°¡ »¡¶óÁø´Ù.
    (Intel x86°è¿­, ´Ù¸¥ CPU´Â AlignµÇ¾î¾ß¸¸ ÇÏ´Â °ÍÀÌ ¸¹´Ù.)

    º¯ÇüµÈ »ê¼úÄÚµù
    0¿¡ ¾öû³­ °¡ÁßÄ¡¸¦ µÐ´Ù. º¯È¯À» Çϸé 0ÀÌ ¾öû³ª°Ô ¸¹ÀÌ ³ª¿À´Âµ¥, ÀÌ°ÍÀ» À§ÇÑ °ÍÀÌ´Ù.

    »ê¼úÄÚµù¿¡ [OFF],[ON],1,2,3,4,...255ÀÇ ¼øÀ¸·Î °¡ÁßÄ¡¸¦ µÐ´Ù.
    0Àº ¾ø´Ù. ´ë½Å [OFF] [ON]À¸·Î Ç¥½ÃÇÑ´Ù.

          [OFF][1][2].....        => 0 1 2 ...
          [ON] [1][2].....        => 00 1 2 ...
          [OFF][OFF][1][2]...  => 000 1 2 ...
          [ON][OFF][1][2]....   => 0000 1 2 .....
    ´ëÃæ ÀÌ·± ½ÄÀÌ´Ù. Àß »ý°¢ÇØ º¸¸é 0¿¡ ´ëÇؼ­ ¾öû³­ °¡ÁßÄ¡¸¦  µÎ°í ÀÖ´Â °ÍÀÌ´Ù.
    * ÀÚ¼¼ÇÑ ³»¿ëÀº bzip¼Ò½º¸¦ ºÐ¼®ÇØ ³ª°¡±â ¹Ù¶õ´Ù.        

 

¡Ü ¸¶Ä¡±âÀü »ç°úÀÇ ¸»¾¸

    ½ÃÀÛÇϱâÀü¿¡¼­ º¸¿©ÁØ ¾ÐÃà °á°ú´Â È£±â½É(?) À¯¹ßÀ» À§Çؼ­ º»ÀÎÀÌ ÀǵµÀûÀ¸·Î ³ÖÀº °ÍÀÌ´Ù. ¹°·Ð bzipÀ» ½áº¸½Å ºÐµéÀº ´À³¢°ÚÁö¸¸... ¾ÐÃà·üÀº  ÁÁ¾Æµµ ¾ÐÃàÇϴµ¥ µå´Â ½Ã°£Àº gzip¿¡  ºñÇϸé Àå³­ÀÌ ¾Æ´Ï´Ù. °É¸° ½Ã°£À» °°ÀÌ ½á¾ß µÇ³ª, Èï¹Ì À¯¹ßÀ» À§ÇØ ÀϺη¯ ¾²Áö ¾Ê¾ÒÀ½À» ¾çÇØÇϱ⠹ٶõ´Ù.

 

¡Ü ¸¶Ä¡¸ç....

    ¼ö¹Ú °ÑÇӱ⠽ÄÀ¸·Î Çѹø »ìÆ캸¾Ò´Ù. ¹°·Ð ÀúÀÇ ÀÛ¹® ½Ç·Â ºÎÁ·À¸·Î ÀÌÇØ°¡ ¿Ïº®È÷ µÇÁö´Â ¾Ê¾ÒÀ» Å×Áö¸¸, ±×³É ÃÖ±Ù(?)¿¡ ³ª¿Â ¾Ë°í¸®ÁòÀ» ´Ü¼øÈ÷ ÀÌÇØÇÑ´Ù´Â Â÷¿øÀ¸·Î º¸¾ÒÀ¸¸é ÇÑ´Ù. ¹°·Ð ¿©±â¼­ ¹àÈù °ÍÀ¸·Î bzipÀ» ±¸¼ºÇÒ ¼ö ÀÖ´Ù. ±×·¯³ª ±ºµ¥ ±ºµ¥ ¾ÐÃà·üÀ» ³ôÀ̱â À§ÇÑ Å×Å©´ÐÀÌ ÀÖ´Ù. ƯÈ÷ À§¿¡¼­ ¹®ÀåµéÀ» Á¤·ÄÇÏ´Â °Í¿¡ ´ëÇÑ Å×Å©´ÐÀÌ Áß¿äÇÏ´Ù.. bzip¿¡¼­ ºí·° Å©±â´Â ÃÖ´ë 900k±îÁö ÁöÁ¤ÇÒ ¼ö ÀÖ´Ù. Çѹø 900kÀÇ ±æÀÌÀÇ ¹®ÀÚ¿­À» Á¤·ÄÇÑ´Ù°í Çغ¸ÀÚ. ¾Æ¸¶ ¾öû³­ ½Ã°£ÀÌ °É¸± °ÍÀÌ´Ù. Á¦ ¾Æ¹«¸® ºü¸¥ Quick-Sort¸¦ ½áµµ n*log(n)¾Ë°í¸®ÁòÀÌ´Ù. °Å±â´Ù ¹®ÀÚ¿­ÀÇ ±æÀÌ°¡ °öÇØÁø´Ù. ÀÌ°ÍÀ» Á» ´õ ºü¸£°Ô ÇÏ´Â ¹ýµµ ÀÖ´Ù. ±× ¹æ¹ýÀº Bzip¼Ò½º¿¡ ÀÖ´Ù.

    ±×·³ BzipÀ¸·Î ´õ ¸¹Àº °ø°£À» È®º¸Çϱ⠹ٶó¸ç....

    Copyleft (c) 1997-1999 by Á¤¿ìÀç 




¡ã top

homeÀ¸·Î...