ОБ ОДНОМ ПОДХОДЕ К СОПОСТАВЛЕНИЮ ТАБЛИЦ - Студенческий научный форум

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

ОБ ОДНОМ ПОДХОДЕ К СОПОСТАВЛЕНИЮ ТАБЛИЦ

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

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

В частности, данная работа приурочена к проверке одного из заданий межрегионального дистанционного конкурса «ТРИЗформашка» [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 - множество дуг.

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

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

  • Vt - вершина таблицы,
  • Vname - вершина названия заголовка таблицы,
  • Vnum - вершина номера таблицы,
  • Vstruct - вершина структуры таблицы,
  • Vstruct_g - вершина структуры головки,
  • Vstruct_b - вершина структуры боковика,
  • Vdata - вершина данных таблицы,
  • Vg - вершина головки,
  • Vb - вершина боковика,
  • Vp - вершина прографки,
  • Vtext - текстовая вершина,

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

При этом вершин типов Vt , Vstruct , Vstruct_g , Vstruct_b , Vdata  являются промежуточными и не несут в себе никакой новой информации, но они не исключаются из сети сознательно, т.к. в дальнейшем планируется доработать алгоритм таким образом, чтобы он мог не только определять сопоставимы ли таблицы, но и оценить таблицу по сравнению с эталоном. В этой  модификации алгоритма понадобятся уже все типы вершин.

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

  • Ea_part_of - связь типа часть-целое,
  • Eis_instance_of - связь класс-экземпляр,
  • Eparent - связь между вершиной головки и вершиной боковика или прографки. Направлена в сторону вершины головки. Так же в эту связь входят ребра между двумя вершинами головки смежных ярусов. В этом случае связь направлена в сторону вершины с меньшим номером яруса.
  • Ename - именованные связи, которые включают в себя:
  • o Evalue - связь «значение вершины». Связь между текстовой вершиной и вершиной любого другого типа. Направлена в сторону текстовой вершины.
  • o Emeasure - связь «единица измерения»

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

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

|Vt| = 1

|Vname| ≤ 1

|Vnumber| ≤ 1

|Vstruct| = 1

|Vdata| = 1

|Vstruct_g| = 1

|Vstruct_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 (P1) <> type (P2))

              return false

  if (

              return Text(P1) = = Text(P2)

  foreach ( )

  begin

              A=start(R1)

              foreach ( )

              begin

                          B=start(R2)

                          if (not Compare(A,B))

                                      return false

              end

  end

 

  bool result = false

  foreach ( )

  begin

              A=start(R1)

              if (Compare(A,P2))

              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).

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

Просмотров работы: 3