JP4254511B2 - Tree structure data creation device and method - Google Patents

Description

  The present invention relates to an apparatus and a method for expressing a relation of a document group having a hyperlink structure in a tree structure.

  A document group on the WWW (World Wide Web) has a hypertext structure (also called a hyperlink structure) in which a document is a node and a link between documents is an arc. This hypertext structure has the advantage that any document can be easily linked by a link. However, since it is basically a network structure, when the number of documents increases and the relationship between documents becomes complicated, humans can create documents. It becomes difficult to grasp the relationship between them.

  On the other hand, a method of displaying the hypertext structure in a simplified tree structure is conventionally used. Patent Documents 1 to 3 disclose a system that displays a hypertext structure formed by a document group in a tree structure format in which a document is a node and a link is an edge.

  In addition, “GoLive”, a website management tool of Adobe Systems, Inc., when specifying a starting document on the WWW, examines the hypertext structure by following links in order from that document, and 1 in the hypertext structure. When a document is specified, it has a function of creating and displaying a tree structure having the document as a root node from the hypertext structure.

JP-A-2-282929 JP-A-4-321144 Japanese Patent Laid-Open No. 10-222415

  The contents of the documents on the website and the intranet are updated as needed, and as a result, the hypertext structure formed by the documents is updated. For this reason, in a system in which tree structure data created from a hypertext structure is stored in a storage device and a service is provided using the tree structure data, the tree structure data in the storage device is stored in order to cope with changes in the hypertext structure. Updates need to be performed accordingly.

  Such tree structure data update processing has a problem unless it is executed in one transaction. One reason for this is that update processing is started and completed, that is, until all documents that can be reached by sequentially following links from the document at the starting point of the tree structure are included in the tree structure data. This is because partial inconsistency appears in the contents of the tree structure data in the storage device. In other words, the updated data is registered in the storage device for the documents already incorporated in the tree structure when the processing is stopped, and the pre-update data remains in the storage device for the documents that are not incorporated in the tree structure at that time. . If such inconsistencies remain, correct information services cannot be performed.

  When tree-structured data created from a hypertext structure is stored in a storage device and used to provide document search and navigation (guidance) services, the tree-structured data includes the document data for each document. It is necessary to have a position on the tree structure, that is, path information from the root of the tree structure (that is, information indicating which document is reached from the root document through which the document is reached). When updating this tree structure data in response to a change in the hypertext structure link, if a part of the tree structure changes, it is necessary to rewrite the path information of all nodes (ie, documents) below the changed part. come. This rewriting is also required when there is no change in the parent-child relationship between the nodes below the changed portion. Therefore, when the size of the tree structure increases, the number of nodes that must be rewritten during one transaction increases.

  On the other hand, in general, when the scale of a document group for which a tree structure is to be created increases, the processing cost of conversion from a hypertext structure to a tree structure, for example, the amount of memory required as a work space for processing and the processing required Time will increase. Therefore, when the scale of a document group that is the subject of one transaction increases, the amount of processing increases as described above, and the cost required for the transaction increases. If a system for creating a tree structure is to be operated stably, it is desirable to keep the cost of one transaction below a certain level. Therefore, as described above, if the size of the tree structure increases, Problems come out.

  None of the prior arts including the above-mentioned patent documents consider such a problem.

  The present invention is directed to overcoming at least one of these prior art problems.

In one aspect of the present invention, an apparatus for creating integrated tree structure data representing a tree structure corresponding to a hypertext structure based on a hypertext structure formed by a group of documents included in a hierarchical directory structure. And means for dividing the document group into a plurality of clusters, the cluster dividing means for dividing the document group so that the number of documents included in each cluster is equal to or less than a predetermined upper limit, and a reference for each cluster. select the document, the reference document embedded in the lower tree structure data corresponding to the cluster, when going those said reference document Tsu sequentially Tado links of the hypertext structure starting from the link destination of the document is the the document of the landing only if it belongs to the cluster by incorporating a lower tree structure data corresponding to the cluster, the person the reference document and the root node A lower tree structure creating means for creating a lower tree structure data indicating a tree structure of documents in the cluster, integrated wood by integrating each of the lower tree structure data for each of the clusters created by the lower tree structure creating means There is provided a tree structure data creation device comprising integrated tree structure creation means for creating structure data.

  In a preferred aspect of the present invention, the tree structure data creation device creates upper tree structure data representing a hierarchical relationship between the reference documents based on position information of the reference documents in the directory structure. The integrated tree structure creating means creates integrated tree structure data by combining the upper tree structure data and the lower tree structure data.

  In another preferred aspect, the cluster dividing unit divides the document group into a plurality of clusters so that each cluster includes only documents belonging to a directory group below the highest directory to which the cluster belongs.

  In another preferred aspect, the cluster dividing unit obtains (a) a document group included in a directory group below the designated target directory as a first cluster, and (b) a document included in the first cluster. (C) If the number of documents obtained in step (b) exceeds a predetermined upper limit, the directory immediately under the target directory is selected as a new target directory, and the new target directory is selected. The document group included in the directory group below the directory is obtained as a second cluster, the document group included in the second cluster is deleted from the first cluster, and (d) the step obtained in step (c) Steps (b) and subsequent steps are recursively repeated with the second cluster as the new first cluster.

  Preferred embodiments of the present invention will be described below with reference to the drawings.

  FIG. 1 is a functional block diagram of an integrated tree structure data creation device according to the present invention. In this configuration, the link information collection unit 10 is a functional module for obtaining a hypertext structure of a web document group described in a hypertext description language such as HTML. The link information collection unit 10 obtains link relationship information (ie, hypertext structure) between web documents, for example, by following link descriptions in web documents on the Internet.

  In other words, the link information collection unit 10 analyzes the web document and detects an HTML link description such as an anchor tag (“<A HREF="... (character string indicating the link destination URL)”>”). When the link description is found, the document acquisition processing of the link destination URL indicated in the link description is executed. In this acquisition process, an acquisition request (such as a GET request) for requesting the document indicated by the link destination URL is issued. In response to this acquisition request, when the document can be acquired from the web server that manages the document of the URL related to the request, the link information collection unit 10 performs the above-described link description detection process and its link for the acquired document. Execute the previous acquisition process. The link information collection unit 10 starts the analysis from one or more web documents given as start points, and repeats the above-described link description detection processing and link destination acquisition processing so that the web documents and their links are obtained. Collect relationship information. This repetition is a “tour” of the web by the link information collection unit 10. The link information collection unit 10 stores the actual data of the web document acquired in the circulation process (that is, document data described in HTML) in a document storage device (not shown), and also detects the web detected in the circulation process. Information on links between documents is stored in the hypertext structure storage unit 12. The function of the link information collection unit 10 described so far is equivalent to an existing crawler or spider used by a robot search type search engine to collect web documents.

  By the cyclic processing by the link information collecting unit 10 as described above, the hypertext structure storage unit 12 stores the document table in which management information about the web document detected during the cyclic processing is registered, and the management of the detected link. A link table in which information is registered is formed. An example of the data contents of the document table is shown in FIG. 2, and an example of the data contents of the link table is shown in FIG. 2 and 3 represent a part of the hypertext structure formed by the documents 30-1, 2,..., 11,.

  In the document table, as shown in FIG. 2, for each detected web document, a unique document ID 102 assigned to the document and the URL 104 of the document (which may be a URI (Uniform Resource Identifier) excluding the protocol designation description) The title 106 of the document and the status information 108 indicating whether or not the document exists are registered. In the title 106, a title character string indicated by a <title> tag is registered in the header of the document. The item of the status information 108 is present for the following reason. That is, in the course of the cyclic processing of the link information collection unit 10, the web document is detected except for the web document given as the start point, except for the URL (or URI) indicated in the link description in the other web document. Because. However, it is possible that the web document does not actually exist in the URL (that is, the web document is not returned from the web server in response to the acquisition request). Therefore, when the document can be acquired from the URL of the link description, the status information 108 becomes “exist”, and otherwise “non-exist”. Note that the link information collection unit 10 may store each document acquired during the web tour in the integrated tree structure data creation apparatus. In this case, address information indicating a storage location of each document Is preferably added as a data item of each document in the document table.

  In the link table, as shown in FIG. 3, for each detected link, the document ID of the link source web document (link source ID 112) and the document ID of the link destination web document (link destination ID 114). Is registered. When the link information collection unit 10 detects a link description from a web document, the link information collection unit 10 adds one entry to the link table, and uses the document ID of the web document as the link source of the entry and indicates the web indicated by the URL of the link description. The document ID of the document is registered as a link destination.

  The link information collection unit 10 executes a link information collection process periodically or whenever a predetermined collection start condition is satisfied. A collection process end condition can be set for the link information collection unit 10, and after the collection is started, the collection unit 10 ends the collection process when the end condition is satisfied. The termination condition is, for example, a condition that collection is terminated when all documents that can be traced via a link are detected from one or more documents specified as a starting point of a link search. Note that the range for collecting link information can be limited (for example, limited to one or more domains registered in advance).

  The request processing unit 14 receives a request for creating an integrated tree structure data (a tree structure request) from a client apparatus connected to the integrated tree structure data creation apparatus via a data communication network such as a LAN (local area network) or the Internet. 200). The tree structure request 200 can include information for specifying the creation range of the integrated tree structure, that is, the location range of the document group to be incorporated into the integrated tree structure. As information for specifying the creation range, information (for example, URL) for identifying a document (called a start document) that is a starting point for creating a tree structure, a website domain name, a host name, or the like can be used. . In the case where the tree structure request 200 including the creation range information is received from the client device, the request processing unit 14 provides the client device with a web page for inputting information for specifying the creation range, for example. Information input to the page is received as a tree structure request 200. When receiving the tree structure request 200 from the client device, the request processing unit 14 instructs the integrated control unit 20 to create the integrated tree structure data 202. Here, the request processing unit 14 extracts information for specifying the creation range of the integrated tree structure from the tree structure request 200 and passes it to the integrated control unit 20. Note that the information for specifying the creation range of the integrated tree structure may be registered in the integrated tree structure data creation device for each user, for example. In this case, the tree structure request 200 does not require that information.

  The integrated control unit 20 controls the cluster dividing unit 16 and the tree structure data creating unit 17 to create the integrated tree structure data 202 in accordance with the command. At this time, the integration control unit 20 passes information for specifying the creation range of the integrated tree structure to the cluster division unit 16 and instructs cluster division of the creation range. Details of this creation process will be described later. The request processing unit 14 receives the integrated tree structure data 202 created by the integrated control unit 20 and provides it to the requesting client device.

  The cluster dividing unit 16 divides a web document group existing in the creation range into a plurality of clusters based on information specifying the creation range of the integrated tree structure. Details of the cluster division processing will be described in detail later.

  The tree structure data creation unit 17 receives the result of the cluster division processing by the cluster division unit 16 and creates a lower tree structure for each cluster and an upper tree structure that integrates these lower tree structures. Details of this creation process will be described later. The data of the created lower tree structure and upper tree structure is stored in the tree structure data storage unit 18. The data of the lower tree structure and the upper tree structure are integrated by the integrated control unit 20 to become integrated tree structure data 202.

  FIG. 5 is a flowchart showing an overall processing procedure of the integrated tree structure data creation device. In this procedure, the request processing unit 14 receives the tree structure request 200 from the client device, and specifies the creation range of the integrated tree structure corresponding to the request (S10). If information on the creation range is included in the tree structure request 200, it can be specified by extracting it. If the information on the creation range of each user is registered in the device, the tree structure request 200 is issued. The creation range can be specified by extracting the registration information corresponding to the original user. When a domain name or a web server host name is specified as information for specifying the creation range, a document group in the domain or web server is the creation range. If the storage location information of the start document is specified as the creation range information, a directory group under the directory (or folder) where the start document is located (that is, a directory tree having the directory at the top belongs to the directory group). A document group belonging to the directory group) is a creation range. It is also possible to specify a plurality of domain names, host names, or starting documents as the creation range. When a plurality of start documents are designated, the union of creation ranges corresponding to the individual start documents is the overall creation range for the designation.

  Next, the cluster dividing unit 16 divides the creation range into a plurality of clusters (S12). A specific example of the cluster division processing will be described with reference to FIGS.

  FIG. 6 is a flowchart showing an example of specific processing contents of the cluster division processing. In this process, first, the highest directory in the creation range is selected as a target directory (S20), and the process proceeds to S22. The processes after S22 (enclosed by broken lines in the figure) are logically parallel processes in units of clusters.

  In S22, a document group included in a directory group in a hierarchy below the target directory (that is, a directory group belonging to a directory tree having the target directory as a vertex) is recognized as one cluster (S22). Since the hypertext structure storage unit 12 stores URLs of individual documents, such recognition can be performed by referring to the URLs. In this cluster recognition process, for example, a unique cluster ID is assigned to a cluster consisting of a directory group in a hierarchy below the target directory, and each document belonging to the directory in the cluster is associated with the cluster ID. As a method of association, for example, as shown in FIG. 7, for each document ID 122 of each document within the work range, a cluster management table that holds the cluster ID 124 of the cluster to which the document belongs is created.

  FIG. 7A shows the contents of the cluster management table when the highest directory in the work range is the target directory. In this case, the ID “C001” of the same top-level cluster is associated with all the documents in the work range.

  When a new cluster is recognized in this way, the document group belonging to the new cluster is deleted from the cluster to which the document group previously belonged (referred to as a parent cluster) (S24). As a result, the number of documents in the parent cluster is reduced by the number of documents in the newly recognized cluster. When the highest directory in the work range is the target directory, the first cluster is recognized in S22, and no higher cluster exists, so nothing is performed in S24.

  The above S22 and S24 are cluster configuration update processing. When the update of the cluster configuration is finished, the number of documents in the cluster newly recognized in S22 is counted (S26), and it is determined whether or not the value of the counting result is equal to or less than a predetermined upper limit value (S28). ). If the counted number of documents is equal to or less than the upper limit value, the process for the cluster is terminated.

  When it is determined in S28 that the number of documents in the counted cluster has exceeded the upper limit, each directory immediately below the target directory at that time is selected as a new target directory (S30), and for each new target directory, The processes from S22 to S30 are recursively executed. In this case, in the processes of S22 and S24 for the new directory of interest, a new unique cluster ID is assigned to the cluster of the directory of interest, and the cluster ID 124 of each document belonging to the directory below the directory of interest in the cluster management table. Is rewritten to the new cluster ID. FIG. 7B shows an example of data contents of the cluster management table after such rewriting has been performed. By such processing, a cluster having the number of documents exceeding the upper limit number is recursively divided into smaller clusters.

  The processing of FIG. 6 is described as follows according to a specific example. When the creation range is a directory tree as shown in FIG. 8, when the number of documents in the cluster composed of the directories (42 to 48) below the highest directory 40 exceeds the above upper limit (S28), Each directory 42 and 44 immediately below the directory 40 is selected as the next directory of interest (S30). Then, the directory tree 45 having the directory 42 as a vertex and the directory tree having the directory 44 as a vertex are respectively recognized as new clusters (S22), and these clusters are deleted from the cluster of the directory 40 which is a parent cluster. (S24). Thereby, the cluster of the directory 40 becomes a cluster composed only of documents directly under the directory 40. Documents in the descendant directory of the directory 40 belong to another cluster. If the number of documents in the cluster having the directory 44 as a vertex exceeds the upper limit, the cluster having the directories 46, 48,... Separated from.

  In the foregoing, the cluster division process for the hierarchy below one top directory has been described. When a plurality of different ranges are designated as the creation range of the integrated tree structure data, the above-described process may be performed for each range. For example, when a plurality of host names are designated, the above-described processing may be performed for each host. In addition, when a document in a different directory having no hierarchical relationship in the directory hierarchy is designated as the start document, the above-described processing may be performed with each of these directories as the top directory. In addition, when a document in a different directory having a hierarchical relationship in the directory hierarchy is designated as the start document, a cluster consisting of directories under the lower directory is defined as a directory under the upper directory in the same manner as described above. What is necessary is just to isolate | separate from the cluster which consists of a group.

  Returning to the description of FIG. When cluster division is completed in this way, the cluster division unit 16 selects one document from each of these clusters as a root node of the tree structure (S14). Here, when a start document is specified as information for specifying the creation range of the integrated tree structure, the start document is selected as a root node. For a cluster for which no starting document exists, a root node document is selected from the cluster according to a predetermined rule. In this case, it is preferable to select the root node from the documents in the top directory of the cluster. As a rule for selecting a root node from documents in the same directory, for example, a predetermined document name such as “index.htm” or “main.htm” (which is registered in advance in the apparatus) is used. If there is something you have, you can select it as the root node.

  When the document of the root node of each cluster is determined in this way, the tree structure data creation unit 17 creates a tree structure with the document as the root node for each of the documents (S16). In this process, the tree structure formed by the web document group is obtained by following the links registered in the link table of the hypertext structure storage unit 12 in the depth-first search or the breadth-first search in order from the document of the root node. Tree structure data indicating the tree structure is created. Various methods for creating a tree structure from a hyperlink structure have been proposed including the above-mentioned patent documents, and the tree structure data creating unit 17 may use those conventional methods. The tree structure data created by the tree structure data creation unit 17 is stored in the tree structure data storage unit 18.

  However, the tree structure creation processing of the tree structure data creation unit 17 is different from normal tree structure creation in that the documents to be incorporated into the tree structure are limited to the inside of the cluster. That is, the tree structure data creation unit 17 refers to the cluster to which the linked document belongs, for example, referring to the cluster management table in FIG. 7 when following the link of the link table starting from the document of the root node. The link destination document is incorporated into the tree structure being created only when it belongs to the same cluster as the root node document. A tree structure created with one root node as a starting point in this way is called a lower tree structure. The lower tree structure is one subtree of the integrated tree structure.

  Further, the tree structure data creation unit 17 creates an upper tree structure formed by each directory to which the document of the selected root node belongs (S16). In the process of creating the upper tree structure, first, for each root node document, the directory to which the document belongs is obtained from the URL of the document. The URL of a resource is composed of a combination of the protocol name ("http") for obtaining the resource, the name of the host device in which the resource is stored, and the path to the resource in the file system of the host device Is done. Therefore, if the file name indicated at the end of the path portion of the URL is deleted from the URL of the document of the root node, the remaining character string can be regarded as indicating a virtual directory to which the reference page belongs. Then, an upper tree structure is created on the basis of the hierarchical relationship on the directory hierarchical structure between the directories to which the documents of the respective root nodes belong. If the directory storing a document of a certain root node (assuming it is directory a) is a subordinate directory of the directory storing a document of another root node (assuming it is directory b), the upper tree structure The node corresponding to the directory a becomes a descendant node of the node corresponding to the directory b. Here, if the directory to which the document of each root node belongs does not have a directory located between the directory a and the directory b on the directory hierarchy, the directory a becomes a child node of the directory b in the upper tree structure. . As described above, the tree structure data creation unit 17 selects the directories in the directory tree structure (directory tree) in the directory tree in which the document of the root node of each cluster is stored, on the upper tree structure. Then, tie it with a parent-child relationship. By such processing, an upper tree structure is created. Note that this is only an example, and when there is another directory in the directory hierarchy between the directories in the immediate relationship, it is of course possible to incorporate the intervening directory in the upper tree structure. Good.

  When the host names of a plurality of sites are specified as the creation range, the hosts are in an equal relationship in the hierarchical structure, and therefore the upper tree structure can be individually created for each host in the above method. Therefore, in order to combine these into one upper tree structure, a method of providing a virtual uppermost node and connecting the upper tree structure for each host to the uppermost node is also possible.

  The data of the upper tree structure created in this way is also stored in the tree structure data storage unit 18.

  When each lower tree structure and upper tree structure are created in this way, the integrated control unit 20 combines the data of the upper tree structure and the plurality of lower tree structures stored in the tree structure data storage unit 18. The integrated tree structure data 202 indicating the entire tree structure corresponding to the tree structure request 200 is created.

  In this integration process, the root node of each lower tree structure is linked to the node of the upper tree structure. In other words, the root node of the lower tree structure corresponding to the document stored in the directory corresponding to the node is connected as a child node to the node of the upper tree structure.

  The created integrated tree structure data 202 is transmitted by the request processing unit 14 to the client device that is the transmission source of the tree structure request 200.

  An example of the integrated tree structure created in this way is shown in FIG. The example shown in FIG. 9 is an example when “ABCD company top page” in the hypertext structure of FIG. 4 is designated as the start document. More specifically, since there are more documents than the upper limit in the cluster consisting of the hierarchy below the directory “/abcd.co.jp/” to which the starting document belongs, the two directories “/abcd.co.jp” directly below the upper limit are included. This is an example when two clusters with vertices / product / "and" /abcd.co.jp/download/ "are separated (the number of documents in the two separated clusters is less than the upper limit value) To do).

  In the example of FIG. 9, the top directory 50-1 ("/abcd.co.jp/"), 50-2 ("/abcd.co.jp/product/") and 50-3 ("/" abcd.co.jp/download/ ") constitutes the upper tree structure. For example, since the directory “/abcd.co.jp/product/” is directly below the directory “/abcd.co.jp/”, the child of the directory 50-1 is the directory 50-2 in the upper tree structure. It has become.

  In the example of FIG. 9, the integrated tree structure includes an ABCD company top page 56-1 which is a start document, a product page 56-2 selected from each separated cluster, and a download page 56 as a lower tree structure group. Included are subtrees 55-1, 55-2 and 55-3, each having −6 as a root node. The merchandise page 56-2 and the download page 56-6 are selected as root nodes because they are in the top directory of the separated clusters and are documents named “index.html”.

  In the tree structure of FIG. 9, the root nodes 56-1, 2 and 6 of the lower tree structure 55-1, 2 and 3 are children respectively for the nodes 50-1, 2, and 3 of the upper tree structure. Connected as a node.

  In the example of FIG. 9, one root node of the lower tree structure is connected to one node of the upper tree structure, but this is only an example. Processing such as selecting multiple documents from the same cluster as the root node is also possible. When such processing is adopted, each subtree structure starting from each root node is created, and each root node is the top node. It will be connected to nodes in the same directory of the tree structure.

  As described above, in this embodiment, the creation range of the integrated tree structure is divided into a plurality of clusters according to the directory structure, and a lower tree structure made up of documents in each cluster is created. Then, an integrated tree structure is created by connecting the lower tree structure of each cluster to the upper tree structure showing the hierarchical relationship on the directory structure of the top directory of each cluster.

  In the present embodiment, since the lower tree structure is created for each cluster as described above, the classification is conceptually easier to understand than the tree structure created by the conventional method. This is for the following reason.

  First, in general, when a web designer designs a website, rather than saving a file describing individual documents (web pages) in a random place (directory) in terms of data management efficiency, It is more likely to create a conceptually organized directory structure and store each document file in the appropriate directory within that directory structure. In an ideal case, the hierarchical structure of the directory group in which the document group is stored represents a hierarchical concept classification formed by the document group. In reality, this is not necessarily the ideal directory structure, but if you consider the efficiency of the subsequent data management, the directory structure more or less reflects the concept classification of the document group. . On the other hand, in the integrated tree structure data creation device according to the present embodiment, one cluster is composed of a directory and a directory group having a lower hierarchy, and one lower tree structure is composed only of documents belonging to one cluster. Is done. Accordingly, in each sub-tree structure, only the directory to which the document of the root node belongs, or the document that belongs to the directory group under this directory appears below the root node (descendant). Therefore, each lower tree structure can be regarded as a subtree corresponding to the concept classification corresponding to the directory to which the document of each root node belongs.

  In this way, in the integrated tree structure created by the apparatus of the present embodiment, each lower tree structure 55 is divided into concepts, so that the user can easily find a desired web page on the integrated tree structure. For example, since the “product C page” in the hypertext structure of FIG. 4 has a link from “ABCD company top page”, a child node of “ABCD company top page” in the tree structure created by the conventional method. In the integrated tree structure of FIG. 9 created according to the present embodiment, it is a child node 56-5 of the “product page” 56-2.

  If the client device that has received the integrated tree structure data 202 displays the integrated tree structure of FIG. 9 on the navigation screen of the browser, at least in the upper tree structure part, nodes in the directory group having the same concept level exist in the same hierarchy. Indicated. In addition, the root node of the lower tree structure is linked to the node of the upper tree structure, and the upper tree structure is determined by a directory structure (that is, a URL hierarchical structure) that is harder to change than a hypertext structure link. The position of the root node in the structure is difficult to change. Further, each lower tree structure 55 extending from the upper tree structure node includes nodes of document groups belonging to the same directory, and thus the same concept classification. In addition, the link described in the document changes variously due to the update, but it is considered that the storage location of the document file itself is less likely to change compared to the link, so the integrated tree structure in FIG. It can be said that the position of a node indicating an individual document is less likely to change compared to the tree structure. For this reason, if this integrated tree structure is used, the user can easily search for a desired document.

  In the above example, only the nodes of the documents in the same cluster appear in the lower tree structure, but this cannot express a link between documents across the clusters. As a modified example for expressing such a link across clusters, there is a method of incorporating a link destination document outside the cluster into a lower tree structure as a reference node having a different node type from the document in the cluster. In this modification, when creating a lower tree structure of a cluster, documents in the cluster are incorporated into the lower tree structure as real nodes. On the other hand, when a link from a real node document to a document belonging to another cluster is detected, the link destination document is incorporated into the lower tree structure as a reference node. The link destination document is further searched for the real node, but the link beyond the node is not searched for the reference node. That is, the reference node only appears as a leaf. By incorporating a link destination outside the cluster as a reference node in this way, it is possible to express a link relationship across clusters while basically satisfying the principle of creating a subtree structure from documents in the cluster. . As can be seen from the above description, in the integrated tree structure creation procedure of the present embodiment, each document is a real node only once in the subordinate tree structure corresponding to the cluster to which the document belongs in the integrated tree structure. It appears as a reference node even if it appears in other subtree structures.

  Next, FIG. 10 shows data contents of the integrated tree structure data indicating the integrated tree structure. This integrated tree structure data corresponds to the hypertext structure shown in FIG. 4, and is an integrated tree structure data obtained by adding a reference node indicating a link destination document outside the cluster to the integrated tree structure shown in FIG. Indicates.

  This data includes a node ID 302, a URL 304, display data 306, child node information 308, node type information 310, and a tree structure path 312 for each node constituting the integrated tree structure. Among these, nodes S001, S002, and S003 are nodes of the upper tree structure, and the remaining nodes I001 and below are nodes of the lower tree structure. The node ID 302 is identification information uniquely assigned to each node. It is preferable that the node ID 302 can identify whether the node has an upper tree structure or a lower tree structure based on the value. Of course, this is not necessary if identification information indicating whether the node belongs to the upper tree structure or the lower tree structure is added separately for each node. URL 304 is a URL indicating the location of the document corresponding to the node. The display data 306 is display data used when the node is displayed by a browser or the like. In the case of a document node, the title of the document (title 106 in FIG. 2) can be used. In the case of a node having an upper tree structure, the URL of the directory corresponding to the node can be used as display data. The child node information 308 is a list of node IDs of child nodes possessed by the node. The node type information 310 is identification information indicating whether the node is a real node or a reference node. In the example of FIG. 10, nodes I012 and I013 are reference nodes. Incidentally, the reference node I013 indicates the same document as the real node I008. The tree structure path 312 is information indicating a path in the integrated tree structure from the root node (node S001 in the example of FIG. 10) of the integrated tree structure to the node. In the illustrated example, the parent-child relationship of the integrated tree structure is traced from the root node, and the IDs of the nodes that pass until the node is reached are linked. The tree structure path 312 is a data item provided to execute a search process for a search condition for a position in an integrated tree structure, such as “node belonging to a hierarchy below the node I002”, for example.

  Such integrated tree structure data can be created as follows. That is, when the clustering of the creation range is finished and the root node document of each cluster is selected, the value of all data items for each node of the upper tree structure can be determined. Each data item of each node of the lower tree structure that is a descendant of each node of the upper tree structure can be obtained in the process of creating the tree structure by following the link relationship in the corresponding cluster. Such processing is conceptually equivalent to processing for integrating the upper tree structure and each lower tree structure.

  The configuration and processing contents of the integrated tree structure data creation device according to the present embodiment have been described above. The integrated tree structure data creation device of the present embodiment described above can be constructed using a general computer system. Typically, by installing a program describing the functions of the function modules 10, 14, 16, 17, 18, and 20 shown in FIG.

  In the apparatus of the present embodiment described above, each lower tree structure in the integrated tree structure basically includes only the documents in the corresponding cluster. Here, according to the above-described cluster division processing, except in a special case where the number of documents directly under one directory exceeds the upper limit value, the document group in the creation range is divided into clusters each having a document number equal to or less than the upper limit value. Will be.

  For this reason, even if the link relationship of the hypertext structure changes due to a document update, etc., the lower tree structure of the cluster that includes the node related to the changed link is affected by the change in the integrated tree structure. Limited to only. This is because in the creation of the integrated tree structure of this embodiment, the lower tree structure is created in units of clusters, so even if the link related to a certain real node changes, that node is not included in the lower tree structure of another cluster. This is because it does not appear as a real node. As described above, this embodiment has an advantage that the range affected by the link change can be limited to the individual lower tree structure.

  In the present embodiment, the number of documents in the cluster is equal to or less than a predetermined upper limit except for the cluster corresponding to the special case described above, so the data content corresponds to the change of one link in the integrated tree structure data. The number of nodes that need to be changed is at most the above-described upper limit value, except for the above-mentioned special cases. For example, in the integrated tree structure data of FIG. 10, all the data contents of the tree structure path 312 must be updated for the node whose parent node has changed in accordance with the link change and its descendants. The number of target nodes is basically less than or equal to the above upper limit value. Even in a configuration in which a reference node is added to the integrated tree structure, since the reference node has no descendants, the data content update target does not increase explosively. For this reason, according to the present embodiment, the cost of the change process of the integrated tree structure data according to the change of one link can be limited to the value according to the above upper limit value. It is possible to contribute to stable operation of a system for creating and updating tree structure data.

  In the above example, even if the number of documents directly under one directory exceeds the upper limit, that directory is defined as one cluster. However, it is of course possible to divide such a directory into a plurality of clusters instead so that the number of documents in all the clusters is less than or equal to the upper limit value. In this case, instead of simply dividing at random, by defining a division rule and performing division according to the rule, the cluster can be divided in the same manner no matter how many times the division is performed.

  In the above example, when it is found that the number of documents in a cluster exceeds the upper limit value, all directories are selected as directories of interest directly under the top directory of the cluster (S30 in FIG. 6). The invention is not limited to such a processing procedure. For example, if one or more target directories are selected, one or more clusters having the target directory as a vertex are separated from the original cluster, and if the number of documents in the original cluster still exceeds the upper limit, an additional 1 It is also possible to perform a procedure of selecting clusters of interest and separating the clusters one by one.

  In the above example, one document is selected as a root node from each cluster, but it is of course possible to select a plurality of documents.

  In the above example, an upper tree structure is created with the directory to which the root node of each cluster belongs as a node, and an integrated tree structure is created by connecting each lower tree structure to the upper tree structure. It is not limited to such an embodiment. For example, a configuration in which an integrated tree structure is created by connecting the root nodes of each lower tree structure as a child of one common root node is also within the scope of the present invention.

  In the above, an example in which the integrated tree structure data creation device is configured as a server device that creates and provides integrated tree structure data in response to a request from a client device has been shown. An apparatus configuration provided with a display processing unit for displaying an integrated tree structure based on the generated integrated tree structure data is also included in the scope of the present invention.

It is a functional block diagram which shows the structure of the integrated tree structure data creation apparatus which concerns on this invention. It is a figure which shows an example of a document table. It is a figure which shows an example of a link table. It is a figure which shows an example of a hypertext structure. It is a flowchart which shows the whole process sequence of an integrated tree structure data preparation apparatus. It is a flowchart which shows the process sequence of a cluster division part. It is a figure for demonstrating a cluster management table. It is a figure which shows the specific example of the directory tree divided into clusters. It is a figure which shows an example of an integrated tree structure. It is a figure which shows an example of integrated tree structure data.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 10 Link information collection part, 12 Hypertext structure storage part, 14 Request processing part, 16 Cluster division part, 17 Tree structure data creation part, 18 Tree structure data storage part, 20 Integrated control part.

Claims (11)

An apparatus for creating integrated tree structure data representing a tree structure corresponding to a hypertext structure based on a hypertext structure formed by a group of documents included in a hierarchical directory structure,
Means for dividing the document group into a plurality of clusters, wherein the number of documents included in each cluster is divided so as to be equal to or less than a predetermined upper limit value; and
For each of the clusters, select the reference document, when the reference document embedded in the lower tree structure data corresponding to the cluster, go to those the reference document starting from the Tsu sequentially Tado hypertext links structure, the document of the destination only when the link destination document belongs to the cluster by incorporating a lower tree structure data corresponding to the cluster, the documents in the cluster that the person the reference document and a root node tree Subtree structure creation means for creating subtree structure data indicating
Integrated tree structure creating means for creating integrated tree structure data by integrating the respective lower tree structure data for each cluster created by the lower tree structure creating means;
A tree structure data creation device comprising: Upper tree structure creation means for creating upper tree structure data representing a hierarchical relationship between the reference documents based on position information of the reference documents in the directory structure;
The integrated tree structure creation means creates integrated tree structure data by combining the upper tree structure data and the lower tree structure data.
The tree structure data creation device according to claim 1. The cluster dividing unit divides the document group into a plurality of clusters so that each cluster includes only documents belonging to a directory group below the highest directory to which the cluster belongs.
The tree structure data creation device according to claim 1 or 2, characterized in that. The cluster dividing means includes
(A) obtaining a document group included in a directory group below the designated directory of interest as a first cluster;
(B) counting the number of documents contained in the first cluster;
(C) When the number of documents obtained in step (b) exceeds a predetermined upper limit, a directory immediately below the target directory is selected as a new target directory, and the directory group below the new target directory is selected. Determining the included document group as a second cluster, deleting the document group included in the second cluster from the first cluster,
(D) recursively repeating the steps after step (b) with the second cluster obtained in step (c) as a new first cluster;
The tree structure data creation device according to claim 1 or 2, characterized in that. Means for accepting designation of a starting document in the directory structure;
The cluster dividing unit executes processing with the directory including the start document as the directory of interest in the step (a),
The lower tree structure creation means selects the start document as a reference document for the cluster obtained in step (a).
5. The tree structure data creating apparatus according to claim 4, wherein In the process of sequentially following the hypertext structure link from the reference document of the cluster, the lower tree structure creation means detects the link from a document in the cluster to a document outside the cluster. A means for incorporating a link destination document indicated by the link into the lower tree structure data as a reference node having no child node;
The tree structure data creation device according to any one of claims 1 to 5, wherein An apparatus for creating integrated tree structure data representing a tree structure corresponding to a hypertext structure based on a hypertext structure formed by a group of documents included in a hierarchical directory structure,
Cluster dividing means for dividing the document group into a plurality of clusters;
For each of the clusters, select the reference document, when the reference document embedded in the lower tree structure data corresponding to the cluster, go to those the reference document starting from the Tsu sequentially Tado hypertext links structure, the document of the destination only when the link destination document belongs to the cluster by incorporating a lower tree structure data corresponding to the cluster, the documents in the cluster that the person the reference document and a root node tree Subtree structure creation means for creating subtree structure data indicating
Integrated tree structure creating means for creating integrated tree structure data by integrating the respective lower tree structure data for each cluster created by the lower tree structure creating means;
With
The cluster dividing means is
(A) obtaining a document group included in a directory group below the designated directory of interest as a first cluster;
(B) counting the number of documents contained in the first cluster;
(C) When the number of documents obtained in step (b) exceeds a predetermined upper limit, the directory immediately below the target directory is selected as a new target directory, and the directory group below the new target directory is selected. Determining the included document group as a second cluster, deleting the document group included in the second cluster from the first cluster,
(D) recursively repeating the steps after step (b) with the second cluster obtained in step (c) as a new first cluster;
Tree structure data creation device. A method for creating integrated tree structure data representing a tree structure corresponding to a hypertext structure based on a hypertext structure formed by a group of documents included in a hierarchical directory structure,
Cluster dividing means is means for dividing the document group into a plurality of clusters, and performs division so that the number of documents included in each cluster is equal to or less than a predetermined upper limit,
A lower tree structure creation means, for each of the clusters, select the reference document, the reference document embedded in the lower tree structure data corresponding to the cluster were a link of the hypertext structure equivalent to the reference document in the origin sequentially when going throat Tsu, by incorporating the documents of the destination only if the document destination belongs to the cluster to the lower tree structure data corresponding to the cluster, the cluster of those said reference document and a root node Create sub-tree data indicating the tree structure of the documents
An integrated tree structure creating means integrates each lower tree structure data for each cluster created by the lower tree structure creating means to create integrated tree structure data;
Tree structure data creation method. A method for creating integrated tree structure data representing a tree structure corresponding to a hypertext structure based on a hypertext structure formed by a group of documents included in a hierarchical directory structure,
A cluster dividing means for dividing the document group into a plurality of clusters;
A lower tree structure creation means, for each of the clusters, select the reference document, the reference document embedded in the lower tree structure data corresponding to the cluster were a link of the hypertext structure equivalent to the reference document in the origin sequentially when going throat Tsu, by incorporating the documents of the destination only if the document destination belongs to the cluster to the lower tree structure data corresponding to the cluster, the cluster of those said reference document and a root node A sub-tree structure creation step for creating sub-tree data indicating the tree structure of the documents in the document group;
An integration step of integrating tree structure data by integrating each lower tree structure data for each cluster created by the lower tree structure creation means;
Including
The cluster dividing step includes:
(A) obtaining a document group included in a directory group below the designated directory of interest as a first cluster;
(B) counting the number of documents contained in the first cluster;
(C) When the number of documents obtained in step (b) exceeds a predetermined upper limit, a directory immediately below the target directory is selected as a new target directory, and the directory group below the new target directory is selected. Determining the included document group as a second cluster, deleting the document group included in the second cluster from the first cluster,
(D) recursively repeating the steps after step (b) with the second cluster obtained in step (c) as a new first cluster;
A tree structure data creation method characterized by the above. A computer system is made to function as an apparatus for creating integrated tree structure data representing a tree structure corresponding to a hypertext structure based on a hypertext structure formed by a group of documents included in a hierarchical directory structure. A computer program comprising:
Means for dividing the document group into a plurality of clusters, wherein the number of documents included in each cluster is divided so as to be equal to or less than a predetermined upper limit value;
For each of the clusters, select the reference document, when the reference document embedded in the lower tree structure data corresponding to the cluster, go to those the reference document starting from the Tsu sequentially Tado hypertext links structure, the document of the destination only when the link destination document belongs to the cluster by incorporating a lower tree structure data corresponding to the cluster, the documents in the cluster that the person the reference document and a root node tree Subtree structure creation means for creating subtree data indicating
Integrated tree structure creation means for creating integrated tree structure data by integrating each lower tree structure data for each cluster created by the lower tree structure creation means;
Program to function as. To make a computer system function as an apparatus for creating integrated tree structure data representing a tree structure corresponding to a hypertext structure based on a hypertext structure formed by a group of documents included in a hierarchical directory structure A computer system comprising:
Cluster dividing means for dividing the document group into a plurality of clusters;
For each of the clusters, select the reference document, when the reference document embedded in the lower tree structure data corresponding to the cluster, go to those the reference document starting from the Tsu sequentially Tado hypertext links structure, the document of the destination only when the link destination document belongs to the cluster by incorporating a lower tree structure data corresponding to the cluster, the documents in the cluster that the person the reference document and a root node tree Subtree structure creation means for creating subtree data indicating
Integrated tree structure creation means for creating integrated tree structure data by integrating each lower tree structure data for each cluster created by the lower tree structure creation means;
Function as
The cluster dividing means is
(A) obtaining a document group included in a directory group below the designated directory of interest as a first cluster;
(B) counting the number of documents contained in the first cluster;
(C) When the number of documents obtained in step (b) exceeds a predetermined upper limit, a directory immediately below the target directory is selected as a new target directory, and the directory group below the new target directory is selected. Determining the included document group as a second cluster, deleting the document group included in the second cluster from the first cluster,
(D) recursively repeating the steps after step (b) with the second cluster obtained in step (c) as a new first cluster;
A program to perform processing including the steps.

Images