- PVSM.RU - https://www.pvsm.ru -
После посещения Yet another Conference 2013 у меня возникла идея написать API для всех сервисов яндекс лингвистики под .NET. После недлительного гугления, таких библиотек к счастью не оказалось. Несмотря на то, что может она никому особо и не понадобится, я все же решил реализовать ее хотя бы для того, чтобы попрактиковаться с RestSharp [1], тестированием и различными функциями гитхаба (issuers, release, markdown и др.). Кроме того, в процессе реализации пришлось столкнуться с интересным алгоритмом сравнения строк, о котором я упомяну в топике.
Сразу кидаю ссылки на исходники и бинарики на GitHub: Code [2], Binary [3]
RestSharp позволяет очень легко писать код для синхронных и асинхронных HTTP GET и POST запросов, а также преобразовывать полученные ответы в формате XML или JSON в .NET объекты (в данном проекте использовался XML).
В процессе реализации спеллера мне захотелось, чтобы пользователю отображался не только исправленный вариант текста, но и ошибки в нем. В голову сразу пришла мысль о расстоянии Левейштейна [8]. Однако:
Первый недостаток был нивелирован с помощью расстояния Дамерау—Левенштейна [9], а второй — с помощью анализа матрицы, полученной в процессе работы алгоритма (расстояние — это значение элемента последнего ряда в последнем столбце матрицы. Соответственно в моем случае расстоянием будет общее количество ошибок, возвращенной этой функцией).
Таким образом были реализован алгоритм для поиска следующих ошибок в ошибочном (word) и корректном (correctedWord) словах:
Кроме того, веса различных ошибок могут настраиваться (по-умолчанию все имеют одинаковый вес, равный единице).
public static List<Mistake> DamerauLevenshteinDistance(
string word, string correctedWord,
bool transposition = true,
int substitutionCost = 1,
int insertionCost = 1,
int deletionCost = 1,
int transpositionCost = 1)
{
int w_length = word.Length;
int cw_length = correctedWord.Length;
var d = new KeyValuePair<int, CharMistakeType>[w_length + 1, cw_length + 1];
var result = new List<Mistake>(Math.Max(w_length, cw_length));
if (w_length == 0)
{
for (int i = 0; i < cw_length; i++)
result.Add(new Mistake(i, CharMistakeType.Insertion));
return result;
}
for (int i = 0; i <= w_length; i++)
d[i, 0] = new KeyValuePair<int, CharMistakeType>(i, CharMistakeType.None);
for (int j = 0; j <= cw_length; j++)
d[0, j] = new KeyValuePair<int, CharMistakeType>(j, CharMistakeType.None);
for (int i = 1; i <= w_length; i++)
{
for (int j = 1; j <= cw_length; j++)
{
bool equal = correctedWord[j - 1] == word[i - 1];
int delCost = d[i - 1, j].Key + deletionCost;
int insCost = d[i, j - 1].Key + insertionCost;
int subCost = d[i - 1, j - 1].Key;
if (!equal)
subCost += substitutionCost;
int transCost = int.MaxValue;
if (transposition && i > 1 && j > 1 && word[i - 1] == correctedWord[j - 2] && word[i - 2] == correctedWord[j - 1])
{
transCost = d[i - 2, j - 2].Key;
if (!equal)
transCost += transpositionCost;
}
int min = delCost;
CharMistakeType mistakeType = CharMistakeType.Deletion;
if (insCost < min)
{
min = insCost;
mistakeType = CharMistakeType.Insertion;
}
if (subCost < min)
{
min = subCost;
mistakeType = equal ? CharMistakeType.None : CharMistakeType.Substitution;
}
if (transCost < min)
{
min = transCost;
mistakeType = CharMistakeType.Transposition;
}
d[i, j] = new KeyValuePair<int, CharMistakeType>(min, mistakeType);
}
}
int w_ind = w_length;
int cw_ind = cw_length;
while (w_ind >= 0 && cw_ind >= 0)
{
switch (d[w_ind, cw_ind].Value)
{
case CharMistakeType.None:
w_ind--;
cw_ind--;
break;
case CharMistakeType.Substitution:
result.Add(new Mistake(cw_ind - 1, CharMistakeType.Substitution));
w_ind--;
cw_ind--;
break;
case CharMistakeType.Deletion:
result.Add(new Mistake(cw_ind, CharMistakeType.Deletion));
w_ind--;
break;
case CharMistakeType.Insertion:
result.Add(new Mistake(cw_ind - 1, CharMistakeType.Insertion));
cw_ind--;
break;
case CharMistakeType.Transposition:
result.Add(new Mistake(cw_ind - 2, CharMistakeType.Transposition));
w_ind -= 2;
cw_ind -= 2;
break;
}
}
if (d[w_length, cw_length].Key > result.Count)
{
int delMistakesCount = d[w_length, cw_length].Key - result.Count;
for (int i = 0; i < delMistakesCount; i++)
result.Add(new Mistake(0, CharMistakeType.Deletion));
}
result.Reverse();
return result;
}
Интерфейс был реализован на WinForms с надеждой, что приложение будет запускаться и на Mono. Однако на нем тестирование не проводилось.
Данную библиотеку можно использовать в любых проектах, но с указанием авторства (Apache 2.0).
Автор: KvanTTT
Источник [10]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/open-source/50746
Ссылки в тексте:
[1] RestSharp: http://restsharp.org/
[2] Code: https://github.com/KvanTTT/Yandex-Linguistics.NET
[3] Binary: https://github.com/KvanTTT/Yandex-Linguistics.NET/releases/download/1.0/YandexLinguistics.NET.7z
[4] Яндекс.Предиктор.: http://api.yandex.ru/predictor/
[5] Яндекс.Словарь.: http://api.yandex.ru/dictionary/
[6] Яндекс.Перевод.: http://api.yandex.ru/translate/
[7] Яндекс.Спеллер.: http://api.yandex.ru/speller/
[8] расстоянии Левейштейна: http://en.wikipedia.org/wiki/Levenshtein_distance
[9] расстояния Дамерау—Левенштейна: http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
[10] Источник: http://habrahabr.ru/post/204372/
Нажмите здесь для печати.