Method and apparatus for identifying words described in a portable electronic document

• US 5,832,530 A
• Filed: 06/27/1997
• Issued: 11/03/1998
• Est. Priority Date: 09/12/1994
• Status: Expired due to Term

• Current Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Paknad, Mohammad Daryoush, Ayers, Robert M.
• Primary Examiner(s): Burwell, Joseph R.
• Application Number:
  US08/884,003
• Time in Patent Office: 494 Days
• Field of Search: 707/500, 707/530
• US Class Current: 715/235
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

A method and apparatus for identifying words stored in a portable electronic document. A digital computation apparatus stores a page of a document including characters in text segments that have not been identified as words. A word identifying mechanism analyzes the text segments of the page and stores the text segments as text objects in a linked list. The word identifying mechanism identifies words from the text objects in the linked list by analyzing the text objects for word breaks and by analyzing gaps between text objects using position data associated with the text segments. The identified words are stored in a word list and are sorted if necessary. A method of the present invention receives a text segment from a page of a document having multiple text segments and associated position data, including x and y coordinates for each text segment. A text object is created for each text segment, and the text objects are entered into a linked list. Words are then identified from the linked list by analyzing the text objects for word breaks and by analyzing gaps between text objects using the associated position data. Words that are identified in the text objects are added to a word list. The above steps are repeated until the end of the page is reached. The method and apparatus can be used for searching for words in a portable electronic document.

Claims

1. A method for identifying words in a document comprising:

(a) retrieving a text segment including its x,y position from a portable electronic document that has a page including a plurality of characters that have been identified as characters but not identified as words and a plurality of text segments and associated position data;

(b) creating a text object from each text segment and entering the text object into a linked list of text objects;

(c) identifying words from the linked list by analyzing the text object for word breaks and by analyzing a gap between the text object with a prior text object using the associated position data;

(d) adding identified words to a word list; and

(e) repeating steps (a) to (e) until the end of the page is reached.

2. A method as recited in claim 1 wherein the x, y position is stored in the object associated with the text segment.

3. A method as recited in claim 1 wherein said step of creating a text object includes reassigning encoded characters of said text segments utilizing a re-assignment table and storing said reassigned characters in said text object.

4. A method as recited in claim 1 wherein said word is identified by finding a word break character in a text object.

5. A method as recited in claim 1 wherein said word is identified by finding a gap having a size greater than a threshold size between adjacent text objects.

6. A computer program product for programming a data processing apparatus to identify words on a page of a portable electronic document, comprising instructions to:

read from the portable electronic document a description of the intended appearance of a page of the document when rendered, the description including text segments having one or more characters to be rendered on the pages each text segment associated with position information on the page, the position information of the text segments defining a display order that is independent of a storage order of the text segments;

using the position information of the text segments to distinguish characters that are part of the same word from characters that are not part of the same word; and

collect characters that are part of the same word.

7. The product of claim 6, wherein the instructions to collect the characters into words comprise instructions to:

identify words having characters in the text segment by using the position information of the text segment to compute the positions of text segment characters on the page.

8. The product of claim 6, wherein the instructions to use the position information comprise instructions to:

identify as words closely-spaced characters having a gap between them of less than a predetermined threshold; and

store identified words in a word list.

9. The product of claim 6, wherein the instructions to use the position information comprise instructions to:

find a word break character; and

identify words based on the position of the word break character.

10. A system for identifying words in a page of a portable electronic document, comprising:

a data processing apparatus operable to store a page of a portable electronic document as a file including a plurality of characters that have not been identified as words, wherein each character is at least part of a text segment that has associated position information indicating where the text segment is to be displayed; and

a word identifying program implemented on the data processing apparatus for analyzing the text segments together with their position data to distinguish characters that are part of the same word from characters that are not part of the same word to create a list of words in the page.

11. A system as recited in claim 10, further comprising:

a scattered document identification program implemented on the data processing apparatus for determining whether the page includes scattered characters, the word identifying program performing the analyzing if the page includes scattered characters.

12. A system for identifying words as recited in claim 10, wherein each text segment is associated with a single display command, and wherein the position information of each text segment includes an x coordinate and y coordinate that define an x,y coordinate pair indicating where the text segment is to be displayed.

13. A system for identifying words as recited in claim 10, wherein the word identifying program further comprises scattered document identification means and sorting means for sorting the word list if the scattered document identification means determines that the page requires sorting.

14. A system for identifying words as recited in claim 13, wherein each word in the word list has an associated x coordinate and y coordinate that define an x,y coordinate pair indicating where the word is to be displayed on a displayed page, and wherein the sorting means sorts the words in said word list first by the y coordinates and then by the x coordinates.

15. A system for identifying words as recited in claims 10, wherein the word identifying program stores a text segment as a text object in a linked list of text objects.

16. A system for identifying words as recited in claim 15, wherein associated information describing the text segment, including x,y coordinate pair information, is stored in the text object.

17. A system for identifying words as recited in claim 16, wherein the word identifying program concatenates words in the word list that are positioned within a threshold distance of each other and words that include a hyphen character at the end of the word.

18. A system for identifying words as recited in claim 17, wherein each text object has an associated bounding box, wherein each text object indicates whether it is a rotated text object, and wherein at least portions of adjacent rotated text objects are added as a word to the word list by the word identifying program when their bounding boxes intersect or are separated by less than a predetermined gap.

19. A system for identifying words as recited in claim 18, wherein the word identifying program identifies a word by finding a word break character in the text objects.

20. A system for identifying words as recited in claim 19, wherein the word identifying program identifies a word by finding a gap having a size greater than a threshold size between adjacent text objects.

21. A system for identifying words as recited in claim 20, wherein the word identifying program detects the gap by analyzing the spatial distance between adjacent text objects in the linked list by utilizing coordinates of the text segments stored in the text objects.

22. A system for identifying words as recited in claim 21, wherein the word identifying program adds at least a portion of adjacent text objects as a word to the word list when the gap between the adjacent text objects is below the threshold size.