CN115204147A - Data feature fingerprint construction and similarity measurement method and index - Google Patents

Abstract

The invention discloses a data characteristic fingerprint construction method based on a bloom filter, which is characterized in that a data characteristic set is mapped to a bit vector space with a fixed length, and all characteristics contained in data are uniformly characterized; the space complexity of the data feature set is effectively reduced to a constant level, and the storage cost of high-dimensional data features in the current big data is effectively reduced. The data feature similarity calculation adopts the Hamming distance of two fixed-length bit vectors to calculate, so that the similarity of data on features can be effectively represented, the complexity magnitude of the calculation is reduced, and the calculation efficiency is improved. For mass data feature similarity measurement, a data feature fingerprint index is constructed in an inverted index mode, corresponding feature fingerprints are segmented only, and then the segment of fingerprints are stored in a data feature inverted index database as index keys, so that similar data can be retrieved, and the data fingerprint retrieval matching efficiency is further improved.

Description

A Data Feature Fingerprint Construction and Similarity Measurement Method and Index

technical field

The invention relates to a data feature fingerprint, in particular to a data feature fingerprint construction and similarity measurement method and index.

Background technique

The traditional test data feature extraction and identification methods focus on the processing of test data of a single category or mode, including numerical calculation, correlation analysis, etc., to obtain the characteristics of the test data object, and to perform correlation and retrieval through the characteristics.

According to statistics, global data traffic reached 180 and 230 exabytes per month in 2019 and 2020, respectively, and it is expected that by 2026, this data will increase to 780 exabytes per month. Fixed data traffic accounted for nearly 75% of all data traffic in 2019, and mobile broadband data traffic is expected to grow rapidly as the number of mobile terminals and IoT devices increases, reaching nearly one-third of total data traffic by 2026 . With the rapid growth of data volume and wide application of data, the corresponding feature scale also grows rapidly, and there is an urgent need for data multidimensional feature representation and similarity measurement. However, the existing multi-dimensional feature representation and similarity measurement methods face the problems of complex calculation, high time overhead and high maintenance cost.

At present, there are many methods and implementation techniques for data similarity measurement, such as Sorensen-Dice coefficient, Jaro-Winkler distance, Shingle set similarity, cosine distance, etc. The main disadvantages are:

(1) High computational complexity: it is necessary to calculate the similarity of all features contained in data U and data V to return the result, and its complexity is O(uv), where u and v represent the feature values in data U and data V the number of;

(2) The cost of data feature storage space is high: all features of any data need to be stored. Since the number of feature values is not a fixed length, its storage needs to be selected according to different databases, resulting in additional space occupation. If you choose a relational database (RDBMS), you often need to add a table to any data to store data features;

(3) The calculation process relies on the original data characteristic values, and there is a hidden danger of sensitive data leakage.

Regarding data fingerprinting technologies, such as MD5 hashing, local-sensitive hashing, similar hashing, etc., data fingerprints are constructed by mapping original data of arbitrary length into hash values of fixed length through different hash functions, which can effectively solve the calculation problem. Complexity, storage cost and other issues, and the hash itself does not contain the semantic information of the feature, so it can protect the security of sensitive data.

However, this type of method is mainly aimed at the similarity of data files, and it is difficult to be directly used for the construction of data feature fingerprints. Its main disadvantages are:

(1) Scalability defects: when a certain data has multi-dimensional features, it is necessary to hash the multi-dimensional features one by one and build fingerprints, which will lead to a large amount of redundancy in the data feature fingerprint library;

(2) Poor maintainability: when a certain data is analyzed to obtain new features, it is difficult for the original data fingerprint to support the insertion of new data features;

(3) It is difficult to support the construction of feature fingerprints of heterogeneous data and cross-modal data: Since this type of method is mainly aimed at the content of data files, it is difficult to reflect the similarity in features of heterogeneous data and cross-modal data with similar characteristics. . For example, text data and image data that describe the same object have completely different data content but have similarities in data. Existing data fingerprinting technology is difficult to support cross-modality data similarity measurement.

Therefore, there is an urgent need to propose a multi-dimensional feature fingerprint construction for experimental data and a rapid measurement method of data feature similarity to meet application requirements such as duplicate or similar data feature detection, feature-based data retrieval query, and data association identification.

SUMMARY OF THE INVENTION

In order to solve the deficiencies of the prior art, the purpose of the present invention is to provide a method for constructing a data feature fingerprint, which constructs a data feature fingerprint of a fixed length, and supports the maintenance of newly generated data features, so as to accurately reflect the data features and support data heterogeneity. , cross-modality and other complex data applications; and a similarity measurement method is provided, which supports the similarity measurement of the feature fingerprint constructed by the present invention, thereby supporting the needs of data query and retrieval.

In order to achieve above-mentioned goal, the present invention adopts following technical scheme:

A data feature fingerprint construction includes the following steps:

S1. Use the TF-IDF method to extract features (words) from the data;

S2. Based on the Bloom filter structure, the features (words) of different data are mapped to the corresponding BF bit vector table through hash operation, and the sequence composed of 0 and 1 in the final bit vector is used as the fingerprint output of the data feature .

The TF-IDF method used in the above-mentioned step S1 includes the following steps:

A1. Calculate the word frequency TF of the extracted data features by the following formula (1):

Among them, i represents the index of the word, j represents the text index of the data, n _i,j represents the number of times the i-th word appears in the j-th text, and the denominator represents the total number of words in the j-th text; that is, the TF value is the ratio of the frequency of a word in a text to the total number of words in the text;

A2. Calculate the inverse text frequency IDF by the following formula (2):

Among them, M represents the total number of texts, m _i represents the number of texts containing the i-th word, and ɑ represents the empirical coefficient, generally 0.01;

A3. The TF-IDF weight corresponding to the feature item of each text vector is calculated by the following formula (3):

TFIDF _i,j =TF _i,j ·IDF _i (3)

A4. After calculating the weight of each feature item using the TF-IDF weight method, select data with a larger weight as the feature of the text.

The above step S1 also includes step S10, preprocessing the data to be extracted, including:

B1. Cleaning data: Take text data as an example, including deleting HTML tags, non-alphanumeric characters, special characters and accented characters, and stop words;

B2. Abbreviations in extended data.

The above step S1 also includes step S12, sorting the extracted features to standardize the features, including the following steps:

C1. Use cosine similarity to calculate the similarity between different features;

C2. Set the similarity threshold;

C3. Compare the features in pairs; if the similarity is greater than the threshold, delete the duplicate features;

C4. Repeat step C3 until the feature (descriptor) is unique.

The calculation of the cosine similarity in the above step C1 is specifically:

Calculate the distance between text feature vectors to obtain the similarity between texts; in general, the closer the distance between two text vectors, the more similar the two texts are;

The cosine similarity is used to calculate the similarity between different features, and the formula is:

Among them, A=(x ₁ , x ₂ ,...x _n ), B=(y ₁ , y ₂ ,... y _n ), which are text vectors.

In the above step S2, the data features are hashed and mapped to the corresponding bit vector table of the BF, specifically:

Given a set of data sets A={a ₁ , a ₂ , ... a _n }, use k hash functions {h ₁ , h ₂ , ... h _k } to obtain the index values of the data features to be inserted h _i (a _j ), where i∈[1,k], j∈[1,n];

In the initial state, all values in the bit vector table are set to 0; when inserting, the bit vector values of the k positions corresponding to the index value h _i (a _j ) are set to 1;

The sequence composed of 0 and 1 in the final bit vector table is output as the fingerprint of the data feature.

Applicable to the above similarity measurement method of data feature fingerprints, since the same features of different data can be hashed to the same position of the BF, the more the same feature values contained in the data, the Hamming distance of the feature fingerprints corresponding to the two data. will be shorter, so the similarity of data features can be measured by Hamming distance. The steps include:

D1. Select fingerprints of any two data features from the data feature fingerprint set;

D2. Calculate the Hamming distance between two data feature fingerprints;

D3. Measure the similarity of two data features based on the Hamming distance.

The index applicable to the above-mentioned data feature fingerprints, including the establishment of an inverted index library, includes the following steps:

段；F1. Number the data respectively, take c as the segment length, and divide the feature fingerprint of the data with length m into

part;

F2. Take the fingerprint value of each segment as the fingerprint segment value and use it as the index key;

F3. Use the data number with the same fingerprint segment value in the same segment as the index value;

F4. The data feature fingerprint is stored in the feature fingerprint index table with <fingerprint segment value, data number> as a key-value pair to form an inverted index library.

Search, including the following steps:

段；G1. Divide the feature fingerprint of the data to be retrieved, with c as the segment length, into

part;

G2. Index with the fingerprint segment value and obtain the data number of each segment;

G3. Add the data number to the collection;

次的数据，h为汉明距离；G4, the number of occurrences of the search number is greater than

times data, h is the Hamming distance;

G5. Use formula (5) to calculate the similarity between the features of the data to be retrieved and the existing features in the index database:

In the formula, it is assumed that the segment length c is 4, and num marks whether the corresponding fingerprint number appears each time it is extracted. If it appears, num(b) is 1, otherwise it is 0.

The benefits of the present invention are:

(1) The space utilization rate is high. The method for constructing a data feature fingerprint based on the Bloom filter proposed by the present invention, by mapping the data feature set to a fixed-length bit vector space, uniformly characterizes all the features contained in the data; effectively the complex space of the data feature set is The degree is reduced from O(N) to a constant level, which effectively reduces the storage cost of high-dimensional data features in current big data. At the same time, when adding data features, the data features are still mapped to a fixed-length bit vector, and no additional storage space cost is required.

(2) The computational complexity is low. The data similarity measurement method proposed by the present invention uses the Hamming distance to judge the similarity between features. For multi-dimensional data features, by building a data feature fingerprint database and storing data feature fingerprints in blocks, the traditional method of hashing multi-dimensional features one by one and constructing fingerprints causes a large number of data feature fingerprint redundancy problems, and also reduces data features. The number of pairwise comparisons. And for the problem that the data content of the same object is different in different modalities but the data features are similar, the data feature fingerprint construction based on Bloom filter can map the data to the same dimension to support the cross-modal data similarity measurement. By using the Hamming distance of two fixed-length bit vectors for calculation, it can not only effectively characterize the similarity degree of data in features, but also reduce the computational complexity to O(1) level, which greatly improves the similarity measurement of massive data. s efficiency.

(3) Scalability and maintainability. Since the data feature fingerprint is constructed by using the Bloom filter, when a new data feature is generated after analysis or labeling, it is only necessary to add the newly generated data feature to the data feature fingerprint, and it is not necessary to recalculate all the feature fingerprints.

(4) Sensitive data security. Since any fingerprint is hashed using different hash functions, and the hash itself does not contain the semantic information of the feature, it can protect the security of sensitive data and prevent data leakage.

(5) Fingerprint indexing efficiency. Using the inverted index method to construct the data feature fingerprint index, it only needs to segment the corresponding feature fingerprint, and then save the segment fingerprint as the index key in the data feature inverted index database, and then the similar data can be retrieved. The traditional pairwise comparison method saves a lot of time and further improves the efficiency of data fingerprint retrieval and matching. In addition, the present invention constructs data fingerprints according to data features, which can reduce the dimensionality of the features of multimodal data and construct data feature fingerprints with unified dimensions, thereby effectively solving the problem of heterogeneous and difficult cross-modal retrieval.

Description of drawings

Figure 1 shows the initial state of the Bloom filter.

FIG. 2 is a schematic diagram of interpolating index values into corresponding bit vectors.

FIG. 3 is a schematic diagram of inserting an added feature into a corresponding bit vector.

FIG. 4 is a schematic diagram of constructing an inverted index library.

Detailed ways

The present invention will be described in detail below with reference to the accompanying drawings and specific embodiments.

Take text data as an example.

Text data usually consists of documents, which contain a large number of words, sentences, and texts. Since text documents have no fixed structure, and compared with structured data, the sentence lengths of text documents are also different, so when extracting data features, the data should be cleaned first, and special characters such as HTML tags and non-alphanumeric characters should be removed. and accented characters that are of little value to the content of the document. At the same time, when extracting data features, words with little meaning are generally called stop words. Such words are usually words that appear with the highest frequency in the document, such as a, an, the, etc. Stop words are identified in the text and deleted. . Then expanding the abbreviations in the text contributes to the normalization of the text (S10).

Data feature fingerprint construction:

S1. Use the TF-IDF method to extract features (words) from the data:

A1. Term frequency (TF) is calculated by the following formula:

Among them, i represents the index of the word, j represents the text index of the data, n _i,j represents the number of times the i-th word appears in the j-th text, and the denominator represents the total number of words in the j-th text; that is, the TF value is the ratio of the frequency of a word in a text to the total number of words in the text;

A2. The inverse document frequency (IDF) is calculated by the following formula:

Among them, M represents the total number of texts, m _i represents the number of texts containing the i-th word, and ɑ represents the empirical coefficient, which is generally taken as 0.01, in order to prevent the denominator from being 0;

A3. The TF-IDF weight corresponding to the feature item of each text vector is calculated by the following formula (3):

TFIDF _i,j =TF _i,j .IDF _i (3)

It can be seen from the above formula that when a word appears frequently in a single text and rarely appears in other texts, the TF-IDF value of the word will be very large;

A4. After calculating the weight of each feature item using the TF-IDF weight method, select data with a larger weight as the feature of the text.

Next, the obtained data features are preliminarily sorted to standardize the data features. By judging the feature similarity and removing duplicate or similar feature descriptors, the data features can be made clearer, and the computational load of the subsequent fingerprint similarity judgment of the data features can be saved. The standardization of data features is mainly to delete the duplicate or similar feature descriptors of the same data. Proceed as follows:

S12. Calculate the distance between the text feature vectors, thereby obtaining the similarity between the texts. Generally speaking, the closer the distance between two text feature vectors, the more similar the two texts are. The cosine similarity is used to judge the similarity between different features (step C1), and the formula is:

Among them, two text vectors A=(x ₁ , x ₂ , . . . x _n ), B=(y ₁ , y ₂ , . . . y _n ).

Then set the similarity threshold (step C2); compare the features pairwise, if the similarity is greater than the threshold, delete other similar features and keep only the unique feature (step C3); repeat the steps until the feature (descriptor) is unique (step C3) C4).

Design Algorithm 1: Data Feature Normalization

Input: test data DSn, feature extraction threshold σ ₁ , similarity threshold σ ₂ , feature set S _t

Output: data features

S2. Obtain the index values of different features (words) of the data through hash operation, insert the index values into the corresponding bit vector table using a Bloom filter, and use the sequence composed of 0 and 1 in the final bit vector as the data feature fingerprints; specifically:

As a probabilistic data structure, BF is given a set of data sets A={a ₁ , a ₂ ,...a _n }, using k hash functions {h ₁ , h ₂ ,...h _k } to get The index value hi (a _j ) of the data to be inserted, where _i∈ [1,k], j∈[1,n]. In the initial state, all values in the bit vector table are set to 0, and when inserting, the bit vector values of k positions corresponding to the index value h _i (a _j ) are set to 1. If the position corresponding to the index value is already 1, it means that a hash collision has occurred at this time, and an element has been mapped to this position before, and the value of the corresponding position will not be modified this time. The sequence composed of 0 and 1 in the final bit vector table is output as the fingerprint of the data feature.

In actual operation,

About Bloom filter parameter setting and initialization:

If the length of the bit vector of the Bloom filter is too small, the probability of mapping to the same bit vector is very high when inserting data features, that is, the probability of false positive is very large. As the amount of data increases, the probability of false positive may reach 1.

In order to reduce the density of large data features and reduce hash collisions when representing large data features, the bit vector length of the Bloom filter should be large enough. A longer Bloom filter also ensures the accuracy of similarity detection in subsequent hash maps. When initializing the Bloom filter, for a bit array of length m, all bit vector values are set to 0, where the size of m is related to the size of the data feature. The initial state of the Bloom filter is shown in Figure 1, where The length of m is chosen to be 19.

About calculating the data feature hash value:

The number of k independent hash functions used in mapping also needs to be weighed. The larger the number, the faster the Bloom filter mapping speed will be, but the execution efficiency will be reduced, while too few hash functions will increase the false positive rate.

According to the false positive probability of Bloom filter, when k=(m/n)ln2, the false positive rate is the lowest, and the number of hash functions is the ratio of ln2 times the bit vector size to the data feature element n. At the same time, if the performance of the hash function is too low, it will also affect the computational efficiency. Commonly used hash functions include MurmurHash, FNV, and MD5.

After the data feature standardization in the first stage, each data has a feature set, such as data A={feature 1, feature 2, feature 3}, and then use the hash function {h ₁ , h ₂ , ...h _k } obtains the index value of the data to be inserted, and the index value corresponds to the array subscript that needs to be set to 1 in the bit vector. As shown in Figure 2, feature 1 of data A uses hash functions h ₁ (x) and h ₂ (x) to map features to bits 4 and 9 of the bit vector, and feature 2 is mapped to bits 2 and 2 14 bits, feature 3 is mapped to bits 10 and 17.

About generating data feature fingerprints:

For each data, after mapping the data features to a fixed-length bit vector, a string of 0 and 1 will be obtained, as shown in Figure 2, the bit vector of data A becomes "0100100001100010010" after mapping , use this string as the data feature fingerprint.

If the data is analyzed to obtain new features, it is only necessary to map the new features to the bit vector using the same k hash functions as other features, and it is not necessary to add new spatial storage features, as shown in Figure 3.

Design Algorithm 2: Data Feature Fingerprint Construction

Input: bit array length m, hash function k, data feature set S

Output: Data Feature Fingerprint

The Bloom filter can quickly determine whether the data is in the collection without obtaining the data content, which effectively protects data privacy. At the same time, when querying members, the Bloom filter will not have false negatives, which can be used in some occasions where it is necessary to quickly determine whether a certain data belongs to a certain set but does not require a high accuracy rate.

In addition, the Bloom filter queries membership with constant-level complexity, and its space efficiency and query time are far less than other data structures, making up for the shortcomings of traditional hash table queries.

At the same time, since the data features in most existing applications are generally incrementally expanded, and there is almost no feature deletion, the maintenance requirement of the feature fingerprint is mainly the insertion of newly generated features. The use of Bloom filters to construct data feature fingerprints can maximize the use of the incremental characteristics of data features, which not only maintains the advantages of the Bloom filter in terms of space utilization and query efficiency, but also avoids the maintainability of deletion operations. cost.

Data feature similarity measure:

Hamming Distance is often used for data transmission error control coding. It indicates that two codewords of the same length correspond to different numbers of bits. For a binary string a and b, the Hamming distance is equal to a XOR b The number of 1's in the result of the operation.

For example, for a string sequence of length n a=(a ₁ , a ₂ ··· a _n ) and b=(b ₁ , b ₂ ··· b _n ), the Hamming distance is calculated as follows:

The similarity of data features can be measured by the Hamming distance between a pair of BF bit vectors. Since the same features of different data can be hashed to the same position of the BF, the more the data contains the same feature values, the shorter the Hamming distance of the feature fingerprints corresponding to the two data.

For example, the bit vector string corresponding to data A is "0100100001100010010", the bit vector string corresponding to data B is "0001100001101010010", and data C is "0001100111000101001", the Hamming of data A and data B after characterization can be obtained. The distance is 4, and the Hamming distance between data A and data C after characterization is 10, so data A and data C have a shorter Hamming distance, that is, data A and data C have more similar data features.

Therefore, the similarity of data features can be effectively measured by the Hamming distance. The steps are:

D1. Select the feature fingerprints of any two data from the data feature fingerprint set;

D2. Calculate the Hamming distance between two data feature fingerprints;

D3. Measure the similarity of two data features based on the Hamming distance.

Design Algorithm 3: Data Feature Similarity Measurement

Input: data feature fingerprint set Fn

Output: data feature similarity

for(i=0; i<n; i++)do

Output Result

Existing data similarity detection technologies include Shingle, Min-Wise and Mins technologies, which are simple and easy to implement and have wide applicability, but there are still certain defects: For example, Shingle technology uses two document data consecutive words to form the intersection of vocabulary and calculates documents. The similarity and inclusion of the algorithm are very high, and the computational cost is very high; the use of Bloom filter for similar data detection can make up for the high computational and storage space cost caused by the similarity of files calculated by the intersection of feature sets in Shingle. Balance between matching accuracy.

In addition, when the heterogeneous data has similar data features in multiple modalities, in the face of a large amount of data features, the traditional pairwise comparison method of data features will cause great computational resource overhead, so the combination of the inverted index retrieval method can be used. Make the data feature similarity discrimination more efficient.

The construction of the index database of data feature fingerprints is to make up for the shortage of a large amount of computing resources consumed by one-by-one comparison in the fingerprint database, so as to improve the speed of similarity measurement. It includes the establishment of the inverted index database and the fast retrieval based on the inverted index database.

The construction of the inverted index library, as shown in Figure 4, includes the following steps:

段，若两个数据特征化后指纹汉明距离小于等于n，则在分段后至少有8-n段的数值是相同的；F1. First perform segment operation on the fingerprint value of the existing data features in each modality: assuming that the fingerprint value after data characterization has m bits (the value of m is related to the size of the data feature, here is 32 bits), Take 4 bits (that is, c=4) as a group, which are divided into

If the Hamming distance of the fingerprints after the characterization of the two data is less than or equal to n, then at least 8-n segments have the same value after the segmentation;

F2. Take the fingerprint value of each segment as the fingerprint segment value and use it as the index key;

F3. Use the data number with the same fingerprint segment value in the same segment as the index value;

F4. The data feature fingerprint is stored in the feature fingerprint index table with <fingerprint segment value, data number> as a key-value pair to form an inverted index library.

Algorithm Design 4: Build an Inverted Index Library

Input: data feature fingerprint set Fn, fingerprint bits m, bits per block c

Output: data feature index table <key, value>

段(步骤G1)；然后以每一段的指纹值(指纹段值)作为索引键，在倒排索引库中查找每一段对应的索引值(步骤G2)，该索引值为每一个对应的数据编号集合(步骤G3)；在查找完每一块的集合后，仅需提取次数不低于

次的指纹编号，使用提取时每个指纹编号出现的次数与提取总次数的比作为检索数据特征与数据特征指纹库中已有数据特征的相似性，具体公式为：Quick retrieval, segment the fingerprint value of the newly generated data feature or the fingerprint value of the data feature in other modalities, and also divide it into

segment (step G1); then use the fingerprint value (fingerprint segment value) of each segment as the index key, search for the index value corresponding to each segment in the inverted index library (step G2), the index value is each corresponding data number Set (step G3); after finding the set of each block, only the number of times of extraction is not less than

The ratio of the number of occurrences of each fingerprint number to the total number of times of extraction is used as the similarity between the retrieved data feature and the existing data feature in the data feature fingerprint database. The specific formula is:

Among them, num marks whether the corresponding fingerprint number appears each time it is extracted, if it appears, num(b) is 1, otherwise it is 0.

Algorithm Design 5: Data Feature Search (Quick Search)

Input: data feature fingerprint f, fingerprint number m, number of bits per block c, Hamming distance h

Output: data feature number

The foregoing has shown and described the basic principles, main features and advantages of the present invention. Those skilled in the art should understand that the above-mentioned embodiments do not limit the present invention in any form, and all technical solutions obtained by means of equivalent replacement or equivalent transformation fall within the protection scope of the present invention.

Claims (9)

1. a data feature fingerprint construction, is characterized in that, comprises the following steps: S1. Use the TF-IDF method to perform feature extraction on the data; S2. Based on the Bloom filter structure, the features of different data are mapped to the bit vector table corresponding to the BF through a hash operation, and the sequence formed by 0 and 1 in the final bit vector is output as the fingerprint of the data feature. 2. data feature fingerprint construction according to claim 1, is characterized in that, the use TF-IDF method in described step S1, comprises the following steps: A1. Calculate the word frequency TF of the extracted data features by the following formula (1):

Among them, i represents the index of the word, j represents the text index of the data, n _i,j represents the number of times the i-th word appears in the j-th text, and the denominator represents the total number of words in the j-th text; that is, the TF value is the ratio of the frequency of a word in a text to the total number of words in the text; A2. Calculate the inverse text frequency IDF by the following formula (2):

Among them, M represents the total number of texts, m _i represents the number of texts containing the i-th word, and ɑ represents the empirical coefficient, generally 0.01; A3. The TF-IDF weight corresponding to the feature item of each text vector is calculated by the following formula (3): TFIDF _i,j =TF _i,j ·IDF _i (3) A4. After calculating the weight of each feature item using the TF-IDF weight method, select data with a larger weight as the feature of the text. 3. The data feature fingerprint construction according to claim 1, wherein the step S1 further comprises a step S10, preprocessing the data to be extracted, including: B1. Cleaning data: Take text data as an example, including deleting HTML tags, non-alphanumeric characters, special characters and accented characters, and stop words; B2. Abbreviations in extended data. 4. The data feature fingerprint construction according to claim 1, wherein the step S1 further comprises a step S12, sorting the extracted features to standardize the features, comprising the following steps: C1. Use cosine similarity to calculate the similarity between different features; C2. Set the similarity threshold; C3. Compare the features in pairs; if the similarity is greater than the threshold, delete the duplicate features; C4. Repeat step C3 until the feature is unique. 5. data feature fingerprint construction according to claim 4, is characterized in that, the calculation of cosine similarity in described step C1, is specifically: Calculate the distance between text feature vectors to obtain the similarity between texts; in general, the closer the distance between two text vectors, the more similar the two texts are; The cosine similarity is used to calculate the similarity between different features, and the formula is:

Among them, A=(x ₁ , x ₂ ,...x _n ), B=(y ₁ , y ₂ ,... y _n ), which are text vectors. 6. data feature fingerprint construction according to claim 1 is characterized in that, in described step S2, data feature is hashed and mapped in the corresponding bit vector table of BF, specifically: Given a set of data sets A={a ₁ , a ₂ , ... a _n }, use k hash functions {h ₁ , h ₂ , ... h _k } to obtain the index values of the data features to be inserted h _i (a _j ), where i∈[1,k], j∈[1,n]; In the initial state, all values in the bit vector table are set to 0; when inserting, the bit vector values of the k positions corresponding to the index value h _i (a _j ) are set to 1; The sequence composed of 0 and 1 in the final bit vector table is output as the fingerprint of the data feature. 7. is applicable to the similarity measuring method of the data characteristic fingerprint of any one of claim 1-6, it is characterized in that, Since the same features of different data can be hashed to the same position of the BF, the more the same feature values are contained in the data, the shorter the Hamming distance of the feature fingerprints corresponding to the two data will be, so the Hamming distance can be used to compare the data features. Similarity is measured, and the steps include: D1. Select fingerprints of any two data features from the data feature fingerprint set; D2. Calculate the Hamming distance between two data feature fingerprints; D3. Measure the similarity of two data features based on the Hamming distance. 8. be applicable to the index of the data characteristic fingerprint of any one of claim 1-6, it is characterized in that, also comprise the establishment of inverted index library, comprise the following steps: F1. Number the data respectively, take c as the segment length, and divide the feature fingerprint of the data with length m into

part; F2. Take the fingerprint value of each segment as the fingerprint segment value and use it as the index key; F3. Use the data number with the same fingerprint segment value in the same segment as the index value; F4. The data feature fingerprint is stored in the feature fingerprint index table with <fingerprint segment value, data number> as a key-value pair to form an inverted index library. 9. retrieval, is characterized in that, is applicable to the described inverted index library of claim 8, comprises the following steps: G1. Divide the feature fingerprint of the data to be retrieved, with c as the segment length, into

part; G2. Index with the fingerprint segment value and obtain the data number of each segment; G3. Add the data number to the collection; G4, the number of occurrences of the search number is greater than

times data, h is the Hamming distance; G5. Use formula (5) to calculate the similarity between the features of the data to be retrieved and the existing features in the index database:

In the formula, it is assumed that the segment length c is 4, and num marks whether the corresponding fingerprint number appears each time it is extracted. If it appears, num(b) is 1, otherwise it is 0.

Images