Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Жолдарды салыстырудың математикалық моделі
Компьютер ғылымында, w жолы және n саны үшін Левенштейн автоматы – бұл w-ға қатысты Левенштейн қашықтығы n-нен аспайтын барлық жолдар жиынын танитын шекті күйдегі автомат. Яғни, x жолы Левенштейн автоматы танитын формальді тілге кіреді, егер және тек қана егер x жолын ең көп дегенде n бір символдық қосылу, жою және алмастыру арқылы w жолына түрлендіруге болады.
Mathematical model for string comparison
In computer science, a Levenshtein automaton for a string w and a number n is a finite state automaton that can recognize the set of all strings whose Levenshtein distance from w is at most n. That is, a string x is in the formal language recognized by the Levenshtein automaton if and only if x can be transformed into w by at most n single character insertions, deletions, and substitutions.
Қолданбалар
Левенштейн автоматтары дұрыс жазылмаған сөзге жақын сөздерді табу арқылы орфографиялық түзету үшін қолданылуы мүмкін. Осы қолданбада сөздің дұрыс жазылмағаны анықталғанда, оның Левенштейн автоматы құрастырылып, сөздіктегі барлық сөздерге қолданылады, осылайша қайсысының дұрыс жазылмаған сөзге жақын екені анықталады. Егер сөздік три түрінде сығымдалған күйде сақталса, автомат құрылғаннан кейін бұл алгоритмнің жұмыс істеу уақыты тридегі түйіндер санына пропорционалды болады, бұл әрбір сөздік сөзі үшін Левенштейн қашықтығын жеке есептеу үшін динамикалық бағдарламалауды қолданудан әлдеқайда жылдам.
Levenshtein automata may be used for spelling correction, by finding words in a given dictionary that are close to a misspelled word. In this application, once a word is identified as being misspelled, its Levenshtein automaton may be constructed, and then applied to all of the words in the dictionary to determine which ones are close to the misspelled word. If the dictionary is stored in compressed form as a trie, the time for this algorithm (after the automaton has been constructed) is proportional to the number of nodes in the trie, significantly faster than using dynamic programming to compute the Levenshtein distance separately for each dictionary word.
Құрылыс
Кез келген тұрақты n үшін, w және n үшін Левенштейн автоматы O(|w|) уақытында құрастырылуы мүмкін. Тюзе осы автоматты құруға арналған тиімді алгоритм ұсынды. Левенштейн (немесе Дамерау–Левенштейн) қашықтығының үшінші автомат құрастыру әдісі – Хассан және авторлардың Левенштейн түрлендіргіштері. Олар өңдеу қашықтығын 1-ге тең ететін шекті күйдегі түрлендіргіштерді көрсетеді, содан кейін оларды белгілі бір тұрақтыға дейінгі өңдеу қашықтығын іске асыру үшін біріктіреді.
For any fixed constant n, the Levenshtein automaton for w and n may be constructed in time O(|w|). Touzet proposed an effective algorithm to build this automaton. Yet a third finite automaton construction of Levenshtein (or Damerau–Levenshtein) distance are the Levenshtein transducers of Hassan et al., who show finite state transducers implementing edit distance one, then compose these to implement edit distances up to some constant.