Проблема исправления строки в строку - String-to-string correction problem
В информатике , то проблема коррекции строки к строке относится к определению минимального количества операций редактирования , необходимых для изменения одной строки в другую (например, вычисление кратчайшего расстояния редактирования ). Одной операцией редактирования может быть изменение одного символа строки на другой, удаление или вставка символа. Длина последовательности редактирования является мерой расстояния между двумя строками.
Существует несколько алгоритмов, обеспечивающих эффективный способ определения расстояния между строками и указания минимального количества требуемых операций преобразования. Такие алгоритмы особенно полезны для операций создания дельты, когда что-то хранится в виде набора отличий от базовой версии. Это позволяет хранить несколько версий одного объекта намного эффективнее, чем хранить их по отдельности. Это верно даже для отдельных версий нескольких объектов, если они не сильно различаются, или чего-либо промежуточного. Примечательно, что такие алгоритмы различия используются в молекулярной биологии для обеспечения некоторой степени родства между различными видами организмов на основе сходства их макромолекул (таких как белки или ДНК ).