Granted Patent B1

US 7,080,314 · App. 09/595,719 · Granted Jul 18, 2006

Abstract

Claims (43)

1. A document descriptor determination method comprising the steps of:

generalizing input sequences associated with a document to develop general sequences, said input sequences reflecting the structure of a document;

factoring said input sequences and said general sequences to develop factored sequences;

selecting a document descriptor from said input sequences, said general sequences, and said factored sequences using minimum descriptor length (MDL) principles.

2. The method of claim 1 , wherein said selecting step comprises the steps of:

encoding said input sequences, said general sequences, and said factored sequences; and

selecting a document descriptor which encompasses all of said input sequences and exhibits a minimum MDL cost.

3. The method of claim 2 , wherein said encoding step employs an algorithm which applies a set of rules comprising:

seq(D,s)=ε if D=s, if D does not contain metacharacters;

seq(D 1 . . . D k , s 1 . . . s k )=seq(D 1 ,s 1 ) . . . seq(D k ,s k );

seq(D 1 | . . . |D m ,s)=i seq(D i ,s);

seq(D*,s 1 . . . s k )={k seq(D,s 1 ) . . . seq(D,s k ) if k>0; 0 otherwise};

wherein D is a sequence of symbols, s is a sequence, and i is an index of a regular expression that the corresponding sequence s matches, wherein log m bits are needed to encode index i.

4. The method of claim 3 , wherein said minimum MDL cost is determined by employing an algorithm to solve a facility location problem (FLP), said FLP modified to compute said minimum MDL cost of potential document descriptors.

5. The method of claim 4 , wherein said document descriptor is a document type descriptor (DTD), and said document is an eXtensible Markup Language (XML) document.

6. The method of claim 5 , wherein said minimum MDL cost comprises summing a first length of bits describing the DTD and a second length of bits for encoding the sequences.

7. A document descriptor determination method comprising the steps of:

generalizing input sequences to develop general sequences, said input sequences reflecting the structure of data within a document;

selecting a document descriptor from said input sequences and said general sequences using minimum descriptor length (MDL) principles.

8. The method of claim 7 , wherein said selecting step comprises the steps of:

encoding said input sequences and said general sequences; and

selecting a document descriptor which encompasses all of said input sequences and exhibits a minimum MDL cost.

9. The method of claim 8 , wherein said encoding step employs an algorithms which applies a set of rules comprising:

seq(D,s)=ε if D=s, if D does not contain metacharacters;

seq(D 1 . . . D k , s 1 . . . s k )=seq(D 1 ,s 1 ) . . . seq(D k ,s k ), if D is a concatenation of D 1 . . . D k ;

seq(D 1 | . . . |D m ,s)=i seq(D i ,s);

seq(D*,s 1 . . . s k )={k seq(D,s 1 ) . . . seq(D,s k ) if k>0; 0 otherwise};

wherein D is a sequence of symbols, s is a sequence, and i is an index of a regular expression that the corresponding sequence s matches, wherein log m bits are needed to encode index i.

10. The method of claim 9 , wherein said minimum MDL cost is determined by employing an algorithm to solve a facility location problem (FLP), wherein said FLP is modified to compute said minimum MDL cost of potential document descriptors.

11. The method of claim 10 , wherein said document descriptor is a document type descriptor (DTD), and said document is an extensible Markup Language (XML) document.

12. The method of claim 11 , wherein said minimum MDL cost comprises summing a first length of bits describing the DTD and a second length of bits for encoding the sequences.

13. The method of claim 7 , further comprising the step of:

factoring said input sequences and said general sequences to develop factored sequences, wherein said factored sequences are available for said step of selecting.

14. A document descriptor determination method comprising the steps of:

generalizing input sequences, said generalizing step comprising the steps of:

discovering OR patterns among said input sequences, and

discovering sequence patterns among said input sequences and OR patterns; and

selecting a document descriptor from said input sequences and said general sequences.

15. The method of claim 14 , wherein said discovering OR patterns step comprises the step of partitioning said input sequences.

16. The method of claim 15 , further comprising the steps of:

factoring said input sequences and said general sequences to develop factored sequences, wherein said factored sequences are available to said step of selecting.

17. The method of claim 16 , wherein said step of selecting employs minimum descriptor length (MDL) principles.

18. The method of claim 14 , wherein said document descriptor is a document type descriptor (DTD) and said document is an extensible Markup Language (XML) document.

Assignments (7)