消除字符串中的冗余字母？(例如好->好)

Question

我正在尝试为Twitter的朴素贝叶斯分类器设置一些示例数据。

我想做的tweet的后处理之一是删除不必要的重复字符。

例如，其中一条推文是:Twizzlers. mmmmm goooooooooooood!

我想把w的数量减少到两个。为什么两个?我所关注的文章就是这么做的。任何少于2个字符的单词都会被丢弃(参见上面的mmmmm)。至于gooooooood，我想双字母是最常被重复的。

那么，从执行时间来看，将gooooooooood这样的单词简化为good的最快方法是什么呢?

[编辑]我将在这个应用程序中处理800,000条推文，因此需要最快的执行速度(/编辑)

[Edit2]我只是运行了一些简单的基准测试，基于经过的时间来迭代1000条记录&保存为文本文件。我对每个方法重复这个迭代100次。平均结果如下:

方法1:386 ms [LINQ - answer被删除]方法2:407 ms[正则表达式]方法3:303 ms [StringBuilder]方法4:301 ms [StringBuilder part 2]

方法一:LINQ(答案明显被删除)

static string doIt(string a)
    {
        var l = a.Select((p, i) => new { ch = p, index = i }).
            Where(p => (p.index < a.Length - 2) && (a[p.index + 1] == p.ch) && (a[p.index + 2] == p.ch))
            .Select(p => p.index).ToList();
        l.Sort();
        l.Reverse();
        l.ForEach(i => a = a.Remove(i, 1));
        return a;
    }

方法2:

Regex.Replace(tweet,@"(S)1{2,}","$1$1");

方法三:

static string StringB(string s)
    {
        string input = s;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < input.Length; i++)
        {
            if (i < 2 || input[i] != input[i - 1] || input[i] != input[i - 2])
                sb.Append(input[i]);
        }
        string output = sb.ToString();
        return output;
    }

方法四:

static string sb2(string s)
    {
        string input = s;
        var sb = new StringBuilder(input);
        char p2 = '';
        char p1 = '';
        int pos = 0, len = sb.Length;
        while (pos < len)
        {
            if (p2 == p1) for (; pos < len && (sb[pos] == p2); len--)
                    sb.Remove(pos, 1);
            if (pos < len)
            {
                p2 = p1;
                p1 = sb[pos];
                pos++;
            }
        }
        return sb.ToString();
    }

Answer 1

Regexen看起来是最简单的。REPL中的简单概念证明:

using System.Text.RegularExpressions;  
var regex = new Regex(@"(S)1{2,}"); // or @"([aeiouy])1{2,}" etc?
regex.Replace("mmmmm gooood griieeeeefff", "$1$1");

,>

"mm good griieeff"

对于原始性能，使用更像这样的东西:查看它在https://ideone.com/uWG68

using System;
using System.Text;
class Program
{
    public static void Main(string[] args)
    {
        string input = "mmmm gooood griiiiiiiiiieeeeeeefffff";
        var sb = new StringBuilder(input);
        char p2 = '';
        char p1 = '';
        int pos = 0, len=sb.Length;
        while (pos < len)
        {
            if (p2==p1) for (; pos<len && (sb[pos]==p2); len--)
                sb.Remove(pos, 1);
            if (pos<len)
            {
                p2=p1;
                p1=sb[pos];
                pos++;
            }
        }
        Console.WriteLine(sb);
    }
}

Answer 2

这也很容易通过正则表达式实现:

var re = @"((.)2)2*";
Regex.Replace("god", re, "$1")    // god
Regex.Replace("good", re, "$1")   // good
Regex.Replace("gooood", re, "$1") // good

它比其他方法快吗?好吧，这是基准测试;-)正则表达式在非退化回溯情况下非常有效。以上内容可能需要修改(例如，这也将匹配空格)，但这只是一个小示例。

快乐编码。

Answer 3

我建议使用NLP解决方案，而不是c#/regex。在这种情况下，python是首选。NLTK见。我推荐Nodebox语言学，它会给你拼写更正。你甚至可以用词干，甚至可以用不定式。

Answer 4

我同意这在一般情况下不起作用的评论，特别是在"Twitter讲话"中。你提到的规则很简单——去掉与前两个字符相同的所有字符:

string input = "goooooooooooood";
StringBuilder sb = new StringBuilder(input.Length);
sb.Append(input.Substring(0, 2));
for (int i = 2; i < input.Length; i++)
{
    if (input[i] != input[i - 1] || input[i] != input[i - 2])
        sb.Append(input[i]);
}
string output = sb.ToString();