Plain-text analysis of complex document formats

A first document is stored in a first format having an ordered sequence of data elements including characters and embedded objects accessible by index location into the ordered sequence. The first document in the first format is converted into a second document in a second format having a second ordered sequence including a subset of the data elements of the first document including the characters but not the embedded objects, such that the index location into the ordered sequence of the characters differs between the first and second documents. The second document is analyzed in the second format as plain text to identify a string of the data elements of interest. A document location of the string of the data elements of interest is represented as a relative location into the second document. The relative location into the second document is mapped into the index location of the first document.

TECHNICAL FIELD

Aspects of the disclosure generally relate to the efficient plain-text analysis of complex document formats.

SUMMARY

In one or more illustrative examples, a system for document analysis is provided. The system includes a memory configured to store a first document in a first format, the first document having an ordered sequence of data elements, the data elements in the first format including characters and embedded objects, each data element being accessible by index location into the ordered sequence. The system further includes a processor programmed to convert the first document in the first format into a second document in a second format, the second document having a second ordered sequence including a subset of the data elements of the first document, the subset including the characters but not the embedded objects, such that the index location into the ordered sequence of the characters differs between the first document and the second document, analyze the second document in the second format as plain text, identify a string of the data elements of interest in the second document, represent a document location of the string of the data elements of interest as a relative location into the second document, and map the relative location into the second document into the index location of the first document.

In one or more illustrative examples, a method for document analysis is provided. A first document is stored in a first format having an ordered sequence of data elements, the data elements in the first format including characters and embedded objects, each data element being accessible by index location into the ordered sequence. The first document in the first format is converted into a second document in a second format, the second document having a second ordered sequence including a subset of the data elements of the first document, the subset including the characters but not the embedded objects, such that the index location into the ordered sequence of the characters differs between the first document and the second document. The second document is analyzed in the second format as plain text. A string of the data elements of interest is identified in the second document. A document location of the string of the data elements of interest is represented as a relative location into the second document. The relative location into the second document is mapped into the index location of the first document.

In one or more illustrative examples, a non-transitory medium includes instructions for document analysis that, when executed by a processor cause the processor to perform operations including to store a first document in a first format having an ordered sequence of data elements, the data elements in the first format including characters and embedded objects, each data element being accessible by index location into the ordered sequence; convert the first document in the first format into a second document in a second format, the second document having a second ordered sequence including a subset of the data elements of the first document, the subset including the characters but not the embedded objects, such that the index location into the ordered sequence of the characters differs between the first document and the second document; analyze the second document in the second format as plain text; identify a string of the data elements of interest in the second document; represent a document location of the string of the data elements of interest as a relative location into the second document; and map the relative location into the second document into the index location of the first document.

DETAILED DESCRIPTION

A container document refers to a document in which one or more documents are embedded within or linked to the container document. Embedded items may include plain text, structured text, images, mathematical equations, metafiles, shapes, lines, binaries, etc. Such documents may be stored as a sequence of bytes and/or characters, with the embedded elements or links located within the sequence at their respective locations within the container document. Elements in the container document, such as text, embedded objects, or linked objects, may be indexed by their byte or character position within the container document. This may allow the elements of the container document to be accessed by their indexed location.

Many software tools are available for locating textual elements within a plaintext document. In an example, regular expression libraries define search expression syntax for locating patterns in textual documents. In another example, text indexing tools may preprocess text documents, email messages, and other text documents to identify metadata elements in the documents for later search. However, these types of tools may be difficult to use on binary documents, container documents, or other file types that are beyond plain text. Moreover, these types of tools may be difficult to use on documents with embedded elements, as the embeds may not be processable by the tool. If the embeds are removed from the document to perform a search, then the indexes into the overall document may be offset due to the bytes used by the embedded elements.

A container document may be stored in a first format having an ordered sequence of data elements, where the data elements in the first format including characters and embedded objects, with each data element being accessible at its index location into the ordered sequence. To allow for the use of such search tools on such a document, the container document in the first format is converted into a plaintext document in a plaintext format, the plaintext document having a second ordered sequence including a subset of the data elements of the container document, the subset including the characters but not the embedded objects, such that the index location into the ordered sequence of the characters differs between the container document and the plaintext document. The plaintext document may then be analyzed in the second format as plain text. A string of the data elements of interest may be identified in the plaintext document. Having identified this location, the document location of the string of the data elements of interest may be mapped back into the index location into the container document.

This mapping may be performed, for example, by identifying the document location in the second document by a relative location. An example representation of the relative location may be a paragraph number of the paragraph including the string of the data elements and the occurrence number of the string of the data elements within the paragraph. Using this representation, the document location in the plaintext document may be mapped into a corresponding index location into the container document by finding, in a corresponding paragraph of the container document, the occurrence number of the identified string of the data elements. Further aspects of the disclosure are discussed in detail herein.

FIG.1illustrates a system100including an example of a computing device102for the efficient plain-text analysis of complex document formats. As shown, the computing device102may include a processor104that is operatively connected to a storage106, an output device108, an input device110, and a network device112. It should be noted that this is merely an example, and computing devices102with more, fewer, or different components may be used.

The processor104may include one or more integrated circuits that implement the functionality of a central processing unit (CPU) and/or graphics processing unit (GPU). In some examples, the processors104are a system on a chip (SoC) that integrates the functionality of the CPU and GPU. The SoC may optionally include other components such as, for example, the storage106and the network device112into a single integrated device. In other examples, the CPU and GPU are connected to each other via a peripheral connection device such as Peripheral Component Interconnect (PCI) express or another suitable peripheral data connection. In one example, the CPU is a commercially available central processing device that implements an instruction set such as one of the x86, ARM, Power, or Microprocessor without Interlocked Pipeline Stages (MIPS) instruction set families.

During operation, the processor104executes stored program instructions that are retrieved from the storage106. The stored program instructions, accordingly, include software that controls the operation of the processors104to perform the operations described herein. The storage106may include both non-volatile memory and volatile memory devices. The non-volatile memory includes solid-state memories, such as NOT-AND (NAND) flash memory, magnetic and optical storage media, or any other suitable data storage device that retains data when the system100is deactivated or loses electrical power. The volatile memory includes static and dynamic random-access memory (RAM) that stores program instructions and data during operation of the system100.

The GPU may include hardware and software for display of at least two-dimensional (2D) and optionally three-dimensional (3D) graphics to the output device108of the computing device102. The output device108may include a graphical or visual display device, such as an electronic display screen, projector, printer, or any other suitable device that reproduces a graphical display. As another example, the output device108may include an audio device, such as a loudspeaker or headphone. As yet a further example, the output device108may include a tactile device, such as a mechanically raiseable device that may, in an example, be configured to display braille or another physical output that may be touched to provide information to a user.

The input device110may include any of various devices that enable the computing device102to receive control input from users. Examples of suitable input devices that receive human interface inputs may include keyboards, mice, trackballs, touchscreens, voice input devices, graphics tablets, and the like.

The network devices112may each include any of various devices that enable the computing device102to send and/or receive data from external devices over networks. Examples of suitable network devices112include an Ethernet interface, a Wi-Fi transceiver, a cellular transceiver, or a BLUETOOTH or BLUETOOTH Low Energy (BLE) transceiver, or other network adapter or peripheral interconnection device that receives data from another computer or external data storage device, which can be useful for receiving large sets of data in an efficient manner.

The storage106may be configured to maintain documents114. These documents114may include, for example, plaintext documents114, container documents114, etc. In one example, the documents114may include documents114in the Office Open Extensible Markup Language (XML). In other examples, the documents114may include documents114in other formats such as hypertext markup language (HTML), JavaScript Object Notation (JSON), Portable Document Format (PDF), etc. The storage106may be further configured to maintain one or more applications116. The applications116may include instructions that, when executed by the processor104cause the computing device102to perform operations as discussed in detail herein.

FIG.2illustrates an example200of a container document114A including text and an embedded object202, as well as corresponding a plaintext document114B including the text but not the embedded object202. The plaintext document114B may be generated from the container document114A by copying the text, but not other elements, from the container document114A.

In the illustrated example200, the container document114A may be represented as a data sequence204A. The data sequence204A is shown as laid out continuously in memory. Each text character and embedded object202in the data sequence204A may be referenced by an index206A into the data sequence204in memory. For instance, the character S′ may be referenced at index206A location “0”, the embedded object202may be referenced at index206A location “6”, and the character ‘x’ may be referenced at index206A location “10”.

Similarly, the plaintext document114B is represented as a data sequence204B. Each text character in the data sequence204B may be referenced by its index206B into the data sequence204. Significantly, as there are no embedded objects202in the plaintext document114B, some of the index206B values into the plaintext document114B differ from those of the index206A values into the container document114A. For instance, the character ‘S’ may still be referenced at index206B location “0”, but the character ‘x’ may instead be referenced at index206A location “9”, the embedded object202no longer taking an index position before the ‘x’ character.

FIG.3illustrates an example300of a container document114A having a term to be located. As shown, the word “document” appears six times in the container document114A, at index206A offsets of 9, 45, 90, 151, 196, and 230. As the container document114A may not be searchable with a plain text search tool, however, these locations may be difficult to locate. This may be because, for example, there is no fast and accurate interface to capture the locations or index length of the embeds in the container document114A. Accordingly, the container document114A may be converted into a plaintext document114B instead. This conversion may involve copying the textual elements from the container document114A into the plaintext document114B, without also copying the embedded objects202.

FIG.4illustrates an example400of use of a text search tool on the plaintext document114B to locate the term. As noted above, the textual search tool may not be operable on the container document114A but may be operable on the plaintext document114B. This may be the case, for example, due to limitations in the interface available for accessing the container document114A. In an example, the application programming interface (API) used to access the data in the container document114A may allow for access by index206A or by range of indexes in the container document11A, but not to the raw underlying memory data sequence204A used by the container document114A.

Referring more specifically to the example400, the search may be performed for the word “document.” This word appears six times in the plaintext document114B, beginning at the index206B offsets of 9, 45, 88, 148, 192, and 226. As the embedded objects202are not included in the plaintext document114B, the index206B offsets for the located elements into the plaintext document114B are different form the index206A offsets of the terms into the container document114A. If the index206B offsets into the plaintext document114B are used as offsets into the container document114A, incorrect data within the container document114A may be retrieved. Accordingly, index206B locations for elements located by the textual search tool in the plaintext document114B may be unusable with the index206A into the container document114A.

(It should be noted that it may be possible to determine the offset length of the embedded objects202into the container document114A and add those values to the index206B values. This may allow for the adjustment of the index206B values back into the index206A values. However, such an approach involves the ability to identify the exact locations of the embedded objects202within the container document114A, as well to identify the offset lengths (which may be more than one character unit) of each of the embedded objects202within the container document114A. This information on the offset length of the embedded objects202into the container document114A may be difficult to determine or may be opaque to the user or otherwise not be exposed from the API used to access the contents of the container document114A.)

FIG.5illustrates an example500of the identified terms in the plaintext document114B being referenced by relative location into the plaintext document114B. As shown, an example definition of the relative location may be based on a relatively more stable offset into the container document114A, such as paragraph number (as opposed to character position). For instance, the relative locations may be specified by paragraph number and occurrence number within the paragraph. The index206B offsets may be converted into the relative location format, for instance, by counting the number of occurrences of each term from the beginning of the paragraph to the located element. As shown, the six identified terms may instead be represented as “paragraph 1, occurrence 1,” “paragraph 1, occurrence 2,” “paragraph 2, occurrence 1,” “paragraph 2, occurrence 2,” “paragraph 2, occurrence 3,” and “paragraph 2, occurrence 4.”

FIG.6illustrates an example600of the relative locations in the container document114A. Significantly, the same relative measures may be used for both the plaintext document114B and the container document114A. The index206A locations into the container document114A may then be computed for the relative locations by locating the corresponding paragraph number within the container document114A and then searching, within that paragraph, for the number of that occurrence within the container document114A.

Accordingly, search tools that are incompatible with the container document114A may be utilized to provide complex textual search techniques, while avoiding issues with computation of the correct index206A within the container document114A. Moreover, the search operations that are represented as relative locations may be immune to minor changes in the container document114A that can occur between when the search was performed and when a term is to be located in the container document114A. For instance, additional text may have been inserted into the paragraph before a term, and/or text may have been deleted from the paragraph including the term. In either case, these edit operations would affect the index206A location of the term within the paragraph. However, if these minor changes to the container document114A do not affect the paragraph number or occurrence number of the term within the paragraph, the term may easily be located at the correct index206A into the container document114A.

FIG.7illustrates an example process700for the efficient plain-text analysis of complex document formats. In an example, the process700may be performed by the processor104of the computing device102executing the applications116on documents114maintained to the storage106.

At operation702, the computing device102converts the container document114A into the plaintext document114B. In one example, the documents114may include documents114in the Office Open XML format. The computing device102may generate the plaintext document114B from the container document114A by copying the text from the container document114A, but not other elements such as embedded objects202from the container document114A.

At operation704, the computing device102analyzes the plaintext document114B. In an example, the computing device102executes one or more textual analysis operations on the plaintext document114B. These may include, as some examples, regular expression searches of the plaintext document114B or other textual searching or processing of the plaintext document114B.

At operation706, the computing device102identifies data elements of interest as indices206B into the plaintext document114B. In an example, these data elements may be search results of the analysis performed at operation704.

At operation708, the computing device102represents the locations of the data elements as relative locations into the plaintext document114B. For instance, an example definition of the relative location may be based on a relatively more stable offset into the container document114A, such as paragraph number (as opposed to character position). This relative locations may be specified by paragraph number and occurrence number within the paragraph, in an example. The index206B offsets may be converted into the relative location format by counting the number of occurrences of each term from the beginning of the paragraph to the located element. In other examples, this occurrence number may be computed as a count from the end of the paragraph, as opposed to from the beginning of the paragraph. Other relative location measures may also be used. For instance, indexes may be computed from the beginning of sentences in another example. Or, indexes may be computed from any of a set of common English stop words, in another example.

At operation710, the computing device102maps the relative locations into the plaintext document114B into index206A locations into the container document114A. The index206A locations into the container document114A may then be computed for the relative locations by locating the corresponding paragraph number within the container document114A and then searching, within that paragraph, for (as an example) the number of that occurrence within the container document114A. Thus, search tools that are incompatible with the container document114A may be utilized to provide complex textual search techniques, while avoiding issues with offset computation of the index206A within the container document114A. For example, using the mapped location, the string of the data elements of interest may be highlighted in a display of the first document. This may be done, e.g., using the opaque document114API as the correct offset is now known. After operation710, the process700ends.

In sum, by converting the container document114A into a plaintext document114B, powerful tools for locating textual elements within a plaintext document114B may be used on the container document114A. Moreover, by conversion of the located indexes206B into the plaintext document114B into relative locations and then into indexes206A into the container document114A, the locations of elements found in the plaintext document114B may be identified in the container document114A. Such an approach may be especially useful for opaque document114APIs, such as the document interface available by the Microsoft Word® word processor, which allows for access to the document by index, but lacks advanced search facilities or available information with respect to how embedded objects202may affect the indexes into the document114.