Сходство Джаро - Винклера. Нечеткое сравнение строк

05.03.20

Разработка - Универсальные функции

В области информатики и статистики сходство Джаро - Винклера представляет собой меру схожести строк для измерения расстояния между двумя последовательностями символов. В публикации рассмотрены некоторые особенности алгоритма, и представлен вариант его реализации на языке 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, нужно убедиться, что выполняется условие, связанное с ограничением расстояния поиска -

Ограничим вложенный цикл по количеству лишних интераций.

  1. Если при поиске "назад" расстояние межу символами ещё не достигло d - не выполняя сравнения переходим к следующему символу строки s2 
  2. Если при поиске "вперед" расстояние между символами уже превысило 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-ой и т.д. позициях, но не более четырех подряд.
Эту задачу мы решим так:

  1. присвоим L=1; при совпадении первых символов;
  2. далее отслеживаем выполнение следующих условий:
  • 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                                                

 

Обратите внимание!, что в некоторых случаях перестановка местами длинной и короткой строк может дать разный результат (может дело в магии слов о_О?!:), скорее всего всё-таки математика:)
О разных результатах, связанных с перестановкой слов, так-же не встретилось упоминаний. Возьмем на заметку эту особенность и реализуем её потом в функции.

Но сначала решим основную проблему. Каким образом можно избавиться от "фантомных" транспозиций?

  1. Необходимо "запоминать", на какой позиции в строке s2 был найден символ из строки s1.
  2. Если при совпадении символов окажется, что такой же символ на этой позиции уже был найден ранее - продолжить поиск до конца разрешенного расстояния - d в строке s2
  3. Если при совпадении символов окажется, что такой символ на этой позиции не был найден ранее - запомнить сам найденный символ, его позицию в строке 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

См. также

Вставляем картинку из буфера обмена (платформа 1С 8.3.24)

Универсальные функции Платформа 1С v8.3 Конфигурации 1cv8 Абонемент ($m)

Задача: вставить картинку из буфера обмена на форму средствами платформы 1С.

1 стартмани

18.03.2024    2664    0    John_d    8    

53

GUID в 1С 8.3 - как с ними быть

Универсальные функции Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Пришлось помучиться с GUID-ами немного, решил поделиться опытом, мало ли кому пригодится.

12.02.2024    4595    atdonya    22    

45

Переоткрытие внешних обработок

Универсальные функции Платформа 1С v8.3 Бесплатно (free)

На заключительных этапах, когда идет отладка или доработка интерфейса, необходимо много раз переоткрыть внешний объект. Вот один из способов автоматизации этого.

30.11.2023    3956    ke.92@mail.ru    16    

61

Валидация JSON через XDTO (включая массивы)

WEB-интеграция Универсальные функции Механизмы платформы 1С Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

При работе с интеграциями рано или поздно придется столкнуться с получением JSON файлов. И, конечно же, жизнь заставит проверять файлы перед тем, как записывать данные в БД.

28.08.2023    8802    YA_418728146    6    

141

Печать непроведенных документов для УТ, КА, ERP. Настройка печати по пользователям, документам и печатным формам

Пакетная печать Печатные формы Адаптация типовых решений Универсальные функции Платформа 1С v8.3 1С:ERP Управление предприятием 2 1С:Управление торговлей 11 1С:Комплексная автоматизация 2.х Россия Абонемент ($m)

Расширение для программ 1С:Управление торговлей, 1С:Комплексная автоматизация, 1С:ERP, которое позволяет распечатывать печатные формы для непроведенных документов. Можно настроить, каким пользователям, какие конкретные формы документов разрешено печатать без проведения документа.

2 стартмани

22.08.2023    2071    21    progmaster    7    

3

Расширение: Быстрые отборы через буфер [Alt+C] Копировать список, [Alt+V] Вставить список, [Ctrl+C] Копировать из файлов

Инструментарий разработчика Универсальные функции Платформа 1С v8.3 Конфигурации 1cv8 1С:Розница 2 1С:ERP Управление предприятием 2 1С:Бухгалтерия 3.0 1С:Управление торговлей 11 1С:Комплексная автоматизация 2.х 1С:Зарплата и Управление Персоналом 3.x Абонемент ($m)

Копирует в буфер значения из списков, из ячеек отчетов, таблиц, настроек списков, других отборов и вставляет в выбранную настройку отбора. Работает с Объект не найден. Работает как в одной так и между разными базами 1С. Использует комбинации [Alt+C] Копировать список, [Alt+V] Вставить список. Также для копирования данных используется стандартная [Ctrl+C] (например из открытого xls, mxl, doc и т.п. файла скопировать список наименований)

1 стартмани

13.10.2022    16140    133    sapervodichka    112    

129

Система контроля ведения учета [БСП]

Универсальные функции Механизмы типовых конфигураций БСП (Библиотека стандартных подсистем) Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

В данном материале рассмотрим типовой алгоритм подсистемы контроля учета БСП в конфигурациях на примерах.

18.07.2022    7242    quazare    8    

109
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Поручик 4670 25.12.19 23:37 Сейчас в теме
Добавляйте в избранное, пригодится. Массив шаблонов мусора можно дополнить разными сокращениями типа ГАУ, МБДОУ, МОБУ, ГБУЗ и несть им числа.
Держите. Это словарь сокращений из нашей конфигурации.

ГКС(К)ОУ
ГБС(К)ОУ
С(К)ОШИ
ГООУ СТ
ГС(К)ОУ
ДЮСШ-2
ДЦП-VI
ГКС(К)
(ДЮСШ)
В(С)ОШ
Ц.Р.Р.
(К)ОУ
С-КК
СОШ
Д/С
В/Ч
ООКПГВВ
МОБУДОД
ГБОУДОД
ММППЖКХ
СДЮСШОР
МАОУДОД
МОАУДОД
МБОУДОД
ГОУНПО
ГОУДПО
МОУДОД
ГБУДОД
ГКУСОН
ВИОГЕМ
НИПИЭП
ВНИИПО
МУССЗН
МОБУДО
ЖИЛКОМ
ГБУОШИ
ТГАРБО
ОГОТМК
МБУДОД
ОДОМСУ
МБОУДО
ДОДДШИ
ГБУСОН
МСУСО
ИМЦУО
МУАКП
ЦСДОУ
МУДОД
МИФНС
ГСУСО
ОРГМУ
ГБПОУ
ГБУУТ
ОСКАЛ
УТПСП
ВОТКЗ
ГАПОУ
УМИТЦ
ОГОДТ
РОДЕФ
ГБУСО
УФССП
УФСИН
ФГБОУ
ММООО
МОМВД
МБДОО
ГКООУ
СКОШИ
МАУДО
МБУДО
МЦДОД
СДЮТЭ
ГИБДД
СДЮСШ
ММБУК
МКУСО
МБДОУ
МДОБУ
ТИСИЗ
МДБОУ
НОЭМЗ
ЦСПСД
МБУСО
ЯМЦКС
ОВОВЗ
МАДОУ
МГКПЦ
АДЮСШ
ЦРТДЮ
ООКВД
ГАУСО
КЦСОН
ГБСОУ
ГКУСО
ЯМЦБС
МДОАУ
ИНПРО
ОМЕГА
ДЭРИИ
ООКПБ
ООСПК
ООКНД
ООКИБ
КАИГ
КЦСО
КУМИ
ГСТК
СРЦН
УГМС
ОГПУ
ГРИН
МБУЗ
ГОСТ
УФМС
УСЗН
ГКПЦ
УСДХ
МОШИ
КЭПО
УПСК
БАСТ
ЦДОД
ДООШ
КАРИ
ГООУ
НИПИ
ОФКС
ВАРС
ДСОШ
МОАУ
ФРИЗ
ИФНС
УДОД
ММУЗ
МРСК
СПИД
ДЗОЛ
БЦКС
ФСИН
ДИНА
ДЭБЦ
ОМСУ
ФГОУ
ФГКУ
МЦБС
ФСКН
МБУО
ОСЗН
ОРОФ
ВДПО
ДСКВ
ФГУП
МДОО
ОТГК
ГЭТИ
МКПУ
ЕДДС
ИФСО
ЦРДЮ
ЦБОУ
УПХГ
ЦДЮТ
ФССП
МБУК
КНХП
ГПДС
СПКФ
РУСТ
ППАБ
БЮРО
МПМК
СЖКУ
УКЖФ
ПАТП
РОНА
ИКДЦ
РМУП
ММПП
МЦКС
УЖКХ
ПРМЗ
ООКС
ЦИУС
МУСО
ГСОУ
ОКВД
ФГБУ
СРЦН
МАОУ
МАУК
ДГКБ
МАУЗ
ГКОУ
АОЗТ
ООШИ
СКШИ
ОКЭИ
ГАОУ
УРАЛ
ЭСКО
ЮУСК
ОООИ
ВИЛС
НОРД
ИЗОЛ
СПМК
ЦМТО
ОРЭП
УМВД
ПЖКХ
ОЗОН
НИКА
ЗЗМК
ЭКРА
МКДЦ
ГОБУ
ГАУК
ООКБ
ЗАТО
ФОМЦ
ОПТД
ОГТИ
ОЦПБ
ГАУЗ
МОБУ
ГБУК
ДИПИ
ОГИИ
ДЮСШ
МСАУ
АСДМ
РКДЦ
НЦПБ
ОЖБИ
ССЗН
МДОУ
ГПТД
КПТД
РЦРО
ГБУЗ
МБОУ
ГБОУ
ГСЮН
АСОШ
ОГДТ
ДМУП
ДООЛ
ГУОВ
СКОШ
УФСБ
УФСКН
ФГБНУ
ЦКИБО
МКЦС
ЦЭВД
КУМИ
ССОШ
МБОУДОДТ
ЦРТДИЮ
ЦСПСИД
УХТО
СДТТ
КУИ
БДК
КНТ
УОО
УИО
УИС
ЦСС
ООШ
ОШИ
ТСЖ
ТОО
МВФ
ЛУЧ
КИТ
КВК
ИМС
ИКЦ
ЖЭК
ПНИ
РТЦ
ГЕО
ССК
ВКБ
БМЗ
ГКС
ПРО
АСУ
АРС
ЦРБ
ГСП
ГЭС
СМЭ
ДНК
НТЦ
ППП
ДОД
ГТТ
РСП
РСЦ
СВК
СВС
СИМ
СМК
СТД
ОАС
ГКБ
ТКС
ТПГ
ТСО
СПК
АНО
СМУ
ФМС
ФКУ
ООО
ПХГ
ОАО
ПАО
АГП
ААА
ФКП
СОШ
ЦСМ
ФБУ
МУП
НАШ
ФМЛ
ПЛП
БСБ
ГКУ
ДПС
РСМ
ЖКС
ПСК
ЦСП
ЦЗН
ЦКД
ВИС
ПМК
ПКФ
АХУ
ОТС
ГБУ
ВПО
ОПИ
НПО
НПФ
РАД
ЭСМ
БНК
НПК
ОИК
ШТТ
ОНТ
УЮТ
ГАУ
СОЦ
ЖСК
ДДТ
МОА
МНУ
ПИЦ
ЖКХ
ТВЦ
КЦО
АХЦ
МКУ
ШИК
ПМП
ПИФ
ДПО
ПИК
ПИИ
ФПС
УКС
КСК
ДОО
МУК
МУЗ
СЮТ
ГУЗ
ГУК
ОКС
ГУП
ЖХХ
МОУ
ЮВР
ФСБ
ТТТ
ОСР
ЦВР
ДМШ
ДШИ
НОШ
ДШП
МБУ
БКМ
ЦБС
МКС
СДК
ЦСО
ДОЛ
ЦДТ
ФОК
ХИТ
МКП
НВФ
НПП
ТАФ
УВД
МВД
ДРЦ
ТМЦ
ЦКС
ЦГБ
КДЦ
РДК
МАУ
МЧС
ЗАО
НИИ
НОУ
АНК
СРЦ
ТГК
ПСБ
ОМК
РЖД
НТП
УФК
ОГУ
БУК
БТИ
ФГУ
СПО
МФЦ
СТС
ОТТ
МИК
ОФК
ОЦМ
ПТК
ЖКО
ГОУ
ЦПД
КШП
ФСК
ЦСА
ЕЭС
РОО
УЖФ
ПСП
РЖКХ
УГХ
ЖКК
ГС
ЮЦ
МУ
ИБ
МП
ПФ
ДЦ
НП
ГЦ
ГК
СО
ТВ
СУ
ГБ
ПУ
ОО
КС
ЧС
АТ
ПБ
ОП
БО
ЦК
ПО
ГУ
ВА
ПК
РФ
КУ
ЦБ
ГО
АУ
НО
ТК
ДС
ОУ
ДО
СП
ОШ
АО
МО
РБ
ФК
ОБ
ТМ
СК
РУ
ЭК
УК
УО
ПИ
РЦ
СЗ
СЛ
ВК
ПЦ
ИП
ПЛ
РО
СТ
Показать
DrAku1a; Pavl0; gaglo; forseil; Kolobash; JohnyDeath; +6 Ответить
2. script 128 26.12.19 01:31 Сейчас в теме
Классно. Однозначно в коллекцию. Спасибо.
3. Yashazz 4709 26.12.19 01:34 Сейчас в теме
Грамотная, хорошая, нужная публикация. Спасибо.

Правда, щас набегут фанаты длинных имён переменных и начнут "поливать" все ваши "dw", "dj" и прочие "инд1", ай-ай. Да ещё вспомнят про убирание кода под спойлер)

Реально вижу применение, например, для собственного полнотекстового поиска, который априори будет гораздо управляемее платформенного.
Dnki; starik-2005; +2 Ответить
4. AlexSinichenko 26.12.19 06:38 Сейчас в теме
Браво коллега. Очень хорошая и достаточно редкая публикация. Побольше таких статей!
5. lmnlmn 69 26.12.19 08:33 Сейчас в теме
Отличная работа! Хотя я могу быть предвзятым так как алгоритмы и разная "комбинаторика" моя слабость.
Поручик; +1 Ответить
6. kuzyara 1900 26.12.19 08:51 Сейчас в теме
А запросом это можно сделать?
Прикрепленные файлы:
ZOMI; arakelyan; AzagTot; user774630; wowik; shard; newdigger; CyberCerber; +8 Ответить
10. Prometeus2011 210 27.12.19 11:40 Сейчас в теме
(6)Ахахахаха! Тоже его вспомнил.
7. volsh77 17 26.12.19 09:21 Сейчас в теме
8. Vortigaunt 96 26.12.19 09:29 Сейчас в теме
Где ж ты раньше был, когда мне надо было найти дубли адресов в базе?
Тогда наваял свой какой-то велосипедно-костыльный алгоритм, который возвращал процент схожести строк.
А здесь с выкладками, все четко! Однозначно плюс. Спасибо.
9. vbuots 20 27.12.19 11:00 Сейчас в теме
Отлично оформленная статья. Спасибо!
11. AzagTot 40 03.03.20 17:21 Сейчас в теме
Отличная работа! Спасибо!
Добавьте файл в раздел "Скачать файлы" за SM.
Уверен, что многие в качестве благодарности скачают)
12. Perfolenta 204 03.03.20 22:35 Сейчас в теме
В примере 2 не понятно почему L=3, хотя должно быть 4...
В примере 3 на правой картинке одна 1 стоит не правильно и в результате m посчитано не правильно...
В примере 3 слева условие dj >= bt не применялось, хотя в функции оно есть...
Использование в функции Соответствия наверное перебор, без него можно было бы обойтись...
А так, да, материал полезный...
13. brooho 191 04.03.20 10:50 Сейчас в теме
(12) Спасибо за внимательное прочтение и замечания. Постараюсь ответить по-порядку.
1. В примере 2 длина префикса L действительно равна 4-м, а не 3-м, как было на картинке. Поправил вместе с результатом.
2. В примере 3 на правой картинке обозначение одной из транспозиций символа "А" действительно находилась не на своем месте (в столбце символа "В". Поправил. Однако эта перестановка не меняет величину m и соответственно не влияет на результат. Отсюда следует, что утверждение ".. посчитано не правильно..." основано на предположении, а не практической проверке.
3. "В примере 3 слева условие dj >= bt не применялось, хотя в функции оно есть..." - верно. Добавил соответствующее примечание перед примером.
Слава Богу данные ошибки не системные, а результат нудной оформительской работы. Надеюсь на понимание.
4. "Использование в функции Соответствия наверное перебор," - это уже из области холивара:) - "без него можно было бы обойтись..." - с удовольствием добавлю в публикацию второй, более изящный вариант реализации алгоритма, если порадуете.

А вот ошибку в функции основного алгоритма не заметили:) В первом условии, где "в лоб" сравниваются оба слова, функция всегда возвращала - 1, вне зависимости от значения параметра "Процент". Поправил.
Было:
Если s1 = s2 Тогда
Возврат 1;
КонецЕсли;

Стало:
Если s1 = s2 Тогда
Возврат ?(Процент,100,1);
КонецЕсли;
14. Perfolenta 204 04.03.20 14:16 Сейчас в теме
(13)
Однако эта перестановка не меняет величину m и соответственно не влияет на результат.

ну не знаю... объясните тогда почему вы в столбце 9 засчитали в m две транспозиции из трех? может я и не прав...
это уже из области холивара:)

почему холивара? скорее из области производительности...
свою версию реализации без Соответствия я конечно могу привести, но сначала ответьте на вопрос про столбец 9, т.к. возможно, что мы с вами по разному интерпретируем правила подсчета транспозиций... весьма не четко описанные в Википедии и других источниках... вы провели хорошую работу по исследованию вопроса...
судя по структуре формулы Джаро, она ни когда не должна превышать 1, т.к. все три слагаемых не превышают единицу... если превышают, значит трактовка подсчета m и tr не верная... так мне кажется...
однако, алгоритм довольно странный... например, если взять строки АААААААА и ААА, то будет 3 совпадения и море транспозиций... мне кажется, что на каждый столбец надо учитывать либо совпадение, либо транспозицию, с приоритетом совпадения...
я ни чего не утверждаю, я сам хочу разобраться...
А вот ошибку в функции основного алгоритма не заметили

я ваш код не изучал и не использовал (только бегло просмотрел, когда обнаружил, что не использовано условие)... я попытался написать свой и в процессе тестирования на ваших примерах обнаружил те ошибки о которых написал...
15. brooho 191 05.03.20 05:27 Сейчас в теме
(14)
мне кажется, что на каждый столбец надо учитывать либо совпадение, либо транспозицию, с приоритетом совпадения...
- Вы абсолютно правы. Я того-же мнения. И не смотря на действительное не четкое описание правил транспозиции, этот вывод напрашивается сам собой. Транспозиция, она же перестановка, может быть только одна для одного символа. Либо совпадение по позиции, либо перестановка. По злосчастному столбцу 9 признаю ошибку, которую упорно не хотел замечать (поправил, кстати). Та единица на картинке должна была быть красная (неверно посчитанная транспозиция) и само-собою не должна влиять на величину m и результат. Приведенная функция её естественно и не учитывает. Как это не смешно, но это тоже ошибка исключительно оформительская. Естественно результат в примере 3 изменился в меньшую сторону, но утверждение, что результат конечно же зависит от порядка сравнения строк, длинной с короткой и наоборот, остается верным. Большое спасибо за указанную неточность.

например, если взять строки АААААААА и ААА, то будет 3 совпадения и море транспозиций
- функция выдаст 3 совпадения и 0 транспозиций. Результат будет одинаков для любого варианта сравнения. Хотя сравнивать разной длины последовательности из одинаковых символов на мой взгляд не совсем корректно. Всё-таки алгоритм направлен именно на сравнение слов. Ведь (повторюсь) расстояние Джаро между двумя словами — это минимальное число одно— символьных преобразований, которое необходимо для того, чтобы изменить одно слово в другое.

почему холивара? скорее из области производительности...
- Возможно и так. По поводу производительности универсальных коллекций 1С есть замечательный материал с подробными выкладками - Эффективная обработка данных в оперативной памяти за счет использования коллекции "соответствие"
Замеров производительности функции не осуществлялось, ибо написана была под конкретный случай для обработки ограниченного объёма информации. Поэтому быстродействие не являлось ключевым фактором.
16. Perfolenta 204 05.03.20 11:39 Сейчас в теме
(15)
По поводу производительности универсальных коллекций

Соответствие быстрее других коллекций при поиске элемента, но без него еще быстрее :)
я написал бы, например, так:
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 

Показать
17. Perfolenta 204 05.03.20 12:04 Сейчас в теме
(15) не везёт... :)
теперь у меня не сходится с вашими цифрами Пример 2...
m=9
tr=1
t=0, а у вас 1
результат у меня 0.944
ошибка наверное тоже оформительская... но не сходится же :)
18. user1501924 08.12.20 14:34 Сейчас в теме
Пример с АБРАКАДАБРОЙ неверный
Проверьте по сайту
https://asecuritysite.com/forensics/simstring
20. user1779715 01.05.22 14:52 Сейчас в теме
(18)
Расстояние Джаро — Винклера

на сайте на котором вы проверяли в число транспозиции включаются только те позиции которые "нарушают" последовательность букв (в википедии вроде такие же расчеты, но там тоже не понятно, т.к. в одном случае одно а в другом другое), а в данном методе в транспозиции включаются все отклонения от индекса в сравниваемой строке.

Что бы было понятно, порядок букв которые считаются "совпавшими" в словах АбрАКАДАбРА и АвАДАКедАвРА я выделил прописными буквами.
Дак вот, в описанном методе под число транспозиции попадают 7 букв, т.к. индексы у найденных позиций во второй строке не соответствуют первой строке (по факту совпала только первая буква А).
А если считать только те буквы которые нарушили последовательность, это только буквы К и Д. Если это учесть в расчете, то значения на сайте и в данном коде совпадут.

P.S.: Какой из расчетов правильный - сложно сказать, тк как уже ранее заметили - непонятно что считать транспозицией в данном случае...
21. user1779715 01.05.22 15:36 Сейчас в теме
(20)причем, если махнуть местами буквы в слове абракДАабра, для того что бы проверить эту теорию (только буква К не на том месте в последовательности совпадений), на том же сайте итоговое значение остается неизменным,так что не факт что там правильно, хотя скорее всего это связано с округлением значения t при делении t на 2. что кстати говоря тоже не оговорено, т.к. число t может быть не целым в уравнении.
19. y22-k 250 10.03.21 13:33 Сейчас в теме
Спасибо, супер статья, очень пригодилось!
22. user1950534 08.11.23 16:16 Сейчас в теме
Ну неплохо было бы в самом начале написать хотя бы цитату из Википедии:

Чем меньше расстояние Джаро — Винклера d_{w} для двух строк, тем больше сходства имеют эти строки друг с другом. Результат нормируется, так что 0 означает отсутствие сходства, а 1 — точное совпадение.

А то непонятно, 0.75 это много или мало и 1.2 чем это плохо))

В остальном огонь, но практическое применение я думаю будет сводиться к подбору именно целевого минимального значения схожести....
Оставьте свое сообщение