CN115577149B - Data processing method, device and equipment and readable storage medium - Google Patents
Data processing method, device and equipment and readable storage mediumDownload PDFInfo
- Publication number
- CN115577149B CN115577149BCN202211592819.2ACN202211592819ACN115577149BCN 115577149 BCN115577149 BCN 115577149BCN 202211592819 ACN202211592819 ACN 202211592819ACN 115577149 BCN115577149 BCN 115577149B
- Authority
- CN
- China
- Prior art keywords
- hash
- address
- point information
- character segment
- read
- 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
Images
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/9014—Indexing; Data structures therefor; Storage structures hash tables
- 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
- G06F16/90335—Query processing
- G06F16/90344—Query processing by using string matching techniques
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Software Systems (AREA)
- Computational Linguistics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
Translated fromChinese
Description
Translated fromChinese技术领域technical field
本申请涉及计算机技术领域，特别涉及一种数据处理方法、装置、设备及可读存储介质。The present application relates to the field of computer technology, and in particular to a data processing method, device, equipment and readable storage medium.
背景技术Background technique
目前在压缩数据时，可以查询预设字典，以构建待压缩数据的哈希链表。其中，针对任一压缩数据，会对其中的不同字符片段同时查询得到相应的哈希链表，而有的字符片段的哈希链表长，有的字符片段的哈希链表短，因此查到这些哈希链表的查询返回时间不定，也即：查询返回时间与各字符片段在压缩数据中的原顺序不一致，导致各个哈希链表乱序输出，影响数据压缩的后续处理。At present, when compressing data, you can query the preset dictionary to build a hash list of the data to be compressed. Among them, for any compressed data, different character fragments in it will be queried at the same time to obtain the corresponding hash list, and some character fragments have a long hash list, and some character fragments have a short hash list, so these hashes can be found The query return time of the hash linked list is uncertain, that is, the query return time is inconsistent with the original order of each character segment in the compressed data, resulting in the out-of-order output of each hash linked list, which affects the subsequent processing of data compression.
因此，如何使待压缩数据对应的各个哈希链表顺序存储，是本领域技术人员需要解决的问题。Therefore, how to sequentially store each hash list corresponding to the data to be compressed is a problem to be solved by those skilled in the art.
发明内容Contents of the invention
有鉴于此，本申请的目的在于提供一种数据处理方法、装置、设备及可读存储介质，以使待压缩数据对应的各个哈希链表顺序存储。其具体方案如下：In view of this, the object of the present application is to provide a data processing method, device, device and readable storage medium, so that each hash list corresponding to the data to be compressed is stored sequentially. The specific plan is as follows:
第一方面，本申请提供了一种数据处理方法，应用于硬件设备，包括：In the first aspect, the present application provides a data processing method applied to hardware devices, including:
获取目标字符串；Get the target string;
在所述目标字符串中确定多个字符片段；determining a plurality of character segments in the target character string;
根据各个字符片段在所述目标字符串中的位置查询各个字符片段对应的哈希链表，并确定各个哈希链表在所述硬件设备的双口RAM中的写入地址；Query the hash linked list corresponding to each character segment according to the position of each character segment in the target character string, and determine the write address of each hash linked list in the dual-port RAM of the hardware device;
按照所述写入地址将每一哈希链表中的各链点信息写入所述双口RAM。Write the link point information in each hash link list into the dual-port RAM according to the write address.
可选地，所述根据各个字符片段在所述目标字符串中的位置查询各个字符片段对应的哈希链表，包括：Optionally, the querying the hash list corresponding to each character segment according to the position of each character segment in the target string includes:
根据各个字符片段在所述目标字符串中的位置以及位置在前先查询的规则确定各个字符片段的查询顺序；Determine the query order of each character segment according to the position of each character segment in the target character string and the rule that the position is inquired first;
按照所述查询顺序查询各个字符片段对应的哈希链表。The hash linked list corresponding to each character segment is queried according to the query sequence.
可选地，任一字符片段对应的哈希链表的查询过程包括：Optionally, the query process of the hash list corresponding to any character segment includes:
计算当前字符片段的哈希值；Calculate the hash value of the current character segment;
确定所述哈希值对应的当前需读地址；Determine the current address to be read corresponding to the hash value;
判断所述当前需读地址与已查到哈希链表的字符片段的哈希值是否相同；Judging whether the current address to be read is the same as the hash value of the character segment found in the hash list;
若否，则从所述当前需读地址中读取链点信息后，为该链点信息添加链表结束标志位，并将读取到的链点信息构建为当前字符片段对应的哈希链表。If not, after reading the link point information from the current address to be read, add the link list end flag bit for the link point information, and build the read link point information into a hash list corresponding to the current character segment.
可选地，若所述当前需读地址与已查到哈希链表的字符片段的哈希值相同，则从所述当前需读地址中读取链点信息后，为该链点信息添加链表未结束标志位，并确定下一需读地址，并执行所述判断所述当前需读地址与已查到哈希链表的字符片段的哈希值是否相同的步骤。Optionally, if the current address to be read is the same as the hash value of the character segment of the hash linked list found, after the link point information is read from the current address to be read, a linked list is added to the link point information Unfinished flag bit, and determine the next address to be read, and perform the step of judging whether the current address to be read is the same as the hash value of the character segment found in the hash list.
可选地，所述确定所述哈希值对应的当前需读地址，包括：Optionally, the determining the current address to be read corresponding to the hash value includes:
将所述哈希值作为所述当前需读地址。The hash value is used as the current address to be read.
可选地，所述确定各个哈希链表在所述硬件设备的双口RAM中的写入地址，包括：Optionally, the determining the write address of each hash linked list in the dual-port RAM of the hardware device includes:
按照所述查询顺序以及先查询写入地址在前的规则确定各个哈希链表在所述双口RAM中的写入地址。The write address of each hash linked list in the dual-port RAM is determined according to the query sequence and the rule that the write address is first queried.
可选地，所述双口RAM为多个；Optionally, there are multiple dual-port RAMs;
相应地，任一哈希链表中的各链点信息的写入过程包括：Correspondingly, the writing process of each link point information in any hash list includes:
按照所述写入地址将当前哈希链表中的各链点信息分别写入各双口RAM。Write the link point information in the current hash linked list into each dual-port RAM according to the write address.
可选地，还包括：Optionally, also include:
按照所述写入地址从各双口RAM中读出任一字符片段对应的哈希链表；Read the hash linked list corresponding to any character segment from each dual-port RAM according to the write address;
确定当前读取的哈希链表中的各链点信息对应的编码长度，并选择编码长度最长的链点信息作为当前字符片段的压缩信息。Determine the code length corresponding to each link point information in the currently read hash linked list, and select the link point information with the longest code length as the compressed information of the current character segment.
可选地，所述选择编码长度最长的链点信息作为当前字符片段的压缩信息，包括：Optionally, the selection of the chain point information with the longest encoding length as the compression information of the current character segment includes:
以并行级联方式比较当前读取的哈希链表中的各链点信息对应的编码长度，以选择编码长度最长的链点信息作为当前字符片段的压缩信息。Comparing the encoding lengths corresponding to each link point information in the currently read hash linked list in a parallel cascading manner, to select the link point information with the longest encoding length as the compressed information of the current character segment.
可选地，还包括：Optionally, also include:
若编码长度最长的链点信息有多个，则确定多个编码长度最长的链点信息对应的距离值，并选择距离值最小的链点信息作为当前字符片段的压缩信息。If there are multiple chain point information with the longest code length, then determine the distance values corresponding to the chain point information with the longest code length, and select the chain point information with the smallest distance value as the compressed information of the current character segment.
可选地，还包括：Optionally, also include:
任意双口RAM中的任一RAM地址写入携带有链表结束标志位的链点信息后，将该RAM地址对应的状态寄存器置1；相应地，该RAM地址中的数据被读出后，将该RAM地址对应的状态寄存器置0。After any RAM address in any dual-port RAM is written into the link point information carrying the link list end flag bit, the state register corresponding to the RAM address is set to 1; correspondingly, after the data in the RAM address is read, the The status register corresponding to the RAM address is set to 0.
可选地，任意字符片段对应的哈希链表中的链点信息的个数不超过双口RAM的个数。Optionally, the number of link point information in the hash linked list corresponding to any character segment does not exceed the number of dual-port RAMs.
第二方面，本申请提供了一种数据处理装置，应用于硬件设备，包括：In a second aspect, the present application provides a data processing device applied to hardware devices, including:
获取模块，用于获取目标字符串；An acquisition module, used to acquire the target string;
确定模块，用于在所述目标字符串中确定多个字符片段；A determining module, configured to determine a plurality of character segments in the target character string;
处理模块，用于根据各个字符片段在所述目标字符串中的位置查询各个字符片段对应的哈希链表，并确定各个哈希链表在所述硬件设备的双口RAM中的写入地址；A processing module, configured to query the hash linked list corresponding to each character segment according to the position of each character segment in the target character string, and determine the write address of each hash linked list in the dual-port RAM of the hardware device;
写入模块，用于按照所述写入地址将每一哈希链表中的各链点信息写入所述双口RAM。The writing module is used to write the link point information in each hash linked list into the dual-port RAM according to the write address.
可选地，所述处理模块具体用于：Optionally, the processing module is specifically configured to:
根据各个字符片段在所述目标字符串中的位置以及位置在前先查询的规则确定各个字符片段的查询顺序；Determine the query order of each character segment according to the position of each character segment in the target character string and the rule that the position is inquired first;
按照所述查询顺序查询各个字符片段对应的哈希链表。The hash linked list corresponding to each character segment is queried according to the query sequence.
可选地，所述处理模块具体用于：针对任一字符片段，计算当前字符片段的哈希值；确定所述哈希值对应的当前需读地址；判断所述当前需读地址与已查到哈希链表的字符片段的哈希值是否相同；若否，则从所述当前需读地址中读取链点信息后，为该链点信息添加链表结束标志位，并将读取到的链点信息构建为当前字符片段对应的哈希链表。Optionally, the processing module is specifically used to: calculate the hash value of the current character segment for any character segment; determine the current address to be read corresponding to the hash value; determine the current address to be read and the checked address. Whether the hash value of the character segment to the hash linked list is the same; if not, after reading the link point information from the current address to be read, add the linked list end flag bit for the link point information, and read the The link point information is constructed as a hash list corresponding to the current character segment.
可选地，所述处理模块具体用于：若所述当前需读地址与已查到哈希链表的字符片段的哈希值相同，则从所述当前需读地址中读取链点信息后，为该链点信息添加链表未结束标志位，并确定下一需读地址，并执行所述判断所述当前需读地址与已查到哈希链表的字符片段的哈希值是否相同的步骤。Optionally, the processing module is specifically configured to: if the current address to be read is the same as the hash value of the character segment of the hash list that has been found, after reading the link point information from the current address to be read , adding the link list unfinished flag bit for the link point information, and determining the next address to be read, and performing the step of judging whether the current address to be read is the same as the hash value of the character segment of the hash list that has been found .
可选地，所述处理模块具体用于：Optionally, the processing module is specifically configured to:
将所述哈希值作为所述当前需读地址。The hash value is used as the current address to be read.
可选地，所述处理模块还包括：Optionally, the processing module also includes:
地址确定单元，用于按照所述查询顺序以及先查询写入地址在前的规则确定各个哈希链表在所述双口RAM中的写入地址。The address determination unit is configured to determine the write address of each hash linked list in the dual-port RAM according to the query order and the rule that the query write address comes first.
可选地，所述双口RAM为多个；相应地，写入模块具体用于：针对任一哈希链表，按照所述写入地址将当前哈希链表中的各链点信息分别写入各双口RAM。Optionally, there are multiple dual-port RAMs; correspondingly, the writing module is specifically configured to: for any hash linked list, write each link point information in the current hash linked list according to the write address Each dual-port RAM.
可选地，还包括：Optionally, also include:
读取模块，用于按照所述写入地址从各双口RAM中读出任一字符片段对应的哈希链表；Read module, for reading the hash linked list corresponding to any character segment from each dual-port RAM according to the write address;
选择模块，用于确定当前读取的哈希链表中的各链点信息对应的编码长度，并选择编码长度最长的链点信息作为当前字符片段的压缩信息。The selection module is configured to determine the code length corresponding to each link point information in the currently read hash linked list, and select the link point information with the longest code length as the compressed information of the current character segment.
可选地，所述选择模块具体用于：Optionally, the selection module is specifically used for:
以并行级联方式比较当前读取的哈希链表中的各链点信息对应的编码长度，以选择编码长度最长的链点信息作为当前字符片段的压缩信息。Comparing the encoding lengths corresponding to each link point information in the currently read hash linked list in a parallel cascading manner, to select the link point information with the longest encoding length as the compressed information of the current character segment.
可选地，还包括：Optionally, also include:
另一选择模块，用于若编码长度最长的链点信息有多个，则确定多个编码长度最长的链点信息对应的距离值，并选择距离值最小的链点信息作为当前字符片段的压缩信息。Another selection module is used to determine the distance values corresponding to the chain point information with the longest code length if there are multiple chain point information with the longest code length, and select the chain point information with the smallest distance value as the current character segment compressed information.
可选地，还包括：Optionally, also include:
地址状态更改模块，用于任意双口RAM中的任一RAM地址写入携带有链表结束标志位的链点信息后，将该RAM地址对应的状态寄存器置1；相应地，该RAM地址中的数据被读出后，将该RAM地址对应的状态寄存器置0。The address state change module is used for any RAM address in any dual-port RAM to write the link point information that carries the link list end flag bit, and then set the state register corresponding to the RAM address to 1; correspondingly, the After the data is read out, set the status register corresponding to the RAM address to 0.
可选地，任意字符片段对应的哈希链表中的链点信息的个数不超过双口RAM的个数。Optionally, the number of link point information in the hash linked list corresponding to any character segment does not exceed the number of dual-port RAMs.
第三方面，本申请提供了一种电子设备，包括：In a third aspect, the present application provides an electronic device, including:
存储器，用于存储计算机程序；memory for storing computer programs;
处理器，用于执行所述计算机程序，以实现前述公开的数据处理方法。A processor, configured to execute the computer program to implement the data processing method disclosed above.
第四方面，本申请提供了一种可读存储介质，用于保存计算机程序，其中，所述计算机程序被处理器执行时实现前述公开的数据处理方法。In a fourth aspect, the present application provides a readable storage medium for storing a computer program, wherein when the computer program is executed by a processor, the aforementioned disclosed data processing method is implemented.
通过以上方案可知，本申请提供了一种数据处理方法，应用于硬件设备，包括：获取目标字符串；在所述目标字符串中确定多个字符片段；根据各个字符片段在所述目标字符串中的位置查询各个字符片段对应的哈希链表，并确定各个哈希链表在所述硬件设备的双口RAM中的写入地址；按照所述写入地址将每一哈希链表中的各链点信息写入所述双口RAM。可见，本申请的有益效果为利用硬件设备获取目标字符串后，在目标字符串中确定多个字符片段，然后根据各个字符片段在目标字符串中的位置查询各个字符片段对应的哈希链表，并确定各个哈希链表在硬件设备的双口RAM中的写入地址，之后按照写入地址将每一哈希链表中的各链点信息写入硬件设备中的双口RAM，由此可使各个哈希链表按照其写入地址存储在双口RAM中。该方案在存储各个哈希链表之前，提前按照各个字符片段在目标字符串中的位置为各个哈希链表确定了写入地址，后续在使用双口RAM存储某一哈希链表时，也按照之前为该哈希链表确定的写入地址完成其中各链点信息的写入，也即：各个哈希链表可在双口RAM中按照预先确定的写入地址进行存储，使得各个哈希链表在RAM中的地址的顺序符合原查询顺序，而不会乱序存储，由此可实现：待压缩数据对应的各个哈希链表的顺序存储。那么后续可以按照RAM地址的顺序读出各个哈希链表，而不会乱序读取各个哈希链表，也不会影响后续压缩操作。同时，本申请利用硬件设备也可加速压缩效率。It can be seen from the above scheme that the present application provides a data processing method applied to hardware devices, including: obtaining a target character string; determining a plurality of character segments in the target character string; The position inquires the corresponding hash list of each character segment, and determines the write address of each hash list in the dual-port RAM of the hardware device; according to the write address, each chain in each hash list Point information is written into the dual-port RAM. It can be seen that the beneficial effect of the present application is to determine a plurality of character segments in the target character string after using the hardware device to obtain the target character string, and then query the hash list corresponding to each character segment according to the position of each character segment in the target character string, And determine the write address of each hash linked list in the dual-port RAM of the hardware device, then write each link point information in each hash linked list into the dual-port RAM in the hardware device according to the write address, so that the Each hash linked list is stored in dual-port RAM according to its write address. Before storing each hash linked list, this scheme determines the write address for each hash linked list according to the position of each character segment in the target string in advance, and then uses the dual-port RAM to store a certain hash linked list. The write address determined for the hash linked list completes the writing of each link point information, that is: each hash linked list can be stored in the dual-port RAM according to the predetermined write address, so that each hash linked list can be stored in the RAM The order of the addresses in is consistent with the original query order, and will not be stored out of order, so that the sequential storage of each hash list corresponding to the data to be compressed can be realized. Then, the hash linked lists can be read out in the order of the RAM addresses later, without reading the hash linked lists out of order, and without affecting subsequent compression operations. At the same time, the present application can also accelerate the compression efficiency by using hardware devices.
相应地，本申请提供的一种数据处理装置、设备及可读存储介质，也同样具有上述技术效果。Correspondingly, a data processing device, device, and readable storage medium provided by the present application also have the above-mentioned technical effects.
附图说明Description of drawings
为了更清楚地说明本申请实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本申请的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。In order to more clearly illustrate the technical solutions in the embodiments of the present application or the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only It is an embodiment of the present application, and those skilled in the art can also obtain other drawings according to the provided drawings without creative work.
图1为本申请公开的一种数据处理方法流程图；Fig. 1 is a flow chart of a data processing method disclosed in the present application;
图2为本申请公开的一种链点写入示意图；FIG. 2 is a schematic diagram of writing a chain point disclosed in the present application;
图3为本申请公开的一种构建哈希链表的示意图；Fig. 3 is a schematic diagram of constructing a hash linked list disclosed in the present application;
图4为本申请公开的一种并行级联比较方式与串行冒泡比较法的对比示意图；4 is a schematic diagram of a comparison between a parallel cascade comparison method disclosed in the present application and a serial bubble comparison method;
图5为本申请公开的一种比较结果递归传输示意图；FIG. 5 is a schematic diagram of recursive transmission of a comparison result disclosed in the present application;
图6为本申请公开的一种数据处理装置示意图；FIG. 6 is a schematic diagram of a data processing device disclosed in the present application;
图7为本申请公开的一种电子设备示意图。FIG. 7 is a schematic diagram of an electronic device disclosed in the present application.
具体实施方式Detailed ways
下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。The following will clearly and completely describe the technical solutions in the embodiments of the application with reference to the drawings in the embodiments of the application. Apparently, the described embodiments are only some of the embodiments of the application, not all of them. Based on the embodiments in this application, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the scope of protection of this application.
目前，在压缩数据时，可以查询预设字典，以构建待压缩数据的哈希链表。其中，针对任一压缩数据，会对其中的不同字符片段同时查询得到相应的哈希链表，而有的字符片段的哈希链表长，有的字符片段的哈希链表短，因此查到这些哈希链表的查询返回时间不定，也即：查询返回时间与各字符片段在压缩数据中的原顺序不一致，导致各个哈希链表乱序输出，影响数据压缩的后续处理。为此，本申请提供了一种数据处理方案，能够使待压缩数据对应的各个哈希链表顺序存储。Currently, when compressing data, you can query the preset dictionary to build a hash list of the data to be compressed. Among them, for any compressed data, different character fragments in it will be queried at the same time to obtain the corresponding hash list, and some character fragments have a long hash list, and some character fragments have a short hash list, so these hashes can be found The query return time of the hash linked list is uncertain, that is, the query return time is inconsistent with the original order of each character segment in the compressed data, resulting in the out-of-order output of each hash linked list, which affects the subsequent processing of data compression. For this reason, the present application provides a data processing scheme, which can store the respective hash lists corresponding to the data to be compressed sequentially.
参见图1所示，本申请实施例公开了一种数据处理方法，应用于硬件设备，包括：Referring to Figure 1, the embodiment of the present application discloses a data processing method applied to hardware devices, including:
S101、获取目标字符串。S101. Obtain a target character string.
S102、在目标字符串中确定多个字符片段。S102. Determine multiple character segments in the target character string.
在本实施例中，目标字符串为待压缩的数据。例如：目标字符串为：ABCDEFGH。相应地，在目标字符串中确定的多个字符片段可以为：ABC、BCD、CDE、DEF、EFG、FGH。可见，字符片段一般包括3个字符。In this embodiment, the target character string is the data to be compressed. For example: the target string is: ABCDEFGH. Correspondingly, the plurality of character segments determined in the target character string may be: ABC, BCD, CDE, DEF, EFG, FGH. It can be seen that a character segment generally includes 3 characters.
适用于本实施例的压缩算法有LZ77算法等。LZ77算法是一种常用的字典匹配算法，利用恒定大小的“滑动窗口”来处理数据中重复出现的字符串。字典的构建及字符串的匹配目前常用的算法就是利用哈希方法，提取固定字节的个别比特，然后根据特定的哈希函数计算哈希值，将计算出的哈希值作为写地址，将链点信息进行写入。字符串匹配时再利用该字符串固定字节的个别比特进行哈希，将哈希值作为读地址，以读出链点信息，然后根据此链点信息找到原始字典的字符串进行一一比较，进而得到一个匹配长度信息；匹配距离信息可以由当前查找字符串的位置信息和从字典中读出的匹配链点的位置信息两者之差计算而来。最终可以用一个匹配长度和匹配距离的信息作为一段字符的压缩信息。The compression algorithm applicable to this embodiment includes the LZ77 algorithm and the like. The LZ77 algorithm is a commonly used dictionary matching algorithm that utilizes a constant-sized "sliding window" to process repeated strings in the data. The current commonly used algorithm for dictionary construction and string matching is to use the hash method to extract individual bits of a fixed byte, and then calculate the hash value according to a specific hash function, and use the calculated hash value as the write address. The chain point information is written. When the string is matched, use the individual bits of the fixed byte of the string to hash, use the hash value as the read address to read out the link point information, and then find the string in the original dictionary according to the link point information for one-to-one comparison , and then obtain a matching length information; the matching distance information can be calculated from the difference between the position information of the current search string and the position information of the matching link read from the dictionary. Finally, the information of a matching length and a matching distance can be used as the compressed information of a segment of characters.
S103、根据各个字符片段在目标字符串中的位置查询各个字符片段对应的哈希链表，并确定各个哈希链表在硬件设备的双口RAM中的写入地址。S103. Query the hash linked list corresponding to each character segment according to the position of each character segment in the target character string, and determine the write address of each hash linked list in the dual-port RAM of the hardware device.
参照上述示例的目标字符串ABCDEFGH，ABC、BCD、CDE、DEF、EFG、FGH在目标字符串中的位置可以按序记录为：1、2、3、4、5、6，那么这6个字符片段的查询顺序按照1、2、3、4、5、6的顺序进行。可见，位置靠前的字符片段的查询顺序靠前。Referring to the target string ABCDEFGH in the above example, the positions of ABC, BCD, CDE, DEF, EFG, and FGH in the target string can be recorded in sequence as: 1, 2, 3, 4, 5, 6, then these 6 characters The query sequence of fragments is in the order of 1, 2, 3, 4, 5, and 6. It can be seen that the query order of the character segment at the front is at the top.
在一种具体实施方式中，根据各个字符片段在目标字符串中的位置查询各个字符片段对应的哈希链表，包括：根据各个字符片段在目标字符串中的位置以及位置在前先查询的规则确定各个字符片段的查询顺序；按照查询顺序查询各个字符片段对应的哈希链表。In a specific embodiment, querying the hash list corresponding to each character segment according to the position of each character segment in the target string includes: according to the position of each character segment in the target string and the rule that the position is first queried Determine the query sequence of each character segment; query the hash list corresponding to each character segment according to the query sequence.
其中，任一字符片段对应的哈希链表的查询过程包括：计算当前字符片段的哈希值；确定哈希值对应的当前需读地址；判断当前需读地址与已查到哈希链表的字符片段的哈希值是否相同；若否，则从当前需读地址中读取链点信息后，为该链点信息添加链表结束标志位，并将读取到的链点信息构建为当前字符片段对应的哈希链表。若当前需读地址与已查到哈希链表的字符片段的哈希值相同，则从当前需读地址中读取链点信息后，为该链点信息添加链表未结束标志位，并确定下一需读地址，并执行判断当前需读地址与已查到哈希链表的字符片段的哈希值是否相同的步骤，直至当前需读地址与已查到哈希链表的字符片段的哈希值不同。Wherein, the query process of the hash list corresponding to any character segment includes: calculating the hash value of the current character segment; determining the current address to be read corresponding to the hash value; judging the current address to be read and the characters in the hash list Whether the hash values of the segments are the same; if not, after reading the link point information from the current address to be read, add the link list end flag bit to the link point information, and construct the read link point information as the current character segment Corresponding hash list. If the current address to be read is the same as the hash value of the character segment of the hash linked list that has been found, after reading the link point information from the current address to be read, add the link list unfinished flag bit for the link point information, and determine the following One needs to read the address, and execute the step of judging whether the hash value of the current address to be read is the same as the character segment of the hash list that has been found, until the hash value of the current address to be read and the character segment of the hash list has been found different.
例如：上述字符片段ABC对应的哈希链表为：A1，A1中包括链表结束标志位。而查询字符片段BCD的哈希链表时，字符片段BCD的哈希值与字符片段ABC相同，此时以该哈希值作为当前需读地址，从中读取A1，并为A1添加链表未结束标志位（如0），之后确定下一需读地址，然后继续判断当前需读地址（此时的当前需读地址即前一步骤确定的下一需读地址）与已查到哈希链表的字符片段的哈希值是否相同；若是，则重复上述过程；若否，则从下一需读地址中读取A2，并为A2添加链表结束标志位（如1），如此可得到字符片段BCD的哈希链表：A1→A2，在此链表中，A1、A2为其链点信息，A1中包括链表未结束标志位，A2中包括链表结束标志位。可见，预先存有包括所有链点信息的字典，而查询某一字符片段对应的哈希链表，就是确定当前字符片段可对应哪些链点信息。For example: the hash linked list corresponding to the above character segment ABC is: A1, and A1 includes the end flag bit of the linked list. When querying the hash linked list of the character segment BCD, the hash value of the character segment BCD is the same as that of the character segment ABC. At this time, the hash value is used as the current address to be read, and A1 is read from it, and the linked list is not ended for A1. bit (such as 0), then determine the next address to be read, and then continue to judge the current address to be read (the current address to be read at this time is the next address to be read determined in the previous step) and the characters that have been found in the hash list Whether the hash values of the fragments are the same; if yes, repeat the above process; if not, read A2 from the next address to be read, and add the linked list end flag (such as 1) to A2, so that the character fragment BCD can be obtained Hash linked list: A1→A2, in this linked list, A1 and A2 are the link point information, A1 includes the linked list unfinished flag bit, and A2 includes the linked list ended flag bit. It can be seen that a dictionary including all link information is stored in advance, and querying the hash list corresponding to a certain character segment is to determine which link information the current character segment can correspond to.
其中，确定哈希值对应的当前需读地址，包括：将哈希值作为当前需读地址。下一需读地址可按照预设算法或策略确定。一个哈希链表最少包括1个链点信息，最多包括预设值个链点信息。其中，预设值不大于双口RAM的个数。可见，将一个字符片段的哈希值作为需读地址，从此地址中可读到该字符片段的偏移地址，该偏移地址为该字符片段的哈希链表的其中一个链点信息。Wherein, determining the current address to be read corresponding to the hash value includes: using the hash value as the current address to be read. The next address to be read can be determined according to a preset algorithm or strategy. A hash linked list includes at least 1 link point information, and includes a preset value of link point information at most. Wherein, the preset value is not greater than the number of dual-port RAMs. It can be seen that the hash value of a character segment is used as the address to be read, from which the offset address of the character segment can be read, and the offset address is one of the link point information of the hash linked list of the character segment.
S104、按照各个哈希链表在硬件设备的双口RAM中的写入地址将每一哈希链表中的各链点信息写入双口RAM。S104. Write the link point information in each hash link list into the dual-port RAM according to the write address of each hash link list in the dual-port RAM of the hardware device.
如上所述，位置靠前的字符片段的查询顺序靠前，而查询顺序靠前的字符片段的写入地址靠前。可见，查询顺序和写入地址依赖于字符片段在目标字符串中的位置。因此在一种具体实施方式中，确定各个哈希链表在硬件设备的双口RAM中的写入地址，包括：按照查询顺序以及先查询写入地址在前的规则确定各个哈希链表在双口RAM中的写入地址。As mentioned above, the query order of the character segment earlier in the query order is earlier, and the writing address of the character segment earlier in the query order is earlier. It can be seen that the query order and write address depend on the position of the character segment in the target string. Therefore in a specific implementation manner, determining the write address of each hash linked list in the dual-port RAM of the hardware device includes: determining the write address of each hash linked list in the dual-port RAM according to the query sequence and the rule that the first query write address comes first. Write address in RAM.
在一种具体实施方式中，双口RAM为多个；相应地，任一哈希链表中的各链点信息的写入过程包括：按照写入地址将当前哈希链表中的各链点信息分别写入各双口RAM。In a specific embodiment, there are multiple dual-port RAMs; correspondingly, the writing process of each link point information in any hash linked list includes: writing each link point information in the current hash linked list according to the write address Write to each dual-port RAM respectively.
请参见图2，若双口RAM有6个，分别为：RAM0、RAM1、RAM2、RAM3、RAM4、RAM5，则按照字符片段ABC、BCD、CDE、DEF、EFG、FGH的位置：1、2、3、4、5、6，它们的写入地址可以是地址0、地址1、地址2、地址3、地址4、地址5。也即：当ABC对应的哈希链表为：A1时，A1写入RAM0的地址0，而RAM1-RAM5的地址0不写数据。当BCD对应的哈希链表为：A1→A2时，A1写入RAM0的地址1，A2写入RAM1的地址1，而RAM2-RAM5的地址1不写数据。当DEF对应的哈希链表有5个链点信息时，这5个链点信息分别写入RAM0的地址3、RAM1的地址3、RAM2的地址3、RAM3的地址3、RAM4的地址3。可见，任意字符片段对应的哈希链表中的链点信息的个数不能超过双口RAM的个数，否则哈希链表无法被完全存储。Please refer to Figure 2, if there are 6 dual-port RAMs, namely: RAM0, RAM1, RAM2, RAM3, RAM4, and RAM5, then according to the positions of the character segments ABC, BCD, CDE, DEF, EFG, and FGH: 1, 2, 3, 4, 5, 6, their write addresses can be address 0, address 1, address 2, address 3, address 4, address 5. That is to say: when the hash list corresponding to ABC is: A1, A1 writes the address 0 of RAM0, and the address 0 of RAM1-RAM5 does not write data. When the hash list corresponding to BCD is: A1→A2, A1 is written into address 1 of RAM0, A2 is written into address 1 of RAM1, and address 1 of RAM2-RAM5 does not write data. When the hash list corresponding to DEF has 5 link point information, these 5 link point information are respectively written into address 3 of RAM0, address 3 of RAM1, address 3 of RAM2, address 3 of RAM3, and address 3 of RAM4. It can be seen that the number of link point information in the hash linked list corresponding to any character segment cannot exceed the number of dual-port RAM, otherwise the hash linked list cannot be completely stored.
需要说明的是，基于各个字符片段对应的哈希链表可确定其压缩信息。在一种具体实施方式中，还包括：按照写入地址从各双口RAM中读出任一字符片段对应的哈希链表；确定当前读取的哈希链表中的各链点信息对应的编码长度，并选择编码长度最长的链点信息作为当前字符片段的压缩信息。若编码长度最长的链点信息有多个，则确定多个编码长度最长的链点信息对应的距离值，并选择距离值最小的链点信息作为当前字符片段的压缩信息。其中，一个链点信息对应有一个编码长度和一个距离值。It should be noted that the compression information of each character segment can be determined based on the hash list corresponding to each character segment. In a specific embodiment, it also includes: reading the hash linked list corresponding to any character segment from each dual-port RAM according to the write address; determining the code length corresponding to each link point information in the currently read hash linked list , and select the chain point information with the longest encoding length as the compressed information of the current character segment. If there are multiple chain point information with the longest code length, then determine the distance values corresponding to the chain point information with the longest code length, and select the chain point information with the smallest distance value as the compressed information of the current character segment. Wherein, a chain point information corresponds to a coding length and a distance value.
其中，选择编码长度最长的链点信息作为当前字符片段的压缩信息，包括：以并行级联方式比较当前读取的哈希链表中的各链点信息对应的编码长度，以选择编码长度最长的链点信息作为当前字符片段的压缩信息。选择一个链点信息作为某一字符片段的压缩信息，表示：该链点信息对应的编码长度和距离值可以用于解压缩出相应字符片段。Wherein, selecting the link point information with the longest encoding length as the compressed information of the current character segment includes: comparing the encoding lengths corresponding to each link point information in the currently read hash linked list in a parallel cascading manner, to select the link point information with the longest encoding length The long chain point information is used as the compression information of the current character segment. Selecting a link point information as the compressed information of a certain character segment means that the encoding length and distance value corresponding to the link point information can be used to decompress the corresponding character segment.
本实施例中的双口RAM具有两套完全独立的数据线、地址线和读写控制线，可用于提高RAM的吞吐率。为了实现读写控制，本实施例在任意双口RAM中的任一RAM地址写入携带有链表结束标志位的链点信息后，将该RAM地址对应的状态寄存器置1；相应地，该RAM地址中的数据被读出后，将该RAM地址对应的状态寄存器置0。The dual-port RAM in this embodiment has two sets of completely independent data lines, address lines and read-write control lines, which can be used to improve the throughput rate of the RAM. In order to realize read and write control, after any RAM address in any dual-port RAM is written into the link point information carrying the link list end flag bit in this embodiment, the state register corresponding to the RAM address is set to 1; correspondingly, the RAM After the data in the address is read out, set the status register corresponding to the RAM address to 0.
可见，本申请利用硬件设备获取目标字符串后，在目标字符串中确定多个字符片段，然后根据各个字符片段在目标字符串中的位置查询各个字符片段对应的哈希链表，并确定各个哈希链表在硬件设备的双口RAM中的写入地址，之后按照写入地址将每一哈希链表中的各链点信息写入硬件设备中的双口RAM，由此可使各个哈希链表按照其写入地址存储在双口RAM中。该方案在存储各个哈希链表之前，提前按照各个字符片段在目标字符串中的位置为各个哈希链表确定了写入地址，后续在使用双口RAM存储某一哈希链表时，也按照之前为该哈希链表确定的写入地址完成其中各链点信息的写入，使得各个哈希链表在RAM中的地址的顺序符合原查询顺序，而不会乱序存储，由此可实现：待压缩数据对应的各个哈希链表的顺序存储。那么后续可以按照RAM地址的顺序读出各个哈希链表，而不会乱序读取各个哈希链表，也不会影响后续压缩操作。同时，本申请利用硬件设备也可加速压缩效率。It can be seen that, after the present application obtains the target character string using hardware equipment, a plurality of character segments are determined in the target character string, and then the hash list corresponding to each character segment is queried according to the position of each character segment in the target character string, and each hash is determined. The write address of the linked list in the dual-port RAM of the hardware device, and then write each link point information in each hash linked list into the dual-port RAM in the hardware device according to the write address, so that each hash linked list It is stored in dual-port RAM according to its write address. Before storing each hash linked list, this scheme determines the write address for each hash linked list according to the position of each character segment in the target string in advance, and then uses the dual-port RAM to store a certain hash linked list. The write address determined for the hash linked list completes the writing of the information of each link point in it, so that the order of the addresses of each hash linked list in RAM conforms to the original query order, and will not be stored out of order, so that it can be realized: The sequential storage of each hash list corresponding to the compressed data. Then, the hash linked lists can be read out in the order of the RAM addresses later, without reading the hash linked lists out of order, and without affecting subsequent compression operations. At the same time, the present application can also accelerate the compression efficiency by using hardware devices.
下述实施例使用FPGA这一硬件设计实现本申请，也能够解决哈希匹配存在的乱序输出问题，同时以并行级联比较方式有效提高了链点筛选效率，还可以基于RTL（RegisterTransfer Level，寄存器转换级电路）方便在各个平台移植。The following embodiments use the hardware design of FPGA to implement this application, which can also solve the problem of out-of-order output in hash matching, and effectively improve the efficiency of chain point screening by means of parallel cascade comparison. It can also be based on RTL (RegisterTransfer Level, register conversion level circuit) to facilitate porting on various platforms.
一般哈希查表选取字符串的前三个字节的个别比特位进行哈希运算。假设需要查表的字符串为ABCDEFG…，那么首先选取ABC进行哈希，得到哈希值a1，读取地址a1对应的哈希表内容A1，将A1写入RAM1。如果存在哈希冲突，那么继续向后查找，得到A2、A3…A8等。每查询到一个对应的链点信息就把对应的链点信息写入对应的双口RAM。同理，BCDEFG…字符串进行查表时，选取前三个字节BCD进行哈希，得到哈希值b1，读取地址b1对应的哈希表内容B1，若不存在哈希冲突，则直接将B1写入双口RAM。其他以此类推，将以CDE、DEF、EFG…开头的字符串匹配到的链点信息写入双口RAM。Generally, the hash lookup table selects the individual bits of the first three bytes of the string for hash operation. Assuming that the string that needs to be looked up is ABCDEFG..., then first select ABC for hashing to get the hash value a1, read the hash table content A1 corresponding to the address a1, and write A1 into RAM1. If there is a hash collision, then continue to look backwards to get A2, A3...A8, etc. Whenever a corresponding link point information is found, the corresponding link point information is written into the corresponding dual-port RAM. Similarly, when the BCDEFG... string is used for table lookup, the first three bytes BCD are selected for hashing to obtain the hash value b1, and the hash table content B1 corresponding to the address b1 is read. If there is no hash conflict, directly Write B1 into dual-port RAM. By analogy, write the chain point information matched by the string starting with CDE, DEF, EFG... into the dual-port RAM.
可见，ABC的哈希值a1即为当前读地址，从此地址中可读到ABC的偏移地址，该偏移地址为ABC的哈希链表的第一个链点信息。如图3所示，如果ABC的偏移地址为0000，其存储在RAM中的地址a1中，该地址a1为ABC的哈希值，且ABC的哈希链表仅包括0000。如果下一字符片段BCD的哈希值也是a1，那么先在地址a1中查到0000作为第一个链点，然后按照预设算法确定下一地址X，在地址X中查出另一链点0030；如果X不与其他字符片段的哈希冲突，那么确定字符片段BCD的哈希链表为：0000→0030。It can be seen that the hash value a1 of ABC is the current read address, and the offset address of ABC can be read from this address, which is the first link point information of the hash linked list of ABC. As shown in FIG. 3, if the offset address of ABC is 0000, it is stored in the address a1 in RAM, the address a1 is the hash value of ABC, and the hash list of ABC only includes 0000. If the hash value of the next character segment BCD is also a1, then find 0000 in address a1 as the first link point, then determine the next address X according to the preset algorithm, and find another link point in
其中，写入双口RAM的数据格式为一个比特的表示链表是否结束的标志位加链点信息。若当前链点为最后一个链点，则该标志为1；否则该标志位为0。当写入一个链表的最后一个链点信息至RAM地址，则该地址对应的地址状态寄存器置1。Wherein, the data format written into the dual-port RAM is a one-bit flag indicating whether the linked list ends plus link point information. If the current chain point is the last chain point, the flag is 1; otherwise, the flag is 0. When the last link point information of a linked list is written to the RAM address, the address status register corresponding to the address is set to 1.
双口RAM的读控制是根据后级数据处理通道的个数顺序读取的，例如：后级为双通道处理，则每次读取两个地址的RAM数据。读取一个链表的最后一个链点信息之后，相应地址的地址状态寄存器要置0。可见，从双口RAM每次读几个地址的数据，取决于后级数据处理通道的个数。其中，双口RAM的深度取决于链表长度（即链表中的链点总数）。双口RAM的地址宽度为一个比特的链点结束标志加上8个比特的链点数据，共9比特。The read control of dual-port RAM is read sequentially according to the number of subsequent data processing channels. For example, if the subsequent stage is dual-channel processing, the RAM data of two addresses are read each time. After reading the last link point information of a linked list, the address status register of the corresponding address should be set to 0. It can be seen that reading the data of several addresses each time from the dual-port RAM depends on the number of subsequent data processing channels. Among them, the depth of the dual-port RAM depends on the length of the linked list (that is, the total number of link points in the linked list). The address width of the dual-port RAM is a one-bit chain point end flag plus 8-bit chain point data, a total of 9 bits.
具体的实现步骤包括：The specific implementation steps include:
（1）将字符片段的相对偏移位置作为双口RAM的写地址信息，将哈希匹配的链点信息和一个比特的链点是否结束标志信息写入对应的双口RAM。(1) Use the relative offset position of the character segment as the write address information of the dual-port RAM, and write the hash-matched chain point information and one-bit chain point end flag information into the corresponding dual-port RAM.
（2）当一个RAM地址存储一个链表的最后一个链点信息时，写入后将此地址状态寄存器对应的标志置为1。(2) When a RAM address stores the last link point information of a linked list, set the flag corresponding to the address status register to 1 after writing.
（3）根据后级的数据处理通道顺序读取双口RAM中的链点数据。(3) Read the chain point data in the dual-port RAM in sequence according to the data processing channels of the subsequent stage.
（4）读取一个链表的最后一个链点后，将对应地址的状态寄存器的标志位置0。(4) After reading the last link point of a linked list, set the flag position of the status register corresponding to the address to 0.
读取得到一条哈希链表后，对其中的链点进行比较，以选取一个最优的链点。其中，一个链点对应有一个编码长度和一个距离，选编码长度最长的链点为最优链点。若存在多个长度最长的链点，从中选取距离相对最短的链点。其中，比较一条哈希链表中的链点时，采用并行级联比较方式，此方式相对于传统的串行冒泡比较法，可以提高链点筛选的速率。请参见图4，当哈希链表长度为8时，纵向示意的串行冒泡比较法需要7个时钟周期，而横向示意的并行级联比较法仅需要3个时钟周期。并且，并行级联比较方式相对于完全并行比较，中间增加的时序逻辑能够有效改善模块时序。After reading a hash linked list, compare the link points in it to select an optimal link point. Among them, a chain point corresponds to a code length and a distance, and the chain point with the longest code length is selected as the optimal chain point. If there are multiple chain points with the longest length, select the chain point with the shortest distance among them. Among them, when comparing the link points in a hash linked list, the parallel cascading comparison method is adopted. Compared with the traditional serial bubble comparison method, this method can improve the link point screening rate. Please refer to FIG. 4 , when the length of the hash list is 8, the serial bubble comparison method shown vertically requires 7 clock cycles, while the parallel cascaded comparison method shown horizontally only needs 3 clock cycles. Moreover, compared with the complete parallel comparison method, the timing logic added in the middle can effectively improve the module timing.
如果一条链表中的链点少于8，则比较得到结果后，在后续时钟周期内直接传递比较结果，而无需在后续时钟周期内进行比较。如图5所示，一条链表中的链点只有A1和A2这两个，那么在第一个时钟内得到A21这一比较结果后，在后续第2、3个时钟内，直接传递A21到A31、A41。If the number of link points in a linked list is less than 8, after the comparison result is obtained, the comparison result is directly transferred in the subsequent clock cycle without comparison in the subsequent clock cycle. As shown in Figure 5, there are only two link points in a linked list, A1 and A2, then after the comparison result of A21 is obtained in the first clock, in the subsequent second and third clocks, directly transfer A21 to A31 , A41.
可见，本实施例利用FPGA内部的双口RAM，通过读写控制逻辑，能够使原本乱序输出的链表顺序输出。同时链点比较模块对多个相同地址的链点进行并行级联比较，有效缩短了链点筛选速率，提高了最终的压缩效率。It can be seen that in this embodiment, the dual-port RAM inside the FPGA can be used to output the linked list that was originally output out of order through the read and write control logic. At the same time, the chain point comparison module performs parallel cascade comparison on multiple chain points with the same address, which effectively shortens the chain point screening rate and improves the final compression efficiency.
下面对本申请实施例提供的一种数据处理装置进行介绍，下文描述的一种数据处理装置与上文描述的一种数据处理方法可以相互参照。A data processing device provided in an embodiment of the present application is introduced below, and a data processing device described below and a data processing method described above may refer to each other.
参见图6所示，本申请实施例公开了一种数据处理装置，应用于硬件设备，包括：Referring to Figure 6, the embodiment of the present application discloses a data processing device, which is applied to hardware equipment, including:
获取模块601，用于获取目标字符串；An
确定模块602，用于在目标字符串中确定多个字符片段；A determining
处理模块603，用于根据各个字符片段在目标字符串中的位置查询各个字符片段对应的哈希链表，并确定各个哈希链表在硬件设备的双口RAM中的写入地址；
写入模块604，用于按照写入地址将每一哈希链表中的各链点信息写入双口RAM。The
在一种具体实施方式中，处理模块具体用于：In a specific implementation manner, the processing module is specifically used for:
根据各个字符片段在目标字符串中的位置以及位置在前先查询的规则确定各个字符片段的查询顺序；Determine the query order of each character segment according to the position of each character segment in the target string and the rule that the position is first queried;
按照查询顺序查询各个字符片段对应的哈希链表。Query the hash list corresponding to each character segment according to the query order.
在一种具体实施方式中，处理模块具体用于：针对任一字符片段，计算当前字符片段的哈希值；确定哈希值对应的当前需读地址；判断当前需读地址与已查到哈希链表的字符片段的哈希值是否相同；若否，则从当前需读地址中读取链点信息后，为该链点信息添加链表结束标志位，并将读取到的链点信息构建为当前字符片段对应的哈希链表。In a specific implementation, the processing module is specifically used to: calculate the hash value of the current character segment for any character segment; determine the current address to be read corresponding to the hash value; determine the current address to be read and the hash value that has been found Whether the hash values of the character fragments of the linked list are the same; if not, after reading the link point information from the current address to be read, add the end flag bit of the linked list to the link point information, and construct the read link point information It is the hash list corresponding to the current character segment.
在一种具体实施方式中，处理模块具体用于：若当前需读地址与已查到哈希链表的字符片段的哈希值相同，则从当前需读地址中读取链点信息后，为该链点信息添加链表未结束标志位，并确定下一需读地址，并执行判断当前需读地址与已查到哈希链表的字符片段的哈希值是否相同的步骤。In a specific implementation, the processing module is specifically used for: if the current address to be read is the same as the hash value of the character segment of the hash linked list that has been found, after reading the link point information from the current address to be read, it is The chain point information adds the link list unfinished flag bit, and determines the next address to be read, and performs the step of judging whether the current address to be read is the same as the hash value of the character segment that has been found in the hash list.
在一种具体实施方式中，处理模块具体用于：In a specific implementation manner, the processing module is specifically used for:
将哈希值作为当前需读地址。Use the hash value as the current read address.
在一种具体实施方式中，处理模块还包括：In a specific implementation manner, the processing module also includes:
地址确定单元，用于按照查询顺序以及先查询写入地址在前的规则确定各个哈希链表在双口RAM中的写入地址。The address determination unit is used to determine the write address of each hash linked list in the dual-port RAM according to the query sequence and the rule that the query write address comes first.
在一种具体实施方式中，双口RAM为多个；相应地，写入模块具体用于：针对任一哈希链表，按照写入地址将当前哈希链表中的各链点信息分别写入各双口RAM。In a specific implementation manner, there are multiple dual-port RAMs; correspondingly, the writing module is specifically used to: for any hash linked list, write each link point information in the current hash linked list according to the write address Each dual-port RAM.
在一种具体实施方式中，还包括：In a specific embodiment, it also includes:
读取模块，用于按照写入地址从各双口RAM中读出任一字符片段对应的哈希链表；The reading module is used to read out the hash linked list corresponding to any character segment from each dual-port RAM according to the write address;
选择模块，用于确定当前读取的哈希链表中的各链点信息对应的编码长度，并选择编码长度最长的链点信息作为当前字符片段的压缩信息。The selection module is configured to determine the code length corresponding to each link point information in the currently read hash linked list, and select the link point information with the longest code length as the compressed information of the current character segment.
在一种具体实施方式中，选择模块具体用于：In a specific implementation manner, the selection module is specifically used for:
以并行级联方式比较当前读取的哈希链表中的各链点信息对应的编码长度，以选择编码长度最长的链点信息作为当前字符片段的压缩信息。Comparing the encoding lengths corresponding to each link point information in the currently read hash linked list in a parallel cascading manner, to select the link point information with the longest encoding length as the compressed information of the current character segment.
在一种具体实施方式中，还包括：In a specific embodiment, it also includes:
另一选择模块，用于若编码长度最长的链点信息有多个，则确定多个编码长度最长的链点信息对应的距离值，并选择距离值最小的链点信息作为当前字符片段的压缩信息。Another selection module is used to determine the distance values corresponding to the chain point information with the longest code length if there are multiple chain point information with the longest code length, and select the chain point information with the smallest distance value as the current character segment compressed information.
在一种具体实施方式中，还包括：In a specific embodiment, it also includes:
地址状态更改模块，用于任意双口RAM中的任一RAM地址写入携带有链表结束标志位的链点信息后，将该RAM地址对应的状态寄存器置1；相应地，该RAM地址中的数据被读出后，将该RAM地址对应的状态寄存器置0。The address state change module is used for any RAM address in any dual-port RAM to write the link point information that carries the link list end flag bit, and then set the state register corresponding to the RAM address to 1; correspondingly, the After the data is read out, set the status register corresponding to the RAM address to 0.
在一种具体实施方式中，任意字符片段对应的哈希链表中的链点信息的个数不超过双口RAM的个数。In a specific implementation manner, the number of link point information in the hash list corresponding to any character segment does not exceed the number of dual-port RAMs.
其中，关于本实施例中各个模块、单元更加具体的工作过程可以参考前述实施例中公开的相应内容，在此不再进行赘述。For the more specific working process of each module and unit in this embodiment, reference may be made to the corresponding content disclosed in the foregoing embodiments, and details are not repeated here.
可见，本实施例提供了一种数据处理装置，能够实现：待压缩数据对应的各个哈希链表的顺序存储。It can be seen that this embodiment provides a data processing device capable of realizing sequential storage of each hash list corresponding to the data to be compressed.
下面对本申请实施例提供的一种电子设备进行介绍，下文描述的一种电子设备与上文描述的一种数据处理方法及装置可以相互参照。An electronic device provided by an embodiment of the present application is introduced below, and the electronic device described below and the data processing method and apparatus described above may refer to each other.
参见图7所示，本申请实施例公开了一种电子设备，包括：Referring to Figure 7, the embodiment of the present application discloses an electronic device, including:
存储器701，用于保存计算机程序；
处理器702，用于执行所述计算机程序，以实现上述任意实施例公开的方法。The
进一步的，本申请实施例还提供了一种服务器来作为上述电子设备。该服务器，具体可以包括：至少一个处理器、至少一个存储器、电源、通信接口、输入输出接口和通信总线。其中，所述存储器用于存储计算机程序，所述计算机程序由所述处理器加载并执行，以实现前述任一实施例公开的数据处理方法中的相关步骤。Further, the embodiment of the present application also provides a server as the above-mentioned electronic device. The server may specifically include: at least one processor, at least one memory, a power supply, a communication interface, an input and output interface, and a communication bus. Wherein, the memory is used to store a computer program, and the computer program is loaded and executed by the processor to implement relevant steps in the data processing method disclosed in any of the foregoing embodiments.
本实施例中，电源用于为服务器上的各硬件设备提供工作电压；通信接口能够为服务器创建与外界设备之间的数据传输通道，其所遵循的通信协议是能够适用于本申请技术方案的任意通信协议，在此不对其进行具体限定；输入输出接口，用于获取外界输入数据或向外界输出数据，其具体的接口类型可以根据具体应用需要进行选取，在此不进行具体限定。In this embodiment, the power supply is used to provide working voltage for each hardware device on the server; the communication interface can create a data transmission channel between the server and external devices, and the communication protocol it follows is applicable to the technical solution of this application Any communication protocol is not specifically limited here; the input/output interface is used to obtain external input data or output data to the external, and its specific interface type can be selected according to specific application needs, and is not specifically limited here.
另外，存储器作为资源存储的载体，可以是只读存储器、随机存储器、磁盘或者光盘等，其上所存储的资源包括操作系统、计算机程序及数据等，存储方式可以是短暂存储或者永久存储。In addition, memory, as a resource storage carrier, can be read-only memory, random access memory, magnetic disk or optical disk, etc. The resources stored on it include operating system, computer program and data, etc., and the storage method can be temporary storage or permanent storage.
其中，操作系统用于管理与控制服务器上的各硬件设备以及计算机程序，以实现处理器对存储器中数据的运算与处理，其可以是Windows Server、Netware、Unix、Linux等。计算机程序除了包括能够用于完成前述任一实施例公开的数据处理方法的计算机程序之外，还可以进一步包括能够用于完成其他特定工作的计算机程序。数据除了可以包括虚拟机等数据外，还可以包括虚拟机的开发商信息等数据。Wherein, the operating system is used to manage and control various hardware devices and computer programs on the server, so as to realize the calculation and processing of the data in the memory by the processor, which may be Windows Server, Netware, Unix, Linux, etc. In addition to computer programs that can be used to complete the data processing methods disclosed in any of the foregoing embodiments, the computer programs may further include computer programs that can be used to complete other specific tasks. In addition to data such as the virtual machine, the data may also include data such as developer information of the virtual machine.
进一步的，本申请实施例还提供了一种终端来作为上述电子设备。该终端具体可以包括但不限于智能手机、平板电脑、笔记本电脑或台式电脑等。Further, the embodiment of the present application also provides a terminal as the above-mentioned electronic device. The terminal specifically may include, but is not limited to, a smart phone, a tablet computer, a notebook computer or a desktop computer, and the like.
通常，本实施例中的终端包括有：处理器和存储器。Generally, the terminal in this embodiment includes: a processor and a memory.
其中，处理器可以包括一个或多个处理核心，比如4核心处理器、8核心处理器等。处理器可以采用DSP(Digital Signal Processing，数字信号处理)、FPGA(Field－Programmable Gate Array，现场可编程门阵列)、PLA(Programmable Logic Array，可编程逻辑阵列)中的至少一种硬件形式来实现。处理器也可以包括主处理器和协处理器，主处理器是用于对在唤醒状态下的数据进行处理的处理器，也称CPU(Central Processing Unit，中央处理器)；协处理器是用于对在待机状态下的数据进行处理的低功耗处理器。在一些实施例中，处理器可以在集成有GPU(Graphics Processing Unit，图像处理器)，GPU用于负责显示屏所需要显示的内容的渲染和绘制。一些实施例中，处理器还可以包括AI(ArtificialIntelligence，人工智能)处理器，该AI处理器用于处理有关机器学习的计算操作。Wherein, the processor may include one or more processing cores, such as a 4-core processor, an 8-core processor, and the like. The processor can be realized by at least one hardware form of DSP (Digital Signal Processing, digital signal processing), FPGA (Field-Programmable Gate Array, field programmable gate array), PLA (Programmable Logic Array, programmable logic array) . The processor can also include a main processor and a coprocessor, the main processor is a processor for processing data in the wake-up state, also called a CPU (Central Processing Unit, central processing unit); Low-power processor for processing data in standby state. In some embodiments, the processor may be integrated with a GPU (Graphics Processing Unit, image processor), and the GPU is used for rendering and drawing content that needs to be displayed on the display screen. In some embodiments, the processor may further include an AI (Artificial Intelligence, artificial intelligence) processor, where the AI processor is configured to process computing operations related to machine learning.
存储器可以包括一个或多个计算机可读存储介质，该计算机可读存储介质可以是非暂态的。存储器还可包括高速随机存取存储器，以及非易失性存储器，比如一个或多个磁盘存储设备、闪存存储设备。本实施例中，存储器至少用于存储以下计算机程序，其中，该计算机程序被处理器加载并执行之后，能够实现前述任一实施例公开的由终端侧执行的数据处理方法中的相关步骤。另外，存储器所存储的资源还可以包括操作系统和数据等，存储方式可以是短暂存储或者永久存储。其中，操作系统可以包括Windows、Unix、Linux等。数据可以包括但不限于应用程序的更新信息。The memory may include one or more computer-readable storage media, which may be non-transitory. Memory may also include high-speed random access memory, and non-volatile memory, such as one or more magnetic disk storage devices, flash memory storage devices. In this embodiment, the memory is at least used to store the following computer program, wherein, after the computer program is loaded and executed by the processor, relevant steps in the data processing method performed by the terminal side disclosed in any of the foregoing embodiments can be implemented. In addition, the resources stored in the memory may also include an operating system and data, etc., and the storage method may be temporary storage or permanent storage. Wherein, the operating system may include Windows, Unix, Linux and so on. Data may include, but is not limited to, application update information.
在一些实施例中，终端还可包括有显示屏、输入输出接口、通信接口、传感器、电源以及通信总线。In some embodiments, the terminal may further include a display screen, an input/output interface, a communication interface, a sensor, a power supply, and a communication bus.
下面对本申请实施例提供的一种可读存储介质进行介绍，下文描述的一种可读存储介质与上文描述的一种数据处理方法、装置及设备可以相互参照。A readable storage medium provided by an embodiment of the present application is introduced below, and a readable storage medium described below and a data processing method, device, and device described above may refer to each other.
一种可读存储介质，用于保存计算机程序，其中，所述计算机程序被处理器执行时实现前述实施例公开的数据处理方法。A readable storage medium is used to store a computer program, wherein when the computer program is executed by a processor, the data processing method disclosed in the foregoing embodiments is implemented.
本申请涉及的“第一”、“第二”、“第三”、“第四”等(如果存在)是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。应该理解这样使用的数据在适当情况下可以互换，以便这里描述的实施例能够以除了在这里图示或描述的内容以外的顺序实施。此外，术语“包括”和“具有”以及他们的任何变形，意图在于覆盖不排他的包含，例如，包含了一系列步骤或单元的过程、方法或设备不必限于清楚地列出的那些步骤或单元，而是可包括没有清楚地列出的或对于这些过程、方法或设备固有的其它步骤或单元。"First", "second", "third", "fourth" and the like referred to in the present application, if any, are used to distinguish similar objects and not necessarily to describe a specific order or sequence. It is to be understood that the terms so used are interchangeable under appropriate circumstances such that the embodiments described herein can be practiced in sequences other than those illustrated or described herein. Furthermore, the terms "comprising" and "having", as well as any variations thereof, are intended to cover a non-exclusive inclusion, e.g. a process, method or apparatus comprising a series of steps or elements is not necessarily limited to those steps or elements explicitly listed , but may include other steps or elements not explicitly listed or inherent to the process, method or apparatus.
需要说明的是，在本申请中涉及“第一”、“第二”等的描述仅用于描述目的，而不能理解为指示或暗示其相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。另外，各个实施例之间的技术方案可以相互结合，但是必须是以本领域普通技术人员能够实现为基础，当技术方案的结合出现相互矛盾或无法实现时应当认为这种技术方案的结合不存在，也不在本申请要求的保护范围之内。It should be noted that the descriptions in this application involving "first", "second" and so on are for descriptive purposes only, and should not be understood as indicating or implying their relative importance or implicitly indicating the number of indicated technical features . Thus, the features defined as "first" and "second" may explicitly or implicitly include at least one of these features. In addition, the technical solutions of the various embodiments can be combined with each other, but it must be based on the realization of those skilled in the art. When the combination of technical solutions is contradictory or cannot be realized, it should be considered that the combination of technical solutions does not exist , nor within the scope of protection required by the present application.
本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其它实施例的不同之处，各个实施例之间相同或相似部分互相参见即可。Each embodiment in this specification is described in a progressive manner, each embodiment focuses on the difference from other embodiments, and the same or similar parts of each embodiment can be referred to each other.
结合本文中所公开的实施例描述的方法或算法的步骤可以直接用硬件、处理器执行的软件模块，或者二者的结合来实施。软件模块可以置于随机存储器（RAM）、内存、只读存储器（ROM）、电可编程ROM、电可擦除可编程ROM、寄存器、硬盘、可移动磁盘、CD-ROM、或技术领域内所公知的任意其它形式的可读存储介质中。The steps of the methods or algorithms described in connection with the embodiments disclosed herein may be directly implemented by hardware, software modules executed by a processor, or a combination of both. Software modules can be placed in random access memory (RAM), internal memory, read-only memory (ROM), electrically programmable ROM, electrically erasable programmable ROM, registers, hard disk, removable disk, CD-ROM, or any other Any other known readable storage medium.
本文中应用了具体个例对本申请的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本申请的方法及其核心思想；同时，对于本领域的一般技术人员，依据本申请的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本申请的限制。In this paper, specific examples are used to illustrate the principles and implementation methods of the application. The descriptions of the above embodiments are only used to help understand the method and core idea of the application; meanwhile, for those of ordinary skill in the art, according to the application There will be changes in the specific implementation and scope of application. In summary, the content of this specification should not be construed as limiting the application.
Claims (13)
Translated fromChinesePriority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211592819.2ACN115577149B (en) | 2022-12-13 | 2022-12-13 | Data processing method, device and equipment and readable storage medium |
| PCT/CN2023/101223WO2024124843A1 (en) | 2022-12-13 | 2023-06-20 | Data processing method and apparatus, and device and readable storage medium |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211592819.2ACN115577149B (en) | 2022-12-13 | 2022-12-13 | Data processing method, device and equipment and readable storage medium |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN115577149A CN115577149A (en) | 2023-01-06 |
| CN115577149Btrue CN115577149B (en) | 2023-03-10 |
Family
ID=84590510
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202211592819.2AActiveCN115577149B (en) | 2022-12-13 | 2022-12-13 | Data processing method, device and equipment and readable storage medium |
Country Status (2)
| Country | Link |
|---|---|
| CN (1) | CN115577149B (en) |
| WO (1) | WO2024124843A1 (en) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115577149B (en)* | 2022-12-13 | 2023-03-10 | 浪潮电子信息产业股份有限公司 | Data processing method, device and equipment and readable storage medium |
| CN116112122B (en)* | 2023-01-20 | 2025-07-18 | 阿里巴巴（中国）有限公司 | Data compression method and device |
| CN116683914A (en)* | 2023-04-26 | 2023-09-01 | 上海傲显科技有限公司 | Data compression method, device and system |
| CN117555817B (en)* | 2023-11-21 | 2025-02-11 | 中科驭数（北京）科技有限公司 | Data query method, controller and processor |
| CN119441643B (en)* | 2024-11-01 | 2025-08-22 | 绍兴通泽网络科技有限公司 | Short link generation method, server, storage medium and program product |
| CN120165690B (en)* | 2025-05-20 | 2025-08-01 | 浪潮电子信息产业股份有限公司 | Shifting circuit, integrated circuit device and electronic equipment |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103997346A (en)* | 2014-05-12 | 2014-08-20 | 东南大学 | Data matching method and device based on assembly line |
| WO2022198483A1 (en)* | 2021-03-24 | 2022-09-29 | 深圳市大疆创新科技有限公司 | Data compression method and apparatus, movable platform, and storage medium |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6624762B1 (en)* | 2002-04-11 | 2003-09-23 | Unisys Corporation | Hardware-based, LZW data compression co-processor |
| CN104636377B (en)* | 2013-11-12 | 2018-09-07 | 华为技术服务有限公司 | Data compression method and equipment |
| CN110928483B (en)* | 2018-09-19 | 2021-04-09 | 华为技术有限公司 | Data storage, data acquisition method and device |
| CN112306420B (en)* | 2020-11-13 | 2023-01-17 | 山东云海国创云计算装备产业创新中心有限公司 | Data read-write method, device and equipment based on storage pool and storage medium |
| CN115577149B (en)* | 2022-12-13 | 2023-03-10 | 浪潮电子信息产业股份有限公司 | Data processing method, device and equipment and readable storage medium |
- 2022
- 2022-12-13CNCN202211592819.2Apatent/CN115577149B/enactiveActive
- 2023
- 2023-06-20WOPCT/CN2023/101223patent/WO2024124843A1/ennot_activeCeased
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103997346A (en)* | 2014-05-12 | 2014-08-20 | 东南大学 | Data matching method and device based on assembly line |
| WO2022198483A1 (en)* | 2021-03-24 | 2022-09-29 | 深圳市大疆创新科技有限公司 | Data compression method and apparatus, movable platform, and storage medium |
Non-Patent Citations (1)
| Title |
|---|
| LZW算法在存储测试系统中的硬件实现;裴东兴等;《计量与测试技术》;20100430(第04期);全文* |
Also Published As
| Publication number | Publication date |
|---|---|
| CN115577149A (en) | 2023-01-06 |
| WO2024124843A1 (en) | 2024-06-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN115577149B (en) | Data processing method, device and equipment and readable storage medium | |
| CN106407201B (en) | A data processing method, apparatus and computer readable storage medium | |
| CN112765271A (en) | Block chain transaction index storage method and device, computer equipment and medium | |
| TW201342110A (en) | Counter operation in a state machine lattice | |
| CN104142892B (en) | A kind of data read-write method, apparatus and system | |
| CN111491169B (en) | Digital image compression method, device, equipment and medium | |
| CN113705136A (en) | Integrated circuit automation logic synthesis system, method, device and medium | |
| CN114826793B (en) | A kind of detection method, device and medium of ROP chain | |
| CN112667636A (en) | Index establishing method, device and storage medium | |
| CN118672654B (en) | Register sharing method, device, equipment and medium for general graphics processor | |
| CN116227599A (en) | An optimization method, device, electronic equipment and storage medium for a reasoning model | |
| CN104572994B (en) | Method and apparatus for searching for data | |
| CN115525580A (en) | Namespace setting method and device and readable storage medium | |
| WO2025139305A1 (en) | Data search method and apparatus, and electronic device and storage medium | |
| JP5549177B2 (en) | Compression program, method and apparatus, and decompression program, method and apparatus | |
| CN112035380B (en) | Data processing method, device and equipment and readable storage medium | |
| CN115277553A (en) | Flow table storage method, device, equipment and computer readable storage medium | |
| CN111970007B (en) | Decoding method, decoder, device and medium | |
| CN117873394A (en) | Data compression method, device, electronic device and readable storage medium | |
| CN116804915B (en) | Data interaction method, processor, device and medium based on memory | |
| CN110599568B (en) | A method, device, equipment and storage medium for generating lines | |
| CN117290332A (en) | Data migration verification method, device, equipment and storage medium | |
| CN114124106B (en) | LZ4 decompression method, system, storage medium and equipment | |
| WO2023093023A1 (en) | Sensitive word filtering method and apparatus, and storage medium | |
| CN112612925A (en) | Data storage method, data reading method and electronic equipment |
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 |