JP2014206828A - Data serialization device, data serialization method and data serialization program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To accelerate serialization processing of tree structure data.SOLUTION: A data serialization device 1 comprises: a weight determination section 104 for determining a weight based on a size of a partial tree for each partial tree with each node as a root node; a division section 105 for dividing tree structure data into a plurality of node strings each formed from one or more nodes in a continuous serialization order on the basis of the weight of each partial tree determined by the weight determination section 104; a thread allocation section 106 for allocating one thread to each of the plurality of node strings generated by the division by the division section 105; a serialization section 107 for serializing data corresponding to the nodes included in the node string into byte strings in the serialization order in parallel for each thread; a coupling section 108 for coupling serialization results for each of threads obtained by the serialization section 107 in the serialization order; and an output section 109 for outputting a serialization result coupled by the coupling section 108.

Description

  The present invention particularly relates to a data serialization device, a data serialization method, and a data serialization program for serializing tree structure data.

  In recent years, for example, open source software Hadoop has been widely used as a large-scale data processing platform for handling a huge amount of data called big data. In the processing of big data, in order to reduce the data size as much as possible, a method of storing data in binary format instead of text format is the mainstream. Therefore, in Hadoop, serializers / deserializers (Serializer / Deserializer) such as SequenceFile (see Non-Patent Document 1 below) and ProtocolBuffers (see Non-Patent Document 2 below) are used. A serializer is a technology that converts (serializes) data in the memory of a computer into a byte sequence for storage in storage such as HDD (Hard Disk Drive) and SSD (Solid State Drive) and transmission / reception on the network. It is. The deserializer is a technique for restoring original data from a byte sequence serialized by the serializer. SequenceFile, ProtocolBuffers, and the like serialize individual records (leaf nodes and intermediate nodes including root nodes) expressed as tree structure data into a binary byte string in TLV (Type-Length-Value) format.

Tom White, “Hadoop: The Definitive Guide”, O'Reilly Media, May 2009, p.111 Google, “ProtocolBuffers”, [online], Internet <URL: http://code.google.com/p/protobuf/>

  By the way, when the size of the original data to be serialized is large, the processing time required for serialization naturally becomes longer. In recent years, the number of CPU cores mounted on one computer has increased, and a program using a plurality of threads has been developed in order to effectively use the calculation resources. Therefore, it is considered that the processing can be speeded up by parallelizing the serialization processing to the binary format with a plurality of threads. However, SequenceFile, ProtocolBuffers, and the like shown in Non-Patent Documents 1 and 2 are designed and implemented so as to operate with a single thread, and there is a problem that serialization processing cannot be performed in parallel with a plurality of threads.

  Accordingly, an object of the present invention is to provide a data serialization device, a data serialization method, and a data serialization program that can speed up the serialization processing of tree structure data.

  A data serialization apparatus according to the present invention includes a leaf node that holds a value, an intermediate node that holds a leaf node or another intermediate node as a child node, and a root node that is the only intermediate node that does not have a parent node; Is a data serialization device that serializes tree-structured data having a predetermined serialization order, and determines a weight based on the size of the subtree for each subtree having each node as a root node A dividing unit that divides the tree-structured data into a plurality of node sequences each including one or more nodes that are serialized in sequence based on the weight of each subtree determined by the weight determining unit; Thread allocation means for allocating one thread to each of a plurality of node sequences generated by the means, and each node included in the node sequence in parallel for each thread. Serializing means for serializing data to be byte-sequenced in serialization order, coupling means for combining serialized results for each thread obtained by the serializing means in serialization order, and serialization coupled by the coupling means Output means for outputting a result.

  The data serialization method according to the present invention includes a leaf node that holds a value, an intermediate node that holds a leaf node or another intermediate node as a child node, and a root node that is the only intermediate node that does not have a parent node; Is a data serialization method executed by a data serialization device that serializes tree-structured data in a predetermined serialization order, for each subtree having each node as a root node, the size of the subtree A weight determination step for determining a weight based on the length, and a plurality of node sequences each including one or more nodes in which the serialization order is continuous based on the weight of each subtree determined in the weight determination step A dividing step for dividing into two, and a thread assigning step for assigning one thread to each of a plurality of node sequences generated by dividing in the dividing step In parallel for each thread, a serialization step for serializing data corresponding to each node included in the node sequence into a byte sequence in the serialization order, and serialization results for each thread obtained in the serialization step are serialized A combining step for combining in a normalization order, and an output step for outputting the serialized result combined in the combining step.

  A data serialization program according to the present invention includes a leaf node that holds a value, an intermediate node that holds a leaf node or another intermediate node as a child node, and a root node that is the only intermediate node that does not have a parent node; A computer provided in a data serialization device for serializing tree-structured data having a predetermined serialization order is assigned a weight based on the size of the subtree for each subtree having each node as a root node. Weight determining means for determining, and dividing means for dividing the tree-structured data into a plurality of node sequences each consisting of one or more nodes in which the serialization order is continuous based on the weight of each subtree determined by the weight determining means A thread allocating unit that allocates one thread to each of a plurality of node sequences generated by the dividing unit, and a node in parallel for each thread. Serializing means for serializing data corresponding to each node included in the byte sequence in serialization order, combining means for combining serialized results for each thread obtained by the serializing means in serialization order, and combining It functions as an output means for outputting the serialized result combined by the means.

  According to such a form, the division boundary is determined based on the weight based on the size of each partial tree of the tree structure data, and an independent thread is assigned to each node string divided at the division boundary. As a result, serialization processing for each node sequence is executed in parallel in each thread, and finally the serialization results obtained for each thread are combined and output. In this way, the tree structure data serialization process is processed in parallel by a plurality of threads, so that the tree structure data serialization process can be speeded up.

  In the data serialization apparatus, the serialization means performs serialization after executing a predetermined compression process on overlapping subtree units indicating equivalent subtrees that appear multiple times in the tree-structured data, and the dividing means includes: The tree structure data may be divided so that the node included in the overlapping subtree and the node immediately before the node in the serialization order are not divided.

  Examples of the compression processing in units of overlapping subtrees include lexicographic compression and run-length-encoding (RLE). When serialization processing is executed in combination with such compression processing, if multiple overlapping subtrees that are subject to continuous length compression are assigned to different threads, each thread performs processing independently. Compression may not be performed properly. In addition, when multiple nodes included in the same overlapping subtree to be lexicographically compressed are assigned to different threads, there is a problem that data inconsistency occurs due to inconsistent processing between one thread and the other thread. There is a risk of being aroused. In the above data serialization device, the dividing means avoids the above-mentioned problem by dividing the tree structure data so as not to divide the node included in the overlapping subtree and the node immediately before the node in the serialization order. can do.

  In the data serialization apparatus, the serialization means stores a dictionary table in which data and codes corresponding to overlapping subtrees are stored in association with each other as one of the compression processes included in the predetermined compression process. Lexical compression that replaces the data corresponding to the overlapping subtree with a code based on the root node of the subtree for which the lexicographic compression is executed by the serializing unit, and the root node in the serialization order The tree structure data may be divided by allowing the node immediately before the node to be divided.

  Even if the tree-structured data is divided at a position immediately before the root node of the subtree to be subjected to lexicographic compression, the above-described problem in the compression processing does not occur. Therefore, according to the data serialization apparatus, by allowing the division at such a position, the division position of the tree structure data can be determined more flexibly.

  In the data serialization apparatus, the weight determining unit may be configured to make the weight of the overlapping subtree for which the predetermined compression process is executed smaller than when the predetermined compression process is not executed.

  When compression processing is performed on overlapping subtrees in the serialization processing, the code is replaced with a predetermined code, symbol, or the like in units of overlapping subtrees. That is, since the serialization processing for the overlapping subtree to be subjected to compression processing is substantially performed only on the root node of the overlapping subtree, the processing amount is compared with the case where the compression processing is not performed. Is expected to decrease. Therefore, according to the data serialization apparatus, it is possible to determine a more appropriate weight according to the actual processing amount in the serialization for the overlapping subtree to be subjected to the predetermined compression process.

  In the data serialization apparatus, the dividing unit divides the tree structure data so that the weight for each node sequence determined based on the weight of each subtree determined by the weight determining unit is equalized between the node sequences. It is good also as a structure.

  According to the above-described data serialization apparatus, the processing amount allocated to each thread can be equalized by dividing the tree structure data so as to equalize the weight for each node sequence allocated to each thread by the dividing unit. As a result, it is possible to avoid the processing load being biased toward a specific thread, and to shorten the time until the processing of all threads is completed.

  In the above data serialization apparatus, the dividing means reduces the tree structure data so that the weight for each node string determined based on the weight of each subtree determined by the weight determining means becomes smaller as the node string has a smaller serialization order. It is good also as a structure to divide | segment.

  For example, as a method of combining serialization results, serialization results obtained for each thread are input, serialized after sequentially executing predetermined processing (for example, compression processing) on the input serialization results. It is conceivable to combine the results. In such a case, for example, before the predetermined process for the serialization result of a part of the tree structure data is completed, the serialization process for the next part combined with the part of the tree structure data is completed. If this happens, a predetermined processing time for the next portion cannot be started immediately, and a processing waiting time occurs. According to the above data serialization device, the node sequence located in front of the tree structure data is divided by dividing the tree structure data so that the processing amount (weight) becomes smaller as the node sequence in the serialization order of the tree structure data becomes smaller. The serialization process for is completed before the node sequence located behind. Thereby, in the whole process, a serialization process and a predetermined process can be partially executed in parallel, and the whole process efficiency can be improved.

  In the data serialization apparatus, the combining means inputs the serialization results for each thread one by one in the serialization order, executes a predetermined data compression process, and then combines the serialization results for each thread. Also good.

  As a method of combining serialized results obtained for each thread, in addition to simply combining them, for example, after executing conventional data compression processing such as ZIP compression sequentially from the serialized result of the front part There are ways to combine them. According to the above data serialization apparatus, the tree structure data is divided so that the processing amount (weight) becomes smaller as the part of the tree structure data in the serialization order becomes smaller, so that the tree structure data is serialized first from the front part. Processing can be completed. Thereby, in the whole process, a serialization process and a predetermined data compression process can be partially executed in parallel, and the whole processing efficiency can be improved.

  According to the present invention, it is possible to speed up the serialization processing of tree structure data.

It is a block diagram which shows the function structure of the data serialization apparatus which concerns on one Embodiment of this invention. It is a figure which shows the hardware constitutions of a data serialization apparatus. It is a figure which shows the example of tree structure data. It is a figure which shows the serialization result when the tree structure data shown in FIG. 3 are serialized by a single thread. It is a figure which shows the example of the division | segmentation boundary in the case of dividing | segmenting the tree-structure data shown in FIG. 3 into three node rows. FIG. 6 is a diagram showing a serialization result when the tree structure data shown in FIG. 3 is serialized for each thread divided at the division boundary shown in FIG. 5. FIG. 4 is a diagram showing a serialization result when the tree structure data shown in FIG. 3 is serialized after lexicographic compression and continuous length compression with a single thread. FIG. 6 is a diagram showing a serialization result when the tree structure data shown in FIG. 3 is serialized after lexicographic compression and continuous length compression for each of the threads divided at the division boundary shown in FIG. 5. It is a figure which shows the example of the division | segmentation boundary in the case of dividing | segmenting the tree structure data shown in FIG. 3 considering lexicographic compression and continuous length compression. FIG. 10 is a diagram showing a serialization result when the tree structure data shown in FIG. 3 is serialized after lexicographic compression and continuous length compression for each thread divided at the division boundary shown in FIG. 9. It is a figure which shows the example of the division | segmentation boundary determined so that load might be equal between each thread | sled. FIG. 12 is a diagram illustrating a serialization result when the tree structure data illustrated in FIG. 3 is serialized after being lexicographically compressed and run-length-compressed for each thread divided at the division boundary illustrated in FIG. 11. It is a figure for demonstrating the effect by giving the inclination to the load between threads. It is a flowchart which shows operation | movement of a data serialization apparatus. It is a flowchart which shows the division | segmentation process including the process which determines the division | segmentation boundary shown in FIG. It is a figure which shows the function structure of the data serialization program which concerns on embodiment.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings. In the description of the drawings, the same or equivalent elements are denoted by the same reference numerals, and redundant description is omitted.

  FIG. 1 is a block diagram showing a functional configuration of a data serialization apparatus according to an embodiment of the present invention. As shown in FIG. 1, the data serialization apparatus 1 according to the present embodiment includes a tree structure construction unit 101, an overlapping subtree detection unit 102, a dictionary table generation unit 103, a weight determination unit 104, a division unit 105, and a thread allocation unit. 106, a serialization unit 107, a coupling unit 108, and an output unit 109.

  FIG. 2 is a diagram illustrating a hardware configuration of the data serialization device 1. As shown in FIG. 2, the data serialization apparatus 1 includes a CPU 11 that executes an operating system, application programs, and the like, a main storage unit 12 that includes a ROM and a RAM, and an auxiliary storage unit 13 that includes a hard disk memory and the like. A communication control unit 14 that performs data communication, an output unit 15 including a liquid crystal monitor, an operation unit 16 including a keyboard and a mouse as input devices, and a recording medium such as a CD-ROM and a DVD And a recording medium reading unit 17 that reads 18.

  Each function of the data serialization apparatus 1 shown in FIG. 1 is realized by reading and executing a predetermined software program in the main storage unit 12 under the control of the CPU 11. At that time, the CPU 11 controls the operations of the operation unit 16, the output unit 15, and the communication control unit 14 by controlling the data reading and writing operations in the main storage unit 12 and the auxiliary storage unit 13 according to the processing procedure of the software program. .

  Returning to FIG. 1, each functional element constituting the data serialization device 1 will be described.

  The tree structure construction unit 101 is a functional element that constructs tree structure data that is a target for executing serialization processing by the data serialization device 1. For example, for data having an object structure, the tree structure construction unit 101 constructs the tree structure data as shown in FIG. 3 so that each object corresponds to each node in the tree structure.

  As shown in FIG. 3, the tree structure data includes leaf nodes (“123”, “456”, “9.87”, “6.54”, “hoge”, “foo”) that hold values, It consists of an intermediate node that holds a node or other intermediate node as a child node (“intermediate”), a root node that is the only intermediate node that does not have a parent node (“root”), and an edge that connects each node It is a data structure. There are several methods for implementing tree-structured data, such as a method in which each node holds a pointer to a child node and a method in which each node holds a pointer to a parent node. It is not limited to any of the methods.

  In the present specification, the “subtree” means a tree composed only of elements (nodes and edges) below an arbitrary node in the tree structure data. That is, the partial tree means a tree having the arbitrary node as a root node. In addition, a subtree (equivalent subtree) that appears multiple times in the same tree structure data and whose positions, types, and values of nodes under the root node of the subtree completely match each other is referred to as an “overlapping subtree” Is also called).

  In FIG. 3, the numbers described at the upper left of each node show an example of the serialization order of each node determined in accordance with conditions such as parent node priority, forward node priority, and depth priority. As shown in FIG. 3, this serialization order is an order in which a parent node is first in an arbitrary subtree, and a node positioned forward (left side) is first among child nodes. . Further, the number described at the upper right of each node indicates the number of nodes included in the subtree having the node as a root node.

  The overlapping subtree detection unit 102 is a functional element that detects an overlapping subtree included in the tree structure data. More specifically, the overlapping subtree detection unit 102 detects an overlapping subtree as follows, for example. In other words, the overlapping subtree detection unit 102 circulates the tree structure data constructed by the tree structure construction unit 101 in a predetermined circulation order such as a depth-first search, and the intermediate node at the circulation destination intermediate node Obtain subtree configuration information (information indicating the position, type, and value of a node included in the subtree) with the node as a root node. The overlapping subtree detection unit 102 detects subtrees having the same configuration information as overlapping subtrees by comparing the subtree configuration information acquired at each intermediate node. However, the above method is an example, and the method of detecting the overlapping subtree by the overlapping subtree detection unit 102 is not particularly limited. For example, the overlapping subtree detection unit 102 may detect an overlapping subtree using a method described in Japanese Patent Application No. 2012-164000.

  In the example of FIG. 3, a subtree whose root node is a node whose serialization order is 2 (hereinafter, “node whose serialization order is X” is simply referred to as “node X”) and node 18 is a root node. In the subtree, the positions, types, and values of the nodes under the root node are completely coincident with each other, forming an equivalent subtree. Similarly, the subtree having the node 8 as the root node and the subtree having the node 11 as the root node form an overlapping subtree equivalent to each other. The overlapping subtree detection unit 102 detects a pair of overlapping subtrees equivalent to each other included in the tree structure data.

  For each set of overlapping subtrees detected by the overlapping subtree detection unit 102, the dictionary table generation unit 103 is a code having a data length shorter than the data for the data corresponding to the overlapping subtree associated with the set. Is a functional element that generates a dictionary table associated with. In the example of FIG. 3, for example, the dictionary table generation unit 103 associates the code T1 with data corresponding to the subtree having the node 2 as the root node, and corresponds to the subtree having the node 8 as the root node. A dictionary table in which the code T2 is associated with the data is generated.

  The detection result of the overlapping subtree by the overlapping subtree detection unit 102 is obtained as a result of continuous length compression (RLE: Run-Length-) using redundancy in units of overlapping subtrees when the serializing unit 107 serializes the tree structure data. When performing (Encoding), it is referred to by the dividing unit 105 and the serializing unit 107. The dictionary table generated by the dictionary table generation unit 103 is divided into parts when the serialization unit 107 performs lexicographic compression using redundancy in units of overlapping subtrees when serializing tree structure data. 105 and serializer 107. The lexicographic compression is a compression process for reducing the data size by replacing data corresponding to the overlapping subtree with a code associated with the data in the dictionary table. Continuous length compression is a compression process that reduces the data size by expressing the data corresponding to overlapping subtrees that have the same root node and appear in succession by their continuous length (number of repetitions). It is.

  The weight determination unit 104 is a weight determination unit that determines a weight based on the size of the subtree for each subtree whose root node is each node in the tree structure data. The weight determination unit 104 associates the weight determined for the subtree having each node as the root node with the node as additional information about the node. The weight associated with each node is referred to when the dividing unit 105 divides the tree structure data.

  Although the weight determination method by the weight determination unit 104 is not particularly limited, the weight determination unit 104 determines, for example, the number of nodes included in the subtree as the weight of the subtree. At this time, the weight determining unit 104 may determine the weight of the subtree by setting one node to “1” regardless of the type of the node. For example, the weight for each node may be changed according to the type of the node. The weight of the subtree may be determined. For example, the weight determination unit 104 sets “4” for an integer type leaf node having a length of 4 bytes, “8” for a real type leaf node having an length of 8 bytes, and a string length for a leaf node of a character string type. The weight of the sub-tree may be determined after performing weighting such as “1” for intermediate nodes that do not store data of a proportional size or the above type (integer value, real value, character string). .

  For example, for the subtree having the node 4 in FIG. 3 as the root node, when the weight determination unit 104 determines the weight by the former method, the weight of the subtree is “3”. On the other hand, when the weight determination unit 104 determines the weight of the subtree by the latter method, the weight of the subtree is determined by each node (“intermediate”, “foo”, “123”) included in the subtree. ) Weighting (1, 3, 4) is added to “8”. In the present embodiment, description will be made assuming that the weight of the subtree is determined by the former method. Therefore, the numbers in the upper right of each node in FIG. 3 indicate the weights determined by the former method.

  The dividing unit 105 is a dividing unit that divides the tree structure data into a plurality of node sequences each including one or more nodes in which the serialization order is continuous based on the weight of each subtree determined by the weight determining unit 104. is there. For example, information indicating a division strategy that prescribes, for example, the number of divisions, the distribution method of the weight of each node sequence (the weight of the subtree included in each node sequence), and the like is read in advance.

  The dividing unit 105 divides the tree structure data based on information indicating a division strategy read in advance. Any method may be used in which information indicating the division strategy is read by the division unit 105. For example, the information indicating the division strategy may be hard-coded in a program that executes the division process by the division unit 105, or may be input to the division unit 105 by an operator or the like when the division process is executed, A setting file in which information to be indicated is designated may be read by the dividing unit 105.

  The division strategy read by the dividing unit 105 is not particularly limited. For example, the dividing unit 105 sets the number of divisions to “3” and divides the node sequences so that the weights of the node sequences are equalized between the node sequences. Based on the above, the tree structure data can be divided. In the example of FIG. 3, since the total weight of the tree structure data (weight associated with the root node 1) is 28, the dividing unit 105 has, for example, a weight of “10”, “9”, “9” for each node sequence. The tree structure data is divided so that That is, the dividing unit 105 divides the tree structure data at the dividing boundaries D1 and D2 shown in FIG. Notation), a node string having a weight of 9 consisting of nodes 11 to 19 (hereinafter referred to as “node string 2”), and a node string having a weight of 9 consisting of nodes 20 to 28 (hereinafter referred to as “node string 3”). And split into

  The thread allocation unit 106 is a thread allocation unit that allocates one thread to each of a plurality of node sequences generated by the division unit 105. When the tree structure data is divided by the dividing unit 105 at the dividing boundaries D1 and D2 illustrated in FIG. 5, the thread allocating unit 106 has the thread 1 for the node string 1, the thread 2 for the node string 2, and the node A different thread is assigned to each node column, such as thread 3 for column 3. A thread refers to an execution unit that can execute processing independently and in parallel under the control of the CPU 11 of the data serialization device 1. Each thread includes a buffer that is a storage area for temporarily storing a processing result for each thread.

  The serialization unit 107 serializes the data corresponding to each node included in the node sequence in a serialized order into the byte sequence in parallel for each thread allocated to each of the plurality of node sequences by the thread allocation unit 106. It is the serialization means to make. In the serialization process in each thread, for example, the serialization unit 107 converts the data corresponding to each node included in the node string into a TLV format composed of three fields of type (Type), length (Length), and value (Value). Serialize with.

  First, serialization by the serialization unit 107 when lexicographic compression and continuous length compression in units of overlapping subtrees are not executed will be described. FIG. 4 is a diagram illustrating an example of a serialization result obtained by serializing the tree structure data illustrated in FIG. 3 in a TLV format using a single thread. The numbers described above the boxes in FIG. 4 indicate the start positions of the serialization results of the data corresponding to the nodes in the serialization order indicated by the numbers. In addition, the value in each box indicates each field value (type, length, value) in the TLV format.

  In the example of the serialization result shown in FIG. 4, the type of each node is “C” indicating an intermediate node, “I” indicating an integer type, “D” indicating a real number type, and “S” indicating a character string type. Either one is stored. In addition, as the length of each node, “the number of direct child nodes” is stored in the intermediate node, “character string length” is stored in the character string type, and the integer type of 4 bytes fixed length and the real number type of 8 bytes fixed length are stored. Since the node type and the node length are uniquely associated, they are omitted. In addition, as values of each node, values (integer value, real value, character string) corresponding to each type are stored in types other than the intermediate node, and are omitted in the intermediate node.

  For example, since node 1 (“root”) is an intermediate node and the number of direct child nodes is 4, the serialization result corresponding to the node is “C, 4”. Further, since the node 3 (“hoge”) is of a character string type and has a character string length of 4, the serialization result corresponding to the node is “S, 4, hoge”. Note that the processing itself in which the serialization unit 107 arranges information indicating the node type, length, value, and the like as described above and serializes the information in the TLV format is performed by any conventionally known method.

  The serialization result acquired for each thread by the parallel processing by the threads 1 to 3 assigned by the thread assignment unit 106 by the serialization unit 107 is shown in FIG. Such a serialization result for each thread is temporarily stored in a buffer included in each thread.

  The combining unit 108 is a combining unit that combines the serialized results for each thread obtained by the serializing unit 107 in the serialization order. The coupling unit 108 serializes the serialized results for each thread as shown in FIG. 6 (in this case, the serialized result of the thread 1 → the serialized result of the thread 2 → the order of the serialized result of the thread 3). In this way, one serialization result corresponding to the tree structure data before division as shown in FIG. 4 is obtained. Further, the combining unit 108 can execute various types of combining processes depending on the application. For example, the combining unit 108 does not simply combine the serialization results, but inputs the serialization results for each thread one by one in the serialization order, and performs data compression processing (predetermined data compression processing) such as ZIP compression. It may be combined with execution. Information specifically indicating the combining process to be executed in this way may be hard-coded in a program that executes the combining process by the combining unit 108, or may be input to the combining unit 108 by an operator or the like when the combining process is executed. Then, a setting file in which information indicating the combining process is designated in advance may be read by the combining unit 108. Details of the case where the combining unit 108 combines the serialized results while executing data compression processing such as ZIP compression will be described later.

  The output unit 109 is an output unit that outputs the serialization result combined by the combining unit 108. The output unit 109 outputs, for example, a predetermined server device (not shown) that uses the serialization result via a communication network, or a storage (not shown) for storing the serialization result for a certain period. Output processing such as output.

  As described above, according to the data serialization apparatus 1, the weight based on the size of each subtree of the tree structure data determined by the weight determination unit 104 (“the number of nodes included in the subtree” in the present embodiment). Based on the above, the dividing unit 105 determines the dividing boundaries D1 and D2. Subsequently, different threads 1 to 3 are assigned by the thread assignment unit 106 to the node rows 1 to 3 divided at the division boundaries D1 and D2. Thereby, the serialization unit 107 executes serialization processing for each node sequence in parallel in each thread. Finally, the serialization results obtained for each thread are combined by the combining unit 108, and the combined serialization result is output by the output unit 109. In this way, the tree structure data serialization process is processed in parallel by a plurality of threads, so that the tree structure data serialization process can be speeded up.

  Further, by dividing the tree structure data so that the weights for each node sequence assigned to each thread by the dividing unit 105 are equalized, the processing amount (number of nodes) assigned to each thread can be equalized. As a result, it is possible to avoid the processing load being biased toward a specific thread, and to shorten the time until the processing of all threads is completed.

  Next, the case where the serialization unit 107 executes serialization after performing lexicographic compression and continuous length compression for each overlapping subtree will be described.

  In this case, the serialization unit 107 refers to, for example, a dictionary table generated by the dictionary table generation unit 103 for a subtree having each node to be serialized as a root node, and lexicographically with respect to the subtree. It is determined whether or not compression can be performed. Also, the serialization unit 107 has, for example, a subtree whose root node is each node to be serialized, and the configuration of the subtree has a common parent node with the subtree and is positioned immediately before the subtree. By comparing with the configuration of the subtree, it is determined whether continuous length compression can be performed on the subtree. If the serialization unit 107 determines that these compression processes can be performed, the serialization unit 107 performs the serialization after executing the compression process on the corresponding subtree.

  More specifically, in the serialization to the TLV format, the serialization unit 107 includes a dictionary item indicating data contents to be replaced with codes by lexicographic compression, data corresponding to a subtree to be lexicographically compressed, and Compression processing is realized by using a special type for the data corresponding to the subtree to be subjected to continuous length compression.

  In this embodiment, as an example of serialization using lexicographic compression, data corresponding to a subtree that first appears in a set of overlapping subtrees equivalent to each other (in the example of FIG. 3, node 2 or node 8). For data that corresponds to a subtree having a root node as a root node), a code length marker indicating the code length of the code corresponding to the dictionary item is added to the serialization result without being replaced by the code and included in the serialization result Is adopted. In this system, a dictionary table can be created (restored) by extracting data corresponding to a code length marker and a dictionary item following the code length marker on the decoding side. Thereby, it is not necessary to include a dictionary table in the header portion of the data storing the serialization result, and the data size of the serialization result can be reduced accordingly (see Japanese Patent Application No. 2012-162700).

  Therefore, in this embodiment, a code length marker (denoted as “M”) is used as a type indicating a dictionary item. For the dictionary item, the length is omitted, and a value obtained by serializing the nodes included in the overlapping subtree in the TLV format is used. In addition, for data corresponding to a subtree that is a lexicographic compression target that appears after the second time in a pair of overlapping subtrees equivalent to each other, a code corresponding to the overlapping subtree is used as a type. The length and value are omitted. For the subtree to be subjected to continuous length compression, “R” indicating that it is to be subjected to continuous length compression is used as a model, the number of repetitions of the immediately preceding sibling subtree is the length, and the value is omitted.

  FIG. 7 is a diagram showing a serialization result when the serialization unit 107 serializes the tree structure data shown in FIG. 3 after executing lexicographic compression and continuous length compression with a single thread. As shown in FIG. 7, for example, “M” is used as a type for a dictionary item corresponding to a subtree having node 2 as a root node, the length is omitted, and nodes included in the subtree are serialized. The value (C, 2, S, 4, hoge, C, 2, S, 3, foo, I, 123) is the value.

  Further, all the nodes included in the subtrees to be lexicographically compressed (the subtree having the node 18 as a root node and the subtree having the node 23 as a root node) are associated with the codes “T1” and “T2”, respectively. Is replaced by In addition, all nodes included in the subtree (subtree having the node 11 as a root node) to be subjected to continuous length compression are replaced with “R, 1”. As described above, the serialization unit 107 serializes tree structure data without executing lexicographic compression and continuous length compression by serializing the tree structure data after performing lexicographic compression and continuous length compression. Compared to the case (see FIG. 4), the size of the serialization result can be shortened.

  Here, as an example of failure when serialization is performed after executing lexicographic compression and run length compression, the dividing unit 105 divides the tree structure data using the dividing boundaries D1 and D2 shown in FIG. A case where the thread allocation unit 106 allocates one thread to each node sequence, and the serialization unit 107 executes serialization after executing lexicographic compression and continuous length compression in parallel for each thread. explain. FIG. 8 shows the serialization result for each thread in this case. As shown in FIG. 8, the serialization processing in each thread (threads 1 to 3) for each node sequence divided using the division boundaries D1 and D2 as the division boundaries is not properly executed, resulting in data inconsistency. I understand that. Specifically, the following two problems have occurred.

  The first problem is that the partial length compression is not performed on the subtree whose root node is the node 11 to be subjected to the continuous length compression. This is because the mutually equivalent overlapping subtrees having the same root node and appearing in succession (the subtree having the node 8 as the root node and the subtree having the node 11 as the root node) are mutually different threads. This is because they are assigned to (thread 1 and thread 2). That is, the thread 2 cannot recognize that the subtree having the node 11 as the root node has the same configuration as the subtree having the node 8 assigned to the thread 1 as the root node. It is not running properly.

  The second problem is that nodes 18 and 19 are assigned to thread 2 and nodes 20 to 22 are assigned to thread 3 for nodes 18 to 22 included in a subtree whose root node is node 18 that is a lexicographic compression target. Data inconsistency is caused by being assigned to. This will be described in detail below.

  The overlapping subtree detection unit 102 detects that the subtree having the node 18 as a root node is an overlapping subtree corresponding to the subtree having the node 2 as a root node. Therefore, based on the detection result and the dictionary table generated by the dictionary table generation unit 103, the thread 2 uses the nodes 18 and 19 included in the subtree having the node 18 as a root node as the root node. Perform lexicographic compression to replace the code T1 corresponding to the subtree. Here, the code T1 is a code corresponding to a subtree having the node 2 as a root node, and indicates data corresponding to all the nodes 18 to 22. On the other hand, the thread 3 serializes the nodes 20 to 22 for each node without executing the lexicographic compression processing. Therefore, both the serialization result of the thread 2 and the serialization result of the thread 3 include a portion indicating data corresponding to the nodes 20 to 22, and there is a contradiction with the original data.

  Note that the above problem may be solved if the serializing unit 107 executes node check processing between threads, in which case independent parallel processing is performed for each thread. There is a problem in that the merit of improving the overall processing efficiency is impaired by the processing.

  Therefore, in order to avoid the above-described two problems when the serialization unit 107 performs serialization after performing compression processing such as lexicographic compression and run length compression, the data serialization device 1 includes the following: Execute the process. That is, the dividing unit 105 divides the tree structure data so as not to divide the node included in the overlapping subtree and the node immediately before the node in the serialization order. However, since the above-mentioned problem does not occur even if the root node of the subtree of the lexicographic compression target and the node immediately before the root node in the serialization order are divided, the dividing unit 105 performs the division in this way. May be acceptable.

  FIG. 9 shows examples of division boundaries (division boundaries D3 and D4) when the division unit 105 divides the tree structure data as described above. The dividing unit 105 divides the tree structure data at the division boundaries D3 and D4 shown in FIG. 9, thereby dividing the tree structure data into a node string composed of nodes 1 to 13 (hereinafter referred to as “node string 4”) and a node 14. To 22 (hereinafter referred to as “node string 5”) and a node string consisting of nodes 23 to 28 (hereinafter referred to as “node string 6”). Note that specific processing for the division unit 105 to determine the division boundaries D3 and D4 will be described together with the description of the flow of the data serialization device 1 described later.

  FIG. 10 is a diagram illustrating a serialization result when the tree structure data is serialized after lexicographic compression and continuous length compression for each of the threads divided by the division boundaries D3 and D4 shown in FIG. As shown in FIG. 10, in the thread 1 assigned to the node string 4, the subtree having the node 11 as the root node is subjected to continuous length compression. Further, in the thread 2 to which the node string 5 is assigned and the thread 3 to which the node string 6 is assigned, there is no duplication of nodes and no contradiction occurs in the data. That is, the above two problems do not occur.

  As described above, according to the data serialization apparatus 1, the dividing unit 105 divides the tree structure data so as not to divide the node included in the overlapping subtree and the node immediately before the node in the serialization order. The two problems described above can be avoided. In addition, the dividing unit 105 can determine the division position of the tree structure data more flexibly by allowing the division at the position immediately before the root node of the sub-tree to be subjected to lexicographic compression.

  However, in FIG. 10, the number of nodes to be serialized is not equalized between threads. That is, while thread 1 is serialized for 11 nodes, threads 2 and 3 are only serialized for 5 and 4 nodes, respectively. There is an imbalance in the number of nodes In order to complete the entire processing at a higher speed by parallel processing for each thread, it is more preferable that an almost equal number of nodes are allocated to all the threads.

  In the present embodiment, when lexicographic compression and continuous length compression are performed on overlapping subtrees in the serialization processing by the serialization unit 107, the second and subsequent times in the serialization order among mutually equivalent subtrees. The overlapping subtrees appearing in are replaced with predetermined codes and symbols or the like in units of the overlapping subtrees. That is, in the present embodiment, among the overlapping subtrees equivalent to each other, the overlapping subtree that appears in the second or later in the serialization order is an overlapping subtree to be subjected to compression processing (hereinafter referred to as “compression target overlapping subtree”). "). Here, since the serialization process for the compression target overlapping subtree is substantially performed only for the root node of the compression target overlapping subtree, the processing amount is reduced as compared with the case where the compression process is not performed. There is expected.

  Therefore, the weight determination unit 104 may determine the weight of the compression target overlapping subtree to a value smaller than that when the compression process is not executed. The weight determination unit 104 can specify the compression target overlapping subtree by referring to the detection result of the overlapping subtree detection unit 102, for example.

  One of the simplest weight determination methods for the compression target overlapping subtree by the weight determination unit 104 is to determine the weight as “1”. FIG. 11 shows the weight for each subtree determined by the weight determination unit 104 in this way. As shown in FIG. 11, the weight determination unit 104 sets the weight of the root node (node 11, node 18, node 23) of the compression target overlapping subtree to “1”. In addition, the weight determination unit 104 omits the determination of the weight for nodes other than the root node of the compression target overlapping subtree. This is because the serialization processing is not substantially executed for nodes other than the root node of the compression target overlapping subtree, and it is not necessary to associate a weight corresponding to the processing amount.

  According to such a weight determination method by the weight determination unit 104, the total weight of the tree structure data is 20. The dividing unit 105 allows, for example, dividing the root node of the subtree of the lexicographic compression target and the node immediately before the root node in the serialization order, and the nodes included in the overlapping subtree and the serial node in the serialization order. The tree structure data is divided so that the node immediately before the node is not divided and the weight for each node row is equalized between the node rows. That is, the dividing unit 105 divides the tree structure data at the dividing boundaries D5 and D6 shown in FIG. 11 so that the weights of the respective node strings are equal to “7”, “7”, and “6”. Divide the structure data.

  FIG. 12 is a diagram showing a serialization result when the tree structure data is serialized after lexicographic compression and continuous length compression for each thread divided at the division boundaries D5 and D6 shown in FIG. As shown in FIG. 12, the dividing unit 105 divides the tree-structured data at the dividing boundaries D5 and D6 based on the weights determined by the weight determining unit 104 as described above. The number of performed nodes is equalized compared to the case shown in FIG.

  As described above, according to the data serialization apparatus 1, it is possible to determine a more appropriate weight according to the processing amount for the compression target overlapping subtree. Then, the division unit 105 can divide the tree structure data so that the weight for each node sequence is equalized between the node sequences by using the result of such weighting. Thereby, the processing amount between threads can be equalized, and the overall processing time can be further shortened.

  Next, consider a case where the combining unit 108 inputs serialized results for each thread one by one in the serialization order, executes a predetermined data compression process, and then combines the serialized results for each thread. More specifically, the combining unit 108 executes data compression processing such as ZIP compression sequentially from the serialization result of the front portion of the serialization result obtained by the serialization processing in each thread by the serialization unit 107. Now consider the case of combining the serialized results for each thread.

  For example, there is a GZIPOutputStream object or the like in Java (registered trademark) as a technique for inputting partial byte sequences in order, outputting the result of combining the input byte sequences after ZIP compression. The combining unit 108, for example, inputs one serialized result for each thread to the GZIPOutputStream object, thereby obtaining one serialized result in which all the serialized results for each thread are combined after being ZIP compressed. can do. Here, the combining unit 108 does not need to combine the serialized results for each thread and then input the serialized results for each thread to the GZIPOutputStream object in order, instead of inputting them to the GZIPOutputStream object.

  In the present embodiment, consider a case where the combining unit 108 obtains one serialized result obtained by combining the serialized results for each thread after ZIP compression using the GZIPOutputStream object as described above.

  The ZIP compression processing by the GZIPOutputStream object is sequentially executed serially from the previously input byte string. Therefore, when the processing load for each thread is equalized, as shown in FIG. 13A, before the ZIP compression process (predetermined data compression process) for the serialized result of the thread 1 is completed, the thread 2 The serialization process may be completed. In this case, since the ZIP compression process for the serialized result of the thread 2 cannot be started immediately, a processing waiting time of “1” occurs. Similarly, a processing wait time of “2” occurs for the thread 3 as well. As shown in FIG. 13A, when the processing load between threads is equalized and the serialization processing time for each thread becomes equal to “3”, the ZIP compression processing for the serialization results of all threads is completed. It takes a total of “6” processing time. Here, the processing time required for the ZIP compression process is “1”.

  Therefore, the dividing unit 105 determines that the weight of each node sequence determined based on the weight of each subtree determined by the weight determining unit 104 is a node sequence with a younger serialization order (that is, a node sequence assigned to a thread with a lower number). The tree structure data may be divided so as to be smaller. In this case, as shown in FIG. 13B, the processing load of the serialization process decreases as the thread number becomes smaller, and the serialization process is completed earlier. Thereby, the serialization processing by the serialization unit 107 and the ZIP compression processing by the combining unit 108 are partially executed in parallel. As shown in FIG. 13B, when the processing load between threads is inclined and the serialization processing times of the threads 1 to 3 are “2”, “3”, and “4”, respectively, The processing time until the ZIP compression processing for the serialized result of the thread is completed can be shortened to “5”.

  As described above, the dividing unit 105 divides the tree-structured data so as to incline the processing load between threads, so that serialization processing and ZIP compression processing are partially performed in parallel in the overall processing. It can be executed, and the overall processing efficiency can be improved.

  Next, the operation of the data serialization apparatus 1 (including the data serialization method according to the present embodiment) will be described using FIG. 14 and FIG. FIG. 14 is a flowchart showing the operation of the data serializer. FIG. 15 is a flowchart showing a dividing process including a process in which the dividing unit 105 determines the dividing boundaries D3 and D4 shown in FIG.

  First, tree structure data is constructed by the tree structure construction unit 101 (step S101). Subsequently, an overlapping subtree included in the tree structure data is detected by the overlapping subtree detection unit 102 (step S102), and data corresponding to the overlapping subtree detected by the overlapping subtree detection unit 102 is associated with a code. The dictionary table is generated by the dictionary table generation unit 103 (step S103).

  Subsequently, the weight determination unit 104 determines a weight based on the size of the subtree for each subtree having each node as a root node (step S104, weight determination step). When serialization by the serialization unit 107 is performed together with lexicographic compression and run length compression, in step S104, the weight determination unit 104 determines that the overlapping subtree to be subjected to these compression processes is executed. The weight may be made smaller than when these compression processes are not executed.

  Subsequently, based on the weight of each subtree determined by the weight determination unit 104, a division process for dividing the tree structure data into a plurality of node sequences each including one or more nodes in which the serialization order is continuous is performed by the division unit. (Step S105, division step).

  With reference to FIG. 15, a description will be given of a process in which the dividing unit 105 determines the division boundaries D3 and D4 shown in FIG. 9 and divides the tree structure data at the division boundaries D3 and D4.

  First, the dividing unit 105 provisionally determines a division boundary candidate (step S201). Here, as an example, the division boundaries D1 and D2 shown in FIG. 5 are provisionally determined as division boundary candidates. Subsequently, the dividing unit 105 selects the foremost candidate (division boundary D1) among the undetermined division boundary candidates (division boundaries D1 and D2) (step S202). Subsequently, the dividing unit 105 determines whether there is a determined division boundary (step S203). Here, since there is no confirmed division boundary (step S203: NO), the division unit 105 extracts the ancestor series of the node 11 (candidate node) immediately after the division boundary D1 selected in step S202 (step S206). .

  An ancestor series represents a connection relationship from a node 1 that is a root node of tree-structured data to a node 11 that is a candidate node in a series of serialization order. However, the entire tree having the node 1 as the root node (the tree structure data itself) is not subject to lexicographic compression, run length compression, or the like, and is therefore excluded from the ancestor series. Therefore, for example, the ancestor series of the node 11 is “node 7, node 11”, and the ancestor series of the node 20 is “node 17, node 18, node 20”.

  Subsequently, the dividing unit 105 includes a root node of a subtree to be subjected to lexicographic compression or run length compression in an ancestor (node 7) obtained by removing the own node (node 11) from an ancestor sequence of the node 11 that is a candidate node. It is determined whether or not there is (step S207). Here, since the node 7 is not the root node of the overlapping subtree and cannot be any compression target (step S207: NO), the dividing unit 105 is the root node of the subtree in which the node 11 that is the candidate node is the target of the continuous length compression. It is determined whether or not there is (step S208). Here, the subtree having the node 11 as the root node is subject to continuous length compression with the subtree having the node 8 as the root node (step S208: YES). The boundary D1) is moved to a position immediately after the subtree to be subjected to continuous length compression, that is, the position at which the node 13 and the node 14 are divided (step S209). Note that the dividing unit 105 executes the determinations in step S207 and step S208, for example, by referring to a dictionary table and cyclic scanning of tree structure data.

  Subsequently, the dividing unit 105 executes Steps S206 to S208 for the candidate node (node 14) determined based on the moved dividing boundary (the dividing boundary D3 in FIG. 9). Since the ancestor series of the node 14 is only the node 14 (step S207: NO), and the node 14 is not the root node of the subtree to be subjected to the continuous length compression (step S208: NO), the dividing unit 105 The division boundary D3 is determined as the division boundary (step S210).

  Subsequently, since there are still undecided division boundary candidates D2 (step S211: YES), the division unit 105 selects the division boundary D2 (step S202). Subsequently, the dividing unit 105 determines whether there is a determined division boundary (step S203). Here, since there is a confirmed division boundary D3 (step S203: YES), the division unit 105 determines whether or not the node 20, which is a candidate node, is behind the previous decision division boundary D3. (Step S204). Here, since the node 20 is behind the division boundary D3 (step S204: YES), the division unit 105 extracts the ancestor series of the node 20 that is a candidate node (step S206).

  If it is determined in step S204 that the candidate node is not behind the previous determined division boundary (step S204: NO), the division unit 105 determines the division boundary candidate immediately before. After moving to an arbitrary position behind the division boundary (step S205), the process of step S206 is executed.

  Subsequently, the dividing unit 105 becomes a target of lexicographic compression or run length compression in the ancestors (nodes 17 and 18) obtained by excluding the own node (node 20) from the ancestor series of the node 20 that is a candidate node. It is determined whether there is a root node of the subtree (step S207). Here, the subtree having the node 18 as the root node is an overlapping subtree that overlaps the subtree having the node 2 as the root node, and is a target of lexicographic compression (step S207: YES). Therefore, the division unit 105 moves the division boundary candidate (division boundary D2) to a position immediately after the partial tree to be lexicographically compressed, that is, the position where the node 22 and the node 23 are divided (step S209).

  Subsequently, the dividing unit 105 executes Steps S206 to S208 for the candidate node (node 23) determined based on the moved dividing boundary (the dividing boundary D4 in FIG. 9). The ancestor series of the node 23 is (node 17, node 23), but none of the nodes is the root node of the subtree subject to lexicographic compression or run length compression (step S207: NO). Further, the subtree having the node 23 as a root node is an overlapping subtree that overlaps the subtree having the node 8 as a root node, and is a lexicographic compression target. No (step S208: NO). Therefore, the dividing unit 105 determines the divided boundary D4 after the movement as a divided boundary (step S210).

  As a result of the above processing, there are no more undetermined division boundary candidates (step S211: NO), and the division unit 105 divides the tree structure data at the decided division boundaries D3 and D4 (step S212).

  Subsequently, one thread is allocated to each of the plurality of node sequences generated by the division unit 105 by the thread allocation unit 106 (step S106, thread allocation step).

  Subsequently, the serialization unit 107 serializes the data corresponding to each node included in the node sequence into a byte sequence in the serialization order in parallel for each thread (step S107, serialization step). In step S105, when the dividing unit 105 executes the dividing process shown in steps S201 to S212 to divide the tree structure data, in step S107, the serializing unit 107 performs lexicographic compression in units of overlapping subtrees. In addition, serialization can be performed after executing continuous length compression (predetermined compression processing).

  Subsequently, the serialization results for each thread obtained by the serialization unit 107 are combined in the serialization order by the combining unit 108 (steps S108 to S110, combining step). For example, consider a case where there are three threads (thread 1, thread 2, and thread 3 in ascending order of serialization order of processing target node strings) and three serialization results for each thread are obtained. In this case, the combining unit 108 first selects the serialization result of the frontmost thread 2 from the unconnected parts (serialization results after the thread 2) with respect to the first serialization result (serialization result of the thread 1) ( In step S108, the serialized result of the selected thread 2 is coupled to the rear of the serialized result of thread 1 (step S109). Subsequently, the combining unit 108 determines whether there is an unconnected part (step S110). Here, since there is an uncombined part (result of serialization of the thread 3) (step S110: YES), the joint unit 108 is a part of the part that has already been joined (part where the serialization results of the threads 1 and 2 are joined). The serialized results of the thread 3 are combined backward (steps S108 and S109). As a result, all serialization results are combined and there is no unbonded portion (step S110: NO), so the combining unit 108 completes the combining process.

  In step S109, the combining unit 108 can input the serialization result to be combined and execute a predetermined data compression process such as ZIP compression to combine them.

  Finally, the serialization result combined by the combining unit 108 by the output unit 109 is a predetermined server device (not shown) that uses the serialization result, and storage for storing the serialization result for a certain period of time. (Step S111, output step).

  Next, a data serialization program P1 for causing a computer to function as the data serialization device 1 will be described with reference to FIG. FIG. 16 is a block diagram showing a module configuration of the data serialization program P1. As shown in FIG. 16, the data serialization program P1 includes a weight determination module P11, a division module P12, a thread assignment module P13, a serialization module P14, a combination module P15, and an output module P16. The functions realized by executing the weight determination module P11, the division module P12, the thread allocation module P13, the serialization module P14, the combination module P15, and the output module P16 correspond to the data serialization apparatus 1 described above. The functions are the same as those of the weight determination unit 104, the division unit 105, the thread allocation unit 106, the serialization unit 107, the combination unit 108, and the output unit 109.

  The data serialization program P1 thus configured is stored in the recording medium 18 shown in FIG. 2 and is executed by a computer used as the data serialization device 1. When the recording medium 18 is inserted into the recording medium reading unit 17, the computer can access the data serialization program P1 stored in the recording medium 18 from the recording medium reading unit 17, and executes the data serialization program P1. By doing so, it becomes possible to operate as the data serialization apparatus 1 according to the present embodiment.

  The data serialization program P1 may be provided via a network as a computer data signal superimposed on a carrier wave. In this case, the computer used as the data serialization device 1 can execute the data serialization program P1 by storing the data serialization program P1 received by the communication control unit 14 in the main storage unit 12.

  Heretofore, the data serialization apparatus 1 according to the present embodiment has been described in detail. According to the data serialization apparatus 1, the serialization processing of the tree structure data can be speeded up by processing the serialization processing of the tree structure data into the binary format in parallel by a plurality of threads. The data serialization device 1 can be used for any application that serializes tree structure data in binary format. For example, in an application for storing big data, serialization using compression processing (lexicographic compression, run length compression, ZIP compression, etc.) in combination to reduce the data size to be stored can be executed appropriately and at high speed. In applications where data is transmitted over a network, binary data (serialization result) to be transmitted can be generated at high speed by serializing the original data (tree structure data) into a byte string at high speed.

DESCRIPTION OF SYMBOLS 1 ... Data serialization apparatus, 101 ... Tree structure construction part, 102 ... Duplicate subtree detection part, 103 ... Dictionary table production | generation part, 104 ... Weight determination part, 105 ... Dividing part, 106 ... Thread allocation part, 107 ... Serialization 108, coupling unit, 109 ... output unit, D1 to D6 ... division boundary, P1 ... data serialization program, P11 ... weight determination module, P12 ... division module, P13 ... thread allocation module, P14 ... serialization module, P15 ... coupling module, P16 ... output module.

Claims (9)

Predetermined tree structure data having leaf nodes that hold values, intermediate nodes that hold leaf nodes or other intermediate nodes as child nodes, and root nodes that are the only intermediate nodes that do not have a parent node A data serializer that serializes in a serialization order,
For each subtree having each node as a root node, weight determining means for determining a weight based on the size of the subtree;
A dividing unit configured to divide the tree structure data into a plurality of node sequences each including one or more nodes in which the serialization order is continuous based on the weight of each subtree determined by the weight determining unit;
Thread assignment means for assigning one thread to each of the plurality of node sequences generated by being divided by the dividing means;
Serializing means for serializing data corresponding to each node included in the node sequence into a byte sequence in the serialization order in parallel for each thread;
Coupling means for coupling the serialization results for each thread obtained by the serialization means in the serialization order;
Output means for outputting the serialized result combined by the combining means;
A data serialization device comprising: The serialization means performs serialization after executing a predetermined compression process on overlapping subtree units indicating equivalent subtrees that appear multiple times in the tree structure data,
The dividing unit divides the tree structure data so as not to divide a node included in the overlapping subtree and a node immediately before the node in the serialization order;
The data serialization device according to claim 1. As one of the compression processes included in the predetermined compression process, the duplication unit performs the duplication based on a dictionary table in which data and codes corresponding to the duplication subtree are stored in association with each other in advance. Performing lexicographic compression replacing the data corresponding to the subtree with the code;
Allowing the dividing means to divide a root node of a subtree for which the lexicographic compression is executed by the serializing means and a node immediately before the root node in the serialization order; Split structural data,
The data serialization apparatus according to claim 2. The weight determination means makes the weight of the overlapping subtree to be subjected to the predetermined compression processing smaller than when the predetermined compression processing is not performed;
The data serialization device according to claim 2 or 3. The dividing unit divides the tree structure data so that a weight for each node sequence determined based on a weight of each subtree determined by the weight determining unit is equalized between the node sequences;
The data serialization apparatus as described in any one of Claims 1-4. The dividing unit divides the tree-structured data so that the weight of each node sequence determined based on the weight of each subtree determined by the weight determining unit is smaller for the node sequence having a lower serialization order. To
The data serialization apparatus as described in any one of Claims 1-4. The combining means inputs serialized results for each thread one by one in the serialization order and executes a predetermined data compression process, and then combines the serialized results for each thread.
The data serialization apparatus according to claim 6. Predetermined tree structure data having leaf nodes that hold values, intermediate nodes that hold leaf nodes or other intermediate nodes as child nodes, and root nodes that are the only intermediate nodes that do not have a parent node A data serialization method performed by a data serializer that serializes in a serialization order, comprising:
For each subtree having each node as a root node, a weight determination step for determining a weight based on the size of the subtree;
A division step of dividing the tree-structured data into a plurality of node sequences each including one or more nodes in which the serialization order is continuous based on the weight of each subtree determined in the weight determination step;
A thread allocation step of allocating one thread to each of the plurality of node sequences generated by the division in the division step;
A serialization step of serializing data corresponding to each node included in the node sequence into a byte sequence in the serialization order in parallel for each thread;
A combining step of combining the serialized results for each thread obtained in the serializing step in the serialization order;
An output step for outputting the serialized result combined in the combining step;
A data serialization method including: Predetermined tree structure data having leaf nodes that hold values, intermediate nodes that hold leaf nodes or other intermediate nodes as child nodes, and root nodes that are the only intermediate nodes that do not have a parent node A computer provided in a data serialization device that serializes in a serialization order,
For each subtree having each node as a root node, weight determining means for determining a weight based on the size of the subtree;
A dividing unit configured to divide the tree structure data into a plurality of node sequences each including one or more nodes in which the serialization order is continuous based on the weight of each subtree determined by the weight determining unit;
Thread assignment means for assigning one thread to each of the plurality of node sequences generated by being divided by the dividing means;
Serializing means for serializing data corresponding to each node included in the node sequence into a byte sequence in the serialization order in parallel for each thread;
Coupling means for coupling the serialization results for each thread obtained by the serialization means in the serialization order;
Output means for outputting the serialized result combined by the combining means;
Data serialization program to function as

Images