SYSTEMS AND METHODS FOR SEARCHING EACH LEVEL OF THE INNER STRUCTURE OF A STRING OVER A LANGUAGE HAVING A VOCABULARY AND A GRAMMAR

• US 20050138005A1
• Filed: 12/19/2003
• Published: 06/23/2005
• Est. Priority Date: 12/19/2003
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Roux, Claude, Jacquemin, Bernard
• Granted Patent: US 6,915,300 B1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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 grammatical structure of the string while allowing for a fast search. A single search provides immediate access to every level of a document, without having ato 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 method for searching for at least one indexed string that contains a search string, comprising:

determining a bit index of the 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 search string bit index with the intersection of the search string bit index and the indexed string bit index.

2. The method of claim 1, wherein determining a bit index of the search string comprises:

dividing the search string into at least one component part;

retrieving, for each component part, a bit index associated with that component part; and

unioning the retrieved bit indices of the at least one component part to form a bit index of the search string.

3. The method of claim 1, wherein:

comparing the search string bit index with the intersection of the search string bit index and the indexed string bit index comprises determining whether the search string bit index at least partially matches the intersection of the search string bit index and the indexed string bit index; and

if the search string bit index at least partially matches the intersection of the search string bit index and the indexed string bit index, the method further comprises;

retrieving a bit index of a sub-part of the indexed string;

determining an intersection of the search string bit index and the bit index of the retrieved sub-part; and

comparing the search string bit index with the intersection of the search string bit index and the sub-part bit index.

4. The method of claim 1, wherein:

comparing the search string bit index with the intersection of the search string bit index and the indexed string bit index comprises determining whether the search string bit index at least partially matches the intersection of the search string bit index and an indexed document bit index; and

if the search string bit index at least partially matches the intersection of the search string bit index and the indexed document bit index, the method further comprises;

retrieving a bit index of a paragraph of the matched document;

determining an intersection of the search string bit index and the retrieved bit index of the paragraph; and

comparing the search string bit index with the intersection of the search string bit index and the retrieved paragraph bit index.

5. The method of claim 4, wherein comparing the search string bit index with the intersection of the search string bit index and the retrieved paragraph bit index comprises determining whether the search string bit index at least partially matches the intersection of the search string bit index and retrieved paragraph bit index;

and

if the search string bit index at least partially matches the intersection of the search string bit index and the retrieved paragraph bit index, the method further comprises;

retrieving a bit index of a sentence of the matched paragraph;

determining an intersection of the search string bit index and the bit index of the retrieved sentence; and

comparing the search string bit index with the intersection of the search string bit index and the retrieved sentence bit index.

6. The method of claim 5, wherein comparing the search string bit index with the intersection of the search string bit index and the retrieved sentence bit index comprises determining whether the search string bit index at least partially matches the intersection of the search string bit index and retrieved sentence bit index;

and

if the search string bit index at least partially matches the intersection of the search string bit index and the retrieved sentence bit index, the method further comprises;

retrieving a bit index of a grouped unit of the matched sentence;

determining an intersection of the search string bit index and the bit index of the retrieved grouped unit; and

comparing the search string bit index with the intersection of the search string bit index and the retrieved grouped unit bit index.

7. The method of claim 3, wherein the search string bit index at least partially matches the intersection of the search string bit index and the indexed string bit index if the search string bit index equals the intersection of the search string bit index and the indexed string bit index.

8. The method of claim 3, wherein the search string bit index at least partially matches the intersection of the search string bit index and the indexed string bit index if at least part of the search string bit index equals the intersection of the search string bit index and the indexed string bit index.

9. An index searching system that searches for at least one indexed string that has been determined to at least partially match a search string, 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.

10. The system of claim 9, further comprising a marking circuit, routine, or application that marks the at least one indexed string that has been determined to at least partially match the at least one search string.

11. The system of claim 9, wherein the a bit index determining circuit, routine, or application inputs the search string, divides the search string into at least one element, retrieves the bit index of each at least one element, and combines the bit indices of each at least one element to form a bit index of the search string.

12. The system of claim 9, wherein:

the intersection determining circuit, routine, or application determines the intersection of the search string bit index and a bit index of an indexed document; and

the comparing circuit, routine, or application compares the search string bit index with the intersection of the search string bit index and the indexed document bit index.

13. The system of claim 12, wherein:

if the if the search string bit index at least partially matches the intersection of the search string bit index and the indexed document bit index, the intersection determining circuit, routine, or application inputs a bit index of a paragraph of the matched document; and

the comparing circuit, routine, or application compares the search string bit index with the intersection of the search string bit index and the indexed paragraph bit index.

14. The system of claim 13, wherein:

if the search string bit index at least partially matches the intersection of the search string bit index and the indexed paragraph bit index, the intersection determining circuit, routine, or application inputs a bit index of a sentence of the matched paragraph; and

the comparing circuit, routine, or application compares the search string bit index with the intersection of the search string bit index and the indexed sentence bit index.

15. The system of claim 14, wherein:

if the if the search string bit index at least partially matches the intersection of the search string bit index and the indexed sentence bit index, the intersection determining circuit, routine, or application inputs a bit index of a grouped unit of the matched sentence; and

the comparing circuit, routine, or application compares the search string bit index with the intersection of the search string bit index and the indexed grouped unit bit index

16. The system of claim 9, wherein the at least one indexed string comprises at least one document containing text.

17. The system of claim 9, wherein the at least one indexed string comprises at least one paragraph containing text.

18. The system of claim 9, wherein the at least one indexed string comprises at least one sentence containing text.

19. The system of claim 9, wherein the at least one indexed string comprises at least one grouped unit containing text.

20. The system of claim 9, wherein the comparing circuit, routine, or application determines that the at least one indexed string at least partially matches the at least one search string if the an intersection of the search string bit index and the indexed string bit index, as determined by the intersecting circuit, routine, or application, equals the search string bit index.

21. The system of claim 9, wherein the comparing circuit, routine, or application determines that the at least one indexed string at least partially matches the at least one search string if the an intersection of the search string bit index and the indexed string bit index, as determined by the intersecting circuit, routine, or application equals at least part of the search string bit index.

22. A storage medium storing a set of program instructions executable on a data processing device and usable for searching for at least one indexed string that contains a search string, the set of program instructions comprising:

instructions for determining a bit index of the search string;

instructions for retrieving a bit index of an indexed string;

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

instruction for comparing the intersection of the search string bit search string bit index.