Efficient way to search for phrases that contain specific words

Question

I need the most efficient way to do it in C#.

Assuming:

Collection1: {"I am good", He is best", They are poor", "Mostly they are average", "All are very nice"}
Collection2: {"good", "best" ,"nice"}

I want to search all Collection2 items in Collection1 and store the matching results in Collection3, so Collection3 would be like this:

Collection3: {"I am good", "I am best", "All are very nice"}

Looks like you need an inverted index, look at how Lucene.NET does this, or just use that library. — Lucas Trzesniewski, Mar 06 '16 at 10:57
I am wondering if you have done any research on the subject. For example in the related column here on the right there is [What .NET collection provides the fastest search?](http://stackoverflow.com/questions/1009107/what-net-collection-provides-the-fastest-search?) — Steve, Mar 06 '16 at 11:27
@EugenePodskal; Collection1 items will be like a phrase. Collection2 items will be all one word that will be searched in Collection1 phrases and then put the matching phrases in Collection3. — p0iz0neR, Mar 06 '16 at 12:55

score 0 · Answer 1 · answered Mar 06 '16 at 11:43

0

IList<String> Collection3;

for(int i = 0 ; i < Collectio2.Count ; i++)
{
   foreach(String str in Collection1)
   {
      if(str.Contains(Collection2[i]))
      {
         Collection3.Add(str);
      }
   }
}

answered Mar 06 '16 at 11:43

Leon Barkan

2,676
2
19
43

That using nested loops. I want to avoid recursive loops. – p0iz0neR Mar 06 '16 at 12:51
in this case you need to use LINQ – Leon Barkan Mar 06 '16 at 13:28
I used Dictionary but it only returns TRUE or FALSE but not the index from ContainsValue function. – p0iz0neR Mar 06 '16 at 13:42

Leon Barkan · Accepted Answer · 2016-03-06T14:48:33.293

0

The best way to do it.

string[] Collection1 = {"I am good", "He is best", "They are poor", "Mostly they are average", "All are very nice"};
string[] Collection2 = { "good", "best", "nice" };

var Collection3 = Collection1.Select(x => x.ToLower())
                   .Where(x => Collection2.Any(y => x.Contains(y))).ToArray();

edited Mar 06 '16 at 14:48

answered Mar 06 '16 at 13:40

Leon Barkan

2,676
2
19
43

Not compiling in C# 2010. Can you write correct code please. This looks easy and good. – p0iz0neR Mar 06 '16 at 15:13
great, glad to help. – Leon Barkan Mar 06 '16 at 15:25
@p0iz0neR I'd like to point that this solution is `O(lengthOfCollection2*lengthOfCollection1*averageLengthOfStringInCollection1)`, while solution with lookup is amortized `O(lengthOfCollection1*averageAmountOfWordsInPhrase)` for lookup creation and amortized `O(lengthOfCollection2)` for **any subsequent** `Collection2` used. So if you need **performance**, and, especially if you need to conduct such searches with multiple different `Collection2`, then this solution is an **inefficient** one, though a very concise one and handles not just words, but substrings/phrases as well. – Eugene Podskal Mar 06 '16 at 15:47
@EugenePodskal; Well I have a list not more than thousand and for that it worked. I know this isn't the fastest one and will decrease performance for very large lists. Though its ok for me. – p0iz0neR Mar 06 '16 at 16:53

score 0 · Answer 3 · edited May 23 '17 at 12:23

Assuming that your Collection2 items are words in the usual meaning of that word [no pun intended], you can use LINQ ToLookup - that will give you a proper MultiValueDictionary analogue, and with that you can try something like:

var phrases = new[] { "I am good", "He is best", "They are poor", "Mostly they are average", "All are very nice", "Not so\tgood \t", };

var lookup = phrases
    .Select((phrase, index) =>
        new
        {
            phrase,
            index,
            words = phrase.Split((Char[])null, StringSplitOptions.RemoveEmptyEntries)
        })
    .SelectMany(item =>
        item
            .words
            .Select(word =>
                new
                {
                    word,
                    item.index,
                    item.phrase
                }))
    .ToLookup(
        keySelector: item => item.word,
        elementSelector: item => new { item.phrase, item.index });

var wordsToSearch = new[] { "good", "best", "nice" };

var searchResults = wordsToSearch
    .Select(word =>
        new
        {
            word,
            phrases = lookup[word].ToArray()
        });

foreach (var result in searchResults)
{
    Console.WriteLine(
        "Word '{0}' can be found in phrases : {1}",
        result.word,
        String.Join(
            ", ",
            result
                .phrases
                .Select(phrase => 
                    String.Format("{0}='{1}'", phrase.index, phrase.phrase))));
}

It gives you both the index and the phrase, so you can adapt it as you wish.

But if your Collection2 consists not of words, but of phrases, then you will need something more powerful, like lucene.net, something that can properly handle full text search.

Efficient way to search for phrases that contain specific words

3 Answers3