Исправление текста: как получить LCS для возможно усеченного текста? - PullRequest
Новая
       5

Исправление текста: как получить LCS для возможно усеченного текста?

0 голосов
/ 01 февраля 2020

Я работаю над некоторым программным обеспечением, которое должно использоваться для исправления надиктованного текста по сравнению с его оригинальным сценарием.

Звук диктовки может быть приостановлен, ускорен или замедлен в любое время, но есть ограничение по времени для транскрипции и звука длиннее, поэтому, если транскрибер не сильно ускоряет звук, текст определенно обрезается.

Я обнаружил, что алгоритм LCS работает исключительно хорошо, чтобы найти различия до 90% транскрибированного текста, или даже до 100%, если транскрибер не делает никакой ошибки в конце файла, но если они это делают, это становится беспорядком. Скажем, что транскрибер добавляет слово, которого не было в исходном тексте, и по чистой случайности это слово является последним в файле. Вместо того, чтобы считать это слово как добавленное, алгоритм попытается «оправдать» его, найдя все его буквы в различных частях усеченного текста. Например, если конкурент добавляет «дом», алгоритм может выбрать первый H, который он найдет, затем первый O после этого, первый U и так далее, пока он не завершит слово «дом».

Хотя это поведение, по определению, корректно для алгоритма LCS - он пытается создать подпоследовательность как можно дольше - это вызывает проблему. Мое программное обеспечение должно удалить ту часть текста, которая вообще не была напечатана, то есть оно должно выяснить, в какой момент транскрибер прекратил запись, и ничего после этого не считать ошибкой. Единственный способ сделать это - найти последовательные пропущенные символы от конца вплоть до последней ошибки, которая не является пропущенным или первым правильным символом. Однако, поскольку алгоритм пытается получить так много букв из разных слов, которые пришли после того, как транскрибер прекратил печатать, он пометит эти буквы как правильные, хотя они уже далеко от фактического конца транскрибированной части. Следовательно, я смогу удалить только часть текста, который не был напечатан, выдав окончательную разницу, включающую много текста, который не следует считать неправильным.

Пример: текст «I живу в большом городе посреди россии ". Транскрибер пишет: «Я живу в большом беспорядке». Желаемое поведение будет таким: «Я живу в большом» - это правильно, «беспорядок» был вставлен неправильно, а «город посреди России» не расшифровывается и будет игнорироваться. Вместо этого LCS возвращает это: «Я живу в большом» - это правильно, «город в» отсутствует, «m» - это правильно, «iddl» отсутствует, «e» - это правильно, «of Ru» отсутствует, «ss» правильно, «ia» не расшифровывается и будет игнорироваться. Другими словами, транскрибер только набрал 4 неправильных буквы, но программа будет считать 22.

Мне было интересно, есть ли какой-нибудь алгоритм, более подходящий для этой задачи, или если у кого-либо из вас есть какие-либо предложения противодействовать этому поведению и держать LCS. Я не уверен, что это может помочь, но я включу C# алгоритм, который я использую для вычисления графа LCS. 

private static Direction[,] Difference(List<Word> officialWords, List<Word> competitorWords, out int[,] array, bool wordMode = true)
    {
        array = new int[officialWords.Count + 1, competitorWords.Count + 1];
        Direction[,] directions = new Direction[officialWords.Count + 1, competitorWords.Count + 1];

        for (int i = 1; i <= officialWords.Count; i++)
        {
            for (int j = 1; j <= competitorWords.Count; j++)
            {
                int left = array[i, j - 1], up = array[i - 1, j], upLeft = array[i - 1, j - 1] + 1;

                if (officialWords[i - 1].Equals(competitorWords[j - 1])
                    && left < upLeft && up < upLeft)
                {
                    array[i, j] = upLeft;
                    directions[i, j] = Direction.UpLeft;
                }
                else
                {
                    if (up > left)
                    {
                        array[i, j] = up;
                        directions[i, j] = Direction.Up;
                    }
                    else
                    {
                        array[i, j] = left;
                        directions[i, j] = Direction.Left;
                    }
                }
            }
        }

        return directions;
    }
...