Algoritmo para ver si existen palabras clave dentro de una cadena

Question

Digamos que tengo un conjunto de palabras clave en una matriz { "Juegos Olímpicos", "pista de deportes mejores", "tenis", "reglas de tenis"}

entonces he una gran lista (hasta 50 a la vez) de cadenas (o en realidad tweets), por lo que tienen un máximo de 140 caracteres.

Quiero ver cada cadena y ver qué palabras clave están presentes allí. En el caso en que una palabra clave se compone de varias palabras como "mejor tenis deportivo", las palabras no tienen que estar juntas en la cadena, pero todas tienen que aparecer.

Tengo problemas para encontrar un algoritmo que lo haga de manera eficiente.

¿Tienen alguna sugerencia sobre cómo hacerlo? ¡Gracias! Editar: Para explicar un poco mejor, cada palabra clave tiene una identificación asociada, así que {1: "olimpiadas", 2: "deportes mejor tenis", 3: "tenis", 4: "reglas de tenis"}

Quiero ir a través de la lista de cadenas/tweets y ver qué grupo de palabras clave coinciden. La salida debería ser, este tweet pertenece a la palabra clave # 4. (Se pueden hacer múltiples coincidencias, por lo que cualquier cosa que coincida con la palabra clave 2, también coincidiría con 3, ya que ambos contienen tenis).

Cuando hay varias palabras en la palabra clave, p. "tenis deportivo mejor" no tienen que aparecer juntos, pero tienen que aparecer todos. p.ej. esto coincidirá correctamente: "Acabo de jugar al tenis, me encanta el deporte, es el mejor" ... ya que esta secuencia contiene "mejor tenis deportivo" coincidirá y se asociará con la palabra clave ID (que es 2 para este ejemplo).

Edición 2: Insensible a las mayúsculas y minúsculas.

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

Sugeriría poner todas sus palabras clave en una lista de cadenas y luego revisar su lista de datos (tweets, lo que sea) como otra lista de cadenas.

hacer algo como esto:

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

ruptura; final si Fin Para Fin Para

Entonces MatchingString Contiene todos sus partidos

EDIT: en C# y por sus múltiples palabras en una lista de palabras clave

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

} 

} }

Answer 3

Whoops.

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 4

patrones múltiples pueden ser buscados de manera muy eficiente el uso de varios algoritmos, tales como el algorithm of Aho-Corasick (utilizando un trie) o el de Wu and Manber.

Si el rendimiento es crítico, sugiero tomar cualquiera de esos. Para buscar en múltiples cadenas, puede ser más eficiente concatenar todas sus 50 cadenas en una cadena más grande, manteniendo el libro de las posiciones iniciales de las cadenas individuales.

Answer 5

Tal vez algo como esto?

 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 6

hay formas de pre-procesar cadenas para hacer búsquedas más eficaz, pero creo que la sobrecarga es más que la ganancia para este tipo de cadenas cortas. No son demasiados datos, así que simplemente recorría las cadenas:

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