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

Вступление

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

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

— Ячейки таблицы могут соприкасаться друг с другом только под углом либо 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 полная задача, решается перебором, либо генетическими алгоритмами, которые вероятностны, и прочее, отвечу — да, это справедливо для общего случая, но тут случай очень даже частный, поэтому полного перебора не нужно. Алгоритм достаточно быстр, достаточно точен. Явных косяков в сравнении не сильно различных графов не заметил, так как рассчитывал параллельно вручную и сравнивал результаты. Сильно различные графы вручную тяжело сравнить, поэтому не делал. Сам алгоритм и результаты опишу в следующей статье.