Подводя итог одному предложению: расстояние редактирования — это наименьший шаг, необходимый для перехода от одной строки к другой.

Один: Введение

В теории информации, лингвистике и информатике расстояние Левенштейна — это строковая метрика, используемая для измерения разницы между двумя строками. Неформально расстояние Левенштейна между двумя словами — это наименьший шаг редактирования одного символа (вставка, удаление или замена), необходимый для замены одного слова другим.

Он назван в честь советского математика Владимира Левенштейна, предложившего алгоритм в 1965 году.

Расстояние Левенштейна также можно назвать расстоянием редактирования, хотя этот термин также может относиться к более широкому семейству показателей расстояния.

Расстояние Левенштейна тесно связано с попарным выравниванием строк.

Основной контент здесь мойLevenshtein distanceАнглийский перевод также добавил некоторые мои мысли~

Второе: определение алгоритма

1: Определение

Расстояние Левенштейна между двумя строками a и b определяется следующим образом:

Равен 0, когда ai = bj, 1 в противном случае,

Представляет расстояние от первых i байтов a до первых j байтов b.

Среди них относительно изменения строки b:

: удалить байт от имени a для соответствия b
: добавить байт от имени a для соответствия b
: означает совпадение или отсутствие совпадения, в зависимости от того, одинаковы ли все символы

2: маленький случай

Рассчитаем расстояние редактирования между котенком и сидящим

kиттен →sitten (замените «k» -> «s»)
sitteп → сидетьiп (заменить «е» -> «я»)
сидеть → сидетьg(вставьте «г»).

Количество шагов, необходимых для вышеуказанного процесса изменения, является минимальным количеством шагов, поэтому расстояние редактирования между ними равно «3».

3: Верхняя и нижняя границы алгоритма

Значение расстояния Левенштейна содержит несколько верхних и нижних границ

Минимальное расстояние — это разница в длине двух строк.
Расстояние не больше длины более длинной из двух строк.
длина 0 тогда и только тогда, когда строки одинаковы
Когда строки имеют одинаковую длину, максимальная длина расстояния равна расстоянию Хэмминга (описано ниже).
Расстояние между двумя строками меньше или равно сумме расстояний от другой строки (уравнение треугольника a+b

Расстояние Хэмминга состоит в том, чтобы сравнить две строки одинаковой длины с самого начала, чтобы увидеть, одинаковы ли значения соответствующих позиций символов двух строк, если они не совпадают, добавить 1 к расстоянию, а конечный результат результат - расстояние Хэмминга Например, расстояние между abcd и abhg равно 2, а расстояние между abcd и bcda равно 4.

Три: сценарии применения

1: выравнивание данных

Когда автор работает над связанным сетевым проектом, в фоновом режиме есть два вида специальных данных: адрес и компания.Эти два вида данных представляют собой данные, введенные пользователем, поэтому характерно то, что в нем может быть много разных строк. одно и то же место, например, одно и то же место.Одно местоположение: «ИТ-индустриальный парк, район Чаоян, Пекин», может быть ряд данных, таких как «ИТ-индустриальный парк, район Чаоян, Пекин» или «ИТ-парк, район Чаоян , Пекин» в фоновых данных, и мы не можем выполнять нечеткие запросы (поскольку узел Связь между данными и ребрами составляет десятки миллионов. Нечеткие запросы могут соответствовать большому количеству узлов и возвращать большое количество данных, что будет влияют на стабильность проекта.) Мы используем выравнивание данных для решения этой проблемы.Когда пользователь вводит адрес, мы с помощью алгоритма расстояния редактирования можем получить и отобразить другие соответствующие данные, и можно добиться лучшего эффекта. Конкретные этапы реализации здесь не представлены.

2: Орфографическая коррекция

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

Исправление ошибок в основном решает ситуацию с ошибками ввода в запросе, например, запрос пиньинь, запрос содержит омофонные опечатки или другие слова с другим звучанием, пропущенные слова и так далее. Это исправление ошибок в основном основано на двух правилах: исправление ошибок пиньинь и исправление ошибок расстояния редактирования. В основном в автономном режиме создаются два словаря, а именно словарь пиньинь и словарь расстояния редактирования. Исходный словарь в основном состоит из данных cmc, данных ячеек, данных верхнего запроса и белого списка. Создайте словарь пиньинь и отредактируйте словарь расстояний с помощью скрипта ****. После выполнения скрипта данные словаря будут сгенерированы в каталоге ***. Генерация словаря пиньинь в основном заключается в преобразовании слов исходного словаря в пиньинь, а генерация словаря расстояния редактирования в основном заключается в пропуске определенного слова или определенной буквы пиньинь. Код для создания словаря находится в разделе tool. Логика оперативного исправления ошибок Динамическую библиотеку в каталоге so можно сгенерировать, скомпилировав код с помощью make. Внешне предоставляется служба java RPC, связывающая библиотеку динамической компоновки С++ через java jni.

Основная логика исправления ошибок выглядит следующим образом: сначала разберите запрос и оцените, является ли он полным пиньинь или содержит китайский язык. Если это все пиньинь, он сразу перейдет к соответствующему исправлению ошибок пиньинь и результату отзыва.Если это не может быть решено с помощью пиньинь, перейдите к отзыву расстояния редактирования, чтобы решить ситуацию с пропущенными буквами; если это часть китайского или все китайские запросы, исправление пиньинь будет выполнено в первую очередь.Неправильно, решите проблему омофонических опечаток, если отзыва нет, то сначала выполните сегментацию слов и соединение соседних терминов вместе, чтобы вспомнить пиньинь и отредактировать расстояние.

Четыре: другие алгоритмы редактирования расстояния

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

Расстояние Дамерау-Левенштейна: можно вставлять, удалять, заменять и обмениваться между двумя соседними символами в строке.
расстояние до самой длинной общей подпоследовательности (LCS): разрешить только вставку, удаление и замену строк
Расстояние Хэмминга: позволяет заменять строки, может использоваться только для расчета расстояния редактирования двух строк одинаковой длины.
Расстояние Джаро: разрешен обмен только строками

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

Пятое: реализация алгоритма

1: Рекурсивная реализация

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

//实现方法
private static int distance(String a, int len_a, String b, int len_b) {
    //递归回归点
    if (len_a == 0)
        return len_b;
    if (len_b == 0)
        return len_a;
    
    int cos;
    if (a.charAt(len_a-1) == b.charAt(len_b-1))
        cos = 0;
    else
        cos = 1;

    int re1 = distance(a, len_a - 1, b, len_b) + 1;
    int re2 = distance(a, len_a, b, len_b - 1) + 1;
    int re3 = distance(a, len_a - 1, b, len_b - 1) + cos;
    //返回在a中删除一个字符、在b中删除一个字符、ab中均删除一个字符获得结果中取最小值
    return re1 < re2 ? (re1 < re3 ? re1 : re3) : (re2 < re3 ? re2 : re3);
}
//测试
public static void main(String[] args) {
    String a = "kitten";
    String b = "sitting";
    int re = distnace(a, a.length(), b, b.length());
    System.out.println(re);
    //输出：3
}

Этот метод имеет высокую временную сложность и низкую эффективность, а также многократно вычисляет множество строк.Для реализации ниже используется алгоритм динамического программирования.

2: Реализация динамического программирования

Принципиальная часть алгоритма заимствована из https://www.cnblogs.com/sumuncle/p/5632032.html части статьи блоггера =.=

Обоснование алгоритма: предположим, что мы можем использовать d[ i , j ] шагов (которые можно хранить в двумерном массиве), представляя минимум, необходимый для преобразования строки s[ 1…i ] в строку t [ 1…j ]. количество шагов

Тогда в самом простом случае, то есть когда i равно 0, то есть строка s пуста, тогда соответствующее d[0,j] должно добавить j символов, так что s преобразуется в t, и когда j равно 0 , то есть строка t пуста, тогда соответствующее d[i,0] должно сократить i символов, чтобы s было преобразовано в t.

Затем рассмотрим общую ситуацию и добавим небольшое представление о динамическом программировании.Если мы хотим, чтобы s[1..i] преобразовывалось в t[1..j] после минимального количества добавлений, удалений или операции замены, то мы должны В прошлом ее можно было добавить, удалить или заменить с минимальным количеством операций, так что теперь для строки s и строки t достаточно сделать еще одну операцию или не завершить преобразование из s[1..i] в t[1..j] преобразовать. Так называемое «до» делится на следующие три ситуации:

1) Мы можем преобразовать s[1…i] в t[1…j-1] за k операций
2) Мы можем преобразовать s[1..i-1] в t[1..j] за k операций
3) Мы можем преобразовать s[1…i-1] в t[1…j-1] за k шагов

В первом случае нам нужно только добавить s[1..i] к t[j] в конце, чтобы завершить сопоставление, поэтому всего требуется k+1 операций. Во втором случае нам нужно только удалить s[i] в конце, а затем выполнить эти k операций, поэтому всего требуется k+1 операций. В третьем случае нам нужно всего лишь заменить s[i] на t[j] в конце, чтобы s[1..i] == t[1..j], что требует k+1 всего операций . А если в третьем случае s[i] точно равно t[j], то мы можем завершить процесс, используя всего k операций.

Наконец, чтобы гарантировать, что количество полученных операций всегда будет наименьшим, мы можем выбрать наименее затратную из трех вышеприведенных случаев, которая является наименьшей операцией, необходимой для преобразования s[1..i] в t[1.. j] частота. Основные шаги алгоритма:

(1) Построить матрицу с m+1 строками и n+1 столбцами для хранения количества операций, которые необходимо выполнить для завершения определенного преобразования, и преобразовать строку s[1..n] в строку t[1 …m ] Количество операций, которые необходимо выполнить, равно значению matrix[n][m];
(2) Первая строка матрицы инициализации — от 0 до n, а первый столбец — от 0 до m. Matrix[0][j] представляет значение в строке 1, столбце j-1. Это значение представляет собой количество операций, необходимых для преобразования строки s[1...0] в t[1..j]. Очевидно, что Преобразование пустой строки в строку длины j требует всего j операций сложения, поэтому значением matrix[0][j] должно быть j, и так далее для других значений.
(3) Проверить каждый символ s[i] от 1 до n;
(4) Проверить каждый символ s[i] от 1 до m;
(5) Сравнить попарно каждый символ строки s и строки t. Если они равны, пусть стоимость равна 0. Если они не равны, пусть стоимость равна 1 (эта стоимость будет использоваться позже);
(6)
- А. Если мы можем преобразовать s[1..i-1] в t[1..j] за k операций, то мы можем удалить s[i], а затем выполнить эти k операций, так что всего k+1 требуются операции.
- б) Если мы можем преобразовать s[1…i] в t[1…j-1] за k операций, то есть d[i,j-1]=k, то мы можем преобразовать t[j] плюс s[ 1..i], что в сумме требует k+1 операций.
- в) Если мы можем преобразовать s[1...i-1] в t[1...j-1] за k шагов, то мы можем преобразовать s[i] в t[j] таким образом, что s[ 1. .i] == t[1..j], что также требует всего k+1 операций. (Здесь добавляется стоимость, потому что если s[i] точно равно t[j], то нет необходимости делать операцию замены, ее можно удовлетворить, если не равно, нужно сделать еще одну операцию замены , то нужно k+ 1 операция)
- Поскольку мы хотим получить минимальное количество операций, нам, наконец, нужно сравнить количество операций в этих трех случаях и взять минимальное значение в качестве значения d[i,j];
- г. Затем повторите 3,4,5,6, и окончательный результат будет в d[n,m];

private static int distance(String a, String b) {
    int[][] dis = new int[a.length()+1][b.length()+1];
    for (int i = 1; i <= a.length(); i++)
        dis[i][0] = i;
    for (int j = 1; j <= b.length(); j++)
        dis[0][j] = j;
    int cas;
    for (int j = 1; j <= b.length(); j++) {
        for (int i = 1; i <= a.length(); i++) {
            if (a.charAt(i-1) == b.charAt(j-1))
                cas = 0;
            else
                cas = 1;
            int re = Math.min(dis[i - 1][j] + 1, dis[i][j - 1] + 1);
            dis[i][j] = Math.min(re, dis[i - 1][j - 1] + cas);
        }
    }
    return dis[a.length() - 1][b.length() - 1];
}

public static void main(String[] args) {
    String a = "kitten";
    String b = "sitting";
    int re = distance(a, b);
    System.out.println(re);
    //输出：3
}

Если вы перепечатаете этот пост в блоге, пожалуйста, прикрепите ссылку на эту статью, спасибо за сотрудничество~:Талант /user/407224…

Если вы чувствуете, что эта статья полезна для вас, пожалуйста, нажмите «Нравится» или «Подписаться» на блогера, ваши лайки и внимание будут для меня самой большой мотивацией двигаться вперед!