Вопрос о расстоянии Левенштейна

1) Почему мы добавляем 1 в этой строке?

    d[i-1, j] + 1, // deletion 
    d[i, j-1] + 1, // insertion

Линия

if s[i] = t[j] then cost := 0

        else cost := 1

следует учитывать удаленные/меньшие длины слов, или я что-то упустил?

2) Кроме того, в комментариях указано удаление и вставка. Прав ли я, думая, что он проверяет удаленные символы в обоих словах (целые числа j/i, представляющие длину слов), потому что меньшее значение будет представлять удаленные символы.

Используемый код находится здесь (поскольку это псевдокод, и у меня нет особых проблем с языком, этот поток не относится ни к одной языковой категории):

http://www.iterasi.net/openviewer.aspx?sqrlitid=z0cloj7xhk-ce0f72v4cjq


algorithm levenshtein-distance
person GurdeepS    schedule 13.05.2009    source источник

Ответы (2)


arrow_upward
1
arrow_downward

1) Эти строки вычисляют расстояние в случае удаления, в случае вставки и расстояние с использованием «стоимости» в случае замены...

удаление и вставка фактически учитываются как «1» при расчете расстояния, следовательно, +1.

Мы можем поверить, что произошла замена, только если символы разные, следовательно, «стоимость = 0», если оба символа равны...

Новое расстояние — это минимальное расстояние между этими тремя гипотезами, поэтому вы не всегда добавляете 1...

2) если я вычисляю расстояние между "FooBar" и "FoBaWhatever", у меня есть некоторые удаления символов, даже если вторая строка длиннее первой...

Конечно, если вторая строка короче второй ( FooBar -> FoBa ), я найду некоторые удаления, но не могу заранее знать, где они...

person siukurnin    schedule 13.05.2009

arrow_upward
2
arrow_downward

Вы читали http://www.merriampark.com/ld.htm?

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

Эта «стоимость» преобразования указывает на расстояние между двумя строками.

Что насчет обменов? Это алгоритм Damerau–Levenshtein, который отличается. Включение обменов не сильно улучшает ситуацию.

Суть в том, чтобы создать матрицу между двумя словами и вычислить — столбец за столбцом — «расстояние» от каждой буквы каждого слова до каждой буквы другого слова. Нижний правый угол этой матрицы — это общее расстояние с учетом всех букв.

Вопрос 1)

Ячейка «выше» отражает историю изменений, и символ для этой строки (обычно) отличается от этого, поэтому эта ячейка является удалением по отношению к ней.

Ячейка «слева» отражает историю изменений, и символ для этого столбца (обычно) отличается от этого, поэтому эта ячейка является относительной вставкой.

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

Сравнение строк и столбцов имеет стоимость 0 или 1.

Минимум «история плюс одно изменение» и фактическая стоимость изменения являются применимыми затратами.

Вопрос 2)

Переменные i и j не являются длинами чего-либо. Это позиции в матрице сравнения. «Вставка» и «удаление» — это действия, необходимые для преобразования одного слова в другое. Количество действий вставки/удаления — это расстояние между словами.

person S.Lott    schedule 13.05.2009
comment
Да, я действительно читал эту ссылку. Хороший ответ. Однако, последнее: в минимальной функции есть +1 для ячейки и +стоимость для ячейки. Конечно, 1 и стоимость являются одним и тем же значением (1), поскольку стоимость никогда не превышает 1 и не равна 0, поскольку это приведет к выполнению оператора if (если стоимость == 0 и т. д.). Я не понимаю этой логики? - person GurdeepS; 15.05.2009
comment
Нет. Стоимость не всегда равна 1. Она может быть намного больше единицы, если соседние буквы не совпадают. При первом запуске вы предполагаете, что последняя буква n-символьного слова является результатом n вставок; Его стоимость изначально равна n, пока ваше сравнение не покажет, что она меньше, потому что некоторые символы действительно совпали. - person S.Lott; 15.05.2009