搜索短语列表并与单词列表匹配，计算出现次数。

Question

搜索短语列表并与单词列表匹配，计算出现次数。

3

问题很简单...
已知:

- 一个脏话列表，称为List1。 - 一个需要搜索这些脏话的字符串（或短语）列表，称为List2。

期望输出: 匹配至少一个脏话的短语数量。

样例:
List1: "cat", "dog", "mouse", "Nice animal"
List2: "A cat is good". "a dog is bad", "cat and dog are good", "Nice animal", "Hello", "Hello mouse", "This is bad"

输出: 5个短语包含至少1个脏话。

我的做法:

int sum = list1.Sum(s => list2.Count(t => t.Contains(s)));

这需要大约38秒的时间来搜索5600个敏感词短语，并在大约4000个字符串中进行搜索。（四核，4 GB RAM）... 太慢了！

我寻找过可能存在的解决方案或算法... 但没有找到。

即使有人能指引我正确的方向，命名一个算法，显示一段代码片段或者只是简单地指引一下，那也太好了！

- Ramanpreet Singh

我不确定这是否真的有所帮助，但你可以尝试将所有脏话编译成一个正则表达式（一个包含所有脏话的单一正则表达式），然后运行它来匹配短语。我只是猜测编译后的正则表达式比你的Linq查询更快。 - Alxandr

倒排索引或搜索引擎索引。 - I4V

也许使用正则表达式会更高效。 - filipko

1

@filipko，正则表达式比String.Contains慢得多，因为它们有不同的目的和优化方式。要匹配精确单词，string.Contains始终更快。 - Francesco De Lisi

这里有一份不错的可能适用于字符串中单词列表匹配的方法列表。 - Alexander

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tim Schmelter · Accepted Answer

这样做应该更有效率，因为Any会尽快中断：

int contains = phrases.Count(p => foulWords.Any(fw => p.Contains(fw)));

你的方法也不是最佳的，因为你的起点是List1（foulWords），所以你需要对每个计数求和，这很低效。正确的结果应该在0（没有匹配的脏话）和 phrases.Count之间（所有短语都包含一个脏话）。因此，起点应该是phrases。

演示

问：你能帮我修改上面的代码，还能给我短语列表中每个短语的索引吗？

可以：

var wordIndexes = phrases.Select((phrase, index) => new { phrase, index })
    .Where(x => foulWords.Any(fw => x.phrase.Contains(fw)));

foreach (var wordIndex in wordIndexes)
    Console.WriteLine("Word: {0} Index: {1}", wordIndex.phrase, wordIndex.index);

结果：

Word: A cat is good        Index: 0
Word: a dog is bad         Index: 1
Word: cat and dog are good Index: 2
Word: Nice animal          Index: 3
Word: Hello mouse          Index: 5