KR20050071843A - Transforming tabular information for rendering on a limited-area display - Google Patents

Abstract

A system for converting table information for rendering to a terminal having a limited area display includes a network entity. The network entity includes a document converter capable of receiving an electronic document containing table information including table (s). The document converter converts the table (s) into a linearized representation of the table (s) based on the order of each table, and further based on at least one label if at least one table includes at least one label. I can convert it. More specifically, the document converter arranges the table (s) by arranging the table (s) such that each of the table (s) has a predetermined order, such as row-major order or column-major order. Can be converted). The document converter can then place each label if the table (s) includes at least one label, and then based on the arranged table (s), and additionally at least one table (s). If it contains a label, the table (s) can be linearized based on each placed label.

Description

Transforming tabular information for rendering on a limited-area display}

The present invention relates generally to a system and method for rendering table information, and more particularly to a system, method and computer for preserving memory used to transform table information for rendering on a terminal having a limited display area. It's about the program.

Companies and individuals that produce electronic documents, such as web pages, e-mail messages, word processor files, are considering a typical target platform on which electronic documents will be displayed. In general, such platforms are desktop computers that include adequately sized storage capacity, memory, bandwidth, and large (typically at least 14 inches diagonally) displays. Files created for these destination platforms often contain complex formats of information, including tables, frames, pictures and navigational aids, all of which define how the document should be rendered. .

The user may need to access the document through a medium other than the one originally designed in view of which document is to be displayed. Examples of such a medium include Internet-enabled mobile phones, Personal digital assistants (PDAs), or portable computers. Such devices have limited display area, resolution, and rendering capabilities, and complex electronic documents cannot render as originally designed or render in very slow and / or inconvenient ways. For example, a mobile phone operated by the Internet can only display a few lines of text, and the ability of such a device to render an image is limited to black and white or thumbnail-sized images, You may not be able to render any images at all. There is an extreme example of speech being limited by the display. For voice, systems such as the AT & T VoiceTM Text-to-Speech engine allow users to call electronic documents by calling a service using text-to-speech technology and dictating the contents of the document over the phone. Allow access using. While dictation is necessarily one-dimensional "rendering" of text, it cannot display the information of complex layouts embedded within a two-dimensional table.

According to the prior art, devices that cannot render such electronic documents as they were originally designed because of limited screen size, resolution and rendering capabilities, adopt liberty when asked to render such documents. In this respect, when processing characters containing tabular two-dimensional information, some devices of the prior art omit such tables. Other devices omit one or more selected columns if the table is too large to allow the table to fit within the display area of the device. Other devices also perform "rote linearization" on the table, which is a way of rendering each cell of the table independently, visiting the cells in the table in a certain order (e.g., left to right). , Or from top to bottom), typically in the natural order of the contents of these cells included in the table to perform linearization. Furthermore, other devices render only a partial "viewport" of the entire table, which in this case requires the user of the device to indicate that he or she wants to move the viewpoint within the table (e.g. using a direction key). To do). For example, the user may move the viewpoint from left to right to expose different parts of the table. While these techniques for rendering tables are sometimes appropriate, they render table information on a limited display in a way that ensures that all the table information is provided and also makes the information in the table better understood by the user who displays this information. It is desirable to design an improved system and method for transforming table information.

In view of the prior art as described above, one object of the present invention is to provide an improved system and associated terminals, methods and computer programs for converting table information comprising at least one table.

Another object of the present invention is to make the contents of the table easier and easier to understand for users who display this information, unlike the methods of the prior art, when converting a table for subsequent rendering by a terminal having a limited area display. Is to provide a way.

Yet another object of the present invention is that, unlike the prior art for rendering tables on such a terminal by localizing the labels in the table to the cells associated with each label, embodiments of the present invention provide one or more columns from the table. Select to render the entire contents of the table without truncation.

In view of the prior art as described above, embodiments of the present invention provide an improved system and associated terminal, method and computer program for transforming table information comprising at least one table. Embodiments of the present invention can convert a table to perform subsequent rendering by a terminal having a display of a limited area, in which case the contents of the table are easier for a user to display this information, unlike conventional methods. Provide it in a way that makes it easier to understand. At this time, embodiments of the present invention localize the labels in the table to cells associated with each label. Therefore, unlike the prior art for rendering tables on such a terminal, embodiments of the present invention can render the entire contents of a table without selecting and truncating one or more columns from the table. Examples perform mechanical linearization of a table by rendering each cell of the table without taking into account the natural ordering of the contents of these cells in the table, requiring the user of the device to shift the view so that only a partial view of the entire table is present. It is not rendering.

According to one embodiment of the invention, a system is provided for converting table information for rendering on a terminal having a limited area display. The system according to an embodiment of the present invention is a mobile terminal, an origin server, a proxy / gateway, a short messaging service center (SMSC), a multimedia messaging service center (MMSC), a gateway. It includes a GRPS Service Node (GGSN), a User Processor, or such network entities. The network entity includes a document converter capable of receiving an electronic document having table information including table (s). In this regard, the document converter converts the table (s) into a linearized representation based on the order of each table, and further based on at least one label if at least one table includes at least one label. I can convert it. In particular, the document converter can convert the tables by arranging the table (s) such that the table (s) have a predetermined order, such as row-major ordering or column-major ordering. There may be. The document converter then localizes each label when the table contains at least one label, linearizes the table based on the table arranged to have a predetermined order, and furthermore, the table (s) may select at least one label. If included, linearize based on each localized label.

The document converter may determine whether the terminal supports panning. Then, if the terminal does not support panning, the document converter may choose to either convert the table or deliver the electronic document without converting the table (s). Thereafter, if the selection involves converting the table, the document converter can convert this table (s).

As described below, each table is typically arranged in at least one row and at least one column. Therefore, the document converter can order the table (s) by identifying the unique order of the table (s), and if the table (s) has a unique order that is different from the predetermined order, The branches may be arranged in a predetermined order. The document converter can determine the unique order in one or more different ways. For example, the document converter may determine a characteristic vector of each cell of the table, and determine the distance between adjacent cells based on the characteristic vector of each cell. Thereafter, the document converter can determine the average distance between pairs of adjacent cells in the same row in the table and the average distance between pairs of adjacent cells in the same column in the table. Thus, the document converter can identify the unique order of the table based on the average distance.

The document converter can localize the labels in each table in a number of different ways in the same way. For example, the document converter may identify one or more span labels and / or one or more direct labels. As described below, each span label is associated with a plurality of columns or rows of the table, and a direct label is associated with a single column or row of the table. After identifying the span or direct label (s), the document converter determines the label string of each cell in the table associated with the span label and / or the direct label, and assigns each span label and each direct label to its label (s). It may be localized with respect to the color @ (s) of this referenced table, in which case each label string includes at least one of a span label and a direct label.

The document converter can identify the label (s) directly based on the measured similarity between adjacent rows or adjacent columns of the table. For example, the document converter can determine a measure of similarity between each pair of adjacent rows or columns. For example, the document converter determines a particular vector for each cell of each pair of adjacent rows or columns and measures the similarity by determining the distance between each cell in the same column or rows based on the characteristic vector of the individual cells. You can decide. Thereafter, the document converter can sum the distances of the columns of adjacent rows or the distances of the rows of adjacent columns to determine a measure of similarity between each of the adjacent rows or columns. Then, after determining the measure of similarity, the document converter may identify a pair of dissimilar adjacent rows or columns based on the measure of similarity by a given percentage relative to other pairs of each of the adjacent rows or columns. The document converter can then identify the row or column of the identified pair of adjacent rows or columns, which can be identified as including at least one direct label.

According to another aspect of the present invention, there is provided a terminal, method and computer program for converting table information including at least one table. Therefore, embodiments of the present invention provide a system and associated terminal, method and computer program for converting table information including at least one table. Systems and associated terminals, methods, and computer programs in accordance with embodiments of the present invention may convert tables to allow subsequent rendering to be performed by a terminal, such as a mobile phone. In contrast to the methods in the prior art, the system, the associated terminal, the method and the computer program according to the present invention convert the table in a manner that allows the terminal to provide the full contents of the table. In addition, the system, associated terminals, methods and computer programs according to the present invention can localize the labels in a table to the cells associated with each label, thereby allowing the tables to be rendered in a way that allows them to more harmonize with the design of the original table. . Therefore, the system, associated terminal, method and computer program according to an embodiment of the present invention not only identify problems with the prior art but also provide further advantages.

In describing the present invention using general terms, reference should be made to the accompanying drawings, which are not necessarily drawn to scale.

The invention will be described in detail with reference to the accompanying drawings, in which preferred embodiments are shown. The present invention may be implemented in different forms, but is not necessarily limited thereto and should not be construed as limited to the embodiments illustrated herein. Rather, the embodiments illustrated in this specification are provided to more fully understand the present invention, and are provided to completely convey the technical idea of the present invention to those skilled in the art. In the present specification, the same reference numerals denote the same members.

1, an example of one type of terminal and system to which the advantages of the present invention are applied is provided. The system, terminal, method and computer program according to an embodiment of the present invention will first be described with regard to mobile communication application functionality. However, it should be understood that the systems, terminals, methods, and computer programs according to embodiments of the present invention may be used in combination with various functions within the mobile communications industry and various application technologies outside the mobile communications sector. For example, systems, terminals, methods, and computer programs according to embodiments of the present invention may be used in conjunction with wired and / or wireless networks (such as the Internet, for example).

As shown, the terminal 10 may include an antenna 12 for transmitting signals to a base station or base station (BS) 14 or for receiving signals from the base station. A base station is part of a wireless network, such as a mobile switching center (MSC) 16, which contains the components required to operate the network. In addition, as is known to those skilled in the art, a wireless network may be called a base station / MSC / Interworking function (BMI). In operation, the MSC may connect or receive a call from the terminal when the terminal makes or receives a call. The MSC can also provide connectivity to landline trunks when the terminal is busy. In addition, the MSC may deliver a message to the terminal, receive a message from the terminal, connect the short message service (SMS) messages to the SMS center (SMSC) 17 or receive the terminal from the SMS center. It is also possible to control the delivery of messages to or from the message center.

The MSC 16 may be connected to a data network, such as a local area network (LAN), metropolitan area network (MAN), and / or wide area network (WAN). The MSC can be connected directly to the data network. However, in a typical embodiment of the present invention, the MSC is connected to devices such as proxy 18, gateway (GTW), and the proxy is connected to a WAN, such as Internet 20. For example, the MSC may be connected to a wireless application protocol (WAP), which is connected to the Internet. In addition, devices such as processing elements may also be connected to the terminal 10 via the Internet (personal computer and server computer and such devices). For example, as described below, the processing element may include one or more processing elements associated with the origin server 22 or such devices, one example of which is shown in FIG.

The BS 14 may also be connected to a General Packet Radio Service (GPRS) Support Node (SGSN) 24 that sends a signal. As is known to those skilled in the art, SGSNs can typically perform operations similar to the MSC 16 for packet switched services. SGSNs, such as MSCs, may be connected to data networks, such as the Internet 20. SGSN may be directly connected to the data network. However, in a more typical embodiment, the SGSN is connected to a packet-switched core network, such as GPRS core network 26. The packet-switched core network is then connected to another GTW, such as GTW GPRS Support Node (GGSN) 28, and the GGSN is connected to the Internet. The GGSN may also be connected to a message center, such as a multimedia messaging service (MMS) center 30. In this regard, SGSNs such as GGSN and MSC may control the delivery of messages such as MMS messages. GGSN and SGSN may also control the terminal forwarding messages to or receiving messages from the message center.

In addition, by coupling the SGSN 24 to the GPRS core network 26 and the GGSN 28, devices such as original servers 22 can be coupled to the terminal via the Internet 20, SGSN and GGSN. Can be. In this regard, devices such as origin servers can communicate with the terminal via SGSN, GPRS, and GGSN. For example, according to something like a Multimedia Broadcast Multicast Service (MBMS), original servers may provide content to a terminal. For more detailed information on MBMS, refer to the Third Generation Partnership Project (3GPP) specification 3GPP TS 22.146, named Multimedia Broadcast Multicast Service (MBMS). Here its full description is incorporated by reference.

Terminal 10 may be further coupled to one or more wireless access points (APs) 32. Wireless access points (APs) are technologies such as one of a number of other wireless networking technologies including, for example, Radio Frequency (RF), Bluetooth, Infrared (IrDA) or WLAN technologies. And may include access points configured to communicate with a terminal. In addition, or in the alternative, the terminal may be coupled to one or more user processors 34. Each user processor may include a computing system such as personal computers, laptop computers or the like. In this regard, the user processors are terminal in accordance with any one of a number of other wireline or wireless communication technologies, including, for example, RF, BT, IrDA, or LAN, and / or WLAN technologies. It may be configured to communicate with. One or more user processors may additionally or alternatively include a removable memory capable of storing content, which content may then be delivered to a terminal.

The APs 32 and user processor 34 may be connected to the Internet 20. Similar to the MSC 16, APs and user processors may be directly connected to the Internet. However, in one advantageous embodiment, the APs may be indirectly connected to the Internet through the proxy 18. As assessed below, by combining the terminals and origin server 22 as well as any of a number of other devices, directly or indirectly, the terminals can communicate with each other, the origin server, and so on, through which data, content Or send similar ones to the origin server and / or receive content, data or the like from the origin server from the origin server. As used herein, the terms “data”, “content”, “information” and similar terms may be transmitted, received and / or stored in accordance with embodiments of the present invention. It may be used interchangeably to refer to data that may be. Therefore, use of such terms should not limit the spirit and scope of the present invention.

2, a network capable of operating as a terminal 10, origin server 22, proxy 18, SMSC 17, MMSC 30, GGSN 28, and / or user processor 34. A block diagram of a network entity, such as a network entity, is shown in accordance with one embodiment of the present invention. Although shown as separate entities, in other embodiments one or more entities may support co-located terminals, proxies, origin servers, and / or user processors that are logically separated within the entity (s). have. For example, a single entity can support logically separated but co-located terminals and proxies. Also, for example, a single entity may support origin servers and user processors that are logically separated but coexist.

As shown, a network entity may generally include a processor 36 coupled to the memory 38. The processor may also be coupled to the interface 40 or other means for transmitting and / or receiving data, content or the like. The memory may include volatile and or nonvolatile memory, and typically may store content, data, or the like. For example, the memory may typically store software applications, instructions, or the like for the processor to perform steps related to the operation of an entity in accordance with embodiments of the present invention. Additionally, as described below, the memories can store a document converter capable of converting tabular information for rendering by terminal 10. Also, for example, the memory may store content transmitted or received from the same network entity from another network entity.

3 illustrates a functional block diagram of a mobile station capable of operating as a terminal 10 in accordance with embodiments of the present invention. It is to be understood that the mobile stations described herein and below are merely exemplary of one type of terminal according to the present invention and should therefore not limit the scope of the present invention. While other embodiments of a mobile station are described and described hereinafter for purposes of illustration, personal digital assistants (PDAs), pagers, Laptop Computers and other types of voice and Other types of mobile stations, such as text communication systems, are willing to adopt the present invention.

The mobile station includes a processor such as a transmitter 42, a receiver 44, and a controller 46 that provides signals for transmitting and receiving from the transmitter and the receiver. Such signals include signaling information in accordance with the air interface standard of the applicable cellular system, and user voice and / or user generated data. In this regard, the mobile station can operate with one or more air interface standards, communication protocols, modulation types, and access types. More specifically, the mobile station can be any one of a number of first generation, second generation, and 2.5 generation and / or third generation communication protocols and the like. Can work. For example, the mobile station can operate in accordance with the second generation wireless communication protocols IS 136 (TDMA), GSM, and IS-95 (CDMA). Also, for example, the mobile station can operate in accordance with the 2.5 th generation wireless communication protocols GPRS, Enhanced Data GSM Environment (EDGE), or the like. The mobile station may additionally or alternatively operate according to one of a number of other digital broadcasting technologies, such as DVB technology (eg DVB-T, ETSI standard EN 300 744). The mobile station can also operate in accordance with one of a number of technologies, such as multicast technologies such as a number of other broadcast and / or MBMS technologies (eg, 3GPP TS 22.146). In addition, the mobile station may operate in accordance with ISDB-T, DAB, ATSC technologies or the like. As with dual or high mobile stations (e.g., digital / analog or TDMA / CDMA / analog phones), not only TACS but also narrow-band AMPS (NAMPS), the mobile station is also in an embodiment of the present invention. Gain

It is understood that the controller 46 includes circuitry necessary to implement the audio and logic functions of the mobile station. For example, the controller may be comprised of a digital signal processor device, a microprocessor device, and various analog to digital converters, digital to analog converters, and other support circuits. The control and signal processing functions of the mobile station are assigned between these devices according to their respective capabilities. Thus, the controller also includes the ability to convolutionally encode and interleave messages and data prior to modulation and transmission. The controller may additionally include an internal voice coder (VC) 46A and may include an internal data modem (DM) 46B. In addition, the controller includes the ability to operate one or more software applications that can be stored in memory.

The mobile station also includes a user interface including conventional earphones or speakers 48, a ringer 52, a display 54, and a user input interface, all of which are coupled to the controller 46. The user input interface that allows the mobile station to receive data may include any of a number of devices, such as a keypad 56, a touch display (not shown), or other input device that allows the mobile station to receive data. . In embodiments involving a keypad, the keypad includes a conventional number (0-9) and associated keys (#, *) and other keys for operating the mobile station.

The mobile station may also be in accordance with any of a number of other wired and / or wireless technologies, such as another terminal 10, proxy 18, origin server 22, AP 32, user processor 24, or the like. It also includes one or more means for sharing and / or obtaining data from electronic devices. For example, a mobile station may use a radio frequency (RF) transceiver 58 and / or an infrared (IR) infrared to enable the mobile station to share and / or obtain data in accordance with radio frequency and / or infrared technologies. Transceiver 60 may be included. In addition, the mobile station may include a Bluetooth (BT) transceiver 62 to allow the mobile station to share and / or obtain data, for example in accordance with Bluetooth delivery techniques. Although not shown, the mobile station additionally or alternatively receives data from electronic devices in accordance with wireless networking technologies including a number of other wireline and / or LAN and / or WLAN technologies. Transmit and / or receive.

The mobile station may further include a memory, such as a Subscriber Identity Module (SIM) 64, a Removable User Identity Module (R-UIM), or the like, which is incorporated into the mobile subscriber. Typically stores related information elements. In addition to the SIM, the mobile station may include other memory. In this regard, the mobile station may include embedded and / or removable volatile memory 66 and / or other nonvolatile memory 68. For example, other non-volatile memory may include embedded or removable Multimedia Memory Cards, memory sticks, EEPROM, flash memory, hard disk or the like.

The memories 64, 66, 68 may store a number of pieces of information and data used by the mobile station to implement the functions of the mobile station. For example, the memories may include an International Mobile Equipment Identification (IMEI) code, an International Mobile Subscriber Identification (IMSI) code, which may uniquely identify the mobile station for such things as MSC 16; An identifier such as Mobile Station Integrated Services Digital Network (MSISDN) code or the like may be stored. The memories also store content as received from an origin server 22 and / or user processor 34. Also, for example, the memories can store one or more presentation applications, such as a conventional text viewer, audio player, video player, multimedia viewer, or the like. In addition, as described below, the memories may store a document converter capable of converting tabular information for rendering by the mobile station.

As described in the background section, the terminals 10 are essentially designed due to the inherently limited display area, resolution, and rendering capabilities of those terminals, so that the terminals 10 generally render electronic documents. Can not. For example, many terminals typically only render a few lines of text on a display (e.g., display 54) and render grayscale, thumbnail-sized images. Or render images at all. In this regard, terminals generally cannot render tabular information in electronic documents, as tabular information is fundamentally designed. For example, some conventional devices omit such tabular information. Other devices cut selected column (s) of the tables, or perform a linear linearization of the table, typically each cell of the table without considering the natural order of the contents of those cells in the table. Renders independently. Still other devices render only a partial viewport of the entire table, so that the user of the device needs to move the fractional viewport from left to right in the table and thus expose other parts of the table.

Accordingly, other embodiments of the present invention may transform electronic documents for rendering by a terminal having display, resolution, and / or rendering functions of a limited display area. More specifically, embodiments of the present invention may transform the table information of electronic documents for rendering by such a terminal. Unlike conventional techniques for rendering tables in such terminals, embodiments of the present invention can thus render the entire contents of such tables without truncating one or more selected columns of the tables, and such cells within the table. Perform linear linearization of the table by rendering each cell of the table without taking into account the natural ordering of the contents of the tables, and not rendering only the partial viewport of the entire table, thereby allowing the user of the device to move the viewport. There is a need.

In accordance with embodiments of the present invention, tabular information of electronic documents generally includes one or more tables, each of which encapsulates a two-dimensional matrix of content such as data, information or the like. do. As will be understood by one of ordinary skill in the art, such two-dimensional tables generally comprise at least one row and at least one column. Also, such a table may or may not include complex structures (eg nested tables or images). In addition, high levels of both syntactic and semantic coherence typically exist between the row (s) and column (s) of such a table.

Reference is now made to FIGS. 4 and 5, which individually describe functional block diagrams and flowcharts of proxy 18, and how to transform table information in an electronic document, in accordance with one embodiment of the present invention. . More specifically, FIG. 4 is similar to terminal 10, origin server 22, SMSC 17, MMSC 30, GGSN 28, user processor 34, or the like in accordance with one embodiment of the present invention. A functional block diagram of a proxy that receives and sends electronic documents from the same content server 100 is described. However, prior to sending the electronic document, the proxy can receive the electronic document and then operate a document converter 102 that can transform the table information of the document for rendering by the terminal 10. Can be. The proxy then sends to the terminal an electronic document containing the modified table information for rendering by the terminal, more specifically the display of the terminal (eg, display 56).

Although the proxy 18 operates the document converter 102 as shown and described herein, the document converter is for example a terminal itself 10 or a number of other network entities in the system including the content source 100. It can work from any of these. In this regard, the document converter may be implemented on a single network entity, or alternatively portions of the document converter may be implemented on one or more network entities. In addition, as described herein, a document converter may typically be stored in memory (eg, memory 38) and may include software that may be operated by a processor (eg, processor 36). However, it should be understood that the document converter may alternatively include firmware or hardware without departing from the spirit and scope of the present invention. In addition, it should be understood that the document converter may perform operations on the electronic document rather than modifying the table to facilitate rendering of the electronic document by the terminal. For more detailed information on such various operations, see, eg, US Patent Application No. 09 / 851,404, filed May 8, 2001 and US Application Publication No. 2003/0046318, published March 6, 2003, Their contents are hereby incorporated by reference in their entirety.

As shown in block 104 of FIG. 5, a method of transforming table information that includes at least one table includes a document converter 102 that receives an electronic document from a content source 100. According to embodiments of the present invention, an electronic document includes one or more tables, each table comprising at least one row content and at least one column content. The electronic document includes any one of a number of different formats. For example, an electronic document may be a Hypertext Transfer Protocol (HTTP) document, an email document, a Portable Document Format (PDF) document, a postscript document, an ASCII text format. (TXT) documents, extensible markup language (XML) documents, Microsoft® Word ^™ (DOC) documents, Microsoft® Excel ^™ (XLS) documents, or the like.

After receiving the electronic document, document converter 102 may convert the electronic document into an intermediate data structure representation of the electronic document as shown in FIG. 106. The document converter converts the electronic document in any of a number of ways to create one of a number of different intermediate data structures capable of representing the electronic document. In this regard, the document converter can convert the electronic document into an intermediate data structure that includes a common internal tree-based representation of the electronic document. For example, the document converter can convert an electronic document into an eXtensible HyperText Markup Language (XHTML) Document Object Model (DOM) representation of the electronic document.

The document converter 102 can convert the electronic document into XHTML DOM data structures in a number of different ways. For example, in one embodiment the data converter converts an electronic document into an HTML document (if not an HTML document), converts the HTML document into an XHTML document, and then converts the electronic document into an XHTML DOM data structure. Can be converted. In order to convert an electronic document into documents of the preceding formats to create an XHTML DOM data structure, the document converter can perform a number of different known conversion routines.

The document converter 102 can additionally or alternatively communicate with other software, hardware or firmware modules operating on the proxy 18 or other network entity, where the other module converts the electronic document into an XHTML DOM data structure. One or more conversion routines may be performed to assist the document converter in doing so. For example, the document converter can communicate with the wvWare software package developed by the wvWARE Project to convert DOC documents into HTML documents. Also, for example, to convert XLS documents into HTML documents, the document converter can communicate with the xlHtml software package developed by the Chicago Project. In turn, for example, to convert HTML documents into XHTML documents, the document converter can communicate with the HTML Tidy software package developed by the Tidy Project.

In addition, for example, document converter 102 may communicate with an XML parser such as Xerces XMI, a parser software package (developed in the Apache XML Project) to convert XHTML documents to XHTML DOM data structures. Regardless of how a document converter converts an electronic document into a data structure representing an electronic document, the data structure may be stored in volatile memory as opposed to the nonvolatile memory in which the document converter and the electronic document are typically located, It doesn't have to be. As assessed below, the data structure typically includes a number of nodes corresponding to the tags of the converted XHTML document that may be based on the tags of the underlying HTML document. For example, consider the following source code for an HTML document:

As shown by the source code mentioned above, the HTML document contains two rows and three columns, where two columns of each row contain an image. The HTML document also contains block text of the third image and the small font. From such an HTML document, the document converter creates an XHTML DOM data structure as shown in FIG.

Regardless of how document converter 102 converts an electronic document into an intermediate data structure representation of the electronic document, as or after the document converter converts the electronic document to an intermediate data structure, the document converter As shown in block 108 of FIG. 5, certain "implicit" tables can be identified within the intermediate data structure. As can be seen, for tables that are otherwise identified in the formatting of an electronic document, such as tags in an HTML document (ie, "<table> </ table>"), the document converter will typically identify the tables specifically. no need. However, for other tables, the electronic document may be designed such that the information is in tabular form without otherwise including formatting representing the information as a table. The document converter can identify "implicit" tables, where the implicit tables are typically not otherwise represented by table nodes of a data structure after the document converter converts the electronic document into a data structure. The document converter can then reformulate the data structure to include table nodes for the tables.

For example, considering the formatted ASCII in the TXT document below:

Activity calories / hour

Aerobics 660

Basketball 550

Running 925

Tennis 450

In appearance, the above ASCII format text clearly represents a table. However, the TXT format does not include a mechanism (e.g. tags) that explicitly represents text such as a table. According to a technique using a document converter to convert a TXT document into a data structure, the document converter can recognize a block of text such as a table. However, in various other examples, document converter 102 cannot recognize text blocks such as tables. In some instances, the document may generate a data structure as shown in FIG. 7A. As shown, the data structure identifies text as unstructured text. Therefore, the document converter can also recognize implicit tables as examples, in which the electronic document contains implicit tables and is not otherwise recognized by the document converter during conversion of the electronic document or in the table of the data structure. Nodes are not otherwise represented.

The document converter 102 may identify implicit tables in any of a number of other known methods provided through dedicated syntax parsers and automatic learning techniques. Examples of many known techniques for identifying implicit tables include, but are not limited to, Jianying et al., A System of Understanding and Reformulating Tables, FOURTH ICPR WORKSHOP ON DOCUMENT ANALYSIS SYSTEM 200; Mathew Hurst & Shona Douglas, Layout and Language: Preliminary Investigations in Recognizing the Structure of Tables, PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON DOCUMENT ANALYSIS AND RECOGNITION (ICDAR) 1043-1047 (1997); and Ilwee Tou Ng et al., Learning 'o Recognize Table in Free Text, Proceedings of the 37th Annual Meeting of ACL 443-450 (1999), all of which are herein incorporated by reference in their entirety. Are integrated.

Regardless of how document converter 102 identifies the implicit tables, if the document converter identifies one or more implicit tables in an electronic document, the document converter identifies the data structure to identify the text as a table. Can be created or reformed. For example, the document converter can recognize a block of text as a table, and with the appropriate HTML tags (e.g., <table>, <tr>, <td>, etc.) while converting an electronic document into an HTML document. By encapsulating the text block, you can generate an HTML document formatted to identify the text block like a table. Continuing the example above for a text block of a TXT document, the document converter may identify the text block as an implicit table, and then include the implicit table as an explicit table as shown in FIG. 7B. The structure can be created or reformulated.

After document converter 102 generates a data structure representation of the electronic document that reconstructs certain implicit tables as explicit tables, the document converter has an electronic document to have a predefined order as shown in block 110. You can rearrange the tables in. Here, the electronic converter may identify the natural order of the cells of the electronic document tables according to either row-major ordering or column-first order. As will be appreciated by those skilled in the art, tables generally have a column-first order when the contents of the table are arranged in columns. In contrast, tables generally have a row-first order when the contents of the table are arranged in rows.

After identifying the natural order of the cells of the electronic document tables, document converter 102 may rearrange the tables such that all the tables have a predefined order. In one exemplary embodiment, for example, the document converter may rearrange the tables such that all the tables have a column-first order. In some instances, for tables with row-first order, the document converter may alter the table such that the natural order is column-first. However, the document converter may alternatively rearrange the tables such that the tables have a row-first order according to another operation of the adjusted document converter.

The document converter 102 can identify the natural order of the tables in some other way. For example, the document converter may be configured to find a similar pattern among adjacent cells of each table. Here, consider a row-column table with, for example, a second column containing an image in each cell. The fact that all cells in a column are similar to each other and that the table has a row-first order is clear but nevertheless generally not deterministic. Alternatively, consider a column-first table, for example, with a second row containing an image in each cell and a fifth row containing a number with a percent mark in each row. The fact that the cells in a row are similar to each other and have a column-first order is obvious but again not generally deterministic.

In one exemplary embodiment, document converter 102 identifies the natural order of the table by representing the information in each cell as a characteristic vector. For example, each cell may be represented by a characteristic binary vector of a given length N, where each position corresponds to a predicate (yes / no question) value representing the information characteristic of each cell. As can be seen, the characteristic vector representation is a method for encoding the structural characteristics of each cell of the table. Thus, similarly-visible cells generally have similar feature vector representations.

The characteristic vector contains some bits (N) corresponding to some other number of vectors. For example, the feature vector may include 13 bits (ie, N = 13), with each bit corresponding to the following predicate:

If the cell contains an image and only contains (iff; i.e., if and only if), bit 1 is "1"

If the cell contains a number and only contains it, bit 2 is "1"

If the cell contains a hyperlink and only contains it, bit 3 is "1".

If the cell contains bold text and only contains it, bit 4 is "1"

If the cell contains Italian text and only contains it, bit 5 is "1"

If the cell contains punctuation and only contains, bit 6 is "1"

If the cell contains a character between 0 and 5 and only contains, bit 7 is "1"

If the cell contains characters between 6 and 10 and only contains, bit 8 is "1".

If the cell contains characters between 11 and 15 and only contains, bit 9 is "1".

If the cell contains characters between 16 and 20 and only contains, bit 10 is "1"

If the cell contains characters between 21 and 25 and only contains, bit 11 is "1".

If the cell contains characters between 26 and 30 and only contains, bit 12 is "1"

If the cell contains more than 31 characters and only contains, bit 13 is "1".

The characteristic vectors for the table and the cells of the table are shown for brief reference in FIGS. 8A and 8B, respectively. Referring to the table shown, for example, the cells of the first column and the cells of the first row are blank. Thus, the cells of the first column and the cells of the first row may be represented by the characteristic vector 0000001000000, which corresponds to a cell whose unique "1" bit value is contained between 0 and 5 characters. In contrast, the cell of the second column cell and the first line, and includes, nine (phrase) "paid reserve ^5M limit (equity reserve ^5M line) which may be represented as a feature vector 0.000001 trillion. As shown, only the previously A "1" bit value corresponds to a cell containing between 21 and 25 characters (the phrase includes counting spaces, 21 characters).

After representing the information of each cell as a feature vector, document converter 102 may determine the degree of similarity between cells in the table based on the feature vectors. The document converter can determine the similarity value between adjacent cells in a number of different ways, such as by determining a "Manhattan" distance between adjacent cells. In this regard, the distance can be determined for two adjacent cells by checking the number of different bits between the feature vectors of each cell. For example, the distance between 0111 and 1110 is two. As can be seen, the smaller the distance between adjacent cells, the greater the similarity of each cell. A diagram of the distance between cells of the table of FIG. 8A determined by the embodiment of the present invention is shown in FIG. 8B.

Also, in various examples, one or more predicates corresponding to each bit value (s) of the feature vector may exhibit greater cell similarity than other predicates. For example, the first bit in the 13-bit feature vector may indicate cell similarity greater than the 10th bit. Therefore, according to an embodiment of the present invention, one or more bits will have an associated weight so as to include their associated weights, in sum, when the distance between two feature vectors differs between adjacent cells. Can be.

Regardless of how the degree of similarity or distance between adjacent cells of a table is accurately determined, after determining the distance, document converter 102 may determine whether the table is in column-first or row-first order. More specifically, the document converter can determine the order of the table based on the distances across the various columns and rows of the table. For example, the document converter converts the average distance between pairs of adjacent cells in the same column in a table, Can be determined; Average distance between pairs of adjacent cells in the same row in a table, Can be determined. Lower average distances between adjacent cells in the same column generally indicate that the columns of the table contain similar cells, which suggest that the table may have a row-first order. Conversely, a lower average distance between adjacent cells in the same row indicates that the rows of the table contain similar cells, which suggest that the table may have a column-first order. When used notationally, the document converter is based on the following formula: Wow Can be determined:

As shown in formulas (1) and (2) above, Represents columns in a table; Indicates rows. Also, Represents adjacent cells of the table, Denotes the distance between each adjacent cell. In the table of FIG. 8A and from the distance shown in FIG. 8B, = 2.4 (ie 24/10), = 0.583 (ie, 7/12).

Document converter 102 has the same column Rows such as Having determined the average distance between adjacent pairs of cells of the document converter, the document converter can determine whether the table is in column-first or row-first order. For example, the document converter can determine the order by comparing the average distance. If same row above The average distance between pairs of adjacent cells of the same column Is greater than the average distance between pairs of adjacent cells of The document converter may determine that the table has a row-first order, or else determine that the table has a column-first order. Like the column-first order, in order to rearrange the tables of the electronic document to have a predetermined order, the document converter can change the tables with the row-first order such that all the tables have a column-first order. In notational terms, an electronic document table is represented by each cell Each of these cells This can be changed by reconstructing the DOM tree to be replaced with.

As can be seen, in various examples Wow Can be very similar, and they can be in tables that have been reversed in order from the desired. Thus, document converter 102 makes it easier to change a given table to some extent during the comparison. or Can be weighted. For example, the document converter may have a bias of one or more values, C, Can be multiplied by next, Wow While comparing (i.e. > C * ), As the bias increases, the document converter becomes less easy to change tables when the document converter changes row-first tables, and Wow Has a similar value.

After rearranging the tables to have a predetermined order, document converter 102 may linearize the table into a one-dimensional sequence of cell contents of the tables, which are not otherwise included in the table. Advantageously, however, prior to linearizing the tables, document converter 102 may localize any labels contained within the table, as shown in block 112 of FIG. As can be seen, multiple tables include cells that serve as labels for one or more other cells. In this regard, when a label refers to a single column or row of cells, the label is often referred to as a "direct" label. In contrast, when a label refers to more than one column or more than one row, the level is often referred to as a "span" label. As shown in the table of FIG. 9, for example, labels such as "YR," "TM," "GP," and "G," are direct labels, while the labels "Regular Season". And “Post Season” are span labels.

As can be seen, as shown in FIG. 9, by linearizing a column-first table with row labels, row labels can be separated from the cells to which they are referenced. As such, a given table can be difficult to understand in terminal 10 having a limited display area. In this regard, referring to FIGS. 10A and 10B, which show a portion of the table of FIG. 9 for a terminal display, the table has gone through a direct linearization process. As can be seen, the column labels are separated from the cells that the labels refer to, making the table difficult to understand. More specifically, as shown, the column comprising a number of direct labels (e.g., "YR," "TM," "GP," "G,", etc.) is derived from the data it refers to, ie each It is apparently separated from the cells of each row below the labels.

In order to avoid separating row labels from the data to which the labels refer, the document converter 102 of one advantageous embodiment localizes the labels (if any) located within the electronic document tables. More specifically, the document converter rearranges the labels such that the labels are positioned adjacent to the data that the labels describe. As such, the document converter can help the user understand a given table in succession.

The document converter 102 can localize the labels in the tables of the electronic document in any number of other ways. A very advantageous technique for localizing labels is described below with reference to FIG. As described below, the document converter localizes labels for a column-first table having at least one column that includes at least one label. However, the document converter can localize labels in many other situations. For example, the document converter may localize labels for a row-first table having at least one row that includes at least one label. In such an example, the process of localizing labels can generally proceed with the operations performed on the base of the columns performed on the base of the rows as described herein, and the base of the rows performed on the base of the columns. It may proceed with the operations performed in. In addition, the document converter does not need to localize labels for tables in the tables, especially those that do not contain any labels. In general, when the document converter rearranges tables into column-first tables, the document converter also does not localize labels, and the tables do not include any columns with labels.

According to some techniques, document converter 102 may localize labels by first identifying columns containing span labels, ie, labels spanning one or more rows as shown in block 118 of FIG. 11. More specifically, the document converter includes a predetermined number of columns (e.g., three columns) for tags that identify cells containing table data (e.g., <td>) or table headers (e.g., <th>). Cells may be examined, where the cells also have a multi-row attribute (eg, "colspan"). As can be seen, the above attributes generally represent cells spanning more than one row of the table. For example, in the table of FIG. 9, the first column contains two cells each spanning one or more rows (ie, "regular season" and "post season").

After identifying the columns containing span labels, document converter 102 may directly identify any columns that contain labels, that is, labels, each referred to as a single row, as shown in block 120. Similar to the above, the document converter can examine a predetermined number of columns (eg, three columns) of cells for certain direct labels. The document converter can place the direct labels in any number of other ways. For example, in one embodiment, the document converter places labels directly based on the degree of similarity (eg, distance) between adjacent columns, where the degree of similarity between adjacent columns is determined as described above. Based on the degree of similarity between the cells. In this regard, as those skilled in the art will appreciate, the columns of direct row labels are often different from the rest of the columns of the table in many other respects. For example, the second column of FIG. 9, which constitutes direct row labels, constitutes a character as a whole, whereas the columns below the second column generally constitute almost a number.

To locate the direct labels of the table, document converter 102 can determine its similarity or distance between adjacent columns of the table, where the similarity is determined based on the similarity of vertical-adjacent cells within each column. Written in notation, the document converter uses the distance between adjacent columns of the table according to the following formula (3): You can decide:

In the above formula, Indicates the first column of the table that does not contain at least one span label.

After determining the distance between adjacent columns, the document converter 102 can identify any pair of adjacent columns that have much greater dissimilarity than any pair of next adjacent columns, where significant dissimilarity. Represents the first column of each pair containing the labels directly. In other words, the document converter can determine whether the distance between any pair of adjacent columns is significantly greater than the distance between any next pair of adjacent columns and identify the first column of any pair, such as directly containing labels. Can be. More specifically, for example, the document converter may of, Starting with, we can compare the distance between the next pair of adjacent columns. Then, the first greater than at least a given percentage (eg, 50%) than any next pair of adjacent columns About, open Can be identified directly as a column containing labels.

Once the document converter 102 has identified a column containing span labels and / or direct labels, the document converter has a label tree of the table by any of a number of known techniques as shown in block 122 of FIG. You can create an expression. More specifically, for example, the document converter can create another data structure that is used to localize the labels, where the data structure reflects the association of span and direct row labels to individual cells of a table. do. This data structure, referred to as the "label tree," can capture the structure of span and direct row labels previously identified. In this regard, FIG. 12 illustrates a label tree representation of the table of FIG. 9, according to an embodiment.

After document converter 102 generates the label tree representation of the table, it may localize the labels of the table. As shown at block 124, the document converter may localize the labels by traversing the label tree and data structure representation to determine the position of labels in the linearized representation of the table. As such, the table may then be linearized to include labels located near each table cell. As can be appreciated, the label tree representation and data structure can be traversed in any number of other ways. In one embodiment, for example, the document converter is each column except for any cell (s) including span or direct labels and any cell (s) without content, ie blank cell (s). Examine each cell of each row (i = 1, ..., C) of (j = 1, ..., R).

At this time, for each row of each column except the blank and label cell (s), the document converter goes from the root node to the leaf (L) of the branch of the tree label representation of the table (see FIG. 12), label path x _k = {x ₁ , x ₂ , ..., x _L } can be defined. Each leaf is associated with each row of the table. In addition, the document converter may define a label string s _ij . Each label string is initialized to a zero value for each cell. For each node in each label path (k = 1, ..., L) in the label tree representation of the table above, if x _k contains span labels and x _{k + 1} contains the first node below x _k , The document converter 102 can add a new line to the label string s _ij along with the span label, another new line, and at least one space character (eg, a tab). On the other hand, if x _k includes a direct label, the document converter can add the direct label to the label string s _ij with a separator such as a colon. Then, after examining the table cells and generating the label strings s _ij , the document converter may add each label string to each cell x _ij , for example, during linearization of the table described below.

For example, consider the table of FIG. 9 and the label tree representation of FIG. 12. The table includes a number of span and direct labels. In this case, the examination of the cells of the table can begin with the cells 3,1 containing the values "84-85". Following the leaf node associated with the third column with the root node of the label tree representation, document converter 102 may define the label path x _k = {x ₁ = " YR &quot;}. In addition, the document converter may define a label string s _3,1 , which is initialized to a zero value. At this time, since x ₁ includes a direct label, the document converter may add the direct label to the label string s _ij with a colon. S _3,1 = {"YR:"}. The same process can then be repeated for cells 3 and 2. Where s _3,2 = {"TM:"}. On the other hand, for cells 3 and 3, the document converter has the label path x _k = {x ₁ = "Regular Season"; x ₂ = "GP"}. After initializing the label string (s _3,3 ) to zero, the document converter is new because x ₁ contains the span label and x ₂ (ie, x _{i + 1} ) contains the first node below x _1. Lines can be added to the label string (s _3,3 ) along with span labels, other new lines, and tabs. Then, for x ₂ , the document converter may further add a direct label and a colon to the label string s ₃ , ₃ . Thus, the label string s _3,3 can be expressed as follows: s3,3 = {＼n; "Regular Season"; \ n; \ t; "GP:"}, where "\ n" and "\ t" represent a new line and a tab, respectively, when the label string is represented by the terminal 10.

Referring again to FIG. 5, once the document converter 102 determines the label string s _ij and thereby positions the labels, the document converter linearizes the table into a one-dimensional sequence of cells as shown in block 114. can do. The document converter can linearize the table in one of a number of different ways. For example, in one embodiment, the document converter can linearize the table by replacing the table with one or more individual paragraphs (eg, <p>). Here, each paragraph contains one or more of the cells of the original table. In this regard, the document converter may traverse a table having a row-major order, typically starting at the top leftmost cell and ending at the bottom rightmost cell, in particular the document converter being able to ) Can be arranged in a column-first order, moving the contents of each cell to each paragraph of the linearized representation of the table.

In one embodiment, document converter 102 may linearize a table by examining the data structure representation of the table. For example, consider a data structure representation of an electronic document that includes the table shown in FIG. 13A. For each table node, the document converter can create a new temporary node (shown as node "X" in FIG. 13B) at the same level as each table node. Then, for each data node (i.e. <td>) of each column node (i.e. <tr>) representing cells of the table, typically excluding blank and label cells, the document converter is a child of node "X" ( As a child, you can add paragraph nodes (for example, <p>). As shown in FIG. 13B, the document converter then moves the contents node of each data node (i.e., C1, C2, etc.), or more specifically the contents (x _ij ) of each cell below each paragraph node. Can be. In FIG. 13B, only the first and second content nodes C1 and C2 are shown to be moved. In addition to moving each content node below each paragraph node, the document converter can add each label string s _ij to the contents of each cell if each cell has a corresponding label string.

After moving the content node of each data node of each column node below each paragraph node, document converter 102 causes the table node and the associated column node (s), data node (s) and content node (s) below the table node. Can be deleted. Although the document converter may delete the table node and related nodes after moving the content node of each data node of each column node, the document converter alternatively all children of each node (ie related nodes). You can delete each node after moving or otherwise deleting). Thus, for example, the document converter may delete each table data node (ie, <td>) after moving each content node (ie, C1, C2, C3, etc.) under each paragraph node. Similarly, for example, the document converter may delete each table column node (ie, <tr>) after deleting each table data node (ie, <td>).

However, regardless of the case where document converter 102 deletes a table node after moving the content node of each data node of each column node below each paragraph node, the document converter can delete node "X" from the document structure. And as shown in FIG. 13C, each of the nodes below node “X” may be moved up in the data structure representation of the electronic document. Thus, as shown, each content node (ie, C1, C2, etc.) representing each cell (x _ij ) of the table (except for blank and label cells) may be included in each paragraph node of the data structure representation of the electronic document. . As can be seen in this case, each cell of the original table containing any added label strings s _ij may be included under a separate paragraph node. However, it should be understood that alternatively the document converter can linearize the table so that more than one cell is included under a separate paragraph node. For example, the document converter may linearize the table such that each column of cells of the table is included under each paragraph node. As an example of this case, reference is made to FIG. 14, which shows a linearized representation of the table of FIG. 9 that includes label strings to which one or more cells of the table have been added.

Once the document converter 102 linearizes the table, the document converter will convert the data structure representation of the electronic document (including the linearized representation of the table) back to the electronic document as shown in block 116 of FIG. Can be. As can be seen, the document converter can convert the data structure in a number of different ways, such as the way in which the document converter converted the electronic document into an intermediate data structure (see block 106). Then, once document converter 102 converts the data structure back to an electronic document that contains a linearized representation of each table contained in the original electronic document, proxy 18 then processes the electronic document as shown in block 117. It may be delivered to the terminal 10. The terminal can then present the electronic document, for example on a display (eg display 54). In this regard, reference is made to FIG. 15 for an exemplary representation of the table of FIG. 9 on the display.

As shown and described herein, document converter 102 may receive an electronic document that includes at least one table and convert table information of the document for display by terminal 10. The document converter can then deliver the electronic document containing the converted table information to the terminal for display by the terminal, or more particularly the display (eg display 56) of the terminal. It should be noted that in various cases the document converter can deliver an electronic document without converting the table information of the document. In this regard, as can be seen, in various examples, the terminal may support panning left and right within a display window that is wider than the display of the terminal. Thus, the document converter may determine whether the receiving terminal of the electronic document supports left and right panning before converting the table information. In this case, the document converter may transmit the electronic document without converting the table information. Alternatively, the document converter may request, for example, from the user of the terminal whether to convert the table information of the electronic document or to deliver the electronic document without converting the table information.

The document converter 102 can determine the ability of the terminal 10 to pan electronic documents in a number of different ways. For example, the document converter may maintain an internal "device capability" lookup table that includes a list of one or more receiving devices and indicates whether each device supports electronic document panning. In such cases, the document converter may determine the terminal receiver during the establishment of the communication session, for example between the terminal and the content source 100 (eg HTTP GET), and then the terminal in the "device capability" lookup table. You can perform a search of. Then, after requesting the selection of whether to convert the table information, the document converter can receive the selection and process the selection accordingly. In this regard, if the user chooses to deliver the electronic document without converting the table information, the document converter can act accordingly. Otherwise, if the user chooses to convert the table information or if the terminal does not support panning, the document converter may convert the table information as described above.

Further, as shown and described herein, document converter 102 may be origin server 22, SMSC 17, MMSC 30, GGSN 28, user processor 34, or the like. May operate on any of a number of different network entities, such as a content source or terminal 10, proxy 18, or the like. As can be appreciated, however, the various operations of the document converter, in particular when converting table information including at least one table in an electronic document, can be performed independently of the network connection. Thus, it should be understood that a network entity operating a document converter may include an entity such as a terminal or content source (eg, origin server, SMSC, MMSC, user processor, etc.) that is not connected to the network. In such cases, for example, the electronic document may be provided to the network entity in any of a number of different ways that are independent of the network, and then the document converter may for example have a table of the electronic document in the manner described above. Can be converted).

According to one aspect of the present invention, all or part of the system of the present invention, for example, terminal 10, proxy 18, origin server 22, SMSC 17, MMSC 30, GGSN 28 And / or all or part of user processor 34 generally operates under the control of a computer program product (eg, document converter 102). A computer program product for performing the methods of embodiments of the present invention is a computer readable storage medium, such as a nonvolatile storage medium, and a computer readable program code portion, such as a series of computer instructions contained in the computer readable storage medium. Include them.

5 and 11 are flow charts of systems, program products and methods in accordance with the present invention. It will be understood that each block or step of the flowchart and the combination of blocks in the flowchart can be performed by computer program instructions. The computer program instructions may be loaded into a computer or other programmable device to create a machine, such that the instructions executed in the computer or other programmable device are means for performing the functions specified in the flowchart block (s) or step (s). Create The computer program instructions may also be stored in a computer readable memory that may cause a computer or other programmable device to operate in a particular manner, such that the instructions stored in the computer readable memory may be flow chart block (s) or step (s). Create a product that includes command means to perform the functions specified in. The computer program instructions are also loaded into a computer or other programmable device such that a series of operational steps performed on the computer or other programmable device generates a computer-implemented process, and thus the instructions executed on the computer or other programmable device are flow charts. Provides steps for performing the functions specified in the block (s) or step (s).

Thus, the blocks or steps in the flowchart support a combination of means for performing certain functions, a combination of steps for performing certain functions, and a program instruction means for performing certain functions. It is also to be understood that each block or step of the flowchart and combinations of blocks or steps in the flowchart can be performed by special purpose hardware based computer systems that perform particular functions or steps or combinations of special purpose hardware and computer instructions. will be.

Many modifications and other embodiments of the invention will occur to those skilled in the art using the teachings provided in the foregoing descriptions and the associated drawings. For example, as described above in one implementation, the document converter arranges or rearranges the table (s) such that the tables have a column priority order and then processes the tables based on the column priority order. However, in an alternative implementation, the document converter can arrange or rearrange the tables so that the tables have a row priority order, and other operations of the document converter can be adjusted accordingly. For example, the document converter can place labels on a row first table having at least one row that includes at least one label, and the placement process can be performed in a similar manner as described above, typically in columns. The operations performed on the basis may be performed based on the rows or vice versa. Accordingly, it is to be understood that the invention is not limited to the specific embodiments disclosed and that modifications and other embodiments are included within the scope of the appended claims. Although certain terms have been used herein, the terms are used for the purpose of explanation in a general sense and not for the purpose of limitation.

The present invention provides an improved system and associated terminal, method, and computer program for converting table information including at least one table, to convert the table for subsequent rendering by a terminal having a limited area display. In the case where the information of the table is made easier and easier to understand by the user who displays this information, unlike the methods of the related art, and also by localizing the labels in the table to cells associated with each label, such a terminal Unlike the prior art for rendering tables on, embodiments of the present invention render the entire contents of a table without selecting and truncating one or more columns from the table.

1 is a conceptual block diagram illustrating a wireless communication system according to an embodiment of the present invention, in which a terminal includes a wireless network and a data network connected in both directions by a wireless RF link.

2 is a block diagram conceptually illustrating an entity capable of operating as a terminal, origin server, proxy / gateway, SMSC, MMSC, GGSN, and / or user processor in accordance with an embodiment of the present invention.

3 is a block diagram conceptually illustrating a mobile station capable of operating as a terminal according to an embodiment of the present invention.

4 is a block diagram functionally illustrating a terminal according to an embodiment of the present invention, in which the terminal shown in FIG. 4 downloads or receives an electronic document including a table.

5 is a flow diagram illustrating various steps of a method for converting table information in an electronic document, in accordance with an embodiment of the present invention.

6 is a block diagram of a tree-based data structure representation for an electronic document including a table in accordance with one embodiment of the present invention.

7A is a block diagram of a tree-based data structure representation for an electronic document that includes an implicit table in accordance with an embodiment of the present invention.

FIG. 7B is a block diagram of the tree-based data structure of FIG. 7A in accordance with an embodiment of the present invention, in which the implicit table of FIG. 7A is replaced with an explicit table.

8A is a diagram illustrating a table that may be included in an electronic document, in accordance with an embodiment of the present invention.

8B is a block diagram illustrating the table of FIG. 8A in accordance with an embodiment of the present invention, including similarity measures between cells, as well as feature vectors for the cells of the table.

9 illustrates another table that may be included in an electronic document, in accordance with an embodiment of the present invention.

10A and 10B are conceptual block diagrams illustrating a portion of the table of FIG. 9 rendered on a terminal display, which has been linearized without localizing the label of the table.

11 is a flowchart illustrating various steps of a method for localizing label (s) of a table that may be included in an electronic document, in accordance with an embodiment of the present invention.

12 is a block diagram of a label tree representing a table that may be included in an electronic document, in accordance with an embodiment of the present invention.

13A-13C are block diagrams of data structure representations based on a tree of electronic documents including tables, wherein the tables shown in the figures are linearized in accordance with one embodiment of the present invention.

14 is a diagram illustrating a linearized representation of the table shown in FIG. 9, in accordance with an embodiment of the present invention.

FIG. 15 is a conceptual block diagram illustrating a portion of the table shown in FIG. 9 rendered on a terminal display, wherein the table shown has been converted in accordance with one embodiment of the present invention.

Claims (40)

A system for converting table information for rendering on a terminal with a limited area display, the system comprising: A network entity comprising a document converter capable of receiving an electronic document having table information comprising at least one table, said document converter being based on the order of each table, and further comprising at least one table. And convert the at least one table into a linearized representation of the at least one table based on the at least one label when the label includes the label of. The method of claim 1, wherein the document converter arranges at least one table such that the at least one table has a predefined order, localizes each label if the at least one table comprises at least one label, and then At least one based on at least one table arranged to have a predefined order, and also by linearizing at least one table based on each localized label if the at least one table includes at least one label Table information conversion system, characterized in that the table can be converted. 3. The system of claim 2, wherein each table comprises a plurality of cells organized into at least one column and at least one row, wherein the document converter identifies a unique order of the at least one table, and the at least one table is predefined. In the case where the order is unique, the arrangement of the at least one table is possible by arranging at least one table having a unique order different from the predefined order so that the corresponding at least one table has a predefined order. System for converting table information, characterized in that. 4. The document converter of claim 3, wherein the document converter is capable of determining a feature vector for each cell of the table and determining a distance between adjacent cells based on the feature vector for corresponding cells, wherein the document converter is configured to determine the distance between adjacent cells. It is possible to determine the average distance between pairs of adjacent cells in the same column and the average distance between pairs of adjacent cells in the same row of the table, and then identify the unique order of the table based on the average distance. System for converting table information, characterized in that. 3. The system of claim 2, wherein the document converter is capable of arranging at least one table such that the at least one table has one of a column priority order and a row priority order. The method of claim 1, wherein the document converter is also capable of determining whether the terminal supports panning, and if the terminal supports panning, converting at least one table and converting at least one table. It is possible to receive a selection of sending an electronic document without the document converter, and the document converter is capable of converting at least one table if the selection includes converting at least one table. system. A system for localizing at least one label of a table in an electronic document, the table comprising a plurality of cells organized into at least one column and at least one row, wherein: A network entity comprising a document converter that identifies at least one of at least one span label and at least one direct label, each span label associated with one of a plurality of rows and columns of the table. And each direct label is associated with one of a single row and a single column of the table, the document converter each cell of the table associated with at least one of the span label and the direct label to localize each span label and each direct label. It is also possible to determine a label string for, wherein each label string comprises at least one of a span label and a direct label. 8. The system of claim 7, wherein the document converter is capable of identifying at least one direct label based on a similarity measure between one of adjacent columns and adjacent rows of the table. 9. The document converter of claim 8, wherein the document converter determines a measure of similarity between each pair of adjacent columns and one of the adjacent rows of each pair, and based on the similarity measure, a predetermined percentage of the other pair of adjacent columns. One column of the pair of adjacent columns identified as identifying one of the other pair of adjacent columns and the pair of adjacent rows that are different from the other pair of adjacent rows by a predetermined percentage and then containing at least one direct label At least one direct label can be identified by identifying one of the rows of a pair of adjacent rows. 10. The method of claim 9, wherein the document converter determines a feature vector for each cell of one of each pair of adjacent columns and each pair of adjacent rows, and based on the feature vector for the corresponding cell, Determination of a similarity measure by determining one of the distance between cells in the same row in a column and the distance between cells in the same column in an adjacent row, and then summing the distances across one of the rows of the adjacent column and the columns of the adjacent row This system is possible. In the terminal, A memory capable of storing an electronic document having table information including at least one table; And A controller capable of converting at least one table into a linearized representation of at least one table based on the order of each table and also based on at least one label if the at least one table comprises at least one label. Terminal comprising a. 12. The system of claim 11, wherein the controller arranges at least one table such that the at least one table has a predefined order, localizes each label if the at least one table comprises at least one label, and then Based on at least one table arranged to have a predefined order, and also based on each localized label if the at least one table has at least one label, thereby linearizing at least one table at least Terminal, characterized in that the conversion of one table. 13. The system of claim 12, wherein each table comprises a plurality of cells organized into at least one column and at least one row, wherein the controller identifies a unique order of the at least one table, and wherein the at least one table is predefined. If the order is different from the order, it is possible to arrange the at least one table by arranging at least one table having a unique order different from the predefined order so that the corresponding at least one table has a predefined order. Terminal characterized in that. The method of claim 13, wherein the controller is capable of determining a feature vector for each cell of the table and determining a distance between adjacent cells based on the feature vector for the corresponding cell, wherein the controller is in the same column of the table. Determine an average distance between pairs of adjacent cells and an average distance between pairs of adjacent cells in the same row of the table, and then identify the unique order of the table based on the average distance . 13. The terminal of claim 12, wherein the controller is capable of arranging at least one table such that the at least one table has one of a column priority order and a row priority order. 12. The apparatus of claim 11, wherein the controller is also capable of determining whether the terminal supports panning, and if the terminal supports panning, converting at least one table and without converting at least one table. It is possible to receive a selection of sending a document, and wherein the controller is capable of converting at least one table if the selection includes converting at least one table. In the terminal, A memory capable of storing an electronic document having table information including at least one table, comprising: a memory having a plurality of cells in which each table is organized into at least one column and at least one row; And At least one identifiable controller of at least one span label and at least one direct label, each span label associated with one of a plurality of rows and columns of the table, each direct label being a single of the table It is also possible to determine a label string for each cell of the table associated with at least one of the span label and direct label so as to localize each span label and each direct label. Terminal characterized in that. 18. The terminal of claim 17, wherein the controller is capable of identifying at least one direct label based on a similarity measure between one of adjacent columns and adjacent rows of the table. 19. The apparatus of claim 18, wherein the controller determines a similarity measure between each pair of adjacent columns and one of each pair of adjacent rows, and based on the similarity measure, differs by a predetermined percentage from another pair of adjacent columns. One column of the pair of adjacent columns and the identified adjacent that identify one of the pair of adjacent columns, and one pair of adjacent rows that differ by a predetermined percentage from the other pair of adjacent rows, and then contain at least one direct label And identifying at least one direct label by identifying one of the rows of the pair of rows. 20. The system of claim 19, wherein the controller determines a feature vector for each cell of each pair of adjacent columns and one of each pair of adjacent rows, and based on the feature vector for the corresponding cell, the adjacent column. Determining one of the similarity measures by determining one of the distance between cells in the same row and the distance between cells in the same column in an adjacent row, and then summing the distances across one of the rows of the adjacent column and the columns of the adjacent row. Terminal, characterized in that possible. A method for converting table information for rendering on a terminal having a limited area display, the method comprising: Receiving an electronic document having table information including at least one table; And Converting the at least one table into a linearized representation of the at least one table based on the order of each table and also based on the at least one label if the at least one table includes at least one label. And converting the table information. The method of claim 21, wherein converting the at least one table comprises: Arranging the at least one table such that the at least one table has a predefined order; Localizing each label if the at least one table includes at least one label; And Linearizing the at least one table based on at least one table arranged to have a predefined order, and also based on each localized label if the at least one table includes at least one label. And converting the table information to a table. 23. The method of claim 22, wherein each table comprises a plurality of cells organized into at least one column and at least one row, wherein arranging the at least one table comprises: Identifying a unique order of at least one table; And If at least one table has a unique order that is different from the predefined order, the at least one table may be arranged to have a unique order different from the predefined order such that the corresponding at least one table has a predefined order. And converting the table information to a table. The method of claim 23, wherein the step of identifying the unique order, for each table, Determining a feature vector for each cell of the table; Determining a distance between adjacent cells based on the feature vector for the corresponding cells; Determining an average distance between pairs of adjacent cells in the same column of the table and an average distance between pairs of adjacent cells in the same row of the table; And Identifying the unique order of the table based on the average distance. 23. The method of claim 22, wherein arranging at least one table comprises arranging at least one table such that the at least one table has one of a column priority order and a row priority order. Way. The method of claim 21, Determining whether the terminal supports panning; And If the terminal supports panning, further comprising receiving a selection of converting at least one table and sending the electronic document without converting the at least one table, And converting at least one table comprises converting at least one table if the selection includes converting at least one table. A method of localizing at least one label of a table in an electronic document, the table having a plurality of cells organized into at least one column and at least one row, wherein: Identifying at least one of at least one span label and at least one direct label, wherein each span label is associated with one of a plurality of rows and columns of the table and each direct label is An identification step associated with one of the single row and the single column of the table; And Determining a label string for each cell of the table associated with at least one of the span label and direct label to localize each span label and each direct label, wherein each label string is associated with at least one of the span label and direct label. Comprising a determining step comprising. 28. The method of claim 27, wherein identifying at least one label comprises identifying at least one direct label based on a similarity measure between one of adjacent columns and adjacent rows of the table. The method of claim 28, wherein identifying at least one direct label comprises: Determining a similarity measure between each pair of adjacent columns and one of each pair of adjacent rows; Based on the similarity measure, identifying one of the pair of adjacent columns that are different from the other pair of adjacent columns by a predetermined percentage and the pair of adjacent rows that are different from the other pair of adjacent rows by the predetermined percentage; And Identifying one of the columns of the pair of adjacent columns identified as containing at least one direct label and one of the rows of the pair of identified adjacent rows. 30. The method of claim 29, wherein determining the similarity measure is Determining a feature vector for each cell of one of each pair of adjacent columns and each pair of adjacent rows; Determining one of a distance between cells in the same row in an adjacent column and a distance between cells in the same column in an adjacent row based on the feature vector for the corresponding cell; And Summing the distances across one of the adjacent column and one of the columns of the adjacent row. A computer program product for converting table information for rendering on a terminal having a limited area display, the computer program product comprising a computer readable storage medium having a computer readable program code portion stored therein. The computer readable program code portion, A first executable portion for receiving an electronic document having table information including at least one table; And A second conversion of at least one table into a linearized representation of at least one table based on the order of each table and also based on at least one label if the at least one table includes at least one label. A computer program product comprising an executable portion. The label of claim 31, wherein the second executable portion arranges at least one table such that the at least one table has a predefined order, and wherein each label if the at least one table includes at least one label. At least one based on at least one table arranged to have a predefined order, and also based on each localized label if the at least one table comprises at least one label. Computer program product, characterized in that it is suitable for linearizing the table of. 33. The system of claim 32, wherein each table comprises a plurality of cells organized into at least one column and at least one row, wherein the second executable portion identifies a unique order of the at least one table, If the table has a unique order different from the predefined order, it is suitable for arranging at least one table with a unique order different from the predefined order such that the corresponding at least one table has a predefined order. Computer program product. 34. The method of claim 33, wherein the second executable portion determines a feature vector for each cell of the table, and determines a distance between adjacent cells based on the feature vector for corresponding cells, and in the same column of the table. A unique order for each table by determining an average distance between pairs of adjacent cells in the table and an average distance between pairs of adjacent cells in the same row of the table, and then identifying the unique order of the table based on the average distance And a computer program product suitable for identifying. 33. The computer program product of claim 32, wherein the second executable portion is suitable for arranging at least one table such that the at least one table has one of a column priority order and a row priority order. The method of claim 31, wherein A third executable portion for determining whether the terminal supports panning; And If the terminal supports panning, a fourth executable portion for receiving a selection of converting at least one table and sending the electronic document without converting the at least one table, And said second executable portion is suitable for converting at least one table if said selection comprises converting at least one table. A computer program product for localizing at least one label of a table within an electronic document, the table having a plurality of cells organized into at least one column and at least one row, the computer readable program code portion being stored therein A computer program product comprising a computer readable storage medium, the computer readable program code portion being: A first executable portion identifying at least one of at least one span label and at least one direct label, each span label associated with one of the plurality of rows and columns of the table, each A first executable portion wherein a direct label of is associated with one of the single row and single column of the table; And A second executable term portion for determining a label string for each cell of a table associated with at least one of a span label and a direct label to localize each span label and each direct label, wherein each label string is a span label and And a second executable portion comprising at least one of the direct labels. 38. The computer program product of claim 37, wherein the first executable portion is suitable for identifying at least one direct label based on a similarity measure between one of adjacent columns and adjacent rows of the table. The method of claim 38, wherein the first executable portion determines a similarity measure between each pair of adjacent columns and one of each pair of adjacent rows, and based on the similarity measure, determines a similarity measure with another pair of columns. One column of pairs of adjacent columns identified as including one pair of adjacent columns that differ by a percent of and one pair of adjacent rows that differ by a predetermined percentage from another pair of adjacent rows, and then containing at least one direct label And suitable for identifying one of the rows of the identified pair of adjacent rows. 40. The method of claim 39, wherein the first executable portion determines a feature vector for each cell of one of each pair of adjacent columns and each pair of adjacent rows and based on the feature vector for the corresponding cell. Determining one of the distance between cells in the same row in the adjacent column and the distance between cells in the same column in the adjacent row, then summing the distances across one of the rows of the adjacent column and the columns of the adjacent row And a computer program product suitable for determining similarity measures.