Hierarchical presearch type text search method and apparatus and magnetic disk unit used in the apparatus

• US 5,168,533 A
• Filed: 08/09/1990
• Issued: 12/01/1992
• Est. Priority Date: 06/14/1989
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Hitachi, Ltd.
• Inventors: Kaneoka, Noriyuki, Fujisawa, Hiromichi, Kato, Kanji, Kawaguchi, Hisamitsu, Ooyama, Mitsuo, Akizawa, Mitsuru, Murakami, Masaharu, Hatakeyama, Atsushi, Masuzaki, Hidefumi, Fujinawa, Masaaki
• Primary Examiner(s): Brinich, Stephen
• Application Number:
  US07/555,483
• Time in Patent Office: 845 Days
• Field of Search: 364/200, 382/54, 382/10-14, 382/16
• US Class Current: 382/229
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 10/70 using pattern recognition or machine learning optical pattern recognition or electronic computations therefor G06V10/88
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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 method and apparatus for making document information search and a magnetic disk unit to be used for realizing the method and apparatus. In the document information search method, in performing document search with respect to a desired subject key word, two stages of presearch are carried out. In a first stage of presearch (step 402), a character component table (500) in which existence of character codes for every document is stated with respect to all the character codes contained in the group of document text data of stored documents is generated, and the character component table is searched for all the character codes constituting a desiredly designated search subject key word to thereby extract all the documents each containing all the character codes constituting the search subject key word. In a second stage of presearch step 403), contracted text data for every document in which adjuncts and duplication of repeatedly stated words contained in advance in the text data are eliminated is generated, and the documents each containing the search subject key words by word are extracted from the documents extracted by the first presearch. After the second stage of presearch, text search is performed in accordance with a neighbor condition, a contextual condition, or the like (step 404). Further, as a term comparator means, hardware (1106) for exclusive use for term comparison in accordance with a finite automation is employed. Further, as for different notation and synonym, inputted terms are once subject to different notation development in a different notation development processing portion (2601), each of the different-notation developed terms is subject to synonym development in a synonym development processing portion (2602) while referring to a synonym dictionary, and then the results of synonym development are further subject to different notation development in a different notation development processing portion (2603) in accordance with a conversion rule table (2603).

Claims

1. A document information search method for searching for specified text data containing a given search subject key word from a group of document text data stored in advance, said method comprising the steps of:

generating a character component table in which existence of character codes for every document is stated with respect to all the character codes contained in said group of document text data;

searching said character component table for all the character codes constituting a desiredly designated search subject key word; and

performing a first presearch for extracting all documents each containing all the character codes constituting said search subject key word.

2. A document information search method according to claim 1, further comprising the steps of:

generating contracted text data for every document in which adjuncts and duplication of repeatedly stated words contained in advance in the text data are eliminated; and

performing a second search for extracting documents each containing said search subject key words by word from the documents extracted by said first presearch.

3. A document information search method according to claim 2, further comprising the step of performing a search on the documents extracted by said second presearch to thereby extract documents each satisfying search conditions of the search subject key word from said documents extracted by said second presearch.

4. A document information search method according to claim 2, wherein said second presearch is performed on the whole of said contracted text data in the case where the number of said documents extracted by said first presearch shows that the time taken for selectively reading out the documents in the above number from said contracted text data is longer than the time taken for reading out the whole of said contracted text data.

5. A document information search method according to claim 1, wherein in said step of performing said first presearch, document search on the basis of said desiredly designated search subject key word is interrupted when there is no document containing all the character codes constituting said desiredly designated search subject key word in said character component table.

6. A document information search method according to claim 2, wherein in said step of performing said second presearch, document search on the basis of said desiredly designated search subject key word is interrupted when there is no document in which said desiredly designated search subject key word is contained by word.

7. A document information search method according to claim 3, wherein the search results by said second presearch are regarded as the results of search with said predetermined search subject key word.

8. A document information search method according to claim 3, wherein said predetermined search conditions given to said search subject key word contain at least one of neighbor and contextual conditions.

9. A document information search method according to claim 1, further comprising the step of performing a search on the documents extracted by said first presearch to thereby extract documents each satisfying search conditions of the search subject key word from said documents extracted by said second presearch.

10. A document information search method according to claim 9, wherein said predetermined search conditions given to said search subject key word contain at least one of neighbor and contextual conditions.

19. A document information search apparatus according to claim 10, wherein said term comparator means is used also as said second presearch means.

20. A document information search apparatus according to claim 10, further comprising semiconductor memory means for storing said contracted text data in which adjuncts and duplication of repeatedly stated words are eliminated in the text data.

11. A document information search apparatus comprising:

text data storage means for storing a document text data group;

search expression input means for inputting a search conditional expression in which a complex condition including key words for searching said document text data, and positional and logical relationships among said key words is designated;

search expression analysis means for analyzing the inputted search conditional expression to extract a search subject key word and a complex condition descriptive portion;

synonym development means for generating synonyms of said search subject key word on the basis of said search subject key word outputted from said search expression analysis means;

different notation development means for generating different notation words of said subject key word including said synonyms;

complex condition analysis means for analyzing said complex condition descriptive portion outputted from said search expression analysis means to thereby develop said complex condition descriptive portion into said positional and logical conditions;

term comparator means for reading said text data from said text data storage means so as to collectively compare said text data with respect to the key word group given from said different notation development means;

complex condition judgment means for detecting documents adapted to the conditions designated by said complex condition analysis means on the basis of the results of the comparison outputted from said term comparator means to thereby output identifiers of the detected documents; and

,

search result output means for outputting identifier information of the documents adapted to said search conditional expression on the basis of the output results of said complex condition judgement means.

12. A document information search apparatus according to claim 11, wherein said text data storage means comprise a plurality of storage devices, said storage devices being operated in parallel with each other so that the respective outputs of said storage devices are integrally supplied to said term comparator means.

13. A document information search apparatus according to claim 12, wherein said storage devices constituting said text data storage means comprise magnetic disk units.

14. A document information search apparatus according to claim 12, wherein said storage devices constituting said text data storage means comprise optical disk units.

15. A document information search apparatus according to claim 11, further comprising a first presearch means for preparing in advance table data in which existence of all character codes are stated for every document and for extracting documents in which all the characters constituting the key words in the designated search condition expression are contained, so that the text data with respect to the document collection reduced by said first presearch means are read out from said text data storage means and search is executed on said text data by said term comparator means and said complex condition judgment means.

16. A document information search apparatus according to claim 15, further comprising semiconductor memory means for storing said table data in which existence of all the character codes is stated for every document.

17. A document information search apparatus according to claim 15, wherein said text data storage means includes means for storing the table data together with said text data.

18. A document information search apparatus according to claim 11, further comprising second presearch means for preparing in advance contracted text data for every document in which adjuncts and duplication of repeatedly stated words are eliminated in the text data and for extracting documents in which key words in the designated search conditional expression are contained by word unit, so that the text data with respect to the document collection reduced by said second paragraph means are read out from said text data storage means and search is executed on said text data by said term comparator means and said complex condition judgment means.

21. A document information search apparatus according to claim 18, wherein said text data storage means includes means for storing said contracted text data in which adjuncts and duplication of repeatedly stated words are eliminated in the text data together with said text data.

22. A document information search apparatus according to claim 11, further comprising first presearch means for preparing in advance table data in which existence of all character codes are stated for every document and for extracting documents in which all the characters constituting the key words in the designated search conditional expression are contained, and a second presearch means for preparing in advance contracted text data for every document in which adjuncts and duplication of repeatedly stated words are eliminated in the text data and for extracting documents in which key words in the designated search conditional expression are contained by word unit, so that the search subject document collection is reduced in number by use of said first presearch means, said second presearch means is made to act on the result of reduction, and finally the text data with respect to the document collection as a result of reduction are read out from said text data storage means and search is executed on said text data by said term comparator means and said complex condition judgment means.

23. A document information search apparatus according to claim 22, further comprising semiconductor memory means for storing said table data in which existence of all the character codes is stated for every document and said contracted text data in which adjuncts and duplication of repeatedly stated words are eliminated in the text data.

24. A document information search apparatus according to claim 22, wherein said table data in which existence of all the character codes is stated for every document are stored on a semiconductor memory, and said contracted text data in which adjuncts and duplication of repeatedly stated words are eliminated in the text data are stored on said text data storage means together with said text data.

25. A document information search apparatus according to claim 11, wherein said search result output means includes means for outputting the bibliographic information and text data of the documents on the basis of the identifier information of documents adapted to said search conditional expression.

26. A document information search apparatus according to claim 11, further comprising an image data storage means for storing image information related to stored document information, so that on the basis of the identifiers of documents adapted to search conditions and outputted from said search result output means, image information related to said documents is read out from said image data storage means and outputted together with the bibliographic information and text data of the documents.

27. A document information search apparatus according to claim 11, further comprising a communication means for connection with a communication network, so that a search conditional expression received through said communication means is supplied to said search expression input means and the search result outputted from said search result output means is sent back by use of said communication means to a search conversation terminal from which a search request corresponding to the search result is transmitted.

28. A document information search apparatus according to claim 26, further comprising a communication means for connection with a communication network, so that a search conditional expression received through said communication means is supplied to said search expression input means and the search result outputted from said search result output means is sent back by use of said communication means to a search conversation terminal from which a search request corresponding to the search result is transmitted.

29. A document information search apparatus according to claim 11, wherein said different notation development means includes a conversion rule table in which head terms constituted by terms of one character or more and at least one other term corresponding to every head term are stored therein, so that all portions of inputted terms coincident with said head terms in said conversion rule table are converted into term lists each including one head term and the other term corresponding to the head term, and then terms inputted in combination with the term lists are developed into a group of other terms.

30. A document information search apparatus according to claim 29, further comprising means for using as the conversion rule, a conversion rule table based on at least one notation system selected from the new and old styles or declensional kana of kanji, the katakana notation of adopted words, and the Hepburnian system or directive system notation of romaji to perform the development.

31. A document information search apparatus according to claim 29, further comprising means for developing, when alphabet terms are inputted, each alphabet term into at least one of three kinds of terms including a term in which all the characters are majuscules, a term in which only the head character is a majuscule and the remainder characters are minuscules, and a term in which all the characters are minuscules.

32. A document information search apparatus according to claim 29, further comprising means for re-defining by a user a conversion rule table in which instructions of replacement of partial terms of inputted terms into other terms are stated.

33. A document information search apparatus according to claim 11, wherein said different notation development means includes:

a first different notation development means for developing inputted terms into other terms different in notation system such as syllable notation or the like by use of a partial term conversion rule;

a second synonym development means for developing each of the different notation developed terms into other terms having synonym relationship therewith while making references to a synonym dictionary, and a third different notation development means for developing the terms obtained by the synonym development into other terms by use of the conversion rule in the same manner as said first different notation development means.

34. A document information search apparatus according to claim 33, wherein each of said first and third different notation development means comprise means for carrying out development with respect to at least one notation system selected from the new and old styles or declensional kana or kanji, the katakana notation of adopted words, the Hepburnian system or directive system notation of romaji, and the majuscule/minuscule notation system of alphabet characters, and wherein in said second synonym development means, each term is developed into synonym terms including at least one word group of same-rank words, higher-rank words, lower-rank words or related words.

35. A document information search apparatus according to claim 34, wherein selection as to on which one or ones of said notation system selected from the new and old styles of declensional kana of kanji, the katakana notation of adopted words, the Hepburnian system or directive system notation of romaji, and the majuscule/minuscule notation system of alphabet characters the development is to be carried out by said different notation development means and selection as to on which one or ones of respective word groups of same-rank words, higher-rank words, lower-rank words, and related words is to be carried out by said synonym development means are performed by modes settable by a user.

36. A document information search apparatus according to claim 33, wherein said dictionary to be used for synonym development includes a dictionary in which head terms are described together with same-rank words, higher-rank words, lower-rank words, and related words corresponding to said head terms.

37. A document information search apparatus according to claim 11, wherein said term comparator means comprises means using a finite-state automaton for collectively judging whether a plurality of search subject terms exist or not in terms composed of coded characters over which search is to be executed so that transit from a plurality of states is made to be transit into the same state to thereby reduce the number of states.

38. A document information search apparatus according to claim 11, wherein said term comparator means comprises means using a finite-state automaton for collectively judging whether a plurality of search subject terms exist or not in terms composed of coded characters over which search is to be executed in accordance with an automaton state transit control method in which when comparison is made between said search subject terms and said terms over which search is to be executed, a token for revealing the state in which comparison is to be made is provided to watch whether or not the comparison always shows accord at the starting state, and if the comparison shows accord at the starting state a new token is generated and the new token is moved to a transit state in accordance with said automaton, so that in the state where the token other than at the starting state is disposed, the token is moved to a transit state in accordance with said automaton when the comparison shows accord while the token is made disappeared when the comparison shows discord.

39. A document information retrieval system according to claim 11, in which said term comparator means comprises means for generating different notations in a complex expression format A from a search subject term by using a finite state automaton provided for retrieving a group of different notation terms and generates an automaton with the same transition state as a start point in order from the head character in a group of partial terms given in innermost parentheses, to describe transitions in the automaton like a net in which:

when the same character is given from the group or partial terms, the same transit state is generated;

when a different character is given from the group of partial terms, a new transit state is generated; and

all transit states are collected into one state at the last character in said group of partial terms.

40. A document information search apparatus according to claim 26, wherein said image data storage device comprises an optical disk unit.

42. A document information search apparatus according to claim 11, further comprising at least one image data storage device means for storing thereon image information related to document information stored in said document information search apparatuses, so that upon reception of identifiers of documents adapted to the search conditions as the results of search, the search terminals supply the received identifiers as instructions to said image data storage device so as to receive the image information related to the documents from said image data storage device to thereby display said image information.

43. A document information search apparatus according to claim 42, wherein an optical disk unit is used as said image data storage device.

41. A document information search system for searching document information or the like comprising:

a plurality of document information search apparatuses connected to a communication network and operated in parallel to each other in accordance with search conditions broadcast from a plurality of search terminals connected to said communication network, each of said plurality of document information search apparatuses including;

text data storage means for storing a document text data group;

search expression input means for inputting a search conditional expression in which a complex condition including key words for searching said document text data, and positional and logical relationships among said key words is designated;

search expression analysis means for analyzing the inputted search conditional expression to extract a search subject key word and a complex condition descriptive portion;

synonym development means for generating synonyms of said search subject key word on the basis of said search subject key word outputted from said search expression analysis means;

different notation development means for generating different notation words of said subject key word including said synonyms;

complex condition analysis means for analyzing said complex condition descriptive portion outputted from said search expression analysis means to thereby develop said complex condition descriptive portion into said positional and logical conditions;

term comparator means for reading said text data from said text data storage means so as to collectively compare said text data with respect to the key word group given from said different notation development means;

complex condition judgment means for detecting documents adapted to the conditions designated by said complex condition analysis means on the basis of the results of the comparison outputted from said term comparator means to thereby output identifiers of the detected documents; and

,

search result output means for outputting identifier information of the documents adapted to said search conditional expression on the basis of the output results of said complex condition judgment means;

communication means for connection with the communication network, so that a search conditional expression received through said communication means is supplied to said search expression input means and the search result outputted from said search result output means is sent back by use of said communication means to a search conversation terminal from which a search request corresponding to the search result is transmitted; and

,

means for receiving the search results transmitted from said document information search apparatuses and displaying the received results on said search terminals.

44. A document information search system for searching document information or the like comprising:

a plurality of document information search apparatuses connected to a communication network and operated in parallel to each other in accordance with search conditions broadcast from a plurality of search terminals connected to said communication network, each of said plurality of document information search apparatuses including;

text data storage means for storing a document text data group;

search expression input means for inputting a search conditional expression in which a complex condition including key words for searching said document text data, and positional and logical relationships among said key words is designated;

search expression analysis means for analyzing the inputted search conditional expression to extract a search subject key word and a complex condition descriptive portion;

synonym development means for generating synonyms of said search subject key word on the basis of said search subject key word outputted from said search expression analysis means;

different notation development means for generating different notation words of said subject key word including said synonyms;

complex condition analysis means for analyzing said complex condition descriptive portion outputted from said search expression analysis means to thereby develop said complex condition descriptive portion into said positional and logical conditions;

term comparator means for reading said text data from said text data storage means so as to collectively compare said text data with respect to the key word group given from said different notation development means;

complex condition judgment means for detecting documents adapted to the conditions designated by said complex condition analysis means on the basis of the results of the comparison outputted from said term comparator means to thereby output identifiers of the detected documents; and

,

search result output means for outputting identifier information of the documents adapted to said search conditional expression on the basis of the output results of said complex condition judgment means;

image data storage means for storing image information related to stored document information, so that on the basis of the identifiers of documents adapted to search conditions and outputted from said search result output means, image information related to said documents is read out from said image data storage means and outputted together with the bibliographic information and text data of the documents;

communication means for connection with the communication network, so that a search conditional expression received through said communication means is supplied to said search expression input means and the search result outputted from said search result output means is sent back by use of said communication means to a search conversation terminal from which a search request corresponding to the search result is transmitted; and

,

means for receiving the search results transmitted from said document information search apparatuses and displaying the received results on said search terminals.

45. A document information search apparatus comprising means for storing text data by data unit such as literature unit, means for inputting search terms, and means for searching for said search terms in said stored text data, wherein said apparatus further comprises a different notation development means for developing each of the inputted terms into terms having variations in notation system such as syllable notation system, a synonym development means having a synonym dictionary for developing the inputted terms into synonym terms while making references to said synonym dictionary, and an integral means for integrating the terms obtained by said two term development means, whereby search terms inputted by a user are once developed into a term group A in which terms are different in notation from each other by said different notation develop means, each of the terms in said term group A is developed into a synonym term group B by said synonym development means, each of terms in said synonym term group B is developed into a term group C in which terms are different in notation from each other by said different notation develop means, said term group A and said term group C are integrated by said integral means to thereby obtain a term group D, and search is made on a data unit of said text data in which any one of term in said term group D is contained.

46. In a magnetic disk system comprising:

a collective type magnetic disk device including a plurality of data storage units respectively having magnetic disk units, input/output buffers for temporarily storing data to be inputted/outputted into/from data storage units respectively, and a multi-disk controller for controlling said data storage units and said input/output buffers; and

a higher-rank apparatus for issuing a control instruction for said multi-disk controller;

said collective type magnetic disk device being constituted by n data storage units in which on the assumption that a data transfer rate required from said higher-rank apparatus is represented by T, one-cylinder capacity of said magnetic disk units is represented by M, a data transfer rate from said data storage units to said the input/output buffers is represented by t, the minimum seek time of said magnetic disk units is represented by s, a revolution velocity of said magnetic disk units is represented by R, and the capacity of the input/output buffer is not smaller than the one-cylinder capacity M of said magnetic disk units, then the number n of said data storage units satisfies the following expression of ##EQU31## when said minimum seek time s of said magnetic disk units is longer than the time (M/T) required for transferring the data M from said input/output buffer to said higher-rank apparatus,

while the number n of said data storage satisfies the following expression of ##EQU32## when said minimum seek time s of said magnetic disk units is not longer than the time (M/T) required for transferring the data of M from said input/output buffer to said higher-rank apparatus.

47. A collective type magnetic disk device according to claim 46, wherein said data storage units comprise a plurality of magnetic disk units provided with magnetic disk controller respectively, and a multiplexer for selecting one of said magnetic disk controllers in said magnetic disk units.

48. A collective type magnetic disk device according to claim 46, wherein each of said data storage units includes a pair of said input/output buffers so that while the data of one of said pair of input/output buffers are transferred to said higher-rank apparatus, the other input/output buffer stores data read out from said data storage unit, and when said minimum seek time s of said magnetic disk unit is not longer than the time required for transferring the data of M from said input/output buffer to said higher-rank apparatus, the number n of said data storage units satisfies the following expression of ##EQU33##

49. A collective type magnetic disk device according to claim 46, further comprising a communication means in said multi-disk controller, for connecting said multi-disk controller to said higher-rank apparatus.

50. A collective type magnetic disk device according to claim 49, wherein said communication means comprises a semiconductor storage element.

51. A collective type magnetic disk device according to claim 46, further comprising a physical information table constituted by logical classification identifiers which are identifying codes specified to logic classifications transferred from said higher-rank apparatus and numbers specified to files in the logic classifications, for interrupting file identifiers so as to make the file identifiers correspond to physical positions in said magnetic disk unit.

52. A collective type magnetic disk device according to claim 51, wherein said physical information table includes a semiconductor storage element.

53. A collective type magnetic disk device according to claim 46, wherein said multi-disk controller has means adapted to operate in a manner so that when there are a plurality of files to be read on one and the same cylinder of said magnetic disk unit, and then the following expression ##EQU34## is satisfied on the assumption that a total capacity of file groups not to be read between the files to be read precedingly and succedingly is represented by k, a data transfer rate from said data storage unit to said the input/output buffer is represented by t, and a revolution velocity of said magnetic disk unit is represented by R, said file groups not necessary to be read between said files to be read precedingly and succedingly are also read out once onto said input/output buffer, and when transfer is performed from said input/output buffer to said higher-rank apparatus, the transfer is made while excepting the unnecessary file group.

54. A document information search method for searching for specified text data containing a given search subject key word from a group of document text data stored in advance, said method comprising the steps of:

generating contracted text data for every document in which adjuncts and duplication of repeatedly stated words contained in advance in the text data are eliminated; and

,

performing a contracted text data search for extracting documents each containing a given search subject key word by word from the contracted text data.

55. A document information search method according to claim 54, further comprising the step of performing a search of the documents extracted by said contracted text data search to thereby extract documents each satisfying search conditions of the search subject key word from said documents extracted by said contracted text data search.

56. A document information search method according to claim 55, wherein said predetermined search conditions given to said search subject key word contain at least one of neighbor and contextual conditions.