Нечеткое соответствие нескольких слов в строке

Я пытаюсь использовать Расстояние Левенштейна, чтобы найти нечеткие ключевые слова (статический текст) в OCR. page.
Для этого я хочу указать процент допустимых ошибок (скажем, 15%).

string Keyword = "past due electric service";

Поскольку ключевое слово имеет длину 25 символов, я хочу допустить 4 ошибки (25 * .15 с округлением вверх)
Мне нужно иметь возможность сравнить его с...

string Entire_OCR_Page = "previous bill amount payment received on 12/26/13 thank 
                          you! current electric service total balances unpaid 7 
                          days after the total due date are subject to a late 
                          charge of 7.5% of the amount due or $2.00, whichever/5 
                          greater. "

Вот как я это делаю сейчас...

int LevenshteinDistance = LevenshteinAlgorithm(Keyword, Entire_OCR_Page); // = 202   
int NumberOfErrorsAllowed = 4;   
int Allowance = (Entire_OCR_Page.Length() - Keyword.Length()) + NumberOfErrorsAllowed; // = 205

Ясно, что Keyword не найдено в OCR_Text (чего быть не должно). Но, используя расстояние Левенштейна, количество ошибок меньше, чем запас в 15% (поэтому моя логика говорит, что оно найдено).

Кто-нибудь знает лучший способ сделать это?


c# ocr fuzzy-search levenshtein-distance
person Milne    schedule 06.02.2014    source источник
comment
Написал лучший вопрос. goo.gl/Rb6ejp   -  person Milne    schedule 07.02.2014

Ответы (2)


arrow_upward
1
arrow_downward

Ответил на мой вопрос с использованием подстрок. Публикация на случай, если другие столкнутся с такой же проблемой. Немного неортодоксально, но на мне работает отлично.

int TextLengthBuffer = (int)StaticTextLength - 1; //start looking for correct result with one less character than it should have.
int LowestLevenshteinNumber = 999999; //initialize insanely high maximum
decimal PossibleStringLength = (PossibleString.Length); //Length of string to search
decimal StaticTextLength = (StaticText.Length); //Length of text to search for
decimal NumberOfErrorsAllowed = Math.Round((StaticTextLength * (ErrorAllowance / 100)), MidpointRounding.AwayFromZero); //Find number of errors allowed with given ErrorAllowance percentage

    //Look for best match with 1 less character than it should have, then the correct amount of characters.
    //And last, with 1 more character. (This is because one letter can be recognized as 
    //two (W -> VV) and visa versa) 

for (int i = 0; i < 3; i++) 
{
    for (int e = TextLengthBuffer; e <= (int)PossibleStringLength; e++)
    {
        string possibleResult = (PossibleString.Substring((e - TextLengthBuffer), TextLengthBuffer));
        int lAllowance = (int)(Math.Round((possibleResult.Length - StaticTextLength) + (NumberOfErrorsAllowed), MidpointRounding.AwayFromZero));
        int lNumber = LevenshteinAlgorithm(StaticText, possibleResult);

        if (lNumber <= lAllowance && ((lNumber < LowestLevenshteinNumber) || (TextLengthBuffer == StaticText.Length && lNumber <= LowestLevenshteinNumber)))
        {
            PossibleResult = (new StaticTextResult { text = possibleResult, errors = lNumber });
            LowestLevenshteinNumber = lNumber;
        }
    }
    TextLengthBuffer++;
}




public static int LevenshteinAlgorithm(string s, string t) // Levenshtein Algorithm
{
    int n = s.Length;
    int m = t.Length;
    int[,] d = new int[n + 1, m + 1];

    if (n == 0)
    {
        return m;
    }

    if (m == 0)
    {
        return n;
    }

    for (int i = 0; i <= n; d[i, 0] = i++)
    {
    }

    for (int j = 0; j <= m; d[0, j] = j++)
    {
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

            d[i, j] = Math.Min(
                Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                d[i - 1, j - 1] + cost);
        }
    }
    return d[n, m];
}
person Milne    schedule 11.02.2014

arrow_upward
0
arrow_downward

Я думаю, что это не работает, потому что большая часть вашей строки совпадает. Так что я бы сделал, это попробовать разбить ваше ключевое слово на отдельные слова.

Затем найдите все места, где эти слова совпадают в вашем OCR_TEXT.

Затем посмотрите на все те места, где они совпали, и посмотрите, являются ли какие-либо 4 из этих мест последовательными и соответствуют исходной фразе.

Не уверен, понятно ли мое объяснение?

person Jim W says reinstate Monica    schedule 06.02.2014
comment
Если я правильно понял ваш ответ, я бы потерял возможность объявлять NumberOfErrorsAllowed. нет? - person Milne; 07.02.2014
comment
Да и нет; это будет за слово. - person Jim W says reinstate Monica; 07.02.2014
comment
За слово не получится. Одним словом может быть я, и если оно распознается как 1, я теряю результат. Смотрите ответ, который я придумал. Спасибо - person Milne; 12.02.2014