[go: up one dir, main page]

WO2008041366A1 - Dispositif de recherche de document, procédé de recherche de document et programme de recherche de document - Google Patents

Dispositif de recherche de document, procédé de recherche de document et programme de recherche de document Download PDF

Info

Publication number
WO2008041366A1
WO2008041366A1 PCT/JP2007/001065 JP2007001065W WO2008041366A1 WO 2008041366 A1 WO2008041366 A1 WO 2008041366A1 JP 2007001065 W JP2007001065 W JP 2007001065W WO 2008041366 A1 WO2008041366 A1 WO 2008041366A1
Authority
WO
WIPO (PCT)
Prior art keywords
path expression
tag
tag set
document
expression
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2007/001065
Other languages
English (en)
French (fr)
Inventor
Jun Takeuchi
Takanori Hino
Shingo Ochi
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
JustSystems Corp
Original Assignee
JustSystems Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by JustSystems Corp filed Critical JustSystems Corp
Priority to US12/442,835 priority Critical patent/US20100100544A1/en
Publication of WO2008041366A1 publication Critical patent/WO2008041366A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/80—Information retrieval; Database structures therefor; File system structures therefor of semi-structured data, e.g. markup language structured data such as SGML, XML or HTML
    • G06F16/81—Indexing, e.g. XML tags; Data structures therefor; Storage structures

Definitions

  • Document search device Document search method, and document search program
  • the present invention relates to a document processing technique, and more particularly, to an information retrieval technique for a structured document file.
  • Patent Document 1 Japanese Patent Laid-Open No. 2006-048536
  • HTML Hyper Text Markup Language
  • XML Extensible Markup Language
  • HTML Hyper Text Markup Language
  • XML extensible Markup Language
  • XP at h is a notation that can handle ellipsis.
  • XP at h is a notation that can handle ellipsis.
  • the XP ath expression “/ suggestion ⁇ aggregation” is “in the hierarchy below the ⁇ suggestion> tag.
  • ⁇ Consolidation processing> means all conditions where tags appear. In the following, such a condition related to a tag route is called a “route condition”.
  • the syntax that indicates the tag path based on the tag hierarchy, such as the XP ath expression, is called the “path expression”.
  • any route expression specified as “/ proposed / content / aggregate”, “/ suggest / content / basic / aggregate” is applicable To do.
  • the desired data can be extracted from the structured document file.
  • the tag structure of a structured document file is analyzed, the path information of the tag is expanded in a memory, and the position data that matches the path condition is detected.
  • this method has the problem that the memory usage is large and the processing time is long.
  • searching for desired data from a large number of structured document files or structured document files with complex tag hierarchies such problems are likely to become apparent.
  • the present invention has been made in view of such circumstances, and an object of the present invention is to provide a technique for efficiently retrieving desired data from a structured document file based on an incomplete path expression. There are things to do.
  • One embodiment of the present invention relates to a document search apparatus for searching desired data from a structured document file.
  • This device holds index information that associates a hierarchically set tag set in a structured document file with one or more positions that include the tag set as part of a path expression.
  • this apparatus receives an input of a partial path expression, it refers to the index information, and specifies a position where a tag set included in the partial path expression appears as a part of the path expression as a candidate position for the search target position.
  • desired data can be efficiently searched from a structured document file based on an incomplete path expression.
  • FIG. 1 is a schematic diagram for explaining an overview of processing by a document search device.
  • FIG. 2 is a diagram showing an XML document in the present embodiment.
  • FIG. 3 is a data structure diagram of a complete path index.
  • FIG. 4 is a data structure diagram showing details of the route column in FIG.
  • FIG. 5 is a data structure diagram of a partial path index.
  • FIG. 6 is a functional block diagram of the document search device.
  • FIG. 7 is a flowchart showing the process of search processing based on a partial path expression. Explanation of symbols
  • 1 00 Document retrieval device 1 1 0 User interface processing unit, 1 1 2 Input unit, 1 1 4 Display unit, 1 20 Data processing unit, 1 22 Path decomposition unit, 1 24 Search unit, 1 26 Registration section, 1 28 Partial extraction section, 1 30 Index holding section, 1 32 ID conversion section, 1 34 Location identification section, 1 36 Range identification section, 200 Document database, 21 2 Document location column, 21 4 Complete path index, 21 6 Route field, 21 8 Route ID field, 222 Range field, 226 Key field, 228 Position index field, 230 Partial route index.
  • FIG. 1 is a schematic diagram for explaining an outline of processing by the document search apparatus 100.
  • the document search apparatus 100 searches the document database 200 for data that conforms to the path expression.
  • the document file of the document database 200 is a structured document file structured by tags like an XML document or an XHTML document. In this embodiment, description will be made assuming that the document file to be searched is an XML file.
  • the index holding unit 130 of the document search apparatus 100 holds index information for searching for each document file.
  • index information There are two types of index information, a complete path index 214 and a partial path index 230, each of which will be described in detail later with reference to FIGS.
  • the document search device 100 searches the document database 200 for the position in which document the data to be searched is based on the input path expression and index information.
  • the document search device 100 displays the document ID of the detected document file and the search target data in the document file on the screen. In this way, the user of the document search device 100 can search the data to be searched or the search for any route expression. Search for candidate data to be searched from the document database 2 0 0.
  • FIG. 2 is a diagram showing an XML document 2 10 in the present embodiment.
  • a document ID is assigned to each document file in the document database 200.
  • Document ID of XML document 2 1 0 shown in the figure is “1”.
  • the document ID is an ID for uniquely identifying a document file in the document database 200.
  • This XML document 210 is an XML document related to an idea proposal, and includes a plurality of tags such as “proposal” and “ ⁇ inventor>”.
  • the document position column 2 1 2 indicates the position of various data included in the XML document 2 1 0. For example, the document position of the ⁇ Proposal> tag in this document is “1”, and the document position of the ⁇ / Aggregation> tag is “1 6”.
  • the document position of the character string “Shinori Takeuchi” which is the content data of the ⁇ inventor> tag is “3”.
  • the document position is assigned to each tag, attribute, comment, and tag data, and is a unique value for each document. In the following, the document position with respect to the tag will be mainly described for the sake of simplicity.
  • FIG. 3 is a data structure diagram of the complete path index 2 1 4.
  • the complete path index 2 1 4 is stored in the index holding unit 1 3 0.
  • the route field 2 1 6 is a list of route expressions included in the document database 2 0 0.
  • the route ID column 2 1 8 shows the route ID of the route shown in the route column 2 1 6.
  • the path ID is a numeric string obtained by converting a character string indicating a path expression according to a predetermined rule. Either a hash function or a predetermined table may be used for conversion, but in any case, any value is acceptable as long as each path expression is uniquely identified to the extent that there is no practical problem.
  • route ID 2.
  • route ID 8 for "/ suggestion / content / processing / preprocessing / aggregation processing”.
  • the range column 222 indicates the range of the data range indicated by the path expression in the form of [document ID, start position, end position].
  • the document position of the ⁇ Aggregation process> tag is "1 4" and the document position of the ⁇ / Aggregation process> tag is "1 6”.
  • a node represented as a path expression in the complete path index 214 is not limited to a tag such as ⁇ inventor>.
  • the string “Shinnai Takeuchi”, which is the element data of the ⁇ inventor> tag in Fig. 2 can be registered as a route expression.
  • the route ID 201 4 is a numerical value obtained by converting the character string “/ suggestion / inventor /“ Shinori Takeuchi ”” based on a predetermined rule.
  • FIG. 4 is a data structure diagram showing details of the route field 216 in FIG.
  • the path column 216 does not actually store the character string indicating the path expression as it is, but stores data that expresses the path expression numerically (hereinafter referred to as “numerical path expression” when particularly distinguished). Is done.
  • the numerical route formula shows the route in the reverse order of the actual route.
  • Each numerical value included in the numerical path expression may be a numerical value that can uniquely identify a character string such as “Proposal” or “Shinji Takeuchi” that is a component of the path expression.
  • the path expression “/ suggestion / inventor /“ Shinji Takeuchi ”” is the numerical path of 1 3 by ⁇ “4 8 5 7 3 0 1 0 2 0 8 8 1” in the route field 2 1 6 Expressed as an expression.
  • the document retrieval device 1 0 0 converts the “configuration” of the end node into a numerical expression.
  • the end You can see a node, but you often don't know its upper node.
  • FIG. 5 is a data structure diagram of the partial path index 2 30.
  • the index holding unit 1 3 0 stores the partial path index 2 3 0 in addition to the complete path index 2 1 4.
  • Key column 2 2 6 shows two tags (hereinafter referred to as “key tag set”) that are the search keys in the partial path index 2 3 0, and one tag (hereinafter referred to as “key tag”). Is called). When we call a key tag set and a key tag together, they are simply called “keys”.
  • Key Tag set refers to a combination of tags that are directly related to each other as a hierarchy of tags in a document. For example, in XML document 2 1 0, the direct parent tag of ⁇ configuration> tag is ⁇ content>, so “content / configuration” is a key tag set.
  • ⁇ Proposal> tag ⁇ issue> tag is not a direct parent tag of ⁇ configuration> tag, so “proposal / configuration” and “issue / configuration” are not key tag sets.
  • all tags included in the document can be key tags.
  • the partial path index 2 3 0 is data intended for keys included in all documents included in the document database 2 0 0.
  • the position index field 2 2 8 indicates the position where the key appears in the form of [path ID, appearance hierarchy]. This type of position data is called “position index”.
  • Ru Tono -Do is counted as the 0th hierarchy, and the 1st hierarchy is counted as the hierarchy directly under the root node.
  • the tag set “content / processing” and the tag “aggregation processing” are extracted from the partial path expression.
  • the position index of the key tag set "Content / Process” is 5 of "6, 2", “7, 2", “8, 2", “1 1, 2", “1 2, 2” One.
  • five candidates are identified as position indexes that include the key tag set “content / processing” in the path expression.
  • a candidate position index is referred to as a “candidate position”.
  • the key tag “Aggregation” has two position indexes, “8, 5” and “1 2, 4”. In other words, there are two candidate positions for the key tag “aggregation processing”.
  • range data [1, 14, 4, 16] can be specified.
  • path expression “/ suggestion / content / processing / preprocessing / aggregation processing” is specified in the document (ID: 1).
  • the partial path index 2 3 0 it is not necessary to analyze the path of the XML document itself in the document database 2 0 0 when an incomplete partial search expression is input.
  • the candidate positions can be narrowed down more efficiently than directly searching for a route expression that matches the route condition from the route field 2 1 6 of the complete route index 2 1 4.
  • Search using the partial path index 2 3 0 is a particularly effective search method when the tag hierarchy of the XML document is deep or the number of documents to be searched is large.
  • the keys in the key field 2 2 6 are stored as a numeric string of a predetermined length called a key ID.
  • the key ID only needs to be a numerical value that can uniquely identify the key tag set or key tag.
  • the search process can be speeded up more quickly than storing the character string indicating the key name as it is.
  • the key ID may also be generated by converting a character string indicating the key using a predetermined hash function. Alternatively, they may be associated with each other by a conversion table that uniquely associates keys and keys.
  • FIG. 6 is a functional block diagram of the document search apparatus 100.
  • the document search device 100 includes a user interface_processing unit 110, a data processing unit 120, and an index storage unit 130.
  • the user interface processing unit 110 is responsible for processing related to the user interface in general, such as input processing from the user and information display to the user. In the present embodiment, it is assumed that the user interface processing unit 110 provides the user interface service of the document search apparatus 100. The As another example, the user may operate the document search apparatus 100 via the Internet. In this case, a communication unit (not shown) receives operation instruction information from the user terminal, and transmits processing result information executed based on the operation instruction to the user terminal.
  • the data processing unit 120 performs various data processing based on data acquired from the user interface processing unit 110 or the document database 200.
  • the data processing unit 1 2 0 also serves as an interface between the user interface processing unit 1 1 0 and the index holding unit 1 3 0.
  • the user interface processing unit 1 1 0 includes an input unit 1 1 2 and a display unit 1 1 4.
  • the input unit 1 1 2 receives an input operation from the user.
  • the search path expression is obtained via the input unit 1 1 2.
  • Display unit 1 1 4 displays various types of information to the user.
  • the data processing unit 1 2 0 includes a path decomposition unit 1 2 2, a search unit 1 2 4, and a registration unit 1 2 6.
  • the path decomposition unit 1 2 2 analyzes the path information of partial path expressions and XML documents.
  • the part extractor 1 2 8 extracts tags and tag sets from partial path expressions and XML documents.
  • ID converter 1 3 2 converts path expressions and keys into numerical representations. Further, the I D conversion unit 1 3 2 generates a route ID from the route expression.
  • the registration unit 1 2 6 registers the data about the document in the complete route index 2 1 4 and the partial route index 2 3 0.
  • the ID conversion unit 1 32 converts the path expression in the document into a numerical path expression. Then, the registration unit 1 2 6 registers the numerical route expression and its range data in the complete route index 2 1 4. The partial extraction unit 1 2 8 extracts a key from the document, and the ID conversion unit 1 3 2 converts the key into a key ID in a numerical expression format. The registration unit 1 2 6 registers the key ID and position index in the numerical expression format in the partial path index 2 3 0. The same processing method is used when an XML document with the document database 2 0 0 is edited or deleted. Thus, the complete path index 2 1 4 and the partial path index 2 3 0 are updated.
  • the search unit 1 2 4 detects the document and the corresponding part based on the input route expression.
  • the search unit 1 2 4 includes a position specifying unit 1 3 4 and a range specifying unit 1 3 6.
  • the position specifying unit 1 3 4 refers to the partial path index 2 3 0 and specifies the position index from the key.
  • the range specification unit 1 3 6 specifies range data from the path expression.
  • the partial extraction unit 1 2 8 extracts a key from the partial path expression, and the ID conversion unit 1 3 2 converts the key into a numeric expression key ID.
  • the position specifying unit 1 34 specifies a candidate position from the partial path index 2 30 based on this key ID.
  • the range specifying unit 1 3 6 specifies range data from the candidate positions specified by the position specifying unit 1 3 4. The result is displayed on the display 1 1 4.
  • FIG. 7 is a flowchart showing the process of search processing based on a partial path expression.
  • the input unit 1 1 2 accepts an input of a partial path expression (S 1 0).
  • the partial extraction unit 1 2 8 extracts a tag set or tag as one or more keys from the partial search expression (S 1 2).
  • the partial search expression “ ⁇ content / process / * / aggregation process” is input and the key tag set “content / process” and key tag “aggregation process” are extracted.
  • the extracted key is converted into key_ 1 D by the ID conversion unit 1 3 2.
  • the position specifying unit 1 3 4 refers to the partial path index 2 3 0 and specifies a candidate position from the key ID (S 1 4). If it is a position index of the key tag set “Content / Process”, 5 position indexes of “6, 2”, “7, 2”, “8, 2”, “1 1, 2”, “1 2, 2” Is identified.
  • the process returns to S 14 and the candidate position for the next key is specified.
  • two position indexes of “8, 5” and “1 2, 4” are specified for the key tag “aggregation processing”.
  • the position specifying unit 1 3 4 specifies a position that matches between the candidate positions specified for each key (S 1 8 ) Thus, the number of candidate positions is narrowed down.
  • a pair of “8, 2” and “8, 5” is specified.
  • a complex data search is also possible. For example, suppose that a partial search expression “Takeuchi creator” and a character string ““ Shinji Takeuchi ”” are input.
  • the route formula is “/ suggestor / inventor”.
  • a character string search unit (not shown) of the search unit 1 2 4 searches for the corresponding range data from the complete path index 2 1 4 for the character string "" Shinji Takeuchi "".
  • range data is specified as [1, 3, 3].
  • the range of the data of the string ““ Shinnai Takeuchi ”” falls within the range of the data of “/ suggestor / inventor”.
  • the search section 1 2 4 matches the range data specified for each of the partial search formulas “Kashiwa inventor” and the string “Shinori Takeuchi”, so “/ suggestion / inventor /“ Shinori Takeuchi ”” Identify as data.
  • the key tag set in the present embodiment has been described as a combination of two tags that are directly in a hierarchical relationship, the key tag set does not have to be constrained by such conditions. .
  • it may be a combination of three tags that have a direct hierarchical relationship in the hierarchy.
  • a combination of three or more tags may be used as a key tag set.
  • the tags included in the key tag set do not necessarily have a direct vertical relationship. For example, in the route expression “/ suggestion / content / processing / preprocessing / aggregation processing”, there is a difference of two levels between tags in the tag combination “content-preprocessing”. In the case of the tag combination “content-aggregation”, the hierarchy difference is 3.
  • the position specifying unit 1 3 4 may specify the candidate position by referring to the hierarchy difference of the tag set extracted from the partial path expression and the hierarchy difference in the key tag set.
  • the document search apparatus 100 is a type in which the position of data is specified by a path expression based on a hierarchical structure of tags, such as XHTML, HTML, and SGML. Any document file can be applied.
  • data retrieval based on a partial path expression can be executed efficiently.
  • the candidate positions can be narrowed down based on the tag set or tag included in the partial path expression. it can.
  • the position of the data can be specified more specifically by the complete path index 2 1 4. Since it is not necessary to check the document file at the time of retrieval and expand the route information in memory, efficient retrieval is possible.
  • the document retrieval apparatus 1 0 0 shown in the present embodiment refers to two types of index data, a complete path index 2 1 4 and a partial path index 2 3 0, so that the position of data to be obtained can be calculated at high speed and light computer load. Can be specified at
  • Index information described in the claims is expressed by a partial path index 2 30 in the present embodiment.
  • the “tag set ID” described in the claims is expressed as a key ID for the key tag set in this embodiment.
  • desired data can be efficiently searched from a structured document file based on an incomplete path expression.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Description

明 細 書
文書検索装置、 文書検索方法および文書検索プログラム
技術分野
[0001] 本発明は、 文書処理技術に関し、 特に、 構造化文書ファイルを対象とした 情報検索技術、 に関する。
背景技術
[0002] コンピュータの普及とネットワーク技術の進展にともない、 ネットワーク を介した電子情報の交換が盛んになつている。 これにより、 従来においては 紙ベースで行われていた事務処理の多く力 ネットワークベースの処理に置 き換えられつつある。 デジタル化とネットワーク技術の進展は、 情報取得コ ストを急激に低下させている。 このような状況において、 大量の文書フアイ ルの中から所望のデータを検索する技術の重要性が高まっている。
特許文献 1 ：特開 2006 _ 048536号公報
発明の開示
発明が解決しょうとする課題
[0003] ところで、 近年では、 多くの文書ファイルが、 HTML (Hyper Text Mark up Language; や XHTML (, extensible HyperText Markup Language) 、 X ML (extensible Markup Language) などによる構造化文書ファイルとして 作成されるようになってきている。 構造化文書ファイルはタグによって階層 化されるため、 文書中のデータをタグのパス表記によって指定できる。 この ように、 構造化文書ファイルには、 データの位置を特定しやすいという優れ た特性がある。 中でも、 XMLは、 ネットワークを介して他者とデータを共 有するのに適した形式として注目されている。 XML文書であれば、 XP a t h (XML Path Language) に基づく構文である XP a t h式によりデータを 特定できる。
[0004] XP a t hは、 省略記号にも対応できる表記法となっている。 たとえば、
「/提案〃集約処理」 という XP a t h式は、 「<提案 >タグの下位の階層に <集約処理 >タグが出現する全てのパス」 という条件を意味する。 以下、 こ のようなタグの経路に関する条件のことを 「経路条件」 とよぶことにする。 また、 X P a t h式のように、 タグの階層構造に基づいてタグのパスを示す 構文のことを 「経路式」 とよぶことにする。 上記経路条件に対しては、 「/提 案/集約処理」 、 「/提案/内容/集約処理」 、 「/提案/内容/基本処理/集約処 理」 として指定されるいずれの経路式も適合する。
—方 「/提案/ */集約処理」 という X P a t h式は、 「<提案 >タグから 2 階層下位の階層に <集約処理 >タグが出現する全てのパス」 という経路条件 を意味する。 上記した 3つの経路式のうちでは 「/提案/内容/集約処理」 だけ がこの経路条件に適合する。
[0005] ユーザが省略記号のない X P a t h式を指定できれば、 構造化文書フアイ ルから所望のデータを取り出すことができる。 しかし、 常に正確に経路式が わかるとは限らない。 たとえば、 検索対象となるデータが <提案 >タグの下 の <集約処理 >タグにあることがわかっていても、 <提案 >タグと <集約処 理>タグの間に、 どのようなタグが何階層あるか、 そもそも、 どの文書に求 めるデータがあるかわからないことがある。
上記したような省略記号を含む不完全な経路式が入力されたとき、 その経 路式によって示される経路条件に適合するデータを検索できれば便利である 。 以下、 省略記号を含むなどの理由により、 検索対象となるデータの位置を 一意に特定するには不充分な経路式のことを 「部分経路式」 とよび、 省略記 号を含まない経路式のことを 「完全経路式」 とよぶ。
[0006] 部分経路式に基づくデータ検索方法として、 構造化文書ファイルのタグ構 造を解析し、 タグの経路情報をメモリに展開した上で、 経路条件に適合する 位置のデータを検出するという方法が一般的である。 しかし、 このような方 法は、 メモリの使用量が大きく、 処理時間も長くなるという問題点がある。 特に、 多数の構造化文書ファイルや、 タグの階層構造が複雑な構造化文書フ アイルの中から所望のデータを探す場合には、 このような問題点が顕在化し やすい。 [0007] 本発明はこうした状況に鑑みてなされたものであり、 その目的は、 不完全 な経路式に基づいて構造化文書ファイル中から所望のデータを効率的に検索 するための技術、 を提供することある。
課題を解決するための手段
[0008] 本発明のある態様は、 構造化文書ファイルから所望のデータを検索するた めの文書検索装置に関する。
この装置は、 構造化文書ファイルにおいて階層的に上下関係にあるタグセ ットと、 経路式の一部にそのタグセットを含む 1以上の位置とを対応づけた インデックス情報を保持する。 この装置は、 部分経路式の入力を受け付ける と、 インデックス情報を参照して、 部分経路式に含まれるタグセットが経路 式の一部としてあらわれる位置を検索対象位置の候補位置として特定する。
[0009] インデックス情報としてタグセットごとの位置を登録しておくことにより 、 検索実行時に文書ファイルにアクセスしてタグの階層構造を精査しなくて も、 検索対象となるデータを特定できる。 このため、 不完全な部分経路式が 入力されたときにも、 検索対象となるデータを効率的に検出できる。
[0010] なお、 以上の構成要素の任意の組み合わせ、 本発明の表現を方法、 システ ム、 プログラム、 記録媒体などの間で変換したものもまた、 本発明の態様と して有効である。
発明の効果
[001 1 ] 本発明によれば、 不完全な経路式に基づいて構造化文書ファイル中から所 望のデータを効率的に検索することができる。
図面の簡単な説明
[0012] [図 1 ]文書検索装置による処理の概要を説明するための模式図である。
[図 2]本実施例における X M L文書を示す図である。
[図 3]完全経路インデックスのデータ構造図である。
[図 4]図 3の経路欄の詳細を示すデータ構造図である。
[図 5]部分経路ィンデックスのデータ構造図である。
[図 6]文書検索装置の機能ブロック図である。 [図 7]部分経路式に基づく検索処理の過程を示すフローチヤ一トである。 符号の説明
[0013] 1 00 文書検索装置、 1 1 0 ュ一ザインタフヱ一ス処理部、 1 1 2 入力部、 1 1 4 表示部、 1 20 データ処理部、 1 22 経路 分解部、 1 24 検索部、 1 26 登録部、 1 28 部分抽出部、 1 30 インデックス保持部、 1 32 I D変換部、 1 34 位置特定 部、 1 36 範囲特定部、 200 文書データベース、 21 2 文書 位置欄、 21 4 完全経路インデックス、 21 6 経路欄、 21 8 経路 I D欄、 222 範囲欄、 226 キー欄、 228 位置インデ ックス欄、 230 部分経路インデックス。
発明を実施するための最良の形態
[0014] 図 1は、 文書検索装置 1 00による処理の概要を説明するための模式図で あ 。
ユーザが文書検索装置 1 00に対して経路式を入力すると、 文書検索装置 1 00は経路式に適合するデータを文書データベース 200から検索する。 文書データベース 200の文書ファイルは、 XM L文書や X H TM L文書の ようにタグによって構造化された構造化文書ファイルである。 本実施例にお いては、 検索対象となる文書ファイルは XM Lファイルであるとして説明す る。
[0015] 文書検索装置 1 00のインデックス保持部 1 30は、 各文書ファイルを検 索するためのインデックス情報を保持する。 インデックス情報は、 完全経路 インデックス 21 4と部分経路ィンデックス 230の 2種類があるが、 それ ぞれについては図 3から図 5に関連して後に詳述する。 文書検索装置 1 00 は、 入力された経路式とインデックス情報に基づいて、 文書データベース 2 00から検索対象となるデータがどの文書のどの位置にあるかを検索する。 文書検索装置 1 00は、 検出された文書ファイルの文書 I Dと、 その文書フ アイルにおける検索対象データとを画面表示させる。 こうして、 文書検索装 置 1 00のユーザは、 任意の経路式に対して、 検索対象データ、 または、 検 索対象データの候補を文書データベース 2 0 0から探し出す。
[0016] 図 2は、 本実施例における X M L文書 2 1 0を示す図である。
同図に示す X M L文書 2 1 0を対象として本実施例を説明する。 文書デ一 タベース 2 0 0の各文書ファイルには文書 I Dが付与される。 同図に示す X M L文書 2 1 0の文書 I Dは 「 1」 であるとする。 文書 I Dとは、 文書デ一 タベース 2 0 0において文書ファイルを一意に識別するための I Dである。 このX M L文書2 1 0は、 アイディア提案書に関する X M L文書であり、 く 提案 >ゃ<発案者 >など複数のタグを含む。 文書位置欄 2 1 2は、 X M L文 書 2 1 0に含まれるさまざまなデータの位置を示す。 たとえば、 <提案 >タ グのこの文書における文書位置は 「1」 であり、 < /集約処理 >タグの文書 位置は 「1 6」 である。 また、 <発案者 >タグの内容データである文字列" 竹内真教" の文書位置は 「3」 である。 文書位置は、 タグ、 属性、 コメント 、 タグの内容となるデータごとに割り当てられ、 文書ごとに一意の値となる 以下においては説明を簡単にするため、 タグに対する文書位置を中心とし て説明する。
[0017] 図 3は、 完全経路インデックス 2 1 4のデータ構造図である。
完全経路インデックス 2 1 4は、 インデックス保持部 1 3 0に格納される 。 経路欄 2 1 6は、 文書データベース 2 0 0に含まれる経路式の一覧である 。 経路欄 2 1 6には図 2に示した文書 I D = 1の文書に含まれる経路式だけ でなく、 その他の文書に含まれる経路式も含まれる。 経路 I D欄 2 1 8は、 経路欄 2 1 6に示す経路の経路 I Dを示す。 経路 I Dは、 経路式を示す文字 列を所定規則により変換した数値列である。 ハッシュ関数により変換しても よいし、 所定のテ一ブルによって変換してもよいが、 いずれにしても、 各経 路式が実用上差し支えない程度に一意に識別される値であればよい。
[0018] 同図において、 経路式 「/提案」 の X M L文書 2 1 0における経路 I Dは 「
1」 となっている。 経路式 「/提案/発案者」 の場合、 経路 I D = 2である。 同様に、 「/提案/内容/処理/前処理/集約処理」 については経路 I D = 8とな る。
[0019] 範囲欄 222は、 経路式によって示されるデータ範囲を [文書 I D、 開始 位置、 終了位置] の形式により範囲を示す。 図 2に示した X ML文書 21 0 の場合、 <集約処理 >タグの文書位置は 「1 4」 であり、 < /集約処理 >タ グの文書位置 「1 6」 であるから、 「/提案/内容/処理/前処理/集約処理」 の データは、 文書 I D= 1の文書において文書位置 = (1 4、 1 6) の範囲の データである。 したがって、 範囲欄 222に示される範囲データは、 [1、 1 4、 1 6] となる。
[0020] 同様に、 経路式 「/論文/内容/課題」 の範囲データは [2、 22、 28] で ある。 これは文書 I D = 2の文書において、 文書位置 = (22、 28) の範 囲のデータがこの経路式によって特定されるデータの範囲であることを示す 。 経路式 「/提案/課題」 の範囲データは [1、 5、 7] と [4、 8、 1 6] の 2つである。 これは文書 I D= 1 と文書 I D = 4の 2つの XM L文書のど ちらにも経路式 「/提案/課題」 という経路式が含まれることを意味する。
[0021] 完全経路インデックス 21 4において経路式として表されるノードは <発 案者 >のようなタグに限られない。 たとえば、 図 2の <発案者 >タグの要素 データである文字列" 竹内真教" についても経路式として登録できる。 この 場合、 経路式は 「/提案/発案者/" 竹内真教" 」 、 経路 I D = 201 4、 範囲
[1、 3、 3] となる。 経路 I D = 201 4は、 「/提案/発案者/" 竹内真教 " 」 という文字列を所定規則に基づいて変換することにより得られる数値で
[0022] 図 4は、 図 3の経路欄 21 6の詳細を示すデータ構造図である。
経路欄 21 6には、 実際には経路式を示す文字列がそのまま格納されるの ではなく、 経路式を数値表現したデータ （以下、 特に区別するときには 「数 値経路式」 とよぶ） が格納される。 数値経路式は、 実際の経路とは逆順に経 路を示す。
[0023] 先述した経路式 「/提案/発案者/" 竹内真教" 」 を例として説明する。
数値経路式においては、 まず、 末端ノードである文字列" 竹内真教" を示 す 4バイ トの数値 「4 8 5 7」 が先頭にくる。 「4 8 5 7」 は所定の変換規 則により文字列" 竹内真教" を変換することにより得られる数値である。 次の 1バイ トは、 末端ノードの種別を示す。 種別は、 要素： 1、 属性： 2 、 テキスト ： 3、 処理命令 （Pに Process i ng I nstruct i on) ： 7、 コメント ： 8のいずれかである。 文字列" 竹内真教" は、 「/提案/発案者/」 の内容を示 すテキストなので、 種別は 「3」 となる。
次に、 <発案者 >を示す 4バイ トの数値 「0 1 0 2」 が続く。 「0 1 0 2 」 も所定の変換規則により文字列" 発案者" を変換することにより得られる 数値である。 <提案 >を示す数値は 「0 8 8 1」 となる。 数値経路式に含ま れる各数値は、 経路式の構成要素となる 「提案」 や 「竹内真教」 などの文字 列を一意に識別できる数値であればよい。
以上により、 「/提案/発案者/" 竹内真教" 」 という経路式は、 経路欄 2 1 6においては 「4 8 5 7 3 0 1 0 2 0 8 8 1」 という 1 3バイ 卜の数値経路 式として表される。
[0024] A ：完全経路式が入力された場合
完全経路式として 「/提案/内容/処理/前処理/集約処理」 が入力されたとす る。 文書検索装置 1 0 0は、 まず、 この完全経路式を上述した方法により、 数値経路式に変換する。 この数値経路式と完全経路インデックス 2 1 4の経 路欄 2 1 6における数値経路式を比較することにより、 経路 I D = 8、 範囲 データ [ 1、 1 4、 1 6 ] を検出する。 数値経路式同士のマッチングにより 検出するため、 文字列表現の経路式を比較するよりも高速な検索処理が可能 である。
[0025] B ：部分経路式が入力される場合
部分経路式として 「〃構成」 が入力されたとする。 完全な経路がわからな いので、 文書検索装置 1 0 0は、 末端ノードの 「構成」 を数値表現に変換す る。 このとき、 文書検索装置 1 0 0は、 「構成」 を示す 4バイ 卜の数値と経 路欄 2 1 6の数値経路式の先頭 4バイ トを比較することにより、 経路 I D = 5、 範囲データ [ 1、 9、 1 1 ] を検出する。 部分経路式においては、 末端 ノードがわかるがその上位ノードがわからないことが多い。 本来の経路式の 逆順となるように数値経路式を構成することにより、 部分経路式の末端ノ一 ドだけである程度、 検索対象デ一タの候補を絞り込むことができる。
[0026] ただし、 「〃内容/処理/ */集約処理」 や 「〃内容/処理〃集約処理」 、 「〃 内容/処理/ *」 のような部分経路式が与えられた場合、 完全経路インデックス 2 1 4から検索対象データを特定するためのアルゴリズムは複雑になる。 タ グの階層が深くなるといつそう処理は複雑化する。 そこで、 本実施例におい ては、 完全経路インデックス 2 1 4に加えて部分経路インデックス 2 3 0に より、 検索対象データが存在する可能性がある位置 （以下、 「候補位置」 と よぶ） を効率的に絞り込むための処理を実行している。
[0027] 図 5は、 部分経路インデックス 2 3 0のデータ構造図である。
インデックス保持部 1 3 0は、 完全経路インデックス 2 1 4に加えて部分 経路インデックス 2 3 0も格納している。 キ一欄 2 2 6は、 部分経路インデ ックス 2 3 0において検索のキ一 （Key) となる 2つのタグ （以下、 「キータ グセット」 とよぶ） 力、、 1つのタグ （以下、 「キータグ」 とよぶ） を示す。 キータグセットとキータグを併せていうときには単に 「キー」 とよぶ。 キー タグセッ卜とは、 文書中のタグの階層として直接の上下関係にあるタグの組 み合わせを示す。 たとえば、 X M L文書 2 1 0では <構成 >タグの直接の親 タグは <内容 >なので、 「内容/構成」 はキ一タグセットとなる。 し力、し、 < 提案 >タグゃ <課題 >タグは <構成 >タグの直接の親タグではないので 「提 案/構成」 や 「課題/構成」 はキ一タグセットとはならない。 これに対し、 文 書に含まれる全てのタグがキータグとなることができる。 部分経路ィンデッ クス 2 3 0は、 文書データベース 2 0 0に含まれる全ての文書に含まれるキ 一を対象としたデータである。
[0028] 位置インデックス欄 2 2 8は、 キーの出現する位置を [経路 I D、 出現階 層] の形式で示す。 このような形式の位置データのことを 「位置インデック ス」 とよぶ。 「内容/処理」 というキータグセットは 「/提案/内容/処理」 と いう文書 I D = 1の X M L文書 2 1 0の第 2階層からあらわれる。 ル一トノ -ドを 0階層とし、 第 1階層をルートノード直下の階層として数えている。 以下、 文書 I D = n ( nは自然数） の X M L文書のことを文書 （ I D : n ) のように表記することにする。 位置インデックスには文書 I Dに関する情報 が存在しないため、 部分経路ィンデックス 2 3 0だけでは、 「内容/処理」 が 文書 （ I D ： n ) に存在することはわからない。
[0029] 経路式 「/提案/内容/処理」 の経路 I D = 6より、 「内容/処理」 の位置ィ ンデックスは [ 6、 2 ] となる。 同様にして、 このキ一タグセットは 「/提案 /内容/処理/前処理」 という文書 （ I D ： 1 ) 、 経路 I D = 7の経路式の第 2 階層にもあらわれる。 このときの 「内容/処理」 の位置インデックスは [ 7、 2 ] となる。
[0030] 先ほど例に挙げた 「〃内容/処理/ */集約処理」 という部分経路式の場合、 この部分経路式が示す経路条件は以下の通りである。
1 . 経路式に 「内容/処理」 、 「集約処理」 を含む。
2 . 「内容/処理」 と 「集約処理」 の間には何らかの 1階層がある、 いいか えれば、 <内容 >から 3階層下位に <集約処理 >が出現する。
まず、 部分経路式から、 タグセット 「内容/処理」 、 タグ 「集約処理」 を抽 出する。
[0031 ] キ一タグセット 「内容/処理」 の位置インデックスは、 「6、 2」 、 「7、 2」 、 「8、 2」 、 「1 1、 2」 、 「1 2、 2」 の 5つである。 すなわち、 キータグセット 「内容/処理」 を経路式に含む位置インデックスとして 5箇所 の候補が特定される。 以下、 このような候補となる位置インデックスのこと を 「候補位置」 とよぶ。
キ一タグ 「集約処理」 の位置インデックスは、 「8、 5」 、 「1 2、 4」 の 2つである。 すなわち、 キータグ 「集約処理」 に関する候補位置は 2箇所 である。
[0032] ここで、 「内容/処理」 の位置インデックス 「6、 2」 について、 経路式 I D = 6であるが、 「集約処理」 の位置インデックスには経路 I D = 6となる ものがない。 これは、 経路 I D = 6の経路式には、 「集約処理」 が含まれ得 ないことを意味する。 こうして、 位置インデックス 「6、 2」 は、 上記経路 条件から外れる。 同様の理由から、 「7、 2」 、 「1 1、 2」 も候補から外 れる。 残るのは、 「8、 2」 、 「1 2、 2」 と 「8、 5」 、 「1 2、 4」 と なる。
[0033] 「8、 2」 と 「8、 5」 は、 共に経路 I D = 8という経路式の一部を示し 、 「内容/処理」 が第 2階層、 「集約処理」 が第 5階層にあらわれることを示 している。 すなわち、 経路 I D = 8の経路式は 「/*/内容/処理/ */集約処理」 という経路式を含むことになるが、 これは部分経路式に示された経路条件と 整合している。 完全経路インデックス 21 4の経路 I D = 8のデータを参照 することにより、 範囲データ [1、 1 4、 1 6] を特定できる。 すなわち、 経路式 「/提案/内容/処理/前処理/集約処理」 が文書 （ I D : 1 ) に特定され る。
[0034] —方、 「1 2、 2」 と 「1 2、 4」 は、 共に、 経路 I D= 1 2という経路 式の一部を示し、 「内容/処理」 が第 2階層、 「集約処理」 が第 4階層にあら われることを示している。 すなわち、 経路 I D= 1 2の 「/*/内容/処理/集約 処理」 という経路式を含むことになるが、 これは部分経路式に示された経路 条件と整合していない。 したがって、 文書 （ I D ： 1 ) において、 文書位置 = (1 4、 1 6) の範囲のデータだけが求めるデータである。
[0035] 同様にして、 部分検索式 「〃内容/処理〃集約処理」 が与えられたときには 、 「内容/処理」 と 「集約処理」 の間の階層数が不定なので、 経路 I D = 8と 1 2の両方の経路式が候補となる。 部分検索式 「〃前処理〃集約処理」 が与 えられたときには、 タグ 「前処理」 について [7、 4] 、 [8、 4] 、 [1 5、 3] が候補位置となり、 キータグ 「集約処理」 について [8、 5] 、 [ 1 2、 4] となる。 完全経路インデックス 21 4も参照すると、 文書 I D = 1、 経路式 I D = 8の経路式のみが該当する。 部分検索式 「〃提案/内容/ */ 前処理/集約処理」 であれば、 キータグセット 「提案/内容」 の位置インデッ クスとキ一タグセット 「前処理/集約処理」 についての位置インデックスと完 全経路インデックス 21 4から文書 （ I D : 1 ) の経路 I D = 8の経路式が 特定される。
このように、 部分経路インデックス 2 3 0によれば、 不完全な部分検索式 が入力されたときに文書データベース 2 0 0の X M L文書自体を経路解析す る必要がなくなる。 また、 完全経路インデックス 2 1 4の経路欄 2 1 6から 経路条件に整合する経路式を直接探すよりも、 候補位置を効率的に絞り込む ことができる。 部分経路インデックス 2 3 0を使った検索は、 X M L文書の タグ階層が深くなるときや検索対象となる文書数が多いときには特に有効な 検索方法である。
[0036] キー欄 2 2 6のキーは、 キー I Dとよばれる所定長の数値列として格納さ れる。 キー I Dは、 キータグセットやキータグを一意に識別できる数値であ ればよい。 キー欄 2 2 6におけるキーを数値表現形式で格納することにより 、 キー名を示す文字列をそのまま格納するよりも検索処理をいつそう高速化 することができる。 キー I Dも、 キーを示す文字列を所定のハッシュ関数に よって変換することにより生成してもよい。 あるいは、 キーとキ _ I Dを一 意に対応づける変換テーブルにより、 互いを対応づけてもよい。
[0037] 図 6は、 文書検索装置 1 0 0の機能ブロック図である。
ここに示す各ブロックは、 ハードウェア的には、 コンピュータの C P Uを はじめとする素子や機械装置で実現でき、 ソフトウエア的にはコンピュータ プログラム等によって実現されるが、 ここでは、 それらの連携によって実現 される機能ブロックを描いている。 したがって、 これらの機能ブロックはハ —ドウエア、 ソフトウエアの組み合わせによっていろいろなかたちで実現で きることは、 当業者には理解されるところである。
[0038] 文書検索装置 1 0 0は、 ユーザインタフヱ_ス処理部 1 1 0、 データ処理 部 1 2 0およびインデックス保持部 1 3 0を含む。
ユーザインタフェース処理部 1 1 0は、 ユーザからの入力処理やユーザに 対する情報表示のようなユーザインタフェース全般に関する処理を担当する 。 本実施例においては、 ユーザインタフヱ一ス処理部 1 1 0により文書検索 装置 1 0 0のュ一ザインタフヱ一スサ一ビスが提供されるものとして説明す る。 別例として、 ユーザはインタ一ネットを介して文書検索装置 1 0 0を操 作してもよい。 この場合、 図示しない通信部が、 ユーザ端末からの操作指示 情報を受信し、 またその操作指示に基づいて実行された処理結果情報をユー ザ端末に送信することになる。
[0039] データ処理部 1 2 0は、 ユーザインタフヱース処理部 1 1 0や文書データ ベース 2 0 0から取得されたデータを元にして各種のデータ処理を実行する 。 データ処理部 1 2 0は、 ュ一ザインタフヱ一ス処理部 1 1 0とインデック ス保持部 1 3 0の間のインタフェースの役割も果たす。
[0040] ユーザインタフェース処理部 1 1 0は、 入力部 1 1 2と表示部 1 1 4を含 む。 入力部 1 1 2は、 ユーザからの入力操作を受け付ける。 検索用の経路式 は、 入力部 1 1 2を介して取得される。 表示部 1 1 4は、 ユーザに対して各 種情報を表示する。
[0041 ] データ処理部 1 2 0は、 経路分解部 1 2 2と検索部 1 2 4、 登録部 1 2 6 を含む。
経路分解部 1 2 2は、 部分経路式や X M L文書の経路情報を解析する。 部 分抽出部 1 2 8は、 部分経路式や X M L文書からタグやタグセットを抽出す る。 I D変換部 1 3 2は、 経路式やキーを数値表現に変換する。 また、 I D 変換部 1 3 2は、 経路式から経路 I Dを生成する。 登録部 1 2 6は、 新たな X M L文書が文書データベース 2 0 0に追加されるとき、 その文書について のデータを完全経路インデックス 2 1 4と部分経路インデックス 2 3 0に登 録する。
[0042] X M L文書が文書データべ一ス 2 0 0に追加されるとき、 I D変換部 1 3 2は文書中の経路式を数値経路式に変換する。 そして、 登録部 1 2 6が完全 経路インデックス 2 1 4に数値経路式とその範囲データを登録する。 また、 部分抽出部 1 2 8は文書からキーを抽出し、 I D変換部 1 3 2がキーを数値 表現形式のキー I Dに変換する。 登録部 1 2 6は部分経路インデックス 2 3 0に数値表現形式のキー I Dと位置インデックスを登録する。 文書データべ —ス 2 0 0の X M L文書が編集、 削除されたときにも、 同様の処理方法によ り、 完全経路インデックス 2 1 4と部分経路インデックス 2 3 0が更新され る。
[0043] 検索部 1 2 4は、 入力された経路式に基づいて、 文書および該当箇所を検 出する。 検索部 1 2 4は、 位置特定部 1 3 4と範囲特定部 1 3 6を含む。 位 置特定部 1 3 4は、 部分経路インデックス 2 3 0を参照して、 キーから位置 インデックスを特定する。 範囲特定部 1 3 6は、 経路式から範囲データを特 定する。
部分経路式による検索に際しては、 部分抽出部 1 2 8が部分経路式からキ 一を抽出し、 I D変換部 1 3 2がキーを数値表現形式のキー I Dに変換する 。 位置特定部 1 3 4は、 このキ _ I Dに基づいて部分経路インデックス 2 3 0から候補位置を特定する。 範囲特定部 1 3 6は、 位置特定部 1 3 4が特定 した候補位置から、 範囲データを特定する。 結果は、 表示部 1 1 4により画 面表示される。
[0044] 図 7は、 部分経路式に基づく検索処理の過程を示すフローチャートである まず、 入力部 1 1 2が部分経路式の入力を受け付ける （S 1 0 ) 。 部分抽 出部 1 2 8は、 部分検索式から 1以上のキーとなるタグセットゃタグを抽出 する （S 1 2 ) 。 ここでは、 先ほどの 「〃内容/処理/ */集約処理」 という部 分検索式が入力され、 キータグセット 「内容/処理」 とキータグ 「集約処理」 が抽出されたとする。 抽出されたキ一は、 I D変換部 1 3 2によってキ _ 1 Dに変換される。 位置特定部 1 3 4は、 部分経路インデックス 2 3 0を参照 して、 キー I Dから候補位置を特定する （S 1 4 ) 。 キータグセット 「内容/ 処理」 の位置インデックスであれば、 「6、 2」 、 「7、 2」 、 「8、 2」 、 「1 1、 2」 、 「1 2、 2」 の 5つの位置インデックスが特定される。
[0045] 更に、 別のキーが抽出されていれば （S 1 6の N ) 、 S 1 4に戻って次の キーについての候補位置が特定される。 先ほどの例の場合、 キータグ 「集約 処理」 について 「8、 5」 、 「1 2、 4」 の 2つの位置インデックスが特定 される。 [0046] 全てのキーについて候補位置が特定されると （S 1 6の Y ) 、 位置特定部 1 3 4は各キーについて特定された候補位置の間で整合する位置を特定する ( S 1 8 ) 。 こうして、 候補位置の数が絞り込まれる。 部分検索式 「〃内容/ 処理/ */集約処理」 については、 「8、 2」 と 「8、 5」 のペアが特定される 。 範囲特定部 1 3 6は、 この位置インデックスに示される経路 I D = 8に基 づいて、 完全経路インデックス 2 1 4から範囲データ [ 1、 1 4、 1 6 ] を 特定する （ S 2 0 ) 。 表示部 1 1 4は、 文書 （ I D ： 1 ) の経路 I D = 8の 経路式について該当データ、 すなわち、 文書位置 1 4から文書位置 1 6まで のデータを画面表示させる （S 2 2 ) 。
[0047] 以上のアルゴリズムに基づいて、 更に、 複合的なデータ検索も可能である 。 たとえば、 部分検索式 「〃発案者」 と文字列 「" 竹内真教" 」 が入力され たとする。 位置特定部 1 3 4は、 キータグ 「発案者」 について、 部分経路ィ ンデックス 2 3 0から位置インデックス 「2、 2」 を特定する。 完全経路ィ ンデックス 2 1 4によると、 「〃発案者」 に該当する範囲データは、 文書 （ I D ： 1 ) 、 文書位置 = ( 2、 4 ) にある。 経路式は 「/提案/発案者」 であ る。
[0048] 検索部 1 2 4の図示しない文字列検索部は、 文字列 「" 竹内真教" 」 につ いて、 完全経路インデックス 2 1 4から該当する範囲データを検索する。 範 囲データとして [ 1、 3、 3 ] と特定されたとする。 この場合、 文字列 「" 竹内真教" 」 のデータの範囲は、 「/提案/発案者」 のデータの範囲におさま つている。 検索部 1 2 4は、 部分検索式 「〃発案者」 と文字列 竹内真教 " 」 のそれぞれについて特定された範囲データが整合したので、 「/提案/発 案者/" 竹内真教" 」 を該当データとして特定する。
[0049] なお、 本実施例におけるキータグセッ卜とは、 階層的に直接の上下関係に ある 2つのタグの組み合わせであるとして説明したが、 キータグセットはこ のような条件に制約される必要はない。 たとえば、 階層的に直接の上下関係 にある 3つのタグの組み合わせであってもよい。 もちろん、 3個以上のタグ の組み合わせをキータグセッ卜としてもよい。 [0050] また、 キータグセッ卜に含まれるタグは、 必ずしも直接の上下関係になく てもよい。 たとえば、 「/提案/内容/処理/前処理/集約処理」 という経路式に おいて、 「内容-前処理」 というタグの組み合わせではタグ間に 2階層の差が ある。 また、 「内容-集約処理」 というタグの組み合わせであれば、 階層差は 3となる。 部分経路インデックス 2 3 0においては、 キ一タグセットと、 そ のキータグセットを構成するタグ間の階層差が記録されてもよい。 そして、 位置特定部 1 3 4は、 部分経路式から抽出したタグセットの階層差と、 キー タグセッ卜における階層差を参照して、 候補位置を特定してもよい。
[0051 ] 本実施例では X M L文書を対象として説明したが、 文書検索装置 1 0 0は 、 X H T M Lや H T M L、 S G M Lなど、 タグの階層構造に基づく経路式に よってデータの位置が特定されるタイプの文書フアイルであれば、 いずれを 対象としても応用可能である。
[0052] 以上、 本実施例に示す文書検索装置 1 0 0によると、 部分経路式に基づく データ検索を効率的に実行できる。 部分経路インデックス 2 3 0に 「キータ グ」 や 「キータグセット」 についての位置インデックスを登録しておくこと により、 部分経路式に含まれるタグセットやタグに基づいて、 候補位置を絞 り込むことができる。 そして、 完全経路インデックス 2 1 4により、 より具 体的にデータの位置を特定できる。 検索時に文書ファイルを調べて、 経路情 報をメモリに展開する必要がないため、 効率的な検索が可能となる。
[0053] 部分経路式によるデータ検索の処理負荷が大きくなると、 部分経路式に基 づくデータ検索がユーザにとって使いにくいものとなってしまう。 本実施例 に示した文書検索装置 1 0 0は、 完全経路インデックス 2 1 4と部分経路ィ ンデックス 2 3 0という 2種類のインデックスデータを参照することにより 、 求めるデータの位置を高速かつ軽い計算機負荷にて特定できることになる
[0054] 以上、 本発明を実施の形態をもとに説明した。 この実施の形態は例示であ り、 それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例 が可能なこと、 またそうした変形例も本発明の範囲にあることは当業者に理 解されるところである。
[0055] 請求項に記載の 「インデックス情報」 は、 本実施例における部分経路イン デックス 2 3 0により表現されている。 請求項に記載の 「タグセット I D」 は、 本実施例においては、 キ一タグセットについてのキ一 I Dとして表現さ れている。
これら請求項に記載の各構成要件が果たすべき機能は、 本実施例において 示された各機能ブロックの単体もしくはそれらの連係によって実現されるこ とも当業者には理解されるところである。
産業上の利用可能性
[0056] 本発明によれば、 不完全な経路式に基づいて構造化文書ファイル中から所 望のデータを効率的に検索することができる。

Claims

請求の範囲
[1 ] タグの階層構造に基づく経路式によってデータの位置が特定される構造化 文書ファイルにおいて、 階層的に上下関係にあるタグの組み合わせであるタ グセッ卜と、 経路式の一部にそのタグセットを含む 1以上の位置とを対応づ けたインデックス情報を保持するインデックス保持部と、
前記構造化文書ファイルにおける検索対象位置への経路式の一部を示す部 分経路式の入力を受け付ける経路式入力部と、
前記部分経路式から階層的に上下関係にあるタグセットを抽出するタグセ ット抽出部と、
前記インデックス情報を参照して、 前記部分経路式から抽出されたタグセ ッ卜が経路式の一部としてあらわれる位置を前記検索対象位置の候補位置と して特定する候補位置特定部と、
を備えることを特徴とする文書検索装置。
[2] タグセットとは、 階層的に直接の上下関係にある 2つのタグの組み合わせ であることを特徴とする請求項 1に記載の文書検索装置。
[3] 前記タグセット抽出部が、 前記部分経路式から第 1のタグセッ卜と第 2の タグセットを抽出したとき、
前記候補位置特定部は、 前記第 1のタグセッ卜についての候補位置と前記 第 2のタグセッ卜についての候補位置を比較して互いに整合する位置を、 前 記検索対象位置の候補位置として特定することを特徴とする請求項 1または 2に記載の文書検索装置。
[4] 前記タグセット抽出部が、 前記第 1のタグセットを前記第 2のタグセット よりも階層的に上位のタグセットとして検出したとき、
前記候補位置特定部は、 前記第 1のタグセットと前記第 2のタグセットの 前記部分経路式における階層上の距離と、 前記第 1のタグセッ卜についての 候補位置と前記第 2のタグセットについての候補位置との距離が整合する位 置を、 前記検索対象位置の候補位置として特定することを特徴とする請求項 3に記載の文書検索装置。
[5] 前記インデックス保持部は、 更に、 前記構造化文書ファイルに含まれるタ グと、 経路式の一部にそのタグを含む 1以上の位置とをインデックス情報の —部として対応づけて保持し、
前記タグセット抽出部は、 前記部分経路式から特定タグを抽出し、 前記候補位置特定部は、 前記インデックス情報を参照して、 前記部分経路 式から抽出された特定タグが経路式の一部としてあらわれる位置を前記特定 タグについての候補位置として検出すると共に、 前記部分経路式から抽出さ れたタグセットの候補位置と前記特定タグについての候補位置を比較して互 いに整合する位置を、 前記検索対象位置の候補位置として特定することを特 徵とする請求項 1から 4のいずれかに記載の文書検索装置。
[6] 前記インデックス保持部は、 タグセットを所定規則にしたがって所定長の 文字列に変換したタグセット I Dと、 経路式の一部にそのタグセットを含む 1以上の位置を対応づけてインデックス情報として保持し、
前記候補位置特定部は、 前記部分経路式から抽出されたタグセットを前記 所定規則にしたがってタグセット I Dに変換した上で、 候補位置を特定する ことを特徴とする請求項 1から 5のいずれかに記載の文書検索装置。
[7] タグの階層構造に基づく経路式によってデータの位置が特定される構造化 文書ファイルにおいて、 階層的に上下関係にあるタグの組み合わせであるタ グセッ卜と、 経路式の一部にそのタグセットを含む 1以上の位置とを対応づ けたインデックス情報を取得するステップと、
前記構造化文書ファイルにおける検索対象位置への経路式の一部を示す部 分経路式の入力を受け付けるステップと、
前記部分経路式から階層的に上下関係にあるタグセットを抽出するステツ プと、
前記インデックス情報を参照して、 前記部分経路式から抽出されたタグセ ッ卜が経路式の一部としてあらわれる位置を前記検索対象位置の候補位置と して特定するステップと、
を備えることを特徴とする文書検索方法。 タグの階層構造に基づく経路式によってデータの位置が特定される構造化 文書ファイルにおいて、 階層的に上下関係にあるタグの組み合わせであるタ グセッ卜と、 経路式の一部にそのタグセットを含む 1以上の位置とを対応づ けたィンデックス情報を保持する機能と、
前記構造化文書ファイルにおける検索対象位置への経路式の一部を示す部 分経路式の入力を受け付ける機能と、
前記部分経路式から階層的に上下関係にあるタグセットを抽出する機能と 前記インデックス情報を参照して、 前記部分経路式から抽出されたタグセ ッ卜が経路式の一部としてあらわれる位置を前記検索対象位置の候補位置と して特定する機能と、
をコンピュータに発揮させることを特徴とする文書検索プログラム。
PCT/JP2007/001065 2006-09-29 2007-09-28 Dispositif de recherche de document, procédé de recherche de document et programme de recherche de document Ceased WO2008041366A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
US12/442,835 US20100100544A1 (en) 2006-09-29 2007-09-28 Document searching device, document searching method, and document searching program

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2006-267888 2006-09-29
JP2006267888A JP4860416B2 (ja) 2006-09-29 2006-09-29 文書検索装置、文書検索方法および文書検索プログラム

Publications (1)

Publication Number Publication Date
WO2008041366A1 true WO2008041366A1 (fr) 2008-04-10

Family

ID=39268232

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2007/001065 Ceased WO2008041366A1 (fr) 2006-09-29 2007-09-28 Dispositif de recherche de document, procédé de recherche de document et programme de recherche de document

Country Status (3)

Country Link
US (1) US20100100544A1 (ja)
JP (1) JP4860416B2 (ja)
WO (1) WO2008041366A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2011022867A1 (en) * 2009-08-24 2011-03-03 Hewlett-Packard Development Company, L.P. Method and apparatus for searching electronic documents

Families Citing this family (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2009295013A (ja) * 2008-06-06 2009-12-17 Hitachi Ltd データベース管理方法、データベース管理装置およびプログラム
JP5191441B2 (ja) * 2009-05-14 2013-05-08 日本電信電話株式会社 インデクス構築方法及び装置及び情報検索方法及び装置及びプログラム
JP5084895B2 (ja) * 2010-11-18 2012-11-28 ヤフー株式会社 テキストデータ読出装置、方法及びプログラム
JP4959032B1 (ja) * 2011-09-14 2012-06-20 株式会社マイニングブラウニー ウェブページ解析装置およびウェブページ解析用プログラム
US11487707B2 (en) * 2012-04-30 2022-11-01 International Business Machines Corporation Efficient file path indexing for a content repository
US8914356B2 (en) 2012-11-01 2014-12-16 International Business Machines Corporation Optimized queries for file path indexing in a content repository
US9323761B2 (en) 2012-12-07 2016-04-26 International Business Machines Corporation Optimized query ordering for file path indexing in a content repository
JP6163854B2 (ja) * 2013-04-30 2017-07-19 富士通株式会社 検索制御装置、検索制御方法、生成装置および生成方法
JP5954742B2 (ja) 2013-07-23 2016-07-20 インターナショナル・ビジネス・マシーンズ・コーポレーションＩｎｔｅｒｎａｔｉｏｎａｌ Ｂｕｓｉｎｅｓｓ Ｍａｃｈｉｎｅｓ Ｃｏｒｐｏｒａｔｉｏｎ 文書を検索する装置及び方法
WO2018096686A1 (ja) * 2016-11-28 2018-05-31 富士通株式会社 検証プログラム、検証装置、検証方法、インデックス生成プログラム、インデックス生成装置およびインデックス生成方法

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH11242676A (ja) * 1998-02-25 1999-09-07 Hitachi Ltd 構造化文書登録方法、検索方法、およびそれに用いられる可搬型媒体
JP2003067403A (ja) * 2001-08-24 2003-03-07 Fuji Xerox Co Ltd 構造化文書管理装置及び構造化文書管理方法、検索装置、検索方法

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7877400B1 (en) * 2003-11-18 2011-01-25 Adobe Systems Incorporated Optimizations of XPaths
EP1735726B1 (en) * 2004-04-09 2012-08-22 Oracle International Corporation Index for accessing xml data
JP2006185408A (ja) * 2004-11-30 2006-07-13 Matsushita Electric Ind Co Ltd データベース構築装置及びデータベース検索装置及びデータベース装置
US7370061B2 (en) * 2005-01-27 2008-05-06 Siemens Corporate Research, Inc. Method for querying XML documents using a weighted navigational index
JP4374014B2 (ja) * 2006-11-21 2009-12-02 株式会社日立製作所 インデクス生成装置及びそのプログラム
US8161035B2 (en) * 2009-06-04 2012-04-17 Oracle International Corporation Query optimization by specifying path-based predicate evaluation in a path-based query operator

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH11242676A (ja) * 1998-02-25 1999-09-07 Hitachi Ltd 構造化文書登録方法、検索方法、およびそれに用いられる可搬型媒体
JP2003067403A (ja) * 2001-08-24 2003-03-07 Fuji Xerox Co Ltd 構造化文書管理装置及び構造化文書管理方法、検索装置、検索方法

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2011022867A1 (en) * 2009-08-24 2011-03-03 Hewlett-Packard Development Company, L.P. Method and apparatus for searching electronic documents

Also Published As

Publication number Publication date
US20100100544A1 (en) 2010-04-22
JP2008090403A (ja) 2008-04-17
JP4860416B2 (ja) 2012-01-25

Similar Documents

Publication Publication Date Title
WO2008041366A1 (fr) Dispositif de recherche de document, procédé de recherche de document et programme de recherche de document
US8381095B1 (en) Automated document revision markup and change control
US6889223B2 (en) Apparatus, method, and program for retrieving structured documents
CN103635897B (zh) 对运行页面进行动态更新的方法
US8566343B2 (en) Searching backward to speed up query
KR100638695B1 (ko) 구조화 문서의 데이터를 검색하는 장치 및 방법
US8584009B2 (en) Automatically propagating changes in document access rights for subordinate document components to superordinate document components
KR100995861B1 (ko) 온톨로지 스키마와 결합된 개체명 사전 및 마이닝 규칙을 이용한 용어의 개체명 결정모듈 및 방법
US20090019015A1 (en) Mathematical expression structured language object search system and search method
TW201415254A (zh) 語意標註建議方法及其系統
JP4247108B2 (ja) 構造化文書検索方法、構造化文書検索装置、及びプログラム
WO2008041367A1 (fr) Dispositif de recherche de document, procédé de recherche de document et programme de recherche de document
JP2005227851A (ja) 構造化データ記憶方法および装置
JP3832693B2 (ja) 構造化文書検索表示方法及び装置
US20070055679A1 (en) Data expansion method and data processing method for structured documents
CN100498771C (zh) 用于管理结构化文件的系统和方法
JP3914081B2 (ja) アクセス権限設定方法および構造化文書管理システム
CN108614821B (zh) 地质资料互联互查系统
JP5380874B2 (ja) 情報検索方法、プログラム及び装置
JP2002202973A (ja) 構造化文書管理装置
JP3709890B2 (ja) 文字列検索装置
JP4439497B2 (ja) 検索処理装置及びプログラム
JP4352840B2 (ja) プログラム、データ処理方法およびデータ処理システム
JP6589317B2 (ja) 書換装置、処理方法とそのプログラム、および、情報処理装置
JP3937944B2 (ja) 構造化文書からの情報抽出方法及び装置及び情報抽出プログラム及びコンピュータ読み取り可能な記録媒体

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 07827844

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 12442835

Country of ref document: US

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 07827844

Country of ref document: EP

Kind code of ref document: A1