Text search method and apparatus for structured documents

• US 5,745,745 A
• Filed: 06/27/1995
• Issued: 04/28/1998
• Est. Priority Date: 06/29/1994
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Asakawa, Satoshi, Kato, Kanji, Mizutani, Natsuko, Hatakeyama, Atsushi, Tada, Katsumi, Kawaguchi, Hisamitsu
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/495,232
• Time in Patent Office: 1,036 Days
• Field of Search: 395/605, 395/606, 395/601, 364/419.9, 364/900, 364/519, 389/54
• US Class Current: 1/1
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 2216/11 Patent retrieval
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A text search method for structured documents and apparatus wherein structured document database to be searched is created by adding logical structure length information to logical structure discriminating information on the basis of a structured document constituted by a plurality of logical structures and logical structure discriminator information, and in searching the structured document database in accordance with an entered search key constituted by a logical structure and a search character string, the search of a logical structure other than the entered logical structure is skipped based upon the data length information. In the method and apparatus, by using a structured document, structured document database to be searched is created which is constituted by a condensed text for each logical structure constituted by a list of words contained in the logical structure, a character occurrence bitmap for each logical structure constituted by a list of characters contained in the logical structure and an source structured document, and then the structured document database is searched in accordance with an entered search key constituted by a logical structure and a search character string. An source structured document is searched optionally depending upon the entered search key.

Claims

1. A text search method for searching structured documents, each structured document having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising the steps of:

preparing each of the structured documents to be searched, each structured document being identified by a document identifier, the preparing step for each structured document including;

a) storing the structured document in a database;

b) creating, and storing in the database, condensed texts and the corresponding unique discriminators for each of the respective logical structures, each of the condensed texts being formed by segmenting the structured document according to the predetermined markers and including all words within the respective logical structure without duplication; and

c) creating, and storing in the database, a character occurrence bitmap including all characters without duplication in the structured document;

inputting a search term and a discriminator identifying a logical structure;

searching the character occurrence bitmap for each of the structured documents and identifying a plurality of first document identifiers corresponding to the character occurrence bitmaps indicated as including each character contained in the inputted search term; and

searching the condensed texts corresponding to the input discriminator and identified by the first document identifiers and identifying a plurality of second document identifiers corresponding to the condensed texts which include each word contained in the inputted search term;

wherein if the search term includes a plurality of words and indicates a positional relationship between the words, the method further comprises the step of;

searching the structured documents identified by the second document identifiers and identifying a plurality of third document identifiers corresponding to the structured documents containing all the words having the positional relationship defined in the inputted search term.

6. A method according to claim 1, wherein the structured document stored in step a) is segmented according to the predetermined markers, each segment corresponds to one of the logical structures, the segmented document includes all text within the structured document, and the step of searching the structured documents includes:

searching each segment of the structured documents corresponding to the input discriminator and the second document identifiers and identifying a plurality of third document identifiers corresponding to the structured documents which include the document identifiers in the search term.

2. A text search method for searching structured documents, each structured document having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising the steps of:

preparing each of the structured documents to be searched, each structured document being identified by a document identifier, the preparing step for each structured document including;

a) storing the structured document in a database; and

b) creating, and storing in the database, condensed texts and the corresponding unique discriminators for each of the respective logical structures, each of the condensed texts being formed by segmenting the structured document according to the predetermined markers and including all words within the respective logical structure without duplication;

inputting a search term and a discriminator; and

searching the condensed texts corresponding to the input discriminator and identifying a plurality of first document identifiers corresponding to the condensed texts which include each word contained in the inputted search term;

wherein if the search term includes a plurality of words and indicates a positional relationship between the words, the method further comprises the step of;

searching the structured documents identified by the first document identifiers and identifying a plurality of second document identifiers corresponding to the structured documents containing all the words having the positional relationship defined in the inputted search term.

3. A text search method for searching structured documents, each structured document having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising the steps of:

preparing each of the structured documents to be searched, each structured document being identified by a document identifier, the preparing step for each of the structured documents including;

a) storing the structured document in a database;

b) creating, and storing in the database, condensed texts and the corresponding unique discriminators for each of the respective logical structures, each of the condensed texts being formed by segmenting the structured document according to the predetermined markers and including all words within the respective logical structure without duplication; and

c) creating, and storing in the database, character occurrence bitmaps and the corresponding unique discriminators for each of the respective logical structures, each of the character occurrence bitmaps being formed by segmenting the structured document according to the predetermined markers and including all characters within the respective logical structure without duplication;

inputting a search term and a discriminator;

searching the character occurrence bitmaps corresponding to the input discriminator and identifying a plurality of first document identifiers corresponding to the character occurrence bitmaps indicated as including each character contained in the search term; and

searching the condensed texts corresponding to the input discriminator and the documents identified by the first document identifiers and further identifying a plurality of second document identifiers identifying the condensed texts which include each word contained in the inputted search term;

wherein if the search term includes a plurality of words and indicates a positional relationship between the words, the method further comprises the step of;

searching the structured documents identified by the second document identifiers and identifying a plurality of third document identifiers corresponding to the structured documents containing all the words having the positional relationship defined in the inputted search term.

4. A text search method for searching structured documents, each structured document having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising the steps of:

preparing each of the structured documents to be searched, each structured document being identified by a document identifier, the preparing step for each structured document including;

a) storing the structured document in a database;

b) creating, and storing in the database, a condensed text for the structured document, the condensed text including all words within the structured document without duplication; and

c) creating, and storing in the database, character occurrence bitmaps and the corresponding unique discriminators for each of the respective logical structures, each of the character occurrence bitmaps being formed by segmenting the structured document according to the predetermined markers and including all characters within the respective logical structure without duplication;

inputting a search term and a discriminator;

searching the character occurrence bitmaps corresponding to the input discriminator and identifying a plurality of first document identifiers corresponding to the character occurrence bitmaps indicated as including each character contained in the inputted search term; and

searching the condensed text for each of the structured documents identified by the first document identifiers and identifying a plurality of second document identifiers corresponding to the condensed texts indicated as including each word contained in the inputted search term;

wherein if the search term includes a plurality of words and indicates a positional relationship between the words, the method further comprises the step of;

searching the structured documents identified by the second document identifiers and identifying a plurality of third documents containing all the words having the positional relationship defined in the inputted search term.

5. A text search method for searching structured documents, each structured document having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising the steps of:

preparing each of the structured documents to be searched, each structured document being identified by a document identifier, the preparing step for each structured document including;

a) storing the structured document in a database; and

b) creating, and storing in the database, character occurrence bitmaps and the corresponding unique discriminators for each of the respective logical structures, each of the character occurrence bitmaps being formed by segmenting the structured document according to the predetermined markers and including all characters within the respective logical structure without duplication;

inputting a search term and a discriminator; and

searching the character occurrence bitmaps corresponding to the input discriminator and identifying a plurality of first document identifiers corresponding to the character occurrence bitmaps indicated as including each character contained in the inputted search term;

wherein if the search term includes a plurality of words and indicates a positional relationship between the words, the method further comprises the step of;

searching the structured documents identified by the first document identifiers and identifying a plurality of second document identifiers containing all the words having the positional relationship defined in the inputted search term.

7. A text search method for searching structured documents, each structured document having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising the steps of:

preparing each of the structured documents to be searched, each structured document being identified by a document identifier, the preparing step for each structured document including;

a) creating a segmented structured document according to the predetermined markers, each segment corresponding to one of the logical structures, the segmented document being stored in a database and including all text within the structured document;

b) creating, and storing in the database, condensed texts for each of the respective logical structures, each of the condensed texts being formed by segmenting the structured document according to the predetermined markers and including all words within the respective logical structure without duplication; and

c) creating, and storing in the database, a character occurrence bitmap including all characters from the structured document without duplication;

inputting a search term and a discriminator;

searching the character occurrence bitmap for each of the structured documents and identifying a plurality of first document identifiers corresponding to the character occurrence bitmaps indicated as including each character contained in the search term; and

searching the condensed texts corresponding to the input discriminator and the first document identifiers and further identifying a plurality of second document identifiers corresponding to the condensed texts which include each word contained in the search term;

wherein if the search term includes a plurality of words and indicates a positional relationship between the words, the method further comprises the step of;

searching each segment of the structured documents corresponding to the input discriminator and the second document identifiers and identifying a plurality of third document identifiers corresponding to the structured documents containing all the words having the positional relationship defined in the inputted search term.

8. A text search method for searching structured documents, each structured document having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising the steps of:

preparing each of the structured documents to be searched, each structured document being identified by a document identifier, the preparing step for each structured document including;

a) creating a segmented structured document according to the predetermined markers, each segment corresponding to one of the logical structures, the segmented document being stored in a database and including all text within the structured document; and

b) creating, and storing in the database, a character occurrence bitmap including all characters from the structured document without duplication;

inputting a search term and a discriminator; and

searching the character occurrence bitmap for each of the structured documents and identifying a plurality of first document identifiers corresponding to the character occurrence bitmaps indicated as including each character contained in the search term;

wherein if the search term includes a plurality of words and indicates a positional relationship between the words, the method further comprises the step of;

searching each segment of the structured documents corresponding to the input discriminator and the first document identifiers and identifying a plurality of second document identifiers corresponding to the structured documents containing all the words having the positional relationship defined in the inputted search term.

9. A text search method for searching structured documents, each structured document having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising the steps of:

preparing each of the structured documents to be searched, each structured document being identified by a document identifier, the preparing step for each structured document including;

a) creating a segmented structured document using the predetermined markers, each segment corresponding to one of the logical structures, the segmented document being stored in a database and including all text within the structured document; and

b) creating, and storing in the database, condensed texts for each of the respective logical structures, each of the condensed texts being formed by segmenting the structured document according to the predetermined markers and including all words within the respective logical structure without duplication;

inputting a search term and a discriminator; and

searching the condensed texts corresponding to the input discriminator and identifying a plurality of first document identifiers corresponding to the condensed texts which include each word contained in the inputted search term;

wherein if the search term includes a plurality of words and indicates a positional relationship between the words, the method further comprises the step of;

searching each segment of the structured documents corresponding to the input discriminator and the first document identifiers and identifying a plurality of second document identifiers corresponding to the structured documents containing all the words having the positional relationship defined in the inputted search term.

10. A structured document search apparatus for searching structured documents having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising:

means for storing each of the structured documents in a database;

means for creating, and storing in the database, condensed texts and the corresponding unique discriminators for each of a plurality of segments, identified by the predetermined markers, in each structured document, each condensed text including all words, without duplication, within one segment;

means for creating, and storing in the database, a plurality of character occurrence bitmaps, each character occurrence bitmap containing all characters, without duplication, contained in one of the structured documents;

means for searching the character occurrence bitmaps and identifying a plurality of first document identifiers identifying respective structured documents including all characters contained in a search term of an inputted search equation;

means for searching the condensed texts, identified by the first plurality of document identifiers and a discriminator included in the search equation, and identifying a plurality of second document identifiers corresponding to the condensed texts which include each word contained in the search term; and

means for, if the search equation designates a positional relationship between a plurality of search terms, searching the structured documents identified by the plurality of second document identifiers and identifying a plurality of third document identifiers corresponding to the structured documents which include all words in the inputted search term having the designated positional relationship.

15. A structured document search apparatus according to claim 10, wherein:

the means for storing the structured documents segments each structured document according to the predetermined markers, each segment corresponding to one of the logical structures, the segmented document including all text within the structured document; and

the means for searching the structured documents searches the segments of the documents identified by the plurality of second document identifiers and the discriminator included in the search equation, and identifies a plurality of third document identifiers corresponding to the structured documents which include all words in the inputted search term having the designated positional relationship.

11. A structured document search apparatus for searching structured documents having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising:

means for storing each of the structured documents in a database;

means for creating, and storing in the database, condensed texts and the corresponding unique discriminators for each of a plurality of segments, identified by the predetermined markers, in each structured document, each condensed text including all words, without duplication, within one segment;

means for searching the condensed texts, identified by a discriminator included in an inputted search equation, and identifying a plurality of first document identifiers corresponding to the condensed texts which include each word contained in a search term of the search equation; and

means for, if the search equation designates a positional relationship between a plurality of search terms, searching the structured documents identified by the plurality of first document identifiers and identifying a plurality of second document identifiers corresponding to the structured documents which include all words in the inputted search term having the designated positional relationship.

12. A structured document search apparatus for searching structured documents having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising:

means for storing each of the structured documents in a database;

means for creating, and storing in the database, condensed texts and the corresponding unique discriminators for each of a plurality of segments, identified by the predetermined markers, in each structured document, each condensed text including all words, without duplication, within one segment;

means for creating, and storing in the database, a plurality of character occurrence bitmaps and the corresponding unique discriminators for each of a plurality of segments, identified by the predetermined markers, in each structured document, each character occurrence bitmap containing all characters, without duplication, within one segment;

means for searching the character occurrence bitmaps, identified by a discriminator in an inputted search equation, and identifying a plurality of first document identifiers corresponding to the character occurrence bitmaps which include each character contained in a search term of the inputted search equation;

means for searching the condensed texts, identified by the first document identifiers and the discriminator included in the search equation, and identifying a plurality of second document identifiers corresponding to the condensed texts which include each word contained in the search term of the search equation; and

means for, if the search equation designates a positional relationship between a plurality of search terms, searching the structured documents identified by the plurality of second document identifiers and identifying a plurality of third document identifiers corresponding to the structured documents which include all words in the inputted search term having the designated positional relationship.

13. A structured document search apparatus for searching structured documents having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising:

means for storing each of the structured documents in a database;

means for creating, and storing in the database, a condensed text for each of the structured documents, each condensed text including all words, without duplication, within one structured document;

means for creating, and storing in the database, a plurality of character occurrence bitmaps and the corresponding unique discriminators for each of a plurality of segments, identified by the predetermined markers, in each structured document, each character occurrence bitmap containing all characters, without duplication, within one segment;

means for searching the character occurrence bitmaps, identified by a discriminator in an inputted search equation, and identifying a plurality of first document identifiers corresponding to the character occurrence bitmaps which include each character contained in a search term of the inputted search equation;

means for searching the condensed texts, identified by the first document identifiers, and identifying a plurality of second document identifiers corresponding to the condensed texts which include each word contained in the search term of the search equation; and

means for, if the search equation designates a positional relationship between a plurality of search terms, searching the structured documents identified by the plurality of second document identifiers and identifying a plurality of third document identifiers corresponding to the structured documents which include all words in the inputted search term having the designated positional relationship.

14. A structured document search apparatus for searching structured documents having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising:

means for storing each of the structured documents in a database;

means for creating, and storing in the database, a plurality of character occurrence bitmaps and the corresponding unique discriminators for each of a plurality of segments, identified by the predetermined markers, in each structured document, each character occurrence bitmap containing all characters, without duplication, within one segment;

means for searching the character occurrence bitmaps, identified by a discriminator in an inputted search equation, and identifying a plurality of first document identifiers corresponding to the character occurrence bitmaps which include each character contained in a search term of the inputted search equation; and

means for, if the search equation designates a positional relationship between a plurality of search terms, searching the structured documents identified by the plurality of first document identifiers and identifying a plurality of second document identifiers corresponding to the structured documents which include all words in the inputted search term having the designated positional relationship.

16. A structured document search system for searching structured documents having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising:

means for creating, and storing in a database, a segmented structured document, each segment identified by the predetermined markers and corresponding to one of the logical structures, the segmented document including all text within the structured document;

means for creating, and storing in the database, condensed texts and the corresponding unique discriminators for each of the plurality of segments, identified by the predetermined markers, in each structured document, each condensed text including all words, without duplication, within one segment;

means for creating, and storing in the database, a plurality of character occurrence bitmaps, each character occurrence bitmap containing all characters, without duplication, contained in one of the structured documents;

means for searching the character occurrence bitmaps and identifying a plurality of first document identifiers identifying respective structured documents including all characters contained in a search term of an inputted search equation;

means for searching the condensed texts, identified by the first document identifiers and a discriminator included in the search equation, and identifying a plurality of second document identifiers corresponding to the condensed texts which include each word contained in the search term of the search equation; and

means for, if the search equation designates a positional relationship between a plurality of search terms, searching the segments of the structured documents identified by the plurality of second document identifiers and the discriminator included in the search equation, and identifying a plurality of third document identifiers corresponding to the structured documents which include all words in the inputted search term having the designated positional relationship.

17. A structured document search apparatus for searching structured documents having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising:

means for creating, and storing in a database, a segmented structured document, each segment being identified by the predetermined markers and corresponding to one of the logical structures, the segmented document including all text within the structured document;

means for creating, and storing in the database, a plurality of character occurrence bitmaps, each character occurrence bitmap containing all characters, without duplication, contained in one of the structured documents;

means for searching the character occurrence bitmaps and identifying a plurality of first document identifiers identifying respective structured documents including all characters contained in a search term of an inputted search equation; and

means for, if the search equation designates a positional relationship between a plurality of search terms, searching the segments of the structured documents identified by the plurality of first document identifiers and the discriminator included in the search equation, and identifying a plurality of second document identifiers corresponding to the structured documents which include all words in the inputted search term having the designated positional relationship.

18. A structured document search system for searching structured documents having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising:

means for creating, and storing in a database, a segmented structured document, each segment being identified by the predetermined markers and corresponding to one of the logical structures, the segmented document including all text within the structured document;

means for creating, and storing in the database, condensed texts and the corresponding unique discriminators for each of the plurality of segments, identified by the predetermined markers, in each structured document, each condensed text including all words, without duplication, within one segment;

means for searching the condensed texts, identified by a discriminator included in an inputted search equation, and identifying a plurality of first document identifiers corresponding to the condensed texts which include each word contained in a search term of the search equation; and

means for, if the search equation designates a positional relationship between a plurality of search terms, searching the segments of the structured documents identified by the plurality of first document identifiers and the discriminator included in the search equation, and identifying a plurality of second document identifiers corresponding to the structured documents which include all words in the inputted search term having the designated positional relationship.

19. A text search method for searching structured documents, each structured document having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising the steps of:

a) preparing a search database, including;

a1) scanning each of the structured documents, including;

a2) detecting a first predetermined marker indicating a start of one of the logical structures within a structured document;

a3) detecting a second predetermined marker, indicating an end of the logical structure, and calculating a length of the logical structure from the first and second predetermined markers;

a4) repeating steps a2) to a4) until an end of the structured document is detected;

a5) storing, in the search database, a control code indicating a start of the structured document and an identifier for identifying the structured document;

a6) storing, in the search database, the first detected predetermined marker, the unique discriminator, the calculated logical structure length and corresponding logical structure text, for each logical structure in the structured document;

a7) storing, in the search database, a control code indicating an end of the structured document; and

a8) repeating steps a1) to a8) for each of the structured documents;

b) inputting a discriminator, identifying a logical structure, and a search term; and

c) searching the search database and comparing the input discriminator to each of the discriminators stored in the search database, including;

c1) if the stored discriminator includes the input discriminator, performing character matching between the search term and the logical structure text corresponding to the stored discriminator;

c2) if the stored discriminator does not include the input discriminator, skipping an amount of logical structure text equal to the logical structure length; and

c3) repeating steps c1) to c3) for each of the stored discriminators in the search database.

20. A method according to claim 19, wherein the first predetermined marker is a specific control code and the unique discriminators for the logical structures include identification numbers.

21. A method according to claim 20, wherein the identification numbers are hierarchically defined.

22. A text search method for searching structured documents, each structured document having a plurality of logical structures, each logical structure being enclosed by predetermined markers and having a unique discriminator for identifying the logical structure, comprising the steps of:

a) creating a search database by creating a logical structure information file and a text file, the text file storing text for each logical structure in the structured documents, the logical structure information file storing logical structure discriminator information and area information indicating where the text of each logical structure of each structured document is stored in the text file, including;

a1) detecting a first predetermined marker indicating a start of one of the logical structures within a structured document;

a2) detecting a second predetermined marker indicating an end of the logical structure;

a3) storing the text of the logical structure in the text file;

a4) storing, in the logical structure information file, the logical structure discriminator information and the area information indicating where the text for the respective discriminator is stored in the text file;

a5) repeating steps a1) to a4) for each of the logical structures in the structured document; and

a6) repeating steps a1) to a5) for each structured document; and

b) searching the search database, including;

b1) referring to the logical structure information file and reading the area information indicating where the text of a structured document for a logical structure designated in a search equation is stored in the text file;

b2) reading the text of the structured document corresponding to the logical structure designated in the search equation, from the text file, in accordance with the area information;

b3) performing a character string matching process for the read text of the structured document by using a search term designated in the search equation; and

b4) repeating steps b1) to b4) for each structured document.