Method of identifying data type and locating in a file

• US 5,991,714 A
• Filed: 04/22/1998
• Issued: 11/23/1999
• Est. Priority Date: 04/22/1998
• Status: Expired due to Term

• Current Assignee: The United States of America As Represented By The National Security Agency
• Original Assignee: The United States of America As Represented By The Director National Security Agency
• Inventors: Shaner, Richard Allen
• Primary Examiner(s): Isen, Forester W.
• Assistant Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US09/064,063
• Time in Patent Office: 580 Days
• Field of Search: 704/1, 704/9, 704/10, 707/530, 707/531, 707/532, 707/102, 382/229
• US Class Current: 704/9
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

A method of identifying the types of data contained in an electronic file of unknown data type by gathering exemplary files of each data type of interest; counting the number of unique n-grams within each exemplary file; determining a weight for each unique n-gram; listing the unique n-grams in the exemplary files of a particular data type by descending magnitude of weight for each data type of interest; selecting the top m weighted n-grams and their associated weights; establishing a threshold for each data type of interest; selecting a length of data from the electronic file; listing every n-gram in the data selected; giving each listed n-gram, that was also selected, the weight that that n-gram was given for each data type of interest; summing the weights given to each n-gram according to data type; comparing the sums to the thresholds established in order to determine the types, if any, of the selected data; recording the location of the selected data if it is of a data type of interest; stopping if the number of selected lengths of data reached a user-definable number, otherwise selecting another length of data from the file that is the same length as that selected previously, where the newly selected data overlaps with the previously selected data by at least one position; and repeating the steps from listing every n-gram to stopping using the newly selected data.

Claims

1. A method of identifying the type of data contained in an electronic file of unknown data type, comprising the steps:

a) gathering at least one exemplary file of each data type of interest;

b) counting the number of unique n-grams within each at least one exemplary file,

where n is user-definable range of integers;

c) determining a weight for each unique n-gram for each data type of interest as follows;

space="preserve" listing-type="equation">w.sub.ti .tbd.(log(K(x.sub.ti /N.sub.t)+1))×

((1/log N.sub.t)(Σ

(p.sub.tji log(1/p.sub.tij))))×

(1-((1/logL)(Σ

(p.sub.ti log(1/p.sub.ti))))).sup.d,

where w_ti is the weight of a particular n-gram i for a particular data type t;

where K is a constant that scales the term (x_ti /N_t) away from unity;

where N_t is the number of documents of type t;

where x_tji is the number of occurrences of an n-gram i in exemplary document j of type t divided by the total number of bytes in document j;

where x_ti =Σ

x_tji, summed from j=1 to j=N_t ;

where p_tji.tbd.x_tji /x_ti ;

where Σ

(p_tji log(1/p_tij)) is summed from j=1 to j=N_t ;

where L is the number of data types of interest;

where x_i =Σ

x_ti, summed from t=1 to t=L;

where p_ti .tbd.x_ti /x_i ;

where Σ

(p_ti log(1/p_ti)) is summed from t=1 to t=L; and

where d is a positive real number that controls the concavity of the term that contains d;

d) listing the unique n-grams in the at least one exemplary file of a particular data type of interest in order of descending magnitude of weight for each data type of interest;

e) selecting the top m weighted n-grams and their associated weights from each list generated in the last step, where m is a user-definable integer;

f) establishing a user-definable threshold for each data type of interest for determining data type;

g) selecting a user-definable length of data from the electronic file of unknown data type;

h) listing every n-gram in the data selected in the last step, where n has the same range of integer values as in step (b);

i) giving each n-gram listed in the last step that was also selected in step (e) the weight that that n-gram was given in step (c) for each data type of interest;

j) summing the weights given to each n-gram in the last step according to data type;

k) comparing the sums in the last step to the thresholds established in step (f) in order to determine the data types, if any, of the selected data;

l) recording the location of the selected data if it is determined to be of any data type of interest;

m) stopping if the number of selected lengths of data reached a user-definable number of selected lengths of data, otherwise selecting another length of data from the file that is the same length as the data selected previously, where the data selected in this step overlaps with the previously selected data by at least one position; and

n) repeating step (h) through step (m) using the data selected in the last step.

2. The method of claim 1, wherein said step of gathering at least one exemplary file of each data type of interest is comprised of gathering at least one exemplary file of each data type of interest wherein said data type of interest is selected from the group consisting of any language, any wordprocessor, any executable code, and any data compression scheme.

3. The method of claim 1, wherein said step of counting the number of unique n-grams is comprised of counting the number of unique n-grams within each at least one exemplary file, where n is a range of integers from 1 to 8.

4. The method of claim 1, wherein said step of determining the weight of each unique n-gram where K is a constant is comprised of determining the weight of each unique n-gram where K is 10⁵.

5. The method of claim 1, wherein said step of determining the weight for each unique n-gram where d is a positive real number is comprised of the step of determining the weight for each unique n-gram where d is 3.

6. The method of claim 1, wherein said step of selecting the top m weighted n-grams and their associated weights for each list is comprised of selecting the top 2000 weighted n-grams and their associated weights for each list.

7. The method of claim 1, wherein said step of selecting a user-definable length of data from the file is comprised of selecting 250 bytes of data from the beginning of the file.

8. The method of claim 1, wherein said step of selecting a user-definable length of data from the electronic file of unknown data type is comprised of selecting the entire electronic file of unknown data type.

10. The method of claim 1, wherein said step of recording the location of the selected data is comprised of recording the location of the selected data as being the center of the selected data.

11. The method of claim 2, wherein said step of counting the number of unique n-grams is comprised of counting the number of unique n-grams within each at least one exemplary file, where n is a range of integers from 1 to 8.

12. The method of claim 11, wherein said step of determining the weight of each unique n-gram where K is a constant is comprised of determining the weight of each unique n-gram where K is 10⁵.

13. The method of claim 12, wherein said step of determining the weight for each unique n-gram where d is a positive real number is comprised of the step of determining the weight for each unique n-gram where d is 3.

14. The method of claim 13, wherein said step of selecting the top m weighted n-grams and their associated weights for each list is comprised of selecting the top 2000 weighted n-grams and their associated weights for each list.

15. The method of claim 14, wherein said step of selecting a user-definable length of data from the file is comprised of selecting 250 bytes of data from the beginning of the file.

9. The method of step 1, wherein said step of stopping if the number of selected lengths of data reached a user-definable number of selected lengths of data is comprised of stopping if the end of the electronic file is reached, otherwise selecting another length of data that is one byte position to the right of the previously selected length of data.

16. The method of step 15, wherein said step of stopping if the number of selected lengths of data reached a user-definable number of selected lengths of data is comprised of stopping if the end of the electronic file is reached, otherwise selecting another length of data that is one byte position to the right of the previously selected length of data.

17. The method of claim 16, wherein said step of recording the location of the selected data is comprised of recording the location of the selected data as being the center of the selected data.