Как на основе расстояния Левенштейна вывести промежуточные слова?

Question

[Sushkov]

Вот функция для расчета расстояния Левенштейна , как вывести промежуточные слова и возможно ли это для данной функции?

int editdist(String S1, String S2)
        {
            int m = S1.Length, n = S2.Length;
            int[] D1;
            int[] D2 = new int[n + 1];

            for (int i = 0; i <= n; i++)
                D2[i] = i;

            for (int i = 1; i <= m; i++)
            {
                D1 = D2;
                D2 = new int[n + 1];
                for (int j = 0; j <= n; j++)
                {
                    if (j == 0) D2[j] = i;
                    else {
                        int cost = (S1[i - 1] != S2[j - 1]) ? 1 : 0;

                        if (D2[j - 1] < D1[j] && D2[j - 1] < D1[j - 1] + cost)
                            D2[j] = D2[j - 1] + 1;
                        else if (D1[j] < D1[j - 1] + cost)
                            D2[j] = D1[j] + 1;
                        else
                            D2[j] = D1[j - 1] + cost;
                    }
                }
            }
            return D2[n];
        }

Comments

[nirvimel]

"Промежуточные слова" - это вообще что такое?

Answer 1

[Mrrl]

Достаточно для каждого элемента массива запоминать последовательность действий - "как мы сюда попали". Например, в виде строки с 4 командами - "вставили символ X", "удалили символ X", "заменили X на Y" (X и Y могут совпадать).
Если вторая строчка была "ABCD", то массив, соответствующий начальному состоянию D2, будет выглядеть так:
{"","iA","iAiB","iAiBiC","iAiBiCiD"} - это команды, переводящие пустую строку в различные начальные подстроки этой второй строки.
По мере пересчёта массивов строки будут удлиняться, и в итоге мы получим некоторую строку с командами, переводящими строку1 в строку2. Например, для перевода ASTRA в STARKA это может быть "dArSSrTTiArRRiKrAA".
Дальше можно выполнить несколько первых команд и игнорировать остальные. Увеличивая число выполненных команд, получим промежуточные строки: ASTRA, STRA, STARA, STARKA

Answer 2

[Mercury13]

Разумеется, будем считать, что слова не должны быть осмысленными (иначе это другая задача, где этот алгоритм, с одной стороны, тяжеловат, с другой — совсем не нужен). Если между словами «коза» и «волк» расстояние 3, то промежуточные слова — «коза → воза → вола → волк». Или, если не против, «коза → козк →колк → волк».

Итак, перед нами типичный алгоритм динамического программирования. В алгоритме динамического программирования есть два этапа: обратный ход и прямой. Этот алгоритм страдает двумя недостатками, мешающими взять и написать прямой ход.
1. Матрица сжата. Вместо матрицы (M+1)×(N+1) мы имеем два массива длины N+1, хранящие одну строчку и потихоньку перезаписываемые.
2. Нет второй матрицы, которая указывает направление, куда идти. В нашем случае направления — это три действия над строкой: замена, вставка и удаление.
ну и 3) В сокращённом варианте хватит двух массивов, обмениваемых местами. К делу отношения не имеет, просто вопросы умелого программирования. Кажется, перед нами Java и утечек памяти тут нет — тем лучше.

С задачами 1 и 2 надо сделать три вещи.
1. Массивы D1 и D2 превратить в единую матрицу (M+1)×(N+1).
2. Добавить второй такой же. Элементы его — enum: удалить/вставить/заменить.
3. Написать прямой ход. Мы находимся в точке (M, N); смотрим, куда идти. Заменить — идём туда-то, вставить — идём туда-то, удалить — идём туда-то. Ну и, разумеется, выполняем нашу операцию на строках и выводим, что получилось. Продолжаем путь, пока не попадём в (0, 0).

Comments

[Алексей Уколов]

Разумеется, будем считать, что слова не должны быть осмысленными

Слова не могут быть бессмысленными, иначе это просто набор букв.

[Mercury13]

Алексей Уколов: В математике понятие «слово» совсем другое, это то, что мы, программисты, называем «строкой» (string).