Крафтын тэнцэтгэл биш

Чөлөөт нэвтэрхий толь — Википедиагаас
Харайх: Удирдах, Хайлт

Кодчлолын онолоор (coding theory) Крафтын тэнцэтгэл биш (Леон Крафтын нэрээр нэрлэгдсэн) нь префикс код (prefix code) бүрдүүлэх хангалттай нөхцлийг бүрдүүлэхээс (uniquely decodable code) гадна өгөгдсөн урттай нууц үгийн тайлагдагдахгүй байх кодыг бүрдүүлэхэд чухал үүрэг гүйцэтгэдэг. Энэхүү тэнцэтгэл биш нь компьютерийн шинжлэх ухаан болон мэдээлэл технелогийн префикс код болон модны хүрээнд хэрэглэгддэг.

Цаашилбал, Крафтын тэнцэтгэл биш нь префикс кодын(prefix code) нууц үгийн уртыг хязгаарладаг болно. Жишээ нь: хэрэв ашиглагдаж буй нууц үгийн (codeword) уртын илтгэгч функцыг авахад үлдсэн утга нь магадлалын олонлогын функцтэй төстэй утга үлдэх бөгөөд нийт хэмжээ нь 1-ээс бага буюу тэнцүү байна. Крафтын тэнцэтгэл биш нь нууц үгийн хүрээнд зарцуулах нэгдсэн нөөцөнд хүндрэлтэй тусах бөгөөд нууц үг богино байх тусам илүү хүндрэлтэй байна.


  • Хэрэв Крафтын тэнцэтгэл биш нь тодорхой тэнцэл биш агуулж байвал кодын хувьд илүүдэлтэй байна.
  • Хэрэв Крафтын тэнцэтгэл биш нь тэнцэл биш агуулж байвал асуулгыг бүрэн код гэнэ.
  • Хэрэв Крафтын тэнцэтгэл биш нь тэнцэл биш хэлбэртэй бол код нь цор ганц задлагч (uniquely decodable) байна .


Крафтын тэнцэтгэл бишийг 1949 онд Крафт гаргаж ирсэн. Гэхдээ Крафтын судалгаанд зөвхөн префикс кодын талаар л бичсэн ба Раймонд Рэдхэффэрийн тэнцэл биштэй адилтгаж анализ хийсэн байдаг. 1956 онд МкМиллан (1956)-ийн энэхүү тэнцэл бишийг ашиглан гаргасан нээлтийн дараа энэхүү тэнцэл бишийг Крафт-МкМилланын теором гэж мөн хэлэх болсон. 1955 онд Joseph Leo Doob-ны гаргаж байсан цор ганц задлагч uniquely decodable кодын ерөнхий байдал болон зарин хэлбэрийн префикс кодын шинж чанарыг МкМиллан (1956)нь энэхүү тэнцэл бишийг ашиглан нотолсон юм.

Жишээ[засварлах]

Хоёртын мод[засварлах]

9, 14, 19, 67, 76 нь модны навчнуудын оройнууд бөгөөд харгалзах өргөн нь 3, 3, 3, 3 болон 2 болно

Хоёртын модны (binary tree)навчнуудаар префикс кодын тодорхойлж болохыг Крафтын тэнцэтгэл биш нь баталдаг.

 \sum_{\ell \in \mathrm{leaves}} 2^{-\mathrm{depth}(\ell)} \leq 1.

Энд нийлбэр нь нийт навчны нийлбэрүүд бөгөөд. Ямар нэгэн хүүхэдгүй(No child) орой. Өргөн нь үзүүрийн язгуурын зай болно.

 \frac{1}{4} + 4 \left( \frac{1}{8} \right) = \frac{3}{4} \leq 1.


Чайтингийн тогтмол[засварлах]

Мэдээллийн технологийн шинжлэх ухааны алгоритмийн онолын хувьд Чайтины (Chaitin) тогтмол нь

\Omega = \sum_{p \in P} 2^{-|p|}.

Энэ нь хязгааргүй нийлбэр бөгөөд бичлэгийн хувьд зөв ч гацаж буй програмын хувьд нэг нэмэгдэхүүн байна.|p| нь p-гийн бит-ийн эгнээний уртыг тодорхойлно. Зөв бичигдсэн ч гацаж буй програмын хувьд префикс агуулсан нэмэгдэхүүн байхгүй бөгөөд иймд програм нь префикс код байхгүй байх шаардлагатай. Гэвч битийн эгнээ нь префикс код тул Крафтын тэнцэтгэл бишээр \Omega \leq 1.

Тодорхойлолт[засварлах]

Эх үүсвэр бүрийг үсгээр тэмдэглэн

S=\{\,s_1,s_2,\ldots,s_n\,\}\,

цор ганц задлах нь r нь үсэг хүртэл кодлох ба нууц үгийн урт нь дараахи байдлаар илэрхийлэгдэнэ.

\ell_1,\ell_2,\ldots,\ell_n.\,

тэгэхээр

\sum_{i=1}^{n} \left( \frac{1}{r} \right)^{\ell_i} \leq 1.

Тухайн \ell_1,\ell_2,\ldots,\ell_n\, -ийн хүрээнд дээрх тэнцэл бишийг хангаж буй дурын натурал тоонуудын хувьд эдгээр нууц үгийн урттай цор ганц задлах код нь r үсгийн хэмжээнд оршиж байдаг.

цор ганц задлах код нь префикс код байх тохиолдол элбэг байдаг. Иймд Крафтын тэнцэтгэл биш нь префикс код агуулж байдаг.

Префикс кодын баталгаа[засварлах]

2-тын модны жишээ. Улаан өнгөөр тэмдэглэсэн зангилаа нь префикс кодыг тодоор илэрхийлнэ. Тухайн зангилаанаас салаалж буй салаануудын тоог тооцоолох аргачлалыг доор үзүүлж байна.

Дээрхээс \ell_1 \leq \ell_2 \leq ... \leq \ell_n гэж үзвэл A нь r-тын модны \ell_n-ын нийт өргөн болно. \ell_n-тын модны r өргөний салаа бүрийн үсгийн хувьд урт нь \ell \leq \ell_n байна. Префикс кодын r-дэх үгийн салаа нь v_i ба A_i нь эхэүү зангилаанаас үүсэх язгуурын нь A туслах модны v_i навчнууд байна.

|A_i| = r^{\ell_n-\ell_i}.

Иймээс код нь префикс код тул,

A_i \cap A_j = \varnothing,\quad i\neq j.

тэгэхээр,\ell_n is r^{\ell_n} өргөний хувьд дурын нийт салааны нийлбэр нь,

|\bigcup_{i=1}^n A_i| = \sum_{i=1}^n r^{\ell_n-\ell_i} \leq r^{\ell_n}

бөгөөд эндээс үүдэн.

Дурын n натурал тоонуудын дараалал нь,

\ell_1 \leq \ell_2 \leq \dots \leq \ell_n

Ингэснээр Крафтын тэнцэтгэл бишийн хүрээнд \ell_i урттай нууц үгтэй префикс код боловсруулж болох ба энэ нь \ell_n өргөнтэй r-тын туслах модоор таслагдах болно. Эхлээд \ell_1 өргөнтэй модноос дурын зангилааг сонгож тухайн зангилааны бүх салааг устгах. Ингэснээр нийт модны r^{-\ell_1} зангилааны бутархай нь ашиглаж буй нууц үгийн үлдэгдэл болох болно. Дараагын давталт нь r^{-\ell_2} бутархайг r^{-\ell_1}+r^{-\ell_2} модноос салгана. m давталтын дараагаас,

\sum_{i=1}^m r^{-\ell_i}

Энэхүү бутархайг бодолтоос бүхэн устгаснаар нууц үгийн үлдсэн хэсэг нь ч нэсэн устах болно.Гэвч онолын хувьд энэхүү нийлбэр нь бүх m<n-ийн хувьд 1-ээс бага байна. Тэгэхээр префикс кодын урттай \ell_i байх бүх л n эх үүсвэрийн тэмдэгтийн хүрээнд боловсруулж болно.


Хоёртын модны баталгаа[засварлах]

Энд T нь 2-тын мод гэвэл T' нь T модны нэг хүүхэдтэй залгаасыг холбосон 2-тын мод юм. T' -ын бүх залгаас нь нэг эсвэл хоёр хүүхэдтэй байна. T -ын салаа бүр нь T' -д орсон байгаа иймд

 \sum_{\ell \in \mathrm{leaves}(T)} 2^{-\mathrm{depth}(\ell)} \leq \sum_{\ell \in \mathrm{leaves}(T')} 2^{-\mathrm{depth}(\ell)} \;.

Дурын сонголтын хувьд T' нь одоогын залгаасын хувьд навчинд хүртлээ баруун зүүн талруугаа тогтмол хөдөлж байдаг. Энэхүү хөдөлгөөн нь нэг навчинд хүрэх магадлал нь \ell, бөгөөд 2^{-\mathrm{depth}(\ell)} байна. тэгэхээр магадлалын тархаалт нь \langle 2^{-\mathrm{depth}(\ell)} : \ell \in \mathrm{leaves}(T') \rangle болно

\sum_{\ell \in \mathrm{leaves}(T')} 2^{-\mathrm{depth}(\ell)} = 1 \;.

Үр дүнгийн эсрэг утгын нотолгоог дээр үзүүлэв.

Ерөнхий тохиолдлын баталгаа[засварлах]

S кодын хүрээнд x-ийн эсрэг функц нь доорх гэж үзвэл

 F(x) = \sum_{i=1}^n x^{-|s_i|} = \sum_{\ell=\min}^\max p_\ell \, x^{-\ell}
x^{-\ell}-ийн өмнө байгаа p_\ell нь хувьсагч \ell урттай нууц үгийн ялгаатай дугаар юм. Энд min нь S-ийн хамгийн богино нууц үгийн урт ба max нь хамгийн урт нууц үгийн урт болно.

Дурын эерэг бүхэл тоо m нь Sm бүтээгдэхүүнийг m-ээр хааж байна гэж үзэх бөгөөд s_{i_1}s_{i_2}\dots s_{i_m}-ийг агуулж байдаг бол i_1, i_2, \dots, i_m нь 1 болон n-ийн хооронд зааглагддаг. S нь цор ганц задлах боломжтой шинжтэй ба, хэрэв s_{i_1}s_{i_2}\dots s_{i_m}=s_{j_1}s_{j_2}\dots s_{j_m}, бол i_1=j_1, i_2=j_2, \dots, i_m=j_m байна. Өөрөөр хэлбэл S^m-ийн бүх хэллэг нь S-ийн нууц үгнүүдийн онцгой дарааллаас үүссэн байна. Иймд S^m-ийн хувьд G(x) функцээс F(x) үүсгэх боломжгүй юм.

G(x) = \left( F(x) \right)^m = \left( \sum_{i=1}^n x^{-|s_i|} \right)^m
= \sum_{i_1=1}^n \sum_{i_2=1}^n \cdots \sum_{i_m=1}^n x^{-\left(|s_{i_1}| + |s_{i_2}| + \cdots + |s_{i_m}|\right)} = \sum_{i_1=1}^n \sum_{i_2=1}^n \cdots \sum_{i_m=1}^n x^{-|s_{i_1} s_{i_2}\cdots s_{i_m}|} 
= \sum_{\ell=m \cdot \min}^{m \cdot \max} q_\ell \, x^{-\ell} \; .

Энд G(x)-д байгаа x^{-\ell}-ийн өмнөх q_\ell хувьсагч нь S^m-д байгаа \ell уртын үгийн тоо юм. q_\ell нь r^\ell-ээс урт байж болохгүй. Иймд дурын эерэг x нь


\left( F(x) \right)^m \le \sum_{\ell=m \cdot \min}^{m \cdot \max} r^\ell \, x^{-\ell} \; .

Хэрэв x = r хэмээн орлуулсан тохиолдолд


\left( F(r) \right)^m \le m \cdot (\max-\min)+1

Тухайн m нь дурын бүхэл эерэг тоо байна. Тэнцэтгэл бишийн зүүн тал нь m-ийн илтгэгч зэргээр өсөх ба баруун тал нь шугаман хэлбэрээр өснө. Тэнцэтгэл биш нь m-ийн бүх утгын хувьд зөв байх боломж нь  F(r) \le 1 . Иймд F(x)-ийн тодорхойлолт ёсоор бид дараахи тэнцэл биштэй болно.


\sum_{i=1}^n r^{-\ell_i} = \sum_{i=1}^n r^{-|s_i|} = F(r)  \le 1 \; .


Жагсаалт[засварлах]