OCR: взвешенное расстояние Левенштейна - PullRequest
Новая
       8

OCR: взвешенное расстояние Левенштейна

5 голосов
/ 21 мая 2011

Я пытаюсь создать оптическую систему распознавания символов со словарем.

На самом деле у меня еще нет реализованного словаря =)

Я слышал, что естьпростые метрики, основанные на расстоянии Левенштейна, которые учитывают различное расстояние между различными символами.Например, 'N' и 'H' очень близки друг к другу, и d ("THEATER", "TNEATRE") должно быть меньше d ("THEATER", "TOEATRE"), что невозможно при использовании базового расстояния Левенштейна.

Не могли бы вы помочь мне найти такую ​​метрику, пожалуйста.

Резервуары для внимания.

Ответы [ 2 ]

4 голосов
/ 13 июля 2011

Это может быть то, что вы ищете: http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance (и, пожалуйста, какой-то рабочий код включен в ссылку)

Обновление:

http://nlp.stanford.edu/IR-book/html/htmledition/edit-distance-1.html

1 голос
/ 11 сентября 2012

Вот пример (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

...