Misra–Gries heavy hitters algorithm
ಮಿಶ್ರಾ ಮತ್ತು ಗ್ರೀಸ್ ಅವರು ಹೆವಿ-ಹಿಟ್ಟರ್ಸ್ ಸಮಸ್ಯೆಯನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಿದರು (ಆದರೂ ಅವರು ಹೆವಿ-ಹಿಟ್ಟರ್ಸ್ ಎಂಬ ಪದವನ್ನು ಪರಿಚಯಿಸಲಿಲ್ಲ) ಮತ್ತು ಅದರ ಮೊದಲ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಫೈಂಡಿಂಗ್ ರಿಪೀಟೆಡ್ ಎಲಿಮೆಂಟ್ಸ್ ಎಂಬ ಕಾಗದದಲ್ಲಿ ವಿವರಿಸಿದ್ದಾರೆ. ಅವರ ಅಲ್ಗಾರಿದಮ್ ಬೋಯರ್-ಮೂರ್ ಮೆಜಾರಿಟಿ ಫೈಂಡಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಗಮನಾರ್ಹ ರೀತಿಯಲ್ಲಿ ವಿಸ್ತರಿಸುತ್ತದೆ. ಹೆವಿ-ಹಿಟ್ಟರ್ ಸಮಸ್ಯೆಯ ಒಂದು ಆವೃತ್ತಿಯು ಈ ಕೆಳಗಿನಂತಿದೆಃ ಅಂಶಗಳ ಚೀಲ ಮತ್ತು ಪೂರ್ಣಾಂಕವನ್ನು ನೀಡಲಾಗಿದೆ. ಒಂದಕ್ಕಿಂತ ಹೆಚ್ಚು ಬಾರಿ ಸಂಭವಿಸುವ ಮೌಲ್ಯಗಳನ್ನು ಹುಡುಕಿ. ಮಿಶ್ರಾ-ಗ್ರೀಸ್ ಅಲ್ಗಾರಿದಮ್ ಮೌಲ್ಯಗಳ ಮೇಲೆ ಎರಡು ಪಾಸ್ಗಳನ್ನು ಮಾಡುವ ಮೂಲಕ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುತ್ತದೆ, ಅಲ್ಗಾರಿದಮ್ನ ಅವಧಿಯಲ್ಲಿ ಹೆಚ್ಚಿನ ಮೌಲ್ಯಗಳಲ್ಲಿ ಮತ್ತು ಅವುಗಳ ಘಟನೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ. ಮಿಶ್ರಾ-ಗ್ರೀಸ್ ಆರಂಭಿಕ ಸ್ಟ್ರೀಮಿಂಗ್ ಕ್ರಮಾವಳಿಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ, ಮತ್ತು ಇದನ್ನು #Summaries ವಿಭಾಗದಲ್ಲಿ ಆ ಪದಗಳಲ್ಲಿ ಕೆಳಗೆ ವಿವರಿಸಲಾಗಿದೆ. ಮಿಶ್ರಾ-ಗ್ರೀಸ್ ಅಲ್ಗಾರಿದಮ್ ಒಂದು ಚೀಲವು ಒಂದೇ ಮೌಲ್ಯವು ಅನೇಕ ಬಾರಿ ಸಂಭವಿಸಬಹುದಾದ ಒಂದು ಗುಂಪಿನಂತಿದೆ. ಒಂದು ಚೀಲವು ಅಂಶಗಳ ಒಂದು ಶ್ರೇಣಿಯಾಗಿ ಲಭ್ಯವಿದೆ ಎಂದು ಭಾವಿಸಿ. ಅಲ್ಗಾರಿದಮ್ನ ಅಮೂರ್ತ ವಿವರಣೆಯಲ್ಲಿ, ನಾವು ಅದರ ಭಾಗಗಳನ್ನು ಚೀಲಗಳೆಂದು ಪರಿಗಣಿಸುತ್ತೇವೆ. ಇನ್ನು ಮುಂದೆ, ಚೀಲದ ಭಾರೀ ಹಿಟ್ಟರ್ ಎಂಬುದು ಕೆಲವು ಪೂರ್ಣಾಂಕಗಳಿಗೆ, ಅದರಲ್ಲಿ ಹೆಚ್ಚು ಬಾರಿ ಸಂಭವಿಸುವ ಮೌಲ್ಯವಾಗಿದೆ. ಚೀಲಕ್ಕೆ ಎ-ಕಡಿಮೆ ಚೀಲವನ್ನು ಈ ಕೆಳಗಿನ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಇನ್ನು ಮುಂದೆ ಸಾಧ್ಯವಾಗದವರೆಗೂ ಪುನರಾವರ್ತಿಸುವ ಮೂಲಕ ಪಡೆಯಲಾಗುತ್ತದೆಃ ಚೀಲದಿಂದ ವಿಭಿನ್ನ ಅಂಶಗಳನ್ನು ಅಳಿಸಿ. ಅದರ ವ್ಯಾಖ್ಯಾನದಿಂದ,-ಕಡಿಮೆ ಚೀಲವು ವಿಭಿನ್ನ ಮೌಲ್ಯಗಳಿಗಿಂತ ಕಡಿಮೆ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಈ ಕೆಳಗಿನ ಪ್ರಮೇಯವನ್ನು ಸಾಬೀತುಪಡಿಸುವುದು ಸುಲಭಃ ಪ್ರಮೇಯ 1. ಪ್ರತಿ ಭಾರೀ-ಹಿಟ್ಟರ್ ಒಂದು-ಕಡಿಮೆ ಚೀಲದ ಒಂದು ಅಂಶವಾಗಿದೆ. ಹೆವಿ-ಹಿಟ್ಟರ್ಗಳ ಗಣನೆಯ ಮೊದಲ ಪಾಸ್ ಕಡಿಮೆ ಚೀಲವನ್ನು ನಿರ್ಮಿಸುತ್ತದೆ. ಎರಡನೇ ಪಾಸ್ ಒಂದು ಅಂಶವು ಒಂದಕ್ಕಿಂತ ಹೆಚ್ಚು ಬಾರಿ ಸಂಭವಿಸಿದರೆ ಅದನ್ನು ಭಾರೀ-ಹಿಟ್ಟರ್ ಎಂದು ಘೋಷಿಸುತ್ತದೆ. ಪ್ರಮೇಯ 1ರ ಪ್ರಕಾರ, ಈ ವಿಧಾನವು ಎಲ್ಲಾ ಮತ್ತು ಕೇವಲ ಭಾರೀ-ಹಿಟ್ಟರ್ಗಳನ್ನು ಮಾತ್ರ ನಿರ್ಧರಿಸುತ್ತದೆ. ಎರಡನೇ ಪಾಸ್ ಅನ್ನು ಪ್ರೋಗ್ರಾಂ ಮಾಡುವುದು ಸುಲಭ, ಆದ್ದರಿಂದ ನಾವು ಮೊದಲ ಪಾಸ್ ಅನ್ನು ಮಾತ್ರ ವಿವರಿಸುತ್ತೇವೆ. ನಿರ್ಮಿಸಲು, ಮೌಲ್ಯಗಳನ್ನು ಅನಿಯಂತ್ರಿತ ಕ್ರಮದಲ್ಲಿ ಸ್ಕ್ಯಾನ್ ಮಾಡಿ, ನಿರ್ದಿಷ್ಟತೆಗಾಗಿ ಈ ಕೆಳಗಿನ ಅಲ್ಗಾರಿದಮ್ ಅವುಗಳನ್ನು ಸೂಚ್ಯಂಕಗಳನ್ನು ಹೆಚ್ಚಿಸುವ ಕ್ರಮದಲ್ಲಿ ಸ್ಕ್ಯಾನ್ ಮಾಡುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ನ ಇನ್ವೇರಿಯಂಟ್ ಎಂದರೆ ಸ್ಕ್ಯಾನ್ ಮಾಡಿದ ಮೌಲ್ಯಗಳಿಗೆ-ಕಡಿಮೆ ಚೀಲವಾಗಿದೆ ಮತ್ತು ಇದು ವಿಭಿನ್ನ ಮೌಲ್ಯಗಳ ಸಂಖ್ಯೆಯಾಗಿದೆ. ಆರಂಭದಲ್ಲಿ, ಯಾವುದೇ ಮೌಲ್ಯವನ್ನು ಸ್ಕ್ಯಾನ್ ಮಾಡಲಾಗಿಲ್ಲ, ಅದು ಖಾಲಿ ಚೀಲವಾಗಿದೆ ಮತ್ತು ಶೂನ್ಯವಾಗಿದೆ. ಅಂಶವನ್ನು ಸ್ಕ್ಯಾನ್ ಮಾಡಿದಾಗಲೆಲ್ಲಾ, ಅಸ್ಥಿರತೆಯನ್ನು ಸಂರಕ್ಷಿಸುವ ಸಲುವಾಗಿಃ (1) ಇಲ್ಲದಿದ್ದರೆ, ಅದನ್ನು 1ಕ್ಕೆ ಸೇರಿಸಿ ಮತ್ತು ಹೆಚ್ಚಿಸಿ, (2) ಇದ್ದರೆ, ಅದನ್ನು ಸೇರಿಸಿ ಆದರೆ ಮಾರ್ಪಡಿಸಬೇಡಿ, ಮತ್ತು (3) ಸಮಾನವಾದರೆ, ಅದರಿಂದ ವಿಭಿನ್ನ ಮೌಲ್ಯಗಳನ್ನು ಅಳಿಸುವ ಮೂಲಕ ಕಡಿಮೆ ಮಾಡಿ ಮತ್ತು ಸೂಕ್ತವಾಗಿ ನವೀಕರಿಸಿ. ಅಲ್ಗಾರಿದಮ್ ಮಿಶ್ರಾ-ಗ್ರೀಸ್ 1 = t, d: = {}, 0 ಆಗಿದೆ; i ಗೆ 0 ರಿಂದ n-1 ರವರೆಗೆ b [i] t ಆಗಿದ್ದರೆ ಮಾಡಿ, ನಂತರ t, d: = t ≤ {b [i]}, d + 1 ಇಲ್ಲದಿದ್ದರೆ t, d: = t ≤ {b [i]} ಅಂತ್ಯವು d = k ಆಗಿದ್ದರೆ ನಂತರ ನವೀಕರಣದ ಅಂತ್ಯದಿಂದ ವಿಭಿನ್ನ ಮೌಲ್ಯಗಳನ್ನು ಅಳಿಸಿ. ನಂತರ ಈ ಗುಂಪಿನ ಗಾತ್ರ. "ಡಿಲೀಟ್ ಡಿಸ್ಟಿಂಕ್ಟ್ ವ್ಯಾಲ್ಯೂಸ್ ಫ್ರಮ್" ಹಂತವು ಪ್ರತಿಯೊಂದನ್ನು 1 ರಿಂದ ಕಡಿಮೆ ಮಾಡುತ್ತದೆ ಮತ್ತು ನಂತರ 0 ಆಗಿದ್ದರೆ ಸೆಟ್ನಿಂದ ಯಾವುದೇ ಜೋಡಿ (,) ಅನ್ನು ತೆಗೆದುಹಾಕುತ್ತದೆ. ಎವಿಎಲ್ ಟ್ರೀ ಅನುಷ್ಠಾನವನ್ನು ಬಳಸಿಕೊಂಡು, ಅಲ್ಗಾರಿದಮ್ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯವನ್ನು ಹೊಂದಿದೆ. ಜಾಗದ ಅಗತ್ಯವನ್ನು ನಿರ್ಣಯಿಸಲು, ಅದರ ಅಂಶಗಳು ಸಂಭವನೀಯ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿರಬಹುದು ಎಂದು ಭಾವಿಸಿ, ಆದ್ದರಿಂದ ಮೌಲ್ಯದ ಶೇಖರಣೆಗೆ ಬಿಟ್ಗಳು ಬೇಕಾಗುತ್ತವೆ. ಪ್ರತಿ ಕೌಂಟರ್ ಗರಿಷ್ಠ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುವುದರಿಂದ, ಅದರ ಶೇಖರಣೆಗೆ ಬಿಟ್ಗಳು ಬೇಕಾಗುತ್ತವೆ. ಆದ್ದರಿಂದ, ಮೌಲ್ಯ-ಕೌಂಟರ್ ಜೋಡಿಗಳಿಗೆ, ಸ್ಥಳಾವಕಾಶದ ಅಗತ್ಯವಿರುತ್ತದೆ. ಸಾರಾಂಶಗಳು ಸ್ಟ್ರೀಮಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ಗಳ ಕ್ಷೇತ್ರದಲ್ಲಿ, ಮೊದಲ ಪಾಸ್ನಲ್ಲಿನ ಮಿಶ್ರಾ-ಗ್ರೀಸ್ ಅಲ್ಗಾರಿದಮ್ನ ಔಟ್ಪುಟ್ ಅನ್ನು ಸಾರಾಂಶ ಎಂದು ಕರೆಯಬಹುದು, ಮತ್ತು ಅಂತಹ ಸಾರಾಂಶಗಳನ್ನು ಡೇಟಾ ಸ್ಟ್ರೀಮ್ ಮಾದರಿಯಲ್ಲಿನ ಆಗಾಗ್ಗೆ ಅಂಶಗಳ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಬಳಸಲಾಗುತ್ತದೆ. ಸ್ಟ್ರೀಮಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ ಸ್ಟ್ರೀಮ್ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಡೇಟಾ ಐಟಂಗಳ ಪಟ್ಟಿಯ ಮೇಲೆ ಸಣ್ಣ, ಸೀಮಿತ ಸಂಖ್ಯೆಯ ಪಾಸ್ಗಳನ್ನು ಮಾಡುತ್ತದೆ. ಇದು ಉತ್ತರವನ್ನು ನೀಡಲು ಪಟ್ಟಿಯ ಗಾತ್ರದಲ್ಲಿ ಹೆಚ್ಚಿನ ಲಾಗರಿಥಮಿಕ್ ಪ್ರಮಾಣದ ಹೆಚ್ಚುವರಿ ಜಾಗವನ್ನು ಬಳಸಿಕೊಂಡು ಅಂಶಗಳನ್ನು ಸಂಸ್ಕರಿಸುತ್ತದೆ. ಮಿಶ್ರಾ-ಗ್ರೀಸ್ ಸಾರಾಂಶ ಎಂಬ ಪದವನ್ನು ಗ್ರಹಾಂ ಕಾರ್ಮೋಡ್ ಅವರು ಸೃಷ್ಟಿಸಿದಂತೆ ತೋರುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು ಸ್ಟ್ರೀಮಿಂಗ್ ಕ್ರಮಾವಳಿಗಳು