Package-merge algorithm
ಪ್ಯಾಕೇಜ್-ವಿಲೀನ ಅಲ್ಗಾರಿದಮ್ ಒಂದು O (nL)-ಸಮಯದ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದ್ದು, ನಿರ್ದಿಷ್ಟ ಗಾತ್ರದ n ವರ್ಣಮಾಲೆಯ ಮೇಲೆ ನೀಡಲಾದ ವಿತರಣೆಗೆ ಸೂಕ್ತವಾದ ಉದ್ದ-ಸೀಮಿತ ಹಫ್ಮನ್ ಕೋಡ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುತ್ತದೆ, ಅಲ್ಲಿ ಯಾವುದೇ ಕೋಡ್ ಪದವು L ಗಿಂತ ಉದ್ದವಾಗಿಲ್ಲ. ಪ್ಯಾಕೇಜ್-ವಿಲೀನವು ಕೋಡ್ ನಿರ್ಮಾಣದ ಸಮಸ್ಯೆಯನ್ನು ಬೈನರಿ ನಾಣ್ಯ ಸಂಗ್ರಾಹಕರ ಸಮಸ್ಯೆಗೆ ತಗ್ಗಿಸುವ ಮೂಲಕ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ನಾಣ್ಯ ಸಂಗ್ರಾಹಕನ ಸಮಸ್ಯೆ ನಾಣ್ಯ ಸಂಗ್ರಾಹಕನು ವಿವಿಧ ಪಂಗಡಗಳ ಹಲವಾರು ನಾಣ್ಯಗಳನ್ನು ಹೊಂದಿದ್ದಾನೆಂದು ಭಾವಿಸೋಣ, ಅವುಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದೂ ಅದರ ಪಂಗಡಕ್ಕೆ ಸಂಬಂಧವಿಲ್ಲದ ನಾಣ್ಯಶಾಸ್ತ್ರೀಯ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದೆ. ನಾಣ್ಯ ಸಂಗ್ರಾಹಕನಿಗೆ ಹಣ ಖಾಲಿಯಾಗಿದೆ ಮತ್ತು ಅವನು ತನ್ನ ನಾಣ್ಯ ಸಂಗ್ರಹದ ಕೆಲವು ಭಾಗವನ್ನು ಏನೊ ಬೆಲೆಯ ಏನೊ ಖರೀದಿಸಲು ಬಳಸಬೇಕಾಗುತ್ತದೆ. ಅವನು ತನ್ನ ಕನಿಷ್ಠ ನಾಣ್ಯ ಮೌಲ್ಯದ ಸಂಗ್ರಹದಿಂದ ಒಟ್ಟು ಏನೊ ಮೌಲ್ಯದ ನಾಣ್ಯಗಳ ಉಪಗುಂಪನ್ನು ಆಯ್ಕೆ ಮಾಡಲು ಬಯಸುತ್ತಾನೆ. ಈ ಸಮಸ್ಯೆಯ ಬೈನರಿ ಆವೃತ್ತಿಯು ಎಲ್ಲಾ ಪಂಗಡಗಳು 2ರ, ಅಂದರೆ 1,1/2,1/4, ಇತ್ಯಾದಿಗಳ ಘಾತಗಳಾಗಿವೆ. ಡಾಲರ್. ಪ್ಯಾಕೇಜ್-ವಿಲೀನ ಅಲ್ಗಾರಿದಮ್ನ ವಿವರಣೆಯು ಅತಿದೊಡ್ಡ ಮೌಲ್ಯವು 1 ಡಾಲರ್ ಮತ್ತು ಎನ್ ಒಂದು ಪೂರ್ಣಾಂಕವಾಗಿದೆ ಎಂದು ಭಾವಿಸಿ. (ಈ ಊಹೆಗಳು ಹೊಂದಿರದಿದ್ದರೂ, ಅಲ್ಗಾರಿದಮ್ ಕ್ಷುಲ್ಲಕ ಮಾರ್ಪಾಡುಗಳಿಂದ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ.) ನಾಣ್ಯ ಸಂಗ್ರಾಹಕನು ಮೊದಲು ತನ್ನ ನಾಣ್ಯಗಳನ್ನು ಪಟ್ಟಿಗಳಾಗಿ ವಿಂಗಡಿಸುತ್ತಾನೆ, ಪ್ರತಿ ಪಂಗಡಕ್ಕೆ ಒಂದು, ನಾಣ್ಯಗಳ ಮೌಲ್ಯದಿಂದ ವಿಂಗಡಿಸಲಾಗುತ್ತದೆ. ನಂತರ ಆತ ಸಣ್ಣ ಮೊತ್ತದ ನಾಣ್ಯಗಳನ್ನು ಜೋಡಿಯಾಗಿ ಪ್ಯಾಕೇಜ್ ಮಾಡುತ್ತಾನೆ, ಇದು ಅತಿ ಚಿಕ್ಕ ಒಟ್ಟು ನಾಣ್ಯ ಮೌಲ್ಯದ ಜೋಡಿಯೊಂದಿಗೆ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ. ಒಂದು ನಾಣ್ಯವು ಉಳಿದಿದ್ದರೆ, ಅದು ಆ ಮೌಲ್ಯದ ಅತಿ ಹೆಚ್ಚು ನಾಣ್ಯಶಾಸ್ತ್ರೀಯ ಮೌಲ್ಯದ ನಾಣ್ಯವಾಗಿರುತ್ತದೆ, ಮತ್ತು ಅದನ್ನು ಬದಿಗಿರಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಇನ್ನು ಮುಂದೆ ನಿರ್ಲಕ್ಷಿಸಲಾಗುತ್ತದೆ. ಈ ಪ್ಯಾಕೇಜುಗಳನ್ನು ನಂತರ ನಾಣ್ಯಗಳ ಮೌಲ್ಯದ ಕ್ರಮದಲ್ಲಿ ಮುಂದಿನ ಚಿಕ್ಕ ಮೌಲ್ಯದ ನಾಣ್ಯಗಳ ಪಟ್ಟಿಯಲ್ಲಿ ವಿಲೀನಗೊಳಿಸಲಾಗುತ್ತದೆ. ಆ ಪಟ್ಟಿಯಲ್ಲಿರುವ ವಸ್ತುಗಳನ್ನು ನಂತರ ಜೋಡಿಯಾಗಿ ಪ್ಯಾಕ್ ಮಾಡಲಾಗುತ್ತದೆ ಮತ್ತು ಮುಂದಿನ ಚಿಕ್ಕ ಪಟ್ಟಿಯಲ್ಲಿ ವಿಲೀನಗೊಳಿಸಲಾಗುತ್ತದೆ. ಅಂತಿಮವಾಗಿ, ವಸ್ತುಗಳ ಪಟ್ಟಿ ಇರುತ್ತದೆ, ಅವುಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದೂ 1 ಡಾಲರ್ ನಾಣ್ಯ ಅಥವಾ ಎರಡು ಅಥವಾ ಅದಕ್ಕಿಂತ ಹೆಚ್ಚು ಸಣ್ಣ ನಾಣ್ಯಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಪ್ಯಾಕೇಜ್, ಅದರ ಒಟ್ಟು ಮೌಲ್ಯಗಳು 1 ಡಾಲರ್ ಆಗಿರುತ್ತವೆ. ಅವುಗಳನ್ನು ನಾಣ್ಯಶಾಸ್ತ್ರೀಯ ಮೌಲ್ಯದ ಕ್ರಮದಲ್ಲಿ ವಿಂಗಡಿಸಲಾಗಿದೆ. ನಾಣ್ಯ ಸಂಗ್ರಾಹಕನು ನಂತರ ಅವುಗಳಲ್ಲಿ ಕನಿಷ್ಠ ಮೌಲ್ಯವಾದ ಎನ್ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತಾನೆ. ಅಲ್ಗಾರಿದಮ್ನ ಸಮಯವು ನಾಣ್ಯಗಳ ಸಂಖ್ಯೆಯಲ್ಲಿ ರೇಖೀಯವಾಗಿದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ನಾಣ್ಯ ಸಂಗ್ರಾಹಕ ಸಮಸ್ಯೆಗೆ ಉದ್ದ-ಸೀಮಿತ ಹಫ್ಮನ್ ಕೋಡಿಂಗ್ ಅನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು ಎಲ್ ಯಾವುದೇ ಕೋಡ್ ಪದವನ್ನು ಹೊಂದಲು ಅನುಮತಿಸಲಾದ ಗರಿಷ್ಠ ಉದ್ದವಾಗಿರಲಿ. p1,., pn ಎನ್ಕೋಡ್ ಮಾಡಬೇಕಾದ ವರ್ಣಮಾಲೆಯ ಚಿಹ್ನೆಗಳ ಆವರ್ತನಗಳಾಗಿರಲಿ. ನಾವು ಮೊದಲು ಚಿಹ್ನೆಗಳನ್ನು ಪೈ ≤ ಪೈ + 1 ಎಂದು ವಿಂಗಡಿಸುತ್ತೇವೆ. 2−1,., 2−ಎಲ್ ಪಂಗಡಗಳ ಪ್ರತಿ ಚಿಹ್ನೆಗೆ ಎಲ್ ನಾಣ್ಯಗಳನ್ನು ರಚಿಸಿ, ಪ್ರತಿಯೊಂದೂ ನಾಣ್ಯಗಳ ಮೌಲ್ಯ ಪೈ ಆಗಿರುತ್ತದೆ. ಕನಿಷ್ಠ ನಾಣ್ಯಶಾಸ್ತ್ರೀಯ ಮೌಲ್ಯದ ನಾಣ್ಯಗಳ ಗುಂಪನ್ನು ಆಯ್ಕೆ ಮಾಡಲು ಪ್ಯಾಕೇಜ್-ವಿಲೀನ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸಿ, ಅದರ ಪಂಗಡಗಳು ಒಟ್ಟು n−1 ಆಗಿರುತ್ತವೆ. ಆಯ್ಕೆ ಮಾಡಲಾದ ನಾಣ್ಯಶಾಸ್ತ್ರೀಯ ಮೌಲ್ಯದ ನಾಣ್ಯಗಳ ಸಂಖ್ಯೆ ಹಾಯ್ ಆಗಿರಲಿ. ಆಪ್ಟಿಮಲ್ ಉದ್ದ-ಸೀಮಿತ ಹಫ್ಮನ್ ಕೋಡ್ ಚಿಹ್ನೆ i ಅನ್ನು ಸ್ವಲ್ಪ ಉದ್ದದ ಸ್ಟ್ರಿಂಗ್ನೊಂದಿಗೆ ಎನ್ಕೋಡ್ ಮಾಡುತ್ತದೆ. ಕ್ಯಾನೊನಿಕಲ್ ಹಫ್ಮನ್ ಕೋಡ್ ಅನ್ನು ಸರಳವಾದ ಬಾಟಮ್-ಅಪ್ ದುರಾಸೆಯ ವಿಧಾನದಿಂದ ಸುಲಭವಾಗಿ ನಿರ್ಮಿಸಬಹುದು, ಏಕೆಂದರೆ ಹೈ ಅನ್ನು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಇದು ವೇಗದ ದತ್ತಾಂಶ ಸಂಕೋಚನಕ್ಕೆ ಆಧಾರವಾಗಿರಬಹುದು. ಕಾರ್ಯಕ್ಷಮತೆಯ ಸುಧಾರಣೆಗಳು ಮತ್ತು ಸಾಮಾನ್ಯೀಕರಣಗಳು ಈ ಕಡಿತದೊಂದಿಗೆ, ಅಲ್ಗಾರಿದಮ್ ಒ (ಎನ್ಎಲ್)-ಟೈಮ್ ಮತ್ತು ಒ (ಎನ್ಎಲ್)-ಸ್ಪೇಸ್ ಆಗಿದೆ. ಆದಾಗ್ಯೂ, "ಆಪ್ಟಿಮಲ್ ಲೆಂಗ್ತ್-ಲಿಮಿಟೆಡ್ ಹಫ್ಮನ್ ಕೋಡ್ಗಳಿಗಾಗಿ ಎ ಫಾಸ್ಟ್ ಅಲ್ಗಾರಿದಮ್" ಎಂಬ ಮೂಲ ಪ್ರಬಂಧವು ಇದನ್ನು ಒ (ಎನ್ಎಲ್)-ಟೈಮ್ ಮತ್ತು ಒ (ಎನ್)-ಸ್ಪೇಸ್ಗೆ ಹೇಗೆ ಸುಧಾರಿಸಬಹುದು ಎಂಬುದನ್ನು ತೋರಿಸುತ್ತದೆ. ಮೂಲ ಸಮಸ್ಯೆಯ ಅರ್ಧದಷ್ಟು ಗಾತ್ರದ ಎರಡು ಸಮಾನ ಉಪ-ಸಮಸ್ಯೆಗಳನ್ನು ನಿರ್ಧರಿಸಲು ಸಾಧ್ಯವಾಗುವಂತೆ ಸಾಕಷ್ಟು ಡೇಟಾವನ್ನು ಮಾತ್ರ ಇಟ್ಟುಕೊಂಡು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಮೊದಲ ಬಾರಿಗೆ ಚಲಾಯಿಸುವುದು ಇದರ ಉದ್ದೇಶವಾಗಿದೆ. ಇದನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಮಾಡಲಾಗುತ್ತದೆ, ಇದರ ಪರಿಣಾಮವಾಗಿ ಅಲ್ಗಾರಿದಮ್ ಸುಮಾರು ಎರಡು ಪಟ್ಟು ಹೆಚ್ಚು ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಆದರೆ ಕೇವಲ ರೇಖೀಯ ಸ್ಥಳಾವಕಾಶದ ಅಗತ್ಯವಿರುತ್ತದೆ. ಮಲ್ಟಿಪ್ಲಿಕೇಟಿವ್ ಸ್ಥಿರಾಂಕವನ್ನು ಕಡಿಮೆ ಮಾಡಲು ಮತ್ತು ವಿಶೇಷ ಸಂದರ್ಭಗಳಲ್ಲಿ ಅದನ್ನು ವೇಗವಾಗಿ ಮಾಡಲು ಪ್ಯಾಕೇಜ್-ವಿಲೀನ ಅಲ್ಗಾರಿದಮ್ಗೆ ಅನೇಕ ಇತರ ಸುಧಾರಣೆಗಳನ್ನು ಮಾಡಲಾಗಿದೆ, ಉದಾಹರಣೆಗೆ ಪುನರಾವರ್ತಿತ ಪಿಸ್ ಹೊಂದಿರುವ ಸಮಸ್ಯೆಗಳು. ಪ್ಯಾಕೇಜ್-ವಿಲೀನ ವಿಧಾನವನ್ನು ವರ್ಣಮಾಲೆಯ ಕೋಡಿಂಗ್ನಂತಹ ಸಂಬಂಧಿತ ಸಮಸ್ಯೆಗಳಿಗೆ ಅಳವಡಿಸಿಕೊಳ್ಳಲಾಗಿದೆ. ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತವನ್ನು ಒಳಗೊಂಡಿರುವ ವಿಧಾನಗಳು ಪ್ಯಾಕೇಜ್-ವಿಲೀನ ಕ್ರಮಾವಳಿಗಿಂತ ಉತ್ತಮ ಅಸಿಂಪ್ಟೋಟಿಕ್ ಸ್ಪೇಸ್ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿವೆ ಎಂದು ತೋರಿಸಲಾಗಿದೆ, ಆದರೆ ಇವುಗಳು ಹೆಚ್ಚು ಪ್ರಾಯೋಗಿಕ ಅನ್ವಯವನ್ನು ಕಂಡಿಲ್ಲ. ಉಲ್ಲೇಖಗಳು ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ಪ್ಯಾಕೇಜ್-ವಿಲೀನ ಅಲ್ಗಾರಿದಮ್ನ ಅನುಷ್ಠಾನ "" ಪ್ಯಾಕೇಜ್-ವಿಲೀನ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸುವ ವೇಗದ ಎಂಟ್ರೊಪಿ ಕೋಡರ್ ನಷ್ಟವಿಲ್ಲದ ಸಂಕೋಚನ ಅಲ್ಗಾರಿದಮ್ಗಳು ಕೋಡಿಂಗ್ ಸಿದ್ಧಾಂತ