CN114780801B - A method for constructing a sparse lookup table - Google Patents
A method for constructing a sparse lookup table Download PDFInfo
- Publication number
- CN114780801B CN114780801B CN202210465837.8A CN202210465837A CN114780801B CN 114780801 B CN114780801 B CN 114780801B CN 202210465837 A CN202210465837 A CN 202210465837A CN 114780801 B CN114780801 B CN 114780801B
- Authority
- CN
- China
- Prior art keywords
- lookup table
- node
- splut1
- node2
- sparse lookup
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9024—Graphs; Linked lists
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/903—Querying
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F18/00—Pattern recognition
- G06F18/20—Analysing
- G06F18/25—Fusion techniques
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Data Mining & Analysis (AREA)
- Databases & Information Systems (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Bioinformatics & Cheminformatics (AREA)
- Evolutionary Computation (AREA)
- Evolutionary Biology (AREA)
- Computer Vision & Pattern Recognition (AREA)
- Bioinformatics & Computational Biology (AREA)
- Artificial Intelligence (AREA)
- Computational Linguistics (AREA)
- Life Sciences & Earth Sciences (AREA)
- Software Systems (AREA)
- Complex Calculations (AREA)
Abstract
本发明提供一种稀疏查找表的构建方法，属于计算机技术、数据结构与算法有关的技术领域。该稀疏表通过同时复用父结点和复用子结点，在给定许多形如“[[0，1，2，...，ni1]，[0，1，2，...，ni2]，...，[0，1，2，...，nim]]→Vi”的特征序列转换为稀疏查找表时，构建一个有向无环图，该图占用尽可能少的存储空间存储数据，并确保计算机通过在该有向无环图上搜索，能在常数时间访问到对应的值。本发明能够达到存储空间资源利用的最优化。
The present invention provides a method for constructing a sparse lookup table, and belongs to the technical fields related to computer technology, data structure and algorithm. The sparse table simultaneously reuses parent nodes and reuses child nodes, and when a given number of feature sequences in the form of "[[0, 1, 2, ..., n i1 ], [0, 1, 2, ..., n i2 ], ..., [0, 1, 2, ..., n im ]]→V i " are converted into a sparse lookup table, a directed acyclic graph is constructed, and the graph occupies as little storage space as possible to store data, and ensures that a computer can access a corresponding value in a constant time by searching on the directed acyclic graph. The present invention can achieve the optimization of storage space resource utilization.
Description
Technical Field
The invention relates to a new Lookup Table (Lookup-Table) data structure, in particular to a method for constructing a Lookup Table data structure with sparse storage space, belonging to the technical fields of computer technology, data structure and algorithm.
Background
In computer science, a look-up table is a basic data structure that traditionally uses a high-dimensional array to store data and an index (index) to access the data. For example, a two-dimensional array is equivalent in form to a table having a number of rows and columns, and any element in the table can be uniquely accessed according to the index of the rows and columns. Since the values are often fetched from memory much faster than complex calculations, the resulting speed increase is significant. However, in some specific scenarios, the memory space required for the look-up table is too large to be acceptable. However, by improving the data structure of the lookup table according to the actual problems and characteristics of the data faced, the same advantages as those of the lookup table, i.e. less consumed computing resources, constant access time, etc., can be obtained by fully utilizing the limited resources.
The features of the problem addressed by the method according to the invention will be described in connection with a specific example and the applicability of the relevant background art to this problem will be compared.
In a practical scenario, a problem is faced how to index into a value based on a sequence of features. For example, the feature sequence "is fruit, very large, green, striped, sweet, watery", according to which the value "watermelon" should be indexed, the feature sequence "is fruit, not large, red, no striped, sweet or sour, watery", according to which the value "apple" should be indexed, the feature sequence "is fruit, not large, orange, no striped, sweet or sour, watery", according to which the feature "orange" should be indexed. If we refer to "yes/no fruit" as "0/1," bulk/no "as" 0/1, "green/red/orange" as "0/1/2," striped/not striped "as" 0/1, "sweet/sour" as "0/1," water more/moderate/less "as" 0/1/2, "logical conjunctive" or "connected features as a" list "(e.g.," sweet or sour "is represented as [0,1]," more or less water is represented as [0,1,2 ]), the feature sequence is represented by a "list", the feature sequence and its corresponding value are linked by a symbol "→", then, the above three features should be expressed as "[0, 0] →watermelon", "[0,1, [0,1] →apple", "[0,1,2,1, [0,1] →orange". Then, when the feature sequence "[0,1,2,1,0,1]" is given, we know that the value corresponding to the feature sequence is "orange" because of "[0,1,2,1, [0,1] →orange". Thus, the problem faced can be abstracted by giving a series of feature sequences and their corresponding values, e.g. "0, 0" →watermelon, [0,1, [0,1], 1"→apple, [0,1,2,1, [0,1], 1" →orange ", giving another feature, e.g." [0,1,2,1,0,1] ", how to index to the value corresponding to the latter, e.g." orange ".
The most common solution is to use a high-dimensional array to store a "look-up table" and store the values corresponding to all possible features in the array, indexing the values by way of array index access. For example, for the above example, a sheet of shapes 2 x 3 x2 x 3, the value "watermelon" is written in the [0, 0] position of the array, the value "apple" is written in the two positions of [0,1,1,1,0,1] and [0,1,1,1,1,1], the value "orange" is written in both positions [0,1,2,1,0,1] and [0,1,2,1,1,1], and the value "blank" is written in the remaining positions, so that given another feature [0,1,2,1,0,1], the correct value "orange" can be indexed by accessing the array with the feature as a subscript to the array.
One improved way of storing is by using a pre-Sparse Table (Sparse Table). A sparse table is a memory space that utilizes the sparsity of data in a dimension to compress an array. For example, for the densely stored table shown in FIG. 1a, since the data is dense in 0, 3, 6, 8 columns and 0 in all other columns, columns that are all 0's may be discarded, while only columns that contain 1's remain and the column labels are stored down, resulting in a sparsely stored table as shown in FIG. 1 b.
Another more common way of sparse storage is to store with a prefix tree (Trie). A prefix tree is a tree-like data structure that is originally used for string matching. In the scenario of the above example, given multiple feature sequences, the prefix tree merges those parts that are identical "prefixes" into one node, thereby compressing the memory space and enabling access to the values over a constant time. The prefix tree corresponding to the above scenario is shown in fig. 2.
However, if the actual faced scene is much more complex than the example scene described above, the conventional method is not applicable. For example, assuming that a 20-length list is required as the signature sequence for indexing to a specific value, and the value range of each number in the signature sequence is an integer between 0 and 9, and the type of each value to be accessed is char-type (occupying 1 byte of memory), this lookup table would require 10 20 bytes of memory space, so that astronomical resources would be unacceptably occupied in the project. Therefore, the "look-up table" approach is not applicable at this time. In this example, a conventional sparse table is not applicable because the data is not empty in some locations and is valued in a few locations, although all locations are valued and have the same value, and in this example, a prefix tree is not applicable because if a prefix tree is used, the feature sequence first needs to be split into 10 20 feature sequences and then the prefix tree is built, which requires about 10+10 2+103+...+1020 units of memory space to store all nodes, even if the prefix tree is successfully split and entered into its building phase. These are almost impossible to do in engineering practice. And similar complex scenes are actually faced in engineering.
Disclosure of Invention
The invention aims to provide a construction method of a sparse lookup table, and the sparse lookup table achieves optimization of storage space resource utilization by multiplexing a father node and a multiplexing son node simultaneously.
The invention relates to a sparse lookup table construction method, which is characterized in that a series of characteristic sequences and corresponding values thereof are given
[[0,1,2,...,n1、],[0,1,2,...,n12],...,[0,1,2,...,n1m]]→V1
[[0,1,2,...,n21],[0,1,2,...,n22],...,[0,1,2,...,n2m]]→V2
...
[[0,1,2,...,ni1],[0,1,2,...,ni2],...,[0,1,2,...,nim]]→Vi
When constructing a directed acyclic graph, the graph occupies as little memory space as possible to store data, and ensures that a computer can access corresponding values at constant time by searching on the directed acyclic graph. The directional acyclic graph is characterized in that the depth of all termination nodes is equal, and the nodes without parent nodes are called as 'start nodes', the nodes without child nodes are called as 'end nodes', and the number of edges walked from the start node to any node is called as the 'depth' of the node.
Fig. 4 is a simplified representation of a node connection. Fig. 4a is a diagram of two-to-two connections between two sets of nodes, corresponding to nodes, which is a generally known representation method, and for simplicity of representation, the first set of all nodes is connected to the second set of all nodes two by two, for convenience of representation, the simplified representation method of fig. 4b is adopted, i.e. the first set of nodes is represented in one node, the second set of nodes is represented in the other node, and the arrows are pointing from the former to the latter. For convenience of the following description, when a set of nodes is denoted as a node, the node is referred to as a "node set".
Fig. 5 is two examples of converting a single feature list into a sparse lookup table. One feature may be represented by [ [0,1,2, ], n i1],[0,1,2,...,ni2],...,[0,1,2,...,nim ] ], under which expression [ n ] may be abbreviated as n. A feature sequence and its corresponding value can be directly converted into a sparse lookup table, by converting each feature in the feature sequence into a node set, sequentially connecting the node sets according to the sequence of the feature sequence until the last feature, and directing the last feature to the node corresponding to the value.
The invention provides a construction method of a sparse lookup table, which comprises the following specific steps:
A. Each feature is converted into a sparse lookup table, and the method comprises the steps of traversing each feature in a feature sequence to generate a node set, taking the feature as the content of the node set, and sequentially establishing edges connecting the former node set and the latter node set according to the sequence of the feature in the feature sequence so as to obtain a plurality of sparse lookup tables;
B. the 1 st sparse lookup table is taken as a target sparse lookup table, and the 2 nd sparse lookup table is taken as a sparse lookup table to be fused;
C. Fusing the sparse lookup table to be fused into a sparse lookup table of a target to obtain a new sparse lookup table;
D. C, taking the new sparse lookup table obtained in the step C as a target sparse lookup table, taking the 3 rd to the last sparse lookup tables as sparse lookup tables to be fused, and repeating the step C;
E. and after the last sparse lookup table is fused into the target lookup table, the obtained sparse lookup table of the target is the finally constructed sparse lookup table.
In the step B and the step C, the specific step of fusing the sparse lookup table to be fused into the target sparse lookup table includes:
1) Taking the 1 st node set in the sparse lookup table to be fused as the node set to be fused, and taking a set formed by all node sets with depth of 1 in the target sparse lookup table as a set of target node sets;
2) For each node set in the set of target node sets, calculating the number of father node sets of the node set, calculating the intersection of the node set and the node set to be fused, calculating the difference set of the node set and the node set to be fused, and calculating the difference set of all the node sets in the set of the node set to be fused and all the target node sets. The number of the father node sets of the target node sets, the difference set of the target node sets and the node sets to be fused, the difference set of the node sets to be fused and the target node sets, and whether the father node sets of the node sets to be fused are positioned in the target lookup table are four judgment bases;
3) According to the four judgment bases obtained in the step 2), selectively splitting a target node set, splitting the node set to be fused, adding or deleting the incoming side and the outgoing side of the target node set, and adding or deleting the incoming side and the outgoing side of the node set to be fused;
4) And (3) taking the 2 nd node set in the sparse lookup table to be fused as the node set to be fused, correspondingly taking a set formed by all node sets with depth of 2 in the target sparse lookup table as a set of the target node set, and repeating the steps (2) and (3) until the depth is n, wherein n is the depth of the termination node.
The invention has the technical effects that:
The invention relates to a sparse lookup table construction method, which constructs a directed acyclic graph by multiplexing a father node and a son node at the same time, wherein the directed acyclic graph is named as a sparse lookup table. The graph occupies as little memory space as possible to store data and ensures that the computer can access the corresponding values at constant times by searching through the directed acyclic graph. The graph occupies as little memory space as possible to store data and ensures that the computer can access the corresponding values at constant times by searching through the directed acyclic graph. The sparse lookup table construction method achieves optimization of the utilization of storage space resources.
Drawings
Fig. 1 is a conventional sparse table example. In the figure, (a) represents a densely stored table, a position with a value of 0 represents no value at that point, and a position with a value of 1 represents a value at that point. The valued locations are sparse. In the figure (b) shows a sparsely stored table, the valued columns (0, 3, 6, 8 columns) are indexed by a linked list, and only the valued columns are stored in the dense table, so that the memory resources occupied by those columns without values are saved.
Fig. 2 is a prefix tree example. In the prefix tree, for sequences with common prefixes, parts of the common prefixes are combined into one node for storage, that is, a plurality of nodes with common prefixes, and parent nodes of the nodes are multiplexed, so that the parent nodes with the same content are prevented from being stored for multiple times, and storage space is saved.
Fig. 3 is an example of the present invention converting a feature list into a sparse lookup table. Given the feature list "[ [0,1,2, ], 9], the sparse lookup table constructed is shown in this figure. The sparse lookup table is superior to the prefix tree because the prefix tree saves storage space by multiplexing parent nodes, but child nodes thereof are not multiplexed, that is, the constructed graph is a strict tree structure and still occupies a considerable part of redundant storage space resources when stored, and in the sparse lookup table, for a group of nodes, parent nodes with the same content are combined into one node, child nodes with the same content are combined into one node, that is, both the parent nodes and the child nodes are multiplexed, so that the storage space is saved to a greater extent. For example, in the figure, for each node in the second layer of nodes, its parent node contains nodes with content of "0", so that all nodes with content of "0" in the parent node are combined into one node, and its child nodes contain nodes with content of "0", so that all nodes with content of "0" in the child nodes are combined into one node.
In fig. 4, in the simplified representation of node connection, in the fig. a), the nodes of the first layer are connected with the nodes of the second layer in pairs, so that in representation, all the nodes of the first layer can be represented as one node set, the nodes of the second layer are represented as another node set, and the two node sets are connected by a directed edge, as shown in the fig. b).
FIG. 5 is an example of converting a feature list into a sparse lookup table by traversing each feature in a feature sequence to generate a set of nodes and using the feature as the content of the set of nodes, and sequentially creating edges connecting a previous set of nodes with a subsequent set of nodes in the order of the feature in the feature sequence.
Fig. 6 is an example of the present invention converting a plurality of feature lists into a sparse lookup table. A sparse look-up table constructed given four feature sequences and their corresponding values "[[0,1,2],0,1,[0,1,2]]→a、[[0,1,2],0,[0,1,2],[0,1,2]]→b、[[0,1,2],1,[0,1,2],[0,1,2]]→c、[0,2,[0,1,2],[0,1,2]]→d", is shown in the figure.
Fig. 7 is a schematic diagram of step 5.1 of a specific embodiment, wherein for the left graph, the first row is part of the sparse lookup table splut1 of the target and the second row is part of the sparse lookup table splut to be fused. In the dashed box, the upper set of nodes is the set of nodes of the targetThe lower set of nodes is the set of nodes to be fused Node2 d. Junction setThe number of parent node sets is equal to 1, andNumber of elements intersected with Node2 d Greater than 0, andNumber of elements of difference set from Node2 d Equal to 0, and the parent Node set Node2 d-1 of Node2 d is not added to the sparse lookup table splut of the target. The right graph is the fused result, and the Node set Node2 d to be fused is not added to the sparse lookup table splut of the target, so Node2 d does not establish edges with any Node set in splut 1.
For the left-hand graph, the first row is part of the sparse look-up table splut1 of the target and the second row is part of the sparse look-up table splut to be fused, step 5.2 of the embodiment of fig. 8. In the dashed box, the upper set of nodes is the set of nodes of the targetThe lower set of nodes is the set of nodes to be fused Node2 d. Junction setThe number of parent node sets is equal to 1, andNumber of elements intersected with Node2 d Greater than 0, andNumber of elements of difference set from Node2 d Equal to 0, and the parent Node set Node2 d-1 of Node2 d has been added to the sparse lookup table splut of the target. The right graph is the fused result, node2 d to be fused is added to the sparse look-up table splut of the target, and an edge is established with its parent Node2 d-1 between the corresponding Node sets in splut 1.
Fig. 9 is a schematic diagram of step 5.3 of a specific embodiment, with the first row being part of the sparse lookup table splut1 of the target and the second row being part of the sparse lookup table splut to be fused for the left hand diagram. In the dashed box, the upper set of nodes is the set of nodes of the targetThe lower set of nodes is the set of nodes to be fused Node2 d. Junction setThe number of parent node sets is equal to 1, andNumber of elements intersected with Node2 d Greater than 0, andNumber of elements of difference set from Node2 d Greater than 0, and the parent Node set Node2 d-1 of Node2 d is not added to the sparse lookup table splut of the target. The right graph is the fused result, the Node set to be fused Node2 d is added to the sparse look-up table splut1 of the target, and is combined withParent node set of (a)Creating edges between them.
Fig. 10 is a schematic diagram of step 5.4 of a specific embodiment, with the first row being part of the sparse lookup table splut1 of the target and the second row being part of the sparse lookup table splut to be fused for the left hand diagram. In the dashed box, the upper set of nodes is the set of nodes of the targetThe lower set of nodes is the set of nodes to be fused Node2 d. Junction setThe number of parent node sets is equal to 1, andNumber of elements intersected with Node2 d Greater than 0, andNumber of elements of difference set from Node2 d Greater than 0, and the parent Node set Node2 d-1 of Node2 d has been added to the sparse lookup table splut of the target. The right graph is the fused result, junction setIs replaced byDifference set from Node2 d And the Node set to be fused Node2 d is added twice to the sparse look-up table splut1 of the target and is combined withParent node set of (a)An edge is established between the parent Node set Node2 d-1 of Node2 d and a corresponding set of nodes in splut.
Fig. 11 is a schematic diagram of step 5.5 of a specific embodiment, with the first row being part of the sparse lookup table splut1 of the target and the second row being part of the sparse lookup table splut to be fused for the left hand diagram. In the dashed box, the upper set of nodes is the set of nodes of the targetThe lower set of nodes is the set of nodes to be fused Node2 d. Junction setThe number of parent node sets is greater than 1, andNumber of elements intersected with Node2 d Greater than 0, andNumber of elements of difference set from Node2 d Equal to 0, and the parent Node set Node2 d-1 of Node2 d is not added to the sparse lookup table splut of the target. The right graph is the fused result, and the Node set Node2 d to be fused is not added to the sparse lookup table splut of the target, so Node2 d does not establish edges with any Node set in splut 1.
Fig. 12 is a schematic diagram of step 5.6 of a specific embodiment, with the first row being part of the sparse lookup table splut1 of the target and the second row being part of the sparse lookup table splut to be fused for the left hand diagram. In the dashed box, the upper set of nodes is the set of nodes of the targetThe lower set of nodes is the set of nodes to be fused Node2 d. Junction setThe number of parent node sets is greater than 1, andNumber of elements intersected with Node2 d Greater than 0, andNumber of elements of difference set from Node2 d Equal to 0, and the parent Node set Node2 d-1 of Node2 d has been added to the sparse lookup table splut of the target. The right graph is the fused result, node2 d to be fused is added to the sparse look-up table splut of the target, and an edge is established with its parent Node2 d-1 between the corresponding Node sets in splut 1.
Fig. 13 is a schematic diagram of step 5.7 of a specific embodiment, with the first row being part of the sparse lookup table splut1 of the target and the second row being part of the sparse lookup table splut to be fused for the left hand diagram. In the dashed box, the upper set of nodes is the set of nodes of the targetThe lower set of nodes is the set of nodes to be fused Node2 d. Junction setThe number of parent node sets is greater than 1, andNumber of elements intersected with Node2 d Greater than 0, andNumber of elements of difference set from Node2 d Greater than 0, and the parent Node set Node2 d-1 of Node2 d is not added to the sparse lookup table splut of the target. The right graph is the fused result, junction setIs replaced byDifference set from Node2 d And Node2d to be fused is added into the sparse lookup table splut1 of the target twice to establish corresponding edges.
Fig. 14 is a schematic diagram of step 5.8 of a specific embodiment, with the first row being part of the sparse lookup table splut1 of the target and the second row being part of the sparse lookup table splut to be fused for the left hand diagram. In the dashed box, the upper set of nodes is the set of nodes of the targetThe lower set of nodes is the set of nodes to be fused Node2 d. Junction setThe number of parent node sets is greater than 1, andNumber of elements intersected with Node2 d Greater than 0, andNumber of elements of difference set from Node2 d Greater than 0, and the parent Node set Node2 d-1 of Node2 d has been added to the sparse lookup table splut of the target. The right graph is the fused result, junction setIs replaced byDifference set from Node2 d And Node set to be fused Node2 d is added twice to the sparse look-up table splut1 of the target and corresponding edges are established.
Fig. 15 is a schematic diagram of step 5.9 of a specific embodiment, with the first row being part of the sparse lookup table splut1 of the target and the second row being part of the sparse lookup table splut to be fused for the left hand diagram. In the dashed box, the upper set of nodes is the set of nodes of the targetThe lower set of nodes is the set of nodes to be fused Node2 d. Junction setThe number of parent node sets is equal to 1, andNumber of elements intersected with Node2 d Equal to 0, andNumber of elements of difference set from Node2 d Greater than 0, and the parent Node set Node2 d-1 of Node2 d is not added to the sparse lookup table splut of the target. The right graph is the fused result, the Node set to be fused Node2 d is added to the sparse look-up table splut1 of the target, and is combined withParent node set of (a)Creating edges between them.
Fig. 16 is a schematic diagram of step 5.10 of a specific embodiment, with the first row being part of the sparse lookup table splut1 of the target and the second row being part of the sparse lookup table splut to be fused for the left hand diagram. In the dashed box, the upper set of nodes is the set of nodes of the targetThe lower set of nodes is the set of nodes to be fused Node2 d. Junction setThe number of parent node sets is equal to 1, andNumber of elements intersected with Node2 d Equal to 0, andNumber of elements of difference set from Node2 d Greater than 0, and the parent Node set Noe2 d-1 of Node2 d has been added to the sparse lookup table splut1 of the target. The right graph is the fused result, node set Node2 d to be fused is added to the target sparse lookup table splut1, and the corresponding nodes of parent Node set Node2 d-1 in splut are summed with itCreating edges between them.
Fig. 17 is a schematic diagram of step 5.11 of a specific embodiment, with the first row being part of the sparse lookup table splut1 of the target and the second row being part of the sparse lookup table splut to be fused for the left hand diagram. In the dashed box, the upper set of nodes is the set of nodes of the targetThe lower set of nodes is the set of nodes to be fused Node2 d. Junction setThe number of parent node sets is greater than 1, andNumber of elements intersected with Node2 d Equal to 0, andNumber of elements of difference set from Node2 d Greater than 0, and the parent Node set Node2 d-1 of Node2 d is not added to the sparse lookup table splut of the target. The right graph is the fused result, the set of nodes Nd e2 d to be fused is added to the sparse look-up table splut of the target, and the corresponding edges are established.
Fig. 18 is a schematic diagram of step 5.12 of a specific embodiment, with the first row being part of the sparse lookup table splut1 of the target and the second row being part of the sparse lookup table splut to be fused for the left hand diagram. In the dashed box, the upper set of nodes is the set of nodes of the targetThe lower set of nodes is the set of nodes to be fused Node2 d. Junction setThe number of parent node sets is greater than 1, andNumber of elements intersected with Node2 d Equal to 0, andNumber of elements of difference set from Node2 d Greater than 0, and the parent Node set Node2 d-1 of Node2 d has been added to the sparse lookup table splut of the target. The right graph is the fused result, the Node set to be fused Node2 d is added to the sparse look-up table splut1 of the target, and the corresponding edges are established.
Detailed Description
Example 1:
Given feature list "[ [0,1,2, ], 9], [0,1,2, ], 9], ] →v" (where the features "[0,1,2, ], 9]" 20 in the list), stored in a conventional look-up table manner, requires 10 20 units of storage space, however, the sparse lookup table is used for storage, and this embodiment requires only about 200 units of storage space to store all nodes and about 1900 units of storage space to store all edges, as shown in fig. 3. According to step a, feature 1 is converted into a sparse look-up table. Because only one feature exists in the feature list, the processed 1 st feature is the last feature, and the step E is completed, namely the construction of the coefficient lookup table is completed. It should be noted that the sparse lookup table in fig. 3 does not use a simplified representation as shown in fig. 4b, but rather uses a general representation as shown in fig. 4 a.
Example 2:
the process of converting the feature lists into the sparse lookup table is to give a series of feature sequences and corresponding values
[[0,1,2,...,n11],[0,1,2,...,n12],...,[0,1,2,...,n1m]]→V1
[[0,1,2,...,n21],[0,1,2,...,n22],...,[0,1,2,...,n2m]]→V2
...
[[0,1,2,...,ni1],[0,1,2,...,ni2],...,[0,1,2,...,nim]]→Vi
First, each feature sequence and its corresponding value are converted into a sparse look-up table, such as that shown in fig. 5. Next, the 1 st sparse lookup table is taken and denoted splut, the 2 nd sparse lookup table is fused into splut, and the new sparse lookup table after fusion is denoted as splut. And sequentially taking out the 3 rd to the i th sparse lookup tables, and repeating the fusion process until splut fused with the i th sparse lookup table is obtained, wherein the obtained sparse lookup table is the final obtained sparse lookup table.
The above method of fusing one sparse lookup table into another sparse lookup table is the core content of the present invention. The procedure for fusion is set forth below.
Given one sparse look-up table splut1 (the targeted sparse look-up table) and another sparse look-up table splut (the sparse look-up table to be fused) directly transformed by the feature sequence:
step 1, let d=0, and record splut2 as the length of the corresponding feature sequence.
And step 2, if d is greater than or equal to the length of the feature sequence corresponding to splut2, jumping to step 6, otherwise jumping to step 3.
And 3, taking out the d-th Node set in splut and recording the Node set as Node2 d. Taking all node sets with depth d in splut and recording the set formed by the node sets asThe ith node set in S d is marked as
Step 4, traversing each node set in S d one by oneComputing junction setsIntersection with Node2 d, noted as(The number of the elements is recorded as) Junction setDifference set from Node2 d, noted as(The number of the elements is recorded as) Node set Node2 d andIs marked as the difference set of (1)(The number of the elements is recorded as)。
Step 5, calculating a junction setAccording to the calculated result, node2 d is added into splut, and the addition and deletion of edges are performed.
Step 5.1, as shown in fig. 7. If it isThe number of parent node sets is equal to 1, andGreater than 0, andEqual to 0 and Node2 d-1 is not added to splut1, then Node2 d is not added to splut1, at which point d=d+1 and process 1 is recursively performed.
Step 5.2, as shown in fig. 8. If it isThe number of parent node sets is equal to 1, andGreater than 0, andEqual to 0, and Node2 d-1 has been added to splut1, its corresponding Node in splut is noted asThen add Node2 d to splut1, whose corresponding Node in splut is denoted asEstablishment ofPointing toLet d=d+1 at this time, and recursively perform procedure 1.
Step 5.3, as shown in fig. 9. If it isThe number of parent node sets is equal to 1, andGreater than 0, andGreater than 0, and Node2 d-1 is not added to splut1, thenReplaced byMeanwhile, node2 d is added to splut, and the corresponding Node in splut is marked asEstablishment ofPointing toLet d=d+1 at this time, and recursively perform procedure 1.
Step 5.4, as shown in fig. 10. If it isThe number of parent node sets is equal to 1, andGreater than 0, andGreater than 0, and Node2 d-1 has been added to splut1, its corresponding Node in splut is noted asWill beReplaced byMeanwhile, node2 d is added to splut twice, and the corresponding Node in splut is marked asAndEstablishment ofPointing toIs established by (1)Pointing toIs established by (1)Point to all sides of all the set of nodes in S d+1, at this point let d=d+1 and recursively perform procedure 1.
Step 5.5, as shown in fig. 11. If it isThe number of parent node sets is greater than 1, andGreater than 0, andEqual to 0 and Node2 d-1 is not added to splut1, then Node2 d is not added to splut1, at which point d=d+1 and process 1 is recursively performed.
Step 5.6, as shown in fig. 12. If it isThe number of parent node sets is greater than 1, andGreater than 0, andEqual to 0, and Node2 d-1 has been added to splut1, its corresponding Node in splut is noted asThen add Node2 d to splut1, whose corresponding Node in splut is denoted asEstablishment ofPointing toLet d=d+1 at this time, and recursively perform procedure 1.
Step 5.7, as shown in fig. 13. If it isThe number of parent node sets is greater than 1, andGreater than 0, andGreater than 0, and Node2 d-1 is not added to splut1, recordNode sets equal to Node2 d-1 in all parent Node sets areWill beReplaced byMeanwhile, node2 d is added to splut twice, and the corresponding Node in splut is marked asAndEstablishment ofAll father nodes are intensively dividedAll other junction sets point toIs established by all sides ofPointing toIs established by (1)Point to all sides of all the set of nodes in S d+1, at this point let d=d+1 and recursively perform procedure 1.
Step 5.8, as shown in fig. 14. If it isThe number of parent node sets is greater than 1, andGreater than 0, andGreater than 0, and Node2 d-1 has been added to splut1, its corresponding Node in splut is noted asThen recordNode sets equal to Node2 d-1 in all parent Node sets areWill beReplaced byMeanwhile, node2 d is added to splut twice, and the corresponding Node in splut is marked asAndEstablishment ofAll father nodes are intensively dividedAll other junction sets point toIs established by all sides ofPointing toIs established by (1)Pointing toIs established by (1)Point to all sides of all the set of nodes in S d+1, at this point let d=d+1 and recursively perform procedure 1.
Step 5.9, as shown in fig. 15. If it isThe number of parent node sets is equal to 1, andEqual to 0, andGreater than 0, and Node2 d-1 is not added to splut1, recordNode sets equal to Node2 d-1 in all parent Node sets areNode2 d is added to splut1, the corresponding Node in splut is denoted asEstablishment ofPointing toIs to be followed bySput1 are added sequentially and edges are created sequentially. Jump to step 6.
Step 5.10, as shown in fig. 16. If it isThe number of parent node sets is equal to 1, andEqual to 0, andGreater than 0, and Node2 d-1 has been added to splut1, its corresponding Node in splut is noted asThen add Node2 d to splut1, whose corresponding Node in splut is denoted asEstablishment ofPointing toIs established by (1)All sides pointing to all the junction sets in S d, and thenSput1 are added sequentially and edges are created sequentially. Jump to step 6.
Step 5.11, as shown in fig. 17. If it isThe number of parent node sets is greater than 1, andEqual to 0, andGreater than 0, and Node2 d-1 is not added to splut1, recordNode sets equal to Node2 d-1 in all parent Node sets areNode2 d is added to splut1, the corresponding Node in splut is denoted asEstablishment ofPointing toIs to be followed bySput1 are added sequentially and edges are created sequentially. Jump to step 6.
Step 5.12, as shown in fig. 18. If it isThe number of parent node sets is greater than 1, andEqual to 0, andGreater than 0, and Node2 d-1 has been added to splut1, its corresponding Node in splut is noted asThen add Node2 d to splut1, whose corresponding Node in splut is denoted asEstablishment ofPointing toIs established by (1)Pointing toIs to be followed bySput1 are added sequentially and edges are created sequentially. Jump to step 6.
And 6, obtaining the established coefficient lookup table splut.
The above-mentioned "procedure 1" includes steps 2 to 6.
It should be noted that the disclosed embodiments are intended to aid in a further understanding of the invention, but those skilled in the art will appreciate that various alternatives and modifications are possible without departing from the spirit and scope of the invention and the appended claims. Therefore, the invention should not be limited to the disclosed embodiments, but rather the scope of the invention is defined by the appended claims.
Claims (13)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210465837.8A CN114780801B (en) | 2022-04-29 | 2022-04-29 | A method for constructing a sparse lookup table |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210465837.8A CN114780801B (en) | 2022-04-29 | 2022-04-29 | A method for constructing a sparse lookup table |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN114780801A CN114780801A (en) | 2022-07-22 |
| CN114780801B true CN114780801B (en) | 2025-01-21 |
Family
ID=82434839
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202210465837.8A Active CN114780801B (en) | 2022-04-29 | 2022-04-29 | A method for constructing a sparse lookup table |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN114780801B (en) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106547811A (en) * | 2015-09-22 | 2017-03-29 | 国际商业机器公司 | The distributed merging of data set |
| CN107153647A (en) * | 2016-03-02 | 2017-09-12 | 奇简软件（北京）有限公司 | Carry out method, device, system and the computer program product of data compression |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US9659061B2 (en) * | 2013-05-14 | 2017-05-23 | ServiceSource | Method for efficient aggregation of numerous data using sparse bit sets |
| CN113420804B (en) * | 2021-06-18 | 2024-06-18 | 工业互联网创新中心（上海）有限公司 | Data processing method, device, network equipment and storage medium |
-
2022
- 2022-04-29 CN CN202210465837.8A patent/CN114780801B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106547811A (en) * | 2015-09-22 | 2017-03-29 | 国际商业机器公司 | The distributed merging of data set |
| CN107153647A (en) * | 2016-03-02 | 2017-09-12 | 奇简软件（北京）有限公司 | Carry out method, device, system and the computer program product of data compression |
Also Published As
| Publication number | Publication date |
|---|---|
| CN114780801A (en) | 2022-07-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN112800065B (en) | Efficient data retrieval method based on improved block storage structure | |
| Hao et al. | Bounds and constructions of locally repairable codes: parity-check matrix approach | |
| JP6973150B2 (en) | Shortest path matrix generation program, device, and method | |
| CN101675430A (en) | Method and system for approximate string matching | |
| CN110474762A (en) | The construction method of ring type editable block chain | |
| US20080104108A1 (en) | Schemaless xml payload generation | |
| Apostolico et al. | New clique and independent set algorithms for circle graphs | |
| CN112883241A (en) | Supercomputer benchmark test acceleration method based on connected component generation optimization | |
| CN114780801B (en) | A method for constructing a sparse lookup table | |
| CN110675417B (en) | Raster data fast vectorization method combining run length coding and edge tracking | |
| CN105975694B (en) | A method for constructing cascaded Bayesian networks for combinatorial explosion problems | |
| JP4969151B2 (en) | Data processing system | |
| CN114372097A (en) | Efficient connection comparison implementation method and device for data set serialization | |
| CN114696325A (en) | Power grid topology configuration method | |
| CN103428087B (en) | The longest path preset protection P using depth of round first traversal encloses generation method | |
| CN117632950A (en) | Method, device, equipment and storage medium for constructing data structure | |
| CN107943927B (en) | The memory module conversion method of multidimensional data in a kind of distributed memory system | |
| Demaine et al. | Polylogarithmic fully retroactive priority queues via hierarchical checkpointing | |
| CN116864006A (en) | DNA data encoding and decoding methods, devices, computer equipment and storage media | |
| CN109885794B (en) | Processing method for circularly and synchronously updating webpage based on block chain | |
| CN112035576A (en) | Distributed storage method of blockchain ledger | |
| JP4510041B2 (en) | Document search system and program | |
| CN108959653B (en) | Based on dense grid recombination and K2Graph data representation method of tree | |
| JPH10240741A (en) | How to manage tree structured data | |
| CN110489516B (en) | Method for quickly establishing prefix index for massive structured data |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |