Full text index reference compression

Abstract

A system and method for compressing a text index. The method includes determining which indexed items have been deleted, and forming a new index which does not contain references to deleted indexed items. Portions of the index are regenerated to eliminate references to deleted indexed items, and a remap structure is created and used during the compression process to remap references from the old portions of the index to the newly generated portions of the index. The method runs relatively quickly, even with a large number of indexed items. The method also works with indexes which use a granularity other than document-level granularity, through the use of a remap array which remaps references to documents as well as references to granules.

Claims

I claim:

1. In an index containing a first item list and an indexed word list, the first item list including a plurality of item entries, each item entry having an item index associated therewith, each item entry referring to a deleted or a nondeleted indexed item, wherein at least some of the indexed items comprise a plurality of granules, the index having a first granule cross-reference table including a plurality of granule entries, each granule entry having a granule index associated therewith, and each granule entry referring to an item entry of an indexed item in the first item list, the indexed word list including a plurality of word entries, each word entry associated with a first word reference list, each first word reference list including a reference to an item entry of an indexed item in which the associated word is located, a method for eliminating references to item entries which refer to deleted indexed items, the method comprising:

determining which item entries refer to deleted indexed items;

forming a remap item list which remaps the item entries which refer to nondeleted indexed items from a first item index in the first item list to a second item index in a second item list and which remaps the granule index of granule entries which refer to an item entry of a nondeleted indexed item from a first granule index in the first granule cross-reference table to a second granule index in a second granule cross-reference table;

traversing the indexed word list by

a) for each word entry, traversing the first word reference list associated with the word entry;

b) for each reference in the first word reference list determining if the reference refers to an item entry of a nondeleted indexed item or an item entry of a deleted indexed item, and if the item entry refers to a nondeleted indexed item accessing the remap item list to obtain a reference to a second item entry in the second item list which refers to the nondeleted indexed item and storing the reference in a second word reference list;

associating each word entry in the indexed word list which has at least one reference to an item entry which refers to a nondeleted indexed item with the respective second word reference list; and

forming the second item list by associating the item entries of the nondeleted items with the respective second item index referred to in the remap item list.

2. In an index according to claim 1, wherein each reference in the second word reference list is an item index of an item entry.

3. In an index according to claim 1, wherein the remap item list further comprises a data field containing data indicating which item entries refer to deleted indexed items.

4. In an index according to claim 1, wherein each reference in the second word reference list is a granule index of a granule entry.

5. In an index according to claim 4, wherein the remap item list comprises a plurality of remap entries, each remap entry remapping a range of one or more contiguous item indexes of item entries and the granule indexes of granule entries associated therewith, a remap entry comprising a nondeleted indexed item remap entry or a deleted indexed item remap entry, each item index in a nondeleted indexed item remap entry referring to an item entry of a nondeleted indexed item, and each item index in a deleted indexed item remap entry referring to an item entry of a deleted indexed item.

6. In an index according to claim 5, wherein each nondeleted indexed item remap entry includes a first low granule field and a first high granule field, the first low granule field containing the lowest granule index of the granule entries in the first granule cross-reference table remapped by the remap entry, the first high granule field containing the highest granule index of the granule entries in the first granule cross-reference table remapped by the remap entry, and a second low granule field, the second low granule field containing the lowest granule index of the granule entries in the second granule cross-reference table remapped by the remap entry.

7. In an index according to claim 6, wherein each nondeleted indexed item remap entry further comprises a granule delta field, and the granule delta field contains a value reflecting a difference between the value of the first low granule field and the value of the second low granule field.

8. In an index according to claim 1, wherein the remap item list comprises a plurality of remap entries, each remap entry remapping a range of one or more contiguous item indexes of item entries, a remap entry comprising a nondeleted indexed item remap entry or a deleted indexed item remap entry, each item index in a nondeleted indexed item remap entry referring to an item entry of a nondeleted indexed item, and each item index in a deleted indexed item remap entry referring to an item entry of a deleted indexed item.

9. In an index according to claim 8, wherein each nondeleted indexed item remap entry comprises a first low item field and a first high item field, the first low item field containing the lowest item index of the item entries in the first item list remapped by the remap entry, the first high item field containing the highest item index of the item entries in the first item list remapped by the remap entry, and a second low item field, the second low item field containing the lowest item index of the item entries in the second item list remapped by the remap entry.

10. In an index according to claim 1, wherein at least one of the first item entries in the first item list has the same value as the corresponding second item entry in the second item list.

11. In an index according to claim 1, further comprising forming a second indexed word list, each word entry in the second indexed word list being associated with a second word reference list having at least one reference which refers to a second item entry in the second item list of a nondeleted indexed item.

12. A system for use in conjunction with an index containing a first item list and an indexed word list, the first item list including a plurality of item entries, each item entry having an item index associated therewith, each item entry referring to a deleted or a nondeleted indexed item, wherein at least some of the indexed items comprise a plurality of granules, the index having a first granule cross-reference table including a plurality of granule entries, each granule entry having a granule index associated therewith, and each granule entry referring to an item entry of an indexed item in the first item list, the indexed word list including a plurality of word entries, each word entry associated with a first word reference list, each first word reference list including a reference to an item entry of an indexed item in which the associated word is located, the system being adapted for eliminating references to items entries which refer to deleted indexed items, the system comprising:

a deleted-item task operative to generate a structure for determining which item entries refer to deleted indexed items;

a remap task operative to generate a remap item list which remaps the item index of item entries which refer to nondeleted indexed items from a first item index in the first item list to a second item index in a second item list;

a word index task operative to traverse the indexed word list by

a) for each word entry, traversing the first word reference list associated with the word entry; and

b) for each reference in the first word reference list determining if the reference refers to an item entry of a nondeleted indexed item or a deleted indexed item, and if the item entry refers to a nondeleted indexed item accessing the remap item list to obtain a reference to the second item entry in the second item list which refers to the nondeleted indexed item and storing the reference in a second word reference list, wherein each reference in the second word reference list a granule index of a granule entry;

a task operative to associate each word entry in the indexed word list having at least one reference to an item entry which refers to a nondeleted indexed item with the respective second word reference list; and

a task operative to form the second item list by associating the item entries of the nondeleted items with the respective second item index referred to in the remap item list.

13. In an index according to claim 1, wherein the remap item list comprises a plurality of remap entries, each remap entry remapping a range of one or more contiguous item indexes of item entries and the granule indexes of granule entries associated therewith, a remap entry comprising one of a nondeleted indexed item remap entry or a deleted indexed item remap entry, each item index in a nondeleted indexed item remap entry referring to an item entry of a nondeleted indexed item, and each item index in a deleted indexed item remap entry referring to an item entry of a deleted indexed item.

14. In an index according to claim 13, wherein each nondeleted indexed item remap entry includes a first low granule field and a first high granule field, the first low granule field containing the lowest granule index of the granule entries in the first granule cross-reference table remapped by the remap entry, the first high granule field containing the highest granule index of the granule entries in the first granule cross-reference table remapped by the remap entry, and a second low granule field, the second low granule field containing the lowest granule index of the granule entries in the second granule cross-reference table remapped by the remap entry.

15. In an index according to claim 14, wherein each nondeleted indexed item remap entry further comprises a granule delta field, and the granule delta field contains a value reflecting a difference between the value of the first low granule field and the value of the second low granule field.

16. In an index containing a first item list and an indexed word list, the first item list including a plurality of item entries, each item entry having an item index associated therewith, each item entry referring to a deleted or a nondeleted indexed item, wherein at least some of the indexed items comprise a plurality of granules the index having a first granule cross-reference table including a plurality of granule entries, each granule entry having a granule index associated therewith, and each granule entry referring to an item entry of an indexed item in the first item list the indexed word list including a plurality of word entries, each word entry associated with a first word reference list, each first word reference list including a reference to an item entry of an indexed item in which the associated word is located, a computer-readable medium having encoded thereon a method for eliminating references to item entries which refer to deleted indexed items, the method comprising:

determining which item entries refer to deleted indexed items;

forming a remap item list which remaps the item index of item entries which refer to nondeleted indexed items from a first item index in the first item list to a second item index in a second item list;

traversing the indexed word list by

a) for each word entry, traversing the first word reference list associated with the word entry;

b) for each reference in the first word reference list determining if the reference refers to an item entry of one of a nondeleted indexed item and a deleted indexed item, and if the item entry refers to a nondeleted indexed item accessing the remap item list to obtain a reference to a second item entry in the second item list which refers to the nondeleted indexed item and storing the reference to the second item entry in a second word reference list, wherein each reference in the second word reference list is a granule index of granule entry;

associating each word entry in the indexed word list having at least one reference to an item entry which refers to a nondeleted indexed item with the respective second word reference list; and

forming the second item list by associating the item entries of the nondeleted items with the respective second item index referred to in the remap item list.

Description

TECHNICAL FIELD

The present invention relates generally to the field of text indexers, and is particularly directed to a text index compression system for eliminating references to deleted indexed items.

BACKGROUND OF THE INVENTION

The introduction and increasingly wide usage of computers in the past thirty years has made previously unavailable information increasingly accessible. This "information explosion" has increased exponentially in the past decade with the advent of personal computers (PCs), the large-scale linking of computers via local and wide area networks (LANs and WANs), and related events.

Further, the rapid growth of Internet and intranet technologies has resulted in vast amounts of information which can be accessed on-line. Much of this information is in the form of free format text, such as found in textual documents. One means of searching such information is to navigate through hypertext links using an Internet browser or by traversing the folders of a file system or a document management repository. However, because of the large amount of information, full text indexes of all of the words in the documents are rapidly becoming an essential tool to find needed information.

Indexing is the process of cataloging information in a collection of texts in an efficient and coherent manner so that it can be easily accessed. Most traditional indexing and retrieval schemes are ineffective when dealing with large quantities of variable length document text data.

As PCs have risen from their infancy, when relatively small amounts of data (on the order of kilobytes) were accessible by a single PC, to their current state, in which gigabytes of disparate data are accessible from a single PC, old methods for managing and accessing data are no longer effective.

For a collection of texts, the ability to retrieve data is directly related to the amount and quality of information in the index. For example, the index may contain only the titles of the documents. Or it may contain only certain key terms. The recommended solution is to provide indexing and searching on every word in the collection of texts.

The present invention relates to the class of indexing techniques known as full text indexing. A full text index consists of a word list for a collection of texts which resembles the index of a textbook. It can be viewed as a word list with an ascending order list of numbers associated with each word. Like the index of a book, the numbers refer to the indexing unit, or "granule" (e.g., page 6), where the word occurs in the source text. The core of the problem addressed by full text indexing is how to find documents (or parts thereof) when one does not know by whom they were written, when they were written, or what their contents are, yet one has an idea of the words, phrases, ideas, and possibly the dates involved. Thus, there are generally two search modes contemplated by full text indexers: (1) locate mode, i.e., searches for a specific document known to exist, but about which only fragmentary information is known (e.g., the date or author of the document); and (2) research mode, i.e., searches for documents pertaining to a certain category of information, where it is known whether the documents exist (e.g., documents pertaining to education in the 19th century.

Due to the large quantity of data that must be indexed today, some of the major indexing problems to be addressed are the speed of index creation and access and size of the index. Regarding the speed of index creation, because the data being indexed is constantly changing, a full text indexer must be able to create a new index quickly when data changes. The index must also be quick to locate and access information in the index. Also, since storage space is important and the size of the index is closely related to access speed, it is highly desirable that the index be small relative to the data being indexed.

Limited memory availability when building a full text index quickly creates another problem relating to the relative frequency of words being indexed. The DOS environment, for example, is an especially limited environment for indexing. A word like "the" may occur in almost every indexing unit. A word like "optometrist" might occur in only a few indexing units. If the index is created in a single pass, the word list and the index elements for each word must coexist in the computer's memory. When a new word is encountered, the amount of memory necessary to store the references to that word cannot be known until all documents have been read. A series of small memory allocations would make the index for high frequency words inefficient. Large allocations waste memory.

Full text indexes must be updated as new documents are created and existing documents are changed or deleted, since references to deleted or noncurrent documents can use a significant amount of disk space, and can also decrease the efficiency of retrievals via the full text index. Such space can be reclaimed by reindexing the documents. However, such a reindexing process can be quite time consuming. Another mechanism for reclaiming space utilized by references to deleted documents is by compressing the full text index so that the index contains only active references (nondeleted documents). Since reindexing is generally considerably slower than compressing the index, it is preferable to recover wasted space by compressing the index rather than reindexing the documents.

SUMMARY OF THE INVENTION

It is one object of this invention to provide a method and system for compressing a text index to recover disk space used by references pointing to deleted documents.

It is another object of this invention to provide a text index compression system which executes very quickly.

Additional objects, advantages and other novel features of the invention will be set forth in part in the description that follows and, in part, will become apparent to those skilled in the art upon examination of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out in the appended claims.

To achieve the foregoing and other objects and in accordance with the purposes of the present invention, a method is provided for eliminating references to deleted indexed items in a text index. The method includes determining which item entries of the index refer to deleted indexed items, and forming a remap item list which remaps the item index of item entries which refer to nondeleted indexed items from a first item index in a first item list to a second item index in a second item list. The index includes an alphabetical word list which contains a list of indexed words. Each entry in the alphabetical word list includes a reference to a word index list which contains references to the indexed items which contain that word. The alphabetical word list is processed, and for each word entry, its associated word index list is processed. For each reference in the word index list it is determined if the reference refers to an item entry of a nondeleted indexed item or a deleted indexed item. If the item entry refers to a nondeleted indexed item the remap item list is accessed to obtain the second item entry in the second item list which refers to the nondeleted indexed item. A second word index list is created, and a reference to the second item entry is stored in the second word index list. After all the references in the first word index list are processed, the word entry in the word list is associated with the respective second word index list, discarding the original word index list for that word. A second item list is formed by associating the item entries of the nondeleted items with the respective item index referred to in the remap item list, and at the end of the compression process, the second item list replaces the original item list.

According to another embodiment of this invention, the indexed items include a plurality of granules. A granule generally refers to the finest unit of text in which one wishes to keep track of where a word occurs, for example a granule can refer to a file, a document, a paragraph, or a sentence. The text index can include a granule cross-reference table which includes a plurality of granule entries, each granule entry having a granule index associated therewith, and each granule entry referring to an item entry of an indexed item in the first item list. During the compression process, the remap item list is used to remap the granule index of granule entries which refer to an item entry of a nondeleted indexed item from a first granule index in the original granule cross-reference table to a second granule index in a second granule cross-reference table. At the end of the compression process, the second granule cross-reference table replaces the original granule cross-reference table.

According to another embodiment of this invention, the remap item list includes remap entries which remap a range of one or more contiguous item entries, and the granule entries associated therewith. Each remap entry refers to a range of nondeleted indexed items or a range of deleted indexed items.

Still other objects of the present invention will become apparent to those skilled in the art from the following description, wherein there is shown and described a preferred embodiment of this invention, simply by way of illustration, of one of the best modes contemplated for carrying out the invention. As will be realized, the invention is capable of other different obvious aspects all without departing from the invention. Accordingly, the drawings and description will be regarded as illustrative in nature and not as restrictive.

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings incorporated in and forming a part of the specification, illustrate several aspects of the present invention, and together with the description serve to explain the principles of the invention. In the drawings:

FIG. 1 is a block diagram of the computer system in which the present invention can be practiced;

FIG. 2 is a summary flowchart of the method for rapid full text indexing;

FIG. 3 is a representative portion of an in-memory word list data structure;

FIG. 4 is a flow diagram illustrating the flow of the compression method and system according to one embodiment of this invention;

FIG. 5 is a block diagram illustrating a broad overview of a squeeze operation according to one embodiment of this invention; and

FIG. 6 is a more detailed block diagram of one aspect of the squeeze operation shown in FIG. 5.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

The method and system for index reference compression (also referred to as a `squeeze` operation) described herein has utility in the compression of a variety of text indexes. A method for the creation and generation of one such text index will be described below with reference to a set of documents. The documents may contain alphanumeric text of any language and are limited in number only by the available disk storage. The text index discussed herein may be implemented on virtually any digital computer system.

1. GENERATION OF THE TEXT INDEX

The method disclosed reads each word of the selected documents and for each unique word in the set of documents, the index records the "granules" in which the word is found. A granule may be any grouping of words within a document or set of documents, such as a sentence, paragraph, page number, section, chapter, document, etc. In general, the method remains the same regardless of the granule size chosen.

Referring to FIG. 1, a block diagram schematically illustrating the computer system is disclosed. The system includes CPU and a memory (101) in which the full text indexer is executed, power supply (102), user input device (103), storage device (104), and display terminal (105).

Referring to FIG. 2, a summary flow diagram of the method is disclosed. In Phase IA (201), a selected set of documents are read sequentially from which an in-memory Word List (also called Word List symbol table) and a Non-Repeating Word Number Stream ("NRWNS") are created. A granule cross-reference file is also maintained for recording the document in which each granule occurs. In Phase IB (202), an alphabetized list (the Alpha List) is created from the in-memory Word List and stored in a temporary file. In Phase II, the data compiled in Phase I is processed and merged into a full text index and written to permanent storage. In Phase IIA (203), memory is allocated in a highly efficient manner based on word frequency data gathered in Phase I. A Word Number Access Array ("WNAA") is built which references data necessary to build the final full text index. In Phase IIB (204), an uncompressed in-memory full text index is constructed by sequentially reading the NRWNS and merging the data in the WNAA into the index. In Phase IIC (205), the uncompressed in-memory full text index and WNAA reference list data are compressed into a final fill text index and written to storage. Each word's reference list in the WNAA can be compressed using a combination of four compression methods--Run Length Encoding, Delta Encoding, Absolute Element Reference, or Bit String Representation. In Phase IID (206), the Alpha List is compressed and each word is combined with a pointer to the final compressed index. Finally, in Phase IIE (207), the index and related data is merged into a single index file.

The method can be summarized by the following pseudocode:

1. Initialize Indexer. Open temporary files.

2. Get next file from the list to index.

3. If no more files or low memory condition (insufficient memory available) then Go to 8.

4. Open the file for processing.

5. Scan through the file (Phase IA). Create the NRWNS file, granularity cross reference file, and the hash-tree in-memory Word List.

6. Close the file.

7. Go to 2.

8. Output the hash-tree in-memory Word List to a file in alpha order (Alpha List) (Phase IB).

9. Allocate memory for uncompressed merged index using the Alpha List (Phase IIA). For low memory machines, portions of the word list are marked for merging the uncompressed index in incremental passes.

10. Read the NRWNS and make the uncompressed in-memory index accessed by the word number (Phase IIB). Low memory machines require multiple passes through steps 10 and 11.

11. Compress the index to a disk file while retaining index cross-reference information in memory (Phase IIC).

12. Create a compressed version of the Alpha List adding pointers to the index and its length (Phase IID).

13. Merge the file, path, and granule cross reference information with the compressed Word List and the index into the final index file (Phase IIE).

14. Finish indexer and close files.

INDEX CREATION

I. Phase I

A. Index a File

First, the selected files are read sequentially, word by word, and two primary data structures are built: the in-memory Word List and the NRWNS. The Word List contains information about each unique word found in the set of selected files. The NRWNS is a temporary data file in which is stored sequentially a representation of the stream of words found in the set of documents, each word being represented by a unique word number. Each unique word in the set of files is assigned a word number sequentially according to the order in which the word first occurs in a file.

The logical structure of the Word List is a key factor for the speed with which the index is created. Each word is stored as a node of a binary tree and is accessed in the Word List based on its first two letters (e.g., "TH" for "THIS" or "THOSE"). Referring to FIG. 3, the Word List comprises a 4096 element table (301). Each element ("hash bucket") of the table is accessed by a unique hash number representing the first two characters of the word (e.g., "TH"). In the preferred embodiment, each character is assigned a value from 0-63 and the hash number is determined according to a hash function wherein the assigned value of the first character is multiplied by 64 and added to the assigned value of the second character (e.g., where "T" has assigned value 50 and "H" has assigned value 31, "TH" hashes to (50*64)+31=3231). In single character words, the second character is assigned value "0". (The 64 characters represented include the letters a . . . z, numbers 0 . . . 9, and international characters.)

Each hash bucket points to (i.e., contains the address of) a separate table (302) having ten elements (or which is NULL). Each element ("sub-bucket") of the ten element table represents a group of words beginning with the particular two characters represented by the unique hash number. Each of the ten elements contains a pointer to a separate binary tree (303a) of words and a count of how many words are in the tree. The first sub-bucket contains words of three characters or less. The second sub-bucket contains words of four characters (e.g., THis, THat). The third sub-bucket contains words of five characters and so on until the tenth sub-bucket which contains words of 12 characters or more. Thus, the data structure potentially contains 40,960 binary trees associated with the Word List.

Each node (303a, 303b, 303c) of a binary tree in the Word List is composed of eight fields:

(1) flags for memory control;

(2) a pointer to the left tree node (or NULL);

(3) a pointer to the right tree node (or NULL);

(4) a counter for the number of granules (units) in which the word occurs;

(5) the unique Word Number associated with the word (assigned sequentially);

(6) the last granule (unit) in which the word was found;

(7) the length of the word; and

(8) the actual characters of the word.

The memory for each word can be allocated as a piece of a larger memory allocation unit to avoid wasting overhead space of the allocation system.

The NRWNS is comprised of a series of word numbers demarcated by granule boundary indicators, in the following form:

›100 45 22<New Granule>201 34 . .. <New Granule>. . . 50 20 1 . . . !,

where numbers represent the word numbers assigned to the respective words and <New Granule> represents granule demarcation. The purpose of the NRWNS is to track the granules in which a word occurs, not the total number of occurrences of the word. Thus, the word number for a particular word will only be stored in the NRWNS once for each granule in which it appears. For example, if there are 25 occurrences of the word "the" in the third granule, the word number for "the" will be placed into the NRWNS only once, i.e., upon its first occurrence in the granule. Because the NRWNS is built sequentially as the documents are scanned, it contains a sequential list of the words as they occur in the set of documents.

The Word List is complete after each of the selected documents has been scanned and added to the list.

This step of the preferred embodiment is described in detail by the following pseudocode:

1. Get a word or granule boundary from the file.

When end of file is reached go to 4.

2. If a granule boundary variable was returned then

2.1 Increment CurrentGranuleNumber.

2.2 Output new granule marker to NRWNS.

2.3 Go to 1.

3. A word was returned. Now process it.

3.1 Make hash number based on first two characters of word that preserves sort order (AA before AB) between 0 and 4096. Select this as the main hash bucket.

3.2 Make another hash number based on length of word (0-9).

3.3 If no binary tree exists for this hash into the 40,960 possible buckets, create a bucket and create a binary tree. If a low memory condition exists then go to 5, else go to 3.6.1

3.4 Otherwise, if the binary tree exists, then traverse the binary tree comparing the new word to the words in the tree.

3.5 If a match is found (old word), then

3.5.1 If CurrentGranuleNumber>LastUnitCounted for this entry then

3.5.1.1 If Low Memory Condition then go to 5.

3.5.1.2 Output this word's word number to the NRWNS. Increment TotalNRRefs.

3.5.1.3 Set LastUnitCounted for this word to CurrentGranuleNumber.

3.5.1.4 Increment frequency count for this word.

3.5.2 Go to 1.

3.6 If a match is not found, then

3.6.1 If Low Memory Condition then go to 5.

3.6.2 Add this new word to the binary tree.

3.6.3 Give this word the next available word number.

3.6.4 Output this word number to the NRWNS.

Increment TotaINRRefs.

3.6.5 Set LastUnitCounted for this word to CurrentGranuleNumber.

3.6.6 Increment word number variable.

3.6.7 go to 1.

4. Output end of file granule marker to NRWNS. Go to 6.

5. Save address of the current word in the current document for restart.

6. End Phase IA.

B. Create Alpha List and Output Disk

Second, a temporary alphabetized list file (the Alpha List) is created from the in-memory Word List. Referring to Table 1, a partial sample list, for each unique word the list contains the word, the word number, and the number of granules in which the word occurred (frequency count).

                  TABLE 1
    ______________________________________
                            FREQUENCY
    WORD           WORD #   COUNT
    ______________________________________
    Alice          3        10
    In             1        125
    Wonderland     5        7
    ______________________________________

                                      TABLE 2
    __________________________________________________________________________
                                       INDEX
    WORD   WORD#
                NEXT FLAG
                         REFS
                             BYTES
                                 MEM   POINTER
    __________________________________________________________________________
    NOW    1    12   1   5   2   53F5:0004
                                       13
    IS     2    8    1   5   2   53F5:0000
                                       10
    THE    3    13   1   7   1   53F5:0008
                                       17
    TIME   4    9    1   4   1   53F5:000C
                                       20
    FOR    5    7    1   4   2   53F4:000C
                                        6
    ALL    6    10   1   4   1   53F4:0006
                                        2
    GOOD   7    2    1   4   2   53F4:000E
                                        8
    MEN    8    1    1   4   1   53F5:0002
                                       12
    TO     9    0    1   4   2   53F5:000E
                                       21
    COME   10   14   1   4   1   53F4:0008
                                        3
    AID    11   6    1   4   2   53F4:0004
                                        0
    OF     12   3    1   5   2   53F5:0006
                                       15
    THEIR  13   4    1   5   2   53F5:000A
                                       18
    COUNTRY
           14   5    1   5   2   53F4:000A
                                        4
    __________________________________________________________________________

                                      TABLE 3
    __________________________________________________________________________
    PACKET 1.
           NumberUniqueWords
                       = 2000
           PathRecSize = 88 bytes
           NumGranules = 100
           FileRecSize = 25 Kbytes
           NumPasses   = 2
           NumFiles    = 10
    PACKET 2.
           aaron       offset 0
           mulek       offset 1095
    PACKET 3.
           c:.backslash.research.backslash.info.backslash.general.backslash.*.
           *
           c:.backslash.research.backslash.testing.backslash.*.doc
    PACKET 4.
           histalma.hst
                 10/10/90
                       4:12 p.
                             49,425 bytes
                                   pathrec = 0
           --    --    --    --    --
           --    --    --    --    --
           aletsumm.hst
                 4/1/85
                       12:00 a.
                              1,954 bytes
                                   pathrec = 1
    PACKET 5.
           file = 1,
                offset = 0
                       item offset = 0
           file = 1,
                offset = 245
                       item offset = 0
           file = 1,
                offset = 2481
                       item offset = 0
           --   --
           --   --
           file = 2,
                offset = 0
                       item offset = 100
           --   --
           --   --
           file = 10,
                offset = 598
                       item offset = 2530
    PACKET 6.
           aaron
                numrefs = 5
                       offset = 0
                              indexsize = 5
           --   --     --     --
           --   --     --     --
           mulek
                numrefs = 100
                       offset = 5000
                              indexsize = 40
    PACKET 7.
           Compressed Full Text Index
    PACKET 8.
           "Delete List" of Deleted Documents (Incremental merge
    __________________________________________________________________________
           only)

                  TABLE 4
    ______________________________________
               Document Number
    Bit String Code
                 1         2     3      4   5
    ______________________________________
    0     1        1     1       0   1      0   0
    ______________________________________

                  TABLE 5
    ______________________________________
                 Negative
            Code Jump Size
    ______________________________________
            000  1
            001  2
            010  3
            011  4
            100  5
            101  6
            110  7
            111  8
    ______________________________________

                  TABLE 6
    ______________________________________
                                          COL. 5
    COL. 1    COL. 2    COL. 3            REMAP
    GROUP     ITEM      ITEM     COL. 4   TABLE
    REFERENCE NAME      NUMBER   DELETED  ROW
    ______________________________________
    .backslash.TEST3.backslash.
              ITEM4     1                 1
              ITEM5     2                 1
              ITEM6     3                 1
              ITEM7     4                 1
              ITEM8     5        YES      2
              ITEM9     6                 3
              ITEM10    7        YES      4
    .backslash.TEST1.backslash.
              ITEM1     8                 5
              ITEM2     9                 5
              ITEM3 ----.vertline.
                        10                5
    .backslash.TEST4.backslash.
              ITEM11   .vertline.
                        11                7
              ITEM12   .vertline.
                        12                7
    .backslash.TEST1.backslash.
              ITEM13 <- 13                6
    ______________________________________

                                      TABLE 7
    __________________________________________________________________________
    REMAP TABLE
    ITEM
    REMAP                    GRANULE
    TABLE
         DELETE      NEW
                        ITEM        NEW
                                       GRANULE
    ROW  FLAG LOW
                 HIGH
                     LOW
                        OFFSET
                             LOW
                                HIGH
                                    LOW
                                       DELTA
    __________________________________________________________________________
    1    0    1  4   1   0   1  4   1  0
    2    1    5  5   0   0   5  5   0  0
    3    0    6  6   5  9C   6  6   5  -1
    4    1    7  7   0   0   7  7   0  0
    5    0    8  10  6  C3   8  10  6  -2
    6    0    13 13  9  138  13 13  9  -4
    7    0    11 12  10 160  11 12  10 -1
    __________________________________________________________________________

                  TABLE 8a
    ______________________________________
    NEW GRANULE
    CROSS REFERENCE TABLE
    ITEM         NEW OFFSET
    NUMBER       INTO PACKET 4
    ______________________________________
    1            0
    2            27
    3            4E
    4            75
    5            9C
    6            C3
    7            EA
    8            101
    9            138
    10           160
    11           188
    ______________________________________


              TABLE 8b
    ______________________________________
    OLD GRANULE
    CROSS REFERENCE TABLE
    ITEM         OLD OFFSET
    NUMBER       INTO PACKET 4
    ______________________________________
    1            0
    2            27
    3            4E
    4            75
    5            9C
    6            BC
    7            E3
    8            103
    9            12A
    10           141
    11           178
    12           1A0
    13           1C8
    ______________________________________

                  TABLE 9
    ______________________________________
    GRANULE SORTED ORDER LIST
    GRANULE         GRANULE
    SORTED ORDER    SORTED
    LIST ENTRY      ORDER
    ______________________________________
    1               1
    2               2
    3               3
    4               4
    5               5
    6               7
    7               6
    ______________________________________

                  TABLE 10
    ______________________________________
           REMAP  NEW
           GROUP  GRANULE
           NUMBER POINTER
    ______________________________________
           1      NULL
           2      NULL
           3      NULL
           4      NULL
           5      NULL
           6      NULL
           7      NULL
    ______________________________________


              TABLE 11
    ______________________________________
    ORIGINAL
    INDEX FOR
    WORD `FOLIAGE`
    (FROM PACKET 7)
    ______________________________________
    3
    4
    5
    11
    12
    13
    ______________________________________


              TABLE 12
    ______________________________________
    NEW
    GRANULE
    POINTER
    ______________________________________
    >1->3->4
    NULL
    NULL
    NULL
    NULL
    >9
    >10->11
    ______________________________________


              TABLE 13
    ______________________________________
    NEW INDEX
    FOR WORD
    `FOLIAGE`
    ______________________________________
    3
    4
    9
    10
    11
    ______________________________________

• Inventors
  Millett, Ronald P.;
• Assignee
  Novell, Inc. (Orem, UT)
• Published
  Jun-15-1999
• Current US Classes:
  704/4
  704/7
  704/9
  707/2
  707/3
  707/6
  715/531
• Application #
  888968
• International Classes
  G06F 017/30
• Field of Search
  707/1-6 707/531 707/532 707/3 704/4 704/7 704/9
• Examiner
  Black; Thomas G.
• Agent
  Dinsmore & Shohl LLP
• US Patent References:
  4318184
  4771385
  4817036
  4972349
  4991087
  5099426
  5109433
  5153831
  5201048
  5251129
  5297038
  5321606
  5321833
  5375235
  5383121
  5412807
  5701459
  5717912
  5745899