¡¡¡¡´Ó¼ÆËã»úͳ¿¼´ó¸ÙÊý¾Ý½á¹¹²¿·Ö¼°ÆäÏà¹ØÖªÊ¶µã¿ÉÒÔ¿´³ö£ºÊý¾Ý½á¹¹Õ¼ÁË45·Ö£¬ºÍ¼ÆËã»ú×é³ÉÔÀí²¿·Öͬһ¸ö±ÈÖØ£¬Õâ×ãÒÔÌåÏÖ¼ÆËã»úöλÔÓéÀֵǼÈë¿ÚÏÂÔØÑо¿ÉúÑ¡°Î¶ÔÊý¾Ý½á¹¹¿Î³ÌµÄÖØÊӳ̶ȡ£Õë¶ÔÕâÑùµÄÇé¿ö£¬Ïà¹Ø×¨¼ÒΪÎÒÃǵĿ¼ÉúÃǾ«ÐÄ×¼±¸ÁËһЩÊý¾Ý½á¹¹¸´Ï°µÄ½¨Òé¡£
¡¡¡¡Í³¿¼´ó¸Ù¶ÔÊý¾Ý½á¹¹µÄ¿¼²éÄ¿±ê¶¨Î»ÎªÕÆÎÕÊý¾Ý½á¹¹µÄ»ù±¾¸ÅÄî¡¢»ù±¾ÔÀíºÍ»ù±¾·½·¨£¬ÕÆÎÕÊý¾ÝµÄÂß¼½á¹¹¡¢´æ´¢½á¹¹ÒÔ¼°»ù±¾²Ù×÷µÄʵÏÖ£»Äܹ»¶ÔËã ·¨½øÐлù±¾µÄʱ¼ä¸´ÔӶȺͿռ临ÔӶȵķÖÎö£»Äܹ»ÔËÓÃÊý¾Ý½á¹¹µÄ»ù±¾ÔÀíºÍ·½·¨½øÐÐÎÊÌâµÄ·ÖÎöÇó½â£¬¾ß±¸²ÉÓÃC¡¢C++»òJAVAÓïÑÔÉè¼Æ³ÌÐòÓëʵÏÖËã·¨ µÄÄÜÁ¦¡£
¡¡¡¡µ±È»£¬¿¼ÉúÒ²²»±ØÒò´Ë¶ø×¨ÃŸ´Ï°Ò»±éC»òC++³ÌÐòÉè¼Æ£¬±Ï¾¹¸´Ï°Ê±¼äÓÐÏÞ£¬¶øÇÒÊý¾Ý½á¹¹ÒªÇóµÄÖØµãÔÚÓÚËã·¨Éè¼ÆµÄÄÜÁ¦£¬¶ø²»ÊDZàд´úÂëµÄÄÜÁ¦£¬Òò´Ë£¬Ö»ÒªÄÜÓÃÀàËÆÎ±´úÂëµÄÐÎʽ°Ñ˼·±í´ïÇå³þ¾ÍÐУ¬²»ÓÃÇ¿Çóд³öÒ»¸öûÓÐÈκÎÓï·¨´íÎóµÄ³ÌÐò¡£
¡¡¡¡ÏÂÃæÎÒÃÇÀ´½âÎöÒ»ÏÂ֪ʶµã£º
¡¡¡¡ÏßÐÔ±íÕâÒ»ÕÂÀïÃæµÄ֪ʶµã²»¶à£¬µ«Òª×öµ½Éî¿ÌÀí½â£¬Äܹ»Ó¦ÓÃÏà¹ØÖªÊ¶µã½â¾öʵ¼ÊÎÊÌâ¡£Á´±íÉϲåÈ롢ɾ³ý½ÚµãʱµÄÖ¸Õë²Ù×÷ÊÇÑ¡ÔñÌâµÄÒ»¸ö³£¿¼µã£¬ÖîÈçË«ÏòÁ´±íµÈһЩÏà¶Ô¸´ÔÓµÄÁ´±íÉϵIJÙ×÷Ò²ÊÇ¿ÉÒÔ³öÏÖÔÚ×ÛºÏÓ¦ÓÃÌâµ±Öеġ£
¡¡¡¡Õ»¡¢¶ÓÁкÍÊý×é¿ÉÒÔ¿¼²éµÄ֪ʶµãÏà±ÈÁ´±íÀ´ËµÒª¶àһЩ¡£×î»ù±¾µÄ£¬ÊÇÕ»Óë¶ÓÁÐFILOºÍFIFOµÄÌØµã¡£±ÈÈçÕë¶ÔÕ»FILOµÄÌØµã£¬½øÕ»³öÕ»Ðò ÁеÄÎÊÌâ³£³öÏÖÔÚÑ¡ÔñÌâÖС£Æä´Î£¬ÊÇÕ»ºÍ¶ÓÁеÄ˳ÐòºÍÁ´Ê½´æ´¢½á¹¹£¬ÕâÀïÒ»¸ö³£¿¼µãÊDz»Í¬´æ´¢½á¹¹ÏÂÕ»¶¥Ö¸Õë¡¢¶ÓÊ×Ö¸ÕëÒÔ¼°¶ÓβָÕëµÄ²Ù×÷£¬ÌرðÊÇÑ»·¶Ó ÁÐÅÐÂúºÍÅпյÄ2ÖÖÅжϷ½·¨¡£ÔٴΣ¬ÊÇÌØÊâ¾ØÕóµÄѹËõ´æ´¢£¬Õâ¸ö¿¼µã¸´Ï°µÄÖØµã¿ÉÒÔ·ÅÔÚ¶þά¾ØÕóÓëһάÊý×éÏ໥ת»»Ê±£¬Ï±êµÄ¼ÆËã·½·¨£¬±ÈÈçÓë¶Ô½ÇÏ߯½ÐÐ µÄÈô¸ÉÐÐÉÏÊý¾Ý·ÇÁãµÄ¾ØÕó´æ·ÅÔÚһάÊý×éºó£¬¸÷¸öÊý¾ÝµãÏàÓ¦µÄϱêµÄ¼ÆËã¡£ÕâÒ»Õ¿ÉÄܵĴóÌâµã£¬ÔÚÓÚÀûÓöÑÕ»»ò¶ÓÁеÄÌØÐÔ£¬½«ËüÃÇ×÷Ϊ»ù´¡µÄÊý¾Ý½á¹¹£¬Ö§ ³Öʵ¼ÊÎÊÌâÇó½âËã·¨µÄÉè¼Æ£¬ÀýÈçÓÃÕ»½â¾öµÝ¹éÎÊÌ⣬ÓöÓÁнâ¾öͼµÄ±éÀúÎÊÌâµÈµÈ¡£
¡¡¡¡Ê÷ºÍ¶þ²æÊ÷£ºÕâÒ»ÕÂÖÐÎÒÃÇ´Ó˳ÐòʽµÄÊý¾Ý½á¹¹£¬×ªÏò²ã´ÎʽµÄÊý¾Ý½á¹¹£¬ÒªÕÆÎÕÊ÷¡¢¶þ²æÊ÷µÄ¸÷ÖÖÐÔÖÊ¡¢Ê÷ºÍ¶þ²æÊ÷µÄ²»Í¬´æ´¢½á¹¹¡¢ÉÁÖ¡¢Ê÷ºÍ¶þ²æ Ê÷Ö®¼äµÄת»»¡¢ÏßË÷»¯¶þ²æÊ÷¡¢¶þ²æÊ÷µÄÓ¦ÓÃ(¶þ²æÅÅÐòÊ÷¡¢Æ½ºâ¶þ²æÊ÷ºÍHuffmanÊ÷)£¬ÖصãÒªÊìÁ·ÕÆÎյģ¬ÊÇÉÁÖ¡¢Ê÷ÒÔ¼°¶þ²æÊ÷µÄǰÖкóÈýÖÖ±éÀú·½ ʽ£¬ÒªÄܽøÐÐÏàÓ¦µÄËã·¨Éè¼Æ¡£ÕâÒ»²¿·ÖÊÇÊý¾Ý½á¹¹¿¼ÌâÀúÀ´µÄÖØµãºÍÄѵ㣬¸´Ï°Ê±ÒªÌرð¹Ø×¢¡£Ò»Ð©³£¼ûµÄÑ¡ÔñÌ⿼µã°üÀ¨£ºÂú¶þ²æÊ÷¡¢ÍêÈ«¶þ²æÊ÷½ÚµãÊýµÄ¼Æ Ë㣬ÓÉÊ÷¡¢¶þ²æÊ÷µÄʾÒâͼ¸ø³öÏàÓ¦µÄ±éÀúÐòÁУ¬ÒÀ¾Ý¶þ²æÊ÷µÄ±éÀúÐòÁл¹Ô¶þ²æÊ÷£¬ÏßË÷»¯µÄʵÖÊ£¬¼ÆËã²ÉÓò»Í¬µÄ·½·¨ÏßË÷»¯ºó¶þ²æÊ÷Ê£Óà¿ÕÖ¸ÕëÓòµÄ¸öÊý£¬Æ½ ºâ¶þ²æÊ÷µÄ¶¨Òå¡¢ÐÔÖÊ¡¢½¨Á¢ºÍËÄÖÖµ÷ÕûËã·¨ÒÔ¼°»ØËÝ·¨Ïà¹ØµÄÎÊÌâ¡£³£¼ûµÄ×ÛºÏÓ¦ÓÃÌ⿼µã°üÀ¨£º¶þ²æÊ÷µÄ±éÀúËã·¨£¬±éÀú»ù´¡ÉÏÕë¶Ô¶þ²æÊ÷µÄһЩͳ¼ÆºÍ²Ù×÷ (±ÈÈç½áµãÊýͳ¼Æ¡¢×óÓÒ×ÓÊ÷¶Ô»»µÈµÈ)£¬ÅжÏij¿Ã¶þ²æÊ÷ÊÇ·ñ¶þ²æÅÅÐòÊ÷£¬ÒÔÉÏÕâЩ¶¼ÒªÇóÄÜÓõݹéµÄºÍ·ÇµÝ¹éµÄËã·¨½â¾ö£¬ÌرðÒªÖØÊӷǵݹéµÄËã·¨£¬ÏßË÷»¯ºó ¶þ²æÊ÷µÄ±éÀúËã·¨£¬Èç²éÕÒij½áµãÏßË÷»¯ºóµÄǰÇý»òºó¼Ì½áµãµÄËã·¨ÒÔ¼°¸ø³öHuffman±àÂëµÈµÈ¡£
¡¡¡¡Í¼£ºÔÚÕâÒ»ÕÂÖÐÐèҪʶ¼ÇµÄÊÇͼÒÔ¼°»ùÓÚͼµÄ¸÷ÖÖ¶¨Ò壬´æ´¢·½Ê½¡£ÒªÊìÁ·ÕÆÎÕͼµÄÉî¶È±éÀúºÍ¹ã¶È±éÀúËã·¨£¬ÕâÊÇÓÃͼÀ´½â¾öÓ¦ÓÃÎÊÌâʱ³£ÓõÄËã·¨»ù ´¡¡£ÐèÒªÕÆÎÕ»ùÓÚͼµÄ¶à¸öËã·¨£¬Äܹ»ÒÔÊÖ¹¤¼ÆËãµÄ·½Ê½ÔÚÒ»¸ö¸ø¶¨µÄͼÉÏÖ´ÐÐÌØ¶¨µÄËã·¨Çó½âÎÊÌâ¡£³£¼ûµÄÓ¦ÓÃÎÊÌâÖ±½Ó¸ø³ö»ò¾¹ý³éÏ󣬻á³ÉΪÏÂÁÐÎÊÌ⣺×îС Éú³ÉÊ÷Çó½â(PRIMËã·¨ºÍKRUSKALËã·¨£¬Á½ÖÖ·½·¨Ë¼Ïë¶¼ºÜ¼òµ¥£¬µ«Òª×¢Òâ²»Òª»ìÏýÕâÁ½ÖÖ·½·¨)£¬ÍØÆËÅÅÐòÎÊÌâ(ÕâÀï»áÓõ½Êý×éʵÏÖµÄÁ´±í£¬¿ÉÒÔ×¢ ÒâÒ»ÏÂ)£¬¹Ø¼ü·¾¶ÎÊÌâ(Êý¾Ý½á¹¹µÄ½Ï´óÄѵ㣬Ҫ°Ñ¸ÅÄîÀí½â͸£¬ÄÜ×ö³ö±í¸ñÕÒ³ö¹Ø¼ü·¾¶)£¬×î¶Ì·¾¶ÎÊÌâ(ÓÐÖØÒªµÄÓ¦Óñ³¾°£¬Ò²ÊÇ̰ÐÄ·¨²»¶àµÄÄܸø³ö×îÓÅ ½âµÄµäÐÍÎÊÌâÖ®Ò»)¡£
¡¡¡¡²éÕÒ£ºÕâÒ»Õ£¬ÐèҪʶ¼Ç¹Ø¼ü×Ö¡¢Ö÷¹Ø¼ü×Ö¡¢´Î¹Ø¼ü×ֵĺ¬Ò壻¾²Ì¬²éÕÒÓ붯̬²éÕҵĺ¬Òå¼°Çø±ð£»Æ½¾ù²éÕÒ³¤¶ÈASLµÄ¸ÅÄîÄî¼°ÔÚ¸÷ÖÖ²éÕÒËã·¨ÖÐµÄ ¼ÆËã·½·¨ºÍ¼ÆËã½á¹û£¬ÌرðÊÇһЩµäÐͽṹµÄASLÖµ£¬B-Ê÷µÄ¸ÅÄîºÍ»ù±¾²Ù×÷³åÍ»½â¾ö·½·¨µÄÑ¡ÔñºÍ³åÍ»´¦Àí¹ý³ÌµÄÃèÊö£¬B+Ê÷µÄ¸ÅÄî(ÐÂÔö¿¼µã)£¬ÌرðÒª ×¢ÒâB-Ê÷ºÍB+Ê÷¸ÅÄîµÄ¶Ô±È£¬ÒÔ¼°Hash±íÏà¹ØµÄ¸ÅÄî¡£ÒªÊìÁ·ÕÆÎÕ˳Ðò±í¡¢Á´±í¡¢¶þ²æÊ÷ÉϵIJéÕÒ·½·¨£¬ÌرðҪעÒâ˳Ðò²éÕÒ¡¢¶þ·Ö²éÕÒµÄÊÊÓÃÌõ¼þ(±ÈÈç Á´±íÉÏÓöþ·Ö²éÕҾͲ»ºÏÊÊ)ºÍËã·¨¸´ÔÓ¶È¡£
¡¡¡¡ÅÅÐò£º×îеĴó¸Ù½«È¥ÄêµÄÄÚ²¿ÅÅÐò·¶Î§À©Õ¹ÎªÅÅÐò£¬ÅÅÐò¼ÈÊÇÖØµã£¬ÓÖÊÇÄѵ㡣ÅÅÐòËã·¨Öڶ࣬½ñÄê´ó¸Ù»¹¼ÓÉÏÁËÍⲿÅÅÐò£¬×ܹ²10ÖÖ£¬¸÷ÖÖ²»Í¬Ëã ·¨»¹ÓÐÏàÓ¦µÄһЩ¸ÅÄÒåÐèÒª¼Çס¡£Ñ¡ÔñÌâ³£¼ûµÄÎÊÌâ°üÀ¨£º¸ø¶¨ÊýÁÐÒªÇó¸ø³öijÖÖÌØ¶¨ÅÅÐò·½·¨ÔËÐÐÒ»ÂÖºóµÄÅÅÐò½á¹û£¬»òÕ߸ø³ö³õʼÊýÁкÍÒ»ÂÖÅÅÐò½á¹ûÒªÇó Ñ¡Ôñ²ÉÓõÄÅÅÐòËã·¨£¬¸ø¶¨Ê±¼ä¡¢¿Õ¼ä¸´ÔÓ¶ÈÒªÇóÒÔ¼°ÊýÁÐÌØÕ÷ÒªÇóÑ¡ÔñºÏÊʵÄÅÅÐòËã·¨µÈµÈ¡£Èç¹ûÅÅÐòÕâÒ»¿¼µã³öÏÖÔÚ×ÛºÏÓ¦ÓÃÌâÖÐÔò³£ÓëÊý×é½áºÏÀ´¿¼²é¡£
¡¡¡¡Êý¾Ý½á¹¹µÄ¸´Ï°Òª½ô¿Û²Î¿¼Ê飬°ÑÊéÈÏÕæ¿´¼¸±é£¬ÉîÈëÀí½â´ó¸ÙÏà¹ØµÄ֪ʶµã¡£
¡¡¡¡±¾ÎÄÓÉÍòѧ½ÌÓý¹©¸å¡£
