Method and apparatus for integrating multiple indexed files

• US 5,845,273 A
• Filed: 06/27/1996
• Issued: 12/01/1998
• Est. Priority Date: 06/27/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jindal, Ajay Kumar
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HO, RUAY L
• Application Number:
  US08/670,159
• Time in Patent Office: 887 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/100, 707/102, 707/200, 707/201, 707/205, 397/200.53, 397/183.14, 345/440
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system for integrating multiple indexed files and searching the resulting integrated indexed file. An indexed core content file, which includes a core keyword list containing core keywords, can be updated with update keywords of an update content file. The update content file is accessed and, in response, a virtual keyword list is generated. The virtual keyword list, which contains update keywords and core keywords, is created by determining a position for inserting each update keyword within the core keyword list and positions for each core keyword affected by the insertion of update keywords. An index mapping table is created for tracking the positions of the update keywords and the core keywords within the virtual keyword list. The index mapping table maps the positions of the update keywords within the virtual keyword list to the update keywords within the update content file and maps the positions of the core keywords within the virtual keyword list to the core keywords within the core keyword list.

Claims

1. A computer-implemented method for updating an indexed core content file having a core keyword list containing core keywords, each identified by a core keyword index number, with update keywords of an indexed update content file, comprising the steps of:

reading the update content file;

generating a virtual keyword list of update keywords and core keywords by determining a position for inserting each update keyword within the core keyword list and a position for each core keyword resulting from insertion of each update keyword; and

creating an index mapping table for tracking the positions of the update keywords and the core keywords within the virtual keyword list.

2. The method of claim 1, wherein the index mapping table maps the positions of the update keywords within the virtual keyword list to the update keywords within an update keyword list of the update content file and maps the positions of the core keywords within the virtual keyword list to the core keywords within the core keyword list.

3. The method of claim 1, wherein the index mapping table comprises table entries, each characterized by:

a table index number defining the position of a corresponding update keyword in the virtual keyword list;

a core offset value defining a shift in position of the core keywords located after the corresponding update keyword, the position shift occurring as a result of the insertion of the update keywords within the core keyword list;

an update file identifier for identifying the update content file associated with the corresponding update keyword; and

an update keyword index number for the corresponding update keyword, the update keyword index number defining the position of the corresponding update keyword within an update keyword list of the identified update content file.

4. The method of claim 3, wherein the difference between the table index number and the core offset value defines the core keyword index number for the core keywords located after the corresponding update keyword.

5. The method of claim 3, wherein the core offset value defines the difference between an original position of the core keyword within the core keyword list and the shifted position of the core keyword within the virtual keyword list.

6. The method of claim 3, wherein the core keyword list is maintained as an ordered list, and the corresponding update keyword is inserted within the core keyword list at a position immediately prior to the core keyword having a value that is greater than a value for the corresponding update keyword.

7. The method of claim 6, wherein the core keyword list is ordered by positioning the core keywords in a sequence from low value to high value.

8. A computer-readable medium on which is stored an index mapping table for mapping positions of update keywords and core keywords to a virtual keyword list created in response to updating an indexed core content file with indexed update content files, each core keyword maintained in a core keyword list of the core content file and identified by a core keyword index number, each update keyword maintained in an update keyword list of one of the update content files and identified by an update keyword index number, the index mapping table comprising table entries, each table entry containing fields, comprising:

a table index number defining a position of a corresponding update keyword in the virtual keyword list;

a core offset value defining a shift in a position of the core keywords located after the corresponding update keyword, the position shift occurring in response to inserting the update keywords within the core keyword list;

an update file identifier for identifying the update content file associated with the corresponding update keyword; and

an update keyword index number for the corresponding update keyword, the update keyword index number defining the position of the corresponding keyword within the update keyword list of the identified update content file.

9. The computer-readable medium of claim 8, wherein the difference between the table index number and the core offset value defines the core keyword index number for the core keywords located after the corresponding update keyword.

10. The computer-readable medium of claim 8, wherein the core offset value defines the difference between an original position of the core keyword within the core keyword list and the shifted position of the core keyword within the virtual keyword list.

11. The computer-readable medium of claim 8, wherein the core keywords are ordered within the core keyword list from low value to high value, and the corresponding update keyword is inserted within the core keyword list at a position immediately prior to the core keyword having a value that is slightly greater than a value for the corresponding update keyword.

12. The computer-readable medium of claim 8, wherein each entry in the index mapping table further comprises a token in a duplicate-type field of the index mapping table, the token assigned either a first value or a second value, the first value indicating that the update keyword corresponding to the token represents addendum content, and the second value indicating that the corresponding update keyword represents replacement content.

13. A method for updating an indexed core content file having a core keyword list containing core keywords, each identified by a core keyword index number, with update keywords of update content files, each update keyword having a corresponding value, the method comprising the steps of:

(a) initializing a pointer for each update content file by setting the pointer to select the update keyword having the lowest value in each update content file;

(b) initializing a core offset value by assigning the core offset value a predefined value;

(c) identifying the update keyword having the lowest value among the update content files and selected by the pointer;

(d) constructing a virtual keyword list by determining a position for inserting the identified update keyword within the core keyword list immediately prior to a selected core keyword having a value that is equal to or slightly greater than the identified update keyword and a position for the selected core keyword based on the insertion of the update keyword within the core keyword list;

(e) creating an entry within an index mapping table for tracking the positions of the update keywords and the core keywords within the virtual keyword list;

(f) incrementing the pointer for the selected update content file; and

(g) repeating steps a-f for each remaining update keyword.

14. The method of claim 13, wherein each entry in the index mapping table comprises:

a table index number defining the position of a corresponding update keyword in the virtual keyword list;

the core offset value, which defines a shift in the position of the selected core keyword within the core keyword list;

an update file identifier for identifying the update content file associated with the identified update keyword; and

an update keyword index number for the identified update keyword, the update keyword index number defining the position of the identified keyword within an update keyword list of the update content file.

15. The method of claim 14, wherein the update keywords within the update content files are sorted based on values assigned to the update keywords, the update keywords sorted from a low value to a high value.

16. The method of claim 14, wherein a difference between the table index number and the core offset value defines one of the core keyword index numbers of the core keyword list.

17. The method of claim 14, wherein, in the event that the identified update keyword is equal to the selected core keyword, then the update keyword represents supplemental content.

18. A method for searching for a desired keyword in an updated version of an indexed core content file by using a index mapping table that maps positions of update keywords and core keywords to a virtual keyword list, the virtual keyword list created in response to updating the indexed core content file, the indexed core content file comprising core keywords maintained in a core keyword list and identified by a core keyword index number, the indexed core content file updated with update content files containing the update keywords, each update keyword maintained in an update keyword list and identified by an update keyword index number,

the index mapping table comprising a table index number defining a position of a corresponding update keyword in the virtual keyword list, a core offset value defining a shift in position of the core keywords located after the corresponding update keyword, the position shift occurring as a result of the insertion of the update keywords within the core keyword list, an update file identifier for identifying the update content file associated with the corresponding update keyword, and an update index for defining an update keyword index number for the corresponding update keyword, the update keyword index number defining the position of the corresponding update keyword within an update keyword list of the identified update content file, comprising the steps of

(a) identifying a search index number corresponding to a desired keyword;

(b) selecting the largest table index number in the index mapping table that is less than or equal to the search index number;

(c) if the selected table index number is not equal to the search index number, then calculating a core keyword index number by subtracting the core offset value from the search index value, and using the calculated core keyword index number to locate the desired keyword in the core keyword list; and

(d) if the selected table index number is equal to the search index number, then comparing the core offset value associated with the selected index value to the core offset value in a previous entry of the index mapping table;

if the core offset values are different, then use the update index associated with the selected index number to locate the update keyword index number, and use the update keyword index number to look-up the desired keyword in the update keyword list; and

if the core offset values are the same, then calculate a core keyword index number by subtracting the core offset value from the search index number, and use the calculated core keyword index number to locate the desired keyword in the core keyword list.

19. A computer system operative to execute a program module for updating an indexed core content file having a core keyword list containing core keywords, each identified by a core keyword index number, with update keywords of an update content file, comprising:

a processing device; and

a memory, coupled to the processing device, for storing the program module;

the processing device, in response to instructions of the program module, operates to;

read the update content file;

generate a virtual keyword list of update keywords and core keywords by determining a position for inserting each update keyword within the core keyword list and a position for each core keyword resulting from insertion of each update keyword; and

create an index mapping table for tracking the positions of the update keywords and the core keywords within the virtual keyword list.

20. The computer system of claim 19, wherein the index mapping table comprises table entries, each characterized by:

a table index number defining the position of a corresponding update keyword in the virtual keyword list;

a core offset value defining a shift in position of the core keywords located after the corresponding update keyword, the position shift occurring as a result of the insertion of the update keywords within the core keyword list;

an update file identifier for identifying the update content file associated with the corresponding update keyword; and

an update keyword index number for the corresponding update keyword, the update keyword index number defining the position of the corresponding keyword within an update keyword list of the update content file.

21. A computer-readable medium on which is stored a program module for updating an indexed core content file having a core keyword list containing core keywords, each identified by a core keyword index number, with update keywords of an update content file, the program module comprising instructions which, when executed by the computer, performs the steps of:

reading the update content file;

generating a virtual keyword list of update keywords and core keywords by determining a position for inserting each update keyword within the core keyword list and a position for each core keyword resulting from insertion of each update keyword; and

creating an index mapping table for tracking the positions of the update keywords and the core keywords within the virtual keyword list.

22. The computer-readable medium of claim 21, wherein the index mapping table comprises table entries, each characterized by:

a table index number defining the position of a corresponding update keyword in the virtual keyword list;

a core offset value defining a shift in position of the core keywords located after the corresponding update keyword, the position shift occurring as a result of the insertion of the update keywords within the core keyword list;

an update file identifier for identifying the update content file associated with the corresponding update keyword; and

an update keyword index number for the corresponding update keyword, the update keyword index number defining the position of the corresponding keyword within an update keyword list of the update content file.

23. A method for searching for a desired virtual keyword index number for a virtual keyword list by using an index mapping table that maps positions of update keywords and core keywords to the virtual keyword list, the virtual keyword list created in response to updating an indexed core content file, the indexed core content file comprising core keywords maintained in a core keyword list and identified by a core keyword index number, the indexed core content file updated with update content files containing the update keywords, each update keyword maintained in an update keyword list and identified by an update keyword index number,

the index mapping table comprising entries having a table index number defining a position of a corresponding update keyword in the virtual keyword list, a core offset value defining a shift in position of the core keywords located after the corresponding update keyword, the position shift occurring as a result of the insertion of the update keywords within the core keyword list, an update file identifier for identifying the update content file associated with the corresponding update keyword and an update index for defining an update keyword index number for the corresponding update keyword, the update keyword index number defining the position of the corresponding update keyword within the update keyword list of the update content file, comprising the steps of

(a) identifying a search keyword corresponding to the desired virtual keyword index number;

(b) searching for the search keyword in the core keyword list and returning a selected core keyword representing the closest match to the search keyword;

(c) for each update content file, searching for the search keyword in the update keyword list and returning a selected update keyword representing the closest match to the search keyword;

(d) applying search criteria to determine which of the selected core keyword and each selected update keyword represents the best match for the search keyword; and

(e) in event that the selected core keyword represents the best match, then locate one of the entries in the index mapping table wherein the core keyword index number for the selected keyword is greater than a value defined by "the table index number+1-the core offset value", wherein the desired virtual keyword index number is defined by the sum of the core keyword index number and the core offset value for the located entry,

in event that one of the selected update keywords represents the best match, then locate one of the entries in the index mapping table wherein the update file identifier is equal to the update identifier for the update content file associated with the selected update keyword and the update index is equal to the update keyword index number for the selected update keyword, wherein the desired virtual keyword index number is defined by the table index number for the located entry.

24. The method of claim 23, wherein the step of searching for the search keyword in the update keyword list for each update content file can return a set of selected update keywords representing the closest match to the search keyword.