1

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

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

这是与我的另一篇文章相关的计算密集型问题：计算函数的合理性的算法/蒙特卡洛方法

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

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

    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 的字符元组的概率。例如，如果我正在计算字符串“that”的总概率，我会将其分解为这些独立的元组并计算每个元组的概率首先单独：

[吨][小时]

[t][h][a]

[那]

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

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

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

4

5 回答 5

1

就目前的 parse 函数而言，您无能为力。但是，元组似乎是来自大量文本的四个连续字符。为什么不直接用 int 替换元组，然后在需要字符值时使用 int 来索引大量文本。您的基于元组的方法实际上消耗了原始文本将使用的内存的四倍，并且由于内存通常是性能的瓶颈，因此最好尽可能少地使用。

然后，您尝试查找文本正文中与一组字符的匹配数。我想知道对原始文本正文的直接线性搜索与您正在使用的 linq 语句相比如何？将.Where进行内存分配（这是一个缓慢的操作）并且 linq 语句将具有解析开销（但编译器可能会在这里做一些聪明的事情）。对搜索空间有很好的理解将更容易找到最佳算法。

但是，正如评论中提到的，使用 26 4矩阵将是最有效的。解析一次输入文本并在解析时创建矩阵。您可能需要一组字典：

SortedDictionary <int,int> count_of_single_letters; // key = single character
SortedDictionary <int,int> count_of_double_letters; // key = char1 + char2 * 32
SortedDictionary <int,int> count_of_triple_letters; // key = char1 + char2 * 32 + char3 * 32 * 32
SortedDictionary <int,int> count_of_quad_letters;   // key = char1 + char2 * 32 + char3 * 32 * 32 + char4 * 32 * 32 * 32

最后，关于数据类型的说明。您正在使用该decimal类型。这不是一种有效的类型，因为没有直接映射到 CPU 本机类型，并且在处理数据时存在开销。改用双精度，我认为精度就足够了。最精确的方法是将概率存储为两个整数，分子和分母，然后尽可能晚地进行除法。

于 2011-09-19T08:02:28.343 回答
1

例如，这里最好的方法是在每个 10000 个字符之后使用稀疏存储和修剪。在这种情况下，最好的存储结构是前缀树，它将允许快速计算概率、更新和稀疏存储。您可以在此 javadoc http://alias-i.com/lingpipe/docs/api/com/aliasi/lm/NGramProcessLM.html中找到更多理论

于 2011-09-19T11:45:32.173 回答
1

在 yoiu 概率方法中，您将地图迭代 8 次。您的每个 where 都会迭代整个列表，计数也是如此。在结尾添加 .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");
于 2011-09-19T07:37:38.530 回答
1

我建议更改数据结构以使其更快...

我认为 aDictionary<char,Dictionary<char,Dictionary<char,Dictionary<char,double>>>>会更有效率，因为您将在计算时访问每个“级别”（Item1...Item4）......并且您会将结果缓存在最里面Dictionary，因此下次您根本不必计算..

于 2011-09-19T07:15:12.170 回答
1

好的，我没有时间制定细节，但这确实需要

  • 神经分类器网络（只需将任何现成的，甚至Controllable Regex Mutilator可以以更大的可扩展性方式完成这项工作）——启发式而不是蛮力

  • 您可以使用尝试（Patricia Tries aka Radix Trees来制作可以稀疏的数据结构的空间优化版本（Dictionaries of Dictionaries of Dictionaries ... 对我来说看起来像是这个的近似值）

于 2011-09-19T07:50:13.413 回答