Package-merge algorithm
தொகுப்பு-இணைப்பு வழிமுறை என்பது ஒரு O (nL)-நேர வழிமுறை ஆகும், இது கொடுக்கப்பட்ட அளவு n எழுத்துக்களில் கொடுக்கப்பட்ட விநியோகத்திற்கு உகந்த நீளம்-வரையறுக்கப்பட்ட ஹஃப்மேன் குறியீட்டைக் கண்டுபிடிப்பதற்கான ஒரு வழிமுறையாகும், அங்கு எந்த குறியீடு வார்த்தையும் L ஐ விட நீளமாக இல்லை. பைனரி நாணயம் சேகரிப்பாளரின் சிக்கலுக்கு குறியீடு கட்டுமான சிக்கலைக் குறைப்பதன் மூலம் தொகுப்பு-இணைப்பு செயல்படுகிறது. நாணய சேகரிப்பாளரின் சிக்கல் ஒரு நாணய சேகரிப்பாளரிடம் பல்வேறு பணத்தாள்களின் பல நாணயங்கள் உள்ளன என்று வைத்துக்கொள்வோம், அவை ஒவ்வொன்றும் அதன் பணத்தாளுடன் தொடர்பில்லாத நாணயவியல் மதிப்பைக் கொண்டுள்ளன. நாணய சேகரிப்பாளருக்கு பணம் தீர்ந்துவிட்டது, மேலும் அவரது நாணய சேகரிப்பில் சிலவற்றைப் பயன்படுத்தி விலை N ஐ வாங்க வேண்டும். அவர் தனது குறைந்தபட்ச நாணயவியல் மதிப்பின் சேகரிப்பிலிருந்து நாணயங்களின் துணைக்குழுவைத் தேர்ந்தெடுக்க விரும்புகிறார், அதன் மதிப்புகள் மொத்தம் N. இந்த சிக்கலின் பைனரி பதிப்பு என்னவென்றால், அனைத்து பணத்தாள்களும் 2 இன் சக்திகள், அதாவது 1,1/2,1/4 போன்றவை. டாலர்கள். தொகுப்பு-இணைப்பு வழிமுறையின் விளக்கம் மிகப்பெரிய மதிப்பு 1 டாலர் என்றும், N ஒரு முழு எண் என்றும் வைத்துக்கொள்வோம். (இந்த அனுமானங்கள் பொருந்தாவிட்டாலும், அற்பமான மாற்றங்களால் வழிமுறை செயல்படுகிறது.) நாணய சேகரிப்பாளர் முதலில் தனது நாணயங்களை பட்டியல்களாக பிரிக்கிறார், ஒவ்வொரு மதிப்புக்கும் ஒன்று, நாணயவியல் மதிப்பால் வரிசைப்படுத்தப்படுகிறது. பின்னர் அவர் மிகச்சிறிய மொத்த நாணய மதிப்பின் ஜோடியிலிருந்து தொடங்கி, ஜோடியாக மிகச்சிறிய மதிப்புள்ள நாணயங்களை தொகுக்கிறார். ஒரு நாணயம் எஞ்சியிருந்தால், அது அந்த மதிப்புக்குரிய மிக உயர்ந்த நாணய மதிப்பைக் கொண்ட நாணயமாக இருக்கும், மேலும் அது ஒதுக்கி வைக்கப்பட்டு இனிமேல் புறக்கணிக்கப்படும். இந்த பொதிகள் பின்னர் அடுத்த மிகச்சிறிய மதிப்புள்ள நாணயங்களின் பட்டியலில் மீண்டும் நாணயவியல் மதிப்பின் வரிசையில் இணைக்கப்படுகின்றன. அந்த பட்டியலில் உள்ள உருப்படிகள் பின்னர் ஜோடிகளாக தொகுக்கப்பட்டு, அடுத்த மிகச்சிறிய பட்டியலில் இணைக்கப்படுகின்றன. இறுதியாக, பொருட்களின் பட்டியல் உள்ளது, அவை ஒவ்வொன்றும் 1 டாலர் நாணயம் அல்லது இரண்டு அல்லது அதற்கு மேற்பட்ட சிறிய நாணயங்களைக் கொண்ட ஒரு தொகுப்பாகும், அதன் மதிப்புகள் மொத்தம் 1 டாலர் ஆகும். அவை நாணயவியல் மதிப்பின் வரிசையிலும் வரிசைப்படுத்தப்படுகின்றன. நாணய சேகரிப்பாளர் பின்னர் அவற்றில் குறைந்தபட்ச மதிப்பு N ஐத் தேர்ந்தெடுக்கிறார். வழிமுறையின் நேரம் நாணயங்களின் எண்ணிக்கையில் நேரியல் என்பதை நினைவில் கொள்க. நாணய சேகரிப்பாளரின் சிக்கலுக்கு நீளம்-வரையறுக்கப்பட்ட ஹஃப்மேன் குறியீட்டைக் குறைத்தல் எல் என்பது எந்தவொரு குறியீட்டு வார்த்தையும் அனுமதிக்கப்படும் அதிகபட்ச நீளமாக இருக்கட்டும். p1,., pn என்பது குறியிடப்பட வேண்டிய எழுத்துக்களின் சின்னங்களின் அதிர்வெண்களாக இருக்கட்டும். முதலில் குறியீடுகளை வரிசைப்படுத்துவதன் மூலம் பை ≤ பை + 1 ஆகும். 2−1,., 2−எல், நாணய மதிப்பு பை கொண்ட ஒவ்வொரு குறியீட்டிற்கும் எல் நாணயங்களை உருவாக்கவும். தொகுப்பு-இணைப்பு வழிமுறையைப் பயன்படுத்தி குறைந்தபட்ச நாணயவியல் மதிப்பைக் கொண்ட நாணயங்களின் தொகுப்பைத் தேர்ந்தெடுக்கவும், அதன் மொத்த மதிப்புகள் n−1 ஆகும். தேர்ந்தெடுக்கப்பட்ட நாணயவியல் மதிப்புள்ள பை நாணயங்களின் எண்ணிக்கையாக ஹாய் இருக்கட்டும். உகந்த நீளம்-வரையறுக்கப்பட்ட ஹஃப்மேன் குறியீடு சின்னம் i ஐ நீளத்தின் ஒரு பிட் சரத்துடன் குறியாக்கம் செய்யும். கனோனிக்கல் ஹஃப்மேன் குறியீட்டை ஒரு எளிய பாட்டம்-அப் பேராசை முறையால் எளிதில் உருவாக்க முடியும், ஏனெனில் ஹை அறியப்படுகிறது, மேலும் இது விரைவான தரவு சுருக்கத்திற்கு அடிப்படையாக இருக்கலாம். செயல்திறன் மேம்பாடுகள் மற்றும் பொதுமைப்படுத்தல்கள் இந்த குறைப்புடன், வழிமுறை O (nL)-நேரம் மற்றும் O (nL)-இடம் ஆகும். இருப்பினும், "உகந்த நீளம்-வரையறுக்கப்பட்ட ஹஃப்மேன் குறியீடுகளுக்கான ஒரு வேகமான வழிமுறை" என்ற அசல் கட்டுரை, இதை எவ்வாறு O (nL)-நேரம் மற்றும் O (n)-இடமாக மேம்படுத்த முடியும் என்பதைக் காட்டுகிறது. முதல் முறையாக வழிமுறையை இயக்குவதே யோசனை, அசல் சிக்கலின் பாதி அளவைக் கொண்ட இரண்டு சமமான துணை சிக்கல்களைத் தீர்மானிக்க போதுமான தரவை மட்டுமே வைத்திருப்பது. இது மீண்டும் மீண்டும் செய்யப்படுகிறது, இதன் விளைவாக ஒரு வழிமுறை இரண்டு மடங்கு நேரம் எடுக்கும், ஆனால் நேரியல் இடம் மட்டுமே தேவைப்படுகிறது. பெருக்க மாறிலியைக் குறைப்பதற்கும், மீண்டும் மீண்டும் பிஸ் கொண்ட சிக்கல்கள் போன்ற சிறப்பு சந்தர்ப்பங்களில் அதை விரைவுபடுத்துவதற்கும் தொகுப்பு-இணைப்பு வழிமுறையில் பல மேம்பாடுகள் செய்யப்பட்டுள்ளன. தொகுப்பு-இணைப்பு அணுகுமுறை அகரவரிசை குறியீடு போன்ற தொடர்புடைய சிக்கல்களுக்கும் ஏற்றது. வரைபடக் கோட்பாட்டை உள்ளடக்கிய முறைகள் தொகுப்பு-இணைப்பு வழிமுறையை விட சிறந்த அறிகுறியற்ற இட சிக்கலைக் கொண்டுள்ளன என்று காட்டப்பட்டுள்ளது, ஆனால் இவை அதிக நடைமுறை பயன்பாட்டைக் காணவில்லை. குறிப்புகள் வெளிப்புற இணைப்புகள் தொகுப்பு-இணைப்பு வழிமுறையை செயல்படுத்துதல் "" தொகுப்பு-இணைப்பு வழிமுறையைப் பயன்படுத்தும் ஒரு வேகமான என்ட்ரோபி குறியீட்டாளர் இழப்பற்ற சுருக்க வழிமுறைகள் குறியீட்டு கோட்பாடு