Коррекция строк: вычисление минимальной стоимости преобразования одной строки в другую. Алгоритмы для определения расстояния между строками и кратчайшего пути.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В информатике задача коррекции строки к строке относится к определению минимальной по стоимости последовательности операций редактирования, необходимых для преобразования одной строки в другую (то есть вычислению кратчайшего расстояния редактирования). Каждый тип операции редактирования имеет свою стоимость. Операцией редактирования может быть замена одного символа строки на другой (стоимость 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.