如何用C#在文本中找到反复出现的词组？

Question

我在StringBuilder(sb)中得到了反复出现的单词计数，我在互联网上找到了这段代码，根据作者的说法，这与word的单词计数器是一致的。

StringBuilder wordBuffer = new StringBuilder();
        int wordCount = 0;
        // 1. Build the list of words used. Consider ''' (apostrophe) and '-' (hyphen) a word continuation character.
        Dictionary<string, int> wordList = new Dictionary<string, int>();
        foreach (char c in sb.ToString())
        {

            if (char.IsLetter(c) || c == '\'' || c == '-')
            {
                wordBuffer.Append(char.ToLower(c));
            }
            else
            {
                if (wordBuffer.Length > 3)
                {
                    int count = 0;
                    string word = wordBuffer.ToString();
                    wordList.TryGetValue(word, out count);
                    wordList[word] = ++count;

                    wordBuffer.Clear();
                    wordCount++;
                }
            }
        }

这是我的样本文本：

绿藻(单数:绿藻)是由绿藻和轮藻组成的大型、非正式的藻类群。陆地植物或胚芽植物(高等植物)被认为是从轮藻中产生的。1由于胚性植物不是藻类，因此被排除在外，绿藻是一个骨干类群。然而，包含绿藻和胚性植物的clade是单系的，被称为clade Viridiplantae和王国Plantae。绿藻包括单细胞和殖民地鞭毛，大多数每个细胞有两根鞭毛，还有各种殖民地、球虫和丝状，以及宏观的、多细胞的海藻。在高等植物的近缘植物Charales中，组织的细胞分化完全发生。绿藻约有8,000种。2许多种以单细胞的形式生活，而其他种类则形成长丝状或高度分化的宏观海藻。其他一些生物依靠绿藻来进行光合作用。绿藻和绿藻中的叶绿体都是从食用的绿藻中获得的，在绿藻中保留着一个核形体(残留核)。绿藻也是共生的发现在纤毛虫副卵细胞，在九头蛇病毒和扁虫。一些绿藻，特别是Trebouxiophyceae和Trentepohlia属( Ulvophyceae)，与真菌共生，形成地衣。一般来说，与地衣共生的真菌物种不能靠自己生存，而藻类物种通常在没有真菌的情况下生活在自然中。三叶藻是一种丝状绿色藻类，可以独立生活在湿润的土壤、岩石或树皮上，也可以在壁虎科地衣中形成光共生体。

在我的示例文本中，我得到了绿色和藻类单词，如预期的那样出现在第一行中。

问题是，我不需要单个单词，我也需要单词组。在这个示例文本中，我还需要绿藻单词，以及green和单词。

我的可选问题是:我需要高性能地做这件事，因为文本可能很长。正如我所研究的，在这种情况下使用RegEx并不是很高的性能，但我不确定是否有第二种方法使其成为可能。

提前谢谢。

UPDATE --如果你知道我要问的内容，你不需要读这些行。

由于我看到太多关于我的“组”定义的评论还不清楚，我认为我需要更详细地陈述我的观点，我希望在评论部分写这些行，但这是一个很窄的区域。首先，我知道StackOverflow不是一种编码服务。我试图在一篇文章中找到最常用的单词组，并试图决定文章的内容，我们也可以把它称为标记生成器。为了这个目的，我试着找出最常用的词，一开始没问题。然后我意识到这不是一个决定主题的好方法，因为我不能假设这篇文章只是关于第一个或第二个单词。在我的例子中，我不能说这篇文章仅仅是关于green或藻类的，因为它们在这里意味着一些东西，而不是单独的。如果我用一篇关于像“海伦娜·博汉姆·卡特”这样的三位名人的文章(如果我假设它是写在文章上的全名，而不仅仅是姓氏)，我想把这些词一个接一个地放在一起。我正试图实现更聪明的算法，即用最精确的方式和一次尝试猜出主题。我不想限制计数这个词，因为文章可能是关于“联合国工业发展组织”的(我再一次假设它现在写得像文章中的“工发组织”)。我可以通过试着让每个单词组从任何索引开始到文本末尾的任意长度来实现这一点。好吧，这真的不是个好办法，尤其是长的短信，但也不是不可能的，对吧？但是我正在寻找一种更好的方法来做这件事，我只是问到一个更好的算法思想和最好的工具，我可以自己编写代码。我希望我终于明确了我的目标。

Answer 1

我认为这是相当有效的。

var text = @"The green algae (singular: green alga) are ..."; // include all your text

var remove = "().,:[]0123456789".Select(x => x.ToString()).ToArray();

var words =
    Regex
        .Matches(text, @"(\S+)")
        .Cast<Match>()
        .SelectMany(x => x.Captures.Cast<Capture>())
        .Select(x => remove.Aggregate(x.Value, (t, r) => t.Replace(r, "")))
        .Select(x => x.Trim().ToLowerInvariant())
        .Where(x => !String.IsNullOrWhiteSpace(x))
        .ToArray();

var groups =
    from n1 in Enumerable.Range(0, words.Length)
    from n2 in Enumerable.Range(1, words.Length - n1)
    select String.Join(" ", words.Skip(n1).Take(n2));

var frequencies =
    groups
        .GroupBy(x => x)
        .Select(x => new { wordgroup = x.Key, count = x.Count() })
        .OrderByDescending(x => x.count)
        .ThenBy(x => x.wordgroup.Count(y => y == ' '))
        .ThenBy(x => x.wordgroup)
        .ToArray();

这给了我每一个单词分组的频率，连续的单词序列，包括最多一个单词组的所有单词。

字数是288。单词组的总数是288 x (288 + 1) / 2 = 41,616。单词组的最后数(对重复的单词组进行分组并删除空/空格字符串之后)为41,449。

以下是这41,449人中的头100人：

20 x“、13 x”和“、12 x”藻类“、12 x”在“、11 x”绿色“、10 x”、9 x“”绿藻“、8 x为”、6 x“为”、6 x“、5 x "a”、4 x“是”、4 x或“4 x "to”3 x“、3 x "form”、3 x "found“、3 x "lichens”、3 x "live“、3 x "on”、3“植物”，3 x“a”，3 x“藻类”和“3 x”，在“3x”中“，3 x”为“，3 x”，2 x "alga"，2 x "can"，2 x "clade"，2 x "class"，2 x“殖民地”，2 x“丝状”，2 x“来自”，2 x“较高”，2 x“宏观”，2 x“最”，2 x“其他”，2 x“海藻”，2 x“他们”，2 x "trentepohlia"，2“时间”，2 x，2 x“藻类是”，2 x“绿藻”，2 x“绿藻”，2 x“在地衣”，2 x“绿色”，2 x“种类”，2 x“clade"，2 x”绿藻“，2 x”绿藻和“，2 x”绿藻“，2 x”绿色“，2 x”绿藻“，2 x”绿藻“，1 x”关于“，1”获得“，1 x“藻类”、1 x“还”、1 x“连”、1 x“树皮”、1 x "be“、1 x”两者“、1 x”不能“、1 x”细胞“、1 x "charales”、1 x“轮藻”、1 x“轮藻”、1 x“绿藻”、1 x“叶绿素”、1 x“叶绿体”、1 x“纤毛虫”、1 x“最近”、1 x "coccoid“、1 x "coenobia”、1 x“菌落”、1 x“行为”，1 x“包括”、1 x“分化”、1 x“分化”、1 x“分裂”、1 x“出现”、1 x“正常”、1 x“排除”、1 x“家庭”、1 x“数”、1 x“丝”、1 x“鞭毛”、1 x“鞭毛”、1 x“扁平虫”、1 x“形态”、1 x“完整”、1 x“真菌”、1 x“真菌”

Answer 2

实现这一目标的方法是获取初始文本，并使用string.split(' ');将其按空格拆分为字符串数组。

接下来，您需要遍历数组中的每个字符串。这对于单个单词来说很容易，但对于组来说则更复杂。因此，您需要定义组大小。您必须控制指针在每次迭代中前进的数组中的位置数。

一旦您能够迭代数组，您就需要获取一组单词(不管您选择它的时间有多长)，并将其存储在某个地方。在这个例子中你的字典是一个很好的方法。

如果字典包含单词组，则将其值增加一个。如果它不包含组，只需添加默认值1。

 if (wordList.ContainsKey(theKey)) {
   wordList[theKey]++;
 } else {
   wordList.Add(theKey, 1);
 }

您确实正确地提到，您的研究表明regex不是高性能的。对于这个任务，regex是完全错误的工具--您不是在寻找模式，而是在检查组。为此，您必须从头到尾检查文本，检查值。

任何涉及迭代文本并在其上运行重复函数的任务都不应该使用regex。

编辑:我最初对Regex性能的假设是不正确的--在C#中，它似乎比在Java中快得多，但我仍然坚持认为，纯正则表达式不如使用regex来标记文本，然后使用循环或linq表达式查找组。

他汀

@galakt，就像我上面提到的，比如说3，这有关系吗？

一个词组的概念是完全抽象的。是的，这是一组词，但整块文字是一组词。必须运用规则来指导你对这一组词的行为。

下面是一个示例方法，它将根据通过方法调用传递的大小返回所有单词组的字典。它不会从文本中删除任何非字母数字字符，但它是快速的，即使具有更大的组大小。

要调用它，请使用Dictionary<String, int> SingleWordGroups = GetWordGroupInstances(1);

    private Dictionary<String, int> GetWordGroupInstances(int GroupSize) {

        Dictionary<String, int> WordGroupInstances = new Dictionary<string, int>();

        //Grab the string to work from...
        String[] sourceText = GetSourceText().Split(' ');
        int pointer = 0;
        StringBuilder groupBuilder = new StringBuilder();
        while (pointer < sourceText.Length - GroupSize) {
            groupBuilder.Clear();
            int offset = pointer + GroupSize;
            for (int i = pointer; i < offset; i++) {
                //prepend a space to allow separation between words in groups. 
                //We can make a substring from this later starting from char 1 
                //to lose the initial whitespace from the string.
                groupBuilder.Append(" ").Append(sourceText[i]);
            }

            String key = groupBuilder.ToString().Substring(1);
            if (!WordGroupInstances.ContainsKey(key)) {
                WordGroupInstances.Add(key, 1);
            } else {
                WordGroupInstances[key]++;
            }

            /**
             * Setting the pointer to increase by group size grabs a group, moves on
             * to the end of the group, and grabs the next.
             * 
             */
            pointer += GroupSize;

            /**
             * Setting the point to increment by 1 grabs a group, advances by 1 word, then
             * grabs the next, so from the phrase - "Hello world, I'm some text", the groups of size 2 would be
             * "Hello world,", "world, I'm", "I'm some" etc...
             */
            //pointer++;
        }

        return WordGroupInstances;

    }

对以下方法进行了改进，使之依次产生所有的群产量，如绿藻、绿藻等。

值得注意的是，整个文本必须转换为小写或大写，这样单词就不会依赖大小写。我对此做了一些改进，以提高性能(并消除了中断指令的需要)。

   private Dictionary<String, int> GetAllGroups() {
        Dictionary<string, int> WordGroupInstances = new Dictionary<string, int>();
        StringBuilder groupBuilder = new StringBuilder();
        String[] sourceText = GetSourceText().Split(' ');

        for (int i = 0; i < sourceText.Length; i++) {
            groupBuilder.Clear();
            for (int j = i; j < sourceText.Length; j++) {
                groupBuilder.Append(" ").Append(sourceText[j]);
                String key = groupBuilder.ToString().Substring(1);
                if (!WordGroupInstances.ContainsKey(key)) {
                    WordGroupInstances.Add(key, 1);
                } else {
                    WordGroupInstances[key]++;
                }
            }
        }
        return WordGroupInstances;
    }

在使用文本语料库(288个单词)进行性能测试之后，它将在0.171886秒内创建41773个单词组。

Answer 3

下面是一种流方法，它从可枚举的单词中递归地构建大小为N的组(在本例中为3)。如何将输入标记为单词并不重要(本例中我使用了一个简单的正则表达式)。

//tokenize input (enumerable of string)
var words = Regex.Matches(input, @"\w+").Cast<Match>().Select(m => m.Value);

//get word groups (enumerable of string[])
var groups = GetWordGroups(words, 3);

//do what you want with your groups; suppose you want to count them
var counts = new Dictionary<string, int>(StringComparer.CurrentCultureIgnoreCase);
foreach (var group in groups.Select(g => string.Join(" ", g)))
{
    int count;
    counts.TryGetValue(group, out count);
    counts[group] = ++count;
}


IEnumerable<string[]> GetWordGroups(IEnumerable<string> words, int size)
{
    if (size <= 0) throw new ArgumentOutOfRangeException();
    if (size == 1)
    {
        foreach (var word in words)
        {
            yield return new string[] { word };
        }

        yield break;
    }

    var prev = new string[0];

    foreach (var next in GetWordGroups(words, size - 1))
    {
        yield return next;

        //stream of groups includes all groups up to size - 1, but we only combine groups of size - 1
        if (next.Length == size - 1)
        {
            if (prev.Length == size - 1)
            {
                var group = new string[size];
                Array.Copy(prev, 0, group, 0, prev.Length);
                group[group.Length - 1] = next[next.Length - 1];
                yield return group;
            }

            prev = next;
        }
    }
}

这种流方法的一个优点是，您可以减少任何时候必须保存在内存中的字符串的数量(这减少了对大量文本的内存使用)。根据接收输入的方式，另一个优化可能是在读取输入时使用TextReader来生成令牌的枚举。

下面是中间分组输出的一个示例(每个项实际上是标记数组，这里有一个用于输出的空白)：

The 
green 
The green 
algae 
green algae 
The green algae 
singular 
algae singular 
green algae singular 
green 
singular green 
algae singular green 
alga 
green alga 
singular green alga