Алгоритм Soundex на C#

Культурные различия и ошибки ввода могут привести к тому, что слова будут написаны иначе, чем ожидал пользователь. Это затрудняет быстрый поиск информации. Алгоритм Soundex может облегчить эту проблему, назначая коды на основе звучания слов.



Soundex

Алгоритм Soundex генерирует четырехсимвольные коды на основе произношения английских слов. Эти коды можно использовать для сравнения двух слов, чтобы определить, похожи ли они по звучанию. Это может быть очень полезно при поиске информации в базе данных или текстовом файле, особенно при поиске имен, которые обычно пишутся с ошибками.

Примером использования Soundex является функция поиска в базе данных клиентов. При выполнении текстового поиска по фамилии "Smith" люди с именем "Smythe" не будут найдены. Однако, поскольку код Soundex для обеих фамилий "S530", фонетический поиск на основе Soundex позволит найти обоих клиентов. Коды и данные также могут быть использованы для того, чтобы спросить пользователя: "Вы имели в виду Smythe?".

Алгоритм

Алгоритм Soundex применяет ряд правил к строке для генерации четырехсимвольного кода. Этапы кодирования заключаются в следующем:

• Игнорируйте все символы в кодируемой строке, за исключением английских букв от A до Z.
• Первая буква кода Soundex - это первая буква кодируемой строки.
• После первой буквы в строке не кодируйте гласные или буквы H, W и Y. Эти буквы могут влиять на код, присутствуя, но не кодируются напрямую.
• Назначьте числовую цифру от одного до шести всем буквам после первой, используя следующие сопоставления:
  
  
  • 1: B, F, P или V
  • 2: C, G, J, K, Q, S, X, Z
  • 3: D, T
  • 4: Л
  • 5: М, Н
  • 6: Р
• Если соседние цифры совпадают, удалите все эти цифры, кроме одной, если только в исходном тексте между ними не было найдено гласной, H, W или Y. Код C#, описанный ниже, использует временный заполнитель для этих некодируемых букв, чтобы избежать неправильного удаления соседних совпадающих цифр. ПРИМЕЧАНИЕ: Раздел "Варианты" в конце статьи описывает альтернативную версию этого правила.
• Принудительно введите код длиной в четыре символа, дополнив его нулевыми символами или отрезав лишнее.

Реализация Soundex в C#

В этой статье мы реализуем алгоритм Soundex на C#. Мы создадим класс, содержащий два общедоступных метода. Первый метод сгенерирует код Soundex для строки. Второй будет сравнивать две строки и возвращать значение, указывающее, насколько они похожи по звучанию.

Для начала создайте новый проект консольного приложения и добавьте класс с именем "Soundex".

Вычисление кода Soundex

Первым шагом является добавление подписи метода GetSoundex. Этот открытый метод принимает один параметр, содержащий строку для кодирования. Он возвращает код Soundex в виде строки. Чтобы создать метод, добавьте следующий код в класс Soundex:

public string GetSoundex(string value)
{
} 

При проверке символов входной строки проще работать только в одном случае. Поскольку начальная буква кода Soundex обычно представлена в верхнем регистре, мы начнем с заглавной буквы строки. Мы также создадим новый StringBuilder для хранения кода Soundex по мере его создания. Таким образом, первые две строки метода GetSoundex являются:

value = value.ToUpper();
StringBuilder soundex = new StringBuilder(); 

С инициализированным алгоритмом мы можем обрабатывать отдельные буквы в строке, перебирая символы и вызывая метод с именем "AddCharacter", когда буква найдена. AddCharacter отвечает за добавление буквы и цифр Soundex в объект StringBuilder. Мы создадим метод AddCharacter позже.

foreach (char ch in value)
{
    if (char.IsLetter(ch))
        AddCharacter(soundex, ch);
}

В конце цикла StringBuilder будет содержать преобразованные символы, но, скорее всего, будет иметь длину не более четырех символов. Он также может включать символы-заполнители, как мы вскоре увидим. Заключительная часть метода GetSoundex устраняет эти проблемы перед преобразованием StringBuilder в строку и возвращением результата. Добавьте последние три строки в метод:

RemovePlaceholders(soundex);
FixLength(soundex);
return soundex.ToString();

Добавление кодов символов Soundex

Метод GetSoundex вызывает несколько частных методов, которые еще предстоит определить. Первый-это метод AddCharacter, который кодирует букву как символ Soundex и добавляет ее в код. Первая буква копируется в строку Soundex; последующие буквы сначала преобразуются в цифры и добавляются только в том случае, если они не являются дубликатами предыдущей цифры.

private void AddCharacter(StringBuilder soundex, char ch)
{
    if (soundex.Length == 0)
        soundex.Append(ch);
    else
    {
        string code = GetSoundexDigit(ch);
        if (code != soundex[soundex.Length - 1].ToString())
            soundex.Append(code);
    }
}

Определение цифр Soundex

Метод GetSoundexDigit кодирует буквы в виде цифр. Буква преобразуется в значение от одного до шести в соответствии с правилами алгоритма. Если буква не кодируется, в качестве заполнителя используется символ полной остановки (точки). Заполнители гарантируют, что дубликаты не удаляются при разделении гласной, H, W или Y.

private string GetSoundexDigit(char ch)
{
    string chString = ch.ToString();
 
    if ("BFPV".Contains(chString))
        return "1";
    else if ("CGJKQSXZ".Contains(chString))
        return "2";
    else if ("DT".Contains(chString))
        return "3";
    else if (ch == 'L')
        return "4";
    else if ("MN".Contains(chString))
        return "5";
    else if (ch == 'R')
        return "6";
    else
        return ".";
}

Удаление символов-заполнителей

Следующий метод удаляет символы-заполнители из объекта StringBuilder, оставляя только закодированные символы. Это достигается с помощью вызова метода замены StringBuilder:

private void RemovePlaceholders(StringBuilder soundex)
{
    soundex.Replace(".", "");
}

Установка длины звукового сигнала

Окончательный код должен состоять из четырех цифр. Метод FixLength заполняет строку нулями, если она слишком короткая, или усекает ее, если она слишком длинная:.

private void FixLength(StringBuilder soundex)
{
    int length = soundex.Length;
    if (length < 4)
        soundex.Append(new string('0', 4 - length));
    else
        soundex.Length = 4;
}

Сравнение строк

Второй общедоступный метод класса Soundex сравнивает две строки, чтобы определить, похожи ли они по звучанию. В данном случае мы используем простой алгоритм. Во-первых, две строки кодируются с использованием алгоритма Soundex. Затем сравниваются пары символов в каждой из четырех позиций. Метод возвращает количество совпадающих пар. Результат четыре указывает на наилучшее возможное совпадение и ноль - на наихудшее возможное совпадение. Эти значения полезны при сортировке списка возможных совпадений с наиболее вероятным, появляющимся первым.

public int Compare(string value1, string value2)
{
    int matches = 0;
    string soundex1 = GetSoundex(value1);
    string soundex2 = GetSoundex(value2);
 
    for (int i = 0; i < 4; i++)
        if (soundex1[i] == soundex2[i]) matches++;
 
    return matches;
}

Тестирование методов

Для тестирования алгоритмов мы можем использовать основной метод консольного приложения. Следующий тест кодирует две строки и сравнивает их коды Soundex. Попробуйте изменить строки, чтобы увидеть результаты.

string value1 = "Smith";
string value2 = "Smythe";
 
Soundex soundex = new Soundex();
Console.WriteLine(soundex.GetSoundex(value1));      // Выведет "S530"
Console.WriteLine(soundex.GetSoundex(value2));      // Выведет "S530"
Console.WriteLine(soundex.Compare(value1, value2)); // Выведет "4"

Вариации

Существуют вариации алгоритма Soundex, что затрудняет сравнение кодов Soundex, генерируемых различными системами. Один из вариантов состоит в том, чтобы определить, когда первые несколько согласных слова кодируются как одна и та же числовая цифра, и удалить это дублирование. Мы можем добавить эту модификацию, изменив метод AddCharacter, как показано ниже. Обратите внимание на дополнительную проверку односимвольного кода Soundex, в котором дублированные цифры не добавляются.

private void AddCharacter(StringBuilder soundex, char ch)
{
    if (soundex.Length == 0)
        soundex.Append(ch);
    else if (soundex.Length == 1) 
    {
        string code = GetSoundexDigit(ch);
        string initialCode = GetSoundexDigit(soundex[0]);
        if (code != initialCode)
        soundex.Append(code);
    } 
    else
    {
        string code = GetSoundexDigit(ch);
        if (code != soundex[soundex.Length - 1].ToString())
        soundex.Append(code);
    }
} 

Другой распространенный вариант заключается в том, чтобы по-разному относиться к буквам H, W и Y как к гласным, полностью игнорируя их и удаляя повторяющиеся коды, разделенные одной из трех букв. Вы можете использовать этот вариант, изменив метод GetSoundexDigit следующим образом:

private string GetSoundexDigit(char ch)
{
    string chString = ch.ToString();
 
    if ("BFPV".Contains(chString))
        return "1";
    else if ("CGJKQSXZ".Contains(chString))
        return "2";
    else if ("DT".Contains(chString))
        return "3";
    else if (ch == 'L')
        return "4";
    else if ("MN".Contains(chString))
        return "5";
    else if (ch == 'R')
        return "6";
    else if ("HWY".Contains(chString))
        return "";
    else
        return ".";
}

заметки, си шарп, математика, алгоритмы