Succinct data structure
ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ಸಂಕ್ಷಿಪ್ತ ದತ್ತಾಂಶ ರಚನೆಯು ದತ್ತಾಂಶ ರಚನೆಯಾಗಿದ್ದು, ಇದು ಮಾಹಿತಿ-ಸೈದ್ಧಾಂತಿಕ ಲೋವರ್ ಬೌಂಡ್ಗೆ "ಹತ್ತಿರ" ಇರುವ ಜಾಗವನ್ನು ಬಳಸುತ್ತದೆ, ಆದರೆ (ಇತರ ಸಂಕುಚಿತ ಪ್ರಾತಿನಿಧ್ಯಗಳಿಗಿಂತ ಭಿನ್ನವಾಗಿ) ಇನ್ನೂ ಸಮರ್ಥ ಪ್ರಶ್ನೆಯ ಕಾರ್ಯಾಚರಣೆಗಳಿಗೆ ಅವಕಾಶ ನೀಡುತ್ತದೆ. ಈ ಪರಿಕಲ್ಪನೆಯನ್ನು ಮೂಲತಃ ಜಾಕೋಬ್ಸನ್ ಅವರು ಬಿಟ್ ವಾಹಕಗಳು, (ಲೇಬಲ್ ಮಾಡದ) ಮರಗಳು ಮತ್ತು ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳನ್ನು ಎನ್ಕೋಡ್ ಮಾಡಲು ಪರಿಚಯಿಸಿದರು. ಸಾಮಾನ್ಯ ನಷ್ಟವಿಲ್ಲದ ದತ್ತಾಂಶ ಸಂಕೋಚನ ಕ್ರಮಾವಳಿಗಳಿಗಿಂತ ಭಿನ್ನವಾಗಿ, ಸಂಕ್ಷಿಪ್ತ ದತ್ತಾಂಶ ರಚನೆಗಳು ಅವುಗಳನ್ನು ಮೊದಲು ಡಿಕಂಪ್ರೆಸ್ ಮಾಡದೆಯೇ ಅವುಗಳನ್ನು ಸ್ಥಳದಲ್ಲೇ ಬಳಸುವ ಸಾಮರ್ಥ್ಯವನ್ನು ಉಳಿಸಿಕೊಳ್ಳುತ್ತವೆ. ಸಂಗ್ರಹಿಸಿದ ಅಥವಾ ಎನ್ಕೋಡ್ ಮಾಡಲಾದ ದತ್ತಾಂಶದ ಗಾತ್ರವು ದತ್ತಾಂಶದ ನಿರ್ದಿಷ್ಟ ವಿಷಯದ ಮೇಲೆ ಅವಲಂಬಿತವಾಗಿರುವುದರಿಂದ, ಸಂಕುಚಿತ ದತ್ತಾಂಶ ರಚನೆಯು ಸಂಬಂಧಿತ ಕಲ್ಪನೆಯಾಗಿದೆ. ಇದು ಕೆಲವು ದತ್ತಾಂಶವನ್ನು ಸಂಗ್ರಹಿಸಲು ಅಗತ್ಯವಾದ ಬಿಟ್ಗಳ ಮಾಹಿತಿ-ಸೈದ್ಧಾಂತಿಕ ಅತ್ಯುತ್ತಮ ಸಂಖ್ಯೆ ಎಂದು ಭಾವಿಸೋಣ. ಈ ದತ್ತಾಂಶದ ಪ್ರಾತಿನಿಧ್ಯವನ್ನು ಕರೆಯಲಾಗುತ್ತದೆಃ ಇದು ಸ್ವಲ್ಪ ಜಾಗವನ್ನು ತೆಗೆದುಕೊಂಡರೆ ಸೂಚ್ಯ, ಸ್ವಲ್ಪ ಜಾಗವನ್ನು ತೆಗೆದುಕೊಂಡರೆ ಸಂಕ್ಷಿಪ್ತ, ಮತ್ತು ಸ್ವಲ್ಪ ಜಾಗವನ್ನು ತೆಗೆದುಕೊಂಡರೆ ಸಾಂದ್ರವಾಗಿರುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಶೇಖರಣೆಯ ಬಿಟ್ಗಳನ್ನು ಬಳಸುವ ದತ್ತಾಂಶ ರಚನೆಯು ಸಾಂದ್ರವಾಗಿರುತ್ತದೆ, ಬಿಟ್ಗಳು ಸಂಕ್ಷಿಪ್ತವಾಗಿರುತ್ತವೆ, ಬಿಟ್ಗಳು ಸಹ ಸಂಕ್ಷಿಪ್ತವಾಗಿರುತ್ತವೆ ಮತ್ತು ಬಿಟ್ಗಳು ಸೂಚ್ಯವಾಗಿರುತ್ತವೆ. ಹೀಗಾಗಿ ಸೂಚ್ಯ ರಚನೆಗಳನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಇನ್ಪುಟ್ ಡೇಟಾದ ಕೆಲವು ಕ್ರಮಪಲ್ಲಟನೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಮಾಹಿತಿಯನ್ನು ಸಂಗ್ರಹಿಸಲು ಕಡಿಮೆ ಮಾಡಲಾಗುತ್ತದೆ; ಇದಕ್ಕೆ ಅತ್ಯಂತ ಪ್ರಸಿದ್ಧ ಉದಾಹರಣೆಯೆಂದರೆ ರಾಶಿ. ಶ್ರೇಣಿಯ/ಆಯ್ದ ನಿಘಂಟುಗಳು ಎಂದೂ ಕರೆಯಲಾಗುವ ಸೂಚ್ಯ ಸೂಚ್ಯಂಕದ ನಿಘಂಟುಗಳು, ಬೈನರಿ ಮರಗಳು,-ಆರಿ ಮರಗಳು ಮತ್ತು ಮಲ್ಟಿಸೆಟ್ಗಳು, ಜೊತೆಗೆ ಪ್ರತ್ಯಯ ಮರಗಳು ಮತ್ತು ಸರಣಿಗಳನ್ನು ಒಳಗೊಂಡಂತೆ ಹಲವಾರು ಸಂಕ್ಷಿಪ್ತ ಪ್ರಾತಿನಿಧ್ಯ ತಂತ್ರಗಳ ಆಧಾರವನ್ನು ರೂಪಿಸುತ್ತವೆ. ಮೂಲಭೂತ ಸಮಸ್ಯೆಯೆಂದರೆ ಬ್ರಹ್ಮಾಂಡದ ಉಪವಿಭಾಗವನ್ನು ಸಂಗ್ರಹಿಸುವುದು, ಇದನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಬಿಟ್ ರಚನೆಯಾಗಿ ಪ್ರತಿನಿಧಿಸಲಾಗುತ್ತದೆ, ಅಲ್ಲಿ ಐಎಫ್ಎಫ್ ಸೂಚ್ಯಂಕ ಮಾಡಬಹುದಾದ ನಿಘಂಟುವು ನಿಘಂಟುಗಳಲ್ಲಿನ ಸಾಮಾನ್ಯ ವಿಧಾನಗಳನ್ನು (ಪ್ರಶ್ನೆಗಳು, ಮತ್ತು ಕ್ರಿಯಾತ್ಮಕ ಸಂದರ್ಭದಲ್ಲಿ ಅಳವಡಿಕೆಗಳು/ಅಳಿಸುವಿಕೆಗಳು) ಮತ್ತು ಈ ಕೆಳಗಿನ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಬೆಂಬಲಿಸುತ್ತದೆಃ ಫಾರ್. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಸ್ಥಾನಕ್ಕೆ ಸಮಾನವಾದ ಅಂಶಗಳ ಸಂಖ್ಯೆಯನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ ಮತ್ತು-th ಘಟನೆಯ ಸ್ಥಾನವನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ. ಶೇಖರಣಾ ಸ್ಥಳದ ಬಿಟ್ಗಳನ್ನು (ಮೂಲ ಬಿಟ್ ರಚನೆ ಮತ್ತು ಸಹಾಯಕ ರಚನೆ) ಬಳಸುವ ಸರಳ ಪ್ರಾತಿನಿಧ್ಯವಿದೆ ಮತ್ತು ಸ್ಥಿರ ಸಮಯದಲ್ಲಿ ಶ್ರೇಣಿಯನ್ನು ಮತ್ತು ಆಯ್ಕೆಯನ್ನು ಬೆಂಬಲಿಸುತ್ತದೆ. ಇದು ಶ್ರೇಣಿ-ಕನಿಷ್ಠ ಪ್ರಶ್ನೆಗಳಿಗೆ ಹೋಲುವ ಕಲ್ಪನೆಯನ್ನು ಬಳಸುತ್ತದೆ; ಸೀಮಿತ ಗಾತ್ರದ ಉಪ-ಸಮಸ್ಯೆಯಲ್ಲಿ ನಿಲ್ಲಿಸುವ ಮೊದಲು ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ಪುನರಾವರ್ತನೆಗಳು ಇರುತ್ತವೆ. ಬಿಟ್ ಶ್ರೇಣಿಯನ್ನು ಗಾತ್ರದ ಬಿಟ್ಗಳ ದೊಡ್ಡ ಬ್ಲಾಕ್ಗಳಾಗಿ ಮತ್ತು ಗಾತ್ರದ ಬಿಟ್ಗಳ ಸಣ್ಣ ಬ್ಲಾಕ್ಗಳಾಗಿ ವಿಂಗಡಿಸಲಾಗಿದೆ. ಪ್ರತಿ ದೊಡ್ಡ ಬ್ಲಾಕ್ಗೆ, ಅದರ ಮೊದಲ ಬಿಟ್ನ ಶ್ರೇಣಿಯನ್ನು ಪ್ರತ್ಯೇಕ ಕೋಷ್ಟಕದಲ್ಲಿ ಸಂಗ್ರಹಿಸಲಾಗುತ್ತದೆ; ಅಂತಹ ಪ್ರತಿಯೊಂದು ನಮೂದು ಒಟ್ಟು ಬಿಟ್ಗಳ ಶೇಖರಣೆಗೆ ಬಿಟ್ಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ದೊಡ್ಡ ಬ್ಲಾಕ್ನೊಳಗೆ, ಮತ್ತೊಂದು ಕೋಶವು ಅದು ಒಳಗೊಂಡಿರುವ ಪ್ರತಿಯೊಂದು ಸಣ್ಣ ಬ್ಲಾಕ್ಗಳ ಶ್ರೇಣಿಯನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ. ಇಲ್ಲಿ ವ್ಯತ್ಯಾಸವೆಂದರೆ, ಪ್ರತಿ ನಮೂದಿಗೆ ಬಿಟ್ಗಳು ಮಾತ್ರ ಬೇಕಾಗುತ್ತವೆ, ಏಕೆಂದರೆ ದೊಡ್ಡ ಬ್ಲಾಕ್ ಅನ್ನು ಹೊಂದಿರುವ ಮೊದಲ ಬಿಟ್ನ ಶ್ರೇಣಿಯ ವ್ಯತ್ಯಾಸಗಳನ್ನು ಮಾತ್ರ ಸಂಗ್ರಹಿಸಬೇಕಾಗುತ್ತದೆ. ಹೀಗಾಗಿ, ಈ ಕೋಷ್ಟಕವು ಒಟ್ಟು ಬಿಟ್ಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಒಂದು ಲುಕ್ಅಪ್ ಟೇಬಲ್ ಅನ್ನು ನಂತರ ಬಳಸಬಹುದು, ಅದು ಸಾಧ್ಯವಿರುವ ಪ್ರತಿಯೊಂದು ಶ್ರೇಣಿಯ ಪ್ರಶ್ನೆಗೆ ಉತ್ತರವನ್ನು ಸ್ವಲ್ಪ ಉದ್ದದ ಸ್ಟ್ರಿಂಗ್ನಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತದೆ; ಇದಕ್ಕೆ ಸ್ವಲ್ಪ ಶೇಖರಣಾ ಸ್ಥಳ ಬೇಕಾಗುತ್ತದೆ. ಹೀಗಾಗಿ, ಈ ಪ್ರತಿಯೊಂದು ಸಹಾಯಕ ಕೋಷ್ಟಕಗಳು ಜಾಗವನ್ನು ತೆಗೆದುಕೊಳ್ಳುವುದರಿಂದ, ಈ ದತ್ತಾಂಶ ರಚನೆಯು ಸಮಯ ಮತ್ತು ಬಿಟ್ಗಳ ಜಾಗದಲ್ಲಿ ಶ್ರೇಣಿಯ ಪ್ರಶ್ನೆಗಳನ್ನು ಬೆಂಬಲಿಸುತ್ತದೆ. ಒಂದು ಪ್ರಶ್ನೆಗೆ ಸ್ಥಿರವಾದ ಸಮಯದಲ್ಲಿ ಉತ್ತರಿಸಲು, ಸ್ಥಿರವಾದ ಸಮಯದ ಕ್ರಮಾವಳಿ ಲೆಕ್ಕಾಚಾರ ಮಾಡುತ್ತದೆಃ ಪ್ರಾಯೋಗಿಕವಾಗಿ, ಹುಡುಕಾಟ ಕೋಷ್ಟಕವನ್ನು ಬಿಟ್ವೈಸ್ ಕಾರ್ಯಾಚರಣೆಗಳು ಮತ್ತು ಸಣ್ಣ ಕೋಷ್ಟಕಗಳಿಂದ ಬದಲಾಯಿಸಬಹುದು, ಇದನ್ನು ಸಣ್ಣ ಬ್ಲಾಕ್ಗಳಲ್ಲಿ ಹೊಂದಿಸಲಾದ ಬಿಟ್ಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಬಳಸಬಹುದು. ಇದು ಸಾಮಾನ್ಯವಾಗಿ ಪ್ರಯೋಜನಕಾರಿಯಾಗಿದೆ, ಏಕೆಂದರೆ ಸಂಕ್ಷಿಪ್ತ ದತ್ತಾಂಶ ರಚನೆಗಳು ದೊಡ್ಡ ದತ್ತಾಂಶ ಸೆಟ್ಗಳಲ್ಲಿ ಅವುಗಳ ಬಳಕೆಯನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತವೆ, ಈ ಸಂದರ್ಭದಲ್ಲಿ ಕ್ಯಾಶ್ ಮಿಸ್ಗಳು ಹೆಚ್ಚು ಆಗಾಗ್ಗೆ ಆಗುತ್ತವೆ ಮತ್ತು ಹತ್ತಿರದ CPU ಕ್ಯಾಶ್ಗಳಿಂದ ಲುಕ್ಅಪ್ ಟೇಬಲ್ ಅನ್ನು ಹೊರಹಾಕುವ ಸಾಧ್ಯತೆಗಳು ಹೆಚ್ಚಾಗುತ್ತವೆ. ಶ್ರೇಣಿಗೆ ಬಳಸುವ ಅದೇ ಸಹಾಯಕ ರಚನೆಯ ಮೇಲೆ ಬೈನರಿ ಹುಡುಕಾಟವನ್ನು ಮಾಡುವ ಮೂಲಕ ಆಯ್ದ ಪ್ರಶ್ನೆಗಳನ್ನು ಸುಲಭವಾಗಿ ಬೆಂಬಲಿಸಬಹುದು; ಆದಾಗ್ಯೂ, ಇದು ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಹೆಚ್ಚುವರಿ ಸಂಗ್ರಹಣೆಯ ತುಣುಕುಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಹೆಚ್ಚು ಸಂಕೀರ್ಣವಾದ ರಚನೆಯನ್ನು ಸ್ಥಿರ ಸಮಯದಲ್ಲಿ ಆಯ್ಕೆ ಮಾಡಲು ಬಳಸಬಹುದು. ಆಚರಣೆಯಲ್ಲಿ, ಈ ಪರಿಹಾರಗಳಲ್ಲಿ ಅನೇಕವು ಸಂಕೇತದಲ್ಲಿ ಗುಪ್ತ ಸ್ಥಿರಾಂಕಗಳನ್ನು ಹೊಂದಿದ್ದು, ಯಾವುದೇ ಅಸಿಂಪ್ಟೋಟಿಕ್ ಪ್ರಯೋಜನವು ಸ್ಪಷ್ಟವಾಗುವ ಮೊದಲು ಪ್ರಾಬಲ್ಯವನ್ನು ಹೊಂದಿರುತ್ತವೆ; ಬ್ರಾಡ್ ವರ್ಡ್ ಕಾರ್ಯಾಚರಣೆಗಳು ಮತ್ತು ಪದ-ಹೊಂದಾಣಿಕೆಯ ಬ್ಲಾಕ್ಗಳನ್ನು ಬಳಸುವ ಅನುಷ್ಠಾನಗಳು ಸಾಮಾನ್ಯವಾಗಿ ಆಚರಣೆಯಲ್ಲಿ ಉತ್ತಮವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತವೆ. ಎಂಟ್ರೊಪಿ-ಸಂಕುಚಿತ ಪರಿಹಾರಗಳು ಬಾಹ್ಯಾಕಾಶ ವಿಧಾನವನ್ನು ವಿಭಿನ್ನವಾದ ಉಪಗುಂಪುಗಳಿವೆ (ಅಥವಾ ನಿಖರವಾಗಿ 1 ರೊಂದಿಗೆ ಉದ್ದದ ಬೈನರಿ ತಂತಿಗಳಿವೆ) ಎಂಬುದನ್ನು ಗಮನಿಸುವುದರ ಮೂಲಕ ಸುಧಾರಿಸಬಹುದು, ಮತ್ತು ಆದ್ದರಿಂದ ಇದು ಶೇಖರಿಸಿಡಲು ಅಗತ್ಯವಿರುವ ಬಿಟ್ಗಳ ಸಂಖ್ಯೆಯ ಮೇಲೆ ಮಾಹಿತಿಯ ಸೈದ್ಧಾಂತಿಕ ಕೆಳ ಮಿತಿಯಾಗಿದೆ. ಒಂದು ಸಂಕ್ಷಿಪ್ತ (ಸ್ಥಿರ) ನಿಘಂಟು ಇದೆ, ಅದು ಈ ಮಿತಿಯನ್ನು ಸಾಧಿಸುತ್ತದೆ, ಅಂದರೆ ಜಾಗವನ್ನು ಬಳಸುತ್ತದೆ. ಈ ರಚನೆಯನ್ನು ಶ್ರೇಣಿಯನ್ನು ಬೆಂಬಲಿಸಲು ಮತ್ತು ಪ್ರಶ್ನೆಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡಲು ವಿಸ್ತರಿಸಬಹುದು ಮತ್ತು ಜಾಗವನ್ನು ತೆಗೆದುಕೊಳ್ಳಬಹುದು. ಈ ರಚನೆಯಲ್ಲಿ ಸರಿಯಾದ ಶ್ರೇಣಿಯ ಪ್ರಶ್ನೆಗಳು ಸೆಟ್ನಲ್ಲಿ ಒಳಗೊಂಡಿರುವ ಅಂಶಗಳಿಗೆ ಸೀಮಿತವಾಗಿವೆ, ಇದು ಕನಿಷ್ಠ ಪರಿಪೂರ್ಣ ಹ್ಯಾಶಿಂಗ್ ಕಾರ್ಯಗಳು ಹೇಗೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತವೆ ಎಂಬುದಕ್ಕೆ ಹೋಲುತ್ತದೆ. ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುವ ಪ್ರಶ್ನೆಗಳೊಂದಿಗೆ ನಿಘಂಟಿನ ಶೇಖರಣಾ ಸ್ಥಳವನ್ನು ಕಡಿಮೆ ಮಾಡುವ ಮೂಲಕ ಈ ಮಿತಿಯನ್ನು ಸ್ಪೇಸ್/ಟೈಮ್ ಟ್ರೇಡ್ಆಫ್ಗೆ ಕಡಿಮೆ ಮಾಡಬಹುದು. ಬಿಟ್ಗಳಿಗಿಂತ ಕಡಿಮೆ ಬಳಸುವ ಶ್ರೇಣಿಯನ್ನು ಬೆಂಬಲಿಸುವ (ಆದರೆ ಆಯ್ಕೆ ಮಾಡದ) ಸೂಚ್ಯಂಕದ ನಿಘಂಟನ್ನು ನಿರ್ಮಿಸಲು ಸಹ ಸಾಧ್ಯವಿದೆ. ಅಂತಹ ನಿಘಂಟನ್ನು ಮೊನೊಟೋನ್ ಮಿನಿಮಲ್ ಪರ್ಫೆಕ್ಟ್ ಹ್ಯಾಶ್ ಫಂಕ್ಷನ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಮತ್ತು ಇದನ್ನು ಕಡಿಮೆ ಬಿಟ್ಗಳನ್ನು ಬಳಸಿ ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದು. ಸಂಕ್ಷಿಪ್ತ ಕ್ರಮವಿಲ್ಲದ ನಿಘಂಟು ಎಂದೂ ಕರೆಯಲಾಗುವ ಸಂಕ್ಷಿಪ್ತ ಹ್ಯಾಶ್ ಕೋಷ್ಟಕವು, ಬಾಹ್ಯಾಕಾಶ ಬಿಟ್ಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಬ್ರಹ್ಮಾಂಡದ ಕೀಲಿಗಳನ್ನು ಸಂಗ್ರಹಿಸುವ ದತ್ತಾಂಶ ರಚನೆಯಾಗಿದ್ದು, ಸ್ಥಿರವಾದ ನಿರೀಕ್ಷಿತ ಸಮಯದಲ್ಲಿ ಸದಸ್ಯತ್ವದ ಪ್ರಶ್ನೆಗಳನ್ನು ಬೆಂಬಲಿಸುತ್ತದೆ. ಒಂದು ಸಂಕ್ಷಿಪ್ತ ಹ್ಯಾಶ್ ಕೋಷ್ಟಕವು ಸ್ಥಿರವಾದ ನಿರೀಕ್ಷಿತ ಸಮಯದಲ್ಲಿ ಒಳಸೇರಿಸುವಿಕೆ ಮತ್ತು ಅಳಿಸುವಿಕೆಯನ್ನು ಸಹ ಬೆಂಬಲಿಸಿದರೆ, ಅದನ್ನು ಡೈನಾಮಿಕ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಇಲ್ಲದಿದ್ದರೆ ಅದನ್ನು ಸ್ಥಿರ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಮೊದಲ ಕ್ರಿಯಾತ್ಮಕ ಸಂಕ್ಷಿಪ್ತ ಹ್ಯಾಶ್ ಟೇಬಲ್ 2003 ರಲ್ಲಿ ರಾಮನ್ ಮತ್ತು ರಾವ್ ಕಾರಣವಾಗಿತ್ತು. ಅಂತಹ ಸಂದರ್ಭದಲ್ಲಿ, ಅವುಗಳ ದ್ರಾವಣವು ಸ್ಪೇಸ್ ಬಿಟ್ಗಳನ್ನು ಬಳಸುತ್ತದೆ. ತರುವಾಯ, ಯಾವುದೇ ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ಲಾಗರಿದಮ್ಗಳಿಗೆ ಈ ಸ್ಪೇಸ್ ಬೌಂಡ್ ಅನ್ನು ಬಿಟ್ಗಳಾಗಿ ಸುಧಾರಿಸಬಹುದು ಎಂದು ತೋರಿಸಲಾಯಿತು. ನಂತರದ ಪರಿಹಾರವು ಹೆಚ್ಚಿನ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ಕೆಟ್ಟ-ಸ್ಥಿತಿಯ ಸ್ಥಿರ ಸಮಯದಲ್ಲಿ ಎಲ್ಲಾ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಬೆಂಬಲಿಸುತ್ತದೆ. ಮೊದಲ ಸ್ಥಿರ ಸಂಕ್ಷಿಪ್ತ ಹ್ಯಾಶ್ ಟೇಬಲ್ 1999 ರಲ್ಲಿ ಪಾಗ್ ಕಾರಣವಾಗಿತ್ತು. ಅಂತಹ ಸಂದರ್ಭದಲ್ಲಿ, ಅವರ ಪರಿಹಾರವು ಸ್ಪೇಸ್ ಬಿಟ್ಗಳನ್ನು ಬಳಸುತ್ತದೆ ಮತ್ತು ಕೆಟ್ಟ-ಸಂದರ್ಭದಲ್ಲಿ ಸ್ಥಿರ-ಸಮಯದ ಪ್ರಶ್ನೆಗಳನ್ನು ಬೆಂಬಲಿಸುತ್ತದೆ. ಈ ಬಂಧವನ್ನು ತರುವಾಯ ಬಿಟ್ಗಳಾಗಿ ಮತ್ತು ನಂತರ ಬಿಟ್ಗಳಾಗಿ ಸುಧಾರಿಸಲಾಯಿತು. ಮೊದಲ ಎರಡು ಪರಿಹಾರಗಳು ಕೆಟ್ಟ-ಸಂದರ್ಭದ ಸ್ಥಿರ-ಸಮಯದ ಪ್ರಶ್ನೆಗಳನ್ನು ಬೆಂಬಲಿಸುತ್ತವೆಯಾದರೂ, ಕೊನೆಯದು ನಿರಂತರ ನಿರೀಕ್ಷಿತ-ಸಮಯದ ಪ್ರಶ್ನೆಗಳನ್ನು ಬೆಂಬಲಿಸುತ್ತದೆ. ಅಂತಿಮ ಪರಿಹಾರಕ್ಕೆ ಗಾತ್ರದ ಲುಕ್ಅಪ್ ಟೇಬಲ್ಗೆ ಪ್ರವೇಶದ ಅಗತ್ಯವಿರುತ್ತದೆ, ಆದರೆ ಈ ಲುಕ್ಅಪ್ ಟೇಬಲ್ ಸಂಗ್ರಹಿಸಲಾಗುವ ಅಂಶಗಳ ಗುಂಪಿನಿಂದ ಸ್ವತಂತ್ರವಾಗಿದೆ. ಇತರ ಉದಾಹರಣೆಗಳು ಅನಿಯಂತ್ರಿತ ಉದ್ದ (ಪ್ಯಾಸ್ಕಲ್ ಸ್ಟ್ರಿಂಗ್) ಹೊಂದಿರುವ ಸ್ಟ್ರಿಂಗ್ Z + ಲಾಗ್ (Z) ಜಾಗವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಸಂಕ್ಷಿಪ್ತವಾಗಿರುತ್ತದೆ. ಗರಿಷ್ಠ ಉದ್ದವಿದ್ದರೆ-ಇದು ಆಚರಣೆಯಲ್ಲಿ ಕಂಡುಬಂದರೆ, ಏಕೆಂದರೆ 232 = 4 ಜಿಬಿ ದತ್ತಾಂಶವು ಬಹಳ ಉದ್ದವಾದ ಸ್ಟ್ರಿಂಗ್ ಆಗಿರುತ್ತದೆ, ಮತ್ತು 264 = 16 ಐಬಿ ದತ್ತಾಂಶವು ಆಚರಣೆಯಲ್ಲಿರುವ ಯಾವುದೇ ಸ್ಟ್ರಿಂಗ್ಗಿಂತ ದೊಡ್ಡದಾಗಿದೆ-ಆಗ ಉದ್ದವಿರುವ ಸ್ಟ್ರಿಂಗ್ ಸಹ ಸೂಚ್ಯವಾಗಿರುತ್ತದೆ, ಇದು ಝಡ್ + ಕೆ ಜಾಗವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಅಲ್ಲಿ ಕೆ ಗರಿಷ್ಠ ಉದ್ದವನ್ನು ಪ್ರತಿನಿಧಿಸುವ ದತ್ತಾಂಶದ ಸಂಖ್ಯೆ (ಉದಾಹರಣೆಗೆ, 64 ಬಿಟ್ಗಳು). ವೇರಿಯೇಬಲ್-ಉದ್ದದ ವಸ್ತುಗಳ ಅನುಕ್ರಮವನ್ನು (ಸ್ಟ್ರಿಂಗ್ಗಳಂತಹ) ಎನ್ಕೋಡ್ ಮಾಡಬೇಕಾದರೆ, ವಿವಿಧ ಸಾಧ್ಯತೆಗಳಿವೆ. ಪ್ರತಿ ದಾಖಲೆಯಲ್ಲಿ ಒಂದು ಉದ್ದ ಮತ್ತು ಒಂದು ವಸ್ತುವನ್ನು ಸಂಗ್ರಹಿಸುವುದು ನೇರವಾದ ವಿಧಾನವಾಗಿದೆ-ಇವುಗಳನ್ನು ನಂತರ ಒಂದರ ನಂತರ ಒಂದರಂತೆ ಇರಿಸಬಹುದು. ಇದು ಸಮರ್ಥವಾದ ಮುಂದಿನದನ್ನು ಅನುಮತಿಸುತ್ತದೆ, ಆದರೆ kth ಐಟಂ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವುದಿಲ್ಲ. ಪರ್ಯಾಯವೆಂದರೆ ವಸ್ತುಗಳನ್ನು ಡಿಲಿಮಿಟರ್ನೊಂದಿಗೆ ಕ್ರಮದಲ್ಲಿ ಇಡುವುದು (ಉದಾಹರಣೆಗೆ, ಶೂನ್ಯ-ಕೊನೆಗೊಂಡ ಸ್ಟ್ರಿಂಗ್). ಇದು ಉದ್ದದ ಬದಲು ಡಿಲಿಮಿಟರ್ ಅನ್ನು ಬಳಸುತ್ತದೆ ಮತ್ತು ಗಣನೀಯವಾಗಿ ನಿಧಾನವಾಗಿರುತ್ತದೆ, ಏಕೆಂದರೆ ಸಂಪೂರ್ಣ ಅನುಕ್ರಮವನ್ನು ಡಿಲಿಮಿಟರ್ಗಳಿಗಾಗಿ ಸ್ಕ್ಯಾನ್ ಮಾಡಬೇಕು. ಇವೆರಡೂ ಬಾಹ್ಯಾಕಾಶ ದಕ್ಷತೆ ಹೊಂದಿವೆ. ಬ್ಯಾಂಡ್ನ ಹೊರಗೆ ಬೇರ್ಪಡಿಸುವಿಕೆಯು ಒಂದು ಪರ್ಯಾಯ ವಿಧಾನವಾಗಿದೆಃ ಯಾವುದೇ ಡಿಲಿಮಿಟರ್ಗಳಿಲ್ಲದೆ ವಸ್ತುಗಳನ್ನು ಒಂದರ ನಂತರ ಒಂದರಂತೆ ಇರಿಸಬಹುದು. ಐಟಂ ಬೌಂಡರಿಗಳನ್ನು ನಂತರ ಉದ್ದದ ಅನುಕ್ರಮವಾಗಿ ಸಂಗ್ರಹಿಸಬಹುದು, ಅಥವಾ ಈ ಅನುಕ್ರಮಕ್ಕೆ ಉತ್ತಮವಾದ ಆಫ್ಸೆಟ್ಗಳನ್ನು ಮಾಡಬಹುದು. ಪರ್ಯಾಯವಾಗಿ, ಒಂದು ವಸ್ತುವು ಪ್ರಾರಂಭವಾಗುವ ಸ್ಥಾನಗಳಲ್ಲಿ 1s ಅನ್ನು ಒಳಗೊಂಡಿರುವ ಪ್ರತ್ಯೇಕ ಬೈನರಿ ಸ್ಟ್ರಿಂಗ್, ಮತ್ತು ಎಲ್ಲೆಡೆ 0s ಅನ್ನು ಅದರೊಂದಿಗೆ ಎನ್ಕೋಡ್ ಮಾಡಲಾಗುತ್ತದೆ. ಈ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ನೀಡಿದರೆ, ಅದರ ಸೂಚ್ಯಂಕವನ್ನು ನೀಡಿದರೆ, ಪ್ರತಿಯೊಂದು ವಸ್ತುವು ಎಲ್ಲಿಂದ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ ಎಂಬುದನ್ನು ಕಾರ್ಯವು ತ್ವರಿತವಾಗಿ ನಿರ್ಧರಿಸಬಹುದು. ಇದು ಸಾಂದ್ರವಾಗಿದೆ ಆದರೆ ಸಂಕ್ಷಿಪ್ತವಾಗಿಲ್ಲ, ಏಕೆಂದರೆ ಇದು 2Z ಜಾಗವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಇದು O (Z) ಆಗಿದೆ. ಮತ್ತೊಂದು ಉದಾಹರಣೆಯೆಂದರೆ ಬೈನರಿ ಮರದ ಪ್ರಾತಿನಿಧ್ಯಃ ಯಾವುದೇ ನೋಡ್ನಲ್ಲಿ ವಿವಿಧ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಬೆಂಬಲಿಸುವಾಗ ನೋಡ್ಗಳ ಮೇಲಿನ ಅನಿಯಂತ್ರಿತ ಬೈನರಿ ಮರವನ್ನು ಬಿಟ್ಗಳಲ್ಲಿ ಪ್ರತಿನಿಧಿಸಬಹುದು, ಇದರಲ್ಲಿ ಅದರ ಮೂಲ, ಅದರ ಎಡ ಮತ್ತು ಬಲ ಚೈಲ್ಡ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಮತ್ತು ಅದರ ಸಬ್ಟ್ರೀಯ ಗಾತ್ರವನ್ನು ಹಿಂದಿರುಗಿಸುವುದು, ಪ್ರತಿಯೊಂದೂ ಸ್ಥಿರ ಸಮಯದಲ್ಲಿ. ನೋಡ್ಗಳ ಮೇಲೆ ವಿವಿಧ ಬೈನರಿ ಮರಗಳ ಸಂಖ್ಯೆ. ದೊಡ್ಡದಾದರೆ, ಇದು ಸುಮಾರು; ಆದ್ದರಿಂದ ಅದನ್ನು ಎನ್ಕೋಡ್ ಮಾಡಲು ನಮಗೆ ಕನಿಷ್ಠ ಬಿಟ್ಗಳ ಅಗತ್ಯವಿರುತ್ತದೆ. ಆದ್ದರಿಂದ ಒಂದು ಸಂಕ್ಷಿಪ್ತ ದ್ವಿಮಾನ ಮರವು ಪ್ರತಿ ನೋಡ್ಗೆ ಬಿಟ್ಗಳನ್ನು ಮಾತ್ರ ಆಕ್ರಮಿಸುತ್ತದೆ. ಮಿನಿಮಲ್ ಪರ್ಫೆಕ್ಟ್ ಹ್ಯಾಶ್ ಫಂಕ್ಷನ್ ಸಕ್ಸಿಂಕ್ಟ್ ನಾನ್-ಇಂಟರಾಕ್ಟಿವ್ ಆರ್ಗ್ಯುಮೆಂಟ್ಸ್ ಆಫ್ ನಾಲೆಡ್ಜ್ ರೆಫೆರೆನ್ಸ್ಗಳನ್ನು ಸಹ ನೋಡಿ.