Несколько мыслей, так как это потенциально сложная проблема, чтобы понять:
- Разделить имя каждого сотрудника на список строк. Лично я бы, наверное, отказался от чего-либо с двумя или менее буквами, если только это не все из названия. Это должно помочь с фамилиями, такими как "De La Cruz", которые могут быть найдены как "Dela Cruz". Сохраните список имен для каждого сотрудника в словаре, который указывает на этого сотрудника.
- Разделите условия поиска так же, как вы разделяете имена в списке. Для каждого поискового термина найдите имена с наименьшим расстоянием Левенштейна, затем для каждого, начиная с самого низкого, повторите поиск с остальными поисковыми терминами, сравнивая его с другими именами этого сотрудника. Повторите этот шаг для каждого слова в запросе. Например, если запрос -
John Smith, найдите наилучшие совпадения имен отдельных слов для John, затем сопоставьте оставшиеся имена для этих сотрудников с "наилучшим соответствием" на Smith и получите сумму расстояний. Затем найдите наилучшие совпадения для Smith и сопоставьте оставшиеся имена на John и суммируйте расстояния. Наилучшим совпадением является тот, который имеет наименьшее общее расстояние. Вы можете предоставить список лучших совпадений, вернув 10 лучших, скажем, отсортированных по общему расстоянию. И не имеет значения, какие имена в базе данных или условия поиска. На самом деле они могут быть совершенно не в порядке, и это не будет иметь значения.
- Подумайте, как обрабатывать дефисные имена. Я, вероятно, разделил бы их, как если бы они не были переносами.
- Рассмотрим символы верхнего / нижнего регистра, если вы этого еще не сделали. Вы должны хранить поиски в одном случае и преобразовать поисковые термины в один и тот же случай перед сравнением.
- Будьте осторожны с акцентированными буквами, многие люди имеют их в своих именах, например
á. Ваш алгоритм не будет работать правильно с ними. Будьте еще более осторожны, если вы ожидаете, что когда-нибудь у вас будут двухбайтовые символы не-альфа, например. Китайский, японский, арабский и др.
Еще два преимущества разделения имен каждого сотрудника:
- «Неиспользуемые» имена не будут учитываться при подсчете, поэтому, если я буду искать только по фамилии, это не будет учитываться при поиске кратчайшего расстояния.
- В том же духе вы можете применить некоторые дополнительные правила, чтобы помочь в поиске нестандартных имен. Например, дефисные имена могут храниться как в виде переносов (например,
Wells-Harvey), составных (WellsHarvey), так и индивидуальных имен (Wells и Harvey отдельно), все в отношении одного и того же сотрудника. Совпадение на малом расстоянии для любого имени - это совпадение на малом расстоянии для сотрудника, опять же, дополнительные имена не учитываются при подсчете.
Вот некоторый базовый код, который, кажется, работает, однако он действительно учитывает только пункты 1, 2 и 4:
using System;
using System.Collections.Generic;
using System.Linq;
namespace EmployeeSearch
{
static class Program
{
static List<string> EmployeesList = new List<string>() { "Jim Carrey", "Uma Thurman", "Bill Gates", "Jon Skeet" };
static Dictionary<int, List<string>> employeesById = new Dictionary<int, List<string>>();
static Dictionary<string, List<int>> employeeIdsByName = new Dictionary<string, List<int>>();
static void Main()
{
Init();
var results = FindEmployeeByNameFuzzy("Umaa Thurrmin");
// Returns:
// (1) Uma Thurman Distance: 3
// (0) Jim Carrey Distance: 10
// (3) Jon Skeet Distance: 11
// (2) Bill Gates Distance: 12
Console.WriteLine(string.Join("\r\n", results.Select(r => $"({r.Id}) {r.Name} Distance: {r.Distance}")));
var results = FindEmployeeByNameFuzzy("Tormin Oma");
// Returns:
// (1) Uma Thurman Distance: 4
// (3) Jon Skeet Distance: 7
// (0) Jim Carrey Distance: 8
// (2) Bill Gates Distance: 9
Console.WriteLine(string.Join("\r\n", results.Select(r => $"({r.Id}) {r.Name} Distance: {r.Distance}")));
Console.Read();
}
private static void Init() // prepare our lists
{
for (int i = 0; i < EmployeesList.Count; i++)
{
// Preparing the list of names for each employee - add special cases such as hyphenation here as well
var names = EmployeesList[i].ToLower().Split(new char[] { ' ' }).ToList();
employeesById.Add(i, names);
// This is not used here, but could come in handy if you want a unique index of names pointing to employee ids for optimisation:
foreach (var name in names)
{
if (employeeIdsByName.ContainsKey(name))
{
employeeIdsByName[name].Add(i);
}
else
{
employeeIdsByName.Add(name, new List<int>() { i });
}
}
}
}
private static List<SearchResult> FindEmployeeByNameFuzzy(string query)
{
var results = new List<SearchResult>();
// Notice we're splitting the search terms the same way as we split the employee names above (could be refactored out into a helper method)
var searchterms = query.ToLower().Split(new char[] { ' ' });
// Comparison with each employee
for (int i = 0; i < employeesById.Count; i++)
{
var r = new SearchResult() { Id = i, Name = EmployeesList[i] };
var employeenames = employeesById[i];
foreach (var searchterm in searchterms)
{
int min = searchterm.Length;
// for each search term get the min distance for all names for this employee
foreach (var name in employeenames)
{
var distance = LevenshteinDistance.Compute(searchterm, name);
min = Math.Min(min, distance);
}
// Sum the minimums for all search terms
r.Distance += min;
}
results.Add(r);
}
// Order by lowest distance first
return results.OrderBy(e => e.Distance).ToList();
}
}
public class SearchResult
{
public int Distance { get; set; }
public int Id { get; set; }
public string Name { get; set; }
}
public static class LevenshteinDistance
{
/// <summary>
/// Compute the distance between two strings.
/// </summary>
public static int Compute(string s, string t)
{
int n = s.Length;
int m = t.Length;
int[,] d = new int[n + 1, m + 1];
// Step 1
if (n == 0)
{
return m;
}
if (m == 0)
{
return n;
}
// Step 2
for (int i = 0; i <= n; d[i, 0] = i++)
{
}
for (int j = 0; j <= m; d[0, j] = j++)
{
}
// Step 3
for (int i = 1; i <= n; i++)
{
//Step 4
for (int j = 1; j <= m; j++)
{
// Step 5
int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;
// Step 6
d[i, j] = Math.Min(
Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
d[i - 1, j - 1] + cost);
}
}
// Step 7
return d[n, m];
}
}
}
Просто позвоните Init() при запуске, затем позвоните
var results = FindEmployeeByNameFuzzy(userquery);
чтобы вернуть упорядоченный список лучших матчей.
Отказ от ответственности: Этот код не оптимален и только кратко проверен, не проверяет наличие нулей, может взорваться и убить котенка и т. Д., И т. Д. Если у вас есть большое количество сотрудников, то это может быть очень медленно. Есть несколько улучшений, которые можно сделать, например, когда вы перебираете алгоритм Левенштейна, вы можете пропасть, если расстояние превышает текущее минимальное расстояние.