В статистике сходство Джаро-Винклера — это способ измерения сходства между двумя строками.
Сходство Джаро (sim j ) между двумя строками определяется как:
sim j = 1/3 * ( м /|с 1 | + м/|с 2 | + (мт)/м )
куда:
- m : Количество совпадающих символов
- Два символа из s 1 и s 2 считаются совпадающими, если они одинаковы и не дальше, чем [max(|s 1 |, |s 2 |) / 2] – 1 символ друг от друга.
- |с 1 | , |с 2 | : Длина первой и второй строк соответственно.
- t : Количество транспозиций
- Рассчитывается как количество совпадающих символов (но с разным порядком следования), деленное на 2.
Сходство Яро-Винклера (sim w ) определяется как:
sim w = sim j + lp (1 – sim j )
куда:
- sim j : Сходство Джаро между двумя строками, s 1 и s 2
- l : Длина общего префикса в начале строки (максимум 4 символа)
- p : Масштабный коэффициент для того, насколько оценка корректируется вверх из-за наличия общих префиксов. Обычно это определяется как p = 0,1 и не должно превышать p = 0,25.
Сходство Яро-Винклера между двумя строками всегда находится в диапазоне от 0 до 1, где:
- 0 указывает на отсутствие сходства между строками
- 1 указывает, что строки точно совпадают
Примечание.Расстояние Яро-Винклера определяется как 1 – sim w .
В следующем примере показано, как на практике вычислить сходство Яро-Винклера между двумя строками.
Пример. Вычисление сходства Яро-Винклера между двумя строками
Предположим, у нас есть следующие две строки:
- Строка 1 (s1): мышь
- Строка 2 (s 2 ): без звука
Во-первых, давайте вычислим сходство Яро между этими двумя строками:
sim j = 1/3 * ( м /|с 1 | + м/|с 2 | + (мт)/м )
куда:
- m : Количество совпадающих символов
- Два символа из s 1 и s 2 считаются совпадающими, если они одинаковы и не дальше, чем [max(|s 1 |, |s 2 |) / 2] – 1 символ друг от друга.
В этом случае [max(|s 1 |, |s 2 |) / 2] – 1 вычисляется как 5/2 – 1 = 1,5. Мы определили бы три буквы как совпадающие: m, u, e. Таким образом, m = 3 .
- |с 1 | , |с 2 | : Длина первой и второй строк соответственно.
В этом случае |s 1 | = 5 и |s 1 | = 4 .
- t : Количество транспозиций
- Рассчитывается как количество совпадающих символов (но с разным порядком следования), деленное на 2.
В этом случае есть три совпадающих символа, но они уже находятся в том же порядке последовательности, поэтому t = 0 .
Таким образом, мы бы рассчитали сходство Яро как:
сим j = 1/3 * (3/5 + 3/4 + (3-0)/3) = 0,78333.
Далее, давайте вычислим сходство Джаро-Винклера (sim w ) как:
sim w = sim j + lp (1 – sim j )
В этом случае мы будем рассчитывать:
сим ш = 0,78333 + (1)*(0,1)(1 – 0,78333) = 0,805.
Сходство Яро-Винклера между двумя строками составляет 0,805 .
Поскольку это значение близко к 1, это говорит нам о том, что две строки очень похожи.
Мы можем подтвердить, что это правильно, рассчитав сходство Яро-Винклера между двумя строками в R:
library (stringdist)
#calculate Jaro-Winkler similarity between 'mouse' and 'mute'
1 - stringdist("mouse", "mute", method = "jw", p= 0.1 )
[1] 0.805
Это соответствует значению, которое мы рассчитали вручную.
Дополнительные ресурсы
В следующих руководствах объясняется, как рассчитать другие показатели сходства:
Введение в несходство Брея-Кертиса
Введение в индекс подобия Жаккара