Document categorization by word length distribution analysis

• US 5,909,680 A
• Filed: 09/09/1996
• Issued: 06/01/1999
• Est. Priority Date: 09/09/1996
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Inventors: Hull, Jonathan J.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): MILLS, JOHN G
• Application Number:
  US08/709,707
• Time in Patent Office: 995 Days
• Field of Search: 707/6, 707/104, 707/7
• US Class Current: 1/1
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system and method for efficient document categorization are disclosed. In one embodiment, word length distribution information is used as a basis for categorization. Greater than 90% accuracy in classification may be achieved in, e.g., distinguishing newspaper articles from scientific journal articles. Word length distribution information may be developed without optical character recognition (OCR), permitting use of degraded document images.

Claims

1. A computer-implemented method for categorizing digitized documents comprising the steps of:

providing an electronic representation of an image of a document;

developing word length distribution information of said image from said electronic representation wherein said word length distribution information includes a document feature vector characterizing said document, said document feature vector comprises elements representative of distribution of estimates of word lengths, said elements comprise conditional probabilities of words of A characters proximate to words of B characters, for a plurality of values of A and B; and

categorizing said document responsive to said word length distribution information and word length distribution information for representative categories of documents.

2. The method of claim 1 wherein said conditional probabilities include, for a plurality of values of A and B, joint probabilities of a word of A characters and a following word of B characters.

3. The method of claim 1 wherein said conditional probabilities include, for a plurality of values of A and B, transitional probabilities that given a word of A characters, a word of B characters follows after said word of A characters.

4. The method of claim 1 wherein said conditional probabilities include 0th order probabilities for word length estimates.

5. The method of claim 1 wherein said conditional probabilities include 1st order probabilities for word length estimates.

6. The method of claim 1 wherein said conditional probabilities include 2nd order probabilities for word length estimates.

7. The method of claim 1 wherein said categorizing step comprises:

comparing said document feature rector to a set of feature vectors for said representative categories of documents; and

assigning a category to said document based on a feature vector of said set most similar to said document feature vector.

8. The method of claim 1 wherein said developing step comprises:

invoking optical character recognition to obtain word length estimates.

9. The method of claim 1 wherein said developing step comprises:

estimating pixel lengths of words of said document image to obtain word length estimates.

10. A computer program product for categorizing documents comprising:

code for providing an electronic representation of an image of a document;

code for developing word length distribution information of said image from said electronic representation wherein said word length distribution information includes a document feature vector characterizing said document, said document feature vector comprise elements representative of distribution of estimate of word lengths, said elements comprise conditional probabilities of words of A characters proximate to words of B characters, for a plurality of values of A and B;

code for categorizing said document responsive to said word length distribution information; and

a computer-readable storage medium for storing said codes.

11. The product of claim 10 wherein said conditional probabilities include, for plurality of values of A and B, joint probabilities of a word of A characters and a following word of B characters.

12. The product of claim 10 wherein said conditional probabilities include, for plurality of values of A and B, transitional probabilites that after given a word of A characters, a word of B characters follows after said word of A characters.

13. The product of claim 10 wherein said conditional probabilities include 0th order probabilities for word length estimates.

14. The product of claim 10 wherein said conditional probabilities include 1st order probabilities for word length estimates.

15. The product of claim 10 wherein said conditional probabilities include 2nd order probabilities for word length estimates.

16. The product of claim 10 wherein said categorizing code comprises:

code for comparing said document feature vector to a set of feature vectors for swaid representative categories of documents; and

code for assigning a category to said document based on a feature vector of said set most similar to said document feature vector.

17. The product of claim 10 wherein said developing code comprises:

code for invoking optical character recognition to obtain word length estimates.

18. The product of claim 10 wherein said developing code comprises:

code for estimating pixel lengths of words of said document image to obtain word length estimates.

19. A computer-implemented method for categorizing digitized documents comprising the steps of:

providing an electronic representation of an image of a document;

developing word length information of said image from said electronic representation, wherein said word length information includes a document feature vector characterizing said document, said document feature vector comprises elements representative of word length estimates, said elements comprise statistics of word lengths of a plurality of words located within a predetermined proximity; and

categorizing said document responsive to said word length information and word length information for representative categories of documents.

20. The method of claim 19 wherein said conditional probabilities include joint probabilities of a word of length A and a following word of length B, for a plurality of values of A and B.

21. The method of claim 19 wherein said conditional probabilities include transitional probabilities that given a word of length A a word of length B follows after said word of length A, for a plurality of values of A and B.

22. The method of claim 19 wherein said conditional probabilities include 1st order probabilities for word length estimates.

23. The method of claim 19 wherein said conditional probabilities 2nd order probabilities for word length estimates.