предисловие
В настоящее время существует множество различных схем для вычисления сходства предложений, таких как методы на основе семантического словаря, методы на основе одного и того же словаря, методы на основе статистики и методы на основе расстояния редактирования. В этой статье впервые представлены основы расстояния редактирования.
изменить расстояние
Расстояние редактирования на самом деле относится к стоимости минимальной операции редактирования, необходимой для преобразования одной строки в другую строку. Включает символы вставки, замены и удаления. Чем меньше расстояние редактирования, тем больше сходство.
Например, мы будемwhatпреобразовать вwhere, возможно, изменив a -> e, затем t -> r, наwher, добавьте e в конце, готово. Потому что каждый шаг можно вставить, удалить или заменить, как получить в итоге минимальную стоимость, что и будет решать динамическое программирование.
Предположим, у нас есть длиныi、jДве строки , пусть расстояние редактирования будетedit(i,j). Тогда давайте посмотрим, если их последние символы равны, расстояние редактирования на самом деле равноedit(i-1,j-1). И если последние символы не равны, то мы можем сделать их равными вставкой или заменой, но соответствующие затраты разных операций не одинаковы, если вставкаedit(i,j-1)+1илиeidit(i-1,j)+1, заменяетсяedit(i-1,j-1)+1.
решать
Он представлен следующим динамическим уравнением:
Взяв предыдущий пример, что куда, предполагая, что два символа пусты, соответствующие затраты следующие:
| изменить расстояние | нулевой | w | h | a | t |
| нулевой | 0 | 1 | 2 | 3 | 4 |
| w | 1 | ||||
| h | 2 | ||||
| e | 3 | ||||
| r | 4 | ||||
| e | 5 |
После динамического программирования:
| изменить расстояние | нулевой | w | h | a | t |
| нулевой | 0 | 1 | 2 | 3 | 4 |
| w | 1 | 0 | 1 | 2 | 3 |
| h | 2 | 1 | 0 | 1 | 2 |
| e | 3 | 2 | 1 | 1 | 2 |
| r | 4 | 3 | 2 | 2 | 2 |
| e | 5 | 4 | 3 | 3 | 3 |
Во всем процессе динамического программирования всегда выбирается минимальная стоимость, поэтому последние 3 — это минимальная стоимость двух строк, то есть расстояние редактирования.
github
https://github.com/sea-boat/TextAnalyzer/blob/master/src/main/java/com/seaboat/text/analyzer/distance/CharEditDistance.java
выполнить
public class EditDistance {
public static int getEditDistance(String s, String t) {
int d[][];
int n;
int m;
int i;
int j;
char s_i;
char t_j;
int cost;
n = s.length();
m = t.length();
if (n == 0) {
return m;
}
if (m == 0) {
return n;
}
d = new int[n + 1][m + 1];
for (i = 0; i <= n; i++) {
d[i][0] = i;
}
for (j = 0; j <= m; j++) {
d[0][j] = j;
}
for (i = 1; i <= n; i++) {
s_i = s.charAt(i - 1);
for (j = 1; j <= m; j++) {
t_j = t.charAt(j - 1);
cost = (s_i == t_j) ? 0 : 1;
d[i][j] = Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1);
d[i][j] = Math.min(d[i][j], d[i - 1][j - 1] + cost);
}
}
return d[n][m];
}
public static void main(String[] args) {
EditDistance ed = new EditDistance();
System.out.println(ed.getEditDistance("what", "where"));
}
}
------------- Рекомендуем прочитать ------------
Резюме моей статьи за 2017 год — машинное обучение
Резюме моих статей за 2017 год — Java и промежуточное ПО
Резюме моих статей 2017 года — глубокое обучение
Краткое изложение моих статей за 2017 год — исходный код JDK
Резюме моей статьи за 2017 год — обработка естественного языка
Резюме моих статей 2017 года — Java Concurrency
Поговори со мной, задай мне вопросы:
Меню официальной учетной записи было разделено на «Сводка для чтения», «Распределенное», «Машинное обучение», «Глубокое обучение», «НЛП», «Глубина Java», «Ядро параллелизма Java», «Исходный код JDK», "Tomcat Core" "Подождите, может быть, есть тот, который соответствует вашему аппетиту.
Зачем писать «Анализ проектирования ядра Tomcat»
Добро пожаловать, чтобы следовать: