Closest string
ಸೈದ್ಧಾಂತಿಕ ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ಹತ್ತಿರದ ಸ್ಟ್ರಿಂಗ್ ಎನ್ಪಿ-ಹಾರ್ಡ್ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಮಸ್ಯೆಯಾಗಿದೆ, ಇದು ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ಗಳ ಗುಂಪಿನ ಜ್ಯಾಮಿತೀಯ ಕೇಂದ್ರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಪ್ರಯತ್ನಿಸುತ್ತದೆ. "ಸೆಂಟರ್" ಎಂಬ ಪದವನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳಲು, ಎರಡು ತಂತಿಗಳ ನಡುವಿನ ಅಂತರವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುವುದು ಅವಶ್ಯಕವಾಗಿದೆ. ಸಾಮಾನ್ಯವಾಗಿ, ಈ ಸಮಸ್ಯೆಯನ್ನು ಹ್ಯಾಮಿಂಗ್ ಅಂತರವನ್ನು ಗಮನದಲ್ಲಿಟ್ಟುಕೊಂಡು ಅಧ್ಯಯನ ಮಾಡಲಾಗುತ್ತದೆ. ಔಪಚಾರಿಕ ವ್ಯಾಖ್ಯಾನ ಹೆಚ್ಚು ಔಪಚಾರಿಕವಾಗಿ, n ಉದ್ದ-m ತಂತಿಗಳು s1, s2,., sn ಅನ್ನು ನೀಡಿದರೆ, ಹತ್ತಿರದ ಸ್ಟ್ರಿಂಗ್ ಸಮಸ್ಯೆಯು ಹೊಸ ಉದ್ದ-m ಸ್ಟ್ರಿಂಗ್ s ಅನ್ನು ಹುಡುಕುತ್ತದೆ, ಅಂದರೆ ಎಲ್ಲಾ i ಗೆ d (s, si) ≤ k, ಅಲ್ಲಿ d ಹ್ಯಾಮಿಂಗ್ ದೂರವನ್ನು ಸೂಚಿಸುತ್ತದೆ, ಮತ್ತು ಅಲ್ಲಿ k ಸಾಧ್ಯವಾದಷ್ಟು ಚಿಕ್ಕದಾಗಿದೆ. NP-ಕಂಪ್ಲೀಟ್ ಆಗಿರುವ ಹತ್ತಿರದ ಸ್ಟ್ರಿಂಗ್ ಸಮಸ್ಯೆಯ ನಿರ್ಧಾರ ಸಮಸ್ಯೆಯ ಆವೃತ್ತಿಯು, ಬದಲಿಗೆ k ಅನ್ನು ಮತ್ತೊಂದು ಇನ್ಪುಟ್ ಆಗಿ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಮತ್ತು ಎಲ್ಲಾ ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ಗಳ ಹ್ಯಾಮಿಂಗ್ ದೂರ k ಒಳಗೆ ಸ್ಟ್ರಿಂಗ್ ಇದೆಯೇ ಎಂದು ಪ್ರಶ್ನಿಸುತ್ತದೆ. ಹತ್ತಿರದ ಸ್ಟ್ರಿಂಗ್ ಸಮಸ್ಯೆಯನ್ನು ಸಾಮಾನ್ಯ 1-ಕೇಂದ್ರ ಸಮಸ್ಯೆಯ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿ ಕಾಣಬಹುದು, ಇದರಲ್ಲಿ ಅಂಶಗಳ ನಡುವಿನ ಅಂತರವನ್ನು ಹ್ಯಾಮಿಂಗ್ ದೂರವನ್ನು ಬಳಸಿಕೊಂಡು ಅಳೆಯಲಾಗುತ್ತದೆ. ಬಯೋಇನ್ಫರ್ಮ್ಯಾಟಿಕ್ಸ್ನಲ್ಲಿ, ಹತ್ತಿರದ ಸ್ಟ್ರಿಂಗ್ ಸಮಸ್ಯೆಯು ಡಿಎನ್ಎಯಲ್ಲಿ ಸಂಕೇತಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವ ಸಮಸ್ಯೆಯ ತೀವ್ರವಾಗಿ ಅಧ್ಯಯನ ಮಾಡಿದ ಅಂಶವಾಗಿದೆ. ಸರಳೀಕರಣಗಳು ಮತ್ತು ದತ್ತಾಂಶ ಕಡಿತಗಳು ಹತ್ತಿರದ ಸ್ಟ್ರಿಂಗ್ನ ನಿದರ್ಶನಗಳು ಸಮಸ್ಯೆಗೆ ಅನಿವಾರ್ಯವಲ್ಲದ ಮಾಹಿತಿಯನ್ನು ಹೊಂದಿರಬಹುದು. ಕೆಲವು ಅರ್ಥದಲ್ಲಿ, ಹತ್ತಿರದ ಸ್ಟ್ರಿಂಗ್ನ ಸಾಮಾನ್ಯ ಇನ್ಪುಟ್ ಮಾಹಿತಿಯನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಅದು ಸಮಸ್ಯೆಯ ಗಡಸುತನಕ್ಕೆ ಕಾರಣವಾಗುವುದಿಲ್ಲ. ಉದಾಹರಣೆಗೆ, ಕೆಲವು ತಂತಿಗಳು a ಅಕ್ಷರವನ್ನು ಹೊಂದಿದ್ದರೆ, ಆದರೆ ಯಾವುದೂ z ಅಕ್ಷರವನ್ನು ಹೊಂದಿಲ್ಲದಿದ್ದರೆ, ಎಲ್ಲವನ್ನೂ zs ನೊಂದಿಗೆ ಬದಲಾಯಿಸುವುದರಿಂದ ಮೂಲಭೂತವಾಗಿ ಸಮಾನವಾದ ಉದಾಹರಣೆಯನ್ನು ನೀಡುತ್ತದೆ, ಅಂದರೆಃ ಮಾರ್ಪಡಿಸಿದ ನಿದರ್ಶನದ ಪರಿಹಾರದಿಂದ, ಮೂಲ ಪರಿಹಾರವನ್ನು ಪುನಃಸ್ಥಾಪಿಸಬಹುದು, ಮತ್ತು ಪ್ರತಿಯಾಗಿ. ಇನ್ಪುಟ್ ಅನ್ನು ಸಾಮಾನ್ಯಗೊಳಿಸುವುದು ಒಂದೇ ಉದ್ದವನ್ನು ಹಂಚಿಕೊಳ್ಳುವ ಎಲ್ಲಾ ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ಗಳನ್ನು ಪರಸ್ಪರರ ಮೇಲೆ ಬರೆಯುವಾಗ, ಅವು ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ರೂಪಿಸುತ್ತವೆ. ಕೆಲವು ಸಾಲಿನ ಪ್ರಕಾರಗಳು ಪರಿಹಾರಕ್ಕೆ ಮೂಲಭೂತವಾಗಿ ಒಂದೇ ರೀತಿಯ ಪರಿಣಾಮಗಳನ್ನು ಹೊಂದಿವೆ. ಉದಾಹರಣೆಗೆ, ಒಂದು ಅಂಕಣವನ್ನು ನಮೂದುಗಳೊಂದಿಗೆ (a, a, b) ಮತ್ತೊಂದು ಅಂಕಣದೊಂದಿಗೆ (x, x, y) ಬದಲಾಯಿಸುವುದರಿಂದ ಬೇರೆ ಪರಿಹಾರ ಸ್ಟ್ರಿಂಗ್ಗೆ ಕಾರಣವಾಗಬಹುದು, ಆದರೆ ಪರಿಹಾರದ ಮೇಲೆ ಪರಿಣಾಮ ಬೀರುವುದಿಲ್ಲ, ಏಕೆಂದರೆ ಎರಡೂ ಅಂಕಣಗಳು ಒಂದೇ ರಚನೆಯನ್ನು ವ್ಯಕ್ತಪಡಿಸುತ್ತವೆ, ಅಂದರೆ. ಮೊದಲ ಎರಡು ನಮೂದುಗಳು ಸಮಾನವಾಗಿವೆ, ಆದರೆ ಮೂರನೆಯದಕ್ಕಿಂತ ಭಿನ್ನವಾಗಿವೆ. ಪ್ರತಿ ಅಂಕಣದಲ್ಲಿ, ಹೆಚ್ಚಾಗಿ ಸಂಭವಿಸುವ ಅಕ್ಷರವನ್ನು a ಯೊಂದಿಗೆ, ಎರಡನೆಯದಾಗಿ ಹೆಚ್ಚಾಗಿ ಸಂಭವಿಸುವ ಅಕ್ಷರವನ್ನು b ಯೊಂದಿಗೆ ಬದಲಾಯಿಸುವ ಮೂಲಕ ಇನ್ಪುಟ್ ನಿದರ್ಶನವನ್ನು ಸಾಮಾನ್ಯಗೊಳಿಸಬಹುದು. ಸಾಮಾನ್ಯೀಕೃತ ನಿದರ್ಶನಕ್ಕೆ ಪರಿಹಾರವನ್ನು ನೀಡಿದರೆ, ಪ್ರತಿ ಅಂಕಣದಲ್ಲಿ ಪರಿಹಾರದ ಅಕ್ಷರಗಳನ್ನು ಅದರ ಮೂಲ ಆವೃತ್ತಿಗೆ ಮರುರೂಪಿಸುವ ಮೂಲಕ ಮೂಲ ನಿದರ್ಶನವನ್ನು ಕಾಣಬಹುದು. ಕಾಲಮ್ಗಳ ಕ್ರಮವು ಸಮಸ್ಯೆಯ ಗಡಸುತನಕ್ಕೆ ಕೊಡುಗೆ ನೀಡುವುದಿಲ್ಲ. ಅಂದರೆ, ನಾವು ಒಂದು ನಿರ್ದಿಷ್ಟ ಕ್ರಮಪಲ್ಲಟನೆಯ ಪ್ರಕಾರ ಎಲ್ಲಾ ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ಗಳನ್ನು ಕ್ರಮಪಲ್ಲಟಗೊಳಿಸಿದರೆ ಮತ್ತು ಆ ಮಾರ್ಪಡಿಸಿದ ನಿದರ್ಶನಕ್ಕೆ ಪರಿಹಾರ ಸ್ಟ್ರಿಂಗ್ s ಅನ್ನು ಪಡೆದರೆ, π−1 (s) ಮೂಲ ನಿದರ್ಶನಕ್ಕೆ ಪರಿಹಾರವಾಗಿರುತ್ತದೆ. ಉದಾಹರಣೆ ಮೂರು ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ಗಳಾದ uvwx, xuwv, ಮತ್ತು xvwu ಹೊಂದಿರುವ ಉದಾಹರಣೆಯನ್ನು ನೀಡಲಾಗಿದೆ. ಇದನ್ನು ಈ ರೀತಿಯ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಎಂದು ಬರೆಯಬಹುದುಃ ಮೊದಲ ಅಂಕಣವು (u, x, x) ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿದೆ. x ಎಂಬುದು ಹೆಚ್ಚಾಗಿ ಕಾಣಿಸಿಕೊಳ್ಳುವ ಅಕ್ಷರವಾಗಿರುವುದರಿಂದ, ನಾವು ಅದನ್ನು a ನಿಂದ ಬದಲಾಯಿಸುತ್ತೇವೆ ಮತ್ತು ನಾವು ಎರಡನೇ ಅಕ್ಷರವಾದ u ಅನ್ನು b ನಿಂದ ಬದಲಾಯಿಸುತ್ತೇವೆ, ಹೊಸ ಮೊದಲ ಅಂಕಣವನ್ನು (b, a, a) ಪಡೆಯುತ್ತೇವೆ. ಎರಡನೇ ಅಂಕಣವು (v, u, v) ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿದೆ. ಮೊದಲ ಅಂಕಣಕ್ಕೆ ಸಂಬಂಧಿಸಿದಂತೆ, v ಅನ್ನು a ನಿಂದ ಬದಲಾಯಿಸಲಾಗುತ್ತದೆ ಮತ್ತು u ಅನ್ನು b ನಿಂದ ಬದಲಾಯಿಸಲಾಗುತ್ತದೆ, ಇದು ಹೊಸ ಎರಡನೇ ಅಂಕಣವನ್ನು (a, b, a) ಪಡೆಯುತ್ತದೆ. ಎಲ್ಲಾ ಕಾಲಮ್ಗಳೊಂದಿಗೆ ಇದೇ ರೀತಿ ಮಾಡುವುದರಿಂದ ಸಾಮಾನ್ಯೀಕರಣದಿಂದ ಪಡೆದ ಡೇಟಾ ಕಡಿತವನ್ನು ನೀಡುತ್ತದೆ ಇನ್ಪುಟ್ ಅನ್ನು ಸಾಮಾನ್ಯಗೊಳಿಸುವುದರಿಂದ ವರ್ಣಮಾಲೆಯ ಗಾತ್ರವನ್ನು ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ಗಳ ಸಂಖ್ಯೆಗೆ ಕಡಿಮೆ ಮಾಡುತ್ತದೆ. ವರ್ಣಮಾಲೆಯ ಗಾತ್ರವನ್ನು ಅವಲಂಬಿಸಿರುವ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯದ ಕ್ರಮಾವಳಿಗಳಿಗೆ ಇದು ಉಪಯುಕ್ತವಾಗಿದೆ. ಅಂದಾಜು Li ಮತ್ತು ಇತರರು. ದೊಡ್ಡ ಗುಪ್ತ ಸ್ಥಿರಾಂಕಗಳ ಕಾರಣದಿಂದಾಗಿ ಪ್ರಾಯೋಗಿಕವಾಗಿ ನಿಷ್ಪ್ರಯೋಜಕವಾಗಿರುವ ಬಹುಪದ-ಸಮಯದ ಅಂದಾಜು ಯೋಜನೆಯನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸಲಾಗಿದೆ. ಸ್ಥಿರ-ನಿಯತಾಂಕ ಟ್ರ್ಯಾಕ್ಟಬಿಲಿಟಿ ಹತ್ತಿರದ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಇಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು, ಅಲ್ಲಿ k ಎಂಬುದು ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ಗಳ ಸಂಖ್ಯೆ, L ಎಂಬುದು ಎಲ್ಲಾ ಸ್ಟ್ರಿಂಗ್ಗಳ ಉದ್ದ ಮತ್ತು d ಎಂಬುದು ಪರಿಹಾರ ಸ್ಟ್ರಿಂಗ್ನಿಂದ ಯಾವುದೇ ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ಗೆ ಅಪೇಕ್ಷಿತ ಗರಿಷ್ಠ ದೂರವಾಗಿದೆ. ಇತರ ಸಮಸ್ಯೆಗಳೊಂದಿಗಿನ ಸಂಬಂಧಗಳು ಹತ್ತಿರದ ಸ್ಟ್ರಿಂಗ್ ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾದ ಹತ್ತಿರದ ಸಬ್ಸ್ಟ್ರಿಂಗ್ ಸಮಸ್ಯೆಯ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿದೆ, ಇದು ಕಟ್ಟುನಿಟ್ಟಾಗಿ ಹೆಚ್ಚು ಕಷ್ಟಕರವಾಗಿದೆ. ಹತ್ತಿರದ ಸ್ಟ್ರಿಂಗ್ ಹಲವಾರು ರೀತಿಯಲ್ಲಿ ಸ್ಥಿರ-ನಿಯತಾಂಕವನ್ನು ಸಾಗಿಸಬಹುದಾದರೂ, ಈ ನಿಯತಾಂಕಗಳಿಗೆ ಸಂಬಂಧಿಸಿದಂತೆ ಹತ್ತಿರದ ಸಬ್ಸ್ಟ್ರಿಂಗ್ W [1]-ಗಟ್ಟಿಯಾಗಿರುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು ಎನ್. ಪಿ.-ಕಠಿಣ ಸಮಸ್ಯೆಗಳು ಔಪಚಾರಿಕ ಭಾಷೆಗಳು