From cb1e3e3ba6169557d3aff226e8f5fac39cec4aca Mon Sep 17 00:00:00 2001 From: Koji Arai Date: Wed, 16 Jul 2008 23:44:24 +0900 Subject: [PATCH] update Hacking_of_LHa --- Hacking_of_LHa | 80 +++++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 60 insertions(+), 20 deletions(-) diff --git a/Hacking_of_LHa b/Hacking_of_LHa index d57c0f3..67f4070 100644 --- a/Hacking_of_LHa +++ b/Hacking_of_LHa @@ -5108,29 +5108,44 @@ Huffman : | . ... ³¬ÁØ:11 | / \ | - x x ... ³¬ÁØ:12 .' <- ɽ°ú¤­¤Î·ë²Ì x ¤¬(>=NC)¤Î¾ì¹ç¡¢ + x y ... ³¬ÁØ:12 .' <- ɽ°ú¤­¤Î·ë²Ì x ¤¬(>=NC)¤Î¾ì¹ç¡¢ / \ Ìڤγ¤­¤¬¤¢¤ë¤³¤È¤ò¼¨¤¹ - . . ... ³¬ÁØ:13 `. + z . ... ³¬ÁØ:13 `. | : > left[]/right[]¤Çɽ¸½ (³¬ÁØ12¤¬root) ... ³¬ÁØ:16 .' - - ³¬ÁØ 1 ¡Á 12 (1¡Á12bit)¤ÎHuffmanÌڤˤĤ¤¤Æ¤Ï¡¢É½°ú¤­¤ÇÉü¹æ - ³¬ÁØ 13 °Ê¾å¤ÎHuffmanÉä¹æ¤Ë¤Ä¤¤¤Æ¤Ï¡¢ÀèƬ 12 bit¤òɽ°ú¤­¤·¡¢¤½¤ÎÃÍ - ¤ÏNC ¤è¤êÂ礭¤¤ÃͤȤʤ롣 - - ɽ°ú¤­¤·¤¿·ë²Ì¤¬ >= NC ¤Î¾ì¹ç¡¢¤½¤ÎÃͤÏÀá¤ò¼¨¤·¡¢left[ɽ°ú¤­¤ÎÃÍ], - right[ɽ°ú¤­¤ÎÃÍ]¤¬¤½¤Î²¼¤ÎÀá¤ò»Ø¤¹¡£ ---------------------------------------------------------------------------- ³¬ÁØ12¤è¤ê²¼(13 °Ê¾å¤Î bit ¿ô¤Î Huffman Éä¹æ)¤Î Huffman ÌڤˤĤ¤¤Æ -left[], right[] ¤Çɽ¤·¤Æ¤¤¤ë¤è¤¦¤À¡£¤³¤ÎÌڤΥΡ¼¥É¤ÎÃÍ¤Ï NC °Ê¾å¤Î¿ôÃÍ -¤òÏ¢È֤dzä¤êÅö¤Æ¤Æ¤¤¤ë¤è¤¦¤À(¤³¤ì¤Ë¤Ä¤¤¤Æ¤Ï¸å½Ò¤¹¤ë)¡£ +left[], right[] ¤Çɽ¤·¤Æ¤¤¤ë¤è¤¦¤À¡£ + +¾å¤ÎÎã¤Ç¡¢13 ¥Ó¥Ã¥È¤Î Huffman Éä¹æ¤ÇÉä¹æ²½¤µ¤ì¤ëÊ£¹ç¸ì z ¤Ë¤Ä¤¤¤Æ¤Ï¡¢ +y ¤Ë¤½¤ÎÌڤΥ롼¥È¥Î¡¼¥È¤ÎÃÍ(y > NC)¤¬³ä¤êÅö¤Æ¤é¤ì¤ë¡£ + +¿Þ¤«¤éÌÀ¤é¤«¤À¤¬¡¢Ê£¹ç¸ì¤½¤Î¤â¤Î¤ò»Ø¤¹ 12 bit ¤ÎÉä¹æ(¤¿¤È¤¨¤Ð x)¤È¡¢ÌÚ +¤Î¥ë¡¼¥È¥Î¡¼¥É¤ò»Ø¤¹ 12 bit ¤ÎÉä¹æ(¤¿¤È¤¨¤Ð y)¤¬Æ±¤¸Éä¹æ¤È¤Ê¤ë¤³¤È¤Ï¤Ê +¤¤¡£¤³¤ì¤ÏHuffman Éä¹æ¤¬¸ìƬ¾ò·ï¤òËþ¤¿¤¹¤«¤é¤Ç¤¢¤ë¡£ + +¤Ç¤Ï¡¢y ¤Ë³ä¤êÅö¤Æ¤ëÃͤϤɤΤ褦¤Ë·è¤Þ¤ë¤«¤È¤¤¤¦¤È¤ª¤½¤é¤¯ NC °Ê¾å¤Î¿ô +ÃͤòÏ¢ÈÖ¤«²¿¤«¤Ç³ä¤êÅö¤Æ¤Æ¤¤¤ë¤Î¤Ç¤Ï¤Ê¤¤¤«¤È»×¤ï¤ì¤ë¡£¤³¤ì¤Ë¤Ä¤¤¤Æ¤Ï¤³ +¤ì°Ê¹ß¤Ç³Îǧ¤¹¤ë¡£ ¤Ê¤ª¡¢³¬Áؤ¬¿¼¤¤ Huffman ÌڤȤϡ¢bit Ť¬Ä¹¤¤Éä¹æ¤Ç¤¢¤ê¡¢bit Ť¬Ä¹¤¤¤È ¤¤¤¦¤³¤È¤Ï½Ð¸½ÉÑÅÙ¤¬Ä㤤¤Ï¤º¤Ç¤¢¤ë¤«¤é¡¢left[], right[] ¤ÇÌÚ¤òé¤ë²ó¿ô ¤Ï¾¯¤Ê¤¤¤Ï¤º¤Ç¤¢¤ë¡£¤³¤ì¤ÏÍý¤Ë¤«¤Ê¤Ã¤Æ¤¤¤ë¡£ +¤¢¤È¡¢¤³¤ÎÌÚ¤ËɬÍפʥµ¥¤¥º¤Ï¤¤¤¯¤Ä¤Ç¤¢¤ë¤«¤È¤¤¤¦ÅÀ¤¬µ¤¤Ë¤Ê¤ë¡£¤³¤ì¤Ï¡¢ +³¬ÁØ13°Ê¾å¤Î¥Î¡¼¥É¤Î¿ô¤È¤Ê¤ë¤¬¡¢³¬ÁØ n ¤ÎÆóʬÌڤΥΡ¼¥É¤Î¿ô¤¬2^(n+1) - +1 ¤Ç¤¢¤ë(³¬ÁØ n ¤ÎÍդοô¤Ï 2^n ¤Ç¡¢Àá¤Î¿ô¤Ï 2^n-1)¤«¤é¡¢ + + ³¬ÁØ 12 ¤Î¥Î¡¼¥É¤Î¿ô¤Ï¡¢(2^(12+1)-1) = 8191 + ³¬ÁØ 16 ¤Î¥Î¡¼¥É¤Î¿ô¤Ï¡¢(2^(16+1)-1) = 131071 + +¤È¤Ê¤ê¡¢¤½¤Îº¹¤Ï 131071 - 8191 = 122880 ¤È¤Ê¤ë¡£Ã±½ã¤Ë¹Í¤¨¤ë¤È¡¢ºÇ°­¤Î +¾ì¹ç¤òÁÛÄꤷ¤Æleft[], right[] ¹ç·×¤Ç 122880 ¤Î¥µ¥¤¥º¤¬É¬ÍפǤ¢¤ë¤³¤È¤Ë +¤Ê¤ë¡£¤½¤¦¤¹¤ë¤ÈÎΰè¤òÀáÌ󤹤ë¤È¤¤¤¦ÌÜŪ¤«¤é¤Ï¸µ¤â»Ò¤â¤Ê¤¤¤³¤È¤È¤Ê¤ë¡£ +¤Ê¤¼¤À¤í¤¦¡©¡Ê¡¦¡¦¡¦²¿¤«´Ö°ã¤Ã¤Æ¤¤¤ë¤Î¤À¤í¤¦¤«¡©¡Ë + ³¤­¤ò¸«¤Æ¤¤¤³¤¦¡¢(E) ¤Î½èÍý /* (E) */ @@ -5141,7 +5156,27 @@ left[], right[] for (i = j; i < k; i++) table[i] = 0; -¼¡¤Ë (F) ¤Î½èÍý¡£²¼µ­¤ÎÄ̤ê (F.1), (F.2) ¤ÈºÙʬ²½¤·¤Æ¤ß¤¿¡£ +table[] ¤Î½é´üÃͤȤ·¤Æ 0 ¤òÀßÄꤷ¤Æ¤¤¤ë¡£ + +Huffman Éä¹æ¤Ç¤¢¤ë j ¤Ë¤Ï¡¢start[tablebits + 1] ¤Ä¤Þ¤ê¡¢¥Ó¥Ã¥ÈĹ +tablebits ¤ÎºÇÂç¤Î Huffman Éä¹æ+1¤¬ÀßÄꤵ¤ì¤ë¡£(·«¤êÊÖ¤·¤Ë¤Ê¤ë¤¬¡¢¥Ó¥Ã +¥ÈĹ i ¤Î Huffman Éä¹æ¤Ï¡¢start[i] ¤«¤é start[i+1]-1¤ÎÈϰϤÎÉä¹æ¤Ç¤¢¤ë) +m ¤Ç±¦¥·¥Õ¥È¤·¤Æ¤¤¤ë¤Î¤Ï¡¢(D) ¤Ç¤Ï¡¢tablebits ¤Þ¤Ç¤Î start[i] ¤·¤« ±¦ +¥·¥Õ¥È¤·¤Æ¤¤¤Ê¤¤¤¿¤á¤Ç¤¢¤ë¡£ + +k ¤Ï¡¢1 << tablebits ¤«¤é tablebits + 1 ÈÖÌܤΥӥåȤ¬Î©¤Ã¤¿¿ôÃͤȤʤ롣 +¤³¤ÎÃͤϤĤޤê¤Ï tablebits ¥Ó¥Ã¥È¤Î Huffman Éä¹æ¤ÎºÇÂçÃÍ + 1 ¤Ç¤¢¤ë¡£ + +¤½¤·¤Æ¡¢start[j...k] ¤ÎÈϰϤˤĤ¤¤Æ 0 ¤òÀßÄꤷ¤Æ¤¤¤ë¡£·ë¶É tablebits ¤Î +¥Ó¥Ã¥ÈŤÎÈϰϤdzä¤êÅö¤Æ¤é¤ì¤ë¤³¤È¤¬¤Ê¤¤ Huffman Éä¹æ¤ËÂФ·¤Æ 0 ¤Ç½é´ü +²½¤·¤Æ¤¤¤ë¤È¤¤¤¦¤³¤È¤Î¤è¤¦¤À¡£ + +¤Á¤ç¤Ã¤Èµ¿Ìä¤Ê¤Î¤À¤¬¡¢if (j != 0) ¤ÏɬÍפʤΤÀ¤í¤¦¤«¡©¤Ä¤Þ¤ê¡¢j = 0 ¤È +¤·¤Æ¡¢table[] ¤ÎÁ´Í×ÁǤˤĤ¤¤Æ 0 ¤Ç½é´ü²½¤·¤Æ¤â²¿¤âÌäÂê¤Ï¤Ê¤¤¤Î¤Ç¤Ï¤Ê¤¤ +¤«¡©¤½¤·¤Æ¤½¤ì¤Ê¤é make_table() ¤Ë table[] ¤Î¥µ¥¤¥º(sizeof)¤òÅϤ· +memset() ¤Ë¤Æ 0 ¤Ç½é´ü²½¤·¤¿Êý¤¬Â®¤¤¤Î¤Ç¤Ï¤Ê¤¤¤À¤í¤¦¤«¡© + +¼¡¤Ë (F) ¤Î½èÍý¡£¾¯¤·Â礭¤¤¤Î¤Ç²¼µ­¤ÎÄ̤ê (F.1), (F.2) ¤ÈºÙʬ²½¤·¤Æ¤ß¤¿¡£ /* (F) */ /* create table and tree */ @@ -5182,7 +5217,10 @@ left[], right[] ¤³¤ÎÉôʬ¤Ï°ì»þÊÑ¿ô¤ÎÎ̤¬Â¿¤¤¡¢i,j,k,l,m,n,p ¤Þ¤Ç»È¤ï¤ì¤Æ¤¤¤ë¡£ (¤·¤«¤â¡¢Á°¤Î½èÍý¤Þ¤Ç¤ÈÊÑ¿ô¤ÎÍÑÅÓ¤¬°ã¤Ã¤Æ¤¿¤ê¤¹¤ë¤Î¤Ç¡¢Ê£»¨¤Ë¤Ê¤Ã¤Æ¤¤¤ë) -°ìö¡¢°Ê²¼¤ËÀ°Íý¤·¤Æ¤ß¤¿¡£ + +°ìö¡¢°Ê²¼¤ËÀ°Íý¤·¤Æ¤ß¤¿¡£(¤É¤ÎÊÑ¿ô¤Îź¤¨»ú¤Ë»È¤ï¤ì¤Æ¤¤¤ë¤«¤Ê¤É¤«¤é¤Ò¤È +¤á¤ÇȽÃǤ·¤Æ¤ß¤¿·ë²Ì¤Ç¤¢¤ë¡£¤½¤·¤Æ¡¢n, p ¤Ë¤Ä¤¤¤Æ¤Ï¤Ò¤È¤á¤Ç¤Ï¤ï¤«¤é¤Ê¤«¤Ã +¤¿)¡£ i: Huffman Éä¹æ j: Éü¹æʸ»ú @@ -5192,8 +5230,6 @@ left[], right[] n: ?? p: ?? -n, p ¤Ë¤Ä¤¤¤Æ¤Ï¤Ò¤È¤á¤Ç¤Ï¤ï¤«¤é¤Ê¤«¤Ã¤¿¡£ - ¤³¤ì¤òƧ¤Þ¤¨¤Æ½èÍýÆâÍƤò¸«¤Æ¤ß¤è¤¦¡£¤Þ¤º¡¢(F)Á´ÂΤˤĤ¤¤Æ /* (F) */ @@ -5215,7 +5251,7 @@ bitlen[] ¤Îʸ»ú¤Ï¥¹¥­¥Ã¥×¤·¤Æ¤¤¤ë¡£¤³¤³¤Ï¡¢Îɤ¤¤À¤í¤¦¡£ (F.1), (F.2) ¤Ï¡¢HuffmanÉä¹æ²½¤µ¤ì¤Æ¤¤¤ëʸ»ú j ¤Ë¤Ä¤¤¤Æ -¤Î½èÍý¤È¤Ê¤ë¡£(ºÇ¸å¤Îstart[k] = l ¤Ï¸å²ó¤·) +¤Î½èÍý¤È¤Ê¤ë¡£(ºÇ¸å¤Îstart[k] = l ¤Ï¸å¤Ç¹Í¤¨¤è¤¦) ½èÍý¤ÎÌÜŪ¤«¤éÂ绨ÇÄ¤Ë @@ -5247,8 +5283,8 @@ bitlen[] a /\ b: 10 b c c: 11 -ʸ»úa¤Ï¡¢1¥Ó¥Ã¥È¤Ç¡¢00...10 ¤ÎÈÏ°Ï -ʸ»úb¤Ï¡¢2¥Ó¥Ã¥È¤Ç¡¢10...11 ¤ÎÈÏ°Ï +ʸ»úa¤Ï¡¢1¥Ó¥Ã¥È¤Ç¡¢00...10 ¤ÎÈÏ°Ï(¤Ä¤Þ¤ê¡¢00¤È01) +ʸ»úb¤Ï¡¢2¥Ó¥Ã¥È¤Ç¡¢10...11 ¤ÎÈÏ°Ï(¤Ä¤Þ¤ê¡¢10) ʸ»úc¤Ï¡¢2¥Ó¥Ã¥È¤Ç¡¢11 ¤È¤Ê¤ë¡£¤³¤³¤Ç¡¢Ê¸»ú c ¤Ë¤Ä¤¤¤Æ¤Ï¤³¤Î¥ë¡¼¥×¤Ç¤Ï¥Æ¡¼¥Ö¥ë¤ËÃͤ¬¥»¥Ã¥È¤µ¤ì @@ -5282,7 +5318,7 @@ bitlen[] *p = j; } -¤Þ¤º¡¢ +¤Á¤ç¤Ã¤ÈÊ£»¨¤À¤¬Æñ¤·¤¤¤³¤È¤Ï¤Ê¤¤¡£¤Þ¤º¡¢ p = &table[(i = start[k]) >> m]; @@ -5291,7 +5327,11 @@ bitlen[] i = start[k]; p = &table[i >> m] -¤Ç¤¢¤ê¡¢i ¤Ï Huffman Éä¹æ¤Î½é´üÃÍ +¤Ç¤¢¤ê¡¢i ¤Ï Huffman Éä¹æ¤Î½é´üÃͤǤ¢¤ë¡£i ¤¬ m ¤Ç±¦¥·¥Õ¥È¤µ¤ì¤Æ¤¤¤ë¤¬¡¢ +½é´ü²½Éôʬ¤Î (D) ¤Ç¤Ï¡¢tablebits ¤Þ¤Ç¤Î¥¤¥ó¥Ç¥Ã¥¯¥¹¤ËÂФ¹¤ëÃÍ +(start[1..tablebits])¤·¤«¥·¥Õ¥È¤·¤Æ¤ª¤é¤º¡¢¤³¤Î (F.2) ¤ÎÉôʬ¤Ï k > +tablebits ¤Ç¤¢¤ë¤«¤é start[k] ¤Ï m ¤Ç¥·¥Õ¥È¤µ¤ì¤Æ¤¤¤Ê¤¤ Huffman Éä¹æ¤È +¤Ê¤Ã¤Æ¤¤¤ë¡£ p ¤Ï¡¢HuffmanÉä¹æ i ¤Î table ¾å¤Î°ÌÃÖ¤ò»Ø¤¹¡£¸å¤Ç¡¢*p ¤Ë¤ÏÌڤΥ롼¥È°ÌÃÖ ¤òµ­Ï¿¤¹¤ë¤³¤È¤¬Í½ÁÛ¤µ¤ì¤ë¡£ -- 2.11.0