WikiSort.ru - Не сортированное

Расстояние Джаро

Расстояние Джаро ${\displaystyle d_{j}}$ между двумя заданными строками ${\displaystyle s_{1}}$ и ${\displaystyle s_{2}}$ это:

${\displaystyle d_{j}=\left\{{\begin{array}{l l}0&{\text{когда }}m=0\\{\frac {1}{3}}\left({\frac {m}{|s_{1}|}}+{\frac {m}{|s_{2}|}}+{\frac {m-t}{m}}\right)&{\text{в остальных случаях}}\end{array}}\right.}$

Где:

• ${\displaystyle |s_{i}|}$  — длина строки ${\displaystyle s_{i}}$ ;
• ${\displaystyle m}$  — число совпадающих символов (см. ниже);
• ${\displaystyle t}$  — половина числа транспозиций (см. ниже).

Два символа из ${\displaystyle s_{1}}$ и ${\displaystyle s_{2}}$ соответственно, считаются совпадающими только если они одинаковы и не дальше, чем ${\displaystyle \left\lfloor {\frac {\max(|s_{1}|,|s_{2}|)}{2}}\right\rfloor -1}$ .

Каждый символ строки ${\displaystyle s_{1}}$ сравнивается со всеми соответствующими ему символами в ${\displaystyle s_{2}}$ . Количество совпадающих (но отличающихся порядковыми номерами) символов, которое делится на 2, определяет число транспозиций. Например, при сравнении слова CRATE со словом TRACE, только 'R' 'A' и 'Е' являются совпадающими символами, то есть m=3. Хотя 'C' и 'T' появляются в обоих строках, они дальше, чем на 1, то есть floor(5/2)-1=1. Следовательно, t=0 . В сравнении DwAyNE с DuANE соответствующие буквы находятся уже в том же самом порядке D-A-N-E, так что никаких перестановок не требуется.

Расстояние Джаро — Винклера

Расстояние Джаро — Винклера использует коэффициент масштабирования ${\displaystyle p}$ , что дает более благоприятные рейтинги строкам, которые совпадают друг с другом от начала до определённой длины ${\displaystyle \ell }$ , которая называется префиксом. Даны две строки ${\displaystyle s_{1}}$ и ${\displaystyle s_{2}}$ . Их расстояние Джаро — Винклера ${\displaystyle d_{w}}$ это:

${\displaystyle d_{w}=d_{j}+(\ell p(1-d_{j}))}$

где:

• ${\displaystyle d_{j}}$  — расстояние Джаро для строк ${\displaystyle s_{1}}$ и ${\displaystyle s_{2}}$
• ${\displaystyle \ell }$  — длина общего префикса от начала строки до максимума 4-х символов
• ${\displaystyle p}$  — постоянный коэффициент масштабирования, использующийся для того, чтобы скорректировать оценку в сторону повышения для выявления наличия общих префиксов. ${\displaystyle p}$ не должен превышать 0,25, поскольку в противном случае расстояние может стать больше, чем 1. Стандартное значение этой константы в работе Винклера: ${\displaystyle p=0.1}$ .

Хотя расстояние Джаро-Винклера часто называют метрикой расстояния, это не метрика в математическом смысле этого слова, потому что оно не подчиняется неравенству треугольника . Также расстояние Джаро-Винклера не удовлетворяет аксиоме, которая гласит, что ${\displaystyle d(x,y)=0\leftrightarrow x=y}$ ^[1].

В некоторых реализациях алгоритма расчёта расстояния Джаро — Винклера префиксный бонус ${\displaystyle \ell p(1-d_{j})}$ добавляется, только если сравниваемые строки имеют расстояние Джаро выше установленного «порога усиления» ${\displaystyle b_{t}}$ . Порог в реализации Винклера составил 0,7.

${\displaystyle d_{w}=\left\{{\begin{array}{l l}d_{j}&{\text{если }}d_{j}<b_{t}\\d_{j}+(\ell p(1-d_{j}))&{\text{в остальных случаях}}\end{array}}\right.}$

Пример 1

Даны строки ${\displaystyle s_{1}}$ MARTHA и ${\displaystyle s_{2}}$ MARHTA. Представим их пересечение в табличном виде:

Здесь максимальное расстояние составляет 6/2 — 1 = 2. В желтых ячейках приведенной таблицы указаны единицы, когда символы идентичны (имеется совпадение), и нули в противном случае.

Получается:

• ${\displaystyle m=6}$
• ${\displaystyle |s_{1}|=6}$
• ${\displaystyle |s_{2}|=6}$
• Есть несовпадающие символы T/H и Н/Т, в результате: ${\displaystyle t={\frac {2}{2}}=1}$

Расстояние Джаро:

${\displaystyle d_{j}={\frac {1}{3}}\left({\frac {6}{6}}+{\frac {6}{6}}+{\frac {6-1}{6}}\right)=0.9(4)}$

Чтобы найти результат Джаро — Винклера с помощью стандартного веса ${\displaystyle p=0.1}$ мы продолжаем искать:

${\displaystyle \ell =3}$

Таким образом:

${\displaystyle d_{w}=0.9(4)+(3\cdot 0.1(1-0.9(4)))=0.96(1)}$

Пример 2

Даны строки ${\displaystyle s_{1}}$ DWAYNE и ${\displaystyle s_{2}}$ DUANE. Получается:

• ${\displaystyle m=4}$
• ${\displaystyle |s_{1}|=6}$
• ${\displaystyle |s_{2}|=5}$
• ${\displaystyle t=0}$

Расстояние Джаро:

${\displaystyle d_{j}={\frac {1}{3}}\left({\frac {4}{6}}+{\frac {4}{5}}+{\frac {4-0}{4}}\right)=0.8(2)}$

Чтобы найти результат Джаро-Винклера с помощью стандартного веса ${\displaystyle p=0.1}$ мы продолжаем искать:

${\displaystyle \ell =1}$

Таким образом:

${\displaystyle d_{w}=0.8(2)+(1\cdot 0.1(1-0.8(2)))=0.84}$

Пример 3

Даны строки ${\displaystyle s_{1}}$ DIXON и ${\displaystyle s_{2}}$ DICKSONX. Получается:

Здесь закрашенные клетки — это окно соответствия для каждого символа. Единицы в ячейке указывает на совпадение. Заметим, что два икса (X) не считаются совпавшими, поскольку они находятся за пределами третьего окна совпадения.

• ${\displaystyle m=4}$
• ${\displaystyle |s_{1}|=5}$
• ${\displaystyle |s_{2}|=8}$
• ${\displaystyle t=0}$

Расстояние Джаро:

${\displaystyle d_{j}={\frac {1}{3}}\left({\frac {4}{5}}+{\frac {4}{8}}+{\frac {4-0}{4}}\right)=0.7(6)}$

Чтобы найти результат Джаро-Винклера с помощью стандартного веса ${\displaystyle p=0.1}$ мы продолжаем искать:

${\displaystyle \ell =2}$

Таким образом:

${\displaystyle d_{w}=0.7(6)+(2\cdot 0.1(1-0.7(6)))=0.81(3)}$