代码之家 › 专栏 › 技术社区 › Ventus

快速文本预处理

text-processing regex c#

Ventus · 技术社区 · 14 年前

获取HTML页->(到纯文本->堵塞->删除停止语)—>进一步的文本处理

括号中有预处理步骤。应用程序运行大约10.265秒,但预处理需要9.18秒!这是预处理50个HTML页面(不包括下载)的时间。

我使用HtmlAgilityPack库将HTML转换为纯文本。这相当快。转换一个文档需要2.5毫秒,所以相对来说还可以。

问题来得晚。对一个文档进行词干分析需要120毫秒。不幸的是,那些HTML页面是波兰语的。不存在用C#编写的波兰语词干分析器。我只知道两个用Java编写的免费软件:stempel和morfologic。在IKVM软件的帮助下,我将stempel.jar预编译为stempel.dll。所以没什么可做的了。

消除停止词也需要很多时间(1个文档约70毫秒)。它是这样做的:


result = Regex.Replace(text.ToLower(), @"(([-]|[.]|[-.]|[0-9])?[0-9]*([.]|[,])*[0-9]+)|(\b\w{1,2}\b)|([^\w])", " ");
while (stopwords.MoveNext())
{
   string stopword = stopwords.Current.ToString();                
   result = Regex.Replace(result, "(\\b"+stopword+"\\b)", " ");                               
}
return result;

编辑:

我想做的是删除所有不超过2个字母的单词。所以我想找出所有的特殊字符(包括“.”、“,”、“?”、“!”,等等)数字,停止词。我只需要纯文字,我可以使用数据挖掘。

6 回复 | 直到 14 年前

LBushkin 14 年前

迭代替换单词将是实现中的最大瓶颈。 在每次迭代中,您必须扫描整个字符串以查找停止字,然后replace操作必须分配一个新字符串并用替换后的文本填充它。不会很快的。

将输入内容分成单独的单词,用适当的空格或分隔符分隔。您可以增量地执行此操作,这样就不需要分配任何额外的内存来执行此操作。对于每个单词(标记),现在可以在stopwords的hashset中执行查找-如果找到匹配项,则在将最终文本流式输出到单独的 StringBuilder 未修改。这种方法应该具有O(n)性能,因为它只扫描字符串一次并使用 HashSet

下面是一个我希望表现更好的方法。而不是完全流式传输(它使用 String.Split()

下面的代码返回一个单词列表,其中不包括结果中的所有停止词和两个字母或更短的单词。它还对停止词使用不区分大小写的比较。

public IEnumerable<string> SplitIntoWords( string input,
                                           IEnumerable<string> stopwords )
{
    // use case-insensitive comparison when matching stopwords
    var comparer = StringComparer.InvariantCultureIgnoreCase;
    var stopwordsSet = new HashSet<string>( stopwords, comparer );
    var splitOn = new char[] { ' ', '\t', '\r' ,'\n' };

    // if your splitting is more complicated, you could use RegEx instead...
    // if this becomes a bottleneck, you could use loop over the string using
    // string.IndexOf() - but you would still need to allocate an extra string
    // to perform comparison, so it's unclear if that would be better or not
    var words = input.Split( splitOn, StringSplitOptions.RemoveEmptyEntries );

    // return all words longer than 2 letters that are not stopwords...
    return words.Where( w => !stopwordsSet.Contains( w ) && w.Length > 2 );
}

Community Egal 4 年前

最后,多亏了你们,我的文本预处理得到了更好的优化。首先,我从我的问题(按照乔希·凯利的回答)中简化了这个冗长的表达:

[0-9]|[^\w]|(\b\w{1,2}\b)

它和第一个一样,但是非常简单。然后再次遵循Josh Kelley的建议,我将这个正则表达式放入汇编。我发现了一个将表达式编译成汇编的好例子 here . 我这么做了,因为这个正则表达式被使用了很多次。在讲了几篇关于编译正则表达式的文章之后,这是我的决定。我删除了结束语后的最后一个表达式(没有真正的意义)。

因此,在12KiB文本文件上的执行时间是~15ms。这仅适用于上述表达式。

一个大正则表达式

执行时间:~215ms

String.Replace()

string.Replace() 方法。结果有许多循环:

执行时间:~65ms

林克

LBushkin提出的方法。没什么好说的了。

我只能说哇。只需比较第一个和最后一个的执行时间!非常感谢伊布什金!

mqp 14 年前

与其在循环中替换regex,为什么不动态构造一个匹配regex的怪物来匹配任何一个stopword,然后运行一个replace,将其替换为空?像这样的 "\b(what|ok|yeah)\b"

Josh Kelley 14 年前

加速你的正则表达式

你的正则表达式需要一些工作。

例如,该行:

result = Regex.Replace(result, "(\\b"+stopword+"\\b)", " ");

使用括号捕获停止字以供以后使用,然后它就不会使用它。在这种情况下,也许.NET正则表达式引擎足够聪明,可以跳过捕获,也许不是。

这个正则表达式太复杂了:

"(([-]|[.]|[-.]|[0-9])?[0-9]*([.]|[,])*[0-9]+)|(\b\w{1,2}\b)|([^\w])"

"([-]|[.]|[-.]|[0-9])?" 与相同 "([-.0-9])?" . (除非你想把“-”作为你的可能性之一?如果您不需要捕获(在您的示例中也不需要),那么它与 "[-.0-9]?"
"[-.0-9]?" "[0-9]*" . 你可以进一步简化为 "[-.]?[0-9]*" .
同样,如果你不需要捕捉,那么 "([.]|[,])*" 与相同 "[,.]*" .

最后,测试 compiling your regexes

减少正则表达式和字符串操作

构造一堆字符串,组成一堆Regex对象,然后丢弃它们,就像您在这个循环中所做的那样,可能不是很快:

result = Regex.Replace(result, "(\\b"+stopword+"\\b)", " ");

尝试将stopwords预处理到Regex对象数组中,或者创建一个monster预编译Regex(正如其他人所建议的那样)。

重新构造算法

看起来您只对处理词干、非停止词、文本感兴趣,而不是标点符号、数字等。

为此,您的算法采用以下方法:

干所有文本(包括停止词?)。
使用regex(不一定是最快的方法)将非单词替换为空格(这需要不断地重新排列字符串的主体)。
使用regex(同样,不一定是最快的方法)用空格替换(同样)停止字,一次替换一个停止字。

我开始在这里写另一种方法,但LBushkin打败了我。照他说的做。请记住,作为一般规则,更改算法通常比微优化(如提高regex使用率)带来更大的改进。

Charlie Salts 14 年前

你呢可以会遇到 Schlemiel the Painter problem . 在C#(和其他语言)中,当附加或连接字符串时,实际上是在创建一个全新的字符串。在循环中这样做通常会导致大量的内存分配,而这是可以避免的。

Xzhsh 14 年前

我同意mquander的观点,这里有更多的信息。每次使用正则表达式时,C#都会创建一个与文本匹配的表。如果只调用几次regex函数,这是很好的,但是您在这里要做的是创建大约270个新表,并为每个html文档销毁它们。

http://en.csharp-online.net/CSharp_Regular_Expression_Recipes%E2%80%94Compiling_Regular_Expressions

你应该看到一个戏剧性的加速就这样