Сходство Джаро - Винклера
В области информатики и статистики сходство Джаро — Винклера представляет собой меру схожести строк для измерения расстояния между двумя последовательностями символов. Это вариант, который в 1999 году предложил Уильям Э. Винклер (William E. Winkler) на основе расстояния Джаро (1989, Мэтью А. Джаро, Matthew A. Jaro). Неформально, расстояние Джаро между двумя словами — это минимальное число одно— символьных преобразований, которое необходимо для того, чтобы изменить одно слово в другое.
Расстояние Джаро
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 | d | m | tr | t | L | dj | dw | ||
А | 1 | 1 | ← | 11 | 11 | 4 | 20 | 9 | 4 | 4 | 1,479 | 1,287 | |||||||||
Б | 1 | ||||||||||||||||||||
Р | 1 | a | b | d | m | tr | t | L | dj | dw | |||||||||||
А | 1 | 1 | 1 | 1 | ← | 11 | 11 | 4 | 11 | 0 | 0 | 4 | 1,000 | 1,000 | |||||||
К | 1 | ||||||||||||||||||||
А | 1 | 1 | 1 | ||||||||||||||||||
Д | 1 | ||||||||||||||||||||
А | 1 | 1 | 1 | ||||||||||||||||||
Б | 1 | ||||||||||||||||||||
Р | 1 | ||||||||||||||||||||
А | 1 | 1 |
Из примера видно, что причиной столь высокого результата стали ложные транспозиции, непомерно "раздув" величины m и tr.
Красным цветом в таблицах выделены ложные транспозиции и ложные результаты, которые выдает код в его теперешнем виде.
Зелёным, соответственно - правильные результаты.
К слову заметить, что данная особенность явно не оговорена в открытых источниках, которые попались автору.
Для большей наглядности приведу ещё два примера для упомянутых выше слов. Заодно сопоставим результаты сравнения короткой строки с длинной, и наоборот, длинной с короткой.
Пример 2. РАЗРАБОТКА и РАЗРАБОТЧИК
Р | А | З | Р | А | Б | О | Т | К | А | a | b | d | m | tr | t | L | dj | dw | Р | А | З | Р | А | Б | О | Т | Ч | И | К | |||||
Р | 1 | 1 | ← | 10 | 11 | 4 | 13 | 5 | 3 | 4 | 1,097 | 1,058 | Р | 1 | 1 | |||||||||||||||||||
А | 1 | 1 | А | 1 | 1 | |||||||||||||||||||||||||||||
З | 1 | a | b | d | m | tr | t | L | dj | dw | З | 1 | ||||||||||||||||||||||
Р | 1 | 1 | ← | 10 | 11 | 4 | 9 | 1 | 1 | 4 | 0,888 | 0,933 | Р | 1 | 1 | |||||||||||||||||||
А | 1 | 1 | А | 1 | 1 | |||||||||||||||||||||||||||||
Б | 1 | a | b | d | m | tr | t | L | dj | dw | Б | 1 | ||||||||||||||||||||||
О | 1 | 11 | 10 | 4 | 13 | 5 | 3 | 4 | 1,097 | 1,058 | → | О | 1 | |||||||||||||||||||||
Т | 1 | Т | 1 | |||||||||||||||||||||||||||||||
Ч | a | b | d | m | tr | t | L | dj | dw | К | 1 | |||||||||||||||||||||||
И | 11 | 10 | 4 | 9 | 1 | 1 | 4 | 0,888 | 0,933 | → | А | |||||||||||||||||||||||
К | 1 |
Примечание: Как справедливо заметил бро Perfolenta, в Примере 3 не используется "порог усиления" префиксного бонуса в реализации Винклера, который применяется в функции. Другими словами префиксный бонус применен без учета "порога усиления".
Пример 3. АБРАКАДАБРА и АВАДАКЕДАВРА
А | Б | Р | А | К | А | Д | А | Б | Р | А | a | b | d | m | tr | t | L | dj | dw | А | В | А | Д | А | К | Е | Д | А | В | Р | А | ||||
А | 1 | 1 | ← | 11 | 12 | 4 | 17 | 16 | 8 | 1 | 1,164 | 1,147 | А | 1 | 1 | 1 | |||||||||||||||||||
В | Б | ||||||||||||||||||||||||||||||||||
А | 1 | 1 | 1 | a | b | d | m | tr | t | L | dj | dw | Р | ||||||||||||||||||||||
Д | 1 | ← | 11 | 12 | 4 | 8 | 7 | 3 | 1 | 0,673 | 0,706 | А | 1 | 1 | 1 | ||||||||||||||||||||
А | 1 | 1 | 1 | 1 | К | 1 | |||||||||||||||||||||||||||||
К | 1 | А | 1 | 1 | 1 | ||||||||||||||||||||||||||||||
Е | a | b | d | m | tr | t | L | dj | dw | Д | 1 | 1 | |||||||||||||||||||||||
Д | 1 | 12 | 11 | 4 | 18 | 17 | 8 | 1 | 1,231 | 1,208 | → | А | 1 | 1 | 1 | ||||||||||||||||||||
А | 1 | 1 | Б | ||||||||||||||||||||||||||||||||
В | a | b | d | m | tr | t | L | dj | dw | Р | 1 | ||||||||||||||||||||||||
Р | 1 | 12 | 11 | 4 | 9 | 8 | 4 | 1 | 0,708 | 0,737 | → | А | 1 | 1 | |||||||||||||||||||||
А | 1 | 1 |
Обратите внимание!, что в некоторых случаях перестановка местами длинной и короткой строк может дать разный результат (может дело в магии слов о_О?!:), скорее всего всё-таки математика:)
О разных результатах, связанных с перестановкой слов, так-же не встретилось упоминаний. Возьмем на заметку эту особенность и реализуем её потом в функции.
Но сначала решим основную проблему. Каким образом можно избавиться от "фантомных" транспозиций?
- Необходимо "запоминать", на какой позиции в строке s2 был найден символ из строки s1.
- Если при совпадении символов окажется, что такой же символ на этой позиции уже был найден ранее - продолжить поиск до конца разрешенного расстояния - d в строке s2
- Если при совпадении символов окажется, что такой символ на этой позиции не был найден ранее - запомнить сам найденный символ, его позицию в строке s2 и перейти к следующему символу в строке s1
Нам потребуется таблица с двумя полями, одно из которых - индексируемое. В нем мы будем хранить позицию найденного символа и осуществлять по нему поиск. Для этой цели хорошо подойдёт объект Тип("Соответствие"); Назовем его условно bf - буфер. Объявим переменную позже, в блоке объявления переменных, а сейчас опишем три перечисленных выше пункта, модифицировав код в условии Символ1 = Символ2
Если Символ1 = Символ2 Тогда
Если bf.Получить(Инд2) = Символ1 Тогда
// на этой позиции текущий сивол строки s1 был найден ранее
// продолжаем поиск в строке s2
Продолжить; // Для Инд2 По b
Иначе
// фиксируем позицию найденного символа в строке s2
bf.Вставить(Инд2,Символ1);
//m = m + 1;
// транспозиция -----------
// считаем префикс (до 4-х)
// ------------------------
// переходим к следующему символу в s1
Прервать; // Для Инд2 По b
КонецЕсли; // bf.Получить(Инд2) = Символ1
КонецЕсли; //
В таком виде код вполне работоспособен и отдаёт ожидаемые результаты. Перед тем как собрать полный листинг функции, ещё пару слов. Вернее - пару параметров. Чтобы функция была чуть более универсальной. Оба будут необязательными.
Процент, Тип - Булево
Необязательный, по-умолчанию - Ложь
Истина - результат в процентах
Ложь - результат в виде десятичной дроби
ПерваяКороткая, Тип - Неопределено или Булево
Необязательный, по-умолчанию - Неопределено
Неопределено - первая строка сравнивается со второй
Истина - короткая строка сравнивается с длинной
Ложь - длинная строка сравнивается с короткой
Иногда удобнее (для визуализации) получить результат не в виде десятичной дроби, а в виде процента-отношения одной строки к другой. Понятно, что можно просто умножить результат на 100, но, всё-же:)
Второй параметр отвечает за порядок сравнения строк. Мы же помним, что от этого тоже зависит результат.
Поэтому предоставим возможность выбора варианта для сравнения.
Функция в достаточной степени комментирована, и логика использования параметров будут понятна без дополнительного описания.
Полный листинг функции
////////////////////////////////////////////////////////////////////////////////
//
// Функция ПолучитьСходствоДжароВинклера
//
// Описание:
// Функция вычисляет Сходство Джаро-Винклера для двух строк
//
//
// Параметры:
// Строка1, Строка, Первая строка для сравнения
// Строка2, Строка, Вторая строка для сравнения
// Процент, Булево, Необязательный, по-умолчанию - Ложь
// Истина - результат в процентах
// Ложь - результат в виде десятичной дроби
// ПерваяКороткая, Неопределено или Булево,
// Необязательный, по умолчанию - Неопределено
// Неопределено - первая строка сравнивается со второй
// Истина - короткая строка сравнивается с длинной
// Ложь - длинная строка сравнивается с короткой
//
// Возвращаемое значение: Число, Коэффициент сходства Джаро-Винклера для двух строк
//
// Примечание:
// Никакие входящие параметры не проверяются на валидность
// и соответствие Типу.
// Источники:
// https://elbuz.com/algorithms-approximate-matching-words-price-lists-part2
// https://ru.wikipedia.org/wiki/Сходство Джаро — Винклера
// https://nauchforum.ru/studconf/tech/17/53155
//
// Programmer: Andrey Arsentev, november 2019
Функция ПолучитьСходствоДжароВинклера(Строка1,Строка2,Процент = Ложь,ПерваяКороткая = Неопределено) Экспорт
s1 = ВРег(СокрЛП(Строка1));
s2 = ВРег(СокрЛП(Строка2));
// а вдруг?
Если s1 = s2 Тогда
Возврат ?(Процент,100,1);
КонецЕсли;
// При необходимости меняем порядок строк
Если НЕ ПерваяКороткая = Неопределено
И СтрДлина(s1) <> СтрДлина(s2) Тогда
Буфер = Неопределено;
Если ПерваяКороткая Тогда
Если СтрДлина(s1) > СтрДлина(s2) Тогда
Буфер = s1;
s1 = s2;
s2 = Буфер;
КонецЕсли;
Иначе
Если СтрДлина(s2) > СтрДлина(s1) Тогда
Буфер = s1;
s1 = s2;
s2 = Буфер;
КонецЕсли;
КонецЕсли;
Буфер = Неопределено;
КонецЕсли;
// инициализация переменных
a = СтрДлина(s1);
b = СтрДлина(s2);
d = Цел(Макс(a,b)/2)-1; // Допустимое расстояние
m = 0; //- количество подходящих символов
tr = 0; //- количество транспозиций
t = 0; //- половина числа транспозиций
L = 0; //- длина общего префикса от начала строки до максимума 4-х символов
p = 0.1; // — постоянный коэффициент масштабирования
bt = 0.7; // - "порог усиления" применения префиксного бонуса в реализации Винклера
dj = 0; //- расстояние Джаро
dw = 0; //- результат Джаро — Винклера
bf = Новый Соответствие; // буфер для хранения позиций найденных символов
//--------------------------------------
// поиск соответствия
Для Инд1 = 1 По a Цикл
Символ1 = Сред(s1,Инд1,1);
Для Инд2 = 1 По b Цикл
// Ограничиваем цикл допустимым расстоянием - d
Если Инд2 < Инд1 - d Тогда
Продолжить;
КонецЕсли;
Если Инд2 > Инд1 + d Тогда
Прервать;
КонецЕсли;
// Сравнение и поиск
Символ2 = Сред(s2,Инд2,1);
Если Символ1 = Символ2 Тогда
Если bf.Получить(Инд2) = Символ1 Тогда
// на этой позиции текущий сивол строки s1 был найден ранее
// продолжаем поиск в строке s2
Продолжить; // Для Инд2 По b
Иначе
// фиксируем позицию найденного символа в строке s2
bf.Вставить(Инд2,Символ1);
m = m + 1; // прибавляем совпавший символ
// транспозиция -------
Если Инд1 <> Инд2 Тогда
tr = tr + 1; //не совпадают позиции символов - транспозиция
КонецЕсли;
// считаем префикс (до 4-х)
Если Инд1 = Инд2 Тогда
Если Инд1 = 1 Тогда
L = 1; // начало цепочки L
Иначе
Если L <= 3 И Инд1 = L + 1 Тогда
L = L + 1; //
КонецЕсли;
КонецЕсли;
КонецЕсли; //Инд1 = Инд2
// переходим к следующему символу в s1
Прервать; // Для Инд2 По b
КонецЕсли; // bf.Получить(Инд2) = Символ1
КонецЕсли; // Символ1 = Символ2
КонецЦикла; // Для Инд2 По b
КонецЦикла; // Для Инд1 По a
// расчет коэффициента ----------------------------
Если 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 = dw * 100;
КонецЕсли;
// результат
Возврат dw;
КонецФункции //ПолучитьСходствоДжароВинклера
тем, кто дочитал до конца..
БОНУС
Ниже представлены ещё три функции. Одна из них является оберткой к рассмотренному алгоритму и предназначена для сравнения длинных строк. Две другие - вспомогательные.
Сразу оговорюсь, функции написаны под личные нужды и не обладают достаточной гибкостью. Предназначались в основном для сравнения адресов при упорядочивании базы. Показала хорошие результаты.
Помимо аналогичных параметров, передающихся в функцию и присутствующих в основном алгоритме, есть ещё два. И передаются параметры в функцию не по отдельности, а в виде структуры. Вот они:
Очищать, Тип - Булево,
Необязательный, по-умолчанию - Истина
Истина - Очищать строки перед сравнением от Спец.Символов и мусорных слов/аббривеатур
Ложь - Только сравнить строки, без предварительной обработки
РезультатПоВторой, Тип - Булево,
Необязательный, по умолчанию - Истина
Истина - Реузультат = средний коэффициент Строки1 по основанию количества слов в Строке2
Ложь - Реузультат = средний коэффициент Строки1 по основанию количества слов в Строке1
Параметр - Очищать, задействует перед сравнением две вспомогательных функции, для очистки строки от различных спец. символов, мусорных слов и аббривеатур.
При сравнении адресов это оказалось полезным, т.к. например, игнорировались различающиеся обозначения одной и той же административной единицы. "г., гор., город" и.т.д.
Параметр возможно будет полезен при поиске совпадений в списке Номенклатуры. Можно убрать всевозможные тире, скобки, шт., литры и пр.
Параметр РезультатПоВторой,
Тут требуется пояснение. Дело в том, что "вес" строки состоит из среднего значения максимальных коэффициентов каждого, отдельно взятого слова.
Но вот вопрос, на какое количество слов делить общий результат, чтобы получить среднее значение?
Вариантов всего два - разделить на количество слов той-же строки, которую проверяли, или разделить на количество слов строки по которой искали совпадения. Параметр РезультатПоВторой отвечает именно за это. Зачем это нужно? Проще пояснить на примере:
s1 = "Россия, Нижегородская обл., г.Нижний Новгород";
s2 = "Россия, Нижегородская обл., г.Нижний Новгород, ул.Переходникова";
Если мы будем сравнивать "короткую" строку с "длинной", Каждое слово в s1 будет иметь коэффициент - 1,Поскольку каждое слово встречается и в строке s2. И если мы поделим общий результат на количество слов в самой строке - 4/4=1 (пускай не смущают 4 слова, "обл" мы отбросили при очистке), мы получим ложный результат. Якобы s1 на 100% совпадает с s2. Хотя очевидно, что это не так.
А если результат проверки - 4, мы поделим на 5 (количество слов в s2) то получим 80% совпадения, что близко к истине.
Практика показала, что при сравнении длинных строк наилучший результат показывает вариант сравнения короткой строки с длинной, и получение результата по основанию длинной.
Листинг функций
////////////////////////////////////////////////////////////////////////////////
//
// Функция СравнитьСтрокиМетодомДжароВинклера
//
// Описание: Нечеткое сравнение Длинных строк
//
// Параметры :
//
// begin_copy_to_clipboard
//
// Параметр = Новый Структура;
// Параметр.Вставить("Строка1",Строка1); // Строка для сравнения 1
// Параметр.Вставить("Строка2",Строка2); // Строка для сравнения 2
//
//// НЕОБЯЗАТЕЛЬНЫЙ
// Параметр.Вставить("Процент",Ложь); // Формат результата
//// По-умолчанию - Ложь
//// Ложь - Коэффицент совпадения
//// Истина - Процент совпадения
//
//// НЕОБЯЗАТЕЛЬНЫЙ
// Параметр.Вставить("ПерваяКороткая",Неопределено); // Неопределено или Булево,
//// По умолчанию - Неопределено
//// Неопределено - Первая Строка сравнивается со Второй
//// Истина - Короткая строка сравнивается с Длинной
//// Ложь - Длинная строка сравнивается с Короткой
//
//// НЕОБЯЗАТЕЛЬНЫЙ
// Параметр.Вставить("РезультатПоВторой",Истина); // "Булево",
//// По умолчанию - "Истина"
//// Истина - Реузультат - Средний коэффициент Строки1 по
//// основанию количества слов в Строке2
//// Ложь - Реузультат - Средний коэффициент Строки1 по
//// основанию количества слов в Строке1
//
////НЕОБЯЗАТЕЛЬНЫЙ
// Параметр.Вставить("Очищать",Истина);
//// Очищать строки перед сравнением от Спец.Символов
//// и мусорных слов/аббривеатур
//// По-умолчаию - Истина
//
//// Примечание:
//// Никакие параметры структуры не проверяются на валидность
//// и соответствие Типу.
//
// Результат = ОбщегоНазначенияРасширение.СравнитьСтрокиМетодомДжароВинклера(Параметр);
//
// end_copy_to_clipboard
//
// Возвращаемое значение:
// Число - Коэффициент однообразия Джаро-Винклера
// Неопределено - В случае невозможности сравнения
//
// Programmer: Andrey Arsentev, november 2019
Функция СравнитьСтрокиМетодомДжароВинклера(Параметр) Экспорт
Если НЕ ТипЗнч(Параметр) = Тип("Структура") Тогда
Возврат Неопределено;
КонецЕсли;
// 0.Инициализация переменных ----------------------
Процент = Ложь;
ПерваяКороткая = Неопределено;
РезультатПоВторой = Истина;
Очищать = Истина;
Результат = 0;
Если Параметр.Свойство("Процент") Тогда
Процент = Параметр.Процент;
КонецЕсли;
Если Параметр.Свойство("ПерваяКороткая") Тогда
ПерваяКороткая = Параметр.ПерваяКороткая;
КонецЕсли;
Если Параметр.Свойство("РезультатПоВторой") Тогда
РезультатПоВторой = Параметр.РезультатПоВторой;
КонецЕсли;
Если Параметр.Свойство("Очищать") Тогда
Очищать = Параметр.Очищать;
КонецЕсли;
//----------------------------------------------------
// 1. Очистка строки перед сравнением от Спец.Символов
// и мусорных слов/аббривеатур
Если Очищать Тогда
МассивСтрок = Новый Массив;
МассивСтрок.Добавить(Параметр.Строка1);
МассивСтрок.Добавить(Параметр.Строка2);
Результат = ОчиститьСтрокиОтМусора(МассивСтрок);
Если ТипЗнч(Результат) = Тип("Массив") Тогда
Параметр.Вставить("Строка1",Результат.Получить(0));
Параметр.Вставить("Строка2",Результат.Получить(1));
КонецЕсли;
КонецЕсли;
// 2. "упакуем" строки в массивы для сравнения по словам
МассивСлов1 = СтрРазделить(Параметр.Строка1," ",Ложь);
МассивСлов2 = СтрРазделить(Параметр.Строка2," ",Ложь);
// 3. При необходимости смена очередности Строк
Если НЕ ПерваяКороткая = Неопределено
И МассивСлов1.Количество() <> МассивСлов2.Количество() Тогда
Буфер = Неопределено;
Если ПерваяКороткая Тогда
Если МассивСлов1.Количество() > МассивСлов2.Количество() Тогда
Буфер = МассивСлов1;
МассивСлов1 = МассивСлов2;
МассивСлов2 = Буфер;
КонецЕсли;
Иначе
Если МассивСлов2.Количество() > МассивСлов1.Количество() Тогда
Буфер = МассивСлов1;
МассивСлов1 = МассивСлов2;
МассивСлов2 = Буфер;
КонецЕсли;
КонецЕсли;
Буфер = Неопределено;
КонецЕсли;
// 4. Поиск и сравнение -----------------------------------
Коэффициент = 0;
Для Инд1 = 0 По МассивСлов1.Количество()-1 Цикл
Слово1 = МассивСлов1.Получить(Инд1);
КоэффициентСлова = 0;
Для Инд2 = 0 По МассивСлов2.Количество()-1 Цикл
Слово2 = МассивСлов2.Получить(Инд2);
КоэффициентВременный = ПолучитьСходствоДжароВинклера(Слово1,Слово2,Ложь,ПерваяКороткая);
// получаем максимальный коэффициент для Слово1
Если КоэффициентСлова < КоэффициентВременный Тогда
КоэффициентСлова = КоэффициентВременный;
Если КоэффициентСлова = 1 Тогда
Прервать;
КонецЕсли;
КонецЕсли;
КонецЦикла;
Коэффициент = Коэффициент + КоэффициентСлова;
КонецЦикла;
// 5. Обработка результата ------------------
Результат = Коэффициент / МассивСлов1.Количество();
Если РезультатПоВторой Тогда
Результат = Коэффициент / МассивСлов2.Количество();
КонецЕсли;
Если Процент Тогда
Результат = Результат * 100;
КонецЕсли;
// 6. Возврат результата работы функции
Возврат Результат;
КонецФункции //СравнитьСтрокиМетодомДжароВинклера
////////////////////////////////////////////////////////////////////////////////
//
// Функция ОчиститьСтрокиОтМусора
//
// Описание: Для улучшения результатов сравнения
// очищает строку от
// мусорных символов и слов по шаблону.
//
// Параметры: МассивСтрок, Массив , содержит строки для очистки
//
// Возвращаемое значение: Массив , Содержит очищенные строки в том же порядке
//
// Programmer: Andrey Arsentev, november 2019
Функция ОчиститьСтрокиОтМусора(МассивСтрок) Экспорт
МассивШаблонов = ПолучитьМассивШаблоновМусора();
Для Инд1 = 0 По МассивСтрок.Количество() - 1 Цикл
ТекущаяСтрока = ВРег(МассивСтрок.Получить(Инд1));
Для Инд2 = 0 По МассивШаблонов.Количество() - 1 Цикл
Шаблон = МассивШаблонов.Получить(Инд2);
Если ТипЗнч(Шаблон) = Тип("Строка") Тогда
Буфер = "";
Для Инд3 = 1 По СтрДлина(ТекущаяСтрока) Цикл
Символ = Сред(ТекущаяСтрока,Инд3,1);
Если СтрНайти(Шаблон,Символ) > 0 Тогда
Буфер = Буфер + " ";
Иначе
Буфер = Буфер + Символ;
КонецЕсли;
КонецЦикла;
ТекущаяСтрока = Буфер;
ИначеЕсли ТипЗнч(Шаблон) = Тип("Массив") Тогда
Для Инд3 = 0 По Шаблон.Количество() - 1 Цикл
ТекущаяСтрока = СтрЗаменить(ТекущаяСтрока,Шаблон.Получить(Инд3)," ");
КонецЦикла;
КонецЕсли;
КонецЦикла;
МассивСтрок.Установить(Инд1,ТекущаяСтрока);
КонецЦикла;
Возврат МассивСтрок;
КонецФункции //ОчиститьСтрокиОтМусора
////////////////////////////////////////////////////////////////////////////////
//
// Функция ПолучитьМассивШаблоновМусора
//
// Описание: Назначение очевидно
//
//
// Параметры (название, тип, дифференцированное значение)
//
// Возвращаемое значение:
//
//Programmer: Andrey Arsentev, november 2019
Функция ПолучитьМассивШаблоновМусора()
МассивШаблонов = Новый Массив;
//
СтрокаШаблон = "!.,:;%*()_-+=\/";
МассивШаблонов.Добавить(СтрокаШаблон);
//
МассивЗамены = Новый Массив;
МассивЗамены.Добавить(" ОБЛАСТЬ ");
МассивЗамены.Добавить(" ОБЛ ");
МассивЗамены.Добавить(" КРАЙ ");
МассивЗамены.Добавить(" ГОРОД ");
МассивЗамены.Добавить(" ГОР ");
МассивЗамены.Добавить(" Г ");
МассивЗамены.Добавить(" ПОСЕЛОК ");
МассивЗамены.Добавить(" ПОСЁЛОК ");
МассивЗамены.Добавить(" ПОС ");
МассивЗамены.Добавить(" СЕЛО ");
МассивЗамены.Добавить(" СЕЛ ");
МассивЗамены.Добавить(" С ");
МассивЗамены.Добавить(" РАЙОН ");
МассивЗамены.Добавить(" Р ОН ");
МассивЗамены.Добавить(" Р Н ");
МассивЗамены.Добавить(" ПЛОЩАДЬ ");
МассивЗамены.Добавить(" ПЛ ");
МассивЗамены.Добавить(" УЛИЦА ");
МассивЗамены.Добавить(" УЛ ");
МассивЗамены.Добавить(" ДОМ ");
МассивЗамены.Добавить(" Д ");
МассивЗамены.Добавить(" СТРОЕНИЕ ");
МассивЗамены.Добавить(" СТР ");
МассивШаблонов.Добавить(МассивЗамены);
Возврат МассивШаблонов;
КонецФункции //ПолучитьМассивШаблоновМусора
end