असमान अक्षर लागतों के लिए इष्टतम उपसर्ग-मुक्त कोड खोजने की समस्या में न्यूनतम लागत उपसर्ग-मुक्त कोड की गणना करना शामिल है जिसमें एन्कोडिंग वर्णमाला में असमान लागत (लंबाई) अक्षर होते हैं, लंबाई α और β, जहां α β। हम खुद को बाइनरी ट्री तक सीमित रखते हैं।
कोड को एकतरफा पेड़ द्वारा दर्शाया जाता है, उसी तरह जैसे हफमैन पेड़ हफमैन कोडिंग समस्या के समाधान का प्रतिनिधित्व करता है। समानता के बावजूद, असमान पत्र लागत का मामला शास्त्रीय हफ़मैन समस्या की तुलना में बहुत कठिन है; समस्या पर एक समृद्ध साहित्य के बावजूद, कोई बहुपद समय एल्गोरिदम ज्ञात या सामान्य अक्षर लागत के लिए उपलब्ध नहीं है।
हालांकि, ज्ञात बहुपद समय एल्गोरिदम उपलब्ध हैं α और β पूर्णांक स्थिरांक हैं।
इस मामले में कम से कम लागत वाले पेड़ की गणना की समस्या का पहली बार 1961 में कार्प द्वारा अध्ययन किया गया था, जिसने n और β दोनों में एक एल्गोरिथ्म घातांक का निर्माण करते हुए पूर्णांक रैखिक प्रोग्रामिंग में कमी करके समस्या का समाधान किया। उस समय से समस्या के विभिन्न पहलुओं पर बहुत काम हुआ है जैसे; इष्टतम पेड़ की लागत को सीमित करना; विशेष मामले की सीमा जब सभी भार समान हों।
इन सभी प्रयासों के बावजूद, यह अभी भी आश्चर्यजनक रूप से अज्ञात है कि मूल समस्या बहुपद-समय हल करने योग्य है या एनपी-पूर्ण।
गोलिन और रोटे एक O(nβ+2)-टाइम डायनेमिक प्रोग्रामिंग एल्गोरिथम का वर्णन करते हैं जो ट्री को टॉप-डाउन फैशन में बनाता है।
इसे एक अलग दृष्टिकोण (मोनोटोन-मैट्रिक्स अवधारणाएं, उदाहरण के लिए, मोंज प्रॉपर्टी और एसएमएडब्ल्यूके एल्गोरिदम) को लागू करने में सुधार किया गया है।
प्रमेय 1:इष्टतम एकतरफा पेड़ों का निर्माण O(nβ) समय में किया जा सकता है।
β के छोटे मान के मामले में यह सबसे कुशल ज्ञात एल्गोरिथम है; व्यवहार में पत्र की लागत आम तौर पर छोटी होती है (उदा., मोर्स कोड)।
हाल ही में एक कुशल सन्निकटन एल्गोरिथ्म की एक योजना प्रदान की गई है।
प्रमेय 2
इष्टतम एकतरफा पेड़ों के लिए एक बहुपद समय सन्निकटन योजना है।