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

Вступление

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

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

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