Kraft–McMillan inequality
کوڈنگ تھیوری میں، کرافٹ-میک ملن عدم مساوات کوڈ ورڈ کی لمبائی کے دیئے گئے سیٹ کے لیے ایک سابقہ کوڈ (لیون جی کرافٹ کے ورژن میں) یا ایک منفرد ڈیکوڈیبل کوڈ (بروک وے میک ملن کے ورژن میں) کے وجود کے لیے ایک ضروری اور کافی شرط دیتی ہے۔ پریفیکس کوڈز اور ٹریز کے لیے اس کی ایپلی کیشنز اکثر کمپیوٹر سائنس اور انفارمیشن تھیوری میں استعمال ہوتی ہیں۔ کرافٹ کی عدم مساوات میں شائع ہوئی تھی۔ تاہم، کرافٹ کے مقالے میں صرف سابقہ کوڈز پر بحث کی گئی ہے، اور عدم مساوات کا باعث بننے والے تجزیے کو ریمنڈ ریڈ ہیفر سے منسوب کیا گیا ہے۔ نتیجہ آزادانہ طور پر دریافت کیا گیا۔ میک ملن منفرد طور پر ڈی کوڈ ایبل کوڈز کے عمومی کیس کے نتائج کو ثابت کرتا ہے، اور پریفیکس کوڈز کے ورژن کو 1955 میں جوزف لیو ڈوب کے بولی جانے والی مشاہدے سے منسوب کرتا ہے۔ ایپلی کیشنز اور وجدان کرافٹ کی عدم مساوات ایک سابقہ کوڈ میں کوڈ ورڈز کی لمبائی کو محدود کرتی ہے: اگر کوئی ہر درست کوڈ ورڈ کی لمبائی کا ایکسپونینشل لیتا ہے، تو اس کے نتیجے میں اقدار کا مجموعہ ممکنہ ماس فنکشن کی طرح نظر آنا چاہیے، یعنی اس کی کل پیمائش ایک سے کم یا برابر ہونی چاہیے۔ کرافٹ کی عدم مساوات کے بارے میں کوڈ ورڈز پر خرچ کیے جانے والے محدود بجٹ کے لحاظ سے سوچا جا سکتا ہے، جس میں چھوٹے کوڈ ورڈز زیادہ مہنگے ہوتے ہیں۔ عدم مساوات سے درج ذیل مفید خصوصیات میں درج ذیل بیانات ہیں: اگر کرافٹ کی عدم مساوات سخت عدم مساوات کے ساتھ ہے، تو کوڈ میں کچھ بے کار پن ہے۔ اگر کرافٹ کی عدم مساوات مساوات کے ساتھ ہے، تو زیر بحث کوڈ ایک مکمل کوڈ ہے۔ اگر کرافٹ کی عدم مساوات برقرار نہیں رہتی ہے، تو کوڈ منفرد طور پر ڈی کوڈ ایبل نہیں ہے۔ ہر منفرد ڈی کوڈ ایبل کوڈ کے لیے، ایک ہی لمبائی کی تقسیم کے ساتھ ایک پریفیکس کوڈ موجود ہے۔ رسمی بیان حروف تہجی سے ہر ماخذ کی علامت کو کوڈ ورڈ کی لمبائی کے ساتھ سائز کے حروف تہجی پر ایک منفرد ڈیکوڈ ایبل کوڈ میں انکوڈ کیا جائے۔ پھر اس کے برعکس، مندرجہ بالا عدم مساوات کو پورا کرنے والے قدرتی اعداد کے دیئے گئے سیٹ کے لیے، ان کوڈ ورڈ کی لمبائی کے ساتھ سائز کے حروف تہجی پر ایک منفرد ڈیکوڈ ایبل کوڈ موجود ہے۔ مثال: بائنری ٹری کسی بھی بائنری ٹری کو ٹری کے پتوں کے لیے پریفیکس کوڈ کی وضاحت کے طور پر دیکھا جا سکتا ہے۔ کرافٹ کی عدم مساوات بتاتی ہے کہ یہاں رقم درخت کے پتوں پر لی جاتی ہے، یعنی۔ بچوں کے بغیر نوڈس۔ گہرائی جڑ نوڈ کا فاصلہ ہے۔ دائیں طرف کے درخت میں، یہ رقم پریفیکس کوڈز کے لیے ثبوت کا ثبوت ہے۔ پہلے، آئیے یہ ظاہر کریں کہ جب بھی کوڈ کے لیے پریفیکس کوڈ ہوتا ہے تو کرافٹ کی عدم مساوات برقرار رہتی ہے۔ فرض کریں کہ۔ گہرائی کا مکمل-ایری درخت ہونے دیں (اس طرح، سطح کے ہر نوڈ میں بچے ہوتے ہیں، جبکہ سطح پر نوڈ پتے ہوتے ہیں)۔ - ary حروف تہجی پر لمبائی کا ہر لفظ گہرائی میں اس درخت کے نوڈ سے مطابقت رکھتا ہے۔ سابقہ کوڈ میں واں لفظ نوڈ سے مطابقت رکھتا ہے ؛ تمام لیف نوڈس کا مجموعہ ہونے دیں (یعنی۔ گہرائی میں نوڈس کا) جڑ کے ذیلی درخت میں۔ چونکہ کوڈ ایک پریفیکس کوڈ ہے، اس لیے وہ سبٹریز کسی بھی پتے کا اشتراک نہیں کر سکتے، جس کا مطلب ہے کہ اس طرح، یہ دیکھتے ہوئے کہ گہرائی میں نوڈس کی کل تعداد ہے، ہمارے پاس ہے جس سے نتیجہ آتا ہے۔ اس کے برعکس، قدرتی اعداد کی کسی بھی ترتیب شدہ ترتیب کو دیکھتے ہوئے، کرافٹ کی عدم مساوات کو مطمئن کرتے ہوئے، کوئی بھی صوابدیدی طور پر لمبائی کے لفظ کا انتخاب کرکے کوڈ ورڈ کی لمبائی کے ساتھ ایک سابقہ کوڈ بنا سکتا ہے، پھر زیادہ لمبائی کے ان تمام الفاظ کو مسترد کر سکتا ہے جن میں یہ سابقہ ہوتا ہے۔ وہاں ایک بار پھر، ہم اس کی تشریح گہرائی کے درخت کے پتی کے نوڈس کے لحاظ سے کریں گے۔ پہلے گہرائی میں پورے درخت سے کسی بھی نوڈ کا انتخاب کریں ؛ یہ ہمارے نئے کوڈ کے پہلے لفظ سے مطابقت رکھتا ہے۔ چونکہ ہم ایک پریفیکس کوڈ بنا رہے ہیں، اس نوڈ کی تمام نسلیں (یعنی وہ تمام الفاظ جن میں یہ پہلا لفظ بطور پریفیکس ہے) کوڈ میں شامل کرنے کے لیے نامناسب ہو جاتے ہیں۔ ہم اولاد کو گہرائی میں دیکھتے ہیں (یعنی اولاد کے درمیان پتی کے نوڈس) ؛ ایسے نسل نوڈس ہیں جنہیں غور سے ہٹا دیا جاتا ہے۔ اگلی تکرار گہرائی میں ایک (زندہ) نوڈ کو چنتی ہے اور مزید پتی کے نوڈس کو ہٹا دیتی ہے، وغیرہ۔ تکرار کے بعد، ہم نے کل نوڈس کو ہٹا دیا ہے۔ سوال یہ ہے کہ کیا ہمیں کوڈ بنانے کے عمل میں اصل میں دستیاب-مجموعی طور پر-سے زیادہ لیف نوڈس کو ہٹانے کی ضرورت ہے۔ چونکہ کرافٹ کی عدم مساوات برقرار ہے، ہمارے پاس واقعی ہے اور اس طرح ایک سابقہ کوڈ بنایا جا سکتا ہے۔ نوٹ کریں کہ چونکہ ہر مرحلے پر نوڈس کا انتخاب بڑی حد تک من مانی ہے، اس لیے عام طور پر بہت سے مختلف موزوں سابقہ کوڈ بنائے جا سکتے ہیں۔ عام معاملے کا ثبوت اب ہم یہ ثابت کریں گے کہ جب بھی منفرد طور پر ڈی کوڈ ایبل کوڈ ہوتا ہے تو کرافٹ کی عدم مساوات برقرار رہتی ہے۔ (اس کے برعکس ثابت کرنے کی ضرورت نہیں ہے، کیونکہ ہم پہلے ہی اسے سابقہ کوڈز کے لیے ثابت کر چکے ہیں، جو کہ ایک مضبوط دعوی ہے۔) اشارہ کریں۔ ثبوت کا خیال یہ ہے کہ اس کے لیے اوپری حد حاصل کی جائے اور یہ ظاہر کیا جائے کہ یہ صرف اس صورت میں سب کے لیے برقرار رہ سکتا ہے جب. الفاظ کی شکل میں تمام ایم-پاورز پر غور کریں، جہاں 1 اور 1 کے درمیان انڈیکس ہیں۔ نوٹ کریں کہ، چونکہ S کو منفرد طور پر ڈیکوڈیبل سمجھا گیا تھا، اس کا مطلب ہے۔ اس کا مطلب یہ ہے کہ ہر خلاصہ بالکل ایک لفظ سے مطابقت رکھتا ہے۔ یہ ہمیں مساوات کو دوبارہ لکھنے کی اجازت دیتا ہے جہاں لمبائی میں کوڈ ورڈز کی تعداد ہے اور اس میں سب سے طویل کوڈ ورڈ کی لمبائی ہے۔ ایک حرفی حروف تہجی کے لیے صرف لمبائی کے ممکنہ الفاظ ہوتے ہیں۔ اس کا استعمال کرتے ہوئے، ہم اوپری باؤنڈ کرتے ہیں:-th جڑ کو لیتے ہوئے، ہمیں یہ باؤنڈ کسی کے لیے بھی ملتا ہے۔ دائیں طرف غیر علامتی طور پر 1 ہے، لہذا اسے برقرار رکھنا چاہیے (بصورت دیگر عدم مساوات کافی بڑی حد تک ٹوٹ جائے گی)۔ متغیر کے لیے متبادل تعمیر قدرتی اعداد کی ترتیب کو دیکھتے ہوئے، کرافٹ کی عدم مساوات کو مطمئن کرتے ہوئے، ہم مندرجہ ذیل طور پر ایک سابقہ کوڈ بنا سکتے ہیں۔ ریڈکس پوائنٹ کے بعد پہلے ہندسوں کے طور پر کوڈ ورڈ، سی آئی کی وضاحت کریں (مثال کے طور پر۔ اعشاریہ نقطہ) بیس آر کی نمائندگی میں نوٹ کریں کہ کرافٹ کی عدم مساوات کے لحاظ سے یہ مجموعہ کبھی بھی 1 سے زیادہ نہیں ہوتا ہے۔ لہذا کوڈ ورڈز رقم کی پوری قیمت پر قبضہ کرتے ہیں۔ لہذا، جے> آئی کے لیے، سی جے کے پہلے ہندسے سی آئی سے بڑی تعداد بناتے ہیں، اس لیے کوڈ پریفیکس فری ہے۔ حوالہ جات نوٹ کریں۔ ۔ چیتین کا مستقل کینونکل ہفمین کوڈ کوڈنگ تھیوری عدم مساوات بھی دیکھیں۔