Алгоритм, чтобы увидеть, существуют ли ключевые слова внутри строки

Question

Допустим, у меня есть набор ключевых слов в массиве {"олимпийские игры", "лучший теннисный спорт", "теннис", "правила тенниса"}

У меня тогда есть большой список (до 50 за раз) строк (или фактически твитов), так что они не более 140 символов.

Я хочу посмотреть на каждую строку и посмотреть, какие ключевые слова там присутствуют. В случае, когда ключевое слово состоит из нескольких слов, таких как «лучший теннисный спорт», слова не обязательно должны быть вместе в строке, но все они должны отображаться.

У меня проблемы с поиском алгоритма, который делает это эффективно.

У вас, ребята, есть предложения, как это сделать? Спасибо!

Edit: Чтобы объяснить это немного лучше, каждому ключевому слову соответствует идентификатор, поэтому {1: «Олимпийские игры», 2: «Лучший теннисный спорт», 3: «Теннис», 4: «Правила тенниса»}

Я хочу просмотреть список строк / твитов и посмотреть, какая группа ключевых слов соответствует. Вывод должен быть, этот твит принадлежит ключевому слову # 4. (Можно сделать несколько совпадений, поэтому все, что соответствует ключевому слову 2, также будет соответствовать 3, поскольку они оба содержат теннис).

Если в ключевом слове несколько слов, например, «лучший спортивный теннис», они не должны появляться вместе, но должны появляться все. например это будет правильно соответствовать: «я только что играл в теннис, я люблю спорт, это лучшее» ... так как эта строка содержит «лучший теннисный спорт», она будет соответствовать и ассоциироваться с ключевым словом ID (в данном примере это 2).

Редактировать 2: без учета регистра.

Answer 1

IEnumerable<string> tweets, keywords;

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

Answer 2

Может как то так?

        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();

Answer 3

Множество паттернов можно найти очень эффективно, используя несколько алгоритмов, таких как алгоритм Aho-Corasick (с использованием trie) или один из Wu и Manber .

Если производительность критична, я предлагаю принять любой из них. Для поиска по нескольким строкам может быть наиболее эффективно объединить все ваши 50 строк в одну большую строку, сохраняя список начальных позиций отдельных строк.

Answer 4

Существуют способы предварительной обработки строк, чтобы сделать поиск более эффективным, но я думаю, что издержки больше, чем выигрыш для таких коротких строк.Это не так много данных, поэтому я бы просто перебрал строки:

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
    }
  }
}

Answer 5

Упс.

  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;
}

Answer 6

Я бы предложил поместить все ваши ключевые слова в список строк, а затем просмотреть список данных (твиты и т. Д.) Как другой список строк.

Сделайте что-то вроде этого:

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);

перерыв; Конец ЕСЛИ Конец для Конец для

Тогда 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;
          }
    }

 }

} }