Approximate counting algorithm
ಅಂದಾಜು ಎಣಿಕೆಯ ಕ್ರಮಾವಳಿಯು ಸಣ್ಣ ಪ್ರಮಾಣದ ಸ್ಮರಣೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಹೆಚ್ಚಿನ ಸಂಖ್ಯೆಯ ಘಟನೆಗಳನ್ನು ಎಣಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. 1977 ರಲ್ಲಿ ಬೆಲ್ ಲ್ಯಾಬ್ಸ್ನ ರಾಬರ್ಟ್ ಮೋರಿಸ್ ಅವರು ಕಂಡುಹಿಡಿದ ಇದು ಕೌಂಟರ್ ಅನ್ನು ಹೆಚ್ಚಿಸಲು ಸಂಭವನೀಯ ತಂತ್ರಗಳನ್ನು ಬಳಸುತ್ತದೆ. ಇದನ್ನು 1980ರ ದಶಕದ ಆರಂಭದಲ್ಲಿ ಐ. ಎನ್. ಆರ್. ಐ. ಎ. ರೊಕ್ವೆನ್ಕೋರ್ಟ್ನ ಫಿಲಿಪ್ ಫ್ಲಾಜೋಲೆಟ್ ಅವರು ಸಂಪೂರ್ಣವಾಗಿ ವಿಶ್ಲೇಷಿಸಿದರು, ಅವರು ಅಂದಾಜು ಎಣಿಕೆ ಎಂಬ ಹೆಸರನ್ನು ಸೃಷ್ಟಿಸಿದರು ಮತ್ತು ಸಂಶೋಧನಾ ಸಮುದಾಯದಲ್ಲಿ ಅದರ ಮಾನ್ಯತೆಗೆ ಬಲವಾದ ಕೊಡುಗೆ ನೀಡಿದರು. ಹೆಚ್ಚಿನ ಗುಣಮಟ್ಟದ ಅಂದಾಜು ಮತ್ತು ವೈಫಲ್ಯದ ಕಡಿಮೆ ಸಂಭವನೀಯತೆಯ ಮೇಲೆ ಕೇಂದ್ರೀಕರಿಸಿದಾಗ, ನೆಲ್ಸನ್ ಮತ್ತು ಯು, ಸಮಸ್ಯೆಯ ಎಲ್ಲಾ ಕ್ರಮಾವಳಿಗಳಲ್ಲಿ ಮೋರಿಸ್ ಕೌಂಟರ್ಗೆ ಬಹಳ ಕಡಿಮೆ ಮಾರ್ಪಾಡು ಲಕ್ಷಣರಹಿತವಾಗಿ ಸೂಕ್ತವಾಗಿದೆ ಎಂದು ತೋರಿಸಿದರು. ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸ್ಟ್ರೀಮಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ಗಳ ಪೂರ್ವಗಾಮಿಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ ಎಂದು ಪರಿಗಣಿಸಲಾಗಿದೆ ಮತ್ತು ಡೇಟಾ ಸ್ಟ್ರೀಮ್ನ ಆವರ್ತನ ಕ್ಷಣಗಳನ್ನು ನಿರ್ಧರಿಸುವ ಹೆಚ್ಚು ಸಾಮಾನ್ಯ ಸಮಸ್ಯೆಯು ಕ್ಷೇತ್ರದ ಕೇಂದ್ರಬಿಂದುವಾಗಿದೆ. ಮೋರಿಸ್ನ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು, ಕೌಂಟರ್ ನಿಜವಾದ ಎಣಿಕೆಯ "ಪ್ರಮಾಣದ ಅಂದಾಜಿನ ಕ್ರಮ" ವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. ಅಂದಾಜು ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ ಪಕ್ಷಪಾತರಹಿತವಾಗಿದೆ. ಕೌಂಟರ್ ಅನ್ನು ಹೆಚ್ಚಿಸಲು, ಹುಸಿ-ಯಾದೃಚ್ಛಿಕ ಘಟನೆಯನ್ನು ಬಳಸಲಾಗುತ್ತದೆ, ಅಂದರೆ ಏರಿಕೆಯು ಸಂಭವನೀಯ ಘಟನೆಯಾಗಿದೆ. ಜಾಗವನ್ನು ಉಳಿಸಲು, ಘಾತಾಂಕವನ್ನು ಮಾತ್ರ ಇಡಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಬೇಸ್ 2 ರಲ್ಲಿ, ಕೌಂಟರ್ ಎಣಿಕೆ 1,2,4,8,16,32, ಮತ್ತು ಎರಡರ ಎಲ್ಲಾ ಶಕ್ತಿಗಳೆಂದು ಅಂದಾಜು ಮಾಡಬಹುದು. ಕೇವಲ ಘಾತಾಂಕವನ್ನು ಹಿಡಿದಿಟ್ಟುಕೊಳ್ಳುವುದು ಮೆಮೊರಿಯ ಅಗತ್ಯವಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, 4 ರಿಂದ 8 ಕ್ಕೆ ಹೆಚ್ಚಿಸಲು, ಸೂಡೋ-ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಯನ್ನು ಉತ್ಪಾದಿಸಲಾಗುತ್ತದೆ, ಅಂದರೆ ಕೌಂಟರ್ ಹೆಚ್ಚಾಗುವ ಸಂಭವನೀಯತೆಯು 0.25 ಆಗಿದೆ. ಇಲ್ಲದಿದ್ದರೆ, ಕೌಂಟರ್ 4ನೇ ಸ್ಥಾನದಲ್ಲಿರುತ್ತದೆ. ಕೆಳಗಿನ ಕೋಷ್ಟಕವು ಕೌಂಟರ್ ನ ಕೆಲವು ಸಂಭಾವ್ಯ ಮೌಲ್ಯಗಳನ್ನು ವಿವರಿಸುತ್ತದೆಃ ಕೌಂಟರ್ 101 ರ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದ್ದರೆ, ಅದು 5 ರ ಘಾತಾಂಕಕ್ಕೆ (101 ರ ದಶಮಾಂಶಕ್ಕೆ ಸಮಾನ) ಸಮನಾಗಿರುತ್ತದೆ, ಆಗ ಅಂದಾಜು ಎಣಿಕೆ, ಅಥವಾ 32 ಆಗಿದೆ. ಹೆಚ್ಚಳದ ಘಟನೆಗಳ ನಿಜವಾದ ಎಣಿಕೆ 5 () ಎಂದು ಸಾಕಷ್ಟು ಕಡಿಮೆ ಸಂಭವನೀಯತೆ ಇದೆ. ಹೆಚ್ಚಳದ ಘಟನೆಗಳ ನಿಜವಾದ ಸಂಖ್ಯೆಯು "ಸುಮಾರು 32" ಆಗಿರಬಹುದು, ಆದರೆ ಇದು ಅನಿಯಂತ್ರಿತವಾಗಿ ಹೆಚ್ಚಾಗಿರಬಹುದು (39 ಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ನಿಜವಾದ ಎಣಿಕೆಗಳ ಸಂಭವನೀಯತೆಗಳು ಕಡಿಮೆಯಾಗುವುದರೊಂದಿಗೆ). ಕೌಂಟರ್ ಮೌಲ್ಯಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದು 2 ರ ಪವರ್ಗಳನ್ನು ಕೌಂಟರ್ ಮೌಲ್ಯಗಳಾಗಿ ಬಳಸುವಾಗ ಮೆಮೊರಿ ದಕ್ಷವಾಗಿರುತ್ತದೆ, ಅನಿಯಂತ್ರಿತ ಮೌಲ್ಯಗಳು ಕ್ರಿಯಾತ್ಮಕ ದೋಷ ವ್ಯಾಪ್ತಿಯನ್ನು ಸೃಷ್ಟಿಸುತ್ತವೆ ಮತ್ತು ಸಣ್ಣ ಮೌಲ್ಯಗಳು ದೊಡ್ಡ ಮೌಲ್ಯಗಳಿಗಿಂತ ಹೆಚ್ಚಿನ ದೋಷ ಅನುಪಾತವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಕೌಂಟರ್ ಮೌಲ್ಯಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡುವ ಇತರ ವಿಧಾನಗಳು ಮೆಮೊರಿ ಲಭ್ಯತೆ, ಅಪೇಕ್ಷಿತ ದೋಷ ಅನುಪಾತ ಅಥವಾ ಎಣಿಕೆಯ ವ್ಯಾಪ್ತಿಯಂತಹ ನಿಯತಾಂಕಗಳನ್ನು ಪರಿಗಣಿಸಿ ಸೂಕ್ತವಾದ ಮೌಲ್ಯಗಳ ಗುಂಪನ್ನು ಒದಗಿಸುತ್ತವೆ. ಆದಾಗ್ಯೂ, ಹಲವಾರು ಕೌಂಟರ್ಗಳು ಒಂದೇ ಮೌಲ್ಯಗಳನ್ನು ಹಂಚಿಕೊಂಡಾಗ, ಅತಿದೊಡ್ಡ ಎಣಿಕೆಯ ವ್ಯಾಪ್ತಿಯ ಕೌಂಟರ್ಗೆ ಅನುಗುಣವಾಗಿ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದುವಂತೆ ಮಾಡಲಾಗುತ್ತದೆ ಮತ್ತು ಸಣ್ಣ ಕೌಂಟರ್ಗಳಿಗೆ ಉಪ-ಅತ್ಯುತ್ತಮ ನಿಖರತೆಯನ್ನು ನೀಡುತ್ತದೆ. ಸ್ವತಂತ್ರ ಕೌಂಟರ್ ಎಸ್ಟಿಮೇಷನ್ ಬಕೆಟ್ಗಳನ್ನು ನಿರ್ವಹಿಸುವ ಮೂಲಕ ತಗ್ಗಿಸುವಿಕೆಯನ್ನು ಸಾಧಿಸಲಾಗುತ್ತದೆ, ಇದು ಬಕೆಟ್ನಲ್ಲಿರುವ ಇತರ ಕೌಂಟರ್ಗಳಿಗೆ ದೊಡ್ಡ ಕೌಂಟರ್ನ ಪರಿಣಾಮವನ್ನು ನಿರ್ಬಂಧಿಸುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಕೈಯಿಂದ ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದು. ಕೌಂಟರ್ ಅನ್ನು ಹೆಚ್ಚಿಸುವಾಗ, ಕೌಂಟರ್ನ ಪ್ರಸ್ತುತ ಮೌಲ್ಯಕ್ಕೆ ಅನುಗುಣವಾದ ನಾಣ್ಯವನ್ನು ಹಲವಾರು ಬಾರಿ ತಿರುಗಿಸಿ. ಪ್ರತಿ ಬಾರಿಯೂ ಅದು ತಲೆಯ ಮೇಲೆ ಬಂದರೆ, ನಂತರ ಕೌಂಟರ್ ಅನ್ನು ಹೆಚ್ಚಿಸಿ. ಇಲ್ಲದಿದ್ದರೆ, ಅದನ್ನು ಹೆಚ್ಚಿಸಬೇಡಿ. ಇದನ್ನು ಕಂಪ್ಯೂಟರ್ನಲ್ಲಿ ಸುಲಭವಾಗಿ ಸಾಧಿಸಬಹುದು. ಕೌಂಟರ್ನ ಪ್ರಸ್ತುತ ಮೌಲ್ಯವಾಗಿರಲಿ. ಹುಸಿ-ಯಾದೃಚ್ಛಿಕ ಬಿಟ್ಗಳನ್ನು ಉತ್ಪಾದಿಸುವುದು ಮತ್ತು ಆ ಎಲ್ಲಾ ಬಿಟ್ಗಳ ತಾರ್ಕಿಕ AND ಅನ್ನು ಬಳಸುವುದು ಮತ್ತು ಫಲಿತಾಂಶವನ್ನು ಕೌಂಟರ್ಗೆ ಸೇರಿಸುವುದು. ಆ ಹುಸಿ-ಯಾದೃಚ್ಛಿಕ ಬಿಟ್ಗಳಲ್ಲಿ ಯಾವುದಾದರೂ ಶೂನ್ಯವಾಗಿದ್ದರೆ ಫಲಿತಾಂಶವು ಶೂನ್ಯವಾಗಿದ್ದು, ಹೆಚ್ಚಳದ ಸಂಭವನೀಯತೆಯನ್ನು ಸಾಧಿಸುತ್ತದೆ. ಕೌಂಟರ್ ಅನ್ನು ಹೆಚ್ಚಿಸಲು ವಿನಂತಿಸಿದಾಗಲೆಲ್ಲಾ ಈ ಕಾರ್ಯವಿಧಾನವನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಲಾಗುತ್ತದೆ. ಅನ್ವಯಗಳು ಮಾದರಿಗಳಿಗಾಗಿ ದೊಡ್ಡ ದತ್ತಾಂಶ ಸ್ಟ್ರೀಮ್ಗಳನ್ನು ಪರೀಕ್ಷಿಸಲು ಅಲ್ಗಾರಿದಮ್ ಉಪಯುಕ್ತವಾಗಿದೆ. ದತ್ತಾಂಶ ಸಂಕೋಚನ, ದೃಷ್ಟಿ ಮತ್ತು ಧ್ವನಿ ಗುರುತಿಸುವಿಕೆ ಮತ್ತು ಇತರ ಕೃತಕ ಬುದ್ಧಿಮತ್ತೆಯ ಅನ್ವಯಿಕೆಗಳಲ್ಲಿ ಇದು ವಿಶೇಷವಾಗಿ ಉಪಯುಕ್ತವಾಗಿದೆ. ಹೈಪರ್ಲಾಗ್ ಲಾಗ್ ಉಲ್ಲೇಖಗಳ ಮೂಲಗಳು ಮೋರಿಸ್, ಆರ್. ದೊಡ್ಡ ಸಂಖ್ಯೆಯ ಘಟನೆಗಳನ್ನು ಸಣ್ಣ ರೆಜಿಸ್ಟರ್ಗಳಲ್ಲಿ ಎಣಿಕೆ ಮಾಡುವುದನ್ನು ಸಹ ನೋಡಿ. ಕಮ್ಯುನಿಕೇಷನ್ಸ್ ಆಫ್ ದಿ ಎಸಿಎಂ 21,10 (1978), ಫ್ಲಾಜೋಲೆಟ್, ಪಿ. ಅಂದಾಜು ಎಣಿಕೆಃ ಒಂದು ವಿವರವಾದ ವಿಶ್ಲೇಷಣೆ. ಬಿಐಟಿ 25, (1985), 113-134 ಫೌಚ್ಸ್, ಎಮ್., ಲೀ, ಸಿ-ಕೆ., ಪ್ರೊಡಿಂಗರ್, ಎಚ್., ಪೊಯ್ಸನ್-ಲ್ಯಾಪ್ಲೇಸ್-ಮೆಲಿನ್ ವಿಧಾನದ ಯಾದೃಚ್ಛಿಕ ಕ್ರಮಾವಳಿಗಳ ಮೂಲಕ ಅಂದಾಜು ಎಣಿಕೆ