Bài toán tìm mã không có tiền tố tối ưu cho chi phí chữ cái không bằng nhau bao gồm việc tính toán một mã không có tiền tố chi phí tối thiểu trong đó bảng chữ cái mã hóa bao gồm các chữ cái có giá (độ dài) không bằng nhau, có độ dài α và β, trong đó α ≤ β. Chúng tôi giới hạn bản thân giới hạn trong cây nhị phân.
Mã được biểu diễn bằng một cây lệch, theo cách tương tự như cây Huffman biểu thị giải pháp của vấn đề mã hóa Huffman. Mặc dù giống nhau, trường hợp chi phí thư không bằng nhau khó hơn nhiều so với bài toán Huffman cổ điển; không có thuật toán thời gian đa thức nào được biết đến hoặc có sẵn cho chi phí thư chung, mặc dù có tài liệu phong phú về vấn đề này.
Tuy nhiên, có các thuật toán thời gian đa thức đã biết sẵn có α và β là các hằng số nguyên.
Bài toán tính toán cây có chi phí thấp nhất trong trường hợp này lần đầu tiên được nghiên cứu bởi Karp vào năm 1961, người đã giải quyết vấn đề bằng cách rút gọn thành lập trình tuyến tính số nguyên, tạo ra một thuật toán hàm mũ trong cả n và β. Kể từ thời điểm đó, đã có nhiều nghiên cứu về các khía cạnh khác nhau của vấn đề như; giới hạn chi phí của cây tối ưu; giới hạn cho trường hợp đặc biệt khi tất cả các trọng số bằng nhau.
Bất chấp tất cả những nỗ lực này, đáng ngạc nhiên là vẫn chưa xác định được vấn đề cơ bản là giải theo thời gian đa thức hay ở dạng NP -complete.
Golin và Rote mô tả thuật toán lập trình động thời gian O (nβ + 2) xây dựng cây theo kiểu từ trên xuống.
Điều này đã được cải thiện khi triển khai một cách tiếp cận khác (các khái niệm ma trận đơn điệu, ví dụ:thuộc tính Monge và thuật toán SMAWK.
LÝ THUYẾT 1:Có thể tạo cây lệch tầng tối ưu trong thời gian O (nβ).
Đây là thuật toán hiệu quả nhất được biết đến cho trường hợp giá trị nhỏ của β; trong thực tế, chi phí thư thường nhỏ (ví dụ:mã Morse).
Gần đây, một lược đồ của một thuật toán ước lượng hiệu quả đã được cung cấp.
LÝ THUYẾT 2
Có một lược đồ xấp xỉ thời gian đa thức cho các cây có độ lệch tối ưu.