Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

A parallel suffix sorting method and system

A sorting method and suffix technology, applied in the field of data processing, can solve problems such as the low running speed of the serial IS algorithm and the inability of the computer to fully exert its performance, and achieve the effects of high acceleration ratio, high parallelism, and improved running speed

Active Publication Date: 2022-04-08
SUN YAT SEN UNIV
View PDF8 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0003] In order to solve the problem that the running speed of the serial IS algorithm in the prior art is low, and the computer cannot fully exert its performance, the present invention provides a parallel suffix sorting method and system

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • A parallel suffix sorting method and system
  • A parallel suffix sorting method and system

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 1

[0039] Such as figure 1 As shown, a parallel suffix sorting method includes the following steps:

[0040] Step S101: find out the LMS substring in the character string X, the specific implementation is as follows:

[0041] (1) The last element of the string X is additionally added is the smallest character in the string. Define X[i]X[i+1], then suffix(X, i) is L type; when X [i]=X[i+1], then suffix(X, i) is of the same type as suffix(X, i+1). Use the L / S suffix recognizer to scan the string X from right to left, and store the result in an array t of length n.

[0042] (2) During the scanning process, the size of each bucket and the number of L-type and S-type suffixes of each bucket are counted at the same time. Use the array bucket to record the number of occurrences of each character in the string X. Traverse the string X from left to right, add one to bucket[X[i]] every time a character is traversed. Traverse the bucket array from left to right, set bucket[i]+=bucke...

Embodiment 2

[0063] Such as figure 2 As shown, a parallel suffix sorting system includes a front unit, an analysis unit, and a storage unit; the front unit is used to perform steps S101 to S102; the analysis unit is used to perform steps S103 to S111; The storage unit described above is responsible for storing temporary data generated by multi-thread parallel inductive sorting.

[0064] The front unit includes a decision subunit, an LMS substring calculation subunit and an SA block subunit;

[0065] The decision-making subunit is used to read the string X from the storage unit, use the L / S suffix recognizer to identify the string X, obtain its suffix type array t, count the number of L and S types of each suffix, and Write storage unit; Described LMS substring calculation subunit is used for reading suffix type array t from storage unit, calculates and obtains all LMS characters, then calculates LMS substring position, and writes storage unit; The above SA block subunit is used to divid...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention relates to a parallel suffix sorting method and system. For a character string X with a length of n, when its size is much larger than the Cache size of the computer, the SA block method is used to increase the hit rate of the Cache and reduce the Cache The number of interactions with memory, thus greatly reducing the string sorting time. The present invention utilizes the parallel computing resources of modern multi-core computers to parallelize the data access operations in the sorting process with multi-threads, effectively improving the running speed of the algorithm, and the parallelism of the inductive sorting process is high, and the system can obtain a higher speed-up ratio, greatly Improve work efficiency.

Description

technical field [0001] The present invention relates to the field of data processing, and more specifically, to a method and system for sorting parallel suffixes. Background technique [0002] The CPU of a modern computer reads and writes data from the memory through the cache (Cache), and the data locality of the algorithm has a great influence on the running speed of the algorithm. When performing suffix sorting on large-scale character strings, the serial IS algorithm has poor data locality and long data read and write delays, which reduces the running speed of the algorithm, resulting in the failure of the algorithm performance to be effectively exerted, and greatly reducing the working efficiency of the computer. and increased time costs. Contents of the invention [0003] In order to solve the problems in the prior art that the running speed of the serial IS algorithm is low and the computer cannot fully utilize the performance, the present invention provides a meth...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Patents(China)
IPC IPC(8): G06F9/46G06F16/9032
CPCG06F9/46
Inventor 彭炯瑜解静仪农革
Owner SUN YAT SEN UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com