В области информатики и статистики сходство Джаро - Винклера представляет собой меру схожести строк для измерения расстояния между двумя последовательностями символов. В публикации рассмотрены некоторые особенности алгоритма, и представлен вариант его реализации на языке 1С.
Сходство Джаро - Винклера
В области информатики и статистики сходство Джаро — Винклера представляет собой меру схожести строк для измерения расстояния между двумя последовательностями символов. Это вариант, который в 1999 году предложил Уильям Э. Винклер(William E. Winkler) на основе расстояния Джаро (1989, Мэтью А. Джаро, Matthew A. Jaro). Неформально, расстояние Джаро между двумя словами — это минимальное число одно— символьных преобразований, которое необходимо для того, чтобы изменить одно слово в другое.
Расстояние Джаро
Расстояние Джаро - dj между двумя заданными строками s1 и s2 это:
dj = (m/a + m/b + (m-t)/m)/3;
Где: a — длина строки s1; b - длина строки s2; m — число совпадающих символов (см. ниже); t — половина числа транспозиций (см. ниже).
Два символа из s1 и s2 соответственно, считаются совпадающими только: если они одинаковы, и их позиции относительно друг-друга находятся не дальше, чем на d - максимальное расстояние для поиска,
Где:
d = Цел(Макс(a,b)/2)-1;
Каждый символ строки s1 сравнивается со всеми символами в s2 на допустимом расстоянии d. Количество совпадающих (но отличающихся порядковыми номерами) символов, которое делится на 2, определяет число транспозиций - tr.
Таким образом:
t = Цел(tr/2);
Расстояние Джаро — Винклера
Расстояние Джаро — Винклера использует коэффициент масштабирования - p, что дает более благоприятные рейтинги строкам, которые совпадают друг с другом от начала до определённой длины - L, которая называется префиксом. Даны две строки s1 и s2. Их расстояние Джаро — Винклераdw это:
dw = dj + (L * p * (1-dj));
где: dj — расстояние Джаро для строк s1 и s2 L - длина общего префикса от начала строки до максимума 4-х символов. (цепочка совпавших символов
с тождественными порядковыми номерами) p — постоянный коэффициент масштабирования, использующийся для того, чтобы скорректировать оценку в сторону повышения для выявления наличия общих префиксов. p не должен превышать 0,25, поскольку в противном случае расстояние может стать больше, чем 1. Стандартное значение этой константы в работе Винклера: p=0.1;
В некоторых реализациях алгоритма расчёта расстояния Джаро — Винклера префиксный бонус: L* p * (1-dj) добавляется, только если сравниваемые строки имеют расстояние Джаро выше установленного «порога усиления»bt. Порог в реализации Винклера составил 0.7
Пример:
Даны строки s1 и s2 MARTHA и MARHTA. Представим их пересечение в табличном виде:
M
A
R
T
H
A
a
b
d
m
tr
t
L
dj
dw
M
1
6
6
2
6
2
1
3
0,944
0,961
A
1
R
1
H
1
T
1
A
1
s1 = "MARTHA";
s2 = "MARHTA";
a = СтрДлина(s1);
b = СтрДлина(s2);
d = Цел(Макс(a,b)/2-1);
m = 6;
tr = 2;
t = Цел(tr/2);
L = 3;
p = 0.1;
dj = (6/6 + 6/6 + (6-1)/6)/3;
dw = 0.994 + (3 * 0.1 * (1-0.994));
dw = 0.961;
Практика
Попробуем реализовать этот алгоритм на языке 1с.
Для начала нам нужен вложенный цикл для сравнения всех символов строки s1 со всеми символами строки s2
Для Инд1 = 1 По a Цикл
Символ1 = Сред(s1,Инд1,1);
Для Инд2 = 1 По b Цикл
Символ2 = Сред(s2,Инд2,1);
КонецЦикла; // Для Инд2 По b
КонецЦикла; // Для Инд1 По a
Но перед тем, как мы извлечем очередной символ из строки s2, нужно убедиться, что выполняется условие, связанное с ограничением расстояния поиска - d
Ограничим вложенный цикл по количеству лишних интераций.
Если при поиске "назад" расстояние межу символами ещё не достиглоd - не выполняя сравнения переходим к следующему символу строки s2
Если при поиске "вперед" расстояние между символами уже превысилоd, прекращаем поиск и переходим к следующему символу в строке s1.
Если Инд2 < Инд1 - d Тогда
Продолжить;
КонецЕсли;
Если Инд2 > Инд1 + d Тогда
Прервать;
КонецЕсли;
Теперь мы находимся в "разрешенном" диапазоне поиска в строке s2 для текущего символа строки s1
Самое время сравнивать символы и вычислять величины m и tr - т.е. совпадающие символы и транспозиции.
Символ2 = Сред(s2,Инд2,1);
Если Символ1 = Символ2 Тогда
m = m + 1;
Если Инд1 <> Инд2 Тогда
// транспозиция --(не совпали порядковые номера
tr = tr + 1;
КонецЕсли;
КонецЕсли; // Симв Символ1 = Символ2
Ещё нужно вычислить длину префикса - L
Для этого нужно соблюсти условие:
Должны совпасть символы строк s1 и s2 находящиеся параллельно на 1-й, 2-ой и т.д. позициях, но не более четырех подряд.
Эту задачу мы решим так:
присвоим L=1; при совпадении первых символов;
далее отслеживаем выполнение следующих условий:
L не больше 4-х;
значение L увеличивается пропорционально с порядковым номером текущего символа строки s1, чем обеспечим непрерывность цепочки.
// считаем префикс (до 4-х)
Если Инд1 = Инд2 Тогда
Если Инд1 = 1 Тогда
L = 1;
Иначе
Если L <= 3 И Инд1 = L + 1 Тогда
L = L + 1; //
КонецЕсли;
КонецЕсли;
КонецЕсли; //Инд1 = Инд2
Осталось прописать финальные вычисления и вернуть результат. И поскольку все формулы были даны выше, просто соберём их все вместе.
// расчет коэффициента
Если m > 0 Тогда
t = Цел(tr/2); // половина количества транспозиций
dj = (m/a + m/b + (m-t)/m)/3; // Расстояние Джаро
Если dj >= bt Тогда
dw = dj + (L * p * (1-dj)); // Расстояние Джаро-Винклера
Иначе
dw = dj; // dj < bt - меньше "порога усиления" применения префиксного бонуса
КонецЕсли;
КонецЕсли;
// результат
Возврат dw;
Как думаете, заработает код? Конечно заработает! Но... на некоторых сравнениях он начнет выдавать невообразимые результаты. Простые примеры из Википедий и пр., отрабатывались вполне предсказуемо. На словах по-заковыристей - сбой.
Например следующие словосочетания дали такой результат:
АБРАКАДАБРА в s1 и s2 - 1.287
РАЗРАБОТКА и РАЗРАБОТЧИК - 1.058
АБРАКАДАБРА и АВАДАКЕДАВРА - 1.147
Давайте разберемся почему, при, казалось бы, соблюдении всех условий, код работает неверно?
Лучший способ увидеть ошибку - визуализировать её. Поместим все наши проблемные слова как мы любим - в табличном поле.
Пример 1. АБРАКАДАБРА
А
Б
Р
А
К
А
Д
А
Б
Р
А
a
b
Infostart MagicInput
Улучшенный поиск по строке в 1С:
находит объекты по любой части названия и нескольким ключевым фрагментам, распознаёт ввод в другой раскладке и показывает статусы прямо в списке подбора. Помогает быстрее находить нужные элементы, сокращает ошибки при вводе и подключается как готовое расширение для 1С 8.3/8.5 — без доработок.
Описанный ниже подход позволяет в три шага заполнять формулы в Excel файлы, вне зависимости от ОС сервера (MS Windows Server или Linux).
Подход подразумевает отказ от работы с COM-объектом в пользу работы через "объектную модель документа" (DOM).
Порой необходимо временно отключить расширение 1С, не удаляя его, чтобы не потерять данные. Но в этом случае при каждом запуске всем будет лезть уведомление о неактивном расширении, хотя очевидно, это техническая информация, которой не стоит лишний раз пугать пользователей.
На заключительных этапах, когда идет отладка или доработка интерфейса, необходимо много раз переоткрыть внешний объект. Вот один из способов автоматизации этого.
Добавляйте в избранное, пригодится. Массив шаблонов мусора можно дополнить разными сокращениями типа ГАУ, МБДОУ, МОБУ, ГБУЗ и несть им числа.
Держите. Это словарь сокращений из нашей конфигурации.
Правда, щас набегут фанаты длинных имён переменных и начнут "поливать" все ваши "dw", "dj" и прочие "инд1", ай-ай. Да ещё вспомнят про убирание кода под спойлер)
Реально вижу применение, например, для собственного полнотекстового поиска, который априори будет гораздо управляемее платформенного.
Где ж ты раньше был, когда мне надо было найти дубли адресов в базе?
Тогда наваял свой какой-то велосипедно-костыльный алгоритм, который возвращал процент схожести строк.
А здесь с выкладками, все четко! Однозначно плюс. Спасибо.
В примере 2 не понятно почему L=3, хотя должно быть 4...
В примере 3 на правой картинке одна 1 стоит не правильно и в результате m посчитано не правильно...
В примере 3 слева условие dj >= bt не применялось, хотя в функции оно есть...
Использование в функции Соответствия наверное перебор, без него можно было бы обойтись...
А так, да, материал полезный...
(12) Спасибо за внимательное прочтение и замечания. Постараюсь ответить по-порядку.
1. В примере 2 длина префикса L действительно равна 4-м, а не 3-м, как было на картинке. Поправил вместе с результатом.
2. В примере 3 на правой картинке обозначение одной из транспозиций символа "А" действительно находилась не на своем месте (в столбце символа "В". Поправил. Однако эта перестановка не меняет величину m и соответственно не влияет на результат. Отсюда следует, что утверждение ".. посчитано не правильно..." основано на предположении, а не практической проверке.
3. "В примере 3 слева условие dj >= bt не применялось, хотя в функции оно есть..." - верно. Добавил соответствующее примечание перед примером.
Слава Богу данные ошибки не системные, а результат нудной оформительской работы. Надеюсь на понимание.
4. "Использование в функции Соответствия наверное перебор," - это уже из области холивара:) - "без него можно было бы обойтись..." - с удовольствием добавлю в публикацию второй, более изящный вариант реализации алгоритма, если порадуете.
А вот ошибку в функции основного алгоритма не заметили:) В первом условии, где "в лоб" сравниваются оба слова, функция всегда возвращала - 1, вне зависимости от значения параметра "Процент". Поправил.
Было:
Если s1 = s2 Тогда
Возврат 1;
КонецЕсли;
Стало:
Если s1 = s2 Тогда
Возврат ?(Процент,100,1);
КонецЕсли;
Однако эта перестановка не меняет величину m и соответственно не влияет на результат.
ну не знаю... объясните тогда почему вы в столбце 9 засчитали в m две транспозиции из трех? может я и не прав...
это уже из области холивара:)
почему холивара? скорее из области производительности...
свою версию реализации без Соответствия я конечно могу привести, но сначала ответьте на вопрос про столбец 9, т.к. возможно, что мы с вами по разному интерпретируем правила подсчета транспозиций... весьма не четко описанные в Википедии и других источниках... вы провели хорошую работу по исследованию вопроса...
судя по структуре формулы Джаро, она ни когда не должна превышать 1, т.к. все три слагаемых не превышают единицу... если превышают, значит трактовка подсчета m и tr не верная... так мне кажется...
однако, алгоритм довольно странный... например, если взять строки АААААААА и ААА, то будет 3 совпадения и море транспозиций... мне кажется, что на каждый столбец надо учитывать либо совпадение, либо транспозицию, с приоритетом совпадения...
я ни чего не утверждаю, я сам хочу разобраться...
А вот ошибку в функции основного алгоритма не заметили
я ваш код не изучал и не использовал (только бегло просмотрел, когда обнаружил, что не использовано условие)... я попытался написать свой и в процессе тестирования на ваших примерах обнаружил те ошибки о которых написал...
мне кажется, что на каждый столбец надо учитывать либо совпадение, либо транспозицию, с приоритетом совпадения...
- Вы абсолютно правы. Я того-же мнения. И не смотря на действительное не четкое описание правил транспозиции, этот вывод напрашивается сам собой. Транспозиция, она же перестановка, может быть только одна для одного символа. Либо совпадение по позиции, либо перестановка. По злосчастному столбцу 9 признаю ошибку, которую упорно не хотел замечать (поправил, кстати). Та единица на картинке должна была быть красная (неверно посчитанная транспозиция) и само-собою не должна влиять на величину m и результат. Приведенная функция её естественно и не учитывает. Как это не смешно, но это тоже ошибка исключительно оформительская. Естественно результат в примере 3 изменился в меньшую сторону, но утверждение, что результат конечно же зависит от порядка сравнения строк, длинной с короткой и наоборот, остается верным. Большое спасибо за указанную неточность.
например, если взять строки АААААААА и ААА, то будет 3 совпадения и море транспозиций
- функция выдаст 3 совпадения и 0 транспозиций. Результат будет одинаков для любого варианта сравнения. Хотя сравнивать разной длины последовательности из одинаковых символов на мой взгляд не совсем корректно. Всё-таки алгоритм направлен именно на сравнение слов. Ведь (повторюсь) расстояние Джаро между двумя словами — это минимальное число одно— символьных преобразований, которое необходимо для того, чтобы изменить одно слово в другое.
почему холивара? скорее из области производительности...
- Возможно и так. По поводу производительности универсальных коллекций 1С есть замечательный материал с подробными выкладками -
Замеров производительности функции не осуществлялось, ибо написана была под конкретный случай для обработки ограниченного объёма информации. Поэтому быстродействие не являлось ключевым фактором.
По поводу производительности универсальных коллекций
Соответствие быстрее других коллекций при поиске элемента, но без него еще быстрее :)
я написал бы, например, так:
L=0;
m=0;
tr=0;
// поиск соответствия
Для Инд1 = 1 По a Цикл
БылоСовпадение=0;
БылиТранспозиции=0;
Для Инд2 = 1 По b Цикл
// Ограничиваем цикл допустимым расстоянием - d
Если Инд2 < Инд1 - d Тогда
Продолжить;
КонецЕсли;
Если Инд2 > Инд1 + d Тогда
Прервать;
КонецЕсли;
Если Сред(s1,Инд1,1) = Сред(s2,Инд2,1) Тогда
Если Инд1=Инд2 Тогда
// совпадение
БылоСовпадение=1;
БылиТранспозиции=0;
Если L < 4 И L = Инд1-1 Тогда
L=L+1;
КонецЕсли;
ИначеЕсли БылоСовпадение=0 Тогда
// транспозиция
БылиТранспозиции=1;
КонецЕсли;
КонецЕсли; // Символ1 = Символ2
КонецЦикла; // Для Инд2 По b
m=m+БылоСовпадение+БылиТранспозиции;
tr=tr+БылиТранспозиции;
КонецЦикла; // Для Инд1 По a
(15) не везёт... :)
теперь у меня не сходится с вашими цифрами Пример 2...
m=9
tr=1
t=0, а у вас 1
результат у меня 0.944
ошибка наверное тоже оформительская... но не сходится же :)
на сайте на котором вы проверяли в число транспозиции включаются только те позиции которые "нарушают" последовательность букв (в википедии вроде такие же расчеты, но там тоже не понятно, т.к. в одном случае одно а в другом другое), а в данном методе в транспозиции включаются все отклонения от индекса в сравниваемой строке.
Что бы было понятно, порядок букв которые считаются "совпавшими" в словах АбрАКАДАбРА и АвАДАКедАвРА я выделил прописными буквами.
Дак вот, в описанном методе под число транспозиции попадают 7 букв, т.к. индексы у найденных позиций во второй строке не соответствуют первой строке (по факту совпала только первая буква А).
А если считать только те буквы которые нарушили последовательность, это только буквы К и Д. Если это учесть в расчете, то значения на сайте и в данном коде совпадут.
P.S.: Какой из расчетов правильный - сложно сказать, тк как уже ранее заметили - непонятно что считать транспозицией в данном случае...
(20)причем, если махнуть местами буквы в слове абракДАабра, для того что бы проверить эту теорию (только буква К не на том месте в последовательности совпадений), на том же сайте итоговое значение остается неизменным,так что не факт что там правильно, хотя скорее всего это связано с округлением значения t при делении t на 2. что кстати говоря тоже не оговорено, т.к. число t может быть не целым в уравнении.
Ну неплохо было бы в самом начале написать хотя бы цитату из Википедии:
Чем меньше расстояние Джаро — Винклера d_{w} для двух строк, тем больше сходства имеют эти строки друг с другом. Результат нормируется, так что 0 означает отсутствие сходства, а 1 — точное совпадение.
А то непонятно, 0.75 это много или мало и 1.2 чем это плохо))
В остальном огонь, но практическое применение я думаю будет сводиться к подбору именно целевого минимального значения схожести....
