Редактировать расстояние рекурсивного алгоритма - Skiena

Ответ 1

На странице 287 в книге:

int match(char c, char d)
{
  if (c == d) return(0); 
  else return(1); 
}

int indel(char c)
{
  return(1);
}

Ответ 2

Они объясняются в книге. Пожалуйста, прочтите раздел 8.2.4 Разновидности дистанции редактирования

Ответ 3

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

Рекурсивная структура проблемы дается как здесь, где i,j являются начальными (или конечными) индексами в двух строках соответственно.

Здесь выдержка из этой страницы, которая хорошо объясняет алгоритм.

Проблема: если две строки размера m, n и набор операций заменить (R), вставить (I) и удалить (D) все по равной цене. Найти минимальное количество изменений (операций), необходимых для преобразования одной строки в другую.

Определение рекурсивных методов:

Что будет в этом случае суб-проблемой? Рассмотрите возможность поиска расстояния редактирования части строк, например, небольшой префикс. Обозначим их как [1... i] и [1... j] для некоторого 1 < я < m и 1 < j < п. Ясно, что решая меньший экземпляр конечной задачи, обозначим его как E (i, j). наш целью является поиск E (m, n) и минимизация стоимости.

В префиксе мы можем правильно выровнять строки тремя способами (i, -), (-, j) и (i, j). Символ дефиса (-) не представляет символа. пример может сделать это более понятным.

Указанные строки ВОСКРЕСЕНЬЕ И СУББОТА. Мы хотим конвертировать ВОСКРЕСНО в СУББОТА с минимальными изменениями. Выберем я = 2 и j = 4, то есть префикс строки SUN и SATU соответственно (предположим, что индексы строк начинаются с 1). Правильные символы могут быть выровнены в три разными способами.

Случай 1: Выровняйте символы U и U. Они равны, никаких изменений не требуется. Мы по-прежнему оставили проблему я = 1 и j = 3, E (i-1, j-1).

Случай 2: Выровняйте правый символ из первой строки и не получите символ из вторая строка. Нам нужно удалить (D) здесь. Мы по-прежнему оставили проблему я = 1 и j = 4, E (i-1, j).

Случай 3: Выровняйте правый символ из второй строки и не получите символ из первая строка. Нам нужна вставка (I) здесь. Мы по-прежнему проблема я = 2 и j = 3, E (i, j-1).

Сочетание всех подзадач минимальной стоимости выравнивания префиксных строк заканчивающийся на я и j, заданный

E (i, j) = min ([E (i-1, j) + D], [E (i, j-1) + I], [E (i-1, j-1) + R, если i, j не одинаковы])

Мы еще не сделали. Каким будет базовый регистр (ы)?

Если обе строки имеют размер 0, стоимость равна 0. Когда только одна строка строки равна нулю, нам нужны операции редактирования, такие как ненулевые длина строки. Математически,

E (0, 0) = 0, E (i, 0) = i, E (0, j) = j

Я рекомендую прочитать эту лекцию для хорошего объяснения.

Функция match() возвращает 1, если два символа не совпадают (так что еще один шаг добавляется в окончательный ответ), в противном случае 0.

Ответ 4

Пройдите по этой ссылке: https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/styles/pages/editdistance.html

код, реализующий вышеуказанный алгоритм:

int dpEdit(char *s1, char *s2 ,int len1,int len2)
{
if(len1==0)  /// Base Case
return len2;
else if(len2==0)
return len1;
else
{
    int add, remove,replace;
    int table[len1+1][len2+2];
    for(int i=0;i<=len2;i++)
    table[0][i]=i;
    for(int i=0;i<=len1;i++)
    table[i][0]=i;
    for(int i=1;i<=len1;i++)
    {
        for(int j=1;j<=len2;j++)
        {
          // Add 
          //
          add = table[i][j-1]+1;  
          remove = table[i-1][j]+1;
          if(s1[i-1]!=s2[j-1])
          replace = table[i-1][j-1]+1;
          else
          replace =table[i-1][j-1];
          table[i][j]= min(min(add,remove),replace); // Done :)

        }
    }

Ответ 5

Это рекурсивный алгоритм, а не динамическое программирование. Обратите внимание, что как i, так и j указывают на последний char s и t соответственно при запуске алгоритма.

indel возвращает 1. match (a, b) возвращает 0, если a = b (match) else return 1 (подстановка)

#define MATCH     0       /* enumerated type symbol for match */
#define INSERT    1       /* enumerated type symbol for insert */
#define DELETE    2       /* enumerated type symbol for delete */

int string_compare(char *s, char *t, int i, int j)
{
    int k;                  /* counter */
    int opt[3];             /* cost of the three options */
    int lowest_cost;        /* lowest cost */

    // base case, if i is 0, then we reached start of s and 
    // now it empty, so there would be j * 1 edit distance between s & t
    // think of it if s is initially empty and t is not, how many
    // edits we need to perform on s to be similar to t? answer is where
    // we are at t right now which is j
    if (i == 0) return(j * indel(' '));
    // same reasoning as above but for s instead of t
    if (j == 0) return(i * indel(' '));

    // calculate opt[match] by checking if s[i] = t[j] which = 0 if true or 1 if not
    // then recursively do the same for s[i-1] & t[j-1]
    opt[MATCH] = string_compare(s,t,i-1,j-1) + match(s[i],t[j]);
    // calculate opt[insert] which is how many chars we need to insert 
    // in s to make it looks like t, or look at it from the other way,
    // how many chars we need to delete from t to make it similar to s?
    // since we're deleting from t, we decrease j by 1 and leave i (pointer
    // in s) as is + indel(t[j]) which we deleted (always returns 1)
    opt[INSERT] = string_compare(s,t,i,j-1) + indel(t[j]);
    // same reasoning as before but deleting from s or inserting into t
    opt[DELETE] = string_compare(s,t,i-1,j) + indel(s[i]);

    // these lines are just to pick the min of opt[match], opt[insert], and
    // opt[delete]
    lowest_cost = opt[MATCH];
    for (k=INSERT; k<=DELETE; k++)
            if (opt[k] < lowest_cost) lowest_cost = opt[k];

    return( lowest_cost );
}

Алгоритм не трудно понять, вам просто нужно его прочитать пару раз. Меня всегда развлекает тот, кто его изобрел, и доверие к тому, что рекурсия пойдет правильно.

Ответ 6

Это скорее всего не проблема для ФП, но я напишу свое понимание текста.

/**
 * Returns the cost of a substitution(match) operation
 */
int match(char c, char d)
{
  if (c == d) return 0
  else return 1
}

/**
 * Returns the cost of an insert/delete operation(assumed to be a constant operation)
 */
int indel(char c)
{
  return 1
}

Расстояние редактирования - это, по сути, минимальное количество модификаций в данной строке, необходимое для ее преобразования в другую ссылочную строку. Модификации, как вы знаете, могут быть следующими.

1. Подстановка (замена одного символа)
2. Вставить (вставить один символ в строку)
3. Удалить (удаление одного символа из строки)

Теперь,

Правильная постановка вопроса о сходстве строк требует от нас установить стоимость каждой из этих операций преобразования строк. Присвоение каждой операции равной стоимости 1 определяет расстояние редактирования между двумя строками.

Таким образом, устанавливается, что каждая из трех известных нам модификаций имеет постоянную стоимость O (1).

Но как мы узнаем, где изменить?

Вместо этого мы ищем модификации, которые могут или не могут быть необходимы с конца строки, символ за символом. Так,

1. Мы считаем все операции замещения, начиная с конца строки
2. Мы считаем все операции удаления, начиная с конца строки
3. Мы считаем все операции вставки, начиная с конца строки

Наконец, когда у нас есть эти данные, мы возвращаем минимум из трех указанных выше сумм.