Хаффманы алгоритмыг өгөгдлийг шахах эсвэл кодлоход ашигладаг. Ер нь текст файлын тэмдэгт бүрийг ASCII кодчилол ашиглан тухайн тэмдэгтэд харуулсан найман бит (0 эсвэл 1 гэсэн цифрүүд) хэлбэрээр хадгалдаг. Хаффман кодчилсон файл нь хатуу 8 битийн бүтцийг задалдаг тул хамгийн түгээмэл хэрэглэгддэг тэмдэгтүүдийг хэдхэн битээр хадгалдаг ('a' нь "01100001" болох ASCII биш харин "10" эсвэл "1000" байж болно).). Хамгийн бага нийтлэг тэмдэгтүүд нь ихэвчлэн 8 битээс илүү хэмжээтэй байдаг ('z' нь "00100011010" байж магадгүй), гэхдээ тэдгээр нь маш ховор тохиолддог тул Хаффманы кодчилол нь эх хувьтай харьцуулахад хамаагүй жижиг файл үүсгэдэг.
Алхам
2 -р хэсгийн 1: Кодчилол
Алхам 1. Кодлох файлын тэмдэгт бүрийн давтамжийг тоол
Файлын төгсгөлийг тэмдэглэхийн тулд дамми тэмдэгт оруулаарай - энэ нь дараа нь чухал байх болно. Одоогоор үүнийг EOF (файлын төгсгөл) гэж нэрлээд 1 давтамжтай гэж тэмдэглээрэй.
Жишээлбэл, хэрэв та "ab ab cab" гэсэн текст файлыг кодлохыг хүсвэл 3 давтамжтай 'a', 3 давтамжтай 'b', 2 давтамжтай 'зай', 1 давтамжтай 'c' байх болно., 1 давтамжтай EOF
Алхам 2. Тэмдэгтүүдийг модны зангилаа хэлбэрээр хадгалж, тэргүүлэх дараалалд оруулна уу
Та тэмдэгт бүрийг навч шиг том хоёртын модыг бүтээх болно, тиймээс та тэмдэгтүүдийг модны зангилаа болох хэлбэрээр хадгалах ёстой. Эдгээр зангилааг тэмдэгтийн давтамжийг зангилааны тэргүүлэх чиглэл болгон тэргүүлэх дараалалд оруулна уу.
- Хоёртын мод бол өгөгдлийн хэсэг бүр нэг эцэг эх, хоёр хүүхэдтэй байж болох зангилаа хэлбэртэй өгөгдлийн формат юм. Энэ нь ихэвчлэн салаалсан мод хэлбэрээр зурагддаг тул нэр нь ийм байдаг.
- Дараалал гэдэг нь дарааллаар орох хамгийн эхний зүйл бол гарч ирэх хамгийн эхний зүйл (дараалал хүлээх гэх мэт) гэсэн зөв нэртэй өгөгдлийн цуглуулга юм. Нэн тэргүүнд тавигдах дараалалд өгөгдлийг дарааллаар нь хадгалдаг тул хамгийн түрүүнд гарч ирэх зүйл бол хамгийн чухал зүйл бөгөөд хамгийн түрүүнд хүлээлгэсэн зүйл биш харин хамгийн чухал ач холбогдолтой зүйл юм.
- "Ab ab cab" жишээнд таны тэргүүлэх дараалал дараах байдлаар харагдах болно: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Алхам 3. Модыг барьж эхлээрэй
Хамгийн чухал хоёр зүйлийг нэн тэргүүний дарааллаас хасах (эсвэл салгах). Эдгээр хоёр зангилааны эцэг эх байхын тулд шинэ модны зангилааг үүсгэж, эхний зангилааг зүүн хүүхэд, хоёр дахь хэсгийг нь баруун хүүхэд болгон хадгална уу. Шинэ зангилааны тэргүүлэх чиглэл нь хүүхдийнхээ тэргүүлэх чиглэлүүдийн нийлбэр байх ёстой. Дараа нь энэ шинэ зангилааг тэргүүлэх дараалалд оруулна уу.
Тэргүүлэх дараалал одоо иймэрхүү харагдаж байна: {'': 2, шинэ зангилаа: 2, 'a': 3, 'b': 3}
Алхам 4. Модыг барьж дуусгах:
дараалалд ганц зангилаа байх хүртэл дээрх алхамыг давтана. Тэмдэгтүүд болон тэдгээрийн давтамжид зориулж бүтээсэн зангилаанаас гадна та мод болж хувирч, эцэг эхийн зангилаа, аль хэдийн өөрсдөө мод болсон зангилааг дахин хөрвүүлэх болно гэдгийг анхаарна уу.
- Дууссаны дараа дарааллын хамгийн сүүлчийн зангилаа нь кодлох модны үндэс байх бөгөөд бусад бүх зангилаа үүнээс салаална.
- Хамгийн түгээмэл хэрэглэгддэг тэмдэгтүүд нь модны дээд хэсэгт хамгийн ойрхон навч байх болно, харин ховор хэрэглэгддэг тэмдэгтүүд нь модны ёроолд үндэснээсээ алслагдсан байх болно.
Алхам 5. Кодлох газрын зураг үүсгэх. Тэмдэгт бүрт хүрэхийн тулд модоор алхаарай. Зангилааны зүүн талын хүүхэдтэй уулзах болгонд энэ нь '0' болно. Та зангилааны зөв хүүхэдтэй уулзах болгонд энэ нь '1' болно. Тэмдэгт хүрэх үед тэмдэгтийг тэнд очиход шаардагдах 0 ба 1 -ийн дарааллаар хадгална уу. Энэ дараалал нь шахагдсан файл дээрх шиг тэмдэгтийг кодлох болно. Тэмдэгтүүд ба тэдгээрийн дарааллыг газрын зураг дээр хадгална уу.
- Жишээлбэл, эхнээс нь эхэл. Үндэсийн зүүн хүүхэд рүү очиж, дараа нь зангилааны зүүн хүүхэд рүү зочлоорой. Таны одоо байгаа зангилаа хүүхэдгүй байгаа тул та дүрд хүрсэн байна. Энэ бол ' '. Та энд хүрэхийн тулд зүүн тийш хоёр удаа алхсан тул '' гэсэн кодчилол нь "00" байна.
- Энэ модны хувьд газрын зураг дараах байдлаар харагдах болно: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Алхам 6. Гаралтын файлд кодлох газрын зургийг толгой болгон оруулна уу
Энэ нь файлыг тайлах боломжийг олгоно.
Алхам 7. Файлыг кодчилно уу
Кодлогдох файлын тэмдэгт бүрийн хувьд газрын зураг дээр хадгалсан хоёртын дарааллыг бичнэ үү. Файлыг кодчилж дууссаны дараа EOF -ийг эцэс хүртэл нэмэхээ мартуузай.
- "Ab ab cab" файлын хувьд кодлогдсон файл дараах байдлаар харагдах болно: "1011001011000101011011".
- Файлуудыг байт хэлбэрээр хадгалдаг (8 бит буюу 8 хоёртын оронтой тоо). Huffman Encoding алгоритм нь 8 битийн форматыг ашигладаггүй тул кодлогдсон файлууд ихэвчлэн 8-аас олон тооны урттай байдаггүй. Үлдсэн цифрүүдийг 0-ээр бөглөх болно. Энэ тохиолдолд файлын төгсгөлд хоёр 0 -ийг нэмж оруулах бөгөөд энэ нь өөр зай шиг харагдаж байна. Энэ нь асуудал байж болох юм: декодер уншихаа хэзээ зогсоохоо яаж мэдэх вэ? Гэсэн хэдий ч, бид файлын төгсгөлийн тэмдэгт оруулсан тул декодер үүнд хүрч, дараа нь нэмж оруулсан бусад зүйлийг үл тоомсорлох болно.
2 -р хэсгийн 2: Код тайлах
Алхам 1. Хаффман кодчилсон файлыг уншина уу
Нэгдүгээрт, кодчиллын зураг байх ёстой толгой хэсгийг уншина уу. Файлыг кодлоход ашиглаж байсан модыг бүтээсэн шиг код тайлах модыг бий болгохын тулд үүнийг ашиглана уу. Хоёр мод ижил байх ёстой.
Алхам 2. Нэг оронтой тоог нэг оронтой тоогоор уншина уу
Уншиж байхдаа модыг хөндлөн гулдлаарай: хэрэв та "0" -ээр уншсан бол байгаа зангилааны зүүн талын хүүхэд рүү, хэрэв "1" -ээр уншсан бол баруун талын хүүхэд рүү очно уу. Та навч руу (хүүхэдгүй зангилаа) хүрэхэд та нэг дүрд хүрсэн байна. Тэмдэгтийг тайлсан файлд бичээрэй.
Тэмдэгтүүдийг модонд хадгалах арга хэлбэрээс шалтгаалан тэмдэгт бүрийн код нь угтвар шинж чанартай байдаг тул өөр тэмдэгтийн кодчилол эхлэхэд ямар ч тэмдэгтийн хоёртын кодчилол хэзээ ч гарч болохгүй. Тэмдэгт бүрийн кодчилол нь өвөрмөц онцлогтой. Энэ нь код тайлах ажлыг ихээхэн хөнгөвчилдөг
Алхам 3. EOF -д хүрэх хүртэл давтана
Баяр хүргэе! Та файлын кодыг тайлсан байна.
