Method and means of matching documents based on text genre

• US 6,178,417 B1
• Filed: 06/29/1998
• Issued: 01/23/2001
• Est. Priority Date: 06/29/1998
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Syeda-Mahmood, Tanveer F.
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US09/106,544
• Time in Patent Office: 939 Days
• Field of Search: 707/3-5, 707/6, 707/100, 707/515, 382/181, 700/223, 704/1-10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method for matching documents based on spatial layout of regions based on a shape similarity model for detecting similarity between general 2D objects. The method uses the shape similarity model to determine if two documents are similar by logical region generation in which logical regions are automatically derived from information in the documents to be matched, region correspondence, in which a correspondence is established between the regions on the documents, pose computation in which the individual transforms relating corresponding regions are recovered, and pose verification in which the extent of spatial similarity is measured by projecting one document onto the other using the computed pose parameters.

Claims

1. A computer implemented method of developing text genre from a collection of documents, the method comprising the steps of:

(a) extracting at least one key string from one document;

(b) extracting at least one key string from another document;

(c) forming a sequence of matching strings therefrom which preserve reading order;

(d) using a confusion class for each character of each extracted string;

(e) finding the longest common subsequence of matching strings to form an initial estimate of text genre; and

(f) repeating steps (b) to (e) until a definition of the text genre is developed that captures the spatial structure of key strings as an LCS (longest common sequence) of matching key string sequences.