Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Компьютерлік ғылымда, string to string түзету мәселесі бір тізбені екіншісіне өзгерту үшін қажетті өңдеу операцияларының ең төмен құн тізбесін анықтауды білдіреді (яғни, ең қысқа өңдеу қашықтығын есептеу). Әрбір өңдеу операциясының өзіндік құн шамасы болады. Бір өңдеу операциясы – тізбенің бір символын басқа символға өзгерту (құны WC), символды жою (құны WD) немесе жаңа символ қосу (құны WI) болуы мүмкін. Егер барлық өңдеу операцияларының құны бірдей болса (WC = WD = WI = 1), онда мәселе екі тізбенің Левенштейн қашықтығын есептеумен сәйкес келеді. Тізбе қашықтығын анықтаудың тиімді жолын ұсынатын және қажетті түрлендіру операцияларының ең аз санын көрсететін бірнеше алгоритмдер бар. Мұндай алгоритмдер, әсіресе, бірдеңені бастапқы нұсқаға қатысты айырмашылықтар жиынтығы ретінде сақтау операциялары үшін пайдалы. Бұл бір нысанның бірнеше нұсқасын оларды жеке сақтауға қарағанда әлдеқайда тиімді сақтауға мүмкіндік береді. Бұл бірнеше нысанның бір нұсқасы үшін де дұрыс, егер олар өте көп айырмашылыққа ие болмаса немесе аралық жағдайда болса. Ерекше айта кетелік, мұндай айырмашылық алгоритмдері молекулалық биологияда түрлі организмдер арасындағы туыстық байланысты олардың макромолекулаларының (мысалы, ақуыздар немесе ДНК) ұқсастығы негізінде өлшеу үшін қолданылады.
In computer science, the string to string correction problem refers to determining the minimum cost sequence of edit operations necessary to change one string into another (i. e., computing the shortest edit distance). Each type of edit operation has its own cost value. A single edit operation may be changing a single symbol of the string into another (cost WC), deleting a symbol (cost WD), or inserting a new symbol (cost WI). If all edit operations have the same unit costs (WC = WD = WI = 1) the problem is the same as computing the Levenshtein distance of two strings. Several algorithms exist to provide an efficient way to determine string distance and specify the minimum number of transformation operations required. Such algorithms are particularly useful for delta creation operations where something is stored as a set of differences relative to a base version. This allows several versions of a single object to be stored much more efficiently than storing them separately. This holds true even for single versions of several objects if they do not differ greatly, or anything in between. Notably, such difference algorithms are used in molecular biology to provide some measure of kinship between different kinds of organisms based on the similarities of their macromolecules (such as proteins or DNA).
Ұзарту
Мәселенің кеңейтілген түрі редакциялау операциясының жаңа түрін қамтиды: кез келген екі іргелес символдарды WS бағасымен ауыстыру. Бұл нұсқаны редакциялау операцияларының бағаларына белгілі бір шектеулер қойылған жағдайда полиномиалдық уақытта шешуге болады. Роберт А. Вагнер (1975) жалпы мәселенің NP-толық екенін көрсетті. Атап айтқанда, ол WI < WC = WD = ∞ және 0 < WS < ∞ (немесе, балама ретінде, өзгерту және жою рұқсат етілмегенде) мәселенің NP-толық екенін дәлелдеді.
The extended variant of the problem includes a new type of edit operation: swapping any two adjacent symbols, with a cost of WS. This version can be solved in polynomial time under certain restrictions on edit operation costs. Robert A. Wagner (1975) showed that the general problem is NP complete. In particular, he proved that when WI < WC = WD = ∞ and 0 < WS < ∞ (or equivalently, changing and deletion are not permitted), the problem is NP complete.