4

编辑:我收到了一些非常好的建议,我会尝试解决它们并在某个时候接受答案

我有一个很大的字符串列表(800k),我想尽快过滤掉不需要的单词列表(最终是亵渎,但可以是任何东西)。

我最终希望看到的结果将是一个列表,例如

Hello,World,My,Name,Is,Yakyb,Shell

会成为

World,My,Name,Is,Yakyb

核对后

Hell,Heaven.

到目前为止我的代码是

 var words = items
            .Distinct()
            .AsParallel()
            .Where(x => !WordContains(x, WordsUnwanted));

public static bool WordContains(string word, List<string> words)
    {
        for (int i = 0; i < words.Count(); i++)
        {
            if (word.Contains(words[i]))
            {
                return true;
            }
        }
        return false;
    }

目前这需要大约 2.3 秒(9.5 w/o 并行)来处理 800k 个单词,这一次没什么大不了的。然而,作为一个学习过程,有没有更快的处理方式?

不需要的单词列表长度为 100 个单词,
其中没有一个单词包含标点符号或空格

  1. 删除所有列表中的重复项所采取的步骤
  2. 查看使用数组是否更快(不是)的步骤 有趣的是,将参数 words 更改为 string[] 使其慢 25%
  3. 添加 AsParallel() 的步骤已将时间减少到 ~2.3 秒
4

5 回答 5

1

尝试调用的方法Except

http://msdn.microsoft.com/en-AU/library/system.linq.enumerable.except.aspx

var words = new List<string>() {"Hello","Hey","Cat"};
var filter = new List<string>() {"Cat"};

var filtered = words.Except(filter);

还有怎么样:

var words = new List<string>() {"Hello","Hey","cat"};
var filter = new List<string>() {"Cat"};
// Perhaps a Except() here to match exact strings without substrings first?
var filtered = words.Where(i=> !ContainsAny(i,filter)).AsParallel();    
// You could experiment with AsParallel() and see 
// if running the query parallel yields faster results on larger string[]
// AsParallel probably not worth the cost unless list is large
public bool ContainsAny(string str, IEnumerable<string> values)
{
   if (!string.IsNullOrEmpty(str) || values.Any())
   {
       foreach (string value in values)
       {
             // Ignore case comparison from @TimSchmelter
             if (str.IndexOf(value, StringComparison.OrdinalIgnoreCase) != -1) return true;

             //if(str.ToLowerInvariant().Contains(value.ToLowerInvariant()))
             // return true;
       }
   }

   return false;
}
于 2013-02-22T22:37:13.633 回答
1

几件事

变更 1(简单易用): 通过使用 HashSet 而不是 Distinct 方法,我能够(部分地)加快运行速度。

var words = new HashSet<string>(items) //this uses HashCodes
        .AsParallel()...

变更 2(请耐心等待;)): 关于@Tim 的评论,包含可能无法为您提供足够的搜索黑名单字词。例如Takeshita是一个街道名称。

你已经确定你想要这个词的有限状态(又名 Stemmed)。例如,对于 Apple,我们会将其视为 Apple。为此,我们可以使用诸如 Porter Stemmer 之类的词干提取算法。

如果我们要 Stem 一个词,那么我们可能不需要做 Contains(x),我们可以使用 equals(x) 甚至更好地比较 HashCodes(最快的方法)。

var filter = new HashSet<string>(
    new[] {"hello", "of", "this", "and", "for", "is", 
        "bye", "the", "see", "in", "an", 
        "top", "v", "t", "e", "a" }); 

var list = new HashSet<string> (items)
            .AsParallel()
            .Where(x => !filter.Contains(new PorterStemmer().Stem(x)))
            .ToList();

这将比较其哈希码int == int上的单词。

词干分析器的使用并没有减慢速度,因为我们用 HashSet 对其进行了补充(对于过滤列表,bigO 为 1)。这返回了更大的结果列表。

我正在使用位于 Lucene.Net 代码中的 Porter Stemmer,这不是线程安全的,因此我们每次都新建一个

Alteration 2 的问题,Alteration 2a:与大多数自然语言处理一样,它并不简单。什么时候发生

  1. 该词是禁用词“GrrArgh”的组合(其中 Grr 和 Argh 被禁用)
  2. 这个词被故意拼错了“Frack”,但仍然与被禁止的词具有相同的含义(对不起论坛用户)
  3. 这个词用空格“G r r”拼写。
  4. 你的乐队词不是一个词而是一个短语,糟糕的例子:“桶的儿子”

通过论坛,他们使用人类来填补这些空白。

或者引入白名单(鉴于您提到了 bigO,我们可以说这将有 2n^2 的性能损失,因为我们为每个项目创建 2 个列表,不要忘记删除前导约束和如果我没记错的话,你只剩下 n^2,但我的 bigO 有点生疏)

于 2013-02-24T19:20:33.837 回答
1

更改您的WordContains方法以使用单个 Aho-Corasick 搜索而不是 ~100 包含调用(当然,只需初始化一次 Aho-Corasick 搜索树)。

您可以在此处找到开源实现http://www.codeproject.com/script/Articles/ViewDownloads.aspx?aid=12383

初始化类后,您将为800k 字符串中的每一个StringSearch调用该方法 。public bool ContainsAny(string text)

无论您的不需要的单词列表有多长,一次调用都将花费 O(字符串的长度)时间。

于 2013-02-24T20:39:44.923 回答
0

啊,根据“坏”列表中的匹配项过滤单词。这是一个复杂的问题,已经测试了许多程序员的共识。我来自斯肯索普的朋友为此写了一篇论文。

您真正要避免的是在 O(lm) 中测试单词的解决方案,其中 l 是要测试的单词的长度,m 是坏单词的数量。为了做到这一点,您需要一个解决方案,而不是遍历坏词。我原以为正则表达式可以解决这个问题,但我忘记了典型的实现有一个内部数据结构,每次交替都会增加。正如其他解决方案之一所说,Aho-Corasick 是执行此操作的算法。标准实现会找到所有匹配项,您的执行会更有效率,因为您可以在第一场比赛中退出。我认为这提供了理论上的最佳解决方案。

于 2013-02-22T22:45:01.587 回答
0

我很想看看我是否能想出一种更快的方法来做到这一点——但我只进行了一点优化。那是检查另一个字符串中出现的字符串的索引,因为它首先似乎比“包含”稍快,其次让您指定不区分大小写(如果这对您有用的话)。

下面包括我编写的一个测试类 - 我使用了超过 100 万个单词,并且在所有情况下都使用区分大小写的测试进行搜索。它测试你的方法,也是我试图建立的正则表达式。你可以自己试一试,看看时间;正则表达式的工作速度不如您提供的方法快,但是我可能会错误地构建它。我在 (word1|word2...) 之前使用 (?i) 来指定正则表达式中的不区分大小写(我很想知道如何优化它——它可能遇到了经典的回溯问题!)。

随着更多“不需要的”单词的添加,搜索方法(无论是正则表达式还是提供的原始方法)似乎变得越来越慢。

无论如何-希望这个简单的测试对您有所帮助:

    class Program
{


    static void Main(string[] args)
    {
        //Load your string here - I got war and peace from project guttenburg (http://www.gutenberg.org/ebooks/2600.txt.utf-8) and loaded twice to give 1.2 Million words
        List<string> loaded = File.ReadAllText(@"D:\Temp\2600.txt").Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries).ToList();

        List<string> items = new List<string>();
        items.AddRange(loaded);
        items.AddRange(loaded);

        Console.WriteLine("Loaded {0} words", items.Count);

        Stopwatch sw = new Stopwatch();

        List<string> WordsUnwanted = new List<string> { "Hell", "Heaven", "and", "or", "big", "the", "when", "ur", "cat" };
        StringBuilder regexBuilder = new StringBuilder("(?i)(");

        foreach (string s in WordsUnwanted)
        {
            regexBuilder.Append(s);
            regexBuilder.Append("|");
        }
        regexBuilder.Replace("|", ")", regexBuilder.Length - 1, 1);
        string regularExpression = regexBuilder.ToString();
        Console.WriteLine(regularExpression);

        List<string> words = null;

        bool loop = true;

        while (loop)
        {
            Console.WriteLine("Enter test type - 1, 2, 3, 4 or Q to quit");
            ConsoleKeyInfo testType = Console.ReadKey();

            switch (testType.Key)
            {
                case ConsoleKey.D1:
                    sw.Reset();
                    sw.Start();
                    words = items
                        .Distinct()
                        .AsParallel()
                        .Where(x => !WordContains(x, WordsUnwanted)).ToList();

                    sw.Stop();
                    Console.WriteLine("Parallel (original) process took {0}ms and found {1} matching words", sw.ElapsedMilliseconds, words.Count);
                    words = null;
                    break;

                case ConsoleKey.D2:
                    sw.Reset();
                    sw.Start();
                    words = items
                        .Distinct()
                        .Where(x => !WordContains(x, WordsUnwanted)).ToList();

                    sw.Stop();
                    Console.WriteLine("Non-Parallel (original) process took {0}ms and found {1} matching words", sw.ElapsedMilliseconds, words.Count);
                    words = null;
                    break;

                case ConsoleKey.D3:
                    sw.Reset();
                    sw.Start();
                    words = items
                        .Distinct()
                        .AsParallel()
                        .Where(x => !Regex.IsMatch(x, regularExpression)).ToList();

                    sw.Stop();
                    Console.WriteLine("Non-Compiled regex (parallel) Process took {0}ms and found {1} matching words", sw.ElapsedMilliseconds, words.Count);
                    words = null;
                    break;

                case ConsoleKey.D4:
                    sw.Reset();
                    sw.Start();
                    words = items
                        .Distinct()
                        .Where(x => !Regex.IsMatch(x, regularExpression)).ToList();

                    sw.Stop();
                    Console.WriteLine("Non-Compiled regex (non-parallel) Process took {0}ms and found {1} matching words", sw.ElapsedMilliseconds, words.Count);
                    words = null;
                    break;

                case ConsoleKey.Q:
                    loop = false;
                    break;

                default:
                    continue;
            }
        }
    }

    public static bool WordContains(string word, List<string> words)
    {
        for (int i = 0; i < words.Count(); i++)
        {
            //Found that this was a bit fater and also lets you check the casing...!
            //if (word.Contains(words[i]))
            if (word.IndexOf(words[i], StringComparison.InvariantCultureIgnoreCase) >= 0)
                return true;
        }
        return false;
    }
}
于 2013-02-23T12:29:07.710 回答