N-граммы для исправления последовательности

Question

Извините за сложный вопрос.

У меня есть большой набор последовательностей, которые нужно исправить, добавив цифры или заменив их (никогда не удаляя ничего), что выглядит следующим образом:

• 1,2, 3 => 1,7,4,3
• 4,, 5,6 => 4,4,5,6
• 4,7,8,9 => 4,7,8,9,1
• 4,7 => 4,8
• 4,7,1 => 4,7,2

Начинается с дополненной исходной последовательности и сэмплированной коррекции.

Я хотел бы иметь возможность работать над автоматическим исправлением последовательностей, вычисляя частоты различных исправляемых n-грамм, первая выборка станет

• 1 => 1
• 3 => 3
• 1,2 => 1,7
• 2,3 => 7,4,3
• 1,2,3 => 1,7,4,3

Я бы собрал частоту этих поправок в n-граммах, и я ищу способ рассчитать лучший способ исправить новый вход, который может или не может быть в данных выборки.

Это похоже на SMT .

Answer 1

Назначьте оценку известным заменам на основе продолжительности замены и количества вхождений. Наивно, я бы предложил сделать эту оценку пропорциональной квадрату длины (более длинные совпадения реже, в большинстве сценариев, о которых я могу думать) и квадратному корню из числа вхождений, так что последовательность из 4 элементов имеет такой же вес как последовательность из 2 элементов, которая встречается в 16 раз чаще. Это должно быть скорректировано в зависимости от вашей реальной ситуации.

При заданной последовательности длины M имеется N подстрок длиной от 1 до M, где N = M * (M + 1) / 2, поэтому, если строки достаточно короткие, вы можете перебрать каждую подстроку и посмотреть возможные замены. Я думаю, что количество способов составить целую строку из этих подстрок пропорционально M ^ 2.

Для каждой возможной композиции исходной строки по подстрокам суммируйте общий балл лучшей (самой высокой) замены для каждой подстроки.

Композиция с наивысшей общей оценкой будет (потенциально, учитывая мои предположения о процессе) «лучшим» результатом после замены.