资 源 简 介
This is a one of the algorithms which be called compressed string processing(CSP).
CSP algorithms allow several computing on compressed string without explicit decompression.
Since the decompressed string can be exponentially larger than the compressed string, CSP algorithm can be exponentially faster than the algorithm which runs on uncompressed string.
This program compute the all q-gram frequencies from grammar based compressed string without explicit decompression.
In our experiments, this program practically runs faster than the program on uncompressed string when q is small. We want to emphasize that we did not includes the decompression time for measuring the computation time of the program which runs on uncompressed string.
q-gram is a length-q substring. It sometimes called other words such as n-gram, k-mer.
Related Publication:
(1) Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda: Fast q-gram Mining on SLP C
