Deterministic acyclic finite state automaton
ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ಡಿಟೆರ್ಮಿನಿಸ್ಟಿಕ್ ಅಸೈಕ್ಲಿಕ್ ಫೈನೈಟ್ ಸ್ಟೇಟ್ ಆಟೊಮ್ಯಾಟನ್ (ಡಿಎಎಫ್ಎಸ್ಎ), ಇದನ್ನು ಡೈರೆಕ್ಟೆಡ್ ಅಸೈಕ್ಲಿಕ್ ವರ್ಡ್ ಗ್ರಾಫ್ (ಡಿಎಡಬ್ಲ್ಯೂಜಿ) ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ; ಆದರೂ ಆ ಹೆಸರು ಪ್ರತ್ಯಯ ಸೂಚ್ಯಂಕವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುವ ಸಂಬಂಧಿತ ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ಸಹ ಉಲ್ಲೇಖಿಸುತ್ತದೆ) ಇದು ತಂತಿಗಳ ಗುಂಪನ್ನು ಪ್ರತಿನಿಧಿಸುವ ದತ್ತಾಂಶ ರಚನೆಯಾಗಿದೆ ಮತ್ತು ನಿರ್ದಿಷ್ಟ ಸ್ಟ್ರಿಂಗ್ ಅದರ ಉದ್ದಕ್ಕೆ ಅನುಪಾತದಲ್ಲಿರುವ ಸಮಯಕ್ಕೆ ಸೇರಿದೆಯೇ ಎಂದು ಪರೀಕ್ಷಿಸುವ ಪ್ರಶ್ನೆಯ ಕಾರ್ಯಾಚರಣೆಗೆ ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಅಂತಹ ಆಟೋಮ್ಯಾಟಾವನ್ನು ನಿರ್ಮಿಸಲು ಮತ್ತು ನಿರ್ವಹಿಸಲು ಅಲ್ಗಾರಿದಮ್ಗಳು ಅಸ್ತಿತ್ವದಲ್ಲಿವೆ, ಆದರೆ ಅವುಗಳನ್ನು ಕನಿಷ್ಠವಾಗಿರಿಸುತ್ತವೆ. ಡಿಎಎಫ್ಎಸ್ಎ ಎನ್ನುವುದು ಸೀಮಿತ ಸ್ಥಿತಿಯ ಗುರುತಿಸುವಿಕೆಯ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿದ್ದು, ಇದು ಒಂದೇ ಮೂಲ ಶೃಂಗದೊಂದಿಗೆ (ಒಳಬರುವ ಅಂಚುಗಳಿಲ್ಲದ ಶೃಂಗ) ನಿರ್ದೇಶಿತ ಅಸೈಕ್ಲಿಕ್ ಗ್ರಾಫ್ನ ರೂಪವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಇದರಲ್ಲಿ ಗ್ರಾಫ್ನ ಪ್ರತಿಯೊಂದು ತುದಿಯನ್ನು ಅಕ್ಷರ ಅಥವಾ ಚಿಹ್ನೆಯಿಂದ ಲೇಬಲ್ ಮಾಡಲಾಗುತ್ತದೆ, ಮತ್ತು ಇದರಲ್ಲಿ ಪ್ರತಿ ಶೃಂಗವು ಪ್ರತಿ ಸಂಭವನೀಯ ಅಕ್ಷರ ಅಥವಾ ಚಿಹ್ನೆಗೆ ಗರಿಷ್ಠ ಒಂದು ಹೊರಹೋಗುವ ಅಂಚನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಡಿಎಎಫ್ಎಸ್ಎ ಪ್ರತಿನಿಧಿಸುವ ತಂತಿಗಳು ಮೂಲ ಶೃಂಗದಿಂದ ಯಾವುದೇ ಸಿಂಕ್ ಶೃಂಗಕ್ಕೆ (ಹೊರಹೋಗುವ ಅಂಚುಗಳಿಲ್ಲದ ಶೃಂಗ) ಗ್ರಾಫ್ನಲ್ಲಿರುವ ಮಾರ್ಗಗಳಲ್ಲಿನ ಚಿಹ್ನೆಗಳಿಂದ ರೂಪುಗೊಳ್ಳುತ್ತವೆ. ವಾಸ್ತವವಾಗಿ, ಒಂದು ನಿರ್ಣಾಯಕ ಸೀಮಿತ ಸ್ಥಿತಿಯ ಸ್ವಯಂಚಾಲಿತ ಯಂತ್ರವು ಒಂದು ಸೀಮಿತ ತಂತಿಗಳ ಗುಂಪನ್ನು ಗುರುತಿಸಿದರೆ ಮಾತ್ರ ಅದು ಅಸೈಕ್ಲಿಕ್ ಆಗಿರುತ್ತದೆ. ಒಂದೇ ಶೃಂಗಗಳನ್ನು ಅನೇಕ ಮಾರ್ಗಗಳಿಂದ ತಲುಪಲು ಅನುಮತಿಸುವ ಮೂಲಕ, ಡಿಎಎಫ್ಎಸ್ಎ ಬಲವಾಗಿ ಸಂಬಂಧಿಸಿದ ಟ್ರೈ ಡೇಟಾ ರಚನೆಗಿಂತ ಗಮನಾರ್ಹವಾಗಿ ಕಡಿಮೆ ಶೃಂಗಗಳನ್ನು ಬಳಸಬಹುದು. ಉದಾಹರಣೆಗೆ, "ಟ್ಯಾಪ್", "ಟ್ಯಾಪ್ಸ್", "ಟಾಪ್" ಮತ್ತು "ಟಾಪ್ಸ್" ಎಂಬ ನಾಲ್ಕು ಇಂಗ್ಲಿಷ್ ಪದಗಳನ್ನು ಪರಿಗಣಿಸಿ. ಆ ನಾಲ್ಕು ಪದಗಳಿಗೆ ಒಂದು ಟ್ರೈ 12 ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಈ ಪದಗಳಲ್ಲಿ ಒಂದರ ಪೂರ್ವಪ್ರತ್ಯಯವಾಗಿ ರೂಪುಗೊಂಡ ಪ್ರತಿಯೊಂದು ಸ್ಟ್ರಿಂಗ್ಗೆ ಒಂದು, ಅಥವಾ ಸ್ಟ್ರಿಂಗ್ ಮಾರ್ಕರ್ನ ಅಂತ್ಯವನ್ನು ಅನುಸರಿಸುವ ಪದಗಳಲ್ಲಿ ಒಂದಕ್ಕೆ. ಆದಾಗ್ಯೂ, ಒಂದು ಡಿಎಎಫ್ಎಸ್ಎ ಕೇವಲ ಆರು ಶೃಂಗಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಅದೇ ನಾಲ್ಕು ಪದಗಳನ್ನು ಪ್ರತಿನಿಧಿಸಬಹುದು, ಅಂದರೆ 0 ≤ i ≤ 5, ಮತ್ತು ಈ ಕೆಳಗಿನ ಅಂಚುಗಳನ್ನುಃ "t" ಎಂದು ಲೇಬಲ್ ಮಾಡಲಾದ v0 ನಿಂದ v1 ವರೆಗಿನ ಅಂಚು, "a" ಮತ್ತು "o" ಎಂದು ಲೇಬಲ್ ಮಾಡಲಾದ v1 ನಿಂದ v2ವರೆಗಿನ ಎರಡು ಅಂಚುಗಳು, "p" ಎಂದು ಲೇಬಲ್ ಮಾಡಲಾದ v2 ನಿಂದ v3ವರೆಗಿನ ಅಂಚು, "s" ಎಂದು ಲೇಬಲ್ ಮಾಡಲಾದ ಅಂಚು v3 ರಿಂದ v4ವರೆಗಿನ ಅಂಚುಗಳು, ಮತ್ತು ಸ್ಟ್ರಿಂಗ್ ಮಾರ್ಕರ್ನ ಅಂತ್ಯದೊಂದಿಗೆ ಲೇಬಲ್ ಮಾಡಲಾದ v3 ಮತ್ತು v4 ರಿಂದ v5ವರೆಗಿನ ಅಂಚುಗಳು. ಮೆಮೊರಿ ಮತ್ತು ಕ್ರಿಯಾತ್ಮಕತೆಯ ನಡುವೆ ಹೊಂದಾಣಿಕೆ ಇದೆ, ಏಕೆಂದರೆ ಪ್ರಮಾಣಿತ ಡಿಎಎಫ್ಎಸ್ಎ ಅದರೊಳಗೆ ಒಂದು ಪದವಿದೆಯೇ ಎಂದು ನಿಮಗೆ ಹೇಳಬಹುದು, ಆದರೆ ಅದು ಆ ಪದದ ಬಗ್ಗೆ ಸಹಾಯಕ ಮಾಹಿತಿಯನ್ನು ಸೂಚಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ, ಆದರೆ ಟ್ರೈ ಮಾಡಬಹುದು. ಡಿಎಎಫ್ಎಸ್ಎ ಮತ್ತು ಟ್ರೈ ನಡುವಿನ ಪ್ರಾಥಮಿಕ ವ್ಯತ್ಯಾಸವೆಂದರೆ ತಂತಿಗಳನ್ನು ಸಂಗ್ರಹಿಸುವಲ್ಲಿ ಪ್ರತ್ಯಯ ಮತ್ತು ಇನ್ಫಿಕ್ಸ್ ಪುನರುಕ್ತಿಗಳನ್ನು ತೆಗೆದುಹಾಕುವುದು. ಎಲ್ಲಾ ಸಾಮಾನ್ಯ ಪೂರ್ವಪ್ರತ್ಯಯಗಳನ್ನು ತಂತಿಗಳ ನಡುವೆ ಹಂಚಿಕೊಳ್ಳುವುದರಿಂದ ಟ್ರೈ ಪೂರ್ವಪ್ರತ್ಯಯ ಪುನರುಕ್ತಿಗಳನ್ನು ತೆಗೆದುಹಾಕುತ್ತದೆ, ಉದಾಹರಣೆಗೆ ವೈದ್ಯರು ಮತ್ತು ಡಾಕ್ಟರೇಟ್ ನಡುವೆ ವೈದ್ಯರ ಪೂರ್ವಪ್ರತ್ಯಯವನ್ನು ಹಂಚಿಕೊಳ್ಳಲಾಗುತ್ತದೆ. ಡಿಎಎಫ್ಎಸ್ಎಯಲ್ಲಿ ಸಾಮಾನ್ಯ ಪ್ರತ್ಯಯಗಳನ್ನು ಸಹ ಹಂಚಿಕೊಳ್ಳಲಾಗುತ್ತದೆ, ಪರಸ್ಪರ ಸಂಭವನೀಯ ಪ್ರತ್ಯಯಗಳ ಒಂದೇ ಗುಂಪನ್ನು ಹೊಂದಿರುವ ಪದಗಳಿಗೆ. ಸಾಮಾನ್ಯ ಇಂಗ್ಲಿಷ್ ಪದಗಳ ನಿಘಂಟಿನ ಸೆಟ್ಗಳಿಗೆ, ಇದು ಪ್ರಮುಖ ಮೆಮೊರಿ ಬಳಕೆಯ ಕಡಿತಕ್ಕೆ ಅನುವಾದಿಸುತ್ತದೆ. ಡಿಎಎಫ್ಎಸ್ಎಯ ಅಂತಿಮ ನೋಡ್ಗಳನ್ನು ಅನೇಕ ಮಾರ್ಗಗಳ ಮೂಲಕ ತಲುಪಬಹುದಾದ್ದರಿಂದ, ಡಿಎಎಫ್ಎಸ್ಎ ಪ್ರತಿ ಮಾರ್ಗಕ್ಕೆ ಸಂಬಂಧಿಸಿದ ಸಹಾಯಕ ಮಾಹಿತಿಯನ್ನು ನೇರವಾಗಿ ಸಂಗ್ರಹಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ, ಉದಾಹರಣೆಗೆ. ಇಂಗ್ಲಿಷ್ ಭಾಷೆಯಲ್ಲಿ ಪದದ ಆವರ್ತನ. ಆದಾಗ್ಯೂ, ಪ್ರತಿ ನೋಡ್ಗೆ ನಾವು ರಚನೆಯ ಆ ಬಿಂದುವಿನ ಮೂಲಕ ಅನನ್ಯ ಮಾರ್ಗಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸಂಗ್ರಹಿಸಿದರೆ, ಪದದ ಸೂಚ್ಯಂಕವನ್ನು ಅಥವಾ ಅದರ ಸೂಚ್ಯಂಕವನ್ನು ನೀಡಲಾದ ಪದವನ್ನು ಹಿಂಪಡೆಯಲು ನಾವು ಅದನ್ನು ಬಳಸಬಹುದು. ಸಹಾಯಕ ಮಾಹಿತಿಯನ್ನು ನಂತರ ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ಸಂಗ್ರಹಿಸಬಹುದು. ಉಲ್ಲೇಖಗಳು. ದತ್ತಾಂಶ ರಚನೆಯ ಆರಂಭಿಕ ಉಲ್ಲೇಖಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ. .. ಓಪನ್ ಸೋರ್ಸ್ ಪೈಥಾನ್ ಅನುಷ್ಠಾನ. ಬಾಹ್ಯ ಕೊಂಡಿಗಳು "ಡೈರೆಕ್ಟೆಡ್ ಅಸೈಕ್ಲಿಕ್ ವರ್ಡ್ ಗ್ರಾಫ್ ಅಥವಾ ಡಿಎಡಬ್ಲ್ಯೂಜಿ"-ಜಾನ್ ಪಾಲ್ ಆಡಮೋವ್ಸ್ಕಿ ಪೂರ್ಣಾಂಕಗಳ ಶ್ರೇಣಿಯನ್ನು ಬಳಸಿಕೊಂಡು ಡಿಎಎಫ್ಎಸ್ಎ ಅನ್ನು ಹೇಗೆ ನಿರ್ಮಿಸಬೇಕೆಂದು ಕಲಿಸುತ್ತಾರೆ () "ಕ್ಯಾರೋಲಿನ್ ವರ್ಡ್ ಗ್ರಾಫ್ ಅಥವಾ ಸಿಡಬ್ಲ್ಯೂಜಿ"-ಜಾನ್ ಪಾಲ್ ಆಡಮೋವ್ಸ್ಕಿ ಅನೇಕ ಪೂರ್ಣಾಂಕ ಸರಣಿಗಳೊಂದಿಗೆ ಹೊಸ ಎನ್ಕೋಡಿಂಗ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಡಿಎಎಫ್ಎಸ್ಎ ಹ್ಯಾಶ್ ಕಾರ್ಯವನ್ನು ಹೇಗೆ ನಿರ್ಮಿಸಬೇಕೆಂದು ಕಲಿಸುತ್ತಾರೆ () ಗ್ರಾಫ್ ಡೇಟಾ ಸ್ಟ್ರಕ್ಚರ್ಗಳು ಸ್ಟ್ರಿಂಗ್ ಡೇಟಾ ಸ್ಟ್ರಕ್ಚರ್ಗಳು ಫೈನೈಟ್ ಆಟೋಮ್ಯಾಟಾ