System and method for portable document indexing using n-gram word decomposition

Abstract

A system and method provides for indexing and retrieval of stored documents using a decomposition of words in the documents in n-grams, or linear word subunits. The documents are indexed as pages in a number of banks. For each bank there is a bank index. The individual n-grams are identified for each page are stored in the bank index. Each bank index further contains an entry map that indicates whether a given n-gram is present in any of the pages of the bank, and then provides an index to a page map that further indicates which page in the bank contains the n-gram. When a search query is input, the query words are decomposed into their n-grams. The query word n-grams are compared first with entry maps to determine if the query word n-grams appear on any page in the bank. If so, the associated page map is traversed to determine which page in the bank contains the query word n-grams. The n-grams on the page are compared with the query word n-grams to determine the presence of an match therebetween. Matching pages are flagged. When all pages in all banks have been processed, the pages are consolidated with respect to the documents to which they belong, resulting in a list of documents that match the search query. The results are displayed to a user.

Claims

We claim:

1. A computer-implemented method for indexing stored documents, each document containing at least one page and containing a plurality of words, and searching for at least one document matching an input search query containing at least one query word, comprising the steps of:

for each document:

identifying non-stop words on each page of the document;

determining for each non-stop word at least one n-gram;

for each n-gram, storing a map having a plurality of positions, each position corresponding to a page, and each position indicating whether or not the corresponding page contains the n-gram;

determining at least one query word n-gram for the at least one query word; and

is retrieving documents having n-grams that match selected ones of the query word n-grams, by performing the steps of:

determining a map corresponding to the query word n-gram;

determining from the map at least one page containing the query word n-gram; and

retrieving the page, and the document associated therewith.

2. A computer readable memory including a storage structure for indexing documents by n-grams, each document having a document number, and a document name, and at least one page, each page having a page number, comprising:

a bank comprising a list of page entries, each page entry identifying a page by the document number of the document containing the page, and a page number within the document; and,

a bank index associated with the bank comprising:

i) a plurality of n-gram entry maps, each n-gram entry map associated with a single n-gram, selected n-gram entry maps having an index to an index entry map where at least one page identified in the bank includes the n-gram associated with the n-gram entry map;

ii) a plurality of index entry maps, each index entry map indexed by one of the n-gram entry maps, each index entry map having a plurality of positions, each position corresponding to a page entry in the bank, and each position indicating whether or not the corresponding page entry in the bank identifies a page containing the n-gram associated with the n-gram entry map that indexes the index entry map.

3. The computer readable memory of claim 2, wherein:

a) each page entry in the bank has an offset;

b) each index entry map includes a plurality of bit positions, each bit position associated with a page entry in the bank, each bit position having a first value where the page identified in the page entry associated with the bit position includes the n-gram associated with the n-gram entry map that indexes the index entry map, and a second value where the page identified in the page entry associated with the bit position does not include the n-gram associated with the n-gram entry map that indexes the index entry map.

4. The computer readable memory of claim 2, further comprising:

a) a drawer including:

i) a list of documents, each document uniquely identified in the list;

ii) a plurality of banks, and associated bank indices; and

iii) a bank list including for each of the plurality of banks a count of a number of empty page entries in the bank.

5. The computer readable memory of claim 2, wherein each bank further comprises:

a) a page key table including at least one page key, each page key uniquely associated with a page entry in the bank, and comprising:

b) for each word on the page, a list of the n-grams in the word.

6. A computer implemented method of retrieving a document, comprising:

a) storing the storage structure of claim 2 on a computer readable memory;

b) receiving a query term;

c) for each of a number of n-grams in the query term:

i) determining from the n-gram map in the bank index associated with the n-gram of the query term whether an index entry map exists for the n-gram;

ii) responsive to an existing index entry map, determining from the index entry map each page entry in the bank that identifies a page containing the n-gram associated with the index entry map; and

iii) incrementing for each page that contains the n-gram an n-gram counter;

d) for each page in the bank, determining whether the n-gram counter for the page is sufficiently similar to the number of n-grams in the query term to indicate that the page contains the query term; and

e) responsive to the n-gram counter for a page being sufficiently similar to the number of n-grams in the query term, retrieving the document containing the page for subsequent query analysis.

7. The computer implemented method of claim 6, wherein the n-gram counter for the page is sufficiently similar to the number of n-grams in the query term where: ##EQU5## wherein P is the page;

G is the n-gram match counter for page P;

K is the number of n-grams in the query term; and

E is a matching parameter selected to control the percentage of matches between the n-gram match counter and K.

8. A computer implemented method of indexing a plurality of documents, each document having at least one page, each page having less than a maximum amount of data, and having a plurality of words, comprising:

a) storing a list of pages, each page associated with a document;

b) determining a list of n-grams; and

c) for selected ones of the n-grams, storing a map of pages that contain the n-gram by:

i) retrieving a current page from the documents; and

ii) for each non-stop word of the current page:

1) determining the n-grams in the word; and

2) for each n-gram in the word:

in a map associated with the n-gram and having a plurality of positions, each position corresponding to a page, and each position indicating whether or not the corresponding page contains the n-gram, updating the position for the current page as indicating that the page contains the n-gram.

9. The computer implemented method of claim 8, for additionally retrieving a document including a query term, comprising:

d) receiving a query term;

e) for each of a number of n-grams in the query term:

i) determining whether a map exists for the n-gram;

ii) responsive to an existing map, determining from the map each page in the list that contains the n-gram associated with the map; and

iii) for each page in the list, determining whether the page contains a sufficient number of n-grams in the query term to indicate that the page contains the query term; and

f) responsive to each page containing the query term, retrieving the document containing the page for subsequent query analysis.

10. A computer readable memory including thereon a computer program configuring and controlling a processor to perform the steps of claim 8.

11. A computer readable memory for controlling a processor to index a plurality of documents, each document containing at least one page comprising:

a list of indexed pages;

a set of index maps, each index map associated with one n-gram and having a plurality of positions, each position uniquely associated with a page in the list of indexed pages, and each position indicating whether or not the corresponding page includes the n-gram associated with the index map; and

a page indexing module that:

i) receives a current page to be indexed;

ii) creates an entry for the current page in the list of indexed pages;

iii) stores for each non-stop word of the current page a list of n-grams in the word; and

iv) for each n-gram, updates in the index map associated with the n-gram, the entry for the current page to indicate that the current page includes the n-gram.

12. The computer readable memory of claim 11, wherein the page indexing module stores for a non-stop word of the current page a list of n-grams in the word by:

iii.1) determining an n-gram number for each n-gram in the word;

iii.2) storing the n-gram number of each n-gram in the word; and

iii.3) associating the stored n-gram numbers with the current page.

13. A computer readable memory for controlling a processor to index a plurality of documents, each document containing at least one page, the memory comprising:

a list of indexed pages;

a set of index maps, each index map associated with one n-gram and having a plurality of positions, each position uniquely associated with a page in the list of indexed pages, and each position indicating whether or not the corresponding page includes the n-gram associated with the index map; and

a page indexing module that:

i) receives a current page to be indexed;

ii) creates an entry for the current page in the list of indexed pages;

iii) stores for each non-stop word of the current page a list of n-grams in the word by:

iii.1) determining an n-gram number for each n-gram in the word by the equation: ##EQU6## where NG is the n-gram number of the word; x is an n-gram character number of the i.sup.th character of the word;

C.sub.max is total number of indexable characters; and

N.sub.p is the desired number of letters in the n-gram;

iii.2) storing the n-gram number of each n-gram in the word; and

iii.3) associating the stored n-grams numbers with the current page; and

iv) for each n-gram, updates in the index map associated with the n-gram, the entry for the current page to indicate that the current page includes the n-gram.

14. A computer readable memory for controlling a processor to index a document including a query term from a plurality of documents, each document containing at least one page, comprising:

a list of indexed pages, each page associated with a document;

a set of index maps, each index map associated with one n-gram and having a plurality of positions, each position uniquely associated with a page in the list of indexed pages, and each position indicating whether or not the corresponding page includes the n-gram associated with the index map; and

a search module that: receives a query term;

for each of a number of n-grams in the query term:

determines whether there is an index map associated with the n-gram; and

responsive to an existing index map,

determines from the index map each page in the list of indexed pages that contains the n-gram associated with the map;

for each page in the list of indexed pages, determines whether the page contains a sufficient number of the n-grams in the query term to indicate that the page contains the query term; and

responsive to a page containing the query term, retrieves the document containing the page for subsequent query analysis.

15. The computer readable memory of claim 14, wherein the search module determines whether a page contains a sufficient number of the n-gram in the query term by the equation: ##EQU7## wherein: P is the page;

G is the number of n-grams in the query term contained in page P;

K is the number of n-grams in the query term; and

E is a matching parameter selected to control the percentage of matches between the number of n-grams in the query term that are contained in the page P, and K.

Description

BACKGROUND OF THE INVENTION

This invention relates to the field of document processing with optical scanners and optical character recognition, and more particularly, to systems and methods that index words in a document for subsequent search and retrieval.

BACKGROUND OF THE INVENTION

Optical character recognition (OCR) is widely used to capture printed or handwritten documents in a computer readable form, thereby allowing the documents to be subsequently searched and retrieved using information retrieval systems. Typical information retrieval systems with full text retrieval capability index every significant word in a document input into the system, providing for each word in the index a list of identifiers of where the word occurs, typically by document, page, and some type of word offset, or other similar type of linkage. Documents are retrieved in response to an input search query by exactly matching the words in the search query to words in the index and retrieving the documents indexed to the words. Boolean search operators are typically provided to enable complex search queries.

Accordingly, accurate retrieval of input documents relies primarily on accurate input and OCR analysis. OCR systems are generally very sensitive to spacing differentials between characters, font type, font size, page layout, image resolution, and image quality. Thus, even highly accurate OCR systems, with accuracy rates of about 99%, will misinterpret one character in every hundred, resulting in letter substitutions, missing letters, or similar spelling errors. As a result a typical OCR processed document may then have anywhere from 3 to 8 or more misspellings or errors per page. This does not include the typographical errors that may be originally present in the document. Another problem is that the OCR system will run separate words together.

A misspelled word will not be properly indexed, and hence will not be retrieved during in response to a search query including the properly spelled word. Likewise, individual words in a run together word string will not be indexed at all, but only indexed as part of the entire word string, and hence a document containing any of the individual words in the word string will not be retrieved in response to a search query specifying such words.

Typical solutions to the misspelling problems rely on thesauruses or similar devices to index common misspellings to their correctly spelled sources. One problem with this approach is that it does not account for uncommon misspellings. These approaches also significantly increase the size of the index, and this leads to another aspect of information retrieval system design.

A second major issue in information retrieval systems is the performance and time required to create and maintain an index. Typically, an inverted index is maintained as a single monolith data structure, such as a doubly linked list, or tree structure. Each time a new document is added to the system, which may be daily for on-line databases, the entire index must be adjusted, and each word entry in the index that appears in the input documents must be updated with the relevant data for the input documents. This makes on-line indexing unsuitable for large systems, so that indexing is performed off-line, limiting how quickly one can search the added documents. In addition, the more detailed the index, the more time consuming the indexing process. However, a detailed index may provide the benefit of reduced search times. Thus, there is a tradeoff between indexing time and search time.

Finally, another concern with information systems is the ability to exchange indexed documents for use with adjunct or client systems. Currently, many software applications, and particularly databases and information systems, are client-server based. In addition, there is an ever increasing number of portable computers. These factors make it desirable to provide an indexing system that allows indexed documents to be efficiently added or removed from the system for searching without substantial overhead for re-indexing. Conventional information retrieval systems employ a monolithic inverted index that is not portable, because the index may be many megabytes, or even gigabytes, and index tens of thousands of pages of documents. An index of this size or complexity cannot be conveniently transferred to remote clients, portable computing devices, or removable storage media.

Accordingly, it is desirable to provide an indexing system that compensates for errors in the input document, whether from OCR analysis or otherwise, and allows fast indexing and accurate retrieval of documents that contained misspellings or other typographical errors. It is further desirable to provide a system that allows for rapid indexing without a significant increase in search times, and further supports portability of indexed documents.

SUMMARY OF THE INVENTION

An improved indexing and retrieval method and system overcomes the limitations of existing information retrieval systems by decomposing each word into a number of "n-grams" or word subunits. An n-gram is a ordered linear combination of n characters as they appear in a given word, particularly letters or numbers, such as "cho", "thi", "ment". Generally, an n-gram has an n-gram parameter N.sub.p which is the number of characters in the n-gram. An n-gram with an n-gram parameter N.sub.p of three is conveniently called a "trigram." For example, the word "houseboat" is composed of the trigrams "hou", "ous", "use", "seb", "ebo", "boa", "oat". Note that neither "tbh" or "hbt" is a trigram of "houseboat" even though all of the letters are present in the word because the order and relation of the letters as they appear in the word is significant.

In the present invention, the non-stop words on each page of a document are decomposed into their n-grams, which are indexed and stored. By indexing words by n-grams, rather than complete words, misspellings, partial words, or words embedded in word strings can be identified by searching for matches between n-grams of query words and n-grams in the documents, rather than matches between entire words. For example, assume the word "factory" is misspelled in a document as "factori". Its n-grams are stored as "fac", "act", "cto", "tor", and "ori". These are compared with the n-grams of the search query word "factory" correctly spelled: "fac", "act", "cto", "tor", "ory". Four of five n-grams will match, and the document will be retrieved. Similarly, if the first letter was left off due to OCR analysis problems, the n-grams would still be "act", "cto", "for", and "ory". Here, four of the five n-grams still match, so the word will be retrieved. Clearly, n-grams for words inside a run together word string would be similarly identifiable and separately matchable.

Accordingly, for searching and retrieving documents, a search query is input, and the words in the search query are likewise decomposed into their n-grams. The query word n-grams are then compared with the n-grams for words on the pages of various documents. Where any query word n-grams match any word n-grams on a page, the page is retrieved, and the query word n-grams are further compared with each word n-gram. This allows a determination of the preciseness of the match between the query words and the words on the page. The document containing the page can then be retrieved and displayed to the user. Boolean searching can also be performed once a determination of match between query words and document words has been made.

The foregoing describes the basic idea of the n-gram decomposition and indexing process. Many different systems may be devised to use the n-grams to analyze words or documents. It is desirable however to employ n-gram decomposition in a system that provides for efficient indexing and fast searching with high accuracy, and that further provides for portability of is indices and documents. Accordingly, a separate and further aspect of the invention is the use of a hierarchical indexing scheme that stores the data representing documents in a number of drawers, each drawer containing documents with pages of text and image data. The pages are listed in a number of banks in a drawer. N-gram decomposition and indexing is performed on discrete pages, rather than on entire documents.

Each drawer contains a number of banks. For each bank there is a bank index. The bank index stores data representing the n-grams that actually appear on each page in the associated bank. Since there is a known fixed number of n-grams of a given size, each bank index further includes an entry map that indicates for each possible n-gram whether there are any instances of the n-grams on any of the pages listed in the bank. For each n-gram of which there are instances on any pages in the bank, then the entry map provides access to a further page map that specifically identifies each page in the bank that includes the n-gram. This type of storage structure allows for a very compact, efficient use of memory during indexing and retrieval.

The banks and bank indices provide a rapid retrieval system. When a query is entered, the n-grams of the query words are determined. Each n-gram in the query words is first compared just against the entry map to determine if there are any instances of the n-grams in any pages of the bank. Where the entry map indicates that some page contains the n-grams, the page maps are traversed to determine specifically which pages need further processing. This initial preprocessing very quickly identifies only those pages that need further searching for a given query word, eliminating from consideration pages that do not contain any n-grams of the query words.

A second processing stage then will access only those pages in the bank that contain portions of the query. For each such page, the n-grams on the page, which are stored in the bank index, are then compared with the query word n-grams. When a sufficient percentage of these match the n-grams of a query word, the document associated with the page is indicated for retrieval.

This organization of documents and indices provides for portability of the documents since an entire drawer, including its drawers, documents, banks, and bank indices, can be transferred from the computer system where the document was indexed, to another computer system, and searched thereon without the need to re-index the documents in the drawer.

BREIF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of a system for indexing and retrieving documents using n-gram decomposition.

FIG. 2a is an object model of the storage elements of the system, showing the associations of drawer, folders, documents, banks, bank list, bank index, free list, and document list.

FIG. 2b is an illustration of the user's perspective of these storage elements.

FIG. 3 is an illustration of the structure of the document list.

FIG. 4 is an illustration of the structure of a bank.

FIG. 5 is an illustration of the structure of a bank index.

FIG. 6 is an illustration of one example of the relationship between a bank and a bank index.

FIG. 7 is a flowgraph of the overall method of indexing and searching documents.

FIG. 8 is a flowgraph of the indexing process for a document.

FIG. 9 is a flowgraph of the process of indexing a page in a document.

FIG. 10 is a flowgraph of the process of creating word keys in a page for storage in the bank index.

FIG. 11 is a flowgraph of the searching process.

FIG. 12 is a flowgraph of the pre-processing operation on a bank.

FIG. 13 is a flowgraph of the process of searching selected pages of a bank following pre-processing.

FIG. 14 is flowgraph of the process of matching n-grams of query words with n-grams of word on a page.

DETAILED DESCRIPTION OF THE INVENTION

System Architecture

Referring now to FIG. 1, there is shown a system for using the improved document indexing and retrieval system of the present invention. The system 100 includes a computer 101 having a secondary storage 107 for long term storage of scanned documents, an input device 109 and an output device 116 for receiving and outputting commands and data, and an addressable memory 113 for storing the various code modules for execution by a processor 111.

The input devices 109 include a scanner 115 that is capable of scanning input documents, and producing either gray scale, bitonal, or color bitmap files for the input documents. The scanner 115 preferably has at least 200 dpi resolution. The input devices 109 further include a keyboard 149 for entering commands and data. The output devices 116 include a printer 117 for printing documents, including scanned documents, or other documents resident in the system 100. The output devices 116 also include a display 151 for displaying a user interface for the system to the user, along with search results and other information.

The addressable memory 113 includes a number of code modules that together comprise an executable application that manages the system 100 of the present invention. More particularly, the addressable memory 113 includes an application executive 119, an index executive 121, a search executive 123, a document reference module 125, a page indexing module 127, a search execution module 129, a search list module 131, and a optical character recognition module 133. The operation of these various modules will be described below, following a description of the storage elements that support portable document indexing. An index/search buffer 143 is used to temporarily store data generated during the indexing and searching stages. A page buffer 145 is used to temporarily store data from documents during searching. A stop word file 135 maintains a list of words that are excluded from indexing. The stop word file 135 is provided with the system 100, and may be modified by the user.

The system 100 is accessed through the application executive 119 which provides a suitable user interface on the display 151, allowing the user to input documents into the system 100 through the scanner 115, or other source, such as existing text files, image files, graphic files, and the like, to input search queries containing combinations of word, universal characters, and Boolean or SQL operators, and to review the results of search queries on the output devices, such as the display 151 or printer 117.

The addressable memory 113 further includes a database 141 of storage structures useful for implementing the n-gram decomposition indexing of the present invention. Referring now to FIG. 2a, there is shown an object model of these storage structures in the addressable memory 113. FIG. 2b illustrates the user's perspective of these storage structures.

The addressable memory 113 includes one or more drawers 201. Each drawer 201 preferably has a drawer name, and a logical name, and media type, whether removeable or fixed media. This last attribute allows drawers 201 to be transferred to various computing devices on portable storage media.

Each drawer 201 further includes a hierarchical list of zero or more folders 203. Each folder 203 has a folder name and includes zero or more documents 205 or other folders 203.

Each document 205 preferably has a document name, for recognition by the user, and a unique document number used by the system 100. A document 205 is comprised of at least a text file 207. Additionally a document 205 may include an image file 209, an icon file 213, and a document file structure (DFS) file 211. The text file 207 contains the text data of the document in an ASCII or similar format. The text data will generally be produced from OCR processing on the image data. The text data may also be directly created from user inputs. The text data may also be entered, for example, where the document 205 is a bitmapped or vector graphics file, and the user wishes to include a comment or description of the file for indexing purposes. The text 207 file contains its data in one or more pages 215. Each page is identified by its page number, document name, folder name, and drawer name.

The image file 209 is a bitonal, grayscale, or color bitmap resulting from a scanning and digitization of a corresponding input document, or other similar processing. The data in the image file 209 is similarly stored in pages 215.

The DFS file 211 maps the text file data to the image file data. The DFS file 211 contains for every line of text in the text file 207 a mapping to a image page 215, and a bounding rectangle defined by pixel coordinates (preferably upper-left and lower-right corners) of where the line of text appears in the image page 215. This mapping allows the user to access the text data on a page when viewing the image of the page. The DFS file 211 also preferably maintains a page count for the number of text and image pages in the document 205. The DFS file 211 further maintains reference data about each page 215 in the document 205, including a page number, document number and name, full path name, and icon file name.

The icon file 213 contains thumbnail bitmapped images of each page of the document 205. The thumbnail images are displayed to the user during search and retrieval operations or while the document 205 is being accessed by the user. In the preferred embodiment, where the document only contains text data produced without scanning or the like, then there is no accompanying image file 209 or icon file 213.

Each drawer 201 is associated with a document list 225. The document list is an index of all documents 205 in the drawer 201. FIG. 3 illustrates the structure of the document list 225. The document list 225 stores a variable number of entries 311, up to maximum limit D.sub.max. In the preferred embodiment D.sub.max is limited by the number of overall pages in all of the documents in the drawer 201, with each drawer 201 capable of handling up to 1,044,480 pages. Each entry 311 includes the full path name of each document 205 in the drawer 201. Each document 205 has a unique document number 301 within the document list 225 as a result of its offset in the document list 225. A status value 303 is preferably maintained to indicate for each entry 311 whether it is available to store a document. The document list 225 maintains a count of the number 307 of document entries 311, and a count of the number 309 of unused entries, which are created when existing documents are removed.

The system 100 further includes at least one bank 217. FIG. 4 is an illustration of the structure of a bank 217. Each bank 217 contains a list of pages from various documents in the system 100, up to a predetermined number P.sub.max of entries 413. In the preferred embodiment, a bank 217 contains up to 255 entries, or page references. In other embodiments, P.sub.max may be higher, resulting in indexing of more pages, or P.sub.max may be lower, for fewer indexible pages, but less storage requirements. The document pages are listed with their document number 301 from the document list 225 for the drawer 201, and then by a page number 403 within the document 205. For each entry 413, a status value 405 is preferably maintained indicating whether a page is referenced in the entry. Each entry 413 further has an associated bank offset 411 which is the offset of the entry 413 within the bank 217; the bank offset 411 is not actually stored in the entry 413. Each bank 217 preferably maintains a number 407 of unused entries, which is updated as new pages are referenced, and others are un-referenced in the bank 217. In the preferred embodiment, a drawer 201 may include 4096 banks 217, resulting in up to 1,044,480 pages of indexed data for each drawer 201. Each bank 217 has a bank number 409 that uniquely identifies it in the drawer 201 and bank list 219; the bank number 409 may be stored in the bank 217 itself, or may be can identified by the file name of the bank 217. Together, a bank number 409 and a bank offset 411 form a bank reference for a page.

Each bank 217 is associated with a bank index 223, and a free list 221. Each bank index 223 identifies the n-grams found in each page entry 413 in a bank 217. Referring to FIG. 5, there is shown the preferred structure of the bank index 223. In the preferred embodiment, the bank index 223 does not directly include a list of all n-grams, as data. Rather, each n-gram is assigned a unique number, which is used to index a fixed number of n-gram entry maps 505.

First, the character set and character range indexible by the system 100 for indexing is selected. The total number of indexible characters is called C.sub.max. The total number L of n-grams then is: ##EQU1##

In the preferred embodiment, the indexible characters are "A"-"Z", "0"-"9". All punctuation and special characters, which are typically not used to search for data, are preferably mapped to a single character, such as ".about.". This allows indexing of words such as "AT&T" as "AT.about.T" and numbers, such as "3.1415926" as "3.about.1415926". In addition, where the last several characters of a word are insufficient in number for an n-gram by themselves, ".about." may be used to complete the n-gram. For example, the trigram of "at" would be "at.about.". International characters may be mapped to corresponding English equivalents. Lowercase characters are converted to their uppercase value. This results in the preferred embodiment in 37 different characters for each position in the n-gram. In the preferred embodiment then, there are 50,563 (37.sup.3) trigrams. The 37 characters are ordered in any useful manner, such as by their ASCII value, or other means. The possible n-grams are then listed and serially numbered with an n-gram number. For example, assuming numerals first, letters, and then ".about.", the ordering would be "000", "001", . . . "00A", . . . "00Z", "00.about.", . . . ".about..about..about.". In a preferred embodiment, the n-gram number may be calculated as follows:

    ______________________________________
    n-gram number =
                 (1st n-gram letter no.) * max.sub.-- char.sup.N-1  +
                 (2nd n-gram letter no.) * max.sub.-- char.sup.N-2  +
                 (3nd n-gram letter no.) * max.sub.-- char.sup.N-3  +
                 . . .
                 (N-1.sup.th  n-gram letter no.) * max.sub.-- char +
                 (N.sup.th  n-gram letter no.).
    ______________________________________

    ______________________________________
    trigram number =
                   (1st trigram letter no.) * 37.sup.2  +
                   (2nd trigram letter no.) * 37 +
                   (3nd trigram letter no.).
    ______________________________________

                  TABLE 1
    ______________________________________
                                         Bank
    Bank 1     Bank 2    Bank 3          4096
    ______________________________________
    Free       Free      Free    --      Free
    Count      Count     Count           Count
    ______________________________________

• Inventors
  Rangarajan, Vijayakumar; Ravichandran, Natarajan;
• Assignee
  Rebus Technology, Inc. (Sunnyvale, CA)
• Published
  Jan-6-1998
• Current US Classes:
  707/102
  715/500
• Application #
  419126
• International Classes
  G06K 009/72
• Field of Search
  382/224 382/229 382/230 364/419.13 364/419.19 395/600
• Examiner
  Mancuso; Joseph
• Agent
  Fenwick & West LLP
• US Patent References:
  4495566
  5062142
  5062143
  5265065
  5375235
  5412807
  5418951
  5469354