#ocr #metrics #levenshtein-distance
#распознавание текста #показатели #левенштейн-расстояние
Вопрос:
Я пытаюсь создать систему оптического распознавания символов со словарем.
На самом деле у меня еще нет реализованного словаря =)
Я слышал, что существуют простые показатели, основанные на расстоянии Левенштейна, которые учитывают разное расстояние между разными символами. Например, ‘N’ и ‘H’ очень близки друг к другу, и d («ТЕАТР», «TNEATRE») должно быть меньше d («ТЕАТР», «TOEATRE»), что невозможно при использовании базового расстояния Левенштейна.
Не могли бы вы помочь мне найти такой показатель, пожалуйста.
Ответ №1:
Возможно, это то, что вы ищете: http://en.wikipedia.org/wiki/Damerau–Levenshtein_distance (и, пожалуйста, в ссылку включен некоторый рабочий код)
Обновить:
http://nlp.stanford.edu/IR-book/html/htmledition/edit-distance-1.html
Комментарии:
1. К сожалению, это не то, что я искал. В любом случае, я уже закончил с отличием — и мне больше не нужно решение =)
2. Это странно, потому что его назначение — это именно то, о чем вы просили.
3. хммм.. Я просмотрел вашу ссылку. Но что я понял, так это то, что они просто добавили еще одну операцию: транспонирование. Где транспозиция — это когда вы меняете два соседних символа. Если я ошибаюсь, не могли бы вы, пожалуйста, указать место на вики-странице, где говорится о разном расстоянии между разными буквами?
4. Извините, я просматривал много ссылок в тот день, вторую нужно рассматривать вместе.
Ответ №2:
Вот пример (C #), где вес операции «заменить символ» зависит от расстояния между кодами символов:
static double WeightedLevenshtein(string b1, string b2) {
b1 = b1.ToUpper();
b2 = b2.ToUpper();
double[,] matrix = new double[b1.Length 1, b2.Length 1];
for (int i = 1; i <= b1.Length; i ) {
matrix[i, 0] = i;
}
for (int i = 1; i <= b2.Length; i ) {
matrix[0, i] = i;
}
for (int i = 1; i <= b1.Length; i ) {
for (int j = 1; j <= b2.Length; j ) {
double distance_replace = matrix[(i - 1), (j - 1)];
if (b1[i - 1] != b2[j - 1]) {
// Cost of replace
distance_replace = Math.Abs((float)(b1[i - 1]) - b2[j - 1]) / ('Z'-'A');
}
// Cost of remove = 1
double distance_remove = matrix[(i - 1), j] 1;
// Cost of add = 1
double distance_add = matrix[i, (j - 1)] 1;
matrix[i, j] = Math.Min(distance_replace,
Math.Min(distance_add, distance_remove));
}
}
return matrix[b1.Length, b2.Length] ;
}
Вы видите, как это работает здесь: http://ideone.com/RblFK
Ответ №3:
Опоздание на несколько лет, но следующий пакет python (с которым я НЕ связан) позволяет произвольно взвешивать все операции редактирования Левенштейна и сопоставления символов ASCII и т.д.
https://github.com/infoscout/weighted-levenshtein
pip install weighted-levenshtein
Также этот (также не связанный):
https://github.com/luozhouyang/python-string-similarity
Комментарии:
1. Требуется ли для этого создавать матрицу полного веса? Кто-нибудь знает, существует ли какая-либо разумная матрица весов для базовых символов ascii, например? Не обязательно должно быть идеальным, но в основном имеет меньший вес для таких вещей, как [o O 0] или [i l 1], и больший для таких вещей, как [o x].
2. Вам нужно заполнить каждый элемент матрицы чем -то, даже некоторым значением по умолчанию. Ваши примеры зависят от распознавания текста; вводимые с клавиатуры элементы будут другими. Проблема в том, что нужны достоверные данные, то есть помеченные данные, которые трудоемки, поэтому компании неохотно делятся. Примером может служить reCAPTCHA.
3. Что ж, существует множество ресурсов с открытым исходным кодом, таких как Tesseract, который является полностью открытым механизмом распознавания текста с обученными данными. В нем даже есть список неоднозначных символов: github.com/tesseract-ocr/langdata/blob/master/eng/… Тем не менее, поскольку распознавание текста выполняется так широко, я все еще удивлен, что чего-то подобного не существует в сообществе OSS.
Ответ №4:
Недавно я создал пакет Python, который делает именно это https://github.com/zas97/ocr_weighted_levenshtein .
В моей реализации Weigthed-Levenshtein расстояние между «ТЕАТРОМ» и «TNEATRE» равно 1,3, в то время как расстояние между «ТЕАТРОМ» и «TOEATRE» равно 1,42.
Другими примерами являются значения d («O», «0»), равные 0,06, и d («e», «c»), равные 0,57.
Эти расстояния были рассчитаны путем запуска нескольких методов распознавания в синтетическом наборе данных и составления статистики по наиболее распространенным ошибкам распознавания. Я надеюсь, что это кому-то поможет =)