下面的类会解析一个非常大的字符串（整部小说文本），并将其分解为连续的 4 字符字符串，这些字符串存储为 Tuple（元组）。 然后，可以根据计算为每个元组分配一个概率。 我正在使用它作为蒙特卡洛/遗传算法的一部分，以训练程序仅基于语法（仅字符转换）来识别一种语言。

我想知道是否有更快的方法来做到这一点。 查找任何给定的 4 字符元组的概率大约需要 400 毫秒。 相关方法_Probablity()位于类的末尾。

这是一个计算密集型问题，与我的另一个帖子有关：用于计算函数合理性的算法/蒙特卡洛方法

最终，我想将这些值存储在一个 4 维矩阵中。 但是，考虑到字母表中有 26 个字母，这将是一项艰巨的任务。（26x26x26x26）。 如果我只取小说的前 15000 个字符，那么性能会大大提高，但我的数据就没那么有用了。

这是解析文本“source”的方法：

    private List<Tuple<char, char, char, char>> _Parse(string src)
    {
        var _map = new List<Tuple<char, char, char, char>>(); 

        for (int i = 0; i < src.Length - 3; i++)
        {
          int j = i + 1;
          int k = i + 2;
          int l = i + 3;

          _map.Add
            (new Tuple<char, char, char, char>(src[i], src[j], src[k], src[l])); 
        }

        return _map; 
    }

这是_Probability方法：

    private double _Probability(char x0, char x1, char x2, char x3)
    {
        var subset_x0 = map.Where(x => x.Item1 == x0);
        var subset_x0_x1_following = subset_x0.Where(x => x.Item2 == x1);
        var subset_x0_x2_following = subset_x0_x1_following.Where(x => x.Item3 == x2);
        var subset_x0_x3_following = subset_x0_x2_following.Where(x => x.Item4 == x3);

        int count_of_x0 = subset_x0.Count();
        int count_of_x1_following = subset_x0_x1_following.Count();
        int count_of_x2_following = subset_x0_x2_following.Count();
        int count_of_x3_following = subset_x0_x3_following.Count(); 

        decimal p1;
        decimal p2;
        decimal p3;

        if (count_of_x0 <= 0 || count_of_x1_following <= 0 || count_of_x2_following <= 0 || count_of_x3_following <= 0)
        {
            p1 = e;
            p2 = e;
            p3 = e;
        }
        else
        {
            p1 = (decimal)count_of_x1_following / (decimal)count_of_x0;
            p2 = (decimal)count_of_x2_following / (decimal)count_of_x1_following;
            p3 = (decimal)count_of_x3_following / (decimal)count_of_x2_following;

            p1 = (p1 * 100) + e; 
            p2 = (p2 * 100) + e;
            p3 = (p3 * 100) + e; 
        }

        //more calculations omitted

        return _final; 
    }
}

编辑 – 我提供更多详细信息以澄清问题。

1) 严格来说，到目前为止我只使用过英语，但确实需要考虑不同的字母表。 目前，我只希望程序能够识别英语，类似于本文中描述的内容：http://www-stat.stanford.edu/~cgates/PERSI/papers/MCMCRev.pdf

2) 我正在计算字符的 n 元组的概率，其中 n <= 4。 例如，如果我正在计算字符串“that”的总概率，我会将其分解为以下独立的元组，并首先单独计算每个元组的概率：

[t][h]

[t][h][a]

[t][h][a][t]

[t][h] 的权重最高，然后是 [t][h][a]，然后是 [t][h][a][t]。 由于我不仅仅将 4 字符元组视为单个单元，因此我无法简单地将文本中 [t][h][a][t] 的实例除以下一个文本中 4 元组的总数。

分配给每个 4 元组的值不能过度拟合文本，因为偶然情况下，许多真正的英语单词可能永远不会出现在文本中，并且它们不应该获得不成比例的低分。 强调一阶字符转换（2 元组）可以缓解这个问题。 移动到 3 元组，然后移动到 4 元组只会细化计算。

我想出了一个字典，它只是统计元组在文本中出现的频率（类似于 Vilx 的建议），而不是重复相同的元组，这会浪费内存。 这使我从每次查找约 ~400 毫秒缩短到每次查找约 ~40 毫秒，这是一个非常大的改进。 但是，我仍然需要研究其他一些建议。

回答：

在你的概率方法中，你迭代了 map 8 次。你的每个 where 都会迭代整个列表，count 也是如此。在末尾添加 .ToList() 可能会加快速度。也就是说，我认为你的主要问题是，你选择存储数据的结构不适合概率方法的目的。你可以创建一个单程版本，其中你存储数据的结构会在插入时计算临时分布。这样，当你完成插入时（这不应该减慢太多），你就完成了，或者你可以像下面的代码一样，在需要时廉价地计算概率。

顺便说一句，你可能需要考虑标点符号和空格。句子的第一个字母/单词和单词的第一个字母清楚地表明给定的文本是用什么语言编写的，通过将标点符号字符和空格作为你分布的一部分，你可以包含样本数据的这些特征。我们几年前就这样做过。这样做我们表明，仅使用三个字符几乎和使用更多字符一样精确（我们在测试数据中使用三个字符没有失败，并且几乎一样精确是一个假设，因为必须有一些奇怪的文本，其中缺乏信息会导致不正确的结果）（我们测试到 7 个字符），但三个字母的速度使其成为最佳选择。

编辑

这是一个我可能会在 C# 中如何做它的示例

class TextParser{
        private Node Parse(string src){
            var top = new Node(null);

            for (int i = 0; i < src.Length - 3; i++){
                var first = src[i];
                var second = src[i+1];
                var third = src[i+2];
                var fourth = src[i+3];

                var firstLevelNode = top.AddChild(first);
                var secondLevelNode = firstLevelNode.AddChild(second);
                var thirdLevelNode = secondLevelNode.AddChild(third);
                thirdLevelNode.AddChild(fourth);
            }

            return top;
        }
    }

    public class Node{
        private readonly Node _parent;
        private readonly Dictionary<char,Node> _children 
                         = new Dictionary<char, Node>();
        private int _count;

        public Node(Node parent){
            _parent = parent;
        }

        public Node AddChild(char value){
            if (!_children.ContainsKey(value))
            {
                _children.Add(value, new Node(this));
            }
            var levelNode = _children[value];
            levelNode._count++;
            return levelNode;
        }
        public decimal Probability(string substring){
            var node = this;
            foreach (var c in substring){
                if(!node.Contains(c))
                    return 0m;
                node = node[c];
            }
            return ((decimal) node._count)/node._parent._children.Count;
        }

        public Node this[char value]{
            get { return _children[value]; }
        }
        private bool Contains(char c){
            return _children.ContainsKey(c);
        }
    }

用法如下：

var top = Parse(src);
top.Probability("test");