c# - 寻找一种方法来优化此算法以解析非常大的字符串

Question

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

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

这是一个与我的另一篇文章相关的计算密集型问题:Algorithm for computing the plausibility of a function / Monte Carlo Method

最终我想将这些值存储在一个 4d 矩阵中。但鉴于字母表中有 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 <= 4 字符的 n 元组的概率。例如，如果我正在计算字符串“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 元组的值不能与文本过拟合，因为很多真正的英语单词可能永远不会出现在文本中，它们不应该得到不成比例的低分。强调一阶字符转换(二元组)可以改善这个问题。移动到 3 元组，然后是 4 元组只是改进了计算。

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

Answer 1

在 yoiu 概率方法中，您将 map 迭代 8 次。您的每个位置都会迭代整个列表，计数也是如此。在末尾添加 .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");