Хаффман коддоосун колдонуу менен маалыматты кантип кысуу керек: 10 кадам

Мазмуну:

Хаффман коддоосун колдонуу менен маалыматты кантип кысуу керек: 10 кадам
Хаффман коддоосун колдонуу менен маалыматты кантип кысуу керек: 10 кадам

Video: Хаффман коддоосун колдонуу менен маалыматты кантип кысуу керек: 10 кадам

Video: Хаффман коддоосун колдонуу менен маалыматты кантип кысуу керек: 10 кадам
Video: Flipper Zero - игрушка для школьников и скрипт кидди 2024, Март
Anonim

Хаффмандын алгоритми маалыматтарды кысуу же коддоо үчүн колдонулат. Адатта, текст файлындагы ар бир символдун символу ASCII деп аталган сегиз бит (0 же 1) катары сакталат. Хаффман тарабынан коддолгон файл 8 биттик катаал структураны бузат, ошондуктан эң көп колдонулган белгилер бир нече биттерде сакталат ('a' "01100001" болгон ASCII эмес, "10" же "1000" болушу мүмкүн)). Эң аз таралган символдор көбүнчө 8 биттен ашат ('z' "00100011010" болушу мүмкүн), бирок алар өтө сейрек кездешкендиктен, Хаффман коддоосу, жалпысынан алганда, оригиналына караганда бир кыйла кичине файлды түзөт.

Кадамдар

2 ичинен 1 -бөлүк: Коддоо

Хаффман коддоо 1 -кадамын колдонуп маалыматтарды кысыңыз
Хаффман коддоо 1 -кадамын колдонуп маалыматтарды кысыңыз

Кадам 1. Коддолуучу файлдагы ар бир белгинин жыштыгын эсептеңиз

Файлдын аягына белгилөө үчүн жасалма белгини кошуңуз - бул кийинчерээк маанилүү болот. Азырынча аны EOF (файлдын аягы) деп атап, 1 жыштыгы бар деп белгилеңиз.

Мисалы, эгер сиз "ab ab cab" деген текст файлын коддоону кааласаңыз, анда 3 жыштыгы бар "a", 3 жыштыгы бар "b", 2 жыштыгы бар "боштук", 1 жыштыгы бар "c" болмок жана EOF 1 жыштыгы менен

Хаффман коддоо 2 -кадамын колдонуу менен маалыматтарды кысыңыз
Хаффман коддоо 2 -кадамын колдонуу менен маалыматтарды кысыңыз

Кадам 2. Дарак түйүндөрү катары белгилерди сактаңыз жана аларды артыкчылыктуу кезекке коюңуз

Сиз жалбырак катары ар бир тамгасы бар чоң бинардык даракты куруп жатасыз, андыктан каармандарды дарактын түйүнү боло турган форматта сактооңуз керек. Бул түйүндөрдү түйүнүнүн приоритети катары ар бир белгинин жыштыгы менен артыкчылыктуу кезекке коюңуз.

  • Экилик дарак - бул маалыматтын форматы, анда ар бир маалымат бир ата -энеге жана эки балага чейин боло турган түйүн болуп саналат. Ал көп учурда бутактуу дарак катары тартылган, ошондуктан аты.
  • Кезек - бул туура коюлган маалымат жыйнагы, анда кезекке биринчи кезекте чыгуучу нерсе да чыгат (кезекке туруу сыяктуу). Приоритеттүү кезекте маалыматтар биринчи кезекте эмес, эң шашылыш нерсе, эң кичине артыкчылыкка ээ болгон нерсе кезектүүлүгүнө жараша сакталат.
  • "Ab ab cab" мисалында, артыкчылыктуу кезегиңиз мындай болот: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Huffman Encoding 3 -кадамын колдонуу менен маалыматтарды кысыңыз
Huffman Encoding 3 -кадамын колдонуу менен маалыматтарды кысыңыз

3 -кадам. Дарагыңызды курууну баштаңыз

Приоритеттүү кезектен эң шашылыш эки нерсени алып салуу (же чыгаруу). Бул эки түйүндүн ата -энеси болуу үчүн жаңы дарак түйүнүн түзүңүз, биринчи түйүндү сол баласы, экинчиси оң баласы катары сактаңыз. Жаңы түйүндүн артыкчылыгы анын баласынын артыкчылыктарынын суммасы болушу керек. Андан кийин бул жаңы түйүндү артыкчылыктуу кезекке коюңуз.

Приоритеттүү кезек эми мындай көрүнөт: {'': 2, жаңы түйүн: 2, 'a': 3, 'b': 3}

Хаффман коддоо 4 -кадамын колдонуу менен маалыматтарды кысуу
Хаффман коддоо 4 -кадамын колдонуу менен маалыматтарды кысуу

Кадам 4. Дарагыңызды курууну бүтүрүңүз:

кезекте бир гана түйүн болмоюнча жогорудагы кадамды кайталаңыз. Белгилей кетчү нерсе, сиз белгилер жана алардын жыштыктары үчүн жараткан түйүндөрдөн тышкары, дарактарга айланып, ата-энелик түйүндөрдү, өзүлөрү дарактар болгон түйүндөрдү кайра өткөрүп бересиз.

  • Бүткөндөн кийин, кезектеги акыркы түйүн коддоо дарагынын тамыры болот, башка бардык түйүндөр андан бутактанат.
  • Эң көп колдонулган тамгалар дарактын чокусуна жакын жайгашкан жалбырактар болот, ал эми сейрек колдонулган тамгалар дарактын түбүндө, тамырдан алысыраакта жайгашат.
Маалыматты кысуу Huffman Encoding Step 5
Маалыматты кысуу Huffman Encoding Step 5

Кадам 5. Коддоо картасын түзүңүз. Ар бир каарманга жетүү үчүн даракты аралаңыз. Сиз түйүндүн сол баласына барган сайын, бул "0". Сиз түйүндүн туура баласына барган сайын, бул '1'. Каарманга жеткенде, ал жерге жетүү үчүн керектүү болгон 0 жана 1лердин ырааттуулугу менен белгини сактаңыз. Бул ырааттуулук каарман кысылган файлдагыдай коддолот. Каармандарды жана алардын ырааттуулугун картада сактаңыз.

  • Мисалы, тамырынан баштаңыз. Тамырдын сол баласына барыңыз, анан ошол түйүндүн сол баласына барыңыз. Учурда түйүндүн балдары жок болгондуктан, сиз бир каарманга жеттиңиз. Бул ' '. Бул жакка жетүү үчүн эки жолу солго басканыңыз үчүн, '' үчүн коддоо - "00".
  • Бул дарак үчүн карта мындай болот: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Маалыматты кысуу Huffman Encoding Step 6
Маалыматты кысуу Huffman Encoding Step 6

Кадам 6. Чыгуу файлында коддоо картасын баш катары киргизиңиз

Бул файлдын кодун чечүүгө мүмкүндүк берет.

Хаффман коддоо 7 -кадамын колдонуп маалыматтарды кысыңыз
Хаффман коддоо 7 -кадамын колдонуп маалыматтарды кысыңыз

Кадам 7. Файлды коддоо

Файлдын ар бир символу коддолушу үчүн, сиз картада сакталган бинардык ырааттуулукту жазыңыз. Файлды коддоону аяктагандан кийин, EOF аягына чейин кошууну тактаңыз.

  • "Ab ab cab" файлы үчүн коддолгон файл мындай болот: "1011001011000101011011".
  • Файлдар байт катары сакталат (8 бит же 8 бинардык цифралар). Huffman Encoding алгоритми 8 биттик форматты колдонбогондуктан, коддолгон файлдарда көбүнчө 8ге эселенген узундуктар болбойт. Калган цифралар 0лер менен толтурулат. Бул учурда, файлдын аягына эки 0 кошулат, бул башка боштукка окшош. Бул көйгөй болушу мүмкүн: декодер окууну качан токтотууну кайдан билмек эле? Бирок, биз файлдын аягына чыгуучу белгини киргизгендиктен, декодер буга жетет жана андан кийин кошулган башка нерсеге көңүл бурбай токтойт.

2 ичинен 2 -бөлүк: Декоддоо

Хаффман коддоо 8 -кадамын колдонуп маалыматтарды кысыңыз
Хаффман коддоо 8 -кадамын колдонуп маалыматтарды кысыңыз

Кадам 1. Хаффман коддолгон файлды окуңуз

Биринчиден, кодировкалоочу карта болушу керек болгон баш сөздү окуңуз. Муну файлды коддоо үчүн колдонулган даракты курганыңыздай эле, декоддоо дарагын куруу үчүн колдонуңуз. Эки дарак окшош болушу керек.

Хаффман коддоо 9 -кадамын колдонуп маалыматтарды кысыңыз
Хаффман коддоо 9 -кадамын колдонуп маалыматтарды кысыңыз

Кадам 2. Бир убакта экилик бир цифрадан окуңуз

Окуп жатканда даракты айланып өтүңүз: эгер сиз "0" менен окусаңыз, сиз турган түйүндүн сол баласына, ал эми "1" менен окусаңыз, оң балага өтүңүз. Жалбыракка жеткенде (балдары жок түйүн), сиз бир мүнөзгө жеттиңиз. Белгиңизди декоддолгон файлга жазыңыз.

Белгилер даракта сакталгандыктан, ар бир символдун коддору префикстин касиетине ээ, ошондуктан башка символдун коддоосунун башталышында эч кандай символдун экилик коддолушу эч качан болбойт. Ар бир тамга үчүн коддоо уникалдуу. Бул кодду чечүүнү бир топ жеңилдетет

Хаффман коддоо 10 -кадамын колдонуп маалыматтарды кысыңыз
Хаффман коддоо 10 -кадамын колдонуп маалыматтарды кысыңыз

Кадам 3. EOFке жеткенге чейин кайталаңыз

Куттуктайм! Сиз файлдын кодун чечтиңиз.

Сунушталууда: