Chris Maunder Ответов: 2

Задача кодирования: интеллектуальное сравнение имен

Эту простую идею предложил Брент Хоскиссон.

Создайте метод, который будет разумно сравнивать два имени. "Разумно" означает, что оно должно учитывать различные формы, которые может принимать имя. Например:
John Paul Smith

Будет совпадать с
John Paul Smith
Smith John Paul
John P Smith
Smith John P
J Paul Smith
Smith J Paul
John Smith
Smith John

Решите ли вы использовать бинарное совпадение/отсутствие совпадения или оценку, указывающую на степень уверенности в совпадении, зависит от вас.

Баллы начисляются за краткость кода. Никаких ограничений на количество различных заявок на одного претендента.

Примечание: на следующей неделе я уезжаю в пятницу. Может ли кто-нибудь в галерее арахиса, пожалуйста, отправить вызов в следующую пятницу (24 марта)

Graeme_Grant

Я сделал довольно много из них, так что с удовольствием отдохну и сделаю это для вас на следующей неделе...

PIEBALDconsult

А как насчет Джона Пола Смайта? :Д

PIEBALDconsult

Вот дерьмо, теперь я думаю, что, возможно, изобрел технику, и мне придется ее использовать... Слон! Слон! Слон! Я не хочу этого делать!

На самом деле, сейчас я вспоминаю о задаче, которая была у меня несколько лет назад, когда я должен был попытаться сопоставить аддессы между основным списком и несколькими другими списками. Это было ужасно. Лучшее, что я мог тогда сделать, - это использовать расстояние Левенштейна, а затем вручную просмотреть все, что выше некоторого порога, но меньше 100%.

Graeme_Grant

Опубликовано на этой неделе вызов: Задача кодирования: сортировка списка с помощью свопов и всплывающих окон[^]

2 Ответов

Рейтинг:
2

Henrik Jonsson

Давайте сначала подумаем и уточним требования, в данном случае используя Спецификация на примере, непосредственно закодированные как исполняемые модульные тесты:

[TestMethod]
public void Test_NameMatches()
{
    Assert.IsTrue("John Paul Smith".Matches("Smith John"));    // 1
    Assert.IsTrue("Smith John".Matches("Smith john"));         // 2   
    Assert.IsTrue("Smith Smith".Matches("Smith Smith"));       // 3  
    Assert.IsTrue("Smith Smith".Matches(" Smith Paul Smith "));// 4
    Assert.IsTrue("Smith John".Matches("john S"));             // 5
    Assert.IsTrue("J Smith".Matches("John Smith" ));           // 6
    Assert.IsTrue(" J Paul  Smith ".Matches("John"));          // 7 
    Assert.IsTrue("Smith, J.P".Matches("John Paul Smith"));    // 8
    Assert.IsTrue("John Smith".Matches("John Sm"));            // 9

    Assert.IsFalse("John Jonsson".Matches("John Smith"));      // 10
    Assert.IsFalse("John Smith".Matches( "John Jonsson"));     // 11
}
Обратите внимание здесь, что я включил случай с дублированные имена (3 и 4), аббревиатуры (6-8) , нечувствительность к регистру (2 и 5), дополнительные пробелы (4, 7) и пунктуации (8). Я тоже решил соответствовать неполные имена например, случай 9 для поддержки авто-завершение сценарии. Для удобства чтения кода я решил пойти на String метод расширения.

Лаконичным решением, удовлетворяющим вышеперечисленным требованиям, является
static class Names
{
    public static bool Matches(this String name1, String name2)
    {
       var names1 = name1.Split(Separators, StringSplitOptions.RemoveEmptyEntries);
       var names2 = name2.Split(Separators, StringSplitOptions.RemoveEmptyEntries);
       return names1.Length < names2.Length ? !names1.Except(names2, Comparer).Any() : !names2.Except(names1, Comparer).Any();
    }

    public static char[] Separators = { ' ', '\t', '.', ',' };
}

Для сравнения он использует Comparer который определяется как экземпляр вложенного класса:
private static readonly NameComparer Comparer = new NameComparer();

    private class NameComparer : IEqualityComparer<String>
    {
        public bool Equals(string x, string y)
        {
            return String.Compare(x, 0, y, 0, Math.Min(x.Length, y.Length), ignoreCase: true) == 0;
            return String.Compare(x, 0, y, 0, x.Length, ignoreCase:true) == 0 ||
                   String.Compare(x, 0, y, 0, y.Length, ignoreCase:true) == 0;        }

        public int GetHashCode(string obj)
        {
            return Char.ToUpper(obj[0]).GetHashCode();
        }
    }
Для поддержки сопоставления одного имени я также добавил следующий метод, который принимает всю коллекцию в качестве входных данных и возвращает все совпадения:
public static IEnumerable<String> GetAllMatches(this String name1, IEnumerable<String>  dictionary)
    {
       var names1 = name1.Split(Separators, StringSplitOptions.RemoveEmptyEntries);
       foreach (var name2 in dictionary)
       {
          var names2 = name2.Split(Separators, StringSplitOptions.RemoveEmptyEntries);
          if (names1.Length < names2.Length ? !names1.Except(names2, Comparer).Any() : !names2.Except(names1, Comparer).Any())
          {
              yield return name2;
          }
     }

Проходит ли он экспертная оценка?

PIEBALDconsult

О, и хороший момент насчет нечувствительности к регистру, я совсем забыл об этом.

Рейтинг:
1

Ralf Meier

На этот вызов у меня тоже есть идея. На мой взгляд, ответ такого метода не может быть "истинным" или "ложным" - это должно быть значение, которое дает отношение, насколько хорошо совпадение ...

1-й метод :

Function NameCompare(SourceName As String, NameToCompare As String) As Single
     'Rules :
     'An empty String gives 0.0 as Result
     'Are both String identical the Result is 1.0 = 100% match
     'other cases :
     ' - I give 1 point for each letter which is equal in the Stringparts beginning from the start
     ' - I give an additional point if the Stringpart is complete equal
     ' - I give an additional point if the Stringpart is complete equal and at the right position
     ' - if the NameToCompare beginns with the same letters but have more than the SourceName then each letter more reduces the given points

     If SourceName.Trim = "" Or NameToCompare.Trim = "" Then Return 0.0

     Dim SourceNameArray() As String = SourceName.Split(" ")
     Dim NameToCompareArray() As String = NameToCompare.Split(" ")

     Dim maxPoints As Integer = SourceName.Replace(" ", "").Length + SourceNameArray.Length * 2
     Dim givenPoints As Single = 0.0
     Dim i, j, k As Integer

     For i = 0 To SourceNameArray.Length - 1
         For j = 0 To NameToCompareArray.Length - 1
             If SourceNameArray(i) = NameToCompareArray(j) Then
                 givenPoints += NameToCompareArray(j).Length
                 givenPoints += 1
                 If i = j Then givenPoints += 1
                 Exit For
             ElseIf SourceNameArray(i).Length >= NameToCompareArray(j).Length Then
                 For k = 1 To NameToCompareArray(j).Length
                     If SourceNameArray(i).Substring(0, k) = NameToCompareArray(j).Substring(0, k) Then givenPoints += 1
                 Next
             ElseIf SourceNameArray(i).Length < NameToCompareArray(j).Length Then
                 For k = 1 To SourceNameArray(i).Length
                     If SourceNameArray(i).Substring(0, k) = NameToCompareArray(j).Substring(0, k) Then givenPoints += 1
                 Next
                 givenPoints -= CSng(NameToCompareArray(j).Length - SourceNameArray(i).Length) * 0.25
             End If
         Next
     Next

     If givenPoints = 0 Or maxPoints = 0 Then Return 0.0
     Return givenPoints / CSng(maxPoints)
 End Function


теперь тест с несколькими именами для сравнения :
Dim n0, nc As String
n0 = "John Paul Smith"

nc = "John Paul Smith"
Console.WriteLine(n0 + " :: " + nc + " -> " + NameCompare(n0, nc).ToString("0.00"))
nc = "Smith John Paul"
Console.WriteLine(n0 + " :: " + nc + " -> " + NameCompare(n0, nc).ToString("0.00"))
nc = "John P Smith"
Console.WriteLine(n0 + " :: " + nc + " -> " + NameCompare(n0, nc).ToString("0.00"))
nc = "Smith John P"
Console.WriteLine(n0 + " :: " + nc + " -> " + NameCompare(n0, nc).ToString("0.00"))
nc = "J Paul Smith"
Console.WriteLine(n0 + " :: " + nc + " -> " + NameCompare(n0, nc).ToString("0.00"))
nc = "Smith J Paul"
Console.WriteLine(n0 + " :: " + nc + " -> " + NameCompare(n0, nc).ToString("0.00"))
nc = "John Smith"
Console.WriteLine(n0 + " :: " + nc + " -> " + NameCompare(n0, nc).ToString("0.00"))
nc = "Smith John"
Console.WriteLine(n0 + " :: " + nc + " -> " + NameCompare(n0, nc).ToString("0.00"))
nc = "J P Smith"
Console.WriteLine(n0 + " :: " + nc + " -> " + NameCompare(n0, nc).ToString("0.00"))
nc = "Paul Smith"
Console.WriteLine(n0 + " :: " + nc + " -> " + NameCompare(n0, nc).ToString("0.00"))
nc = "Smith Paul"
Console.WriteLine(n0 + " :: " + nc + " -> " + NameCompare(n0, nc).ToString("0.00"))

nc = "Paula Smith"
Console.WriteLine(n0 + " :: " + nc + " -> " + NameCompare(n0, nc).ToString("0.00"))
nc = "Josephine Smith"
Console.WriteLine(n0 + " :: " + nc + " -> " + NameCompare(n0, nc).ToString("0.00"))
nc = "Johny Smith"
Console.WriteLine(n0 + " :: " + nc + " -> " + NameCompare(n0, nc).ToString("0.00"))


и вот результаты :
John Paul Smith :: John Paul Smith -> 1,00
John Paul Smith :: Smith John Paul -> 0,82
John Paul Smith :: John P Smith -> 0,72
John Paul Smith :: Smith John P -> 0,61
John Paul Smith :: J Paul Smith -> 0,72
John Paul Smith :: Smith J Paul -> 0,61
John Paul Smith :: John Smith -> 0,62
John Paul Smith :: Smith John -> 0,55
John Paul Smith :: J P Smith -> 0,45
John Paul Smith :: Paul Smith -> 0,57
John Paul Smith :: Smith Paul -> 0,61
John Paul Smith :: Paula Smith -> 0,47
John Paul Smith :: Josephine Smith -> 0,21
John Paul Smith :: Johny Smith -> 0,47

PIEBALDconsult

Я не читал это слишком внимательно, но я пытаюсь сделать что-то похожее. Я взвешиваю буквы по тому, насколько они близки к началу "слова".

Ralf Meier

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