Понятие функции, измеряющей расстояние, или метрики, используется в самых разных областях и часто используется для оценки сходства двух векторов. Такие функции применяют для определения силы связи двух признаков, или, например, в распознавании образов при сопоставлении шаблонов с различными частями изображений. Здесь и далее, d - метрика. При обработке строк, однако, символы не всегда уместно считать числами, несмотря на то, что коды символов являются ими. Кроме того, часто требуется сравнивать строки разной длины. Поэтому для сравнения строк обычно используют метрики, оценивающие максимальную стоимость преобразования одной строки в другую. В общем случае, операциям редактирования, используемым в этом преобразовании, а именно замене символов, их вставке и удалению, можно назначить разные цены. Последние две операции иногда объединяют в одну и называют вставуд (indel; от insertion и deletion). Расстояние Хемминга [Hamming, 1982] между двумя строками одинаковой длины определяется как число позиций, в которых символы не совпадают. Это эквивалентно минимальной цене преобразования первой строки во вторую в случае, когда разрешена только операция замены с единичным весом. Если допускается сравнение строк разной длины, то, как правило, требуются также вставка и удаление. Если придать им тот же вес, что и замене, минимальная общая цена преобразования будет равна одной из метрик, предложенных Левенштейном [Levenstein, 1965]. Другая метрика равна минимальной цене преобразования в случае, когда разрешены только вставка и удаление. Это эквивалентно назначению цены 1 удалению и вставке, и 2 замене, так как последнюю можно заменить парой вставка-удаление. Первую из этих метрик мы ниже называем расстоянием Левенштейна, а вторую - расстоянием редактирования.  8  Комментарии к статье  8 8  Обсудить в чате