Я создаю инструмент для исправления орфографии и хотел реализовать зашумленный канал с помощью теоремы Байеса. Для этого мне нужно рассчитать вероятность P(X|W), где X — заданное (с ошибкой) слово, а W — возможное исправление. Вероятность задается путем получения значения из матрицы путаницы, которая зависит от знания того, какой тип ошибки произошел, а это означает, что если, например, X = egh и W = яйцо, то расстояние редактирования будет равно 1, а ошибка будет подстановкой. ошибка, которая произошла на символе номер 2.
Я пытаюсь найти способ получить тип ошибки, а также символ, для которого она произошла, но, похоже, не могу заставить ее работать. Я пытался создать TreeMap и вставлять значения i/j при обнаружении ошибки, но это не сработало.
Я могу предположить, что есть только одна ошибка, означающая, что расстояние редактирования равно 1.
Вот мой код:
public static int DLD(String s1, String s2) {
if (s1 == null || s2 == null) { // Invalid input
return -1;
}
if (s1.equals(s2)) { // No distance to compute
return 0;
}
// The max possible distance
int inf = s1.length() + s2.length();
// Create and initialize the character array indices
HashMap<Character, Integer> da = new HashMap<>();
for (int i = 0; i < s1.length(); ++i) {
da.put(s1.charAt(i), 0);
}
for (int j = 0; j < s2.length(); ++j) {
da.put(s2.charAt(j), 0);
}
// Create the distance matrix H[0 .. s1.length+1][0 .. s2.length+1]
int[][] distances = new int[s1.length() + 2][s2.length() + 2];
// initialize the left and top edges of H
for (int i = 0; i <= s1.length(); ++i) {
distances[i + 1][0] = inf;
distances[i + 1][1] = i;
}
for (int j = 0; j <= s2.length(); ++j) {
distances[0][j + 1] = inf;
distances[1][j + 1] = j;
}
// fill in the distance matrix H
// look at each character in s1
for (int i = 1; i <= s1.length(); ++i) {
int db = 0;
// look at each character in s2
for (int j = 1; j <= s2.length(); ++j) {
int i1 = da.get(s2.charAt(j - 1));
int j1 = db;
int cost = 1;
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
cost = 0;
db = j;
}
distances[i + 1][j + 1] = min(
distances[i][j] + cost, // substitution
distances[i + 1][j] + 1, // insertion
distances[i][j + 1] + 1, // deletion
distances[i1][j1] + (i - i1 - 1) + 1 + (j - j1 - 1));
}
da.put(s1.charAt(i - 1), i);
}
return distances[s1.length() + 1][s2.length() + 1];
}
Любой намек/направление на решение этого будет высоко оценен.
Спасибо!
Редактировать 1: Я кое-что понял, и, похоже, это работает, хотя я не уверен на 100 %. Я заменил сегмент кода, где я использую метод min(), следующим:
int sub = distances[i][j] + cost;
int ins = distances[i + 1][j] + 1;
int del = distances[i][j + 1] + 1;
int trans = distances[i1][j1] + (i - i1 - 1) + 1 + (j - j1 - 1);
distances[i + 1][j + 1] = min(sub, ins, del, trans);
if ((distances[i][j] == 0 || distances[i - 1][j] == 0 ||
distances[i][j - 1] == 0 || distances[i + 1][j + 1] == trans) &&
distances[i + 1][j + 1] == 1) {
TreeMap<String, Integer> error = mappingTermAndError.getOrDefault(s2, null);
if (error != null) {
error.clear();
} else {
error = new TreeMap<>();
}
if (distances[i + 1][j + 1] == trans) {
error.put("trans", i - 2);
} else if (distances[i + 1][j + 1] == del) {
error.put("del", i - 1);
} else if (distances[i + 1][j + 1] == ins) {
error.put("ins", i - 1);
} else { // distances[i + 1][j + 1] == sub
error.put("sub", i - 1);
}
mappingTermAndError.put(s2, error);
}
Что он в основном делает, так это получает значение для каждого типа ошибки, а затем вычисляет минимум. если новый минимум равен 1 (так что это первая ошибка), а также одна из предыдущих ячеек в матрице расстояний равна 0 (это означает, что есть путь без ошибок, ведущий к этой точке) или если ошибка транспонирования (что мы можем только знать об этом после того, как у нас уже была ошибка), чем я заменяю ранее зарегистрированную ошибку новой и получаю «i», соответствующий символу, для которого была сделана ошибка.
Я знаю, что это решение довольно уродливое и, вероятно, не очень эффективное, поэтому, если у кого-то есть какие-либо мысли о том, как это улучшить, это было бы здорово.
