Асимметричное расстояние Левенштейна

Question

Учитывая две битовые строки, x и y, с x длиннее y, я бы хотел вычислить некий асимметричный вариант расстояния Левенштейна между ними. Начиная с x, я хотел бы знать минимальное количество удалений и замещений, необходимых для превращения x в y.

Могу ли я просто использовать обычное расстояние Левенштейна для этого, или мне нужно изменить алгоритм? Другими словами, с обычным набором изменений удаления, подстановки и добавления всегда полезно удалить больше, чем разница в длинах между двумя строками, а затем добавить некоторые биты назад? Я подозреваю, что ответ отрицательный, но я не уверен. Если я ошибаюсь, и мне нужно изменить определение расстояния Левенштейна, чтобы запретить удаление, как мне это сделать?

Наконец, я ожидал бы интуитивно, что получаю такое же расстояние, если бы начал с y (более короткая строка) и допускал только добавления и замены. Это правильно? У меня есть смысл, для чего эти ответы, я просто не могу их доказать.

Answer 1

Если я понимаю вас правильно, я думаю, что ответ да, расстояние редактирования Левенштейна может отличаться от алгоритма, который позволяет только удалять и заменять большую строку. Из-за этого вам нужно будет изменить или создать другой алгоритм, чтобы получить ограниченную версию.

Рассмотрите две строки «ABCD» и «ACDEF». Расстояние Левенштейна равно 3 (ABCD-> ACD-> ACDE-> ACDEF). Если мы начнем с более длинной строки и ограничимся удалениями и заменами, мы должны использовать 4 изменения (1 удаление и 3 замены). Причина в том, что строки, в которых делегирования применяются к меньшей строке для эффективного доступа к большей строке, не могут (если вы не согласны с этим)

Ваш последний абзац прав. Если путь от более короткого до более длинного использует только вставки и замены, то любой разрешенный путь может быть просто изменен с более длинного на более короткий. Замены одинаковы независимо от направления, но вставки при переходе от малого к большому становятся удалениями при обратном.

Я не тестировал это полностью, b ut эта модификация показывает направление, которое я бы взял, и, похоже, работает со значениями, которые я тестировал с ним. Это написано в C# и следует за кодом psuedo в записи википедии для расстояния Левенштейна. Есть очевидные оптимизации, которые можно сделать, но я воздержался от этого, поэтому было более очевидно, какие изменения я внес из стандартного алгоритма. Важное замечание состоит в том, что (используя ваши ограничения), если строки имеют одинаковую длину, то замена является единственной допустимой операцией.

static int LevenshteinDistance(string s, string t) { 
     int i, j; 
     int m = s.Length; 
     int n = t.Length; 

     // for all i and j, d[i,j] will hold the Levenshtein distance between 
     // the first i characters of s and the first j characters of t; 
     // note that d has (m+1)*(n+1) values 
     var d = new int[m + 1, n + 1]; 

     // set each element to zero 
     // c# creates array already initialized to zero 

     // source prefixes can be transformed into empty string by 
     // dropping all characters 
     for (i = 0; i <= m; i++) d[i, 0] = i; 

     // target prefixes can be reached from empty source prefix 
     // by inserting every character 
     for (j = 0; j <= n; j++) d[0, j] = j; 

     for (j = 1; j <= n; j++) { 
      for (i = 1; i <= m; i++) { 
       if (s[i - 1] == t[j - 1]) 
        d[i, j] = d[i - 1, j - 1];  // no operation required 
       else { 
        int del = d[i - 1, j] + 1; // a deletion 
        int ins = d[i, j - 1] + 1; // an insertion 
        int sub = d[i - 1, j - 1] + 1; // a substitution 
        // the next two lines are the modification I've made 
        //int insDel = (i < j) ? ins : del; 
        //d[i, j] = (i == j) ? sub : Math.Min(insDel, sub); 
        // the following 8 lines are a clearer version of the above 2 lines 
        if (i == j) { 
         d[i, j] = sub; 
        } else { 
         int insDel; 
         if (i < j) insDel = ins; else insDel = del; 
         // assign the smaller of insDel or sub 
         d[i, j] = Math.Min(insDel, sub); 
        } 
       } 
      } 
     } 
     return d[m, n]; 
    }