ಕೋರ್ಸ್ ಪ್ರಾರಂಭವಾಗುವ ಮೊದಲು ನಿಮಗಾಗಿ ಮತ್ತೊಂದು ಉಪಯುಕ್ತ ವಸ್ತುವಿನ ಅನುವಾದವನ್ನು ಸಿದ್ಧಪಡಿಸಲಾಗಿದೆ.
ಹಫ್ಮನ್ ಕೋಡಿಂಗ್ ಎನ್ನುವುದು ಡೇಟಾ ಕಂಪ್ರೆಷನ್ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದ್ದು ಅದು ಫೈಲ್ ಕಂಪ್ರೆಷನ್‌ನ ಮೂಲ ಕಲ್ಪನೆಯನ್ನು ರೂಪಿಸುತ್ತದೆ. ಈ ಲೇಖನದಲ್ಲಿ, ನಾವು ಸ್ಥಿರ ಮತ್ತು ವೇರಿಯಬಲ್ ಉದ್ದದ ಎನ್ಕೋಡಿಂಗ್, ಅನನ್ಯವಾಗಿ ಡಿಕೋಡ್ ಮಾಡಬಹುದಾದ ಸಂಕೇತಗಳು, ಪೂರ್ವಪ್ರತ್ಯಯ ನಿಯಮಗಳು ಮತ್ತು ಹಫ್ಮನ್ ಮರವನ್ನು ನಿರ್ಮಿಸುವ ಬಗ್ಗೆ ಮಾತನಾಡುತ್ತೇವೆ.
ಪ್ರತಿಯೊಂದು ಅಕ್ಷರವನ್ನು 0 ಮತ್ತು 1 ರ ಅನುಕ್ರಮವಾಗಿ ಸಂಗ್ರಹಿಸಲಾಗಿದೆ ಮತ್ತು 8 ಬಿಟ್ಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಎಂದು ನಮಗೆ ತಿಳಿದಿದೆ. ಇದನ್ನು ಸ್ಥಿರ ಉದ್ದದ ಎನ್ಕೋಡಿಂಗ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಏಕೆಂದರೆ ಪ್ರತಿ ಅಕ್ಷರವು ಒಂದೇ ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ಬಿಟ್ಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ಬಳಸುತ್ತದೆ.
ನಮಗೆ ಪಠ್ಯವನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳೋಣ. ಒಂದೇ ಅಕ್ಷರವನ್ನು ಸಂಗ್ರಹಿಸಲು ಅಗತ್ಯವಿರುವ ಸ್ಥಳದ ಪ್ರಮಾಣವನ್ನು ನಾವು ಹೇಗೆ ಕಡಿಮೆ ಮಾಡಬಹುದು?
ಮುಖ್ಯ ಉಪಾಯವೆಂದರೆ ವೇರಿಯಬಲ್ ಉದ್ದದ ಎನ್ಕೋಡಿಂಗ್. ಪಠ್ಯದಲ್ಲಿನ ಕೆಲವು ಅಕ್ಷರಗಳು ಇತರರಿಗಿಂತ ಹೆಚ್ಚಾಗಿ ಸಂಭವಿಸುತ್ತವೆ ಎಂಬ ಅಂಶವನ್ನು ನಾವು ಬಳಸಬಹುದು () ಕಡಿಮೆ ಬಿಟ್‌ಗಳಲ್ಲಿ ಒಂದೇ ರೀತಿಯ ಅಕ್ಷರಗಳ ಅನುಕ್ರಮವನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸಲು. ವೇರಿಯಬಲ್ ಉದ್ದದ ಎನ್‌ಕೋಡಿಂಗ್‌ನಲ್ಲಿ, ನಿರ್ದಿಷ್ಟ ಪಠ್ಯದಲ್ಲಿ ಅವು ಎಷ್ಟು ಬಾರಿ ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತವೆ ಎಂಬುದರ ಆಧಾರದ ಮೇಲೆ ನಾವು ಅಕ್ಷರಗಳಿಗೆ ವೇರಿಯಬಲ್ ಸಂಖ್ಯೆಯ ಬಿಟ್ಗಳನ್ನು ನಿಯೋಜಿಸುತ್ತೇವೆ. ಅಂತಿಮವಾಗಿ, ಕೆಲವು ಅಕ್ಷರಗಳು 1 ಬಿಟ್‌ನಷ್ಟು ಕಡಿಮೆ ತೆಗೆದುಕೊಳ್ಳಬಹುದು, ಆದರೆ ಇತರರು 2 ಬಿಟ್‌ಗಳು, 3 ಅಥವಾ ಹೆಚ್ಚಿನದನ್ನು ತೆಗೆದುಕೊಳ್ಳಬಹುದು. ವೇರಿಯಬಲ್ ಉದ್ದದ ಎನ್ಕೋಡಿಂಗ್ನ ಸಮಸ್ಯೆಯು ಅನುಕ್ರಮದ ನಂತರದ ಡಿಕೋಡಿಂಗ್ ಮಾತ್ರ.
ಬಿಟ್‌ಗಳ ಅನುಕ್ರಮವನ್ನು ತಿಳಿದುಕೊಳ್ಳುವುದು, ಅದನ್ನು ನಿಸ್ಸಂದಿಗ್ಧವಾಗಿ ಡಿಕೋಡ್ ಮಾಡುವುದು ಹೇಗೆ?
ರೇಖೆಯನ್ನು ಪರಿಗಣಿಸಿ "ಅಬಾಕ್ಡಾಬ್". ಇದು 8 ಅಕ್ಷರಗಳನ್ನು ಹೊಂದಿದೆ ಮತ್ತು ಸ್ಥಿರ ಉದ್ದವನ್ನು ಎನ್ಕೋಡಿಂಗ್ ಮಾಡುವಾಗ, ಅದನ್ನು ಸಂಗ್ರಹಿಸಲು 64 ಬಿಟ್‌ಗಳು ಬೇಕಾಗುತ್ತವೆ. ಚಿಹ್ನೆ ಆವರ್ತನ ಎಂಬುದನ್ನು ಗಮನಿಸಿ "ಎ", "ಬಿ", "ಸಿ" и "ಡಿ" ಕ್ರಮವಾಗಿ 4, 2, 1, 1 ಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ. ಊಹಿಸಲು ಪ್ರಯತ್ನಿಸೋಣ "ಅಬಾಕ್ಡಾಬ್" ಎಂಬ ಅಂಶವನ್ನು ಬಳಸಿಕೊಂಡು ಕಡಿಮೆ ಬಿಟ್‌ಗಳು "ಗೆ" ಗಿಂತ ಹೆಚ್ಚಾಗಿ ಸಂಭವಿಸುತ್ತದೆ "ಬಿ"ಮತ್ತು "ಬಿ" ಗಿಂತ ಹೆಚ್ಚಾಗಿ ಸಂಭವಿಸುತ್ತದೆ "ಸಿ" и "ಡಿ". ಕೋಡಿಂಗ್ ಮೂಲಕ ಪ್ರಾರಂಭಿಸೋಣ "ಗೆ" ಒಂದು ಬಿಟ್ 0 ಗೆ ಸಮನಾಗಿರುತ್ತದೆ, "ಬಿ" ನಾವು ಎರಡು-ಬಿಟ್ ಕೋಡ್ 11 ಅನ್ನು ನಿಯೋಜಿಸುತ್ತೇವೆ ಮತ್ತು ಮೂರು ಬಿಟ್ಗಳನ್ನು 100 ಮತ್ತು 011 ಬಳಸಿ ನಾವು ಎನ್ಕೋಡ್ ಮಾಡುತ್ತೇವೆ "ಸಿ" и "ಡಿ".
ಪರಿಣಾಮವಾಗಿ, ನಾವು ಪಡೆಯುತ್ತೇವೆ:
a
0
b
11
c
100
d
011
ಆದ್ದರಿಂದ ಸಾಲು "ಅಬಾಕ್ಡಾಬ್" ನಾವು ಎನ್ಕೋಡ್ ಮಾಡುತ್ತೇವೆ 00110100011011 (0|0|11|0|100|011|0|11)ಮೇಲಿನ ಕೋಡ್‌ಗಳನ್ನು ಬಳಸಿ. ಆದಾಗ್ಯೂ, ಮುಖ್ಯ ಸಮಸ್ಯೆ ಡಿಕೋಡಿಂಗ್ನಲ್ಲಿ ಇರುತ್ತದೆ. ನಾವು ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಡಿಕೋಡ್ ಮಾಡಲು ಪ್ರಯತ್ನಿಸಿದಾಗ 00110100011011, ನಾವು ಅಸ್ಪಷ್ಟ ಫಲಿತಾಂಶವನ್ನು ಪಡೆಯುತ್ತೇವೆ, ಏಕೆಂದರೆ ಇದನ್ನು ಪ್ರತಿನಿಧಿಸಬಹುದು:
0|011|0|100|011|0|11 adacdab
0|0|11|0|100|0|11|011 aabacabd
0|011|0|100|0|11|0|11 adacabab
...
ಮತ್ತು ಹೀಗೆ.
ಈ ಅಸ್ಪಷ್ಟತೆಯನ್ನು ತಪ್ಪಿಸಲು, ನಮ್ಮ ಎನ್ಕೋಡಿಂಗ್ ಅಂತಹ ಪರಿಕಲ್ಪನೆಯನ್ನು ಪೂರೈಸುತ್ತದೆ ಎಂದು ನಾವು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಬೇಕು ಪೂರ್ವಪ್ರತ್ಯಯ ನಿಯಮ, ಇದು ಸಂಕೇತಗಳನ್ನು ಒಂದು ಅನನ್ಯ ರೀತಿಯಲ್ಲಿ ಮಾತ್ರ ಡಿಕೋಡ್ ಮಾಡಬಹುದೆಂದು ಸೂಚಿಸುತ್ತದೆ. ಪೂರ್ವಪ್ರತ್ಯಯ ನಿಯಮವು ಯಾವುದೇ ಕೋಡ್ ಇನ್ನೊಂದರ ಪೂರ್ವಪ್ರತ್ಯಯವಲ್ಲ ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ. ಕೋಡ್ ಮೂಲಕ, ನಾವು ನಿರ್ದಿಷ್ಟ ಅಕ್ಷರವನ್ನು ಪ್ರತಿನಿಧಿಸಲು ಬಳಸುವ ಬಿಟ್ಗಳನ್ನು ಅರ್ಥೈಸುತ್ತೇವೆ. ಮೇಲಿನ ಉದಾಹರಣೆಯಲ್ಲಿ 0 ಪೂರ್ವಪ್ರತ್ಯಯವಾಗಿದೆ 011, ಇದು ಪೂರ್ವಪ್ರತ್ಯಯ ನಿಯಮವನ್ನು ಉಲ್ಲಂಘಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ, ನಮ್ಮ ಕೋಡ್‌ಗಳು ಪೂರ್ವಪ್ರತ್ಯಯ ನಿಯಮವನ್ನು ಪೂರೈಸಿದರೆ, ನಾವು ಅನನ್ಯವಾಗಿ ಡಿಕೋಡ್ ಮಾಡಬಹುದು (ಮತ್ತು ಪ್ರತಿಯಾಗಿ).
ಮೇಲಿನ ಉದಾಹರಣೆಯನ್ನು ಮರುಪರಿಶೀಲಿಸೋಣ. ಈ ಸಮಯದಲ್ಲಿ ನಾವು ಚಿಹ್ನೆಗಳಿಗಾಗಿ ನಿಯೋಜಿಸುತ್ತೇವೆ "ಎ", "ಬಿ", "ಸಿ" и "ಡಿ" ಪೂರ್ವಪ್ರತ್ಯಯ ನಿಯಮವನ್ನು ಪೂರೈಸುವ ಸಂಕೇತಗಳು.
a
0
b
10
c
110
d
111
ಈ ಎನ್ಕೋಡಿಂಗ್ನೊಂದಿಗೆ, ಸ್ಟ್ರಿಂಗ್ "ಅಬಾಕ್ಡಾಬ್" ಎಂದು ಎನ್ಕೋಡ್ ಮಾಡಲಾಗುವುದು 00100100011010 (0|0|10|0|100|011|0|10). ಮತ್ತು ಇಲ್ಲಿ 00100100011010 ನಾವು ಈಗಾಗಲೇ ನಿಸ್ಸಂದಿಗ್ಧವಾಗಿ ಡಿಕೋಡ್ ಮಾಡಲು ಮತ್ತು ನಮ್ಮ ಮೂಲ ಸ್ಟ್ರಿಂಗ್‌ಗೆ ಹಿಂತಿರುಗಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ "ಅಬಾಕ್ಡಾಬ್".
ಹಫ್ಮನ್ ಕೋಡಿಂಗ್
ಈಗ ನಾವು ವೇರಿಯಬಲ್ ಉದ್ದದ ಎನ್ಕೋಡಿಂಗ್ ಮತ್ತು ಪೂರ್ವಪ್ರತ್ಯಯ ನಿಯಮದೊಂದಿಗೆ ವ್ಯವಹರಿಸಿದ್ದೇವೆ, ಹಫ್ಮನ್ ಎನ್ಕೋಡಿಂಗ್ ಕುರಿತು ಮಾತನಾಡೋಣ.
ವಿಧಾನವು ಬೈನರಿ ಮರಗಳ ಸೃಷ್ಟಿಯನ್ನು ಆಧರಿಸಿದೆ. ಅದರಲ್ಲಿ, ನೋಡ್ ಅಂತಿಮ ಅಥವಾ ಆಂತರಿಕವಾಗಿರಬಹುದು. ಆರಂಭದಲ್ಲಿ, ಎಲ್ಲಾ ನೋಡ್ಗಳನ್ನು ಎಲೆಗಳು (ಟರ್ಮಿನಲ್‌ಗಳು) ಎಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ, ಇದು ಚಿಹ್ನೆಯನ್ನು ಮತ್ತು ಅದರ ತೂಕವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ (ಅಂದರೆ, ಸಂಭವಿಸುವ ಆವರ್ತನ). ಆಂತರಿಕ ನೋಡ್ಗಳು ಪಾತ್ರದ ತೂಕವನ್ನು ಹೊಂದಿರುತ್ತವೆ ಮತ್ತು ಎರಡು ಸಂತತಿ ನೋಡ್ಗಳನ್ನು ಉಲ್ಲೇಖಿಸುತ್ತವೆ. ಸಾಮಾನ್ಯ ಒಪ್ಪಂದದ ಮೂಲಕ, ಬಿಟ್ "0" ಎಡ ಶಾಖೆಯನ್ನು ಅನುಸರಿಸುವುದನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ, ಮತ್ತು "1" - ಬಲ ಬದಿಯಲ್ಲಿ. ಪೂರ್ಣ ಮರದಲ್ಲಿ N ಎಲೆಗಳು ಮತ್ತು ಎನ್-ಎಕ್ಸ್ಯುಎನ್ಎಕ್ಸ್ ಆಂತರಿಕ ನೋಡ್ಗಳು. ಹಫ್ಮನ್ ಮರವನ್ನು ನಿರ್ಮಿಸುವಾಗ, ಸೂಕ್ತ ಉದ್ದದ ಸಂಕೇತಗಳನ್ನು ಪಡೆಯಲು ಬಳಸದ ಚಿಹ್ನೆಗಳನ್ನು ತ್ಯಜಿಸಲು ಶಿಫಾರಸು ಮಾಡಲಾಗಿದೆ.
ಹಫ್ಮನ್ ಮರವನ್ನು ನಿರ್ಮಿಸಲು ನಾವು ಆದ್ಯತೆಯ ಸರತಿಯನ್ನು ಬಳಸುತ್ತೇವೆ, ಅಲ್ಲಿ ಕಡಿಮೆ ಆವರ್ತನದೊಂದಿಗೆ ನೋಡ್‌ಗೆ ಹೆಚ್ಚಿನ ಆದ್ಯತೆಯನ್ನು ನೀಡಲಾಗುತ್ತದೆ. ನಿರ್ಮಾಣ ಹಂತಗಳನ್ನು ಕೆಳಗೆ ವಿವರಿಸಲಾಗಿದೆ:
- ಪ್ರತಿ ಅಕ್ಷರಕ್ಕೆ ಲೀಫ್ ನೋಡ್ ಅನ್ನು ರಚಿಸಿ ಮತ್ತು ಅವುಗಳನ್ನು ಆದ್ಯತೆಯ ಸರತಿಗೆ ಸೇರಿಸಿ.
- ಸರದಿಯಲ್ಲಿ ಒಂದಕ್ಕಿಂತ ಹೆಚ್ಚು ಹಾಳೆಗಳಿರುವಾಗ, ಈ ಕೆಳಗಿನವುಗಳನ್ನು ಮಾಡಿ:
- ಕ್ಯೂನಿಂದ ಹೆಚ್ಚಿನ ಆದ್ಯತೆಯೊಂದಿಗೆ (ಕಡಿಮೆ ಆವರ್ತನ) ಎರಡು ನೋಡ್ಗಳನ್ನು ತೆಗೆದುಹಾಕಿ;
- ಹೊಸ ಆಂತರಿಕ ನೋಡ್ ಅನ್ನು ರಚಿಸಿ, ಅಲ್ಲಿ ಈ ಎರಡು ನೋಡ್ಗಳು ಮಕ್ಕಳಾಗಿರುತ್ತವೆ ಮತ್ತು ಸಂಭವಿಸುವ ಆವರ್ತನವು ಈ ಎರಡು ನೋಡ್‌ಗಳ ಆವರ್ತನಗಳ ಮೊತ್ತಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ.
- ಆದ್ಯತೆಯ ಸರತಿಗೆ ಹೊಸ ನೋಡ್ ಅನ್ನು ಸೇರಿಸಿ.
- ಉಳಿದಿರುವ ಏಕೈಕ ನೋಡ್ ರೂಟ್ ಆಗಿರುತ್ತದೆ ಮತ್ತು ಇದು ಮರದ ನಿರ್ಮಾಣವನ್ನು ಪೂರ್ಣಗೊಳಿಸುತ್ತದೆ.
ಕೇವಲ ಅಕ್ಷರಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಕೆಲವು ಪಠ್ಯವನ್ನು ನಾವು ಹೊಂದಿದ್ದೇವೆ ಎಂದು ಕಲ್ಪಿಸಿಕೊಳ್ಳಿ "ಎ ಬಿ ಸಿ ಡಿ" и "ಮತ್ತು", ಮತ್ತು ಅವುಗಳ ಸಂಭವಿಸುವಿಕೆಯ ಆವರ್ತನಗಳು ಕ್ರಮವಾಗಿ 15, 7, 6, 6, ಮತ್ತು 5. ಅಲ್ಗಾರಿದಮ್‌ನ ಹಂತಗಳನ್ನು ಪ್ರತಿಬಿಂಬಿಸುವ ಚಿತ್ರಣಗಳನ್ನು ಕೆಳಗೆ ನೀಡಲಾಗಿದೆ.
ರೂಟ್‌ನಿಂದ ಯಾವುದೇ ಎಂಡ್ ನೋಡ್‌ಗೆ ಪಥವು ಆ ಎಂಡ್ ನೋಡ್‌ಗೆ ಸಂಬಂಧಿಸಿದ ಅಕ್ಷರಕ್ಕೆ ಅನುಗುಣವಾಗಿ ಸೂಕ್ತ ಪೂರ್ವಪ್ರತ್ಯಯ ಕೋಡ್ ಅನ್ನು (ಹಫ್ಮನ್ ಕೋಡ್ ಎಂದೂ ಕರೆಯುತ್ತಾರೆ) ಸಂಗ್ರಹಿಸುತ್ತದೆ.
ಹಫ್ಮನ್ ಮರ
ಸಿ++ ಮತ್ತು ಜಾವಾದಲ್ಲಿ ಹಫ್ಮನ್ ಕಂಪ್ರೆಷನ್ ಅಲ್ಗಾರಿದಮ್‌ನ ಅನುಷ್ಠಾನವನ್ನು ನೀವು ಕೆಳಗೆ ಕಾಣಬಹುದು:
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;
// A Tree node
struct Node
{
char ch;
int freq;
Node *left, *right;
};
// Function to allocate a new tree node
Node* getNode(char ch, int freq, Node* left, Node* right)
{
Node* node = new Node();
node->ch = ch;
node->freq = freq;
node->left = left;
node->right = right;
return node;
}
// Comparison object to be used to order the heap
struct comp
{
bool operator()(Node* l, Node* r)
{
// highest priority item has lowest frequency
return l->freq > r->freq;
}
};
// traverse the Huffman Tree and store Huffman Codes
// in a map.
void encode(Node* root, string str,
unordered_map<char, string> &huffmanCode)
{
if (root == nullptr)
return;
// found a leaf node
if (!root->left && !root->right) {
huffmanCode[root->ch] = str;
}
encode(root->left, str + "0", huffmanCode);
encode(root->right, str + "1", huffmanCode);
}
// traverse the Huffman Tree and decode the encoded string
void decode(Node* root, int &index, string str)
{
if (root == nullptr) {
return;
}
// found a leaf node
if (!root->left && !root->right)
{
cout << root->ch;
return;
}
index++;
if (str[index] =='0')
decode(root->left, index, str);
else
decode(root->right, index, str);
}
// Builds Huffman Tree and decode given input text
void buildHuffmanTree(string text)
{
// count frequency of appearance of each character
// and store it in a map
unordered_map<char, int> freq;
for (char ch: text) {
freq[ch]++;
}
// Create a priority queue to store live nodes of
// Huffman tree;
priority_queue<Node*, vector<Node*>, comp> pq;
// Create a leaf node for each character and add it
// to the priority queue.
for (auto pair: freq) {
pq.push(getNode(pair.first, pair.second, nullptr, nullptr));
}
// do till there is more than one node in the queue
while (pq.size() != 1)
{
// Remove the two nodes of highest priority
// (lowest frequency) from the queue
Node *left = pq.top(); pq.pop();
Node *right = pq.top(); pq.pop();
// Create a new internal node with these two nodes
// as children and with frequency equal to the sum
// of the two nodes' frequencies. Add the new node
// to the priority queue.
int sum = left->freq + right->freq;
pq.push(getNode('', sum, left, right));
}
// root stores pointer to root of Huffman Tree
Node* root = pq.top();
// traverse the Huffman Tree and store Huffman Codes
// in a map. Also prints them
unordered_map<char, string> huffmanCode;
encode(root, "", huffmanCode);
cout << "Huffman Codes are :n" << 'n';
for (auto pair: huffmanCode) {
cout << pair.first << " " << pair.second << 'n';
}
cout << "nOriginal string was :n" << text << 'n';
// print encoded string
string str = "";
for (char ch: text) {
str += huffmanCode[ch];
}
cout << "nEncoded string is :n" << str << 'n';
// traverse the Huffman Tree again and this time
// decode the encoded string
int index = -1;
cout << "nDecoded string is: n";
while (index < (int)str.size() - 2) {
decode(root, index, str);
}
}
// Huffman coding algorithm
int main()
{
string text = "Huffman coding is a data compression algorithm.";
buildHuffmanTree(text);
return 0;
}import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
// A Tree node
class Node
{
char ch;
int freq;
Node left = null, right = null;
Node(char ch, int freq)
{
this.ch = ch;
this.freq = freq;
}
public Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
};
class Huffman
{
// traverse the Huffman Tree and store Huffman Codes
// in a map.
public static void encode(Node root, String str,
Map<Character, String> huffmanCode)
{
if (root == null)
return;
// found a leaf node
if (root.left == null && root.right == null) {
huffmanCode.put(root.ch, str);
}
encode(root.left, str + "0", huffmanCode);
encode(root.right, str + "1", huffmanCode);
}
// traverse the Huffman Tree and decode the encoded string
public static int decode(Node root, int index, StringBuilder sb)
{
if (root == null)
return index;
// found a leaf node
if (root.left == null && root.right == null)
{
System.out.print(root.ch);
return index;
}
index++;
if (sb.charAt(index) == '0')
index = decode(root.left, index, sb);
else
index = decode(root.right, index, sb);
return index;
}
// Builds Huffman Tree and huffmanCode and decode given input text
public static void buildHuffmanTree(String text)
{
// count frequency of appearance of each character
// and store it in a map
Map<Character, Integer> freq = new HashMap<>();
for (int i = 0 ; i < text.length(); i++) {
if (!freq.containsKey(text.charAt(i))) {
freq.put(text.charAt(i), 0);
}
freq.put(text.charAt(i), freq.get(text.charAt(i)) + 1);
}
// Create a priority queue to store live nodes of Huffman tree
// Notice that highest priority item has lowest frequency
PriorityQueue<Node> pq = new PriorityQueue<>(
(l, r) -> l.freq - r.freq);
// Create a leaf node for each character and add it
// to the priority queue.
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
pq.add(new Node(entry.getKey(), entry.getValue()));
}
// do till there is more than one node in the queue
while (pq.size() != 1)
{
// Remove the two nodes of highest priority
// (lowest frequency) from the queue
Node left = pq.poll();
Node right = pq.poll();
// Create a new internal node with these two nodes as children
// and with frequency equal to the sum of the two nodes
// frequencies. Add the new node to the priority queue.
int sum = left.freq + right.freq;
pq.add(new Node('', sum, left, right));
}
// root stores pointer to root of Huffman Tree
Node root = pq.peek();
// traverse the Huffman tree and store the Huffman codes in a map
Map<Character, String> huffmanCode = new HashMap<>();
encode(root, "", huffmanCode);
// print the Huffman codes
System.out.println("Huffman Codes are :n");
for (Map.Entry<Character, String> entry : huffmanCode.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("nOriginal string was :n" + text);
// print encoded string
StringBuilder sb = new StringBuilder();
for (int i = 0 ; i < text.length(); i++) {
sb.append(huffmanCode.get(text.charAt(i)));
}
System.out.println("nEncoded string is :n" + sb);
// traverse the Huffman Tree again and this time
// decode the encoded string
int index = -1;
System.out.println("nDecoded string is: n");
while (index < sb.length() - 2) {
index = decode(root, index, sb);
}
}
public static void main(String[] args)
{
String text = "Huffman coding is a data compression algorithm.";
buildHuffmanTree(text);
}
}ಗಮನಿಸಿ: ಇನ್‌ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ ಬಳಸುವ ಮೆಮೊರಿಯು 47 * 8 = 376 ಬಿಟ್‌ಗಳು ಮತ್ತು ಎನ್ಕೋಡ್ ಮಾಡಿದ ಸ್ಟ್ರಿಂಗ್ ಕೇವಲ 194 ಬಿಟ್‌ಗಳು ಅಂದರೆ. ಡೇಟಾವನ್ನು ಸುಮಾರು 48% ರಷ್ಟು ಸಂಕುಚಿತಗೊಳಿಸಲಾಗಿದೆ. ಮೇಲಿನ C++ ಪ್ರೋಗ್ರಾಂನಲ್ಲಿ, ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ಓದುವಂತೆ ಮಾಡಲು ಎನ್ಕೋಡ್ ಮಾಡಿದ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಸಂಗ್ರಹಿಸಲು ನಾವು ಸ್ಟ್ರಿಂಗ್ ವರ್ಗವನ್ನು ಬಳಸುತ್ತೇವೆ.
ಏಕೆಂದರೆ ಸಮರ್ಥ ಆದ್ಯತೆಯ ಸರತಿ ಡೇಟಾ ರಚನೆಗಳು ಪ್ರತಿ ಅಳವಡಿಕೆಯ ಅಗತ್ಯವಿರುತ್ತದೆ ಓ(ಲಾಗ್(ಎನ್)) ಸಮಯ, ಆದರೆ ಸಂಪೂರ್ಣ ಬೈನರಿ ಮರದಲ್ಲಿ N ಪ್ರಸ್ತುತ ಎಲೆಗಳು 2N-1 ನೋಡ್ಗಳು, ಮತ್ತು ಹಫ್ಮನ್ ಮರವು ಸಂಪೂರ್ಣ ಬೈನರಿ ಮರವಾಗಿದೆ, ನಂತರ ಅಲ್ಗಾರಿದಮ್ ರನ್ ಆಗುತ್ತದೆ O(Nlog(N)) ಸಮಯ, ಎಲ್ಲಿ N - ಪಾತ್ರಗಳು.
ಮೂಲಗಳು:
ಮೂಲ: www.habr.com