Method for matching elements of two groups

• US 5,737,594 A
• Filed: 07/05/1995
• Issued: 04/07/1998
• Est. Priority Date: 07/05/1994
• Status: Expired due to Fees

• Current Assignee: Trustus Pty., Ltd.
• Original Assignee: Trustus Pty., Ltd.
• Inventors: Williams, Ross Neil
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Von Buhr, Maria N.
• Application Number:
  US08/525,281
• Time in Patent Office: 1,007 Days
• Field of Search: 395/606
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method for matching-elements of two groups of data objects whose elements do not necessarily exactly match. The method consists of examining successively more abstract projections of the two groups until exact matches occur within elements of the same group, or between elements of the different groups or until there are no longer any more abstract projections to apply. Both random access end sequential embodiments are described.

Claims

1. A method for matching elements of two groups of data elements, comprises the steps of:

a. forming an abstract representation of each of the groups according to one of a set of abstraction methods;

b. classifying as UNMATCHED each unclassified element of said abstract representation that is identical to any other element of said abstract representation within its own group;

c. classifying as UNMATCHED each unclassified element of said abstract representation in each group that is identical to an element of said abstract representation of the other group that is already classified as MATCHED or UNMATCHED;

d. classifying as MATCHED, and identifying a match between, each pair of identical elements of said abstract representation such that one element of the pair is in one group and the other element is in the other group and each element of the pair is not classified as MATCHED OR UNMATCHED;

e. repeating steps a through d until all elements of both groups have been classified as MATCHED or UNMATCHED, or until all abstraction methods in said set of abstraction methods have been used;

f. classifying as UNMATCHED all elements that are not already classified as MATCHED or UNMATCHED.

2. The method in accordance with claim 1 wherein the data elements are file specifications and one of the set of abstraction methods is the removal of the "version number" of the file specification.

3. The method in accordance with claim 1 wherein the data elements are file specifications and one of the set of abstraction methods is the normalization of the alphabetic case of the file specification.

4. The method in accordance with claim 1 wherein the data elements are file specifications and one of the set of abstraction methods is the removal of any trailing "." of file specification.

5. The method in accordance with claim 1 wherein the data elements are file specifications and one of the set of abstraction methods is the truncation of the file specification extension to a predetermined number of bytes.

6. The method in accordance with claim 1 wherein the data elements are file specifications and one of the set of abstraction methods is the truncation or the file specification identifier to a predetermined number of bytes.

7. A method for matching elements of two ordered lists X and Y formed from two groups of data elements, comprises the steps of:

a. initializing an index x into the first list X, and an index y into the second list Y, setting them both to 1;

b. classifying as UNMATCHED, elements x . . . x+n (where n>

=0) such that each element x . . . x+n-1 is identical to either its predecessor or successor element, and element x+n is not identical to its predecessor or successor element, and incrementing x by n;

c. performing step (b) for y in the second group;

d. if one or both of x and y has run off the end of its list, skipping to step h;

e. if the distance d(X x!,Y y!) is at most a maximum distance T, and X x! and Y y! are closer to each other than either is to either X x+1! or Y y+1!, then classifying elements X x! and Y y! as MATCHED with each other, incrementing x and y by 1, and skipping to step b;

f. classifying the lower in the sort order of X x! and Y Y! as UNMATCHED and incrementing its corresponding index by 1;

g. repeating steps b to f until one or both of x and y has run off the end of its list;

h. classifying as UNMATCHED all elements that are not already classified as MATCHED or UNMATCHED.