Парсер таблиц по шаблону. Автоматическая корректировка парсера. Сравнение графов

Публикация № 1054367

Программирование - Практика программирования

графы сравнение таблицы программирование алгоритмы v8

11
Возникла такая задача: нужно нарисовать в макете шаблон таблицы, где расписано какая ячейка за что отвечает, загрузить таблицу из html и сравнить, подходит ли она под шаблон. Если да, то загрузить информацию по правилу из шаблона. Проблема в том, что в html таблица может приходить с ошибками, то есть какие то ячейки совмещены, хотя не должны. Поэтому нужно сделать так, что бы программа понимала, что таблицы похожи и где конкретно ошибки. Соответсвенно, поделил задачу на 3 этапа. 1 - это представление таблицы в виде графа, 2 - сравнение графов, 3 - забор информации. В данной статье пойдет описание пункта 2.

Описание 1го пункта здесь.

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

Идея алгоритма очень проста. Граф 1 назову шаблон, граф 2 - граф. Из шаблона и графа построю новый граф. Рассмотрим i-ый узел у шаблона и графа. Берём i+1 узлы и сравниваем. Если рёбра у них одинаковы, то добавляем i узел в новый граф и его рёбра(здесь и далее "добавлять/вставлять рёбра узла" означает "добавлять/вставлять рёбра узла, которые меньше i"). Если отличаются, то есть 3 действия (сортировка по приоритету):

1) ничего не делаю

2) вставляю узел из шаблона

3) вставляю узел из графа.

Для каждого действия рассчитаю i+1 узел шаблона и графа. Для 1 - это просто i+1 узлы. Для 2 i+1 узел графа- это i, у которого часть рёбер убраны, часть увеличено на 1 (подробнее ниже). i+1 шаблона остаётся прежним. Для 3 у i узла шаблона изменятся рёбра, а у i+1 графа остаётся как есть.

Теперь для каждого действия  рассчитываю функцию ошибки между i+1 узлами. Выбираю то действие, у которого функция ошибки меньше. Если есть равенство, то выбираю по приоритету. 

На выходе получается новый граф с узлами из шаблона и графа. Я знаю какие узлы, откуда вставлял, какие новые рёбра и откуда. Из этого можно сделать вывод какие ячейки объединены, какие разделены. 

функция ВыделитьПервыеЗначенияИзСписка(Список,Предел)
	спис = новый СписокЗначений;
	Для каждого стр из Список цикл
		Если стр.Значение>Предел тогда
			Прервать;
		КонецЕсли;
		спис.Добавить(стр.Значение);
	КонецЦикла;
	возврат спис;
КонецФункции

функция КоэфициентВхожденияСписка1ВСписке2(список1,список2)
	
	//критерий. максимум насколько одна вершина входит во вторую
	Если типЗнч(список1) = тип("Массив") тогда
		_список1 = новый СписокЗначений;
		_список1.ЗагрузитьЗначения(список1);
	иначе
		_список1 = список1;
	КонецЕсли;
	
	Если типЗнч(список2) = тип("Массив") тогда
		_список2 = новый СписокЗначений;
		_список2.ЗагрузитьЗначения(список2);
	иначе
		_список2 = список2;
	КонецЕсли;
	
	Вхождений1 = 0;
	Для каждого стр из _список1 цикл
		Если _список2.найтиПоЗначению(стр.Значение)<> Неопределено тогда
			Вхождений1 = Вхождений1+1;
		КонецЕсли;
	КонецЦикла;
	
    //0 - всё входит, 1 - ничего
	Если _список1.Количество() = 0 или _список2.Количество() = 0 тогда
		возврат 1;
	КонецЕсли;
	
	КоэффициентВхождений = 1-окр(Вхождений1/_список1.Количество(),2);//макс(окр(Вхождений1/_список1.Количество(),2),окр(Вхождений2/_список2.Количество(),2));
	возврат КоэффициентВхождений; 
КонецФункции

функция ВычислитьКоличествоОшибок(список1,список2)
	
	//критерий. насколько отличаются списке в абсолютном значении
	Если типЗнч(список1) = тип("Массив") тогда
		_список1 = новый СписокЗначений;
		_список1.ЗагрузитьЗначения(список1);
	иначе
		_список1 = список1;
	КонецЕсли;
	
	Если типЗнч(список2) = тип("Массив") тогда
		_список2 = новый СписокЗначений;
		_список2.ЗагрузитьЗначения(список2);
	иначе
		_список2 = список2;
	КонецЕсли;
	
	
	если _список1.Количество()< _список2.Количество() тогда
		расСпис = _список1;
		СЧемСравнивать = _список2; 
	иначе
		расСпис = _список2;
		СЧемСравнивать = _список1; 
	КонецЕсли;
	КоэффициентВхождений = 0;
	Для каждого стр из расСпис цикл
		Если СЧемСравнивать.найтиПоЗначению(стр.Значение)<> Неопределено тогда
			КоэффициентВхождений = КоэффициентВхождений+1;
		КонецЕсли;
	КонецЦикла;	
	
	если КоэффициентВхождений = _список1.Количество() и КоэффициентВхождений = _список2.Количество() тогда
		//это абсолютно одинаковые узлы
		возврат 0;
	иначе
		возврат ?(КоэффициентВхождений = 0,100,1/КоэффициентВхождений);
	КонецЕсли;
	
КонецФункции

Процедура ДобавитьСвязиВпрошлыеУзлыСТекущим(Куда, что, Индекс)
	Для каждого узел из что цикл
		если Куда[узел.значение].найтиПоЗначению(Индекс) = Неопределено тогда
			Куда[узел.значение].Добавить(Индекс);
			Куда[узел.значение].СортироватьПоЗначению();
		КонецЕсли;
	КонецЦикла;    	
КонецПроцедуры

Процедура Прибавить1КНомеруУзла(МассивУзлов, Индекс)
	Для инт = 0 по МассивУзлов.Количество()-1 цикл
		НовСписокКуда = новый СписокЗначений;
		Для каждого УзелГрафа из МассивУзлов[инт] цикл
			Если УзелГрафа.Значение>=Индекс тогда
				НовСписокКуда.Добавить(УзелГрафа.Значение + 1);
			иначе
				НовСписокКуда.Добавить(УзелГрафа.Значение);
			КонецЕсли;
		КонецЦикла;
		МассивУзлов[инт] = НовСписокКуда;
	КонецЦикла;    	
КонецПроцедуры

функция РассчитатьСледующийУзел(ИзЧегоСчитать,ВставляемыйУзел,Индекс,УзлыОставлять=Неопределено)
	//если в ВставляемыйУзел есть связь с узлом, которая есть в ИзЧегоСчитать, то её надо поменять на индекс
	//типа разбиваем связь
	если УзлыОставлять = Неопределено тогда
		УзлыОставлять = новый СписокЗначений;
	КонецЕсли;
	РассчетныйСледующийШаблона = новый СписокЗначений;
	Для каждого узел из ИзЧегоСчитать цикл
		Если ВставляемыйУзел.найтиПоЗначению(узел.Значение) <> Неопределено и УзлыОставлять.найтиПоЗначению(узел.Значение) = Неопределено тогда
			если РассчетныйСледующийШаблона.найтиПоЗначению(Индекс) = Неопределено тогда
				РассчетныйСледующийШаблона.Добавить(Индекс);	
			КонецЕсли;
		иначеесли узел.Значение>Индекс тогда
			РассчетныйСледующийШаблона.Добавить(Узел.Значение+1);	
		иначе
			РассчетныйСледующийШаблона.Добавить(Узел.Значение);	
		КонецЕсли;
	КонецЦикла;
	возврат РассчетныйСледующийШаблона;
КонецФункции

Процедура  ВставитьНовыйУзелВГраф(НовыйГраф,Индекс,НовыеУзлы,ВставляемыеУзлы,Источник,ДругойГраф,АтрибутыДругойГраф)
	НовыйГраф.Вставить(Индекс,НовыеУзлы);			
	ДобавитьСвязиВпрошлыеУзлыСТекущим(НовыйГраф, НовыеУзлы,Индекс);
	Прибавить1КНомеруУзла(ДругойГраф,Индекс);
	ДругойГраф.Вставить(Индекс,новый СписокЗначений);
	АтрибутыДругойГраф.Вставить(индекс);
	нов = ВставляемыеУзлы.Добавить();
	нов.Источник = Источник;
	нов.Индекс = Индекс;
КонецПроцедуры

Процедура ОбъединитьРёбраУзла(ВставляемыеРёбра,УзлыГраф,УзлыШаблон,НовыйГраф,Индекс)
	СписокВставляемыРёбер = ВставляемыеРёбра.Получить(Индекс);
	Если СписокВставляемыРёбер = Неопределено тогда
		СписокВставляемыРёбер = новый СписокЗначений;
	КонецЕсли;
	
	НовыеУзлы = новый СписокЗначений;
	Для каждого стр из УзлыГраф цикл 					
		если НовыеУзлы.найтиПоЗначению(стр.значение) = Неопределено тогда
			НовыеУзлы.Добавить(стр.значение);
		КонецЕсли;
		Если УзлыШаблон.найтиПоЗначению(стр.значение) = Неопределено тогда
			СписокВставляемыРёбер.Добавить(стр.значение);
			найд = ВставляемыеРёбра.Получить(стр.значение);
			Если найд = Неопределено тогда
				найд = новый СписокЗначений;
			КонецЕсли;
			найд.Добавить(Индекс);			
			ВставляемыеРёбра.Вставить(стр.значение,найд);
		КонецЕсли;
	КонецЦикла;
	Для каждого стр из УзлыШаблон цикл 					
		если НовыеУзлы.найтиПоЗначению(стр.значение) = Неопределено тогда
			НовыеУзлы.Добавить(стр.значение);
		КонецЕсли;
		Если УзлыГраф.найтиПоЗначению(стр.значение) = Неопределено тогда
			СписокВставляемыРёбер.Добавить(стр.значение);
			найд = ВставляемыеРёбра.Получить(стр.значение);
			Если найд = Неопределено тогда
				найд = новый СписокЗначений;
			КонецЕсли;
			найд.Добавить(Индекс);
			ВставляемыеРёбра.Вставить(стр.значение,найд);
		КонецЕсли; 					
	КонецЦикла;
	НовыйГраф.Вставить(Индекс,НовыеУзлы);
	ДобавитьСвязиВпрошлыеУзлыСТекущим(НовыйГраф, НовыеУзлы,Индекс);
	ВставляемыеРёбра.Вставить(Индекс,СписокВставляемыРёбер);
КонецПроцедуры

функция РассчитатьОшибкиПриВставкеУзла(Откуда,ИндексОткуда,Индекс,Куда,ВставляемыйУзел)
	РассчетныйСледующийОткуда = Откуда[ИндексОткуда];
	РассчетныйСледующийКуда = РассчитатьСледующийУзел(Куда[Индекс],ВставляемыйУзел,Индекс);
	количествоОшибок = ВычислитьКоличествоОшибок(РассчетныйСледующийКуда,РассчетныйСледующийОткуда);
	//расмматриваются все возможные сочетания (без учета места)
	Для инт=0 по ВставляемыйУзел.Количество()-1 цикл
		УзлыОставлять = новый СписокЗначений;
		УзлыОставлять.Добавить(ВставляемыйУзел[инт].Значение);
		РассчетныйСледующийКуда = РассчитатьСледующийУзел(Куда[Индекс],ВставляемыйУзел,Индекс,УзлыОставлять);
		количествоОшибок = мин(ВычислитьКоличествоОшибок(РассчетныйСледующийКуда,РассчетныйСледующийОткуда),количествоОшибок);
		
		Для йцу = инт+1 по  ВставляемыйУзел.Количество()-1 цикл
			УзлыОставлять.Добавить(ВставляемыйУзел[йцу].Значение);
			РассчетныйСледующийКуда = РассчитатьСледующийУзел(Куда[Индекс],ВставляемыйУзел,Индекс,УзлыОставлять);
			количествоОшибок = мин(количествоОшибок,ВычислитьКоличествоОшибок(РассчетныйСледующийКуда,РассчетныйСледующийОткуда));
		КонецЦикла;
	КонецЦикла;
	возврат КоличествоОшибок;
КонецФункции

&НаСервере
процедура ЗаполнитьНовыйГраф(НовыйГраф,Шаблон,Граф,ВставляемыеУзлы,ВставляемыеРёбра,АтрибутыШаблона,АтрибутыГрафа)
	МаксРазмер = макс(Шаблон.Количество(), Граф.Количество());
	Индекс=0;
	Пока Индекс<=МаксРазмер-1 цикл  		
		//рассматриваем только узлы, которые меньше текущего индекса
		если Шаблон.ВГраница()<Индекс и Граф.ВГраница()<Индекс тогда
			Прервать;
		иначеесли Шаблон.ВГраница()<Индекс тогда
			НовыеУзлы = ВыделитьПервыеЗначенияИзСписка(Граф[Индекс],Индекс); 
			ВставитьНовыйУзелВГраф(НовыйГраф,Индекс,НовыеУзлы,ВставляемыеУзлы,"Граф",Шаблон,АтрибутыШаблона);
			Индекс = Индекс + 1;
			Продолжить;
		иначеесли Граф.ВГраница()<Индекс тогда
			НовыеУзлы = ВыделитьПервыеЗначенияИзСписка(Шаблон[Индекс],Индекс); 
			ВставитьНовыйУзелВГраф(НовыйГраф,Индекс,НовыеУзлы,ВставляемыеУзлы,"Шаблон",Граф,АтрибутыГрафа);
			Индекс = Индекс + 1;
			Продолжить;
		КонецЕсли;
		
		УзлыШаблон = Шаблон[Индекс];
		УзлыГраф = граф[Индекс];
		
		если строка(УзлыГраф) = строка(УзлыШаблон) тогда
			//вставим рёбра в прошлые узлы
			Узлы = ВыделитьПервыеЗначенияИзСписка(УзлыШаблон,Индекс); 
			НовыйГраф.Вставить(Индекс,Узлы);	
			ДобавитьСвязиВпрошлыеУзлыСТекущим(НовыйГраф, Узлы,Индекс);
		иначе
			//рассмотрим 3 действия
			//1)объединим рёбра узлов графа и шаблона
			//2)Добавим узел шаблона
			//3)Добавим узел графа
			//Сравним следующие узлы в каждом из случаев. Выберу тот случай, в котором ошибка наименьше.
			//если это последняя узел для одной, то сравниваем следующую с ней.
			//если обе последние, то соединяем
			если Индекс=Шаблон.ВГраница() и Граф.ВГраница()=Индекс тогда
				УзлыГраф = ВыделитьПервыеЗначенияИзСписка(УзлыГраф,Индекс);
				УзлыШаблон = ВыделитьПервыеЗначенияИзСписка(УзлыШаблон,Индекс);				
				ОбъединитьРёбраУзла(ВставляемыеРёбра,УзлыГраф,УзлыШаблон,НовыйГраф,Индекс);
			иначе
				ИндексШаблон = ?(Индекс=Шаблон.ВГраница(),Индекс,Индекс+1);
				ИндексГраф = ?(Индекс=Граф.ВГраница(),Индекс,Индекс+1);
				//1
				СледующийУзелГраф = Граф[ИндексГраф]; 
				СледующийУзелШаблон = Шаблон[ИндексШаблон];
				количествоОшибокНичего = ВычислитьКоличествоОшибок(СледующийУзелГраф,СледующийУзелШаблон);
				//бывает ситуация когда ошибка влияет на рёбра узла. К примеру, рассматриваем 9 узел, ошибка в 11
				//рёбра 9 {12,13,14}. Корректнее ничего не делать, 11 узел добавляю, все корректно.
				//НО, если просто смотреть, то рёбра на текущий момент у одного графа {13,14,15} а у второго {12,13,14}
				//тогда программа решает что выгоднее производить другое действия.
				//поэтому имеет смысл рассматривать варианты +1 к следующим за индексом узлам. 				
				РассчетныйСледующийШаблона = РассчитатьСледующийУзел(СледующийУзелШаблон,новый СписокЗначений,Индекс,новый СписокЗначений);
				РассчетныйСледующийГраф = РассчитатьСледующийУзел(СледующийУзелГраф ,новый СписокЗначений,Индекс,новый СписокЗначений);
				количествоОшибокНичего = мин(количествоОшибокНичего,ВычислитьКоличествоОшибок(СледующийУзелГраф,РассчетныйСледующийШаблона),ВычислитьКоличествоОшибок(СледующийУзелШаблон,РассчетныйСледующийГраф));
				//2  				
				//при вставке узла, есть вариант когда рёбра расчётного следующего разрушаются, а могут и не разрушаться
				//просмотрю все варианты и выберу наименьшую ошибку
				ВставляемыйУзелГраф = ВыделитьПервыеЗначенияИзСписка(Граф[Индекс],Индекс);
				КоличествоОшибокВставитьГраф = РассчитатьОшибкиПриВставкеУзла(Граф,ИндексГраф,Индекс,Шаблон,ВставляемыйУзелГраф);
				//3
				ВставляемыйУзелШаблон = ВыделитьПервыеЗначенияИзСписка(Шаблон[Индекс],Индекс);
				количествоОшибокВставитьШаблон = РассчитатьОшибкиПриВставкеУзла(Шаблон,ИндексШаблон,Индекс,граф,ВставляемыйУзелШаблон);
				
				МинОшибка = мин(количествоОшибокНичего ,количествоОшибокВставитьГраф,количествоОшибокВставитьШаблон);
				
				НичегоНеДелать = МинОшибка =  количествоОшибокНичего;
				ДобавитьУзелИзГрафа = МинОшибка =  количествоОшибокВставитьГраф; 
				ДобавитьУзелИзШаблона = МинОшибка =  количествоОшибокВставитьШаблон; 
				
				//также конкретно следующий узел может быть ошибочным, поэтому сравнение следующих узлов может выдать некорректное действие.
				//Попробую вставить не текущий узел, а следующий, заодно рассчитать послеследующий узел и ошибки в нём
				//Если ошибка меньше чем текущая ошибка вставки, то выгоднее ничего не делать.
				Если  КоличествоОшибокВставитьГраф<>0 и количествоОшибокВставитьШаблон<>0 тогда
					если ДобавитьУзелИзШаблона и ИндексШаблон<Шаблон.ВГраница()и Индекс<Граф.ВГраница() тогда
						КоличествоОшибокВставитьСледующий = ВычислитьКоличествоОшибок(РассчитатьСледующийУзел(Граф[Индекс+1],ВыделитьПервыеЗначенияИзСписка(Шаблон[Индекс+1],Индекс+1),Индекс+1),Шаблон[ИндексШаблон+1]);
						если  КоличествоОшибокВставитьСледующий< количествоОшибокВставитьШаблон тогда
							НичегоНеДелать = истина;
						КонецЕсли;
					КонецЕсли; 
					если ДобавитьУзелИзГрафа и ИндексГраф<Граф.ВГраница() и Индекс<Шаблон.ВГраница() тогда
						КоличествоОшибокВставитьСледующий = ВычислитьКоличествоОшибок(РассчитатьСледующийУзел(Шаблон[Индекс+1],ВыделитьПервыеЗначенияИзСписка(Граф[Индекс+1],Индекс+1),Индекс+1),Граф[ИндексГраф+1]);
						если  КоличествоОшибокВставитьСледующий< КоличествоОшибокВставитьГраф тогда
							НичегоНеДелать = истина;
						КонецЕсли;
					КонецЕсли;
				КонецЕсли;
				
				Если НичегоНеДелать тогда
					//1) объединяем
					//надо запомнить какие узлы откуда были добавлены
					ОбъединитьРёбраУзла(ВставляемыеРёбра,ВставляемыйУзелГраф,ВставляемыйУзелШаблон,НовыйГраф,Индекс);
				ИначеЕсли ДобавитьУзелИзШаблона тогда 
					//2)Добавим узел Шаблона
					НовыеУзлы = новый СписокЗначений;
					НовыеУзлы.ЗагрузитьЗначения(ВставляемыйУзелШаблон.ВыгрузитьЗначения()); 					
					ВставитьНовыйУзелВГраф(НовыйГраф,Индекс,НовыеУзлы,ВставляемыеУзлы,"Шаблон",Граф,АтрибутыГрафа);
				ИначеЕсли ДобавитьУзелИзГрафа тогда    
					//3)Добавим узел графа
					НовыеУзлы = новый СписокЗначений;
					НовыеУзлы.ЗагрузитьЗначения(ВставляемыйУзелГраф.ВыгрузитьЗначения()); 					
					ВставитьНовыйУзелВГраф(НовыйГраф,Индекс,НовыеУзлы,ВставляемыеУзлы,"Граф",Шаблон,АтрибутыШаблона);
				КонецЕсли;
			КонецЕсли;
		КонецЕсли;
		МаксРазмер = макс(Шаблон.Количество(), Граф.Количество());
		Индекс = Индекс + 1;
	КонецЦикла;
КонецПроцедуры

&НаСервере
функция  СгруппироватьОбъединенияВычислитьОшибку(ТабОбъединений,АтрибутыШаблона,АтрибутыГрафа,НовыйГраф,ВставляемыеРёбра,ВставляемыеУзлы)
	СчетчикОшибок = 0;
	КолДобавленныйСвязей = 0;
	Правки = новый Массив;
	
	//в предыдущеё операции получили объединеннные пары узлов. Тут сгруппирую.
	ЗАпрос = новый запрос("ВЫБРАТЬ
	|	таб.ДобавляемыУзел КАК ДобавляемыУзел,
	|	таб.Объединен КАК Объединен,
	|	таб.Источник КАК Источник
	|ПОМЕСТИТЬ Объеденения
	|ИЗ
	|	&таб КАК таб
	|;
	|
	|////////////////////////////////////////////////////////////////////////////////
	|ВЫБРАТЬ РАЗЛИЧНЫЕ
	|	Объеденения.Объединен КАК Объединен,
	|	Объеденения1.ДобавляемыУзел КАК ДобавляемыУзел,
	|	Объеденения1.Источник КАК Источник
	|ИЗ
	|	Объеденения КАК Объеденения
	|		ЛЕВОЕ СОЕДИНЕНИЕ Объеденения КАК Объеденения1
	|		ПО Объеденения.Объединен = Объеденения1.Объединен
	|ИТОГИ ПО
	|	Объединен");
	ЗАпрос.УстановитьПараметр("таб", ТабОбъединений);
	Рез = Запрос.Выполнить().Выбрать(ОбходРезультатаЗапроса.ПоГруппировкам);
	
	РасмотренныеУзлы= новый Массив;
	
	Пока рез.Следующий() цикл
		//паралельно вычислю ошибку по размеру объединённых ячеек.
		//Известно что либо в графе была разбита ясйека, либо в шаблоне,
		//знаю, какие конкретно, а значит могу сравнить суммы разбитых и исходную
		ДобавленоШаблоном = ложь;
		ДобавленоГрафом = ложь;
		Дет = рез.Выбрать();
		Спис = новый СписокЗначений;
		спис.Добавить(рез.Объединен);
		РасмотренныеУзлы.Добавить(рез.Объединен);
		РазмерШаблон = АтрибутыШаблона[рез.Объединен].РазмерХ*АтрибутыШаблона[рез.Объединен].РазмерУ;
		РазмерГраф = АтрибутыГрафа[рез.Объединен].РазмерХ*АтрибутыГрафа[рез.Объединен].РазмерУ;
		
		пока дет.Следующий() цикл
			спис.Добавить(дет.ДобавляемыУзел);
			ДобавленоШаблоном = макс(ДобавленоШаблоном,дет.Источник = "Шаблон");
			ДобавленоГрафом =макс(ДобавленоГрафом,дет.Источник = "Граф");
			РасмотренныеУзлы.Добавить(дет.ДобавляемыУзел);
			РазмерШаблон = РазмерШаблон + АтрибутыШаблона[дет.ДобавляемыУзел].РазмерХ*АтрибутыШаблона[дет.ДобавляемыУзел].РазмерУ;
			РазмерГраф = РазмерГраф + АтрибутыГрафа[дет.ДобавляемыУзел].РазмерХ*АтрибутыГрафа[дет.ДобавляемыУзел].РазмерУ;
		КонецЦикла;
		если ДобавленоШаблоном и ДобавленоГрафом тогда
			источник = "Непонятно что";
		иначеесли ДобавленоШаблоном тогда
			источник = "Шаблон";
		иначеесли ДобавленоГрафом тогда
			источник = "Граф";
		КонецЕсли;
		Правки.Добавить(новый Структура("Источник,Тип,Узлы",источник,"Объединили",спис));
		Если   источник = "Непонятно что" тогда
			СчетчикОшибок = СчетчикОшибок + спис.Количество();
		ИначеЕсли РазмерШаблон<>РазмерГраф Тогда 
			СчетчикОшибок = СчетчикОшибок + 1;
		КонецЕсли;
	КонецЦикла;
	
	//тут рассмотри все остальные ячейки
	Для инт=0 по НовыйГраф.Количество()-1 цикл
		если РасмотренныеУзлы.Найти(инт)<>Неопределено тогда
			Продолжить;
		КонецЕсли;
		если не АтрибутыГрафа[инт].РазмерХ*АтрибутыГрафа[инт].РазмерУ =  АтрибутыШаблона[инт].РазмерХ*АтрибутыШаблона[инт].РазмерУ тогда
			СчетчикОшибок = СчетчикОшибок + 1;
		КонецЕсли;		
	КонецЦикла;	
	
	//количество новых рёбер с недобавленными узлами
	МасПроверенныйСвязей = новый массив();	
	Для каждого Узел из ВставляемыеРёбра цикл
		Для каждого ребро из Узел.Значение цикл
			поиск = ""+Узел.Ключ+"_"+ ребро.Значение;
			если МасПроверенныйСвязей.Найти(поиск)<>Неопределено тогда
				Продолжить;	
			КонецЕсли;
			поиск = ""+ ребро.Значение+"_"+ Узел.Ключ;
			если МасПроверенныйСвязей.Найти(поиск)<>Неопределено тогда
				Продолжить;	
			КонецЕсли;
			Если ВставляемыеУзлы.найти(ребро.Значение,"Индекс") = Неопределено и  ВставляемыеУзлы.найти(Узел.Ключ,"Индекс") = Неопределено тогда
				КолДобавленныйСвязей = КолДобавленныйСвязей + 1;
				МасПроверенныйСвязей.Добавить(""+Узел.Ключ+"_"+ ребро.Значение);
			КонецЕсли;
		КонецЦикла;
	КонецЦикла;
	
	//количество новых рёбер с добавленными узлами
	Для каждого стр из ВставляемыеУзлы цикл
		КолДобавленныйСвязей = КолДобавленныйСвязей + НовыйГраф[стр.индекс].Количество();
	КонецЦикла;
	
	возврат новый Структура("СчетчикОшибок,КолДобавленныйСвязей,Правки",СчетчикОшибок,КолДобавленныйСвязей,Правки);
КонецФункции

&НаСервере
функция СравнитьГрафы(Знач Шаблон,Знач Граф,Знач АтрибутыШаблона,Знач АтрибутыГрафа)
	
	//Строим новый граф 
	НовыйГраф = новый Массив;
	
	ВставляемыеУзлы = новый ТаблицаЗначений;
	ВставляемыеУзлы.Колонки.Добавить("Индекс");
	ВставляемыеУзлы.Колонки.Добавить("Источник");
	
	ВставляемыеРёбра = новый Соответствие;
	
	ЗаполнитьНовыйГраф(НовыйГраф,Шаблон,Граф,ВставляемыеУзлы,ВставляемыеРёбра,АтрибутыШаблона,АтрибутыГрафа);
	
	//интерпритируем полученные данные.    	
	ТабОбъединений = новый ТаблицаЗначений;
	ТабОбъединений.Колонки.Добавить("ДобавляемыУзел",новый ОписаниеТипов("Число"));
	ТабОбъединений.Колонки.Добавить("Объединен",новый ОписаниеТипов("Число"));
	ТабОбъединений.Колонки.Добавить("Источник",новый ОписаниеТипов("Строка",,,,новый КвалификаторыСтроки(20)));
	
	ЗаполнитьТаблицуОбъединений(ВставляемыеУзлы,НовыйГраф,ТабОбъединений,ВставляемыеРёбра);
	
	Ответ = СгруппироватьОбъединенияВычислитьОшибку(ТабОбъединений,АтрибутыШаблона,АтрибутыГрафа,НовыйГраф,ВставляемыеРёбра,ВставляемыеУзлы);
	
	КоличествоСвязей = 0;
	Для каждого стр из НовыйГраф цикл
		КоличествоСвязей = КоличествоСвязей + стр.Количество();
	КонецЦикла;
	
	//Все новые рёбра, все новые узлы, все несовпадения по размерам влияют на результат.
	Похожесть = окр(((КоличествоСвязей - Ответ.КолДобавленныйСвязей) + (НовыйГраф.Количество()-Ответ.СчетчикОшибок))/(НовыйГраф.Количество()+КоличествоСвязей)*100);
	
	Для каждого стр из Ответ.Правки цикл
		Сообщить(стр.Источник + " "+стр.узлы);
	КонецЦикла;
	
	возврат Похожесть;
	
КонецФункции

&НаСервере
Процедура ЗаполнитьТаблицуОбъединений(ВставляемыеУзлы,НовыйГраф,ТабОбъединений,ВставляемыеРёбра)
	//Сформируем все рёбра добавленных узлов, без самих добавленных
	СоседниеУзлы = новый СписокЗначений;
	Для каждого Узел из ВставляемыеУзлы цикл		
		Соседние = НовыйГраф[Узел.Индекс];		
		Для каждого СоседнийУзел из Соседние цикл
			Если ВставляемыеУзлы.Найти(СоседнийУзел.Значение,"Индекс")=Неопределено тогда
				если СоседниеУзлы.НайтиПоЗначению(СоседнийУзел.Значение) = Неопределено тогда
					СоседниеУзлы.Добавить(СоседнийУзел.Значение);
				КонецЕсли;
			КонецЕсли;
		КонецЦикла;
	КонецЦикла;
	
	Для каждого Узел из ВставляемыеУзлы цикл				
		Для каждого СосоеднийУзел из СоседниеУзлы цикл
			//Добавленный узел означает, что узел шаблона/графа разбивается на 2. Нужно выяснить какой конкретно узел разбивается.
			//Если исходный узел разбился, то часть рёбер попадёт в добавленные. Нужно проверить если у соседнего узла
			//добавлённые рёбра полностью включают определённую часть рёбер добавленного узла, то эти узлы должны быть объединенны. 
			//Определенная часть  =  все рёбра - добавленные узлы - текущий соседний узел - узлы, иницдентные и добавленному узлу, и соседнему, но ребро не добавлено в соседний узел
			Соседние = НовыйГраф[Узел.Индекс].ВыгрузитьЗначения();
			СоседниеСоседнего = НовыйГраф[СосоеднийУзел.Значение].ВыгрузитьЗначения();
			//удаляю из соседних вставляемые узлы
			Для каждого УдаляемыУзел из ВставляемыеУзлы цикл
				найд = Соседние.найти(УдаляемыУзел.Индекс);
				Если не найд = Неопределено тогда
					Соседние.Удалить(найд);
				КонецЕсли;
			КонецЦикла;
			//найдем массив вставленных    			
			найд = ВставляемыеРёбра.Получить(СосоеднийУзел.Значение);
			если найд = Неопределено тогда МассивВставленныхРёберДляТекущегоУзла = новый Массив иначе МассивВставленныхРёберДляТекущегоУзла = найд.ВыгрузитьЗначения() КонецЕсли;
			
			//теперь из соседних текущего соседнего нужно удалить все рёбра, которые не вставлены, инциндентны и сам узел
			Для каждого УзелСоседниеСоседнего из СоседниеСоседнего цикл
				найд = Соседние.Найти(УзелСоседниеСоседнего);
				Если найд<>Неопределено и МассивВставленныхРёберДляТекущегоУзла.Найти(УзелСоседниеСоседнего) = Неопределено   тогда
					Соседние.Удалить(найд);
				КонецЕсли;
			КонецЦикла;
			найд = Соседние.найти(СосоеднийУзел.Значение);
			Если найд<>Неопределено тогда
				Соседние.Удалить(найд);
			КонецЕсли;
			//если связь всего одна, то проверяем на равенство
			входит = ложь;
			если Соседние.количество()=1 тогда
				входит = Соседние.Количество() = МассивВставленныхРёберДляТекущегоУзла.Количество() и Соседние[0]= МассивВставленныхРёберДляТекущегоУзла[0];
			иначе
				входит = КоэфициентВхожденияСписка1ВСписке2(Соседние,МассивВставленныхРёберДляТекущегоУзла) = 0;
			КонецЕсли;	
			//проверим, что один входит в другой
			если входит тогда		
				//соеденены
				нов = ТабОбъединений.Добавить();
				нов.ДобавляемыУзел = Узел.Индекс;
				нов.Источник = Узел.Источник;
				нов.Объединен = СосоеднийУзел.Значение;
			КонецЕсли;
		КонецЦикла;
	КонецЦикла;
КонецПроцедуры

Основная функция - СравнитьГрафы. В комментариях более-менее описаны нюансы. Пример использования

РезультатШаблон = РазобратьТаблицу_Область(макет,макет.области.Область1);
РезультатМатрица = РазобратьТаблицу_Область(макет,макет.области.Область2);
сообщить(""+СравнитьГрафы(РезультатШаблон.СписокСмежности,РезультатМатрица.СписокСмежности,РезультатШаблон.АтрибутыУзлов,РезультатМатрица.АтрибутыУзлов) +" % похожи");

Это функции из предыдущей статьи.

Теперь на простом примере опишу как работает сам алгоритм. Возьмём две таблицы.

Их графы следующие.

Списки смежностей такие

 

Шаблон Граф Новый 
( {1,4}
 {0,2,5}
 {1,3,6}
 {2,7}
 {0,5,8}
 {1,4,6,9}
 {2,5,7,10}
 {3,6,11}
 {4,9,12}
 {5,8,10,13}
 {6,9,11,14}
 {7,10,15}
 {8,13}
 {9,12,14}
 {10,13,15}
 {11,14})
( {1,4}
 {0,2,5}
 {1,3,5}
 {2,6}
 {0,5,7}
 {1,2,4,6,7,8,10,11}
 {3,5,8}
 {4,5,9}
 {5,6,12}
 {7,10}
 {5,9,11}
 {5,10,12}
 {8,11})
()

 

Строим новый граф. Смотрим 0 узел. И в шаблоне и в графе одинаковы. Пишем в новый граф.

1 узел, аналогично.

2 узел, рёбра отличаются. Рассмотрим следующие узлы {2,7} и {2,6}. Так как ошибка может быть в следующих узлах, это может влиять на нумерацию. Увеличим номер тех узлов, которые больше 2 и сравним. Получаем {2,8} и {2,7}. Теперь сравниваем {2,8} и {2,6}, {2,7} и {2,7}. Рёбра совпадают, значит ничего не делаем, добавляем в новый граф.

3 узел - аналогично. Возникают следующие рёбра {0,6,9} и {0,5,7}, {0,5,8} и {0,6,8}. При сравнении ошибка при ничего не делать - 0.5, при вставке узла из шаблона - 100, при вставке из графа - 100. Ничего не делаем, добавляем в новый граф.

4 узел - аналогично 3, ничего не делаем, добавляем в новый граф.

5 узел. Если ничего не делать, то следующие узлы будут {3,5,8} и {2,5,7,10}. Даже если увеличивать номера, то минимальная ошибка будет 0.5. Если добавить узел из графа, ошибка - 1, если добавить из шаблона узел {1,4}, то следующие узлы должны быть {2,5,7,10} и {2,5,7,8,9,11,12}. Ошибка - 0.33. Поэтому вставляем узел из шаблона в граф, в новый граф.

И так далее. 6, 7, 8, 11, 12, 13, 14, 15  узлы оставляются, 9,10 - добавляются. По итогу получается.

Шаблон Граф Новый 
( {1,4}
 {0,2,5}
 {1,3,6}
 {2,7}
 {0,5,8}
 {1,4,6,9}
 {2,5,7,10}
 {3,6,11}
 {4,9,12}
 {5,8,10,13}
 {6,9,11,14}
 {7,10,15}
 {8,13}
 {9,12,14}
 {10,13,15}
 {11,14})
( {1,4}
 {0,2,6}
 {1,3,6}
 {2,7}
 {0,6,8}
 {}
 {1,2,4,7,8,11,13,14}
 {3,6,11}
 {4,6,12}
 {}
 {}
 {6,7,15}
 {8,13}
 {6,12,14}
 {6,13,15}
 {11,14})
( {1,4}
 {0,2,5,6}
 {1,3,6}
 {2,7}
 {0,5,6,8}
 {1,4,6,9}
 {1,2,4,5,7,8,10,11,13,14}
 {3,6,11}
 {4,6,9,12}
 {5,8,10,13}
 {6,9,11,14}
 {6,7,10,15}
 {8,13}
 {6,9,12,14}
 {6,10,13,15}
 {11,14})

 

На рисунке оранжевым цветом выделены добавленные узлы и рёбра.

Достаточно чётко видно, что в рёбрах всех добавленных узлов есть узлы инцидентные с 6 и более того, данные рёбра отмечены как добавленные. По данному критерию можно сказать какие узлы должны быть объединены. Для i-го узла рассмотрим все соседние, не добавленные узлы. Если из рёбер i-го узла удалить все другие добавленные узлы, удалить текущий рассматриваемый соседний, а также удалить те узлы, которые инцидентны и i и соседнему, но не являются добавленным для соседнего. То в итоге, оставшиеся рёбра должны полностью включаться в добавленным для соседнего.

То есть, к примеру, у узла 5 рёбра {1,4,6,9}, у узла 6 добавленные  {1,4,5,8,11,13,14}. Удалим узел 6, так как его рассматриваем и узел 9, так как он добавленный. {1,4} оставляем, так как они инцидентны, но в списке добавленных. {1,4} полностью включается в {1,4,5,8,11,13,14}. Значит 5 и 6 объединены.

Рассматривается именно так, потому что смысл добавления узла - это дробление ячейки таблицы, а это значит, что добавленный узел перенимает на себя часть рёбер узла, который дробят.

В итоге, программа поймёт что необходимо объединить {5,6,9,10}. Также программа будет понимать, что узлы вставлены из шаблона, а значит в графе они объединены.

Коэффициент похожести рассчитывается так:

(Количество узлов - количество добавленных узлов - ошибки размеров ячеек)  + (количество рёбер узлов - количество добавленных рёбер, не инцедентных добавленным узлам + количество рёбер добавленных узлов))/(Количество узлов +Количество рёбер)*100

В данном случае: ((16 - 3  - 0) + (60 - 6 - 12))/(60+16) = 72

То есть на 72 % похожи.

Теперь на примере 2 графов из предыдущей статьи. Были такие графы:

Построили новый, получили такой.

 

Если провести расчет описанный выше для добавленных узлов здесь, то получится, что для преобразования шаблона в граф, нужно в шаблоне объединить узлы 4,5 и 6,9, что правильно. 2 графа похожи на 83%.

Данный метод не универсален, на мелких графах (менее 6 узлов) может давать ошибки. Так как знания математического аппарата теории графов недостаточно для обоснования, либо опровержения алгоритма, то, дать гарантий на то, что будет 100% работать на больших графах тоже нельзя. Скорее всего, есть какие-нибудь контрпримеры. Пока такого не встречал.

11

См. также

Специальные предложения

Избранное Подписка Сортировка: Древо
В этой теме еще нет сообщений.
Оставьте свое сообщение