Obtaining Maximum Probability Partitioning by Optimizing Calculation Strategy
Daichi Kozuki, Ayaka Takamoto, Kyoji Umemura · 2023
Maximum probability partitioning is a method for segmenting a string. It determines the occurrence probability of substrings and maximizes their simultaneous probabilities. In time series data classification, a method has been proposed for estimating the label of a string using the self-information amount of the string through maximum string partitioning. To estimate the probability of substring occurrence using a matrix representation, the frequency of the substring in the matrix is counted through binary search using a suffix array. To further accelerate the computation of maximum probability partitioning, we propose a method for determining the starting position with an optimized calculation strategy. This proposed method is approximately 1.4 times faster than previous methods for real-world data, and it does not slow down the processing of data.