Transcript waap134-shiono

XML Representation Based on
Octa-grid for Table Processing
○Yasunori Shiono (Toyo Univ.)
Tomokazu Arita (Obirin Univ.)
Tadaaki Kirishima (Toyo Univ.)
Tomoe Motohashi (Kanto Gakuin Univ.)
Takeo Yaku (Nihon Univ.)
Kensei Tsuchida (Toyo Univ.)
Contents
1. Introduction
2. Preliminaries
Tabular Diagram, Octa-grid
3. Data Structure and XML Representation
for Tables
H10-Code list, H10-Code
4. Normalizing
5. Table Processing System Based on
H10-Code List and H10-Code
RD Table Editor
6. Conclusion
2
1. Introduction
1.1 Background
1.2 Motivation
1.3 Purpose
1.4 Results
3
1.1 Background
Various tables have been used as tools
for visualizing and arranging information
Existent table processing systems

MS-Excel, MS-Word, OpenOffice.org,
TeX, HTML, etc.
4
1.2 Motivation
Existent table processing systems have
problems



Inability to represent various tables
Editing operations often produce unexpected
results
Table data structures sometimes lead to
inefficient editing operations
5
1.2 Motivation (cont.)
Example of unexpected results
Unexpected result (WORD 2003) Expected result
6
1.3 Purpose
To achieve table processing system based
on octa-grid to solve these problems

To develop internal and external data
representation for XML
 Implement XML processing module

To develop efficient editing algorithms
 Do analysis based on formal method
 Consider user expectations
7
1.4 Results
Defined



H10-Code list as list data structure
H10-Code as XML representation
XSLT stylesheet to browse H10-Code
Developed normalizing algorithm
Implemented


XML processing module
Normalizing algorithm
8
2. Preliminaries
2.1 Tabular Diagram
2.2 Octa-grid
9
2.1 Tabular Diagram
Tabular diagrams are formal definitions for
general tables
Table like tabular diagram D1 is
represented as tabular diagram D1p
10
2.1 Tabular Diagram (cont.)
: perimeter cell (width=0 or height=0)
Let us consider tabular
diagrams with perimeter cells
11
2.2 Octa-grid
Octa-grids are graph representations for
general tables
Octa-grids represent tabular diagrams
with perimeter cells
Vd
d
c
Tabular diagram
with perimeter cells
d
Vc
Octa-grid
12
2.2 Octa-grid (cont.)
Vd
d
c
Tabular diagram
with perimeter cells
d
Octa-grid
Vc
Cells correspond to nodes
Connections between cells are defined by edges
Nodes in octa-grids have at most 8 degrees
Octa-grids can represent all slice and non-slice
structure tables
13
3. Data Structure and XML
Representation for Tables
3.1 H10-Code List
3.2 H10-Code
14
3.1 H10-Code List
H10-Code list is list data structure based
on octa-grids for


General tables
XML representation that can be displayed
using a common web browser
Each node corresponds to node of octagrid
15
3.1 H10-Code List (cont.)
Node of H10-Code list has following
information:






Node ID
Cell type
8 pointers that represent 8 edges
4 positions for 4 walls of cell
Content in table cell
Information for transforming documents (H10Code) into HTML documents with XSLT
stylesheet
16
3.1 H10-Code List (cont.)
Illustration of a node of H10-Code list
17
3.1 H10-Code List (cont.)
Octa-grid and its corresponding H10-Code list
Octa-grid
H10-Code list
18
3.1 H10-Code List (cont.)
Using H10-Code list makes use of
computers to process all slice and non-slice
structure tables possible.
Computational complexity of editing
operations can be kept small


E.g, moving a ruled line
This is because maximum degree of each node
is 8 at most
19
3.2 H10-Code
H10-Code is XML representation for H10Code list
By applying XSLT stylesheet to H10-Code,
code can be displayed on common Web
browser
All slice and non-slice structure tables can
be browsed
H10-Code can be converted to H10-Code
list and vice versa

H10-Code can be regarded as file formats of
H10-Code list
20
3.2 H10-Code (cont.)
Element structure of H10-Code
corresponding to table
21
3.2 H10-Code (cont.)
Part of H10-Code document
・
・
・
・
・
・
22
3.2 H10-Code (cont.)
Part of XSLT stylesheet
<?xml version="1.0" encoding="Shift_JIS" ?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="html" encoding="Shift_JIS" />
<xsl:template match="/">
<html>
<head>
</head>
<xsl:apply-templates select=“H10-Code" />
・
・
・
<xsl:if test="@cell_type
= 1">
<xsl:if test="@d_row_s = 1">
<tr>
<td>
<xsl:attribute name=“rowspan">
<xsl:value-of select="@rowspan"/>
</xsl:stylesheet>
・
・
・
23
3.2 H10-Code (cont.)
Result of displaying with IE
24
3.2 H10-Code (cont.)
Another result of displaying with IE
25
3.2 H10-Code (cont.)
By using H10-Code we can save, exchange
and browse H10-Code lists accurately
It is easy to obtain position information,
and to represent tables with slice and nonslice structure
26
4. Normalize
Delete unnecessary perimeter cells
Structure of a normalized octa-grid that
corresponds to one table structure is
unique
27
4. Normalize
Input
Output
28
4. Normalize
29
4. Normalize
C1
30
4. Normalize
C1
31
4. Normalize
C1
32
4. Normalize
C1
C2
33
4. Normalize
C1
C3
C2
34
4. Normalize
C1
C3
C2
35
4. Normalize
C1
C3
C2
36
4. Normalize
C1
C3
C2
37
4. Normalize
C1
C3
C2
38
4. Normalize
C1
C3
C2
39
4. Normalize
C1
C3
C2
40
4. Normalize
C1
C3
C2
41
4. Normalize
C1
C2
42
4. Normalize
C2
C1
43
4. Normalize
C1
C3
C2
44
4. Normalize
C1
C2
45
4. Normalize
C1
C2
46
4. Normalize
C1
47
4. Normalize
C1
48
4. Normalize
C1
49
4. Normalize
50
5. Table Processing System Based
on H10-Code List and H10-Code
5.1 System structure
5.2 RD Table Editor
51
5.1 System structure
52
5.2 RD Table Editor
Internal data structure is H10-Code list
Edits a table by editing algorithms for
octa-grid
Interactive converter of H10-Code list
and H10-Code


Saves H10-Code lists as H10-Code
Loads H10-Code
53
5.2 RD Table Editor(cont.)
DEMO
1.
2.
3.
4.
5.
6.
Load sample H10-Code
Insert a column
Save the table as H10-Code
Browse the H10-Code
Unify cells
Normalize
54
6. Conclusion
H10-Code list was proposed as list data
structure
H10-Code was proposed as XML
representation
Nomalizing algorithm
We are developing a table processing
system based on H10-Code list and
H10-Code
55
6. Conclusion (cont.)
Future work



Other efficient algorithms for editing tables
To implement these algorithms
Add-on for OpenOffice.org
56