Хаффман алгоритмі мәліметтерді қысу немесе кодтау үшін қолданылады. Әдетте, мәтіндік файлдағы әрбір таңба ASCII деп аталатын кодтауды қолдана отырып, осы таңбамен салыстырылатын сегіз бит (цифрлар, 0 немесе 1) түрінде сақталады. Хаффманмен кодталған файл қатаң 8 биттік құрылымды бұзады, сондықтан жиі қолданылатын таңбалар бірнеше биттерде сақталады ('a' ASCII емес, «10» немесе «1000» болуы мүмкін, ол «01100001»)). Ең жиі кездесетін таңбалар 8 биттен көп алады ('z' «00100011010» болуы мүмкін), бірақ олар өте сирек кездесетіндіктен, Хаффман кодтауы түпнұсқадан әлдеқайда кіші файл жасайды.
Қадамдар
2 бөлімнің 1 бөлігі: Кодтау
Қадам 1. Кодталатын файлдағы әр таңбаның жиілігін есептеңіз
Файлдың соңын белгілеу үшін жалған таңбаны қосыңыз - бұл кейінірек маңызды болады. Әзірге оны EOF деп атаңыз (файлдың соңы) және оны 1 жиілігімен белгілеңіз.
Мысалы, егер сіз «ab ab cab» мәтіндік файлын кодтағыңыз келсе, сізде 3 жиілігі бар «а», 3 жиілігіндегі «b», 2 жиілігіндегі «бос орын», 1 жиілігіндегі «с» болады., және EOF жиілігі 1
Қадам 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 жеткенше қайталаңыз
Құттықтаймын! Сіз файлды декодтадыңыз.
