Package-merge algorithm
પેકેજ-મર્જ અલ્ગોરિધમ એ માપ n ના આપેલ મૂળાક્ષર પર આપેલ વિતરણ માટે શ્રેષ્ઠ લંબાઈ-મર્યાદિત હફમેન કોડ શોધવા માટે O (nL)-સમયનું અલ્ગોરિધમ છે, જ્યાં કોઈ કોડ શબ્દ L કરતા લાંબો નથી. તે લોભી અલ્ગોરિધમ છે, અને હફમેનના મૂળ અલ્ગોરિધમનું સામાન્યીકરણ છે. પેકેજ-વિલિનીકરણ કોડ નિર્માણની સમસ્યાને દ્વિસંગી સિક્કા સંગ્રાહકની સમસ્યામાં ઘટાડીને કામ કરે છે. સિક્કા સંગ્રાહકની સમસ્યા ધારો કે સિક્કા સંગ્રાહક પાસે વિવિધ મૂલ્યવર્ગના સંખ્યાબંધ સિક્કા હોય છે, જેમાંથી દરેકનું સિક્કા મૂલ્ય તેના મૂલ્યવર્ગ સાથે અસંબંધિત હોય છે. સિક્કા સંગ્રહકર્તાની પાસે નાણાં ખતમ થઈ ગયા છે અને તેણે તેના સિક્કા સંગ્રહમાંથી અમુકનો ઉપયોગ કરીને એન મૂલ્યની વસ્તુ ખરીદવાની જરૂર છે. તે તેના લઘુતમ સિક્કા મૂલ્યના સંગ્રહમાંથી સિક્કાનો એક ઉપગણ પસંદ કરવા માંગે છે, જેના કુલ મૂલ્ય N છે. આ સમસ્યાનું દ્વિસંગી સ્વરૂપ એ છે કે તમામ મૂલ્યવર્ગ 2ની ઘાત એટલે કે 1,1/2,1/4, વગેરે છે. ડોલર. પેકેજ-મર્જ અલ્ગોરિધમનું વર્ણન ધારો કે સૌથી મોટો મૂલ્યવર્ગ 1 ડોલર છે, અને એન એક પૂર્ણાંક છે. (જો આ ધારણાઓ ન હોય તો પણ અલ્ગોરિધમ કામ કરે છે, તુચ્છ ફેરફારો દ્વારા.) સિક્કા સંગ્રાહક પહેલા પોતાના સિક્કાઓને સૂચિમાં અલગ કરે છે, દરેક મૂલ્ય માટે એક, સિક્કા મૂલ્ય દ્વારા વર્ગીકૃત. તે પછી તે સૌથી નાના મૂલ્યના સિક્કાઓને જોડીમાં પેક કરે છે, જે સૌથી નાના કુલ સિક્કા મૂલ્યની જોડીથી શરૂ થાય છે. જો એક સિક્કો બચ્યો હોય, તો તે તે મૂલ્યનો સૌથી વધુ સિક્કા મૂલ્યનો સિક્કો હશે, અને તેને અલગ રાખવામાં આવે છે અને હવેથી તેને અવગણવામાં આવે છે. આ પેકેજોને પછીના સૌથી નાના મૂલ્યના સિક્કાઓની યાદીમાં ફરીથી સિક્કા મૂલ્યના ક્રમમાં ભેળવી દેવામાં આવે છે. તે સૂચિમાંની વસ્તુઓને પછી જોડીમાં પેક કરવામાં આવે છે, અને આગામી સૌથી નાની સૂચિમાં મર્જ કરવામાં આવે છે, અને તેથી આગળ. છેવટે, વસ્તુઓની યાદી હોય છે, જેમાં દરેક 1 ડોલરનો સિક્કો હોય છે અથવા બે કે તેથી વધુ નાના સિક્કાઓ ધરાવતું પેકેજ હોય છે, જેની કુલ કિંમત 1 ડોલર હોય છે. તેમને સિક્કા મૂલ્યના ક્રમમાં પણ વર્ગીકૃત કરવામાં આવે છે. સિક્કા સંગ્રાહક પછી તેમાંથી સૌથી ઓછું મૂલ્ય N પસંદ કરે છે. નોંધ લો કે અલ્ગોરિધમનો સમય સિક્કાઓની સંખ્યામાં રેખીય છે. સિક્કા સંગ્રાહકની સમસ્યામાં લંબાઈ-મર્યાદિત હફમેન કોડિંગમાં ઘટાડો L એ કોઈપણ કોડ શબ્દની મહત્તમ લંબાઈ હોવાની મંજૂરી છે. ચાલો p1,., pn એ એન્કોડ કરવા માટેના મૂળાક્ષરના પ્રતીકોની આવૃત્તિઓ છે. આપણે પહેલા પ્રતીકોને ક્રમબદ્ધ કરીએ જેથી પાઇ ≤ પાઇ + 1 થાય. 2 − 1,., 2 − L મૂલ્યવર્ગના દરેક પ્રતીક માટે એલ સિક્કા બનાવો. ન્યૂનતમ સિક્કા મૂલ્યના સિક્કાઓના સમૂહને પસંદ કરવા માટે પેકેજ-મર્જ અલ્ગોરિધમનો ઉપયોગ કરો, જેમના મૂલ્યવર્ગ કુલ n − 1 છે. પસંદ કરેલા સિક્કાઓના મૂલ્ય પાઇની સંખ્યા હાય માની લો. શ્રેષ્ઠ લંબાઈ-મર્યાદિત હફમેન કોડ ચિહ્ન i ને લંબાઈ હાયની થોડી સ્ટ્રિંગ સાથે એન્કોડ કરશે. કેનોનિકલ હફમેન કોડ સરળતાથી એક સરળ બોટમ-અપ લોભી પદ્ધતિ દ્વારા બનાવી શકાય છે, જો કે હાય જાણીતા છે, અને આ ઝડપી ડેટા સંકોચન માટેનો આધાર હોઈ શકે છે. પ્રદર્શનમાં સુધારાઓ અને સામાન્યીકરણ આ ઘટાડા સાથે, અલ્ગોરિધમ O (nL)-સમય અને O (nL)-જગ્યા છે. જો કે, મૂળ પેપર, "શ્રેષ્ઠ લંબાઈ-મર્યાદિત હફમેન કોડ્સ માટે ઝડપી અલ્ગોરિધમ", દર્શાવે છે કે આને કેવી રીતે O (nL)-સમય અને O (n)-અવકાશમાં સુધારી શકાય છે. વિચાર એ છે કે અલ્ગોરિધમને પ્રથમ વખત ચલાવવું, માત્ર બે સમકક્ષ પેટા સમસ્યાઓ નક્કી કરવામાં સક્ષમ થવા માટે પૂરતી માહિતી રાખવી કે જે મૂળ સમસ્યાના અડધા કદનો સરવાળો કરે છે. આ પુનરાવર્તિત રીતે કરવામાં આવે છે, પરિણામે એક અલ્ગોરિધમ થાય છે જે લગભગ બમણો સમય લે છે પરંતુ માત્ર રેખીય જગ્યાની જરૂર પડે છે. ગુણાકાર અચળાંકને ઘટાડવા અને ખાસ કિસ્સાઓમાં તેને ઝડપી બનાવવા માટે પેકેજ-મર્જ અલ્ગોરિધમમાં અન્ય ઘણા સુધારા કરવામાં આવ્યા છે, જેમ કે પુનરાવર્તિત પી. આઈ. એસ. ધરાવતી સમસ્યાઓ. પેકેજ-વિલિનીકરણ અભિગમને વર્ણમાલા કોડિંગ જેવી સંબંધિત સમસ્યાઓ માટે પણ સ્વીકારવામાં આવ્યો છે. ગ્રાફ થિયરી સાથે સંકળાયેલી પદ્ધતિઓ પેકેજ-મર્જ અલ્ગોરિધમ કરતાં વધુ સારી એસિમ્પ્ટોટિક સ્પેસ કોમ્પ્લેક્સિટી હોવાનું દર્શાવવામાં આવ્યું છે, પરંતુ આનો વધુ વ્યવહારુ ઉપયોગ જોવા મળ્યો નથી. સંદર્ભો બાહ્ય કડીઓ પેકેજ-મર્જ અલ્ગોરિધમનો અમલ "" એક ઝડપી એન્ટ્રોપી કોડર જે પેકેજ-મર્જ અલ્ગોરિધમનો ઉપયોગ કરે છે લોસલેસ કમ્પ્રેશન અલ્ગોરિધમ્સ કોડિંગ થિયરી