如何从字符串中删除指定的单词

5

这里有一个被禁用的单词列表(或更普遍地说,是字符串列表),还有一个包含用户邮件的列表。我想从所有邮件中删除所有被禁用的单词。

以下是一个简单的例子:

foreach(string word in wordsList)
{
   foreach(string mail in mailList)
   {
      mail.Replace(word,String.Empty);
   }
}

我该如何改进这个算法?


谢谢您的建议。我已经投票支持了一些答案,但由于更像是讨论而不是解决方案,所以没有标记任何一个答案为最佳答案。有些人会错过被禁用的词语,使用不当的词语。但在我的情况下,我不必担心识别“sh1t”或类似的词语。


10
你是否在使用中遇到了性能问题?不要过早进行优化,直到必要的时候再考虑。 - Oded
1
我没有性能问题。我只想学习并提高我的技能 :-) - zgorawski
12个回答

5
简单的骂人话过滤方法行不通,复杂的方法大多也无效。
比如你要过滤掉“ass”,但是当出现“password”这个词时,如果有人用“a$$”代替,意图仍然很明显,对吧?
请参考如何实现一个好的脏话过滤器?,进行详细讨论。

当你得到一个像“password”这样的单词,想要过滤掉其中的“ass”时会发生什么? - 那么你的算法很糟糕。 - Brian R. Bondy
1
当一些聪明人写下“a$$”时会发生什么 - 意图仍然清晰,对吧?很多时候,简化问题是有价值的,不总是需要100%解决问题。 - Brian R. Bondy
@Brian - 我同意,我在这里揣摩了一下。如果 OP 只想构建“尽力而为”的代码,那么对字符串替换的调整是可以的。如果他/她已经签约构建可靠的粗话过滤器,那么工作范围需要明确,否则当它花费比预期更长时间时,他/她可能会陷入麻烦。 - Steve Townsend

2
你可以使用正则表达式使得内容更加整洁:
```

你可以使用正则表达式使得内容更加整洁:

```
var bannedWords = @"\b(this|is|the|list|of|banned|words)\b";

foreach(mail in mailList)
    var clean = Regex.Replace(mail, bannedWords, "", RegexOptions.IgnoreCase);

即便如此,人们总会找到绕过任何类型过滤器的方法,因此这仍然远非完美。

这不是删除禁用词,而是删除禁用子字符串。例如,这将把字符串中的单词“often”更改为“ten”。 - Michael Petito
@Michael - 显然我的正则表达式技巧还不够好。我添加了我认为正确的限制单词边界的方法。有任何更正吗? - Justin Niessner
看起来好多了,谢谢。不过我还要再提一下(如下所述),如果你的列表超过几十个单词,那么制作这样的正则表达式可能并不理想。 - Michael Petito

2
你可以通过绘制有限状态机(FSM)(或生成一个)并逐个字符解析输入,然后按照状态进行操作以获得最佳性能。
你可以使用一个函数轻松地完成这项工作,该函数接受下一个输入字符和当前状态,并返回下一个状态,同时在遍历邮件消息的字符时创建输出。你可以将FSM画在纸上。
或者你可以了解Windows Workflow Foundation: State Machine Workflows。这样一来,你只需要一次遍历每条消息。

除非我误解了你的建议,否则我觉得在这个问题上使用Windows工作流状态机逐个字符解析字符串有点过度设计。 - Michael Petito
这取决于软件是什么。如果这个人试图构建一个过滤粗话的软件,那么我认为不行。 - Brian R. Bondy

1

一般的算法如下:

  1. 根据输入字符串生成一个标记列表(即将空格视为标记分隔符)
  2. 将每个标记与禁用词列表进行比较
  3. 替换匹配的标记

正则表达式方便识别标记,HashSet可提供快速查找您的禁用词列表。在Regex类上有一个重载的Replace方法,它接受一个函数,您可以基于查找控制替换行为。

HashSet<string> BannedWords = new HashSet<string>(StringComparer.InvariantCultureIgnoreCase)
{
    "bad",
};

string Input = "this is some bad text.";

string Output = Regex.Replace(Input, @"\b\w+\b", (Match m) => BannedWords.Contains(m.Value) ? new string('x', m.Value.Length) : m.Value);

这并没有利用正则表达式的威力。它只是将替换循环抽象出来了。请参见Justin的答案以了解我的意思。 - Ahmad Mageed
@Ahmad Mageed:我正在使用一个简单(而且快速)的正则表达式从字符串中生成令牌流,我还需要更多的功能吗?我也不认为像Justin的解决方案那样拿出数百个被禁止的单词并构建一个大的正则表达式是理想的(或者高效的)。 - Michael Petito

1

从单词(word1|word2|word3|...)构建正则表达式,并使用它代替外部循环,这样可能会更快,因为每个电子邮件只需要解析一次。此外,使用正则表达式可以通过使用单词边界标记(\b(word1|word2|word3|...)\b)仅删除“完整的单词”。

总的来说,我认为你不会找到比当前解决方案快几个数量级的解决方案:你必须遍历所有邮件,并且必须搜索所有单词,没有简单的方法可以绕过这些。


1

*替换它很烦人,但比删除单词并留下一个畸形的句子更烦人,因为这样会削弱你的意图。如果在讨论黑斯廷战役时,我看到威廉被称为“诺曼底大*******”,我会感到恼怒,但至少我知道我是在小孩子的游乐场上玩耍,而他被称为“诺曼底大公”只是看起来像个错误,或者(更糟糕的是)我可能会认为那就是他的头衔。

除非有趣,否则不要尝试用更无害的词替换单词。人们在4chan上会明白这个笑话,但是关于历史的雅虎小组却让人困惑,因为当谈论中世纪和文艺复兴时期时,eval(不是亵渎之词,但在一些XSS攻击中使用,雅虎曾遭受过此类攻击)被替换为review时,medieval和mediaeval(显然,medireview是mediareview的美式拼写!)。


这基本上与我的答案相同,并且大约在同一时间提交。每当发生这种情况时,我的一般政策是提交者显然是个天才,值得+1。 :-) - T.E.D.

1
在某些情况下,可能可以改进它: 只是为了好玩:
如果您的邮件列表是邮件列表(因为您有一个类似于“;”的分隔符),则可以使用SortedList进行以下操作:
首先计算您的运行时间算法: 单词:n项。 (每个项目的长度为O(1))。 邮寄清单:K项。 邮寄清单中的每个项目平均长度为Z。 邮寄清单项目中的每个子项目的平均长度为Y,因此邮寄清单项目中子项目的平均数量为m = Z / Y。
您的算法需要O(n * K * Z)。// knut算法的最佳方式
现在,如果您按O(n log n)排序单词列表。
2.1-对于每个邮寄清单项目,请使用mailingListItem.Split(“;”。ToCharArray()):O(Z)。 2.2-对邮寄清单中的项目进行排序:O(m * log m) 总排序最坏情况下需要O(K * Z),而与(m logm << Z)相关的情况除外。
使用合并算法合并不良单词和特定邮件列表的项目:O((m + n)* k)

关于 m << n,总时间为 O((m+n)*K + m*Z + n^2),最坏情况下算法的运行时间为 O(n^2 + Z*K),如果 n < K * Z,则小于 O(n*K*Z)(我认为是这样)。

因此,如果性能非常非常重要,您可以这样做。


0

你可以考虑使用 Regex 而不是简单的字符串匹配,以避免替换单词内部的部分内容。正则表达式将允许你确保只获取完全匹配的单词。你可以使用类似这样的模式:

"\bBADWORD\b"

此外,您可能希望在外部迭代邮件列表,并在内部循环中迭代单词列表。


0

通过将所有字符更改为*或类似的字符,这样做不是更容易(而且更有效率)吗?这样就无需调整或移动任何大型字符串,接收者也会更加清楚发生了什么,而不是得到一些缺少单词的无意义句子。


为什么这样会更有效率? - Heinzi
@Heinzi - 编辑以包含该信息。基本上,除非您要替换的内容恰好具有相同数量的字符,否则Replace将不得不移动替换字符串后面的数据。 - T.E.D.
“Replace” 会创建一个全新的字符串实例,因为字符串是不可变的。不过,我同意你的可用性观点! - Heinzi
@Heinzi - 好的,我不是C#专家,但你可能想在这里使用一些可变的东西,只需更改一个问题中的一个单词,这样你就不必复制或移动大量数据。 - T.E.D.

0

好吧,你肯定不想犯天真的字符串.Replace()错误来做这件事。正则表达式解决方案可能有效,尽管你要么会迭代,要么使用管道交替器(我不知道/多少会减慢你的操作速度,特别是对于一个大的禁用单词列表)。你也可以选择...不这样做,因为无论如何都是徒劳的--即使不使用确切的字母,也有办法使你打算使用的单词非常清晰。

此外,首先拥有“人们认为冒犯”的单词列表是荒谬的。几乎任何单词都会有人感到冒犯

/审查制度是胡说八道的抱怨


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接