如何将列表缩减为最常见的字符串？

Question

我有一个HashSet<string>，我要将不雅的词语加载进去以便过滤。问题是我的列表中会包含“Fu”以及完整拼写的单词。我想做的是将列表过滤，使其仅包含“Fu”，这样可以消除列表中任何其他形式的单词。

换句话说，我想删除列表中所有子字符串也是列表项的字符串。

我应该如何去做这件事？

我有以下代码，其中excludedWords是原始的HashSet，但它并不能完全实现目标：

HashSet<string> copy = new HashSet<string>(exludedWords);

foreach (string w in copy)
{
    foreach (string s in copy)
    {
        if (w.Contains(s) && w.Length > s.Length)
        {
            result.Remove(w);
        }
    }
}

- MAW74656

---

@bzlm 我会说，所有“删除包含列表中任何其他单词的单词”的操作。 - Oskar Kjellin

那么......删除foohead，因为foo已经在列表中了？ - BZink

@OskarKjellin，嗯，既然starts-with是contains的子集，我以为那是个打字错误。 :) - bzlm

你应该使用前缀树作为数据结构。这样在查找字符串时会更加高效。 - Jeff Mercado

@Jeff：我认为这应该是一个答案。从那个数据结构中，算法几乎可以自己编写。 - Merlyn Morgan-Graham

Answer 1

您应该将集合中的每个单词与集合中的所有其他（不同）单词进行比较。您可以按照以下方式完成此操作（虽然我确定这绝不是最有效的方法）：

string[] strings = { "a", "aa", "aaa", "b", "bb", "bbb", "c", "cc", "ccc" };
List<string> results = new List<string>(strings);

foreach (string str1 in strings) {
  foreach (string str2 in strings) {
    if (str1 != str2) {
      if (str2.Contains(str1)) {
        results.Remove(str2);
      }
    }
  }
}

return results;

- Jon Newmuis

---

@MAW74656，使用Contains而不是StartsWith的原因是什么？为什么应该删除“astrofunk”，因为列表中有“fu”？ - bzlm

@bzlm - 因为“fu”是“astrofunk”和“fu*k”的最短常见的冒犯子字符串。我从未说过只删除以...开头的内容，一个子字符串可以在字符串中的任何索引处开始。 - MAW74656

抱歉，根据您的“fu”示例，我理解为StartsWith，但您也可以轻松使用Contains。 - Jon Newmuis

@JonathanNewmuis - 好的，你的代码和我的一样（但循环更少，所以更有效率），但仍然存在一个问题。列表已经被简化了，但并不完全。例如，我的列表中仍然有"AS"、"ASS"和"AS5"，而"AS"应该是唯一的。你有什么想法吗？ - MAW74656

@MAW74656 - 我刚刚使用string[] strings = { "AS", "ASS", "AS5" };作为输入运行了上面的代码片段，结果我得到的只有AS。不确定哪里出了问题。如果您更改了条件，那可能就是原因。 - Jon Newmuis

Answer 2

这是一种方法...

filter.RemoveAll(a => filter.Any(b => b != a && a.Contains(b)));

其中filter是一个列表，并预先填充了过滤字符串。

编辑： 没有看到您想要包含而不是以...开头。所以进行了必要的修改。

- deepee1

---

哎呀，Lambda！这个比循环更高效吗？ - MAW74656

不过，当时我没有我的汇编编辑器可用，无法制作最高效的解决方案。（我没有看到他在帖子中提到任何需要速度的要求） - deepee1

我只是一般地说，哪个表现更好？我知道它不完美，但由于我只需要执行一次，然后循环遍历缩短的列表，因此这个操作的性能并不那么重要。 - MAW74656

这并不是最快的，因为它是n^2（所有项都与所有其他项及其本身进行比较），而替代方案永远不会检查比自身短的字符串。我只是喜欢它的紧凑性和可读性，相对于其他方案，如果你只有一个小单词数据库，我相信它会很好用。 - deepee1

Answer 3

假设您只想丢弃较长的值，您可以使用一个IEqualityComparer<string>实现来获取新的集合。

private class ShortestSubStringComparer : IComparer<string>, IEqualityComparer<string>
{
    public int Compare(string x, string y)
    {
        if (x == null) return (y == null) ? 0 : -1;
        if (y == null) return 1;

        Debug.Assert(x != null && y != null);
        if (this.Equals(x, y)) return x.Length.CompareTo(y.Length);
        return StringComparer.CurrentCulture.Compare(x, y);
    }

    public bool Equals(string x, string y)
    {
        if (x == null) return y == null;
        if (x.StartsWith(y)) return true;
        if (y != null && y.StartsWith(x)) return true;
        return false;
    }

    public int GetHashCode(string obj)
    {
        return obj.GetHashCode();
    }
}

然后您的函数可以使用 GroupBy 函数对项目进行分组，并选择第一个有序项目，如下所示：

public HashSet<string> FindShortestSubString(HashSet<string> set)
{
    var comparer = new ShortestSubStringComparer();
    return new HashSet<string>(set.GroupBy(e => e, comparer).Select(g => g.OrderBy(e => e, comparer).First()));
}

或者可能使用Min也可以解决问题（这意味着您不需要IComparer<string>实现）...

public HashSet<string> FindShortestSubString(HashSet<string> set)
{
    var comparer = new ShortestSubStringComparer();
    return new HashSet<string>(set.GroupBy(e => e, comparer).Select(g => g.Min(e => e)));
}

- Reddog

---

我的列表可以有多个“最不常见的”元素。我需要摆脱较长版本的单词。这种方法似乎假定每个列表只有一个最少常见的子字符串？ - MAW74656

Answer 4

我建议不要使用这种类型的过滤。虽然你可以节省一些 CPU 周期，但你会得到一些意想不到的后果，可能会让你的用户感到困惑（或者只是让他们生气）。

例如，假设这是你的粗俗词汇列表...

foo bar foohead foolery

你想从某些内容中过滤掉所有这些单词。为了高效，你删除了 foohead 和 foolery，只过滤子字符串 foo。

你将过滤包含 foo 但不在你原始的粗俗列表中的无害单词。

这让我想起最近的 Daily WTF...（第二个）。

http://thedailywtf.com/Articles/Progree-of-enail-Status.aspx

- BZink

---

这就是我在评论中所说的。除非我误解了OP将要用这个简化后的粗俗词列表做什么，否则他会遇到这个问题。 - Dan J

@BZink，我认为这个想法是确保随机生成的字符串不可能包含粗俗语言，而不是过滤网页。 :) - bzlm

@BZink - 我正在随机生成字符串，然后将它们与这个列表进行比对。如果它们包含任何冒犯性内容，我就会丢弃这个字符串。如果它们是安全的，我就会将它们保存在内存中，然后稍后写入文件。 - MAW74656

@BZink - 虽然，如果您能提出一种减少这些误报的方法，我相信这也会有助于我的程序性能。 - MAW74656

你可以在创建随机字符串时省略元音字母。如果一开始就没有单词，那么就不可能有粗俗的词语了。 :) - BZink

Answer 5

你可以使用正则表达式。这是VB语言，但我相信你可以转换它。

例子：

Imports System.Text.RegularExpressions
Public Class Form1

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Dim InputString As String
        InputString = Regex.Replace(WHAT THE USER HAS ENTERED, "fu", "**")
    End Sub
End Class

- user959631

---

谢谢，但我真的不想“隐藏”那些脏话。有人知道Regex.Replace()在性能上与String.Replace()相比如何吗？ - MAW74656

嗯，Regex.Replace() 有更多的重载，我认为。 - user959631