Abstract:
A method and an apparatus for content identification and categorization of textual data is disclosed. Using the Burrows-Wheeler transform in conjunction with mapping techniques and statistical comparison, useful information can be extracted from textual documents. This information can be used to categorize, authenticate, and compare such documents, thereby leading to automated searching of databases of documents.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The invention relates to data manipulation and categorization in general, and specifically to processing of textual data for categorization, content identification and authentication. 
     2. Background Information 
     With the advent of the electronic age and the internet as a useful means for communication and storage of data, there is a need for systems for determining whether a given document was authored by a certain person, whether a given document is in a particular language, or what type of material a given document deals with. This is not well addressed by present methods of textual analysis. At best, currently it is possible to analyze a given document utilizing phrase or key word searches and then have a human look at the results of such analysis in an attempt to determine their authorship, content, or language. What is needed is a methodology that will produce a result that can be more readily analyzed by a computer without human intervention. Additionally, what is needed is a methodology that can look at frequency of character utilization, key word searches and frequency of occurrences of phrases all at once rather than looking at them discretely. 
     SUMMARY OF THE INVENTION 
     The present invention provides a method and apparatus for content identification and categorization of data. In one embodiment, a Burrows-Wheeler Transform is performed on a document of textual data to produce a set of transformed textual data. The transformed textual data is divided into a set of one or more intervals. The transformed textual data of that set of intervals is transformed to produce a pattern map. The pattern map is compared to a reference pattern map thereby producing an indication of whether the subject textual data is of a type corresponding to the reference pattern map. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present invention is illustrated by way of example and not limitation in the accompanying figures. 
     FIG. 1 illustrates a Burrows-Wheeler Transform. 
     FIG. 2 is a flow chart illustrating one embodiment of the present invention. 
     FIG. 3 is a flow chart illustrating an alternative embodiment of the present invention. 
     FIG. 4A is an illustration of a small number of intervals within a given textual document. 
     FIG. 4B is an illustration of the textual document of FIG. 4A with a large number of intervals. 
     FIG. 4C is an illustration of the textual document of FIG. 4A where the intervals overlap. 
     FIG. 4D is an illustration of the textual document of FIG. 4A where the intervals are of variable length. 
     FIG. 5A illustrates an exemplary zero pattern map. 
     FIG. 5B is an exemplary pattern map generated from the data used in the Burrows-Wheeler Transform of FIG.  1 . 
     FIG. 6A illustrates results reduced to a single number for correspondence between various textual documents in the English language. 
     FIG. 6B illustrates results reduced to a single number for correspondence between several textual documents derived from the same source in different languages. 
     FIG. 7 is a plot of the occurrences for the letter H within text from the Bible and from two of Shakespeare&#39;s plays. 
     FIGS. 8A,  8 B,  8 C,  8 D,  8 E,  8 F,  8 G and  8 H represent portions of exemplary pattern maps. 
     FIG. 9 is a plot of the occurrences of the letter H in four different languages of the same textual document. 
     FIGS. 10A,  10 B,  10 C,  10 D,  10 E,  10 F,  10 G and  10 H represent portions of exemplary pattern maps. 
     FIG. 11 is an exemplary mapping table for mapping an ASCII character to the corresponding column in a pattern sheet or pattern map. 
     FIG. 12 illustrates a computer system that may be used in one embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION 
     FIG. 1 illustrates a Burrows-Wheeler Transform as described by Burrows and Wheeler (M. Burrows and D. J. Wheeler,  A Block - sorting Lossless Data Compression Algorithm , Digital Systems Research Center Research Report 124, http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/src-rr-124.html). Turning to FIG. 1, array  100  shows text  122  sorted by the first letter of each possible permutation of text  122  and each entry of array  100  is sorted in dictionary order such that entry  104  comes after entry  102  and before entry  106  according to the standard English dictionary. Column  130 , the last column of each row of array  100  represents the Burrows-Wheeler Transform of data  122 . 
     The Burrows-Wheeler Transform can be performed in a variety of ways known in the art. One method is disclosed in a copending application entitled “Method and Apparatus for Dictionary Sorting” filed on the same day as this application, which is hereby incorporated by reference. 
     FIG. 2 is a flow chart illustrating one embodiment of the present invention. In this embodiment data  200  is an original textual document to be categorized or otherwise evaluated. A Burrows-Wheeler Transform  210  is performed on data  200  thereby resulting in Burrows-Wheeler Transformed data  220 . Mapping  230  is performed on the Burrows-Wheeler Transformed data  220  to produce map  240 . Statistical comparison  250  is performed on map  240  to achieve result  260 . 
     Result  260  may consist of a variety of information regarding content. For example, result  260  may be an expression of whether data  200  in the original document was authored by a particular person, whether data  200  is of a particular language, or whether data  200  is similar to a particular type of document. Result  260  can be embodied in a variety of forms including a single number, a table, or a two or three-dimensional graphical representation such as a histogram or curve. Furthermore, result  260  can be shaped by statistical comparison  250  and mapping  230  to represent a particular subset of data  200  or it can be set up to represent equally all of data  200 . 
     FIG. 3 represents an alternative embodiment of the present invention. Data  300  represents data in a textual document which for purposes of discussion may be the same as data  200  of FIG. 2. A Burrows-Wheeler Transform  310  is performed on data  300  to produce Burrows-Wheeler Transformed data  320 . Mapping  330  is performed on Burrows-Wheeler Transformed data  320  to produce map  340 . Updating class pattern  350  is performed to change class pattern map  360 . Statistical comparison  380  compares comparison pattern map  370  with pattern map  340  to produce final results  390 . It should be noted that comparison pattern map  370  can be the same as class pattern map  360  or it can be something entirely different. For example, class pattern map  360  may represent a map typical of the works of Shakespeare if original data  300  was supposedly one of Shakespeare&#39;s plays, for instance  Romeo and Juliet . Additionally, it could be a pattern map for Sir Francis Bacon, and the works that he produced if someone were attempting to determine whether Shakespeare&#39;s works were written by Bacon. Final results  390  can, similarly to results  260  of FIG. 2, take the form of a single number expressing a correlation, it can take the form of an array of numbers similar to a pattern map such as pattern map  340 . Final results  390  could also take the form of a two-dimensional or three-dimensional graph. 
     Turning to FIGS. 4A through 4D, each illustrates a different possible selection of intervals within a document. FIG. 4A illustrates a small number of intervals in the document. Typically, each of intervals  401   a ,  402   a ,  403   a ,  404   a ,  405   a ,  406   a  may be the same length, or the same number of characters. However, this is not an absolute requirement and it is not strictly met within this example. FIG. 4B illustrates a large number of intervals in the document. Again, typically each interval would be the same size as each other interval. FIG. 4C illustrates one example of overlapping intervals. In this case, interval  401   c  overlaps with interval  402   c . Interval  402   c  overlaps with both  401   c  and  403   c . Interval  403   c  overlaps with both intervals  402   c  and  404   c , and interval  404   c  overlaps with both  403   c  and  405   c . Finally, FIG. 4D illustrates a case where the chosen intervals are not of the same length, as interval  403   d  is significantly larger than any of intervals  401   d ,  402   d ,  404   d , or  405   d . This results in emphasis on the ends of the document for statistical analysis purposes. 
     Turning to FIGS. 5A and 5B, both illustrate exemplary pattern sheets appropriate for textual data  122  from FIG.  1 . FIG. 5A is a zero pattern sheet. The pattern sheet includes a column for each character that is to be counted and a row for each interval L that textual data  122  is divided into. At the intersection of each column and each row is an entry. In the case of a zero pattern sheet, each entry is zero. 
     FIG. 5B is a pattern sheet for textual data  122 . In this case, each entry holds the number of characters, corresponding to the column for that entry, that were found within the interval corresponding to the row for that entry. In this case, the interval corresponding to row zero (‘0’ in the ‘L’ column) includes the first three rows of the array of FIG. 1, namely rows  102 ,  104 , and  106 . The interval corresponding to row one (‘1’ in the ‘L’ column) includes the next three rows of the array of FIG. 1, namely rows  112 ,  114 , and  116 . Finally, the interval corresponding to row two (‘2’ in the ‘L’ column) includes the final three rows of the array of FIG. 1, namely rows  122 ,  124 , and  126 . Since there are ‘c’ characters in rows  102  and  106  of the Burrows-Wheeler transform of the text in FIG. 1, an entry of ‘2’ is located at the intersection of the ‘C’ column and the ‘0’ row of FIG.  5 B. Each of the other eight locations is derived in the same manner. 
     Typically, a pattern map is a normalized pattern sheet, but the two terms can be interchangeable, as both pattern sheets and pattern maps take the form of two dimensional arrays of numbers derived from a text document, and some pattern sheets would not require normalization to be transformed to pattern maps. 
     FIGS. 6A and 6B show the results of one method of comparing pattern maps generated from various documents using one embodiment of the method of the present invention. In both FIGS. 6A and 6B, the numbers are derived from comparing the ‘H’ columns of the pattern maps generated for the corresponding documents. FIG. 6A shows a comparison of four different documents to each other, the four documents being the Book of Joshua, Chapter 10 of the Bible, the Book of John, Chapter 20 of the Bible, Shakespeare&#39;s  Hamlet  and Shakespeare&#39;s  Romeo and Juliet . The metrics for generating such a comparison usually have a form of: 
     
       
         (Σa i (p i −r i ) b ) I/b   
       
     
     Normally, a i  and b are integers. As will be apparent to one skilled in the art, a i  can be set to different values for each i thereby assigning a weight to each interval. In this case, the L 2 -distance was applied to the ‘H’ columns of the appropriate maps to generate these numbers, the L 2 -distance having the form of:            2     ∑     (       p   i   2     -     r   i   2       )              (       ∑       p   i                   i                 n                   h       ′           ‵                   column              (       p   i     -     r   i       )     2       )                              
     In both expressions, p i  is an entry in the pattern map generated from the subject document and r i  is an entry in the pattern map generated from whatever the subject document is being compared to. Normally, entries in the pattern maps would be addressed in the form p ij  but in this case, each entry is in the ‘H’ column, so j is constant in this formula and therefore not shown. If the formula were applied to multiple columns, it might involve summing the results of the formula for each column, averaging these same results, or some other statistically meaningful method of combining the results. A formula for summing the results of multiple columns might look like this (L is the number of intervals):          ∑       for                 each                 j                 corresponding       to                 a                 column                 to                 be                 summed              (         2       ∑     i   =   0       L   -   1            (       p   ij   2     -     r   ij   2       )                (         ∑     i   =   0       L   -   1            p   ij       -     r   ij       )     2         )                            
     and a formula for averaging the results of multiple columns might look like this:          ∑       for                 each                 j                 corresponding       to                 a                 column                 to                 be                 summed              (         2       ∑     i   =   0       L   -   1            (       p   ij   2     -     r   ij   2       )                (         ∑     i   =   0       L   -   1            p   ij       -     r   ij       )     2         )                            
     Number of columns to be summed 
     In this case, the pattern map for what the subject document is being compared to is the pattern map for another document. For instance, the pattern maps used to generate the entry at the intersection of Shakespeare&#39;s  Hamlet  and Shakespeare&#39;s  Romeo and Juliet  would be the pattern maps generated from the two plays respectively. 
     The L 2 -distance may be applied to other columns within the pattern maps generated for each document, and further it may be applied to multiple columns within each pattern map. As can be seen though, in this example the ‘H’ column results in significant differences between comparisons of works from similar times (comparing the two Bible chapters or the two Shakespeare plays) and works from differing times (comparing a Bible chapter and a Shakespeare play). 
     Turning to FIG. 6B, this table shows the results of comparing pattern maps for Victor Hugo&#39;s  Les Miserables  as translated into different languages. In each case, the L 2 -distance was applied to the ‘H’ column of the various different translations. As expected, comparing a text to itself results in an L 2 -distance of zero, whereas comparing a text in one language to a text in another language, even though derived from the same work, results in a large L 2 -distance. 
     Other methods of comparing pattern maps and pattern sheets may be used. In particular, generation of a relative pattern sheet or pattern map from two pattern maps may be done by generating one entry in a new or third (R) pattern sheet given a first (P) and a second (Q) pattern sheet. Each entry may be determined as the difference between the entry of the first pattern sheet and the second pattern sheet with the equation: 
     
       
         R ij =P ij −Q ij   
       
     
     In this equation and the following one, P ij  and Q ij  represent the value or magnitude of the entry at the row and column corresponding to the values of i and j in the pattern map. A possibly more useful equation, which would generate an entry based on the proportion of the corresponding entries of each sheet to the total of all entries of each sheet is:          R   ij     =         P   ij       ∑     (   P   )         -       Q   ij       ∑     (   Q   )                                  
     where Σ(P) and Σ(Q) represent the total of all entries of the corresponding tables. Additionally, one might generate a relative pattern sheet where each entry was derived from the difference between the entries divided by the total of all entries for a corresponding column in each of the two sheets. 
     FIG. 7 illustrates a plot of the ‘H’ column in each of the pattern sheets for the two Chapters of the Bible and the two Shakespeare plays. Each column of the plot corresponds to an interval of the document, with the height of the column corresponding to the number of ‘H’s found in that interval. Also, note that these plots have been normalized by well known techniques. 
     FIGS. 8A through 8H are pattern sheets generated from the documents compared in FIG.  6 A. In each case, a set of 100 intervals were used, and while each character was broken out into its own column, such as ‘H’, the numerals were all treated as identical, the punctuation marks were grouped into three categories, all sets of continuous space characters were treated as identical, and other characters were treated as unidentified. In particular, the three categories for punctuation were: sentence pause punctuation marks (‘,’,‘;’,‘.’,‘:’,‘?’,‘!’), grouping punctuation marks (‘{’,‘[’,‘(’,‘&lt;’,‘&#39;’,‘“’, etc.), and math operations (‘+’,‘−’,‘%’,‘{circumflex over ( )}’,‘*’,‘=’,‘/’,‘|’, ‘\’,‘#’, etc.). FIG. 11 is a table showing how the ASCII character set is mapped to each of the different columns of FIGS. 8A through 8H and FIGS. 10A through 10H. As can be seen from FIG. 11, both capital and lowercase versions of a given letter of the alphabet are mapped to the same column. 
     Note that these pattern sheets can be normalized, for instance by multiplying each entry by a constant and they can be massaged with an equalizer function designed to proportionally reduce the largest entries and increase the smallest entries. Other methods of normalization could be used to focus further processing on part of the pattern map, such as multiplying selected entries in the table by one scale factor and unselected entries in a table by another scale factor, thereby emphasizing one portion of the map over another portion. Furthermore, normalization of a pattern sheet might involve combining rows of the sheet (corresponding to intervals of the document) to reduce the number of rows in the map to a standard number. Such a process might be called for when documents of significantly different size are being compared. 
     FIGS. 8A and 8B are the pattern sheet generated from the Book of Joshua, Chapter 10 of the Bible. FIG. 8A is the portion of the pattern sheet for intervals 0 to 49. FIG. 8B is the portion of the pattern sheet for intervals 50 to 99. 
     FIGS. 8C and 8D are the pattern sheet generated from the Book of John, Chapter 20 of the Bible. FIG. 8C is the portion of the pattern sheet for intervals 0 to 49. FIG. 8D is the portion of the pattern sheet for intervals 50 to 99. 
     FIGS. 8E and 8F are the pattern sheet generated from Shakespeare&#39;s  Hamlet . FIG. 8E is the portion of the pattern sheet for intervals 0 to 49. FIG. 8F is the portion of the pattern sheet for intervals 50 to 99. 
     FIGS. 8G and 8H are the pattern sheet generated from Shakespeare&#39;s  Romeo and Juliet . FIG. 80 is the portion of the pattern sheet for intervals 0 to 49. FIG. 8H is the portion of the pattern sheet for intervals 50 to 99. 
     FIG. 9 is a plot of the column for the letter ‘H’ in Hugo&#39;s  Les Miserables  as translated into each of the four languages, English, French, German, and Spanish. It was derived from the pattern maps for the four different versions of  Les Miserables  in the same manner that the plot of FIG. 7 was derived from the corresponding documents. 
     FIGS. 10A and 10B are the pattern sheet generated from the English language version of Hugo&#39;s  Les Miserables . FIG. 10A is the portion of the pattern sheet for intervals 0 to 49. FIG. 10B is the portion of the pattern sheet for intervals 50 to 99. 
     FIGS. 10C and 10D are the pattern sheet generated from the German language version of Hugo&#39;s  Les Miserables . FIG. 10C is the portion of the pattern sheet for intervals 0 to 49. FIG. 10D is the portion of the pattern sheet for intervals 50 to 99. 
     FIGS. 10E and 10F are the pattern sheet generated from the French language version of Hugo&#39;s  Les Miserables . FIG. 10E is the portion of the pattern sheet for intervals 0 to 49. FIG. 10F is the portion of the pattern sheet for intervals 50 to 99. 
     FIGS. 10G and 10H are the pattern sheet generated from the Spanish language version of Hugo&#39;s  Les Miserables . FIG. 10G is the portion of the pattern sheet for intervals 0 to 49. FIG. 10H is the portion of the pattern sheet for intervals 50 to 99. 
     Note that other methods of displaying the pattern sheets and maps and relative pattern sheets and maps can be utilized. These include graphing as a curve the results of comparing a single column, graphing the pattern sheets or maps as two-dimensional color-coded or gray-scale plots, and graphing the pattern sheets or maps as three-dimensional representations. 
     FIG. 11 is the mapping table for the ASCII character set. This table is an array suitable for use in the C programming language. It allows a programmer to use a character as an index into the table yielding a number representing the corresponding column in a pattern sheet or map. It will be apparent to one skilled in the art that modifications of this mapping table could be used to map groups of characters to a single column of a pattern map or sheet. For instance, the five vowels (‘a’,‘e’,‘i’,‘o’,‘u’) could be mapped to a single column. Likewise, characters close to each other in the alphabet, (such as the sequence ‘a’,‘b’,‘c’,‘d’), could be mapped to a single column. 
     FIG. 12 shows a system useful in performing the transformation, mapping, and comparing involved in applicant&#39;s invention. The system includes processor  1301 , Memory  1302 , Storage Device  1303 , Input/Output Device  1304 , Bus  1305 , and Network  1306 . Note that the system need not have all of these components to function. In particular, it need not have storage device  1303  nor network  1306 . Additionally, Input/Output Device  1304  can be split into an input device and an output device. Typically, the input device will be capable of reading machine readable media such as: magnetic disks, optical disks, carrier waves, magnetic tape, or documents (read optically). 
     As will be apparent to one skilled in the art, applicant&#39;s invention can be implemented as instructions on machine readable media, such as instructions in memory such as memory  1302  or other media such as transmission media, or as the logic of an application specific integrated circuit or programmable logic. In each of these cases, the implementation causes a machine, typically some form of processor, to execute the processes necessary to implement applicant&#39;s invention. 
     It will be apparent to one skilled in the art that applicant&#39;s invention can be utilized to automate cataloging and searching of databases. Text documents entered into a database can be transformed and mapped, thus producing individual maps for each document. Those documents can then be compared against other documents for classification according to author, type of document, language, and other forms of classification. Furthermore, a pattern map can be developed as a template, possibly derived from other documents or developed to correspond to the type of document sought. Such a pattern map could be compared to pattern maps of documents in a database with the results reported to someone searching for such a document. 
     In the foregoing detailed description, the method and apparatus of the present invention has been described with reference to specific exemplary embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the present invention. The present specification and figures are accordingly to be regarded as illustrative rather than restrictive.