Method and means using digital data processing means for locating representations in a stored textual data base

• US 4,495,566 A
• Filed: 09/30/1981
• Issued: 01/22/1985
• Est. Priority Date: 09/30/1981
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: System Development Incorporated
• Inventors: Galie, Louis M., Dickinson, Robert V.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): Malamud, Ronni S.
• Application Number:
  US06/307,093
• Time in Patent Office: 1,210 Days
• Field of Search: 364/900, 364/200
• US Class Current: 1/1
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

The method uses digital data processing means and stored representations of a table of textual block identifiers for locating in a stored textual data base those textual blocks having the best match with a query. Textual block identifiers each provide an indication of a textual block in a stored data base which contains the corresponding word. The method comprises the following steps: A query word is received having representations of a plurality of words to be located in textual blocks in the stored data base. For each of a plurality of the query words, determine a corresponding set of equivalent words which are contained in the stored data base. Each set of equivalent words is equivalent to the corresponding query word. Each equivalent word has a corresponding group of textual block identifiers represented in the stored table. Process the representations of the textual block identifiers in those groups which correspond to the determined equivalent words to thereby form a score for at least one textual block. The score provides an indication of the total number of the sets which have at least one equivalent word in the at least one textual block. The score is utilized to provide output data pertaining to selected textual blocks in the stored textual data base.

Claims

1. A method using digital data processing means and stored textual block identifiers in a table for locating in a stored data base having a plurality of textual blocks, those textual blocks having the best match with a query, the textual blocks in the data base having words grouped into such textual blocks, the textual block identifiers being grouped and each group of textual block identifiers corresponding to one of the blocks in the stored data base, each of the textual block identifiers providing an indication of one of the textual blocks in the stored data base which contains the word corresponding to the group of textual block identifiers in which the textual block identifier is located, the method comprising the steps of:

(a) receiving a query having representations of a plurality of query words to be located in the textual blocks contained in the stored data base;

(b) determining, for each one of a plurality of the query words, at least one corresponding set of equivalent words which are contained in the stored data base, each of the equivalent words in such set being equivalent to the corresponding query word and corresponding to one of the groups of textual block identifiers;

(c) processing the textual block identifiers contained in the groups of textual block identifiers which correspond to the words in the determined sets of equivalent words to thereby form a representation of a score for at least a first of the textual blocks which is represented by said textual block identifiers, the representation of a score representing the total number of said sets of equivalent words which have at least one of said equivalent words in said at least a first of the textual blocks; and

(d) utilizing said representation of a score to provide output data pertaining to at least one textual block, for which a representation of a score has been formed.

2. A method according to claim 1 wherein the textual blocks comprise paragraphs and wherein the step of utilizing comprises the step of outputting the paragraphs as the textual blocks.

3. A method according to claim 1 wherein the step of processing comprises the step of reading out, from said textual block identifiers in a table, the texual block identifiers which correspond to each equivalent word which is determined in the step of determining.

4. A method according to claim 3 wherein the step of processing further comprises the step of performing at least one merge sort on representations of the textual block identifiers which are read out in the step of processing.

5. A method according to claim 1 wherein the step of processing comprises the steps of:

merging the textual block identifiers in the groups corresponding to the equivalent words in the sets of equivalent words into a further group of textual block identifiers, one of said further groups of textual block identifiers being formed for each set of equivalent words without duplicating therein any of the same textual block identifiers; and

further processing each said further group of textual block identifiers to thereby form said representation of a score.

6. A method according to claim 5 wherein said step of further processing comprises the steps of:

merging the textual block identifiers taken from different ones of said further groups of textual block identifiers without duplicating therein any of the same textual block identifiers; and

the means for step of processing comprises the step of forming a representation of a score for each of a plurality of the textual blocks, each said representation of a score indicating the number of further groups which contain at least one of the textual block identifiers corresponding to such textual block.

7. A method according to claim 1 wherein, in the step of processing, a different said representation of a score is provided for each of a plurality of the textual blocks, each representation of a score for each of the plurality of textual blocks providing an indication of the total number of sets of equivalent words which contain at least one of the equivalent words in the corresponding textual block.

8. A method according to claim 1 wherein, in the step of processing, one of said representations of a score is formed for each of a plurality of textual blocks;

and

wherein said step of utilizing said representation of a score to provide output data comprises the steps of selecting representations of textual blocks from the stored data base for output, which textual blocks are indicated by the textual block identifiers, and outputting the selected representations of the textual blocks ordered as a function of the corresponding representations of a score.

9. A method according to claim 8 wherein the representations of textual blocks are output in decreasing value order of the corresponding representations of a score.

10. A method according to claim 1 wherein the step of processing comprises the steps of:

forming a pointer set, each pointer set containing a representation of at least one pointer to one of said groups of textual block identifiers, utilizing the at least one representation of a pointer from one of said pointer sets to select a textual block identifier from said representation of a table.

11. A method according to claim 1 wherein the step of determining a corresponding set of equivalent words for a given one of the query words comprises the step of selecting words in the data base which are acceptable misspellings and acceptable inflections of the query word.

12. A method according to claim 11 wherein the step of selecting words which are acceptable misspellings and acceptable inflections comprises the step of selecting words which have an exact match, a character transposition, a single character deletion, or a single character insertion between a stem portion of a query word and the beginning characters of a data base word and which also have acceptable suffixes.

13. Digital data processing means using stored textual block identifiers in a table for locating in a stored data base having a plurality of textual blocks, those textual blocks having the best match with a query, the textual blocks in the data base having words grouped into such textual blocks, the textual block identifiers being grouped and each group of textual block identifiers corresponding to one of the words in the stored data base, each of the textual block identifiers providing an indication of one of the textual blocks in the stored data base which contains the word corresponding to the group of textual block identifiers in which the textual block identifier is located, the data processing means comprising:

(a) means for receiving a query having representations of a plurality of query words to be located in the textual blocks contained in the stored data base;

(b) means for determining, for each one of a plurality of the query words, at least one corresponding set of equivalent words which are contained in the stored data base, each of the equivalent words in such set being equivalent to the corresponding query word and corresponding to one of the groups of textual block identifiers;

(c) means for processing the textual block identifiers contained in the groups of textual block identifiers which correspond to the words in the determined sets of equivalent words to thereby form a representation of a score for at least a first of the textual blocks which is represented by said textual block identifiers, the representation of a score representing the total number of said sets of equivalent words which have at least one of said equivalent words in said at least a first of the textual blocks; and

(d) means for utilizing said representation of a score to provide output data pertaining to at least one textual block, for which a representation of a score has been formed.

14. Means according to claim 13 wherein a textual block consists of a paragraph of the textual data base.

15. Means according to claim 13 wherein the means for processing comprises:

means for reading out, from said textual block identifiers in a table, the textual block identifiers which correspond to each equivalent word which is determined by the means for determining.

16. Means according to claim 15 wherein the means for processing further comprises means performing at lea one merge sort on representations of the textual block identifiers which are read out in forming the representation of a score.

17. Means according to claim 13 wherein the means for processing comprises:

means for merging the textual block identifiers in the groups corresponding to the equivalent words in the sets of equivalent words into a further group of textual block identifiers, one of said further groups of textual block identifiers being formed for each set of equivalent words without duplicating therein any of the same textual block identifiers; and

means for further processing each said further group of textual block identifers to thereby form said representation of a score.

18. Means according to claim 17 wherein said means for further processing comprises:

means for merging the textual block identifiers taken from different ones of said further groups of textual block identifiers without duplicating therein any of the same textual block identifiers; and

the means for processing comprises means for forming a representation of a score for each a plurality of the textual blocks, each said representation of a score indicating the number of further groups which contain at least one of the textual block identifiers corresponding to such textual block.

19. Means according to claim 13 wherein the means for processing comprises means for providing a different said representation of a score for each of a plurality of the textual blocks, each representation of a score for each of the plurality of textual blocks providing an indication of the total number of sets of equivalent words which contain at least one of the equivalent words in the corresponding textual block.

20. Means according to claim 13 wherein the means for processing comprises means for providing one of said representation of a score for each of a plurality of textual blocks;

and

wherein said means for utilizing said representation of a score to provide output data comprises means for selecting representations of textual blocks from the stored data base for output, which textual blocks are indicated by the textual block identifiers, and means for outputting the selected representations of the textual blocks as a function of the corresponding representations of a score.

21. Means according to claim 20 wherein the means for outputting is operative for outputting representations of textual blocks in decreasing value order according to the representation of a score.

22. Means according to claim 13 wherein the means for processing comprises:

means for forming a pointer set, each pointer in the set containing a representation of at least one pointer to one of said groups of textual block identifiers, means for utilizing at least one representation of a pointer from one of said pointer sets to select a textual block identifier from said representation of a table.

23. Means according to claim 13 wherein the means for determining a corresponding set of equivalent words for a given one of the query words comprises means for selecting words in the data base which are acceptable misspellings and acceptable inflections of the query word.

24. Means according to claim 23 wherein the means for selecting words which are acceptable misspellings and acceptable inflections comprises means for selecting words which have an exact match, a character transposition, a character deletion or a character insertion between a stem portion of a query word and the beginning characters of a data base word.

25. Means according to claim 13 comprising at least one memory for storing and deriving therefrom said textual block identifiers in a table.

26. Means according to claim 20 comprising memory means for storing representations of the textual data base from which the representations of textual blocks are selected.

27. A method using digital data processing means and stored textual block identifiers in a table for locating in a stored data base having a plurality of textual blocks, those textual blocks having the best match with a query, the textual blocks in the data base having words grouped into such textual blocks, the textual block identifiers being grouped and each group of textual block identifiers corresponding to one of the words in the stored data base, each of the textual block identifiers providing an indication of one of the textual blocks in the stored data based which contains the word corresponding to the group of textual block identifiers in which the textual blocks comprising the steps of:

(a) receiving a query having a plurality of query words to be located in the textual blocks contained in the stored data base;

(b) determining, for each one of a plurality of the query words, at least one corresponding set of equivalent words which are contained in the stored data base, each of the equivalent words in each set being equivalent to the corresponding query word and corresponding to one of the groups of textual block identifiers;

(c) processing the textual block identifiers contained in the groups of textual block identifiers which correspond to the words in the determined sets of equivalent words to thereby form a representation of a score for at least a first of the textual blocks which is represented by said textual block identifiers, the representation of a score representing the total number of said sets of equivalent words which have at least one of said equivalent words in said at least a first of the textual blocks; and

(d) utilizing said representation of a score to provide signals for locating at least one textual block in said stored data base.

28. Digital data processing means using stored textual block identifers in a table for locating in a stored data base of having a plurality of textual blocks those textual blocks having the best match with a query, the textual blocks in the data base having words grouped into such textual blocks, the textual block identifiers being grouped and each group of textual block identifiers corresponding to one of the words in the stored data base, each of the textual block identfiers providing an indication of one of the textual blocks in the stored data base which contains the word corresponding to the group of textual block identifiers in which the textual block identifier is located, the data processing means comprising:

(a) means for receiving a query having a plurality of query words to be located in the textual blocks contained in the stored data base;

(b) means for determining, for each one of a plurality of the query words, at least one corresponding set of equivalent words which are contained in the stored data base, each of the equivalent words in such set being equivalent to the corresponding query word and corresponding to one of the groups of textual block identifiers;

(c) means for processing the textual block identifiers contained in the groups of textual block identifiers which correspond to the words in the determined sets of equivalent words to thereby form a representation of a score for at least a first of the textual blocks which is represente by said textual block identifiers, the representation of a score representing the total number of said sets of equivalent words which have at least one of said equivalent words in said at least a first of the textual blocks; and

(d) means for utilizing said representations of a score to provide signals for locating at least one textual block, for which a representation of a score has been formed, in said stored data base.