CN110109920B - Data comparison method and server - Google Patents

Abstract

The embodiment of the invention relates to the technical field of data processing, and discloses a data comparison method and a server. The data comparison method comprises the following steps: reading two data in parallel; wherein each of the data comprises a plurality of records and each of the records forms a hash node; attempting to insert each of the hash nodes into a hash tree; and in the process of trying to insert, if determining that the node matched with the hash node exists in the hash tree, rejecting the node. The embodiment of the invention also provides a server. The technical scheme of the embodiment of the invention can efficiently process comparison of large data volume and effectively solve the bottleneck problem of the storage capacity of the Hash table in the comparison scheme.

Description

Data comparison method and server

technical field

The embodiments of the present invention relate to the technical field of data processing, and in particular, to a data comparison method and a server.

Background technique

In the process of office data synchronization, there are often inconsistencies in office data among various systems due to various reasons. For example, the content interface information office data is synchronized by the subsidiary to the office data system, and then synchronized by the office data system to the security management and control. There will be situations where the interface data between the subsidiary and the data system of the office is inconsistent, and the data of the interface between the data system of the office and the security management and control system is inconsistent. Therefore, it is necessary to compare whether the metadata of each network is consistent.

At present, when comparing whether the data of each network element is consistent, the first comparison data is inserted into the first Hash table A, and then the second comparison data is read one by one, and it is judged whether it exists in the first Hash table A. If the first data identical to the current read data exists, delete the first identical data from the first Hash table A, and store the current data in the second Hash table B if it does not exist. After the data is read, the first difference data is stored in the first Hash table A, and the second difference data is stored in the second Hash table B.

The inventor found that there are at least the following problems in the prior art: before the comparison starts, the first comparison data needs to be stored in the Hash table; Due to the limitation of capacity, there will be bottlenecks, and the processing speed will drop rapidly due to serious collisions.

SUMMARY OF THE INVENTION

The purpose of the embodiments of the present invention is to provide a data comparison method and a server, which can efficiently handle the comparison of a large amount of data, and effectively solve the bottleneck problem of the storage capacity of the Hash table in the comparison scheme.

In order to solve the above technical problem, an embodiment of the present invention provides a data comparison method, comprising: reading two copies of data in parallel; wherein, each copy of the data includes multiple records and each of the records forms a hash node; try to insert each hash node into the hash tree; in the process of trying to insert, if it is determined that there is a node matching the hash node in the hash tree, the node is eliminated.

Embodiments of the present invention also provide a server, comprising: at least one processor; and a memory communicatively connected to the at least one processor; wherein the memory stores a program executable by the at least one processor instructions, the instructions being executed by the at least one processor to enable the at least one processor to perform the above-described data comparison method.

Embodiments of the present invention further provide a computer-readable storage medium storing a computer program, and when the computer program is executed by a processor, the above-mentioned data comparison method is implemented.

Compared with the prior art, the embodiment of the present invention reads two pieces of data in parallel, and when it is determined that there is a node matching the hash node in the hash tree, the node is eliminated. The two copies of data are read in parallel, which can avoid the bottleneck problem caused by the capacity limitation of the hash tree that may be caused by accommodating a complete copy of the data in the prior art; the node that matches the hash node is eliminated, that is, the elimination of For the records that are not needed in the data comparison, only the required records are kept, which can further save storage space; therefore, the embodiment of the present invention can efficiently handle the comparison of a large amount of data, and effectively solve the bottleneck of the storage capacity of the Hash table in the comparison scheme question.

In addition, the removing the node includes: if the node is a child node, selecting a leaf node of the node to replace the node and deleting the selected leaf node; if the node is a leaf node, deleting the node node. This embodiment proposes a specific way of removing nodes.

In addition, matching the node with the hash node includes: the node and the hash node have the same keyword and different data sources. This embodiment proposes a specific way of matching.

In addition, after determining that the hash tree has the node that matches the hash node, the method further includes: judging whether the record content of the node and the hash node is the same; if the record content is different, outputting And save the node and the hash node, and enter the step of eliminating the node; if the record content is the same, directly enter the step of eliminating the node. In this embodiment, records with different data sources, the same keywords, and different record contents can also be identified, that is, more types of different data can be identified.

In addition, the hash tree is a prime number-based hash tree. This embodiment implements a data comparison method based on a hash tree of prime numbers, which has a larger capacity and higher comparison efficiency.

Description of drawings

One or more embodiments are exemplified by the pictures in the corresponding drawings, and these exemplifications do not constitute limitations of the embodiments, and elements with the same reference numerals in the drawings are denoted as similar elements, Unless otherwise stated, the figures in the accompanying drawings do not constitute a scale limitation.

1 is a flowchart of a data comparison method according to a first embodiment of the present invention;

2 is a schematic diagram of inserting a hash node according to the first embodiment of the present invention;

FIG. 3 is a schematic diagram of culling a node according to the first embodiment of the present invention;

4 is a flowchart of a data comparison method according to a second embodiment of the present invention;

FIG. 5 is a schematic diagram of a server according to a third embodiment of the present invention.

Detailed ways

In order to make the objectives, technical solutions and advantages of the embodiments of the present invention clearer, the various embodiments of the present invention will be described in detail below with reference to the accompanying drawings. However, those of ordinary skill in the art can appreciate that, in the various embodiments of the present invention, many technical details are set forth in order for the reader to better understand the present application. However, even without these technical details and various changes and modifications based on the following embodiments, the technical solutions claimed in the present application can be realized.

The first embodiment of the present invention relates to a data comparison method, which includes: reading two pieces of data in parallel; wherein each piece of data includes multiple records and each record forms a hash node; Insert into the hash tree; in the process of trying to insert, if it is determined that there is a node matching the hash node in the hash tree, remove the node.

The implementation details of the data comparison method of the present embodiment will be specifically described below. The following contents are only provided for the convenience of understanding, and are not necessary for implementing the present solution.

The data comparison method in this embodiment can be applied to a server, and the server is configured to perform consistency comparison between two pieces of data, so as to identify the difference data in the two pieces of data. For example, a subsidiary needs to synchronize a copy of data A to the data system of the bureau. In order to determine whether the data B received by the data system of the bureau is completely consistent with the data A sent by the subsidiary, it is necessary to compare the data A in the subsidiary with the data of the bureau. The data B received by the system is compared. Therefore, the server obtains data A directly from the subsidiary and data B directly from the bureau data system; then compares the two data A and B, and obtains the difference data between the two data A and B.

1 is a flowchart of the data comparison method of the first embodiment, which specifically includes the following steps:

In step 101, two copies of data are read in parallel.

The server reads the two pieces of data A and B in parallel, and tries to insert the two pieces of data A and B into the hash tree. Specifically, each piece of data contains multiple records and each record forms a hash node. Taking one piece of data A as an example, the server reads each record in data A in turn, and inserts each record (ie, a hash node) into the hash tree. In the process of reading each record, each record forms a hash node, and each hash node includes the keyword key, the record content word, and the data source flag flag; among them, the flag indicates which data is from, such as record 1 from data A, then the flag=A of record 1; the word represents the specific content of the record; the key can uniquely characterize the feature of the record, if the word of the record is the partner office data, the key can be the partner code. In this embodiment, when the server attempts to insert each record, it processes one record and then processes the next record.

In this embodiment, a hash tree is constructed according to the prime number resolution theorem, so as to realize the data comparison method described in this embodiment. The designer can choose multiple prime numbers to construct the hash tree according to the storage capacity. In this embodiment, the prime number sequence PRIM={3, 5, 7, 11, 13, 17, 19, 23, 29} is selected, that is, there are 3 nodes under the root node of the hash tree, which are used as the first layer. There are 5 nodes under each node in the second layer, and there are 7 nodes under each node in the second layer, which is the third layer; and so on. According to the prime number resolution theorem, these 9 prime numbers can accommodate 3*5*7*11*13*17*19*23*29, that is, 3 billion data. In this embodiment, the above 9 prime numbers are selected to construct a hash tree, which can be Take into account storage capacity requirements and complexity. It should be noted that this embodiment does not limit the type of the selected hash tree, and any type of hash tree applicable to the data comparison method of the present application falls within the protection scope of the present application.

The following steps 102 to 107 are the process of trying to insert a record (hash node) into a hash tree based on prime numbers.

Step 102, perform hash operation on the key of the hash node and obtain a random number.

Take a record in one of the data A as an example to illustrate. The record forms a hash node, and the keyword key in the hash node is hashed and a random number is obtained to ensure that each hash node is inserted into the hash tree. The insertion position satisfies or approximately satisfies a random distribution. After the random number is calculated, the location search step is entered, that is, step 103 is entered.

Step 103: Determine the node position corresponding to the hash node according to the random number and the prime number corresponding to the current search layer in the hash tree.

Specifically, use the random number obtained in step 102 to perform a remainder operation on the prime number corresponding to the current search layer, and obtain the remainder i, that is, the node position corresponding to the hash node is the ith node position of the current search layer.

Searching for the position of the node in the hash tree corresponding to the hash node starts from the root node of the hash tree; therefore, the search starts from the first layer, that is, the initial value of the current search layer is the first layer, and the first layer corresponds to the first layer. The prime number is PRIM[0]=3; that is, in this search, the position of the node corresponding to the hash node is the position of the ith child node of the first layer.

Step 104, determine whether the node position is occupied; if it is not occupied, go to step 105; if it is occupied, go to step 106.

If the node position corresponding to the hash node has not been inserted by other hash nodes, it means that the node position is not occupied, and the hash node can be inserted into the node position at this time, that is, step 105; if the node position corresponding to the hash node already has other hash nodes If the hash node is inserted, it means that the node position has been occupied.

Step 105, insert the hash node into the node position.

Step 106 , determine whether the node at the node position matches the hash node; if yes, go to step 107 ; if not, go to step 108 , and then return to step 103 .

When the node position corresponding to the hash node has been occupied, the server returns the node at the node position, wherein the node at the node position is also a hash node, including key, word, and flag; in this embodiment, the record to be inserted is called It is a hash node, and the record that has been inserted at the node position is called a node, just to distinguish the two from the name. The server determines whether the hash node matches the node. In this embodiment, the node in the node position matches the hash node to be inserted, including that the node and the hash node have the same keyword and different data sources. That is, when the key of the node is the same as the key of the hash node, and the flag of the node is different from the flag of the hash node, it can be considered that the node and the hash node are the same record from the above two pieces of data respectively. When the node is to be eliminated, enter step 107; when the key of the node is not the same as the key of the hash node or the flag of the node is the same as the flag of the hash node, it is determined that the node does not match the hash node, at this time , you need to continue to search for the node position corresponding to the hash node to the next layer of the hash tree.

It should be noted that the specific conditions for matching the nodes in the node positions with the hash nodes to be inserted described in this embodiment are merely illustrative, and not limited thereto; those skilled in the art can compare the actual data Set specific conditions for matching.

Step 107, remove the node.

When the node and the hash node are determined to match, the node is removed from the hash tree. The method of removing a node in this embodiment includes: if the node is a child node, selecting a leaf node of the node to replace the node and deleting the selected leaf node; if the node is a leaf node, deleting the node.

Step 108: Update the current search layer according to preset rules.

In this search, when the node at the node position does not match the hash node, it is necessary to continue searching for the node position corresponding to the hash node to the next layer. The preset rule in this embodiment is to update the current search layer to the next layer of the current search layer. If the current search layer is the first layer, the updated current search layer is the second layer; if the current search layer is the second layer, the updated current search layer is the third layer, and so on. After step 108, return to step 103.

As shown in Figure 2, when the node position corresponding to the hash node is not occupied, the hash node is inserted into its corresponding node position. Figure 2 shows the process of trying to insert record 1 and record 2 into the hash tree. In record 1, key=10, flag=A, indicating that record 1 comes from data A and key is 10, in record 2, key=1, flag=B, indicating that record 2 comes from data B and key is 1; it should be noted that , which is not shown in FIG. 2 due to the large amount of data recorded.

As indicated by the dotted line marked record 1 in Figure 2, record 1 corresponds to node position P1 in the first layer of the hash tree that has been occupied by a node (key=0, flag=A) and record 1 does not match this node, Therefore, the node position P12 in the second layer is searched again, and record 1 corresponds to the node position P12 in the second layer that is not occupied, and the mark marked as null in the figure indicates that it is not occupied; therefore, record 1 is inserted into the second layer corresponding to Similarly, as indicated by the dotted line marked with record 2 in Figure 2, record 2 corresponds to the node position P3 in the first layer of the hash tree that has been occupied by a node (key=1, flag=B) and Record 2 does not match this node, so the node position P35 in the second layer is searched again. Record 2 corresponds to the node position P35 in the second layer that is not occupied, so record 2 is inserted into the corresponding node position in the second layer. P35. In the example of FIG. 2, record 2 corresponds to the node (key=1, flag=B) at the node position P3 in the first layer of the hash tree, and its key and flag are the same as the hash node, indicating that there are duplicates in data B Record.

Figure 3 shows a schematic diagram of removing the node when the node position corresponding to the hash node is occupied and the node at the node position matches the hash node. Figure 3 shows the process of trying to insert record 3 into the hash tree. In record 3, key=0, flag=B, indicating that record 3 comes from data B and the key is 0. As indicated by the dotted line marked record 3 in Figure 3, record 3 corresponds to the node position P1 in the first layer of the hash tree that has been occupied by a node (key=0, flag=A), and record 3 has the same key as the node And the flag is different, indicating that record 3 matches the node, and the two are duplicate records, so the node (key=0, flag=A) should be removed; at this time, the node (key=0, flag=A) is obtained a leaf node node1, replace the node with the leaf node node1, and delete the leaf node node1. It should be noted that this embodiment does not impose any limitation on the method of removing a node. In other examples, the nodes at the lower layer of the node may be replaced in sequence upward; for example, in FIG. 3, the node may be replaced by node1 replaces node2, and finally deletes node1.

In this embodiment, in the process of inserting each record into the hash tree, records from different data and with the same keyword can be eliminated, that is, after all records are processed, the nodes stored in the hash tree are two copies of data The difference data in the data, the difference data is a record that exists only in one of the data (only exists in data A, or only exists in data B); traversing the hash tree can get such differences in the two data data.

Compared with the prior art, the embodiment of the present invention reads two pieces of data in parallel, and when it is determined that there is a node matching the hash node in the hash tree, the node is eliminated. Two copies of data are read in parallel, which can avoid the bottleneck problem caused by the capacity limitation of the hash tree that may be caused by accommodating a complete copy of the data in the prior art. When the amount of data is large, the capacity of the hash tree The bottleneck problem caused by the restriction is particularly serious; and, removing the nodes matching the hash nodes, that is, removing the unnecessary records in the data comparison, and retaining only the required records, can further save the storage space; therefore, the embodiment of the present invention can efficiently It can handle the comparison of large data volume effectively, and effectively solve the bottleneck problem of Hash table storage capacity in the comparison scheme.

The second embodiment of the present invention relates to a data comparison method. The second embodiment is substantially the same as the first embodiment, and the main difference is that in the second embodiment of the present invention, nodes with the same keyword but different recorded contents can also be identified.

4 is a flowchart of a data comparison method according to a second embodiment of the present invention, including the following steps:

Step 201, read two pieces of data in parallel; wherein, each piece of data includes multiple records and each record forms a hash node;

Step 202, perform hash operation on the keyword of the hash node and obtain a random number, and enter the location search step;

Step 203, according to the random number and the prime number corresponding to the current search layer in the hash tree, determine the node position corresponding to the hash node;

Step 204, determine whether the node position is occupied; if it is not occupied, go to step 105; if it is occupied, go to step 106;

Step 205, insert the hash node into the node position

Step 206, determine whether the node at the node position matches the hash node; if so, go to Step 207; if not, go to Step 210 and then return to Step 203;

Wherein, when the node whose position is determined matches the hash node, it is determined that there is a node matching the hash node in the hash tree.

Step 207, determine whether the record content of the node and the hash node are the same; if not, go to step 208; if so, go to step 209;

Step 208 , output and save the node and the hash node; and go to step 209 .

Step 209, remove the node.

Step 210, update the current search layer according to preset rules.

Among them, steps 201 to 206 and 209 to 210 are substantially the same as steps 101 to 108 in the first embodiment, and will not be repeated here; the difference is that steps 207 and 208 are also included.

When it is determined in step 206 that the node at the node position matches the hash node, it is also necessary to judge whether the record content of the node and the hash node are the same; if the record content is the same, it means that the node is completely consistent with the hash node, then directly enter step 209 ; If the record content is not the same, it means that the node and the hash node are not completely consistent, then go to step 209, output and save the node and the hash node, the node and the hash node can be saved in a preset difference In the data table, the difference data table is specially used to save records with different flags, the same key and different words. In this embodiment, the words in the records with the same key are different, which may be caused by various uncertain factors in network transmission. Parts are lost or altered.

Compared with the first embodiment, this embodiment can also identify records with different data sources, the same keywords, and different record contents, that is, more types of difference data can be identified.

The steps of the above various methods are divided only for the purpose of describing clearly. During implementation, they can be combined into one step or some steps can be split and decomposed into multiple steps. As long as the same logical relationship is included, they are all within the protection scope of this patent. ;Adding insignificant modifications to the algorithm or process or introducing insignificant designs, but not changing the core design of the algorithm and process are all within the scope of protection of this patent.

The third embodiment of the present invention relates to a server, as shown in FIG. 5 , including:

at least one processor 501; and,

a memory 502 in communication with the at least one processor 501; wherein,

The memory 502 stores instructions executable by the at least one processor 501, the instructions being executed by the at least one processor 501 to enable the at least one processor 501 to perform the above-described method embodiments.

The server may also include: an input device and an output device.

The memory 502 and the processor 501 are connected by a bus, and the bus may include any number of interconnected buses and bridges, and the bus connects one or more processors 501 and various circuits of the memory 502 together. The bus may also connect together various other circuits, such as peripherals, voltage regulators, and power management circuits, which are well known in the art and therefore will not be described further herein. The bus interface provides the interface between the bus and the transceiver. A transceiver may be a single element or multiple elements, such as multiple receivers and transmitters, providing a means for communicating with various other devices over a transmission medium. The data processed by the processor 501 is transmitted on the wireless medium through the antenna, and further, the antenna also receives the data and transmits the data to the processor 501 .

Processor 501 is responsible for managing the bus and general processing, and may also provide various functions including timing, peripheral interface, voltage regulation, power management, and other control functions. The memory 502 may be used to store data used by the processor 501 when performing operations.

The above product can execute the method provided by the embodiments of the present application, and has functional modules and beneficial effects corresponding to the execution method. For technical details not described in detail in this embodiment, reference may be made to the method embodiments provided in the embodiments of this application.

A fourth embodiment of the present invention relates to a computer-readable storage medium storing a computer program. The above method embodiments are implemented when the computer program is executed by the processor.

That is, those skilled in the art can understand that all or part of the steps in the method for implementing the above embodiments can be completed by instructing the relevant hardware through a program, and the program is stored in a storage medium and includes several instructions to make a device ( It may be a single chip microcomputer, a chip, etc.) or a processor (processor) to execute all or part of the steps of the methods described in the various embodiments of the present application. The aforementioned storage medium includes: U disk, removable hard disk, Read-Only Memory (ROM, Read-Only Memory), Random Access Memory (RAM, Random Access Memory), magnetic disk or optical disk and other media that can store program codes.

Those skilled in the art can understand that the above-mentioned embodiments are specific examples for realizing the present invention, and in practical applications, various changes in form and details can be made without departing from the spirit and the spirit of the present invention. scope.

Claims (6)

1. A method of data alignment, comprising:

reading two data in parallel; wherein each of the data comprises a plurality of records and each of the records forms a hash node;

attempting to insert each of the hash nodes into a hash tree; in the process of trying to insert, if the node matched with the hash node exists in the hash tree, the node is removed;

wherein the node matched with the hash node comprises: the nodes are the same as the keywords of the hash nodes and have different data sources;

after determining that the node matching the hash node exists in the hash tree, the method further includes:

judging whether the recorded contents of the node and the hash node are the same; if the recorded contents are different, outputting and storing the node and the hash node, and entering a step of eliminating the node; if the recorded contents are the same, directly entering the step of removing the nodes;

the eliminating the node comprises: and if the node is a child node, selecting a leaf node of the node to replace the node and deleting the selected leaf node, and if the node is a leaf node, deleting the node.

2. The data comparison method of claim 1, wherein the hash tree is a prime number based hash tree.

3. The method of claim 2, wherein the trial insertion process comprises:

carrying out Hash operation on the keywords of the Hash nodes to obtain random numbers, and entering a position searching step;

the position searching step is that the node position corresponding to the hash node is determined according to the random number and the prime number corresponding to the current searching layer in the hash tree;

inserting the hash node into the node location when the node location is unoccupied;

when the node position is occupied, if the node of the node position is matched with the hash node, determining that the node matched with the hash node exists in the hash tree; and if the node at the node position is not matched with the Hash node, updating the current search layer according to a preset rule, and entering the position search step.

4. The method of claim 2, wherein the prime number sequences used to construct the hash tree are 3, 5, 7, 11, 13, 17, 19, 23, 29.

5. A server, comprising:

at least one processor; and the number of the first and second groups,

a memory communicatively coupled to the at least one processor; wherein,

the memory stores instructions executable by the at least one processor to enable the at least one processor to perform the data alignment method of any one of claims 1 to 4.

6. A computer-readable storage medium storing a computer program, wherein the computer program is configured to implement the data matching method according to any one of claims 1 to 4 when executed by a processor.

Images