C # проверка имени человека и алгоритм сопоставления - PullRequest
Новая
       27

C # проверка имени человека и алгоритм сопоставления

0 голосов
/ 14 октября 2019

Существует ли алгоритм или библиотека C # для определения правильности имени человека или, если нет, для нахождения его ближайшего соответствия?

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

ДляПример: кто-то вставляет имя «Гилиам», в то время как оно должно быть «Уильям». Я хочу знать, есть ли какой-либо алгоритм (или группа из них), чтобы обнаружить ошибку и предложить исправление.

Все решения, которые приходят мне в голову, включают в себя реализацию огромного словаря человеческого имени и использование его дляпроверить правильность каждого входного имени, совпадающего по одному ... И это звучит ужасно для меня, поэтому я хочу попросить лучшего подхода.

Спасибо.

1 Ответ

1 голос
/ 14 октября 2019

В сущности, вы спрашиваете, как создать программу проверки орфографии с данным словарем. Один из способов сделать это, не требующий поиска и тестирования каждой возможной записи в списке, - это решить проблему: создать список возможных перестановок из пользовательского ввода и протестировать каждую из них, чтобы убедиться, что ониВы в списке. Это гораздо более управляемая проблема.

Например, вы можете использовать функцию, подобную этой, чтобы генерировать каждую возможную перестановку, которую один «правка» может получить из данного слова: 

static HashSet<string> GenerateEdits(string word)
{
    // Normalize the case
    word = word.ToLower();

    var splits = new List<Tuple<string, string>>();
    for (int i = 0; i < word.Length; i++)
    {
        splits.Add(new Tuple<string, string>(word.Substring(0, i), word.Substring(i)));
    }

    var ret = new HashSet<string>();

    // All cases of one character removed
    foreach (var cur in splits)
    {
        if (cur.Item2.Length > 0)
        {
            ret.Add(cur.Item1 + cur.Item2.Substring(1));
        }
    }

    // All transposed possibilities
    foreach (var cur in splits)
    {
        if (cur.Item2.Length > 1)
        {
            ret.Add(cur.Item1 + cur.Item2[1] + cur.Item2[0] + cur.Item2.Substring(2));
        }
    }

    var letters = "abcdefghijklmnopqrstuvwxyz";

    // All replaced characters
    foreach (var cur in splits)
    {
        if (cur.Item2.Length > 0)
        {
            foreach (var letter in letters)
            {
                ret.Add(cur.Item1 + letter + cur.Item2.Substring(1));
            }
        }
    }

    // All inserted characters
    foreach (var cur in splits)
    {
        foreach (var letter in letters)
        {
            ret.Add(cur.Item1 + letter + cur.Item2);
        }
    }

    return ret;
}

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

// Example file from:
// https://raw.githubusercontent.com/smashew/NameDatabases/master/NamesDatabases/first%20names/all.txt
string source = @"all.txt";
var names = new HashSet<string>();
using (var sr = new StreamReader(source))
{
    string line;
    while ((line = sr.ReadLine()) != null)
    {
        names.Add(line.ToLower());
    }
}

var userEntry = "Giliam";
var found = false;
if (names.Contains(userEntry.ToLower()))
{
    Console.WriteLine("The entered value of " + userEntry + " looks good");
    found = true;
}

if (!found)
{
    // Try edits one edit away from the user entry
    foreach (var test in GenerateEdits(userEntry))
    {
        if (names.Contains(test))
        {
            Console.WriteLine(test + " is a possibility for " + userEntry);
            found = true;
        }
    }
}

if (!found)
{
    // Try edits two edits away from the user entry
    foreach (var test in GenerateEdits(userEntry))
    {
        foreach (var test2 in GenerateEdits(test))
        {
            if (names.Contains(test))
            {
                Console.WriteLine(test + " is a possibility for " + userEntry);
                found = true;
            }
        }
    }
}

kiliam is a possibility for Giliam
liliam is a possibility for Giliam
viliam is a possibility for Giliam
wiliam is a possibility for Giliam

Конечно, поскольку вы говорите очеловеческие имена, вы, в лучшем случае, внесли это предложение и были очень готовы к странным написаниям и написанию вещей, которых вы никогда не видели. И если вы хотите поддерживать другие языки, реализация GenerateEdits становится более сложной, если учесть, что считается «опечаткой»

...