III Международная студенческая научная конференция Студенческий научный форум - 2011

Проблема сравнения двух таблиц в наше время является достаточно актуальной. Об этом свидетельствует и тот факт, что существуют различные разработки, в том числе и коммерческие, которые позволяют сравнить две таблицы. Но на данный момент все существующие проекты сравнивают таблицы только на полное равенство (т.е. определяется, является ли одна таблица копией другой) и позволяют определить, в каких ячейках данные одинаковые, а в каких данные изменились.

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

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

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

Для проведения сравнения необходимо разметить эталонную таблицу. Предлагается выделить ячейки двух типов: ячейки-заголовки и ячейки с данными. Ячейки-заголовки могут быть разных уровней, при этом столбцы и строки внутри заголовков одного уровня можно менять местами. Можно указать, каким может быть текст в ячейке-заголовке: точно такой же, как в правильной таблице, предложить несколько вариантов текста или же допустить произвольный текст в данной ячейке.

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

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

Чтобы разработать более эффективный вариант сравнения, предлагается сравнивать ячейку таблицы-ответа с соответствующими ячейками в сгенерированных эталонных таблицах и затем удалять из списка эталонных таблиц те, которые не прошли это сравнения. В этом случае важную роль будет играть порядок сравнения ячеек таблиц. Предлагается рассмотреть следующие варианты: сначала сравнивать по строкам, затем по столбцам или наоборот; сначала сравнивать структуру таблицы (т.е. заголовки), а затем переходить к сравнению данных или сначала сравнить данные, а потом структуру таблицы; сравнивать данные, но с учетом структуры таблицы, т.е. не только данные в соответствующих ячейках должны быть одинаковыми, но и заголовки по строкам и столбцам тоже должны совпадать.

Выделить какой-либо из этих вариантов, как более эффективный нельзя, поэтому реализованы будут все, с возможностью предоставления выбора варианта сравнения для использования.