Systems and methods for indexing each level of the inner structure of a string over a language having a vocabulary and a grammar

• US 7,194,450 B2
• Filed: 12/19/2003
• Issued: 03/20/2007
• Est. Priority Date: 12/19/2003
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Roux, Claude, Jacquemin, Bernard
• Primary Examiner(s): Alam; Hosain
• Assistant Examiner(s): Lin; Shew-fen
• Application Number:
  US10/739,191
• Publication Number:
  US 20050138000A1
• Time in Patent Office: 1,187 Days
• Field of Search: 707 1- 10, 707200-205, 707/101
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Systems and methods for indexing and searching the inner structure of a string over a language having a vocabulary and a grammar using bit vectors. The index preserves the inner gramatical structure of the string while allowing for a fast search. A single search provides immediate access to every level of a document, without having to re-search a single string to determine which sub-parts of that string match the search string. When a string is indexed, the index maintains a compositional representation and the grammatical relationship between the elements of the vocabulary according to the language. The string is then indexed on different levels by disregarding some of the grammatical relationships of component levels.

Claims

1. A computer-executable method for indexing at least one string containing a language having a vocabulary and a grammar for subsequent retrieval comprising:

receiving at least one input string containing a language having a vocabulary and a grammar;

dividing each string into a plurality of component parts according to the grammar, wherein each component part includes at least one word and at least one grammatical relationship of the at least one word within the language of the input string;

determining a bit index for each component part;

unioning, for each at least one set of component parts, the bit indices of the component parts within that set of component parts into a bit index for that set of component parts; and

recording the bit index for the at least one set of component parts in a memory for subsequent use in document retrieval.

2. The method of claim 1, wherein the at least one string comprises at least one document containing text.

3. The method of claim 1, wherein the each of the at least one set of component parts represents a level selected from a group of levels of the input string consisting of a sentence level, a paragraph level, and a document level.

4. The method of claim 1, wherein dividing that string into a plurality of component parts comprises dividing that string into a plurality of grouped units.

5. The method of claim 4, wherein dividing that string into a plurality of component parts further comprises dividing each grouped unit into a plurality of elements.

6. The method of claim 5, wherein unioning, for each at least one set of component parts, the bit indices of the component parts within that set of component parts further comprises unioning, for each grouped unit, the bit indices of the elements of that grouped unit to form a bit index for that grouped unit.

7. The method of claim 6, further comprising combining the at least one grouped unit into at least one sentence, wherein unioning, for each at least one set of component parts, the bit indices of the component parts within that set of component parts further comprises unioning, for each at least one sentence, the bit indices of the at least one grouped unit of that sentence to form a bit index for that sentence.

8. The method of claim 7, further comprising combining the at least one sentence into at least one paragraph, wherein unioning, for each at least one set of component parts, the bit indices of the component parts within that set of component parts further comprises unioning, for each of the at least one paragraph, the bit indices of the at least one sentence of that paragraph to form a bit index for that paragraph.

9. The method of claim 8, further comprising combining the at least one paragraph into at least one document, wherein unioning, for each at least one set of component parts, the bit indices of the component parts within that set of component parts further comprises unioning, for each of the at least one document, the bit indices of the at least one paragraph of that document to form a bit index for that document.

10. The method of claim 5, wherein unioning, for each at least one set of component parts, the bit indices of the component parts within that set of component parts further comprises unioning the bit indices of a number of elements, the number of elements associated with a given grouped unit, to form a bit index for that grouped unit.

11. The method of claim 10, wherein unioning, for each at least one set of component parts, the bit indices of the component parts within that set of component parts further comprises unioning the bit indices of a number of grouped units, the number of grouped units associated with a given sentence, to form a bit index for that sentence.

12. The method of claim 11, wherein unioning, for each at least one set of component parts, the bit indices of the component parts within that set of component parts further comprises unioning the bit indices of a number of sentences, the number of sentences associated with a given paragraph, to form a bit index for that paragraph.

13. The method of claim 12, wherein unioning, for each at least one set of component parts, the bit indices of the component parts within that set of component parts further comprises unioning the bit indices of a number of paragraphs, the number of paragraphs associated with a given document, to form a bit index for that document.

14. The method of claim 1, wherein dividing that string into a plurality of component parts comprises dividing that string into at least one sentence.

15. The method of claim 14, wherein unioning, for each at least one set of component parts, the bit indices of the component parts within that set of component parts comprises unioning the bit indices of a number of elements, the number of elements associated with a given sentence, to form a bit index for that sentence.

16. The method of claim 1, wherein dividing that string into a plurality of component parts comprises dividing that string into at least one paragraph.

17. The method of claim 16, wherein unioning, for each at least one set of component parts, the bit indices of the component parts within that set of component parts comprises unioning the bit indices of a number of elements, the number of elements associated with a given paragraph, to form a bit index for that paragraph.

32. The method of claim 1, further comprising:

determining a bit index of a search string;

retrieving a bit index of an indexed string;

determining an intersection of the search string bit index and the indexed string bit index; and

comparing the intersection of the search string bit index and the indexed string bit index with the search string bit index.

18. A computer-executed string indexing system that indexes at least one string containing a language having a vocabulary and a grammar for subsequent retrieval, comprising:

a dividing circuit, routine, or application that inputs the at least one string, divides the string according to the grammar and outputs at least one component part, each component part including at least one word and at least one grammatical relationship of the at least one word within the language of the input string;

an element index assigning circuit, routine, or application that assigns an index value to each component part;

an index converting circuit, routine, or application that converts each index value into a corresponding bit index;

a unioning circuit, routine, or application that inputs two or more bit indices and outputs a bit index representing the union of the input two or more bit indices; and

a memory that stores the bit index for subsequent retrieval.

19. The system of claim 18, wherein the dividing circuit, routine, or application comprises:

a parsing circuit, routine, or application that inputs the at least one string and outputs at least one corresponding set of sub-parts for each of the at least one string;

a deconstructing circuit, routine, or application that inputs one or more sub-parts and breaks each sub-part unit into component parts.

20. The system of claim 18, further comprising a presence-determining circuit, routine, or application that inputs a component part and determines whether that component part is present in a list of the assigned index values.

21. The system of claim 18, wherein the at least one string comprises at least one document containing text.

22. The system of claim 19, wherein the parsing circuit, routine, or application divides, for each string, that string into a plurality of grouped units as the sub-parts.

23. The system of claim 22, wherein the deconstructing circuit, routine, or application inputs a grouped unit as each sub-part and, for that grouped unit, outputs a set of at least one element contained within that grouped unit as the component parts.

24. The system of claim 23, wherein the element index assigning circuit, routine, or application assigns each element a unique element index as the index value.

25. The system of claim 24, wherein the index converting circuit, routine, or application, for each element, converts that element'"'"'s unique element index into a corresponding bit index.

26. The system of claim 25, wherein the unioning circuit, routine, or application unions the bit indices of a set of at least one element of a given grouped unit to form a bit index for that grouped unit.

27. The system of claim 26, wherein the unioning circuit, routine, or application unions the bit indices of a number of grouped units, the number of grouped units associated with a given sentence, to form a bit index for that sentence.

28. The system of claim 27, wherein the unioning circuit, routine, or application unions the bit indices of a number of sentences, the number of sentences associated with a given paragraph, to form a bit index for that paragraph.

29. The system of claim 28, wherein the unioning circuit, routine, or application unions the bit indices of a number of paragraphs, the number of paragraphs associated with a given document, to form a bit index for that document.

30. The system of claim 18, wherein the parsing circuit, routine, or application divides the string into at least one corresponding set of at least one sentence as the at least one component part.

31. The system of claim 18, wherein the parsing circuit, routine, or application divides the string into at least one corresponding set of at least one paragraph as the at least one component part.

33. The system of claim 18, further comprising:

a bit index determining circuit, routine, or application that inputs the search string and determines a bit index for the search string;

an intersecting circuit, routine, or application that inputs two or more bit indices and determines an intersection of the two or more bit indices; and

a comparing circuit, routine, or application that inputs at least one bit index and determines whether that at least one bit index at least partially matches the bit index for the search string.

34. A storage medium storing a set of program instructions executable on a data processing device and usable for indexing at least one string over a language having a vocabulary and a grammar for subsequent retrieval, the set of program instructions comprising:

instructions for receiving at least one input string containing a language having a vocabulary and a grammar;

instructions for dividing each string into a plurality of component parts according to the grammar, each component part including at least one word and at least one grammatical relationship of the at least one word within the language of the input string;

instructions for determining a bit index for each component part;

instructions for unioning, for each at least one set of component parts, the bit indices of the component parts within that set of component parts into a bit index for that set of component parts; and

instructions for recording the bit index for the set in a memory for subsequent use in document retrieval.