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

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

Настоящий проект посвящен вопросу семантического сопоставления информации, представленной в форме таблиц. Объем информации, хранящейся в табличной форме, огромен. Это делает задачу семантического сопоставления информации, представленной в табличной форме, весьма актуальной.

В частности, данная работа приурочена к проверке одного из заданий межрегионального дистанционного конкурса «ТРИЗформашка» [1]. Суть этого задания заключается  в том, чтобы представить в табличной форме имеющуюся в тексте задания информацию. Данная работа заключается в автоматизации проверки присланных решений. Задача проверки присланной таблицы сводится к тому, чтобы сопоставить присланную участником конкурса таблицу с одним из эталонных (правильных) решений [2, 3].

Таблицы, содержащие информацию, представленную в тексте, могут быть по-разному структурированы и относиться к разным типам таблиц. Подробнее про структуру и некоторые типы таблиц можно прочитать в [4].

Приведем пример реального задания на построение таблицы по тексту из конкурса «Тризформашка-2011».

В тексте речь идет о росте доходов Пермской приборостроительной компании от продажи своей продукции. Представьте эту информацию в виде таблицы.

В 2005 г. доход от продажи систем авиационной навигации составил 157 млн. руб.

В 2006 г. прирост дохода от продажи систем наземной навигации по сравнению с 2005 г. составил 68%.

В 2009 г. доход от продажи систем авиационной навигации составил 227 млн. руб.

В 2007 г. доход от продажи систем наземной навигации составил 234 млн. руб.

В 2008 г. прирост дохода от продажи систем морской навигации по сравнению с 2005 г. составил 144%.

В 2006 г. доход от продажи систем наземной навигации составил 183 млн. руб.

В 2007 г. доход от продажи систем авиационной навигации составил 242 млн. руб.

В 2008 г. доход от продажи систем наземной навигации составил 348 млн. руб.

В 2007 г. доход от продажи систем морской навигации составил 271 млн. руб.

В 2007 г. прирост дохода от продажи систем наземной навигации по сравнению с 2005 г. составил 115%.

В 2006 г. прирост дохода от продажи систем авиационной навигации по сравнению с 2005 г. составил 2%.

В 2009 г. доход от продажи систем наземной навигации составил 477 млн. руб.

В 2008 г. доход от продажи систем авиационной навигации составил 138 млн.руб.

В 2009 г. прирост дохода от продажи систем наземной навигации по сравнению с 2005 г. составил 338%.

В 2005 г. доход от продажи систем морской навигации составил 119 млн. руб.

В 2007 г. прирост дохода от продажи систем морской навигации по сравнению с 2005 г. составил 128%.

В 2006 г. доход от продажи систем авиационной навигации составил 160 млн. руб.

В 2008 г. снижение дохода от продажи систем авиационной навигации по сравнению с 2005 г. составило 12%.

В 2006 г. доход от продажи систем морской навигации составил 162 млн. руб.

В 2009 г. прирост дохода от продажи систем авиационной навигации по сравнению с 2005 г. составил 45%.

В 2009 г. доход от продажи систем морской навигации составил 434 млн. руб.

В 2008 г. прирост дохода от продажи систем наземной навигации по сравнению с 2005 г. составил 219%.

В 2006 г. прирост дохода от продажи систем морской навигации по сравнению с 2005 г. составил 36%.

В 2007 г. прирост дохода от продажи систем авиационной навигации по сравнению с 2005 г. составил 54%.

В 2009 г. прирост дохода от продажи систем морской навигации по сравнению с 2005 г. составил 265%.

В 2005 г. доход от продажи систем наземной навигации составил 109 млн.руб. В 2008 г. доход от продажи систем морской навигации составил 290 млн.руб.

 После выполнения задания должна получиться одна из четырех представленных ниже таблиц (табл. 1‑4).

Таблица 1. Рост доходов Пермской приборостроительной компании

Год	Вид навигационных систем
	Авиационные		Наземные		Морские
	Доход, млн. руб	Прирост дохода по сравнению с 2005 г., %	Доход, млн. руб	Прирост дохода по сравнению с 2005 г., %	Доход, млн. руб	Прирост дохода по сравнению с 2005 г., %
2005	157	0	109	0	119	0
2006	160	2	183	68	162	36
2007	242	54	234	115	271	128
2008	138	-12	348	219	290	144
2009	227	45	477	338	434	265

Можно переставить местами ярусы (показатель доходности - наверх, вид навигационных систем - вниз). Но в этом случае пропадают слова «Вид навигационных систем». Чтобы их не потерять, придется вынести их в заголовок таблицы (табл. 2).

Таблица 2. Рост доходов Пермской приборостроительной компании от продажи навигационных систем разного вида

Год	Доход, млн. руб			Прирост дохода по сравнению с 2005 г., %
	Авиационные	Наземные	Морские	Авиационные	Наземные	Морские
2005	157	109	119	0	0	0
2006	160	183	162	2	68	36
2007	242	234	271	54	115	128
2008	138	348	290	- 12	219	144
2009	227	477	434	45	338	265

 

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

Таблица 3. Рост доходов Пермской приборостроительной компании

Год	Показатель доходности	Вид навигационных систем
		Авиационные	Наземные	Морские
2005	Доход, млн. руб	157	109	119
	Прирост дохода по сравнению с 2005 г., %	0	0	0
2006	Доход, млн. руб	160	183	162
	Прирост дохода по сравнению с 2005 г., %	2	68	144
2007	Доход, млн. руб	242	234	271
	Прирост дохода по сравнению с 2005 г., %	54	115	128
2008	Доход, млн. руб	138	348	290
	Прирост дохода по сравнению с 2005 г., %	-12	219	144
2009	Доход, млн. руб	227	477	434
	Прирост дохода по сравнению с 2005 г., %	45	338	265

 

Таблица 4. Рост доходов Пермской приборостроительной компании

Вид навигационных систем	Показатель доходности	Год
		2005	2006	2007	2008	2009
Авиационные	Доход, млн. руб	157	160	242	138	227
	Прирост дохода по сравнению с 2005 г., %	0	2	54	-12	45
Наземные	Доход, млн. руб	109	183	234	348	477
	Прирост дохода по сравнению с 2005 г., %	0	68	115	219	338
Морские	Доход, млн. руб	119	162	271	290	434
	Прирост дохода по сравнению с 2005 г., %	0	36	128	144	265

 

Существующие в настоящее время программы или надстройки над MS Office, например Tablediff, Excel Compare, DiffDoc, Compare Spreadsheets for Excel и др., не позволяют проводить сравнение на семантическом уровне, они проводят только синтаксическое сравнение, т.е. сравнение текста в ячейках с одинаковыми индексами [5-7]. Такие программы могут показать даже 100% различие между двумя таблицами, представляющими одну и ту же информацию (например, табл. 2 и 4).

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

Таким образом, мы приходим к необходимости разработки нового, семантического алгоритма для сравнения таблиц. Ниже представлено формальное описание модели представления таблиц и предлагаемого алгоритма сравнения.

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

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

Исходя из представленной структуры таблицы введем следующие допустимые типы вершин:

• V_t - вершина таблицы,
• V_name - вершина названия заголовка таблицы,
• V_num - вершина номера таблицы,
• V_struct - вершина структуры таблицы,
• V_{struct_g} - вершина структуры головки,
• V_{struct_b} - вершина структуры боковика,
• V_data - вершина данных таблицы,
• V_g - вершина головки,
• V_b - вершина боковика,
• V_p - вершина прографки,
• V_text - текстовая вершина,

_•·          V_class - промежуточная вершина, используется в связи is_instance_of.

При этом вершин типов V_t , V_struct , V_{struct_g} , V_{struct_b} , V_data  являются промежуточными и не несут в себе никакой новой информации, но они не исключаются из сети сознательно, т.к. в дальнейшем планируется доработать алгоритм таким образом, чтобы он мог не только определять сопоставимы ли таблицы, но и оценить таблицу по сравнению с эталоном. В этой  модификации алгоритма понадобятся уже все типы вершин.

Допустимые типы дуг:

• E_{a_part_of} - связь типа часть-целое,
• E_{is_instance_of} - связь класс-экземпляр,
• E_parent - связь между вершиной головки и вершиной боковика или прографки. Направлена в сторону вершины головки. Так же в эту связь входят ребра между двумя вершинами головки смежных ярусов. В этом случае связь направлена в сторону вершины с меньшим номером яруса.
• E_name - именованные связи, которые включают в себя:
• o E_value - связь «значение вершины». Связь между текстовой вершиной и вершиной любого другого типа. Направлена в сторону текстовой вершины.
• o E_measure - связь «единица измерения»

В представленной модели выполняются следующие соотношения:

и действуют следующие ограничения:

|V_t| = 1

|V_name| ≤ 1

|V_number| ≤ 1

|V_struct| = 1

|V_data| = 1

|V_{struct_g}| = 1

|V_{struct_b}| = 1

 

Пример сети приведен на рис. 1, 2.

Представленные сети эквивалентны, например, две таблицы представленные ниже (табл.5, 6):

Таблица 5. Обеспеченность некоторых стран нефтью и газом

Страна	Запасы		Обеспеченность запасами (лет)
	нефти (млн.т)	газа (млрд.м3)	Нефти	Газа
Австралия	213	471	9	29
Алжир	1070	2951	32	75

 

Таблица 6. Обеспеченность некоторых стран нефтью и газом

Страна	Обеспеченность запасами (лет)		Запасы
	газа	нефти	газа (млрд.м3)	нефти (млрд.т)
Алжир	75	32	2951	0,213
Австралия	29	9	471	1,07

 

Пусть  - это множество вершин достижимых из вершины v с использованием путей длины 1[8].

Две вершины графа эквивалентны , если для них выполняются следующие условия:

• 1) если , то ;
• 2) если , то
• a.
• b.

Тогда две таблицы эквивалентны друг другу, если эквивалентны вершины

Алгоритм сопоставления таблиц:

Пусть:

• Type(v) - функция, возвращающая тип вершины;
• Incoming(v) - функция, возвращающая список дуг входящих в данную вершину;
• Outcoming(v) - функция, возвращающая список дуг исходящих из данной вершины;
• Start(e) - Возвращает вершину, из которой выходит заданная дуга;
• Finish(e) - Возвращает вершину, в которую входит заданная дуга,

Алгоритм сопоставления начинает свою работу с двух вершин типа «таблица» (из эталонной сети и из сети проверяемой таблицы) - .

Верхний индекс означает принадлежность одной из сетей: 1 - эталонная сеть, 2 - сеть, проверяемой таблицы.

Тогда функцию сопоставления двух вершин можно представить следующим образом:

Boolean Compare( )

Begin

  if (type (P¹) <> type (P²))

              return false

  if (

              return Text(P¹) = = Text(P²)

  foreach ( )

  begin

              A=start(R¹)

              foreach ( )

              begin

                          B=start(R²)

                          if (not Compare(A,B))

                                      return false

              end

  end

 

  bool result = false

  foreach ( )

  begin

              A=start(R¹)

              if (Compare(A,P²))

              begin

                          result = true

                          break

              end

  end

  return result

 

Приведенная в данной работе модель не является универсальной и не описывает все возможные типы таблиц, но при необходимости она может быть расширена путем введения новых типов вершин и дуг.

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

Библиографический список

1. Межрегиональный дистанционный конкурс «ТРИЗформашка» [Электронный ресурс]. URL: http://www.trizformashka.ru/ (Дата обращения: 31.01.2012).
2. Косов В.А., Плаксин М.А. Автоматизация работ по проведению конкурса «ТРИЗформашка» // Информационные технологии в образовании XXI века: материалы всероссийской конференции. - Москва: Изд-во МИФИ, 2011. - С. 301 - 303.
3. Косов В.А., Плаксин М.А. Об автоматизации проведения конкурса «ТРИЗформашка» // Школьная информатика: матер. регион. науч.-практ. конф. - Пермь: Изд-во Перм. гос. пед. ун-т, 2011. - Ч. 2. - С. 13 - 14.
4. Плаксин М.А. Модуль  «Таблицы» «Пермской версии» начального курса информатики. //Информатика в начальной школе. 2003, №3, с.33-83.
5. Косов В.А., Анисимов А.О. Сравнение таблиц на эквивалентность // Материалы III Общероссийского студенческого научного форума 2011 (электронная конференция). [Электронный ресурс]. URL: http://rae.ru/forum2011/104/279 (Дата обращения: 18.01.201).
6. Программа Tablediff [Электронный ресурс]. URL: http://msdn.microsoft.com/ru-ru/library/ms162843.aspx (Дата обращения: 18.01.2012)
7. Программа Compare Spreadsheets for Excel [Электронный ресурс] URL: http://www.mapilab.com/ru/excel/compare_spreadsheets (Дата обращения: 18.01.2012).
8. Волченская Т.В., Князьков В.С. Введение в теорию графов. [Электронный ресурс]. URL: http://www.intuit.ru/department/algorithms/ingrth/4/ (Дата обращения: 20.01.2012).

Научный руководитель:
Кандидат ф.-м. наук, доцент кафедры МОВС М.А. Плаксин

Код для цитирования: Скопировать