عدم المساواة كرافت-ماكميلان

أولاً، دعونا نبين أن متباينة كرافت صحيحة كلما كان رمز لـ${\displaystyle S}$هو رمز بادئة.

لنفترض أن${\displaystyle \ell _{1}\leqslant \ell _{2}\leqslant \cdots \leqslant \ell _{n}}$. يترك${\displaystyle A}$كن كاملاً${\displaystyle r}$شجرة ذات عمق${\displaystyle \ell _{n}}$(وبالتالي، كل عقدة من${\displaystyle A}$على مستوى${\displaystyle <\ell _{n}}$لديه${\displaystyle r}$الأطفال، بينما العقد في المستوى${\displaystyle \ell _{n}}$هي أوراق الشجر). كل كلمة بطول${\displaystyle \ell \leqslant \ell _{n}}$فوق${\displaystyle r}$يتوافق الأبجدية -ary مع عقدة في هذه الشجرة على عمق${\displaystyle \ell }$. ال${\displaystyle i}$الكلمة رقم في رمز البادئة تتوافق مع عقدة${\displaystyle v_{i}}$؛ يترك${\displaystyle A_{i}}$لتكن مجموعة جميع العقد الطرفية (أي العقد الموجودة على عمق${\displaystyle \ell _{n}}$) في الشجرة الفرعية لـ${\displaystyle A}$متجذرة في${\displaystyle v_{i}}$. ذلك الفرع ذو الارتفاع${\displaystyle \ell _{n}-\ell _{i}}$لدينا

${\displaystyle |A_{i}|=r^{\ell _{n}-\ell _{i}}.}$

بما أن الرمز هو رمز بادئة، فلا يمكن لتلك الأشجار الفرعية أن تشترك في أي أوراق، مما يعني أن

${\displaystyle A_{i}\cap A_{j}=\varnothing ,\quad i\neq j.}$

وبالتالي، بالنظر إلى أن العدد الإجمالي للعقد عند العمق${\displaystyle \ell _{n}}$يكون${\displaystyle r^{\ell _{n}}}$لدينا

${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}|A_{i}|=\sum _{i=1}^{n}r^{\ell _{n}-\ell _{i}}\leqslant r^{\ell _{n}}}$

ومن ثمّ تترتب النتيجة.

وعلى العكس من ذلك، بالنظر إلى أي تسلسل مرتب من${\displaystyle n}$الأعداد الطبيعية،

${\displaystyle \ell _{1}\leqslant \ell _{2}\leqslant \cdots \leqslant \ell _{n}}$

بتحقيق متباينة كرافت، يمكن للمرء إنشاء رمز بادئة بأطوال كلمات رمزية متساوية لكل منها${\displaystyle \ell _{i}}$عن طريق اختيار كلمة طويلة${\displaystyle \ell _{i}}$بشكل تعسفي، ثم استبعاد جميع الكلمات الأطول التي تبدأ بها. ومرة ​​أخرى، سنفسر هذا من حيث العقد الطرفية لـ${\displaystyle r}$شجرة ذات عمق${\displaystyle \ell _{n}}$اختر أولاً أي عقدة من الشجرة الكاملة عند العمق${\displaystyle \ell _{1}}$إنها تُطابق الكلمة الأولى في رمزنا الجديد. وبما أننا نبني رمزًا بادئًا، فإن جميع الكلمات الفرعية لهذه العقدة (أي جميع الكلمات التي تبدأ بهذه الكلمة كبادئة) تصبح غير مناسبة للإدراج في الرمز. ندرس الكلمات الفرعية على عمق معين.${\displaystyle \ell _{n}}$(أي، العقد الطرفية بين الفروع)؛ هناك ${\displaystyle r^{\ell _{n}-\ell _{1}}}$يتم استبعاد هذه العقد الفرعية من الاعتبار. في التكرار التالي، يتم اختيار عقدة (باقية) على عمق معين.${\displaystyle \ell _{2}}$ويزيل${\displaystyle r^{\ell _{n}-\ell _{2}}}$ثم المزيد من العقد الورقية، وهكذا. بعد ذلك${\displaystyle n}$بعد عدة تكرارات، قمنا بإزالة ما مجموعه

${\displaystyle \sum _{i=1}^{n}r^{\ell _{n}-\ell _{i}}}$

العقد. السؤال هو ما إذا كنا بحاجة إلى إزالة عدد من العقد الطرفية يفوق العدد المتاح لدينا فعلياً .${\displaystyle r^{\ell _{n}}}$بالمجمل ، في عملية بناء الكود. وبما أن متباينة كرافت صحيحة، فقد حققنا بالفعل

${\displaystyle \sum _{i=1}^{n}r^{\ell _{n}-\ell _{i}}\leqslant r^{\ell _{n}}}$

وبالتالي يمكن إنشاء رمز بادئة. تجدر الإشارة إلى أنه نظرًا لأن اختيار العقد في كل خطوة هو اختياري إلى حد كبير، فإنه يمكن إنشاء العديد من رموز البادئة المناسبة المختلفة، بشكل عام.

سنثبت الآن أن متباينة كرافت صحيحة كلما${\displaystyle S}$هو رمز قابل للفك بشكل فريد. (لا حاجة لإثبات العكس، فقد أثبتناه بالفعل لرموز البادئة، وهو ادعاء أقوى). البرهان من إعداد جاك آي. كاروش. ^{[ 3 ] [ 4 ]}

يكفينا إثبات ذلك عندما يكون عدد الكلمات المشفرة محدودًا. أما إذا كان عددها لانهائيًا، فإن أي مجموعة جزئية محدودة منها قابلة للفك بشكل فريد، وبالتالي تحقق متباينة كرافت-ماكميلان. وبأخذ النهاية، نحصل على المتباينة للرمز الكامل.

دل${\displaystyle C=\sum _{i=1}^{n}r^{-l_{i}}}$تتمثل فكرة البرهان في الحصول على حد أعلى لـ${\displaystyle C^{m}}$ل${\displaystyle m\in \mathbb {N} }$وأظهر أن ذلك لا يمكن أن يكون صحيحًا إلا لجميع${\displaystyle m}$لو${\displaystyle C\leq 1}$أعد كتابة${\displaystyle C^{m}}$مثل

${\displaystyle {\begin{aligned}C^{m}&=\left(\sum _{i=1}^{n}r^{-l_{i}}\right)^{m}\\&=\sum _{i_{1}=1}^{n}\sum _{i_{2}=1}^{n}\cdots \sum _{i_{m}=1}^{n}r^{-\left(l_{i_{1}}+l_{i_{2}}+\cdots +l_{i_{m}}\right)}\\\end{aligned}}}$

ضع في اعتبارك جميع القوى m${\displaystyle S^{m}}$، في شكل كلمات${\displaystyle s_{i_{1}}s_{i_{2}}\dots s_{i_{m}}}$، أين${\displaystyle i_{1},i_{2},\dots ,i_{m}}$هي مؤشرات بين 1 و${\displaystyle n}$لاحظ أنه بما أن S يفترض أنها قابلة للفك بشكل فريد، ${\displaystyle s_{i_{1}}s_{i_{2}}\dots s_{i_{m}}=s_{j_{1}}s_{j_{2}}\dots s_{j_{m}}}$يشير إلى${\displaystyle i_{1}=j_{1},i_{2}=j_{2},\dots ,i_{m}=j_{m}}$هذا يعني أن كل عنصر من عناصر المجموع يتوافق مع كلمة واحدة فقط في${\displaystyle S^{m}}$وهذا يسمح لنا بإعادة كتابة المعادلة إلى

${\displaystyle C^{m}=\sum _{\ell =1}^{m\cdot \ell _{max}}q_{\ell }\,r^{-\ell }}$

أين${\displaystyle q_{\ell }}$عدد الكلمات السرية في${\displaystyle S^{m}}$من الطول${\displaystyle \ell }$و${\displaystyle \ell _{max}}$يمثل طول أطول كلمة رمزية في${\displaystyle S}$لـ${\displaystyle r}$الأبجدية - الحروف فقط${\displaystyle r^{\ell }}$الكلمات المحتملة ذات الطول${\displaystyle \ell }$، لذا${\displaystyle q_{\ell }\leq r^{\ell }}$باستخدام هذا، نحدد الحد الأعلى${\displaystyle C^{m}}$:

${\displaystyle {\begin{aligned}C^{m}&=\sum _{\ell =1}^{m\cdot \ell _{max}}q_{\ell }\,r^{-\ell }\\&\leq \sum _{\ell =1}^{m\cdot \ell _{max}}r^{\ell }\,r^{-\ell }=m\cdot \ell _{max}\end{aligned}}}$

أخذ${\displaystyle m}$الجذر رقم -th، نحصل على

${\displaystyle C=\sum _{i=1}^{n}r^{-l_{i}}\leq \left(m\cdot \ell _{max}\right)^{\frac {1}{m}}}$

ينطبق هذا الحد على أي${\displaystyle m\in \mathbb {N} }$الطرف الأيمن يساوي 1 تقريبًا، لذا${\displaystyle \sum _{i=1}^{n}r^{-l_{i}}\leq 1}$يجب أن يتحقق الشرط (وإلا فإن عدم المساواة سيُكسر لقيمة كبيرة بما فيه الكفاية).${\displaystyle m}$).

بالنظر إلى سلسلة من${\displaystyle n}$الأعداد الطبيعية،

${\displaystyle \ell _{1}\leqslant \ell _{2}\leqslant \cdots \leqslant \ell _{n}}$

بتحقيق متباينة كرافت، يمكننا إنشاء رمز بادئة على النحو التالي. نُعرّف الكلمة الرمزية ^رقم i ، C _i ، بأنها الأولى${\displaystyle \ell _{i}}$الأرقام التي تلي الفاصلة العشرية (مثل الفاصلة العشرية) في التمثيل الأساسي r لـ

${\displaystyle \sum _{j=1}^{i-1}r^{-\ell _{j}}.}$

لاحظ أنه وفقًا لمتباينة كرافت، فإن هذا المجموع لا يتجاوز 1 أبدًا. وبالتالي، فإن الكلمات المشفرة تلتقط القيمة الكاملة للمجموع. لذلك، بالنسبة لـ j > i ، فإن الأول${\displaystyle \ell _{i}}$تشكل أرقام C _j عددًا أكبر من C _i ، لذا فإن الشفرة خالية من البادئات.