असमान अक्षर लागत (Unequal Letter Costs) के लिए इष्टतम प्रीफिक्स-फ्री कोड (Optimal Prefix-free Codes) खोजने की समस्या में एक न्यूनतम लागत प्रीफिक्स-फ्री कोड की गणना शामिल है जिसमें एन्कोडिंग वर्णमाला में असमान लागत (लंबाई) के अक्षर होते हैं, लंबाई α और β की, जहां α ≤ β। हम स्वयं को बाइनरी ट्री तक सीमित रखते हैं।
कोड को एक लॉप्साइडेड ट्री (Lopsided Tree) द्वारा दर्शाया जाता है, उसी तरह जैसे हफमैन ट्री (Huffman Tree) हफमैन कोडिंग समस्या के समाधान को दर्शाता है। समानता के बावजूद, असमान अक्षर लागत का मामला शास्त्रीय हफमैन समस्या की तुलना में बहुत कठिन है; सामान्य अक्षर लागत के लिए कोई बहुपद समय एल्गोरिदम (Polynomial Time Algorithm) ज्ञात या उपलब्ध नहीं है, समस्या पर समृद्ध साहित्य के बावजूद।
हालांकि, जब α और β पूर्णांक स्थिरांक (Integer Constants) होते हैं तो ज्ञात बहुपद समय एल्गोरिदम उपलब्ध हैं।
इस मामले में न्यूनतम लागत ट्री की गणना की समस्या का अध्ययन पहली बार 1961 में कार्प (Karp) द्वारा किया गया था जिन्होंने इस समस्या को पूर्णांक रैखिक प्रोग्रामिंग (Integer Linear Programming) में घटाकर हल किया था, जिससे n और β दोनों में घातीय (Exponential) एल्गोरिदम उत्पन्न हुआ। उस समय से समस्या के विभिन्न पहलुओं पर बहुत काम हुआ है जैसे; इष्टतम ट्री की लागत को बांधना; विशेष मामले तक सीमित जब सभी वजन बराबर हों।
इन सभी प्रयासों के बावजूद यह अभी भी, आश्चर्यजनक रूप से, अज्ञात है कि क्या मूल समस्या बहुपद-समय हल करने योग्य (Polynomial-time Solvable) है या NP-पूर्ण (NP-complete)।
गोलिन और रोट (Golin and Rote) एक O(n^{β+2})-समय डायनामिक प्रोग्रामिंग एल्गोरिदम का वर्णन करते हैं जो ट्री को टॉप-डाउन फैशन (Top-down Fashion) में बनाता है।
इसे एक अलग दृष्टिकोण (मोनोटोन-मैट्रिक्स अवधारणाएं, जैसे मोंज गुण (Monge Property) और SMAWK एल्गोरिदम) लागू करके सुधारा गया है।
थ्योरम 1 (THEOREM 1): इष्टतम लॉप्साइडेड ट्रीज़ को O(n^β) समय में बनाया जा सकता है।
यह β के छोटे मान के मामले के लिए सबसे कुशल ज्ञात एल्गोरिदम है; व्यवहार में अक्षर लागत आमतौर पर छोटी होती है (उदाहरण के लिए, मोर्स कोड)।
हाल ही में एक कुशल सन्निकटन एल्गोरिदम (Approximating Algorithm) की योजना प्रदान की गई है।
थ्योरम 2 (THEOREM 2)
इष्टतम लॉप्साइडेड ट्रीज़ के लिए एक बहुपद समय सन्निकटन योजना (Polynomial Time Approximation Scheme) मौजूद है।
