logo标签列表

检查关键词是否存在于字符串中的算法

c#algorithmstring
5
假设我有一个数组的关键词 {"olympics", "sports tennis best", "tennis", "tennis rules"}。然后我有一个大列表（最多50个），由字符串（或实际上是推文）组成，它们最多有140个字符。
我想查看每个字符串，并查看那里出现了哪些关键字。在关键字由多个单词组成的情况下，例如“sports tennis best”，这些单词不必在字符串中相连，但是它们全部都必须出现。
我遇到了一个解决方案效率低下的难题。
你们有什么建议可以帮助我完成吗？谢谢！
编辑：更好地解释一下，每个关键字都有一个与之相关联的ID，因此 {1：“olympics”，2：“sports tennis best”，3：“tennis”，4：“tennis rules”}。
我要查看字符串/推文列表，并查看哪些关键字匹配。输出应该是，这条推文属于关键字#4。（可能会进行多个匹配，因此任何与关键字2匹配的内容也将匹配3-因为它们都包含“tennis”）。
当关键字中有多个单词时，例如“sports tennis best”，它们不必同时出现，但必须全部出现。例如，这将正确匹配：“我刚打了网球，我喜欢运动，它是最好的”…因为此字符串包含“sports tennis best”，它将匹配并与关键字ID相关联（此示例中为2）。
编辑2：不区分大小写。
1
您想要什么输出结果？包含关键词的字符串列表？还是每个关键词在一个字符串中出现次数的统计？或者其他什么？ - Robin Day
子字符串匹配还是整个单词匹配？区分大小写吗？ - D'Arcy Rittich
我在上面添加了更多的澄清，整个单词匹配...但是用空格分隔的关键字相当于逻辑AND。因此，“sports tennis best”应该与包含“sports”、“tennis”和“best”的关键字匹配。 - rksprst
6个回答
6
IEnumerable<string> tweets, keywords;

var x = tweets.Select(t => new
                           {
                               Tweet = t,
                               Keywords = keywords.Where(k => k.Split(' ')
                                                               .All(t.Contains))
                                                  .ToArray()
                           });
1

可能是这样的吗？

        string[] keywords = new string[] {"olympics", "sports tennis best", "tennis", "tennis rules"};

        string testString = "I like sports and the olympics and think tennis is best.";

        string[] usedKeywords = keywords.Where(keyword => keyword.Split(' ').All(s => testString.Contains(s))).ToArray();
1

使用多种算法，如Aho-Corasick（使用trie）或Wu和Manber的算法，可以非常高效地搜索多个模式。

如果性能很重要，建议选择其中任何一种。要在多个字符串中搜索，最有效的方法可能是将您的50个字符串连接成一个较大的字符串，并保留各个字符串的起始位置。

0
我建议将所有关键词放入字符串列表中，然后将数据列表（推文等）作为另一个字符串列表进行处理。
可以这样做：
Dim matchingStrings As Dictonary(String, String);
For Each stringToSearch As String In tweetList
   For Each keyword As String In keywordList
      If stringToSearch.Contains(keyword)
        matchingString.Add(stringToSearch, keyword);

break; End IF End For End For

然后MatchingString包含所有匹配项

编辑：在C#中，根据您的关键字列表中的多个单词

Dictionary<string, string> matchingString = New Dictionary<string, string>; 
foreach (String stringToSearch In tweetList){
   foreach (String keyword In keywordList){
        If(stringToSearch.Contains(keyword){
            matchingString.Add(stringToSearch, keyword);
            break;
}
else if{
    List<string> split = keyword.Split(" ")
   foreach(String sKeyword In split){
          If(stringToSearch.Contains(keyword){
             matchingString.Add(stringToSearch, keyword);
             break;
          }
    }

 }

} }

但是对于那些包含多个单词的关键字呢？这样就无法匹配了。 - rksprst
它将匹配字符串，如果您需要匹配关键字中的单个单词，则需要拆分关键字。我将在一秒钟内用C#重写这个。 - msarchet
@Mikael Svenson：那又怎样？这只是一个微不足道的一对一翻译。 - Konrad Rudolph
花括号是正确的，只是我无法让它们对齐。 - msarchet
@Konrad，我同意这很简单，但如果你标记了C#，那么你期望的答案应该是C#。否则为什么要打标签呢？ - Mikael Svenson
0

糟糕。

  foreach (var s in strings)
  {
      foreach (var keywordList in keywordSet) 
      {
          if (s.ContainsAll(keywordList))
          {
              // hit!
          }
      }
  }

...

private bool ContainsAll(this string s, string keywordList)
{    
    foreach (var singleWord in keywordList.Split(' '))
    {
        if (!s.Contains(singleWord)) return false;
    }
    return true;
}
0

有一些方法可以预处理字符串，使搜索更有效，但我认为对于这样短的字符串来说，开销大于收益。数据并不是很多，所以我会直接循环遍历字符串：

foreach (string tweet in tweets) {
  foreach (string keywords in theArray) {[
    string[] keyword = keywords.Split(' ');
    bool found = true;
    foreach (string word in keyword) {
      if (tweet.indexOf(word) == -1) {
        found = false;
        break;
      }
    }
    if (found) {
      // all words exist in the tweet
    }
  }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接