用于序列校正的 N-Gram

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-gram 的频率来自动校正序列，第一个样本将变为

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

我会收集这些 n-gram 校正的频率，并且我正在寻找了解一种计算纠正样本数据中可能存在或不存在的新输入的最佳方法的方法。

这似乎与 SMT 类似。

Answer 1

根据替换的长度和出现的次数，为已知的替换分配一个分数。 天真地，我建议使这个分数与长度的平方（在我能想到的大多数情况下，越长的匹配越罕见）和出现次数的平方根成正比，这样 4 项序列就有同样多的权重作为出现次数为 16 次的 2 项序列。 这个需要根据自己的实际情况进行调整。

给定长度为 M 的序列，有 N 个长度为 1 到 M 的子字符串，其中 N=M*(M+1)/2，因此如果字符串相当短，那么您可以迭代每个子字符串并查找可能的替换。 我认为，用这些子字符串组成整个字符串的方法数量也与 M^2 成正比。

对于原始字符串由子字符串组成的每种可能的组合，将每个子字符串的最佳（最高分数）替换的总分相加。

总分最高的作品将（可能，考虑到我对过程的假设）替换后的“最佳”结果。