Annotating token sequences within documents

• US 20080072134A1
• Filed: 09/19/2006
• Published: 03/20/2008
• Est. Priority Date: 09/19/2006
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ramakrishnan, Ganesh, Joshi, Sachindra, Balakrishnan, Sreeram Viswanath
• Application Number:
  US11/532,977
• Publication Number:
  US 20080072134A1
• Time in Patent Office: Days
• US Class Current: 715/230
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 40/295 Named entity recognition

Abstract

Token sequences within a number of documents are annotated. First, a base inverse index for unique tokens within the documents is received. The base inverse index includes a set of the unique tokens within the documents and a set of location lists for each unique token. Second, indices are created for a set of the token sequences within the documents from the base inverse index, to annotate the token sequences.

Claims

1. A method for annotating token sequences within a plurality of documents comprising:

receiving a base inverse index for unique tokens within the plurality of documents, where the base inverse index comprises a set of the unique tokens within the plurality of documents and a set of location lists for each unique token; and

,

creating indices for a set of the token sequences within the plurality of documents from the base inverse index, to annotate the token sequences.

2. The method of claim 1, wherein the base inverse index has an ordered list of the unique tokens, and each location list of the base inverse index is an ordered list of pointers to the plurality of documents.

3. The method of claim 2, wherein each location list comprises an ordered list of pointers configured to locate a document from the plurality of documents and a token offset within the document corresponding to a single occurrence of a token sequence associated with the location list.

4. The method of claim 2, wherein an annotation is defined as a dictionary label associated with all the token sequences annotating dictionary entities of a dictionary, the method further comprising:

creating an index for each token sequence within the dictionary having more than one token, as a multiple-token entry within the dictionary; and

,

creating an index to a final dictionary annotation, by merging the indices for the multiple-token entries within the dictionary and single token entries within the dictionary.

5. The method of claim 4, wherein creating an index for each token sequence within the dictionary having more than one token comprises searching indices for a sequence of tokens within the token sequence for a subset of locations in which all tokens sequentially occur in the sequence.

6. The method of claim 1, further comprising defining a regular-expression entity as a token that matches a regular expression, the regular-expression entity employed in annotating the token sequences within the plurality of documents.

7. The method of claim 1, further comprising defining a merge operation operable on a first location list and a second location list that returns a location list of pointers, where each pointer of the location list returned is within the first location list or the second location list.

8. The method of claim 1, further comprising defining a consecutive-intersection operation operable on a first location list and a second location list that returns a location list of pointers.

9. The method of claim 8, wherein each pointer of the location list returned points to a sequence of tokens having a first consecutive subsequence within the first location list and a second consecutive subsequence within the second location list, and

wherein determining the index as the consecutive intersection of all of the plurality of location lists of pointers within the dictionary entity comprises employing the consecutive-intersection operation.

10. A method for annotating each of a plurality of tokens within a plurality of documents comprising:

receiving a base inverse index for the plurality of documents, the base inverse index having an ordered list of unique tokens and a set of location lists for each unique token, each location list being an ordered list of pointers to the plurality of documents;

for each of a plurality of derived entities, each derived entity being a sequence of tokens, determining an index as a consecutive intersection of all of a plurality of location lists of pointers within the derived entity, such that the index contains location lists of pointers to all occurrences of the sequence of tokens of the derived entity within the plurality of documents; and

,

merging the location lists of pointers for all the derived entities to result in a final location list, such that the documents are annotated with the tokens of the derived entities.

11. The method of claim 10, further comprising composing each derived entity from a plurality of preexisting simpler entities using a set of rules written in modified context-free grammar (CFG).

12. The method of claim 11, wherein composing each derived entity from the preexisting simpler entities using the set of rules written in modified CFG comprises deriving the derived entity from a first consecutive sequence of tokens and a second consecutive sequence of tokens.

13. The method of claim 12, further comprising modifying the CFG from each derived entity is composed from preexisting simpler entity rules, comprising:

defining a parallel intersection operation operable on a first location list and a second location list that returns a location list of pointers that is a subset of pointers to sequences of tokens within both the first location list and the second location list.

14. The method of claim 13, wherein modifying the CFG further comprises:

defining a first extension to consecutive-intersection operation operable on a first location list and a second location list that returns a location list of pointers that is a subset of the second location list, where every sequence within the subset is immediately preceded by a sequence within the first location list; and

,

defining a second extension to consecutive-intersection operation operable on a first location list and a second location list that returns a location list of pointers that is a subset of the first location list, where every sequence within the subset is immediately preceded by a sequence within the second location list.

15. The method of claim 10, further comprising defining a merge operation operable on a first location list and a second location list that returns a location list of pointers, where each pointer of the location list returned is within the first location list or the second location list,

wherein merging the location lists of pointers for all the derived entities comprises employing the merge operation.

16. The method of claim 10, further comprising defining a consecutive-intersection operation operable on a first location list and a second location list that returns a location list of pointers, where each pointer of the location list returned points to a sequence of tokens having a first consecutive subsequence within the first location list and a second consecutive subsequence within the second location list,

wherein determining the index as the consecutive intersection of all of the plurality of location lists of pointers within the derived entity comprises employing the consecutive-intersection operation.

17. The method of claim 10, further comprising imposing a partial ordering of annotations of the tokens within the plurality of documents, so that lower-order annotations do not overlap with higher-order annotations.

18. The method of claim 17, further comprising defining on apply-order operation operable on a location list having an annotation type and an associated integer for the annotation type that returns a location list of pointers that is a subset of the location list having the annotation type for which all tokens in sequences of the subset returned having values less than or equal to the associated integer,

wherein imposing the partial ordering comprises employing the apply-order operation.

19. An article of manufacture comprising:

a tangible computer-readable medium; and

,

means in the medium for annotating each of a plurality of tokens within a plurality of documents based on a base inverse index for the plurality of documents.

20. A computerized system comprising:

a computer-readable medium storing;

a plurality of documents having a plurality of tokens;

a base inverse index previously generated for the documents;

a mechanism to annotate each token within the documents based on the base inverse index, such that annotation of the plurality of documents occurs at a same time.