CN101442731A - Method and apparatus for removing call ticket repeat - Google Patents

Abstract

The present invention discloses a method and device for deduplication of bills, which are mainly used in the field of communication billing, comprising the following steps: extracting key domain information from the bill; using MD5 algorithm to calculate the key domain information, and generating MD5 characteristic strings; Compare the MD5 feature string with the MD5 feature string stored in the index file and corresponding to the normal bill, if the same MD5 feature string is found, then the bill is a duplicate and should be eliminated, otherwise the MD5 corresponding to the bill Save the feature string to the index file, and confirm that the bill is a normal bill. In the present invention, the MD5 characteristic string in the index file is stored in the form of a hash table, and the conflict of the hash table is resolved through a linked list or a balanced binary tree. The present invention integrates the strengths of the hash table, balanced binary tree and MD5 algorithm, realizes the effective processing of any business and any type of bills, and forms a unique de-duplication index after the system processing, and has a unique length, which improves the de-duplication operation efficiency and scalability, greatly saving storage space.

Description

A method and device for deduplicating phone calls

technical field

The invention relates to the field of communication charging, in particular to a method and device for deduplication of bills widely used in charging and settlement systems in the communication field.

Background technique

The billing system must deduplicate each call bill collected from each network element or service platform before appraising the dialogue bill. Therefore, for a billing system that needs to process a large number of bills every day The performance of the system will directly affect the timeliness of bill processing.

Generally, the call list deduplication process is carried out in the memory, and the basic principle is as follows: First, extract the corresponding combination of key field information (such as mobile phone number, call time, party number, SP code, etc., different types of call list keys) from the call list. Field combination is different), and then search whether the information of the combination field exists in the memory, if there is a combination of the key field information of the bill, it is judged as a duplicate order, otherwise the key field information of the bill is stored in the memory. However, only a certain amount of key domain information can be stored in the memory, and the expired data will be output to the disk and stored in the form of a file. When processing delayed bills, they must first be reloaded into memory. Therefore, how to manage and store the key field information of these bills is directly related to the storage size required by the system and the efficiency of deduplication.

Existing duplication check technology generally extracts the combination of key field information in the bill, directly stores it in the page of the memory, and uses hash linked list or balanced binary tree method to retrieve the page where the key field combination information of the bill is stored, and judges whether it is a duplicate information.

A Chinese patent document with the application number 03145603.0 discloses a memory-based call list deduplication method, including: extracting the key field information in the call list, storing them in the page of the memory after simple combination, and using the HASH linked list method Alternatively, the balanced binary tree method can retrieve the combined information storage page of the bill key field, and judge whether it is repeated information.

A Chinese patent document with the application number 200610036536.4 discloses a system and method for eliminating redundant files in the file storage system. The method for eliminating redundant files in the file storage system includes: obtaining files by scanning the storage server module Relevant information, including the size of the file, the number of file references, and the ID of the file, and calculate the MD5 value of the file content, and after the MD5 value of the file is hashed, the corresponding hash table is found through the memory hash map. If the number of file references exceeds the threshold, find redundant files in the storage system through the hash table based on the MD5 value of the file and the size of the file and delete them.

The shortcomings of the existing de-weighting technology can be summarized as the following two points:

1. The key field information of various bills is different, the length of the field and the length of the corresponding combination are different, it is not easy to manage, and the scalability is poor. In addition, the combination fields of the key field information are usually relatively long, occupying a large amount of storage, and at the same time It will affect the efficiency of deduplication comparison to a certain extent.

2. The simple hash list or balanced binary tree method is still not efficient enough when processing massive amounts of data (more than 100 million call records per day, and the peak value can reach tens of millions per hour), and cannot meet the growing needs of communication services.

Contents of the invention

The purpose of the present invention is to provide a method and device for deduplication of bills to solve the problems of different key field information of various existing bills, difficult management, poor scalability, and insufficient efficiency in processing massive data.

In order to achieve the above object, the present invention provides a method for eliminating duplicate calls, comprising the following steps:

Step a: extract key field information from the bill;

Step b: use the MD5 algorithm to calculate the key field information, and generate the MD5 feature string corresponding to the bill;

Step c: comparing the MD5 characteristic string with the MD5 characteristic string stored in the index file and corresponding to the normal bill, if the same MD5 characteristic string is found, the bill is a duplicate, and the bill is eliminated , otherwise, save the MD5 characteristic string into the index file, and confirm that the bill corresponding to the MD5 characteristic string is a normal bill.

In the technique scheme, the MD5 feature string corresponding to the normal call list is stored in the index file in the form of a hash table; the step c specifically includes:

Step c1: The MD5 characteristic string corresponding to the dialogue ticket is hashed according to the set hash function;

Step c2: According to the function value obtained by the hash operation, find the storage node in the hash table:

Step c3: If the MD5 characteristic string identical to the MD5 characteristic string corresponding to the bill is found on the storage node, then the bill is a duplicate bill, and the bill is removed; otherwise, the MD5 characteristic string corresponding to the bill is inserted Go to the storage node, and confirm that the bill is a normal bill.

In the above technical solution, the MD5 characteristic strings in the storage nodes in the hash table are stored in a linked list or a balanced binary tree.

In the above technical solution, when the MD5 characteristic string in the storage node in the hash table is stored in the form of a balanced binary tree, the step of inserting the corresponding MD5 characteristic string of the bill into the bill storage node includes: The MD5 characteristic string is inserted into the balanced binary tree on the storage node, and if the inserted MD5 characteristic string makes the balanced binary tree unbalanced, adjustment is performed by rotation.

Preferably, when the bill is a normal bill, the bill is output, and an updated index increment file is output.

Preferably, the index file and the index increment file are stored in the memory or the disk; if the memory usage exceeds the specified value, the index increment file is merged, and the earlier part of the index file is stored in the disk, and Automatically release the memory; if the index file in the disk needs to be reloaded into the memory, reload it.

Preferably, the key field information includes, but is not limited to: any combination of calling number, called number, call time, and SP code or a combination thereof.

In order to achieve the above object, the present invention also provides a bill deduplication device, including: an extraction module, used to extract key domain information from the bill; a feature string generation module, used to use the MD5 algorithm to calculate the key domain information , generate the MD5 feature string; compare and remove duplicate modules, for comparing the MD5 feature string stored in the index file with the MD5 feature string corresponding to the normal call list; if the same MD5 feature string is found, then the call list is If the bill is repeated, delete the bill; otherwise, save the MD5 characteristic string corresponding to the bill to the index file, and confirm that the bill is a normal bill.

Preferably, the comparison and deduplication module includes: a calculation and positioning unit, configured to perform a hash operation on the MD5 characteristic string according to a set hash function, and find the hash function value according to the hash function value obtained by the operation. A storage node in the table; a search unit, which is used to search for the same feature string as the MD5 feature string on the storage node; a duplicate unit, which is used to determine whether the bill is heavy according to the result of the search If the MD5 signature string identical to the signature string is found on the storage node of the hash table, the bill is a duplicate bill, and is removed; otherwise, the bill is a normal bill.

Preferably, the storage node of the hash table is a linked list or a balanced binary tree.

Preferably, when the storage node in the hash table is a balanced binary tree, the comparison and deduplication module further includes: an insertion unit for inserting the MD5 feature string corresponding to the normal bill into the balanced On the binary tree, output the normal call list and its index incremental file at the same time; the rotation unit is used to make the balanced binary tree unbalanced if the MD5 feature string is inserted into the balanced binary tree, then rotate the balanced binary tree by the rotation unit Make adjustments.

Preferably, the bill deduplication device further includes a loading module, which is used to reload the index file in the disk to the memory as required.

The method and device for deduplicating bills provided by the present invention combine the strengths of hash tables, balanced binary trees and MD5 algorithms to realize effective processing of any business and any type of bills, and form a unique deduplication index after processing by the system, and The length is unique, which improves the efficiency and scalability of deduplication operation, and greatly saves storage space.

Description of drawings

Fig. 1 is the flow chart of embodiment 1 of a kind of bill deduplication method of the present invention;

Fig. 2 is a schematic diagram of a scheme for resolving conflicts using a balanced binary tree as a hash table;

Fig. 3 is a schematic diagram of an unbalanced binary tree;

Fig. 4 is a schematic diagram of a balanced binary tree;

Fig. 5 is a flow chart of Embodiment 2 of a method for deduplicating bills of the present invention;

Fig. 6 is a schematic diagram of balanced binary tree rotation;

Fig. 7 is a schematic diagram of searching for MD5 characteristic strings on a balanced binary tree;

Fig. 8 is a structural diagram of Embodiment 1 of a bill deduplication device according to the present invention;

Fig. 9 is a structural diagram of Embodiment 2 of a bill deduplication device according to the present invention.

Detailed ways

The specific implementation manners of the present invention will be described in detail below in conjunction with the accompanying drawings.

method embodiment

As shown in Figure 1, a flow chart of Embodiment 1 of a method for removing duplicates from a bill is disclosed, and the technical terms mentioned in this embodiment are introduced as follows:

MD5 (Message-Digest Algorithm 5, Information-Digest Algorithm 5) is a single-item hash algorithm for generating digital signatures, which can convert a "byte string" of any length into A 16-byte string. The MD5 algorithm can be used to standardize the combination of any business and any type of bill key field information, and compress it into a unique 16-byte string. In this way, the key field information of any bill can be managed and stored in a unified manner. Moreover, the key field information of general bills is much more than 16 bytes, so converting it into a 16-byte string for management and storage will significantly improve the efficiency of search and comparison, and can also greatly save storage costs. In addition, the 16-byte strings generated by the MD5 algorithm are evenly distributed, which is very conducive to constructing a simple and optimal hash function for positioning, thereby effectively improving the processing efficiency.

The hash function is a many-to-one mapping, assuming that y=F(x), there may be multiple x values corresponding to one y value, which is called a collision of the hash table. Therefore, when using a hash table, a method for resolving this conflict must be designed at the same time, that is, how to store multiple x values corresponding to the same y value in the memory. The present invention can not only store these data using a linked list, but also use a balanced binary tree To solve the problem of hash table collision. For the data in Figure 2, the hash function maps the four values 1, 9, 17, and 25 to the function value 1, and 11 corresponds to the function value 3, etc. For the address with the function value 1, 1, 9, 17, 25 These four data are then stored in a data structure such as a balanced binary tree.

Hash table means that according to a set hash function, the keyword of each element corresponds to a hash function value, and it is used as the storage location of the keyword in the hash table, that is, the hash address , thus eliminating the waste of time caused by traversal comparison, the key lies in designing an optimal hash function and a method of dealing with conflicts. A balanced binary tree is an empty tree, or a binary tree with the following properties: its left and right subtrees are both balanced binary trees, and the absolute value of the difference between the depths of the left and right subtrees does not exceed 1 , as shown in Figure 3 is an unbalanced binary tree, and Figure 4 is a balanced binary tree, the time complexity is 0(log n) on average and in the worst case, and the search efficiency is very high. After inserting or removing nodes, it may become out of balance and need to be adjusted by one or more rotations to keep it balanced.

Embodiment 1 of a method for removing duplicates from a bill of the present invention comprises the following steps:

Step S102, extracting key field information from the call list, such as any one or a combination of field combinations such as calling number, called number, call time, SP code;

Step S104, using the MD5 algorithm to calculate the key domain information to generate an MD5 feature string;

Step S106, perform a hash operation on the MD5 characteristic string generated in step S104 according to the set hash function, and locate the MD5 characteristic string to the storage node of the hash table according to the calculated hash function value on a balanced binary tree;

Step S108, search for the MD5 signature string generated in step S104 on the balanced binary tree that has been positioned, if the MD5 signature string identical to the MD5 signature string is found on the balanced binary tree, jump to step S110, otherwise jump to Step S112;

Step S110, if the MD5 signature string identical to the MD5 signature string is found on the balanced binary tree, then it is determined that the bill is a duplicate bill, and the duplicate bill is eliminated;

Step S112, if no MD5 signature string identical to the MD5 signature string is found on the balanced binary tree, then it is determined that the bill is not a duplicate bill, and the step ends.

The embodiment of a method for deduplication of bills of the present invention, the advantages of comprehensive hash table, balanced binary tree and MD5 algorithm, realizes the effective processing of any business and any type of bills, and forms a unique deduplication after being processed by the deduplication system. Re-indexing, with a unique length, improves the efficiency and scalability of de-duplication operations, and greatly saves storage space.

As shown in Figure 5, a flow chart of Embodiment 2 of a method for eliminating duplicate calls is disclosed. On the basis of Embodiment 1, the scheme is refined, including the following steps:

Step S202, reading the call list into the system, and the step of removing duplicate calls starts;

Step S204, extracting key field information from the call list, such as any one or combination of field combinations such as calling number, called number, call time, SP code, etc., the MD5 characteristic string corresponding to the normal call list is represented by hash The hash table is stored in the index file, and the index file is stored in memory or disk, and the conflict of the hash table is resolved by balancing the binary tree;

Step S206, judging whether there is an index file corresponding to the normal call list stored in the internal memory, if yes, jump to step S210, otherwise, jump to step S208;

Step S208, if the index file of the processed bill is not stored in the memory, reload the index file in the disk to the memory, and continue to execute step S210;

Step S210, otherwise, use the MD5 algorithm to calculate the key field information to generate an MD5 feature string, the MD5 feature string is a unique 16-byte string, and each byte is an 8-bit binary value, such as: 00000000 00000001 00000010 00000011 00000100 00000101 0000011000000111 00001000 00001001 00001010 00001011 00001100 0000110100001110 00010000;

Step S212, since the MD5 characteristic string generated in step S210 is evenly distributed, the hash function can directly take the value of the first or first two digits of the MD5 characteristic string to locate it to the corresponding storage node as a hash table On the balanced binary tree, such a hash function operation can locate 1/256 or 1/65536 of the original data volume. Here, explain the reason why a hash function operation locates 1/256 or 1/65536 of the original data volume: the MD5 algorithm generates a 16-byte characteristic string, such as 0123456789ABCDEF, each of which is an 8-bit Byte, which is composed of 8 binary values, such as 01010101, because each binary bit has two possible values, so the possible value of each byte is 256, that is, 2 ⁸ , therefore, if the 16 words are taken The first bit of the section string is directly addressed as the hash function value, and the traversal search only needs to be performed in the last 15 byte strings. For evenly distributed data, it is only 1/256 of the value of the 16-byte string. If The first two digits are directly addressed as the hash function value, and the data to be searched is 1/65536 of the 16-byte string.

Step S214, the node positioned by the hash function is a balanced binary tree, and the MD5 characteristic string is searched on this balanced binary tree, the left subtree of any node of the balanced binary tree is empty or less than the node value, and the right subtree is empty or greater than The node value; if the root node value of the balanced binary tree is empty, then jump to step S216, if the root node value of the balanced binary tree is equal to the MD5 characteristic string, then the bill is a heavy single, jump to step S226, If the root node value of the balanced binary tree is not equal to the MD5 characteristic string, then jump to step S224;

Step S216, if the root node value of the balanced binary tree is empty, then the bill is not a duplicate, the MD5 character string is inserted into the balanced binary tree, and step S218 is implemented simultaneously;

Step S218, if the bill is not a duplicate, when inserting the MD5 characteristic string into the balanced binary tree, output the correct bill and index incremental file, and jump to step S220;

Step S220, judging whether inserting the MD5 characteristic string causes the balanced binary tree to lose balance, if it loses balance, then jump to step S222, otherwise jump to step S228;

Step S222, if the balanced binary tree is out of balance, it is adjusted by rotation; in the data structure of a balanced binary tree, the value of any node is greater than the value of its left subtree and less than the value of its right subtree, and the height of its left and right subtrees The difference is not greater than 1. When a certain value is inserted in it, the difference between its left and right subtrees may be greater than 1, so it is no longer a balanced binary tree, so it must be rotated to keep it balanced. For example, the simplest one under node 6 in Figure 3 As shown in Figure 6, the height of the left subtree of the root node 14 is 0, and the height of the right subtree is 1. When inserting node 17, the height of the left subtree of the root node 14 is 0, and the height of the right subtree is 0. It is 2, and it is no longer a balanced binary tree. It is necessary to rotate 14 to the left subtree of 17, and 17 is the root node, which is still balanced after rotation. For an unbalanced binary tree, the number of searches is more than that of a balanced binary tree. The above example shows that for an unbalanced binary tree before rotation, the number of comparisons to find 22 is 3, and for a balanced binary tree after rotation. It is 2, when the left and right child When the tree height difference is large, the difference is obvious;

Step S224, if the MD5 characteristic string is less than the root node value of the balanced binary tree, then continue to search the left subtree of the root node, if it is greater than the root node value of the balanced binary tree, then continue to search the right subtree of the root node until the same node value is found Or a certain node has no corresponding left subtree or right subtree; if the same node value is found, the bill is a duplicate order, and jumps to step S226, if there is no corresponding left subtree or right subtree, then the The bill is not a duplicate, jump to step S218; for example, the MD5 characteristic string generated by a certain bill is assumed to be 1122000000000003, as shown in Figure 7, first locate the balanced binary tree whose hash address is 11, and convert the MD5 characteristic string Compare with the value of its root node, for example, the root node A0 is 1123000000000000, and the MD5 characteristic string is smaller than the root node, then search for the root node A01 of its left subtree, if it is 11220000000000000, then continue to search for the root node A012 of the right subtree of A01 , if the value of A012 is empty, the bill is not a duplicate bill, jump to step S218, if the value of A012 is 1122000000000003, the bill is a duplicate bill, jump to step S226, otherwise continue to search for its left subtree or right subtree Tree;

Step S226, if the bill is a duplicate, delete the bill;

Step S228, after executing the process of deduplicating bills, the bill processing ends, and when the memory occupation of the bill deduplicating process exceeds the specified value, the system automatically releases the memory, and merges the index incremental files, and continues processing When a CDR file is created, the index file will be reloaded as needed.

Embodiment 2 of a method for eliminating duplication of bills of the present invention utilizes the MD5 algorithm to perform calculations on dialogue single key domain information to obtain a uniform and unique MD5 feature string, and adopts a hash table for the corresponding MD5 feature strings of normal bills Storage and hash table conflicts are resolved through a balanced binary tree, and the MD5 characteristic string is compared with the node value of the balanced binary tree to judge whether the bill is a duplicate order, and realize the picking of any business and any type of bill Heavy processing improves the operation efficiency and scalability of the deduplication system, and greatly saves storage space. The saved storage space can reach more than 50%. The processed words are stored through the combination of hash table and balanced binary tree. Single, with the characteristics of high efficiency.

Except above-mentioned embodiment, a kind of method of removing duplicates of call list of the present invention utilizes MD5 algorithm dialogue single key field information to carry out operation, obtains MD5 characteristic string, and this MD5 characteristic string adopts the mode storage of hash table, and the conflict of hash table also can pass through Linked list is used to solve, the node value of MD5 character string and linked list is compared, thereby judges whether bill is duplicate, and the method similar to above-mentioned embodiment also can realize the deduplication of bill.

Device embodiment

As shown in FIG. 8 , a structural diagram of Embodiment 1 of a bill deduplication device of the present invention is disclosed. Embodiment 1 of a bill deduplication device includes an extraction module 1 , a feature string generation module 2 , and a comparison deduplication module 3 : the extraction module 1 is used to extract the key field information from the bill; the feature string generation module 2 is used to use the MD5 algorithm to calculate the key field information to generate the MD5 feature string; the comparison module 3 is used to extract the MD5 feature String is compared with the MD5 characteristic string corresponding to the normal bill stored in the index file, if the same MD5 characteristic string is found, the bill is a duplicate bill, and the bill is eliminated; otherwise, the MD5 character string corresponding to the bill is Save the feature string to the index file, and confirm that the bill is a normal bill.

Compare and remove heavy module 3 and comprise: calculate and locate unit 4, be used for carrying out hash operation to described MD5 characteristic string according to the hash function of setting, and according to the function value gained by this operation, find the storage in the hash table Node; search unit 5, used to search the same feature string as the MD5 feature string on the storage node; duplicate unit 6, used to determine whether the bill is a heavy bill according to the result of the search, if Find the same MD5 feature string as the feature string on the storage node of the hash table, and the bill is a duplicate, and is removed; otherwise, the bill is a normal bill.

The workflow of Embodiment 1 of a call list deduplication device is described as follows:

Extraction module 1 extracts the key field information from bill, and feature string generation module 2 calculates the key field information generated in extraction module 1 according to MD5 algorithm, generates MD5 feature string, and compares the calculation location unit 4 in the deduplication module 3 according to The set hash function carries out the hash operation to the MD5 characteristic string generated by the characteristic string generation module 2, and locates the MD5 characteristic string on the balanced binary tree storing the index file according to the calculated hash function value, and the search unit 5 has completed Search the MD5 characteristic string on the balanced binary tree of location, if search unit 5 finds the MD5 characteristic string identical with described MD5 characteristic string on the balanced binary tree, remove the duplicate unit 6 and then determine that the bill is a heavy single, and the repeated single is eliminated, and the search unit 5. If no MD5 signature string identical to the MD5 signature string is found on the balanced binary tree, the deduplication unit 6 determines that the bill is not a duplicate bill.

Embodiment 1 of a bill deduplication device of the present invention combines the advantages of hash table, balanced binary tree and MD5 algorithm, effectively realizes the processing of different services and different types of bills, and generates a uniform and unique MD5 characteristic string , which improves the efficiency of deduplicating call lists and greatly saves storage space.

As shown in Fig. 9, the structural diagram of Embodiment 2 of a bill deduplication device of the present invention is disclosed. Embodiment 2 of a bill deduplication device of the present invention includes the first embodiment All modules. In addition, the comparison and deduplication module also includes an insertion unit 7 and a rotation unit 8. The bill deduplication device also includes a loading module 9: the insertion unit 7 is used to convert the MD5 feature if the deduplication unit 6 determines that the bill is not a duplicate. The string is inserted into the balanced binary tree, and the correct call list and index incremental file are output simultaneously. The rotation unit 8 is used to adjust the balanced binary tree by rotating the balanced binary tree through the rotation unit 8 if the MD5 characteristic string inserted by the insertion unit 7 makes the balanced binary tree unbalanced. Module 9 is used to reload the index file from disk to memory as needed.

The workflow of Embodiment 2 of a kind of call list deduplication device is described as follows:

Extraction module 1 extracts key field information from bill, such as calling number, called number, call time, SP code and other field combinations of any one or several combinations, and the corresponding MD5 feature string of normal bill is hashed The table is stored in the index file, and the index file is stored in the memory or disk, and the conflict of the hash table is solved by balancing the binary tree; the feature string generation module 2 performs the key domain information generated in the extraction module 1 according to the MD5 algorithm. Compute, generate MD5 feature string, compare the calculation positioning unit 4 in the deduplication module 3 to carry out the hash operation to the MD5 feature string generated by the feature string generating module 2 according to the hash function set, and according to the calculated hash function value will The MD5 characteristic string is positioned on the balanced binary tree as the storage node of the hash table, and the search unit 5 searches for the MD5 characteristic string on the balanced binary tree that has been positioned. If the search unit 5 finds the MD5 characteristic string on the balanced binary tree Identical MD5 characteristic strings, the repeated unit 6 then determines that the bill is a heavy single, and the repeated singles are removed, if the search unit 5 does not find the MD5 characteristic strings identical with the MD5 characteristic strings on the balanced binary tree, the repeated unit 6 then determines The bill is not a duplicate, and the search unit 5 searches the process of the MD5 characteristic string on the balanced binary tree specifically as described in method embodiment step S214, step S216, and step S224; if the duplicate unit 6 determines that the bill is not a duplicate, the insertion unit 7 The MD5 feature string is inserted into the balanced binary tree, and the correct call list and index incremental file are output simultaneously. If the MD5 feature string inserted by the insertion unit 7 makes the balanced binary tree unbalanced, the rotation unit 8 adjusts the balanced binary tree by rotating it. After the process of repeating the bill, the bill processing ends. When the memory usage of the bill deduplication process exceeds the specified value, the bill deduplication device automatically releases the memory and merges the index incremental files, and continues to process the next bill file, the load module 9 will reload the index file as needed.

Embodiment 2 of a bill deduplication device of the present invention uses the MD5 algorithm to perform calculations on dialogue single key field information to obtain a uniform and unique MD5 feature string, and the MD5 feature string corresponding to a normal bill is stored in a hash table. The conflict of the hash table is solved by balancing the binary tree, and comparing the MD5 characteristic string with the node value of the balanced binary tree, so as to judge whether the bill is a duplicate order, and realize the duplicate processing of any business and any type of bill , which improves the operation efficiency and scalability of the deduplication system, and greatly saves storage space.

Except above-mentioned embodiment, a kind of phone list of the present invention removes heavy device, compares the calculation in the heavy module and determines that in the unit, linked list can also be used as the storage node of hash table, and the node value of MD5 characteristic string and linked list is compared, From this, it is judged whether the bill is a duplicate bill, and the structure similar to the above embodiment can also realize the function of removing duplicate bills.

The above disclosures are only a few specific embodiments of the present invention, however, the present invention is not limited thereto, and any changes conceivable by those skilled in the art shall fall within the protection scope of the present invention.

Claims (13)

1. A method for removing duplicates from a bill, is characterized in that the method may further comprise the steps: Step a: extract key field information from the bill; Step b: use the MD5 algorithm to calculate the key field information, and generate the MD5 feature string corresponding to the bill; Step c: comparing the MD5 feature string with the MD5 feature string stored in the index file and corresponding to the normal bill; If identical MD5 characteristic strings are found, the bill is a duplicate, and the bill is removed; otherwise, the MD5 characteristic string corresponding to the bill is saved in the index file, and the bill is confirmed to be a normal bill. 2. according to the described method of claim 1, it is characterized in that, the MD5 characteristic string corresponding to the normal bill is stored in the index file in the mode of hash table; Described step c specifically comprises: Step c1: perform a hash operation on the MD5 characteristic string corresponding to the bill according to a set hash function; Step c2: Find the storage node in the hash table according to the function value obtained by the hash operation; Step c3: If the MD5 characteristic string identical to the MD5 characteristic string corresponding to the bill is found on the storage node, Then the bill is a duplicate bill, and the bill is eliminated; otherwise, the MD5 characteristic string corresponding to the bill is inserted into the storage node, and the bill is confirmed to be a normal bill. 3. the method for eliminating duplicates according to claim 2, is characterized in that, the MD5 characteristic string in the storage node in the said hash table is stored in the mode of linked list or the mode of balanced binary tree. 4. according to the described method of claim 3, it is characterized in that, when the MD5 characteristic string in the storage node in the said hash table is stored in the mode of balanced binary tree, in said step c3, said The step of inserting the MD5 characteristic string corresponding to the bill into the storage node specifically includes: The MD5 characteristic string is inserted into the balanced binary tree on the storage node, and if the inserted MD5 characteristic string makes the balanced binary tree unbalanced, adjustment is performed by rotation. 5. The method for deduplicating bills according to any one of claims 1-4, characterized in that, when the bills are normal bills, the bills are output, and an updated index increment file is output. 6. The method for removing duplicates from the bill according to claim 5, wherein the index file and the index increment file are stored in memory or disk. 7. according to the described method of claim 6, it is characterized in that, if the memory usage exceeds the specified value, then merge the index increment file, store the earlier part in the index file in the disk, and release automatically memory; if the index file in the disk needs to be reloaded into the memory, reload it. 8. According to the method for eliminating duplicates according to any one of claims 1-4, it is characterized in that, the key domain information includes: in the combination field made up of calling number, called number, call time, SP code Any one or combination of several. 9. A bill-removing device, characterized in that it comprises: An extraction module, used to extract key field information from the bill; A feature string generation module, configured to use the MD5 algorithm to calculate the key field information to generate an MD5 feature string; Compare duplicate module: be used for comparing described MD5 feature string with the MD5 feature string corresponding to the normal call list stored in the index file; If find identical MD5 characteristic string, then this bill is duplicate bill, and this bill is removed; Otherwise the MD5 characteristic string corresponding to this bill is saved in the index file, and confirms that this bill is normal bill. 10. The bill deduplication device according to claim 9, characterized in that, the comparison deduplication module includes: Calculation and positioning unit, used to carry out hash operation on the MD5 characteristic string according to the set hash function, and find the storage node in the hash table according to the function value obtained by the operation; A search unit, configured to search for a signature string identical to the MD5 signature string on the storage node; A duplicate removal unit is used to determine whether the bill is a duplicate bill according to the result of the search, if the MD5 characteristic string identical to the MD5 characteristic string is found on the storage node of the hash table, the bill If it is a duplicate bill, remove it; otherwise, the bill is a normal bill. 11. The bill deduplication device according to claim 10, wherein the storage node of the hash table is a linked list or a balanced binary tree. 12. The bill deduplication device according to claim 10 or 11, wherein when the storage node in the hash table is a balanced binary tree, the comparison deduplication module further includes: Insertion unit, for inserting the MD5 feature string corresponding to the normal bill into the balanced binary tree, and simultaneously output the normal bill and its index incremental file; A rotation unit is configured to rotate the balanced binary tree through the rotation unit to adjust if the balanced binary tree is unbalanced when the MD5 character string is inserted into the balanced binary tree. 13. The phone bill deduplication device according to claim 9, further comprising a loading module, configured to reload the index file in the disk to the memory as required.

Images