Linq search result by closest match

Question

I have an ObservableCollection, which holds a Person object. I have a search feature in my application, and would like to display the most relevant results at the top. What would be the most efficient way of doing this? My current search method simply calls the contains method:

 var results = (from s in userList
               where s.Name.Contains(query)
               select s).ToList();

This works fine, but the results are ordered in the same order they appear within userList. If I search for Pete, then it should first display Pete, then Peter then Peter Smith etc.. It doesn't have to be too complicated as it will only be dealing with a couple thousand (max) results. My naive approach was to first do s.Name == query, display that item (if any), then perform the s.Name.Contains(query), remove the matched item and append it to the previous matched result. However, this seems a bit all over the place and so is there a better way? thanks (ps - only the name will be used in searching, and I can't use SQL methods)

Answer 1

You can make a single routine that provides a name and a query string, and returns an integer value.

Once you have that, just return via order by:

int QueryOrder(string query, string name)
{
     if (name == query)
         return -1;
     if (name.Contains(query))
         return 0;

     return 1; 
}

Then do:

var results = userList.OrderBy(s => QueryOrder(query, s.Name));

The nice thing about this approach is that, later, you could extend the routine to provide more details, allowing you to sort by how "good" of a match you receive. For example, "Pete" -> "Peter" is probably a better match than "Pete" -> "Peter Smith", so you could have your logic return a different value for the different options...

If you need to remove "non-Pete" matches, you could exclude out with a Where clause, as well.

Answer 2

What you need is some sort of scoring function for similarity. Then you can just do:

from s in userList
let score = Score(s, query)
where score > 80
orderby score descending
select s;

(That's supposing a scoring function which gives a value between 0-100, where 100 is a perfect match.)

Now it's not clear from your example exactly what the scoring function should be - that's for you to work out :)