В C++ изменить расстояние / функция схожести строк на основе Джаро-Винклера алгоритм


Я написал небольшую библиотеку функций, на основе примера из Розетты, чтобы сравнить две строки и определить сходство, используя Джаро-Винклера.

Короткое копипастить готовый пример:

main.cpp

#include <string>
#include <iostream>

#include "jaro_winkler.hpp"

int main() {
    std::string a { "DWAYNE" };
    std::string b { "DUANE" };

    std::cout << "Similarity for '" << a
              << "' and '" << b
              << "': " << edit_distance::jaro_winkler(a, b)
              << std::endl;

    std::cout << "Similarity for 'MARTHA' and 'MARHTA': "
              << edit_distance::jaro_winkler("MARTHA", "MARHTA")
              << std::endl;
    std::cout << "Similarity for 'DIXON' and 'DICKSONX': "
              << edit_distance::jaro_winkler("DIXON", "DICKSONX")
              << std::endl;
    std::cout << "Similarity for 'JELLYFISH' and 'SMELLYFISH': "
              << edit_distance::jaro_winkler("JELLYFISH", "SMELLYFISH")
              << std::endl;
}

jaro_winkler.ГЭС

#pragma once

#include <cstddef>
#include <cstdint>
#include <algorithm>
#include <string_view>

namespace edit_distance {
    template <typename T = float>
    inline T jaro(const std::string_view source,
                  const std::string_view target)
    {
        const unsigned sl = source.length();
        const unsigned tl = target.length();

        if (sl == 0 || tl == 0) return 0;

        const auto match_distance = (sl == 1 && tl == 1)
                                        ? 0
                                        : (std::max(sl, tl) / 2 - 1);
        auto source_matches = new bool[sl] {0};
        auto target_matches = new bool[tl] {0};
        unsigned matches = 0;
        for (unsigned i = 0; i < sl; ++i) {
            const auto end = std::min(i + match_distance + 1, tl);
            for (auto k = i > match_distance ? (i - match_distance) : 0u; k < end; ++k)
            {
                if (!target_matches[k] && source[i] == target[k]) {
                    source_matches[i] = true;
                    target_matches[k] = true;
                    ++matches;
                    break;
                }
            }
        }
        if (matches == 0) {
            delete[] source_matches;
            delete[] target_matches;
            return 0;
        }

        T t = 0.0;
        unsigned k = 0;
        for (unsigned i = 0; i < sl; ++i) {
            if (source_matches[i]) {
                while (!target_matches[k]) ++k;
                if (source[i] != target[k]) t += 0.5;
                ++k;
            }
        }

        const T m = matches;
        delete[] source_matches;
        delete[] target_matches;
        return (m / sl + m / tl + (m - t) / m) / 3.0;
    }

    template <typename T = float>
    inline T jaro_winkler(const std::string_view source,
                          const std::string_view target,
                          const unsigned prefix = 2,
                          const T boost_treshold = 0.7,
                          const T scaling_factor = 0.1)
    {
        const auto similarity = jaro<T>(source, target);

        if (similarity > boost_treshold) {
            int common_prefix = 0;
            const int l = std::min((unsigned)std::min(source.length(), target.length()), prefix);
            for (; common_prefix < l; ++common_prefix) {
                if (source[common_prefix] != target[common_prefix]) break;
            }
            return similarity + scaling_factor * common_prefix * (1 - similarity);
        } else {
            return similarity;
        }
    }
} // namespace edit_distance

Я был бы рад услышать любые комментарии и критику.



448
8
задан 20 февраля 2018 в 07:02 Источник Поделиться
Комментарии
3 ответа

Вот несколько вещей, которые я сразу вижу в этом коде, что есть номер для улучшения:

template <typename T = float>

Если вы хотите только значения с плавающей точкой передаются в качестве параметров шаблона (так как вы с плавающей точкой арифметические позже), можно добавить:

static_assert(std::is_floating_point<T>::value, 
"jaro can only be used with floating point types");


const unsigned sl = source.length();
const unsigned tl = target.length();

В то время как это может работать на ваш код, типа для длины std::string_view не всегда гарантировано, чтобы быть простой unsigned int. Рассмотрите возможность использования std::size_t как тип переменной, или std::string_view::size_type.


auto source_matches = new bool[sl] {0};
auto target_matches = new bool[tl] {0};


  1. Использование auto путает здесь. Трудно сказать, на первый взгляд , что смысл, который вы пытаетесь использовать динамический массив. auto не сократить типа много, так что вам может понадобиться, чтобы удалить его.

  2. Сырые динамические массивы являются большим источником ошибок. Рассмотрите возможность использования std::vector вместо. Это также позволит вам, чтобы удалить удаляет позже в коде.


for (unsigned i = 0; i < sl; ++i)

Вы могли бы использовать std::size_t здесь. Не делайте предположений о unsigned типов.


delete[] source_matches;
delete[] target_matches;

С помощью std::vector позволит вам удалить это.


(unsigned)std::min(source.length(), target.length())

Если вы должны использовать гипс, предпочитают использовать static_cast, как это делает ваши намерения яснее.

2
ответ дан 20 февраля 2018 в 08:02 Источник Поделиться

Именования

Поскольку пространство имен называется edit_distanceлегко предположить, что jaro() означает яро расстояние, но на самом деле вычисляет яро сходство. Аналогично jaro_winkler(). Может быть стоит добавить суффикс различать их.

Включать сначала свои собственные заголовки

Программа испытаний включает в себя <string> и <iostream> перед "jaro_winkler.hpp". Как правило, я предпочитаю в обратном порядке, чтобы избежать маскировки забыли входят в мои собственные заголовки.

Рефакторинг тестов

Есть много повторов в тестах, которые может быть уменьшена:

static void show_distance(std::string_view a, std::string_view b)
{
std::cout << "Similarity for '" << a
<< "' and '" << b
<< "': " << edit_distance::jaro_winkler_similarity(a, b)
<< std::endl;
}

int main() {
show_distance(std::string{"DWAYNE"}, "DUANE");
show_distance("MARTHA", "MARHTA");
show_distance("DIXON", "DICKSONX");
show_distance("JELLYFISH", "SMELLYFISH");
}

По умолчанию double

В C и c++, double по умолчанию тип с плавающей точкой; float и long double должна быть запрошена специально. Остановиться лучше всего согласуется с этим, так что я бы написал template <typename T = double>.

Вы можете использовать SFINAE для предотвращения плавающей запятой рассматривается:

template <typename T = double>
inline std::enable_if_t<std::is_floating_point_v<T>, T>
jaro_similarity(const std::string_view source, const std::string_view target)

Что, если обе строки пусты?

Я бы утверждать, что две равные строки всегда должны иметь сходство, даже если они пустые. Так что я бы переписать этот тест:

    if (source == target)
return 1;
if (source.empty() || target.empty())
return 0;

Я думаю source.empty() свидетельствует о намерениях немногим лучше, чем sl == 0, но это может быть просто меня.

Упростить испытания

    const auto match_distance = (sl == 1 && tl == 1)
? 0
: (std::max(sl, tl) / 2 - 1);

Так как мы используем std::max(sl, tl) в одной ветке (и с std::max() объявлен constexpr), это может быть дешевле/яснее, чтобы использовать его для теста, тоже:

    const auto match_distance = std::max(sl, tl) < 2
? 0
: std::max(sl, tl) / 2 - 1;

Избегайте сырых указателей

Вместо того, чтобы создавать new bool[]мы обычно предпочитают объекты, что C++ будет убирать за нами. Обычный подход заключается в создании std::vectorно когда Тип bool, что выбирает (нестандартное-контейнер) специализация, которой мы не хотим, по соображениям скорости. Мы могли бы использовать std::vector<char> (или <unsigned char>), или мы могли бы придерживаться bool[] но задать умный указатель, чтобы управлять им:

    auto source_matches = std::make_unique<bool[]>(sl);
auto target_matches = std::make_unique<bool[]>(tl);

Предпочитаю std::size_t за unsigned int для индексов

Стандартный тип размер имеет гарантированно достаточный ассортимент даже самого длинного массива.

Граф, используя целочисленный тип

Вместо накопления 0.5 в то время, мы можем накопить на 1 за раз, а разделить в конце:

    std::size_t t = 0;
std::size_t k = 0;
for (std::size_t i = 0; i < sl; ++i) {
if (source_matches[i]) {
while (!target_matches[k]) ++k;
if (source[i] != target[k]) ++t;
++k;
}
}

const T m = matches;
return (m/sl + m/tl + 1 - t/m/2) / 3.0;

Крошечная опечатка

Я думаю boost_treshold должно быть boost_threshold.

Упрощение вложенных min() звонки

Если мы меняем тип prefix в матче source.length() и target.length()мы можем использовать версию std::min() что можно инициализатор списка:

        const auto l = std::min({source.length(), target.length(), prefix});


Моя версия

#include <algorithm>
#include <cstddef>
#include <memory>
#include <string_view>
#include <type_traits>

namespace edit_distance {
template <typename T = double>
inline std::enable_if_t<std::is_floating_point_v<T>, T>
jaro_similarity(const std::string_view source,
const std::string_view target)
{
if (source == target)
return 1;
if (source.empty() || target.empty())
return 0;

const auto sl = source.length();
const auto tl = target.length();

const auto match_distance = std::max(sl, tl) < 2
? 0
: std::max(sl, tl) / 2 - 1;

auto source_matches = std::make_unique<bool[]>(sl);
auto target_matches = std::make_unique<bool[]>(tl);
std::size_t matches = 0;
for (std::size_t i = 0; i < sl; ++i) {
const auto end = std::min(i + match_distance + 1, tl);
const auto start = i > match_distance ? (i - match_distance) : 0u;
for (auto k = start; k < end; ++k) {
if (!target_matches[k] && source[i] == target[k]) {
target_matches[k] = source_matches[i] = true;
++matches;
break;
}
}
}
if (matches == 0) {
return 0;
}

std::size_t t = 0;
for (std::size_t i = 0, k = 0; i < sl; ++i) {
if (source_matches[i]) {
while (!target_matches[k]) ++k;
if (source[i] != target[k]) ++t;
++k;
}
}

const T m = matches;
return (m/sl + m/tl + 1 - t/m/2) / 3.0;
}

template <typename T = double>
inline T jaro_winkler_similarity(const std::string_view source,
const std::string_view target,
const std::size_t prefix = 2,
const T boost_treshold = 0.7,
const T scaling_factor = 0.1)
{
const auto similarity = jaro_similarity<T>(source, target);

if (similarity > boost_treshold) {
const auto l = std::min({source.length(), target.length(), prefix});
std::size_t common_prefix = 0;
for (; common_prefix < l; ++common_prefix) {
if (source[common_prefix] != target[common_prefix]) break;
}
return similarity
+ scaling_factor * common_prefix * (1 - similarity);
} else {
return similarity;
}
}
} // namespace edit_distance

// Test program

#include <string>
#include <iostream>

static void show_distance(std::string_view a, std::string_view b)
{
std::cout << "Similarity for '" << a
<< "' and '" << b
<< "': " << edit_distance::jaro_winkler_similarity(a, b)
<< std::endl;
}

int main() {
show_distance(std::string{"DWAYNE"}, "DUANE");
show_distance("MARTHA", "MARHTA");
show_distance("DIXON", "DICKSONX");
show_distance("JELLYFISH", "SMELLYFISH");
}

2
ответ дан 21 февраля 2018 в 10:02 Источник Поделиться

Другие отзывы ударит по большинству пунктов я бы сделал, так это дополнительный обзор, который смотрит в первую очередь на фактический алгоритм и тестирования. Я пошел к источнику, в документе 2006 года по Винклера и извлечены тестовые векторы из таблицы на стр. 12.

Я хотел, чтобы автоматизировать тестирование самым простым способом (потому что я ленивый!) и поэтому я использовала этот тест проводов.

main.cpp

#include "test.h"
#include "jaro_winkler.hpp"
#include <string_view>
#include <iostream>

float jw(const std::string_view a, const std::string_view b) {
return edit_distance::jaro_winkler(a, b, 4, 0.78, 0.1);
}

int main() {
bool passed{true};
for (const auto &t: tests) {
passed &= t(jw);
}
std::cout << "\nAll tests "
<< (passed ? "passed" : "did NOT pass!")
<< '\n';
}

тест.ч

#ifndef TEST_H
#define TEST_H
#include <string>
#include <string_view>
#include <vector>

class Test {
public:
Test(const std::string &a, const std::string &b, float expected);
bool operator()(float (&func)(const std::string_view a,
const std::string_view b)) const;
private:
std::string a, b;
float expected;
};

extern const std::vector<Test> tests;
#endif // TEST_H

test.cpp

#include "test.h"
#include <vector>
#include <cmath>
#include <string>
#include <iostream>
#include <iomanip>

Test::Test(const std::string &a, const std::string &b, float expected) :
a{a}, b{b}, expected{expected}
{ }

bool Test::operator()(float (&func)(const std::string_view a, const std::string_view b)) const {
constexpr float epsilon{0.0005};
const auto dist{func(a, b)};
const auto delta{std::abs(dist - expected)};
const auto result{epsilon > delta};
std::cout << std::setw(7) << std::boolalpha << result
<< std::setw(15) << a
<< std::setw(15) << b
<< '\t' << std::fixed << std::setprecision(3) << dist
<< '\t' << std::setprecision(4) << delta
<< '\n';
return result;
}

/*
* These sample values are from
* "Overview of Record Linkage and Current Research Directions"
* Winkler, W. (2006)
* https://www.census.gov/srd/papers/pdf/rrs2006-02.pdf
*/
const std::vector<Test> tests{
{ "SHACKLEFORD", "SHACKELFORD", 0.982 },
{ "DUNNINGHAM", "CUNNIGHAM", 0.896 },
{ "NICHLESON", "NICHULSON", 0.956 },
{ "JONES", "JOHNSON", 0.832 },
{ "MASSEY", "MASSIE", 0.933 },
{ "ABROMS", "ABRAMS", 0.922 },
{ "HARDIN", "MARTINEZ", 0.000 },
{ "ITMAN", "SMITH", 0.000 },

{ "JERALDINE", "GERALDINE", 0.926 },
{ "MARHTA", "MARTHA", 0.961 },
{ "MICHELLE", "MICHAEL", 0.921 },
{ "JULIES", "JULIUS", 0.933 },
{ "TANYA", "TONYA", 0.880 },
{ "DWAYNE", "DUANE", 0.840 },
{ "SEAN", "SUSAN", 0.805 },
{ "JON", "JOHN", 0.933 },
{ "JON", "JAN", 0.000 },

};

Результаты

При компиляции и связаны с вашим исходным кодом (и с заданными параметрами, как показано в main) я нашла почти идеальное соглашение. Единственная разница заключалась в том, видимо, что в то время как значения выше порогового значения повышаются (как в коде), значения ниже ужимаются до 0. Я внес соответствующие изменения в код, и в итоге получается, что все значения совпадают:

   true    SHACKLEFORD    SHACKELFORD   0.982   0.0002
true DUNNINGHAM CUNNIGHAM 0.896 0.0003
true NICHLESON NICHULSON 0.956 0.0004
true JONES JOHNSON 0.832 0.0004
true MASSEY MASSIE 0.933 0.0003
true ABROMS ABRAMS 0.922 0.0002
true HARDIN MARTINEZ 0.000 0.0000
true ITMAN SMITH 0.000 0.0000
true JERALDINE GERALDINE 0.926 0.0001
true MARHTA MARTHA 0.961 0.0001
true MICHELLE MICHAEL 0.921 0.0004
true JULIES JULIUS 0.933 0.0003
true TANYA TONYA 0.880 0.0000
true DWAYNE DUANE 0.840 0.0000
true SEAN SUSAN 0.805 0.0000
true JON JOHN 0.933 0.0003
true JON JAN 0.000 0.0000

All tests passed

2
ответ дан 21 февраля 2018 в 04:02 Источник Поделиться