лення символу S1 [i]
для всіх j від 1 до N (i, j) = min ((i-1, j) + ціна видалення символу S1 [i], (i, j-1) + ціна вставки символу S2 [j], (i-1, j-1) + ціна заміни символу S1 [i] на символ S2 [j]
повернути D (M, N)
Для відновлення редакційного приписи потрібно обчислити матрицю D, після чого йти з правого нижнього кута (M, N) у лівий верхній, на кожному кроці шукаючи мінімальне з трьох значень:
В· якщо мінімально (D (i-1, j) + ціна видалення символу S1 [i]), додаємо видалення символу S1 [i] і йдемо в (i -1, j)
В· якщо мінімально (D (i, j-1) + ціна вставки символу S2 [j]), додаємо вставку символу S1 [i] і йдемо в (i , j-1)
В· якщо мінімально (D (i-1, j-1) + ціна заміни символу S1 [i] на символ S2 [j]), додаємо заміну S1 [ i] на S2 [j] (якщо вони не рівні; інакше нічого не додаємо), після чого йдемо в (i-1, j-1)
Тут (i, j) - клітина матриці, в якій ми знаходимося на даному кроці. Якщо мінімальні два з трьох значень (або рівні всі три), це означає, що є 2 або 3 рівноцінних редакційних приписи. br/>
Різні моделі помилок опечаточніков
Одна з перших згадок про проблематику виправлення орфографічних помилок можна знайти в роботі Дамер [1]. У ній корекція помилок припускає пошук певного слова у еталонному словнику й у випадку, якщо, немає у словнику, то пропонуються близькі варіанти. p align="justify"> У разі пошуку по Web для корекції помилок у запитах варіант ручної перевірки малоефективний, тому використовується статистична мовна модель на основі запитів користувачів. Даний підхід простий, але недостатньо ефективний. Відзначається, що якщо дані містять друкарські помилки, то опечаточнік не буде їх виправляти. Ерік Брілл і Роберт Мур пропонують вирішити цю проблему за допомогою більш складної моделі помилок. p align="justify"> Варіанти з використанням моделі помилок описані в роботах Цобеля і Дарта [2] [3]. У них описується, що модель помилок враховує кілька параметрів: статистичні дані про реальні друкарських помилках, фонетичну близькість слів, а так само близькість на клавіатурі. Вони також проводили порівняння алгоритмів аналізу рядків з вимови, і відзначили, що цей варіант, погано підходить для загальної задачі корекції помилок. p align="justify"> Крім моделі помилок хорошим засобом підвищення якості роботи опечаточніка є використання контексту. Суть методу полягає в аналізі слів використовуються по-сусідству з перевіряється. Але для побудови контекстної розширеної моделі потрібні значні обсяги даних. p align="justify"> Незважаючи на наявність розширеної моделі мови і достатньо повною і точною моделі помилок, залишаються слова з друкарською помилкою, які не можуть виправитися, бо їх рейтинг в моделі мови занадто ...
