Method for multi-thread parallel construction of suffix array and system

Abstract

The invention discloses a method for multi-thread parallel construction of a suffix array and a system. The method comprises the following steps: scanning a character string X, calculating the types of characters and suffixes by using an L / S type recognition method, and recording in an array t; scanning the array t, finding out the positions where LMS characters appear, obtaining first character pointers of LMS substrings and recording the pointers of the LMS substrings with an array P1; performing parallel induction and sorting on all LMS substrings in the X by the P1, a B and an SA and saving in an SA1; according to the sorting result, performing multi-thread parallel renaming on the LMS substrings in the X to form an X1; checking whether each character in the X1 is unique, if yes, directly sorting suffixes of the X1 to calculate a suffix array of the X1 and saving in the SA1; and finally calculating a suffix array of the X and saving in the SA according to the suffix array of the X1 saved in the SA1. The invention has high running speed, can be matched with the memory of a multi-core computer, and is suitable for constructing a suffix array of a large-scale string.

Description

technical field [0001] The invention relates to the field of string suffix array construction, in particular to a method and system for constructing a suffix array in parallel with multiple threads. Background technique [0002] Suffix Array (Suffix Array, SA) is an important data structure in computer science. It has the characteristics of compact structure and small space occupation. It is widely used in many fields such as full-text indexing, gene matching and data compression. Given any input string text X[0,n-1] of length n, referred to as string X, all characters from any position i in X to end position n-1 form a character substring X [i,n-1], the substring is called a suffix (Suffix) of the string X. Obviously, a string X with a length of n contains n suffixes, and these n suffixes are stored in an integer array in ascending lexicographical order, then this array is called the suffix array SA of the string X. [0003] In recent years, the memory space of general-pu...

AI Technical Summary

Problems solved by technology

However, with the explosive growth of data scale, existing serial methods and systems cannot meet the needs of fast processing when dealing with large-scale string data, especially under the memory model of multi-core computers, it is difficult to achieve operation target expectations

Images