RU2534368C2 - Method of compressing prefix tree data structure - Google Patents

Abstract

FIELD: physics, computer engineering.

SUBSTANCE: invention relates to information processing and specifically to methods of searching for information and creating data structures to this end. The method of compressing a prefix tree data structure includes node merging after ranking and finding the most suitable merging pair. To this end, values of numerical characteristics of random quantities are calculated at each iteration for all nodes involved in compression. The best node for merging is selected for each node according to a selected criterion. Iterations continue while there is still potential for merging for at least a pair of nodes.

EFFECT: high compression density, which enables to reduce the amount of random-access memory needed to store said data structure without complicating the search algorithm and reducing the information search rate.

5 dwg

Description

The invention relates to the field of information processing, and in particular to methods and methods of information retrieval, as well as the creation of data structures designed for this purpose.

The characteristics of keyword search systems in a data stream depend both on the search algorithm used and on the number of keywords. The essential characteristics are the search speed and the amount of RAM used in the search. The speed of most search algorithms drops significantly with an increase in the number of keywords. On the other hand, algorithms whose speed does not depend on the number of keywords require large amounts of memory. The selection of an appropriate search algorithm under given conditions is a non-trivial task.

The digital search algorithm based on the prefix tree is the best by the criterion of the highest search speed [Fredkin, E. 1960. Trie memory. Communications of the ACM 3, 490-499]. Its advantages are independence from the number of keywords and ease of implementation. The disadvantage of this method is the large amount of memory for storing the data structure due to its strong sparseness (the number of occupied nonzero elements in the structure is low in relation to their total number). Sparseness of the data structure can be eliminated either by modifying or compacting the data structure.

Known methods for modifying the data structure, consisting in changing the structure of the node [US patent No. 7720854 B2 dated 05/18/2010, IPC G06F 7/00 (2006.01), G06F 17/30 (2006.01); US patent No. 6675171 B2 dated January 6, 2004, IPC G06F 17/30; US patent No. 6671694 B1 dated 12.30.2003, IPC G06F 17/30]. These methods have two disadvantages. Firstly, the complexity of the node structure complicates the search algorithm. Secondly, avoiding direct addressing of elements inside the node leads to an increase in the iteration time for the key. This leads to a decrease in the speed of the search algorithm.

The process of compacting the data structure by merging nodes using unoccupied elements is not widely used due to the requirements for the static space of keywords (after the process of compaction, the process of inserting a new keyword leads to a large amount of time). For a certain range of tasks, this requirement is acceptable.

In the general case, the solution to the compaction problem is reduced to searching for such a permutation of all possible that the best (maximum) ratio of the number of occupied elements to their total number is achieved. There is evidence of NP completeness of this process [Dill, J. M. Optimal trie compaction is NP-complete. TR-CSD-167, Pennsylvania State Univ., March 1987].

The closest, taken as a prototype, is the method, system, program and data structure of a compact array for storing character strings [US patent No. 6470347 B1 from 10.22.2002, IPC G06F 17/00]. The method describes the data structure for storing strings in the form of a prefix tree. Data structure compaction is achieved in two steps. At the first stage, duplicate nodes are deleted, i.e. nodes with nonzero elements in the same positions. At the second stage, nodes are merged with each other. Merge condition: non-zero elements of the source node can be inserted in place of the empty elements of the destination node. The displacement of the elements of one node relative to the elements of another is allowed.

This method has two drawbacks. First, deleting duplicate nodes is unacceptable, because this leads to the loss of associativity property, when at the end of the search iteration it is possible to unambiguously match the found key with certain data. Secondly, the merging of nodes according to the principle of the first found option leads to a deviation of the resulting compression density from the maximum possible value.

These shortcomings generally lead to the inability to use the prototype when performing search procedures with the number of keywords in excess of 10 ⁶ .

The objective of the claimed invention is to provide a method of compacting the data structure of the prefix tree, which allows to reduce the amount of RAM required to store this data structure. Complications of the search algorithm, as well as a decrease in the speed of information retrieval, do not occur.

This problem is solved in that the method of compacting the data structure of the prefix tree, which consists in merging the tree nodes with each other according to the principle of the first found option, in which nonzero elements of the source node are inserted into the place of empty elements of the destination node, according to the invention is supplemented by the fact that the merger nodes occurs only after ranking and finding the most suitable merge pairs.

To do this, at each iteration, the numerical characteristics of random variables are calculated for all nodes participating in the compaction. Further, for each node, according to the selected criterion, the best prospective node for merging is selected. If the merge failed, the next node is selected, etc. either until a successful merger, or until the end of the list. Iterations continue as long as there is the potential for merging at least one pair of nodes.

A consequence of the use of the proposed method is an increase in the time required to compact the data structure. Considering that adding new keywords after compaction is not supposed, this increase can be neglected.

The analysis of the level of modern computer technology made it possible to establish that there are no analogues that are characterized by a set of features identical to all the features of the claimed technical solution, which indicates the compliance of the claimed method with the condition of patentability “novelty”.

Search results for known solutions in this and related fields of technology in order to identify features that match the distinctive features of the claimed object from the prototype showed that they do not follow explicitly from the prior art. The prior art also did not reveal the fame of the distinctive essential features that determine the same technical result that is achieved in the claimed method. Therefore, the claimed invention meets the condition of patentability "inventive step".

The claimed method is illustrated by drawings, which show:

figure 1 is a General diagram of a device that implements a method of compacting the data structure of a prefix tree;

figure 2 - the field structure of the elements of the state table and transitions of the data structure;

figure 3 - the structure of the fields of elements of the optimized state table and transitions of the data structure;

figure 4 - structure of the fields of elements of the auxiliary optimized transition table;

5 is a comparison of the experimental results of compaction of the prefix tree for the prototype method and the proposed method.

A device that implements the claimed method, the General scheme of which is presented in figure 1, works as follows.

A sparse data structure is formed from a set of keywords (input data of block 1) using a sparse prefix tree generator block (block 2). Further, the data structure is fed to the input of the decision block 2, which determines the further action: either complete the process, or start the next iteration of compaction. A positive decision to start a new iteration of compaction is made in two cases. Firstly, after the initial generation of the data structure by block 1. Secondly, after the completion of the next iteration of compaction with a positive outcome. The positive outcome of the iteration is determined by the fact that at least two nodes were found for which the merge procedure was completed. The beginning of a new iteration of compaction occurs after the control transfer of the decision block 2 to the block for calculating the numerical characteristics of random variables (block 3). Further, in the unit for calculating the coefficients and forming a list of merge pairs (block 4), the merging coefficients are ranked and a list of pairs of nodes is determined for which the merge operation should be performed in order of priority. According to this list, the nodes are merged in the corresponding block (block 5). After the completion of the iteration, control is again fed to the input of the decision block 2. After the decision is made to complete the cycle of iterations of the summarization, the data structure is transferred to the input of the block of the final iteration of the summarization (block 6). Next, the finally compressed structure is fed to the input of the data structure optimization block (block 7). The optimized data structure is the result of block 7.

Each element of the sparse prefix tree node has the format shown in FIG. 2. There are 5 fields in the element. The State field defines the type of element. If the State (0) field is zero, the element is considered empty and can be used to place a nonzero element of another node during merging. In this case, the values of the remaining fields are ignored and may have an arbitrary value. The value of the State field, which is equal to unity (1), determines that a match has occurred and it is necessary to proceed to the next node, the number of which is indicated in the Index field. At this stage (in a sparse prefix tree), the values of the remaining fields are ignored and can have an arbitrary value. The value of the State field, equal to two (2), determines that a keyword has been found and the unique numeric value associated with it is indicated in the Index field. As a unique value, the serial number of the keyword is usually used in the initial list of keywords from which a sparse array is formed. In this case, the values of the remaining fields are ignored and may have an arbitrary value. Other values for the State field are not valid.

The calculation of the coefficients of merging, ranking the coefficients and determining the priority list of pairs of nodes is performed only for nodes with the number of nonzero elements more than one. Compaction of nodes with a single number of nonzero elements is performed in the block of the final iteration of compaction (block 6).

The calculation of the numerical characteristics of random variables is as follows.

The prefix tree is represented as a set of independent discrete random variables (each random variable is determined by a separate node in the data structure):

$$A={\left\{X_i\right\}}_{i=\mathrm{one}}^N$$

The values accepted by random variables are determined by the size of the alphabet M (the range of values is 0..M-1).

The distribution law of each random variable is represented by the corresponding distribution series, which is determined by the set of occupied elements in the corresponding node:

$$p_{X_i}\left(x_j\right)=\{\begin{array}{c}\frac{\mathrm{one}}{C_i^{*}}PR\mathrm{and}{x}_j=E_{i,j}^{*}\\ 0PR\mathrm{and}{x}_j=E_{i,j}^0\end{array},$$

Where

- занятые элементы; $$E_{n,m}^{*}$$

- busy items;

- свободные элементы; $$E_{n,m}^0$$

- free items;

- количество ненулевых элементов в i-м узле. $$C_i^{*}$$

- the number of nonzero elements in the i-th node.

The mathematical expectation for the i-th node:

$${\nu }_{\mathrm{one}}=N{X}_i=M\left[X_i\right]={\displaystyle \sum _{j=\mathrm{one}}^{C_i^{*}}{\left(x_j-M{X}_j\right)}^2{p}_{X_i}\left(x_j\right)}$$

Dispersion for the i-th node:

$${\mathrm{<figure-callout\; id="2"\; label="\mu "\; filenames="00000014.png"\; state="\{\{state\}\}">\mu </figure-callout>}}_2=D\left[X_i\right]={\displaystyle \sum _{j=\mathrm{one}}^{C_i^{*}}{\left(x_j-M{X}_j\right)}^2{p}_{X_i}\left(x_j\right)}$$

Numerical characteristics are calculated for all possible node offsets. The range of displacements is determined by the extreme non-zero (non-empty) elements of the node. The range is defined as follows. Suppose that in a node the first nonzero element is in position S _high , and the last in position S _low . In this case, the maximum value of the element position in the node is S _max . This means that it is possible to shift elements of a given node up S _high times and non-zero nodes will not go beyond the range 0..S _max . It is also possible to shift the elements of a given node down S _max -S _low times and non-zero nodes will not go beyond the range 0..S _max . Thus, the range of displacements of the elements of this node is set by the following values: -S _high ..S _max -S _low . A negative value indicates an upward offset. A range always has at least one value: 0.

The merge coefficient for the i-th and j-th nodes with k-th and l-th offset, respectively, is determined as follows:

$$K{m}_{i_k,j_l}=|\; |\; |\frac{{\left(|\; |\; |M\left[X_{i_k}\right]-M\left[X_{j_l}\right]|\; |\; |\right)}^2}{9\cdot \sqrt{D\left[X_{i_k}\right]\sqrt{D\left[X_{j_l}\right]}}}|\; |\; |-\mathrm{one}$$

Merging coefficients are ranked by ascending sorting method. The closer the coefficient value to zero, the more priority and probable is the possibility of merging given nodes at given offsets.

The compaction of the two nodes is as follows. The source node is a roaming node, and the destination node is a node whose empty elements are used to host the roaming node. The number of the virtual node in the VIndex destination node is determined: the first unused value of the VIndex _new field is found from all nonzero elements of the destination node, starting from 1. For each nonzero element of the source node, the values of its Index, VTo, Shift fields are copied to the fields of the zero element node-receiver at a given offset. At the same time, the VIndex _new value defined above is recorded in the VIndex field of all formed elements. Next, the source node is deleted and links to it are adjusted from other elements. For all transition elements of all nodes with the value of the Index field equal to the index value of the source node, it is replaced with the index value of the destination node. After that, the memory block used to store the source node is released.

In the case of the next successful merger of two nodes from the list of ranked coefficients, all elements that refer to at least one of the nodes of the merge pair are deleted. This is because after the merger, the structure of the receiver node changes and all the characteristics defined for it lose their relevance. The coefficients for the source node also lose their relevance, since the node no longer exists.

The final iteration of compaction is to merge all source nodes containing only one non-zero element with any destination node containing more than one non-zero element. If there are no receiver nodes containing more than one nonzero element, then merge with any possible receiver node with a minimum location index.

A compacted tree in the general case consists of a predominant number of elements of two types - a transition (State = 1) and successful completion of the search (State = 2). The number of empty elements (State = 0) is relatively small. In this case, there is an irrational use of the device’s memory, as VTo and Shift fields are used only for transition elements. The optimization process eliminates this irrationality. For this, an optimized table of states and transitions and a new auxiliary optimized transition table are formed. The element format of the optimized state and transition table is shown in FIG. 3. The format of the element of the auxiliary optimized conversion table is presented in figure 4. The meaning of optimization is as follows. For all elements of the transition type (State = 1) with the same value of the three fields Index, VTo and Shift, a new element is formed in the auxiliary optimized transition table with the same values of the Index, VTo and Shift fields. Then the transition elements of the optimized state and transition table in the Index field will contain the number of the corresponding element in the auxiliary optimized transition table.

An information retrieval algorithm using a compressed data structure can be described as follows.

The search state is formed by a set of variables: Index - the index of the physical node used in the current iteration of the search; VIndex - index of the virtual node (inside the physical) used in the current iteration of the search; Shift - current shift of character codes. The initial state of the search is determined by the zero values of all the variables in the set. From the input stream in which the search is performed, the next byte of information with the character code C is obtained. If the value (C + Shift) goes beyond the bounds of the index values of the Index node, the current iteration of the search fails, the initial state is reset, and the next character from the input flow. Otherwise, if the value (C + Shift) does not go beyond the bounds of the values of the indices of the Index node, the fields of the element of the Index node in the position (C + Shift) are analyzed. If the value of the VIndex field of the element is not equal to the value of the VIndex field of the search state, the current iteration of the search fails, the initial state is reset, the next character from the input stream is transferred. Otherwise, the value of the State field of the Index node element is analyzed at the position (С + Shift). If the value of the State field is zero (State = 0), the current iteration of the search fails, the initial state is reset, the transition to the next character from the input stream occurs. In the case when the State field has a value of 2 (State = 2), the current iteration of the search succeeds, the numerical value associated with the found keyword is contained in the Index field of the element, then, if necessary, the initial state is reset, the next character from input stream. In the case when the State field has a value of 1 (State = 1), the values of the Index, VIndex, Shift fields are updated by the values of the corresponding Index, VTo, Shift fields taken from the auxiliary transition table, at the index taken from the value of the Index field of the element in position ( C + Shift), then proceeds to the next character from the input stream. To protect against external errors, when the State field has a different value than 0..2, the current iteration of the search fails, the initial state is reset, the next character from the input stream is transferred.

An experimental verification of the characteristics of the method of compacting the data structure of the prefix tree was performed on a computer using the C ++ programming language with the following initial data:

1. The volume of the set of F keywords: from 100 thousand to 10 million;

2. The size of the alphabet M by the number of states 1 byte of information (the number of placements with repetitions, with n = 2, k = 8):

; $$N_p={\overline{A}}_n^k={\overline{A}}_n^k=n^k=2^8=256$$

;

3. The size of the alphabet M cannot be changed during the compaction process. A comparison of the results of the experiment, shown in figure 5, shows that the application of the proposed method gives a gain in the amount of RAM occupied by the compressed prefix tree (the number of nodes in the tree after compression) under equal conditions by 5-7% (depending on the number of keywords and their symbolic content) compared with the prototype method.

The results of the experiment allow us to conclude that the claimed method solves the problem.

Industrial applicability of the invention is due to the fact that a device that implements the proposed method can be implemented using a modern elemental base, achieving the destination specified in the invention, due to the fact that the merger order is determined by calculating the values of the numerical characteristics of random variables for all nodes involved in compaction, and ranking for each receiver node of the source nodes in the sequence of decreasing priority.

Claims (1)

A method of compacting the data structure of a prefix tree, which consists in merging the tree nodes with each other, in which nonzero elements of the source node are inserted into the place of the empty elements of the destination node, characterized in that the merge order is determined by calculating the values of the numerical characteristics of random variables for all nodes, involved in compaction, and ranking for each destination node of the source nodes in the sequence of decreasing priority.

Images