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

25.04.19

Разработка - Математика и алгоритмы

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

Вступление

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

Для начала наложу ограничения

- Ячейки таблицы могут соприкасаться друг с другом только под углом либо 180, либо 90 градусов.

- Вся таблица - прямоугольник

Теперь нужно разбить задачу на 2 подзадачи. Это представление в виде графа для области в макете (далее шаблон) и для html. 

Представление в виде графа для шаблона

Блоком назову ячейку таблицы.

Тут идея проста. Сначала нужно пронумеровать блоки, потом записать какой блок, с каким граничит, таким образом и получается граф.

Идём циклом верх-низ, лево-право. Рассматриваем 4 ячейки. Х текущий, У текущий, Х+1 и У+1. Соответсвенно, если ячейки находятся рядом, то границы ячеек обозначены линиями, а так как углы либо 180, либо 90 градусов, то возможно всего 7 вариантов расположения линий внутри 4 ячеек. Ниже буду ссылаться на эту картинку, как перекрестие имеет тип 2, к примеру

Углы назову ЯЛВ, ЯПВ,ЯЛН,ЯПН (ячейка лево-верх и т.д).

Теперь нужно зарегистрировать ЯЛВ, ЯПВ и т.д. и запомнить х,у самого перекрестия. Последовательно надо нумировать только верхние блоки. Это связано с нюансом нумерации. Это очень важно для последующего сравнения графов. Если сразу нумировать все блоки и связывать с соседними, то потом с html нельзя сравнить, из-за особенностей тегов tr и td. Но если сравнивать область макета с областью макета, то данный нюанс не важен.

Блок регистрируем записью в ТЗ. Записываем стандартные координаты типа лево, право, низ, верх.

Пример. 

Беру такую таблицу.

Рассматриваю по 4 ячейки. Первое перекрестие имеет тип №5. Рассмотрим ЯЛВ. Смотрим в таблице блоков, есть ли блок, с которыми пересекается данная  ячейка. Таких нет, значит добавляем. То же самое делаем с ЯПВ. ЯПН не регистрируем, так как только верхние нужны. Рассмотрим ЯЛН. Видим, что границы нет, значит данная ячейка однозначно принадлежит блоку №1. Значит увеличиваем нижнюю координату блока №1 в таблице блоков. Также регистрируется местоположение самого перекрестия.

Второе перекрестие - тип №6. Рассмотрим ЯЛВ. Видно что координаты этой ячейки пересекаются с блоком №2 из таблицы блоков, поэтому новый не заводим, а ЯПВ и ЯПН объединяем и регистрируем блок №3. Регистрируем само перекрестие. И т.д., самый нижний блок регистрируется, когда нижняя граница всей таблицы попадает в середину рассматриваемых 4 ячеек. 

В итоге получается такая нумерация

Блоки пронумеровали, знаем их местоположения, знаем местоположения перекрестий, тогда можно легко запросом получить связи блока один с другим. Ниже расположен код с этим запросом.

Функция РазобратьТаблицу_Область(Макет,Область)
	ЯчейкаУ = Область.Верх;
	КонецУ = Область.Низ;
	КонецХ = Область.Право;
	
	СтруктураБлоков = новый ТаблицаЗначений;
	СтруктураБлоков.Колонки.Добавить("Лево",новый ОписаниеТипов("число"));
	СтруктураБлоков.Колонки.Добавить("Право",новый ОписаниеТипов("число"));
	СтруктураБлоков.Колонки.Добавить("Низ",новый ОписаниеТипов("число"));
	СтруктураБлоков.Колонки.Добавить("Верх",новый ОписаниеТипов("число"));
	СтруктураБлоков.Колонки.Добавить("РазмерХ",новый ОписаниеТипов("число"));
	СтруктураБлоков.Колонки.Добавить("РазмерУ",новый ОписаниеТипов("число"));
	СтруктураБлоков.Колонки.Добавить("Индекс",новый ОписаниеТипов("число"));
	
	МассивПерекрестий = новый ТаблицаЗначений;
	МассивПерекрестий.Колонки.Добавить("ЯчейкаХ",новый ОписаниеТипов("число"));
	МассивПерекрестий.Колонки.Добавить("ЯчейкаУ",новый ОписаниеТипов("число"));
	МассивПерекрестий.Колонки.Добавить("Индекс",новый ОписаниеТипов("число"));
	
	Пока ЯчейкаУ <= КонецУ цикл
		ЯчейкаХ  = Область.Лево;
		Пока  ЯчейкаХ < КонецХ цикл
			//берем 4 ячйки
			ЯЛВ = Макет.область(ЯчейкаУ,ЯчейкаХ);
			ЯПВ = Макет.область(ЯчейкаУ,ЯчейкаХ+1);
			ЯЛН = Макет.область(ЯчейкаУ+1,ЯчейкаХ);
			ЯПН = Макет.область(ЯчейкаУ+1,ЯчейкаХ+1);
			//смотрим, если у них одно имя, значит принадлежит одному блоку
			//смотрим внутренний крест, есть 7 ситуаций, когда можно сказать, что это разные блоки
			//|		_|_   _ _   _|_   |_    _|   	_ _
			//|      | 		          |  	 | 	 	 |
			//проверим данные ситуации
			//пуста когда это обеъдинение, либо нет границ
			ЛеваяПоловинаПуста = ЯЛВ.имя = ЯЛН.имя или (ЯЛВ.ГраницаСнизу.ТипЛинии = ТипЛинииЯчейкиТабличногоДокумента.НетЛинии и ЯЛН.ГраницаСверху.ТипЛинии = ТипЛинииЯчейкиТабличногоДокумента.НетЛинии);
			ПраваяПоловинаПуста = ЯПВ.имя = ЯПН.имя или (ЯПВ.ГраницаСнизу.ТипЛинии = ТипЛинииЯчейкиТабличногоДокумента.НетЛинии и ЯПН.ГраницаСверху.ТипЛинии = ТипЛинииЯчейкиТабличногоДокумента.НетЛинии);
			ВерхПуст = ЯПВ.имя = ЯЛВ.имя или (ЯПВ.ГраницаСлева.ТипЛинии = ТипЛинииЯчейкиТабличногоДокумента.НетЛинии и ЯЛВ.ГраницаСправа.ТипЛинии = ТипЛинииЯчейкиТабличногоДокумента.НетЛинии);
			НизПуст = ЯПН.имя = ЯЛН.имя или (ЯПН.ГраницаСлева.ТипЛинии = ТипЛинииЯчейкиТабличногоДокумента.НетЛинии и ЯЛН.ГраницаСправа.ТипЛинии = ТипЛинииЯчейкиТабличногоДокумента.НетЛинии);	
			Если ЛеваяПоловинаПуста и ПраваяПоловинаПуста и не ВерхПуст и не НизПуст тогда
				//1
				РезультатЯЛВ = НайтиБлокПоРазмеру(СтруктураБлоков,ЯЛВ);
				РезультатЯПВ = НайтиБлокПоРазмеру(СтруктураБлоков,ЯПВ);
				ДобавитьБлокВниз(РезультатЯЛВ,ЯЛН); 
				ДобавитьБлокВниз(РезультатЯПВ,ЯПН);
				ДобавитьВМассивПерекрестий(МассивПерекрестий,ЯчейкаХ,ЯчейкаУ,КонецУ);
			ИначеЕсли  не ЛеваяПоловинаПуста и не ПраваяПоловинаПуста и не ВерхПуст и не НизПуст тогда
				//2
				РезультатЯЛВ = НайтиБлокПоРазмеру(СтруктураБлоков,ЯЛВ);
				РезультатЯПВ = НайтиБлокПоРазмеру(СтруктураБлоков,ЯПВ);
				ДобавитьВМассивПерекрестий(МассивПерекрестий,ЯчейкаХ,ЯчейкаУ,КонецУ);
			ИначеЕсли  не ЛеваяПоловинаПуста и не ПраваяПоловинаПуста и ВерхПуст и НизПуст тогда
				//3
				РезультатЯЛВ = НайтиБлокПоРазмеру(СтруктураБлоков,ЯЛВ);
				ДобавитьБлокВправо(РезультатЯЛВ,ЯПВ); 
				ДобавитьВМассивПерекрестий(МассивПерекрестий,ЯчейкаХ,ЯчейкаУ,КонецУ);
			ИначеЕсли  не ЛеваяПоловинаПуста и не ПраваяПоловинаПуста и не ВерхПуст и НизПуст тогда
				//4
				РезультатЯЛВ = НайтиБлокПоРазмеру(СтруктураБлоков,ЯЛВ);
				РезультатЯПВ =НайтиБлокПоРазмеру(СтруктураБлоков,ЯПВ);
				ДобавитьВМассивПерекрестий(МассивПерекрестий,ЯчейкаХ,ЯчейкаУ,КонецУ);
			ИначеЕсли   ЛеваяПоловинаПуста и не ПраваяПоловинаПуста и не ВерхПуст и не НизПуст тогда
				//5
				РезультатЯПВ = НайтиБлокПоРазмеру(СтруктураБлоков,ЯПВ);
				РезультатЯЛВ = НайтиБлокПоРазмеру(СтруктураБлоков,ЯЛВ);
				ДобавитьВМассивПерекрестий(МассивПерекрестий,ЯчейкаХ,ЯчейкаУ,КонецУ);
				ДобавитьБлокВниз(РезультатЯЛВ,ЯЛН);				
			ИначеЕсли   не ЛеваяПоловинаПуста и  ПраваяПоловинаПуста и не ВерхПуст и не НизПуст тогда
				//6
				РезультатЯЛВ = НайтиБлокПоРазмеру(СтруктураБлоков,ЯЛВ);
				РезультатЯПВ = НайтиБлокПоРазмеру(СтруктураБлоков,ЯПВ);
				ДобавитьБлокВниз(РезультатЯПВ,ЯПН);				
				ДобавитьВМассивПерекрестий(МассивПерекрестий,ЯчейкаХ,ЯчейкаУ,КонецУ);
			ИначеЕсли   не ЛеваяПоловинаПуста и не ПраваяПоловинаПуста и  ВерхПуст и не НизПуст тогда
				//7
				РезультатЯЛВ = НайтиБлокПоРазмеру(СтруктураБлоков,ЯЛВ);
				ДобавитьБлокВправо(РезультатЯЛВ,ЯПВ);				
				ДобавитьВМассивПерекрестий(МассивПерекрестий,ЯчейкаХ,ЯчейкаУ,КонецУ);
			ИначеЕсли ЛеваяПоловинаПуста и  ПраваяПоловинаПуста и  ВерхПуст и  НизПуст тогда
				//8 нет перекрестий, соединяем все блоки
				РезультатЯЛВ = НайтиБлокПоРазмеру(СтруктураБлоков,ЯЛВ);
				если ЯЛВ.имя<>ЯПВ.имя тогда
					ДобавитьБлокВправо(РезультатЯЛВ,ЯПВ);				
				КонецЕсли;
				если ЯЛВ.имя<>ЯЛН.имя тогда
					ДобавитьБлокВниз(РезультатЯЛВ,ЯЛН);				
				КонецЕсли;
				если ЯЛН.имя<>ЯПН.имя тогда
					РезультатЯЛН = НайтиБлокПоРазмеру(СтруктураБлоков,ЯЛН);
					ДобавитьБлокВправо(РезультатЯЛН,ЯПН);				
				КонецЕсли;
			КонецЕсли;
			//нужно когда ячейка объединена
			Скачок = мин((ЯПВ.Право-ЯчейкаХ),(ЯПН.Право-ЯчейкаХ));
			Скачок = макс(Скачок,1);
			ЯчейкаХ = ЯчейкаХ + Скачок;			
		КонецЦикла;		
		ЯчейкаУ = ЯчейкаУ + 1;
	КонецЦикла;
	возврат СоздатьСписокСмежности(МассивПерекрестий,СтруктураБлоков);	
КонецФункции

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

&НаСервере
Процедура ДобавитьБлокВниз(Результат,Блок)
	//увеличивает нижнюю границу блока
	если Результат.Найденная.Низ < Блок.Низ тогда
		Результат.Найденная.Низ = Блок.Низ;
	КонецЕсли;				
КонецПроцедуры	

&НаСервере
Процедура ДобавитьБлокВправо(Результат,Блок)
	//увеличивает правую границу блока
	если Результат.Найденная.право < Блок.право тогда
		Результат.Найденная.право = Блок.право;
	КонецЕсли;				
КонецПроцедуры

&НаСервере
Процедура СвязатьБлоки(СвязьБлоков,Блоки)
	//создаёт связи каждого блока со всеми остальными из массива блоков
	Для инт = 0 по Блоки.Количество()-1 цикл
		Стр1 = Блоки[инт];
		СтрокаТАблицы1 = СвязьБлоков.Найти(Стр1,"Узел");
		Если СтрокаТАблицы1 = Неопределено тогда
			СтрокаТАблицы1 = СвязьБлоков.Добавить();
			СтрокаТАблицы1.Узел = стр1;
		КонецЕсли;
		мас1 = СтрокаТАблицы1.Связи;
		Если  мас1= Неопределено тогда
			мас1 = новый СписокЗначений
		КонецЕсли;
		Для йцу=инт+1 по Блоки.Количество()-1 цикл
			Стр2 = Блоки[йцу];
			СтрокаТАблицы2 = СвязьБлоков.Найти(Стр2,"Узел");
			Если СтрокаТАблицы2 = Неопределено тогда
				СтрокаТАблицы2 = СвязьБлоков.Добавить();
				СтрокаТАблицы2.Узел = стр2;
			КонецЕсли;
			мас2 = СтрокаТАблицы2.Связи;
			Если  мас2= Неопределено тогда
				мас2 = новый СписокЗначений
			КонецЕсли; 
			Если мас1.НайтиПоЗначению(стр2) = Неопределено тогда
				мас1.Добавить(стр2);
			КонецЕсли;
			Если мас2.НайтиПоЗначению(стр1) = Неопределено тогда
				мас2.Добавить(стр1);
			КонецЕсли;
			СтрокаТАблицы2.Связи = мас2;	
		КонецЦикла;		
		СтрокаТАблицы1.Связи = мас1;	
	КонецЦикла;			
КонецПроцедуры

процедура ДобавитьВМассивПерекрестий(МассивПерекрестий,ЯчейкаХ,ЯчейкаУ,КонецУ)
	//добавляет перекрестие для дальнейшей обработки
	если ЯчейкаУ < КонецУ тогда
		Струк = новый Структура("ЯчейкаХ,ЯчейкаУ,Индекс,Тип",ЯчейкаХ,ЯчейкаУ,МассивПерекрестий.Количество()+1);
		ЗаполнитьЗначенияСвойств(МассивПерекрестий.Добавить(),Струк);
	КонецЕсли;	
КонецПроцедуры

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

Теперь поясню зачем нужны размеры ячеек и атрибуты узлов. Рассмотрю 2 таблицы.

Вполне очевидно, что структура у них одинакова. Список смежности у 1го ({2,3},{1,3},{1,2}). У второго такой же. Но они явно отличаются как таблицы. Для выделение таких ситуаций как раз и запоминаю размеры блоков, потом их можно сравнить и выделить различия. Также в атрибуты можно записать любые значение, типа текстового содержания текущего блока и прочее.

Пример. Возьму простую таблицу

 

Список смежности и граф для неё 

({1,4}                                  
 {0,2,5}
 {1,3,5}
 {2,6}
 {0,5,7}
 {1,2,4,6,8}
 {3,5,9}
 {4,8,10}
 {5,7,9,11,12}
 {6,8,13}
 {7,11}
 {8,10,12}
 {8,11,13}
 {9,12})

 

Представление в виде графа для html

Тут всё гораздо проще. Формируем структуру блоков, сохраняем массив перекрестий как в первом варианте и вызываю функцию для создания списка смежности.

Я понимаю, что таблицу в html можно написать по разному, но я сталкивался конкретно с тегами tr, td, под них код и написан. Особо сложного тут ничего нет, поэтому просто приведу код, без особых пояснений.

&НаСервере
процедура РазобратьТаблицу_Рекурсия(ДочерниеУзлы,СтруктураБлоков,МассивПерекрестий,ТекХ,ТекУ)
	Для каждого узел из ДочерниеУзлы цикл
		если узел.ИмяУзла = "tr" тогда
			РазобратьТаблицу_Рекурсия(узел.ДочерниеУзлы,СтруктураБлоков,МассивПерекрестий,ТекХ,ТекУ);
			ТекУ = ТекУ + 1;
			ТекХ = 1;
			
			найд = СтруктураБлоков.НайтиСтроки(новый Структура("Закрыт", ложь));
			//Если на данном этапе у незакрытых ячеек одинаковые нижние границы, значит закрываем их.
			МаксНиз = Неопределено;
			МинНиз = Неопределено;
			Для каждого Возможно из найд цикл
				МаксНиз = ?(МаксНиз = Неопределено,Возможно.СчетчикУ, макс(МаксНиз, Возможно.СчетчикУ));
				МинНиз = ?(МинНиз = Неопределено,Возможно.СчетчикУ, мин(МинНиз, Возможно.СчетчикУ));
			КонецЦикла;
			если найд.Количество()>0 тогда
				если МаксНиз = МинНиз тогда
					Для каждого Возможно из найд цикл
						Возможно.Закрыт = истина;
					КонецЦикла;
				КонецЕсли;
			КонецЕсли;
			
		ИначеЕсли узел.ИмяУзла = "td" тогда 
			х = 1;
			у = 1;
			Для каждого ячейка из узел.Атрибуты цикл
				если ячейка.ИмяУзла = "colspan" тогда
					х = число(ячейка.ЗначениеУзла);
				ИначеЕсли ячейка.ИмяУзла = "rowspan" тогда
					у = число(ячейка.ЗначениеУзла)
				КонецЕсли;	
			КонецЦикла;
			//если на каком то из у есть блоки с разной высотой, то не так просто вычислить их реальное положение х
			//к примеру есть большой блок, 2 маленьких вертикально, снова большой.
			//первая tr дает 3 td, вторая tr - один td. И нужно понять что вторая строка находится между двумя блоками.
			//Для этого ищем первый возможный незакрытый вариант
			найд = СтруктураБлоков.НайтиСтроки(новый Структура("Закрыт", ложь));
			Для каждого Возможно из найд цикл
				Если Возможно.СчетчикУ<ТекУ  тогда
					ТекХ = Возможно.СчетчикХ; 
					Возможно.СчетчикХ = Возможно.СчетчикХ + х;
					если текх>= Возможно.право тогда
						//Если под текущим блоком располагаем ещё один, то очевидно
						//верхний блок становится закрытым
						Возможно.Закрыт = истина;
					КонецЕсли;
					Прервать;
				КонецЕсли;
			КонецЦикла;
			
			Нов = СтруктураБлоков.Добавить();
			нов.Индекс = СтруктураБлоков.Количество()-1;
			Нов.Лево = ТекХ;
			Нов.право = ТекХ + х-1;
			Нов.Низ =  ТекУ + у-1;
			Нов.Верх =ТекУ;
			Нов.Счетчику =Нов.Низ;
			Нов.СчетчикХ =Нов.Лево;
			Нов.РазмерХ = х;
			Нов.РазмерУ = у;
			
			НовПерекр = МассивПерекрестий.Добавить();
			НовПерекр.Индекс = МассивПерекрестий.Количество();
			НовПерекр.ЯчейкаХ = Нов.право;
			НовПерекр.ЯчейкаУ = Нов.Низ;
			НовПерекр = МассивПерекрестий.Добавить();
			НовПерекр.Индекс = МассивПерекрестий.Количество();
			НовПерекр.ЯчейкаХ = Нов.право;
			НовПерекр.ЯчейкаУ = Нов.Верх;
			НовПерекр = МассивПерекрестий.Добавить();
			НовПерекр.Индекс = МассивПерекрестий.Количество();
			НовПерекр.ЯчейкаХ = Нов.ЛЕво;
			НовПерекр.ЯчейкаУ = Нов.Низ;
			НовПерекр = МассивПерекрестий.Добавить();
			НовПерекр.Индекс = МассивПерекрестий.Количество();
			НовПерекр.ЯчейкаХ = Нов.Лево;
			НовПерекр.ЯчейкаУ = Нов.Низ;
			
			ТекХ = Нов.право + 1;
		КонецЕсли;
	КонецЦикла;
КонецПроцедуры

&НаСервере
функция РазобратьТаблицу_html(путь)
	СтруктураБлоков = новый ТаблицаЗначений;
	СтруктураБлоков.Колонки.Добавить("Лево",новый ОписаниеТипов("число"));
	СтруктураБлоков.Колонки.Добавить("Право",новый ОписаниеТипов("число"));
	СтруктураБлоков.Колонки.Добавить("Низ",новый ОписаниеТипов("число"));
	СтруктураБлоков.Колонки.Добавить("Верх",новый ОписаниеТипов("число"));
	СтруктураБлоков.Колонки.Добавить("РазмерХ",новый ОписаниеТипов("число"));
	СтруктураБлоков.Колонки.Добавить("РазмерУ",новый ОписаниеТипов("число"));
	СтруктураБлоков.Колонки.Добавить("Индекс",новый ОписаниеТипов("число"));
	СтруктураБлоков.Колонки.Добавить("СчетчикУ",новый ОписаниеТипов("число"));
	СтруктураБлоков.Колонки.Добавить("СчетчикХ",новый ОписаниеТипов("число"));
	СтруктураБлоков.Колонки.Добавить("Закрыт",новый ОписаниеТипов("Булево"));
	
	СвязьБлоков = новый ТаблицаЗначений;  
	СвязьБлоков.Колонки.Добавить("Узел");
	СвязьБлоков.Колонки.Добавить("Связи");
	
	МассивПерекрестий = новый ТаблицаЗначений;
	МассивПерекрестий.Колонки.Добавить("ЯчейкаХ",новый ОписаниеТипов("число"));
	МассивПерекрестий.Колонки.Добавить("ЯчейкаУ",новый ОписаниеТипов("число"));
	МассивПерекрестий.Колонки.Добавить("Индекс",новый ОписаниеТипов("число"));
	МассивПерекрестий.Колонки.Добавить("Тип",новый ОписаниеТипов("число"));
	
	Чтение = Новый ЧтениеHtml;
	Чтение.ОткрытьФайл(путь);
	Построитель = Новый ПостроительDOM;                                            
	Документ = Построитель.Прочитать(Чтение);
	Для каждого стр из Документ.Тело.ДочерниеУзлы цикл
		Если стр.ИмяУзла = "table" тогда
			РазобратьТаблицу_Рекурсия(стр.ДочерниеУзлы,СтруктураБлоков,МассивПерекрестий,1,1);
		КонецЕсли;
	КонецЦикла;
	возврат СоздатьСписокСмежности(МассивПерекрестий,СтруктураБлоков);
КонецФункции

Теперь конкретный пример. Есть такие html таблица и шаблон.

У них получаются следующие графы и списки смежности

( {1,3,4}
 {0,2,3}
 {1,3,6}
 {0,1,2,5}
 {0,5,7}
 {3,4,6,7,8,11}
 {2,5,8,9,10}
 {4,5,11,13,15}
 {5,6,9,11,12,13,14,15}
 {6,8,10,12}
 {6,9,12,14,15}
 {5,7,8,13}
 {8,9,10,14}
 {7,8,11,15}
 {8,10,12,15}
 {7,8,10,13,14})

 

 

 

 

 

 

({1,3,4,5}
 {0,2,3}
 {1,3,7}
 {0,1,2,6}
 {0,5,8}
 {0,4,6,8}
 {3,5,7,9}
 {2,6,10,11,12}
 {4,5,9,13,15,17}
 {6,8,10,13}
 {7,9,11,13,14,15,16,17}
 {7,10,12,14}
 {7,11,14,16,17}
 {8,9,10,15}
 {10,11,12,16}
 {8,10,13,17}
 {10,12,14,17}
 {8,10,12,15,16})

 

 

 

 

 

Остаётся сравнить эти 2 графа и выяснить насколько они похожи. Для очень умных, которые скажут, что это равносильно решению задачи изоморфности графа, что это, скорее всего, NP полная задача, решается перебором, либо генетическими алгоритмами, которые вероятностны, и прочее, отвечу - да, это справедливо для общего случая, но тут случай очень даже частный, поэтому полного перебора не нужно. Алгоритм достаточно быстр, достаточно точен. Явных косяков в сравнении не сильно различных графов не заметил, так как рассчитывал параллельно вручную и сравнивал результаты. Сильно различные графы вручную тяжело сравнить, поэтому не делал. Сам алгоритм и результаты опишу в следующей статье.

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

См. также

Закрытие периода Инструменты администратора БД Корректировка данных Бухгалтер Пользователь Бухгалтерский учет 1С:Бухгалтерия 3.0 Россия Бухгалтерский учет Платные (руб)

Расширение «Оперативное проведение» в 4 раза уменьшает время проведения документов и закрытия месяца. Является комплексным решением проблем 62 и 60 счетов. Оптимизирует проведение при включенной функциональной опции «Раздельный учет НДС». Используется в более 10 организациях уже 2 года. Совместимо с конфигурацией Бухгалтерия 3.0 (+КОРП).

14400 руб.

29.04.2020    31724    97    151    

71

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

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

3600 руб.

10.02.2017    109773    657    173    

696

Корректировка данных Зарплата Бухгалтер Пользователь Платформа 1С v8.3 Бухгалтерский учет 1С:Бухгалтерия 3.0 Россия Бухгалтерский учет Платные (руб)

Внешняя обработка предназначена для исправления самых различных ошибок, возникших по самым разным причинам. Общее проявление этих ошибок видно в различии данных между: проводками и различными отчетами по НДФЛ, заполнении ведомостей на выдачу зарплаты, неверным расчетом НДФЛ при начислении ЗП и т.д.

3600 руб.

09.02.2024    1532    11    5    

14

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

Вы наконец разобрались с закрытием месяцев и пора начать контролировать сроки оплаты поставщикам и задолженности клиентов, но в базе расчеты не идут из-за развернутого сальдо? Не беда, есть решение!

7200 руб.

02.11.2020    7168    5    0    

8

Корректировка данных Зарплата Бухгалтер Платформа 1С v8.3 Сложные периодические расчеты 1С:Зарплата и кадры бюджетного учреждения 1С:Зарплата и Управление Персоналом 3.x Россия Бухгалтерский учет НДФЛ Платные (руб)

Обработка исправляет технические ошибки по НДФЛ, взаиморасчетам с сотрудниками в 1С:ЗУП (1С:ЗКГУ) на начало года. Фактически все ошибки, которые проявляются в ведомостях на выплату, расчетных листках, при заполнении ведомостей на выплату и отчетах 6-НДФЛ и т.д. нужно начинать исправлять с начала расчетного года. Это позволит быть уверенными, что после завершения расчетов предыдущего года, начали работать с «чистого листа» без ошибочных остатков.

4800 руб.

06.10.2023    3894    35    17    

43

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

Закрытие месяца - важный процесс в современных конфигурациях, таких как УТ 11.4, УТ 11.5, КА 2.4, КА 2.5 ERP 2.4,ERP 2.5, КА 2 Казахстан, УТ 3 Казахстан регламентные операции влияют на расчет себестоимости, и ошибки в данном расчете не дают картины деятельности организации.

4800 руб.

27.10.2021    23648    240    35    

77

Работа с интерфейсом Программист Платформа 1С v8.3 Конфигурации 1cv8 1С:ERP Управление предприятием 2 Платные (руб)

Обработка предназначена для создания и управления дашбордами.

2400 руб.

29.06.2020    18414    26    6    

40
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. bulpi 217 26.04.19 23:47 Сейчас в теме
Прикольно. Столько труда, и для чего ? Я бы просто на фиг послал заказчика , исходя из соотношения Результат/Затраты. Но интересно, так что +
3. trim89 109 27.04.19 00:52 Сейчас в теме
(1) Всё делалось для разработки из этой публикации, но пока туда не прикрутил. Выхлопа нет вообще, мне просто было интересно.
🅵🅾️🆇; +1 Ответить
5. 🅵🅾️🆇 524 29.04.19 12:39 Сейчас в теме
(3) Спасибо, обязательно почитаю позже.
Тк есть желание прикрутить свой OCR: tesseract, yandex vision, google vision, efsol (abby).
И собственно будет задача перевести полученную структуру в объект 1с.
2. acanta 27.04.19 00:37 Сейчас в теме
Это очень круто. Правильно ли я понимаю, что html файл таблицу можно загрузить в 1с с тем же успехом что и excel?
4. trim89 109 27.04.19 01:08 Сейчас в теме
(2) Нет, не правильно. Стандартные таблицы с шапкой и строками можно было грузить без особых проблем и до этого. Есть куча инструментов для такого, с интерфейсом и финтифлюшками. Проблема возникает в нестандартных таблицах типа шапки счета с банковскими реквизитами. Насколько знаю, её только парсить, но если есть какие-то ошибки в структуре, то парсинг не срабатывает корректно.

Данная методика позволяет сравнить 2 таблицы, определить насколько они похожи и определить ошибки в структуре, а это значит, что можно автоматически скорректировать парсинг, что бы он был корректным. То есть, в статье про html и макеты, потому что это конкретика и у меня такая задача возникла, но, в общем и целом, не надо привязываться к html или excel, суть не в этом.
Оставьте свое сообщение