Online Grammar Compression for Frequent Pattern Discovery
| Autor: | Fukunaga, Shouhei, Takabatake, Yoshimasa, Tomohiro, I, Sakamoto, Hiroshi |
|---|---|
| Rok vydání: | 2016 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Various grammar compression algorithms have been proposed in the last decade. A grammar compression is a restricted CFG deriving the string deterministically. An efficient grammar compression develops a smaller CFG by finding duplicated patterns and removing them. This process is just a frequent pattern discovery by grammatical inference. While we can get any frequent pattern in linear time using a preprocessed string, a huge working space is required for longer patterns, and the whole string must be loaded into the memory preliminarily. We propose an online algorithm approximating this problem within a compressed space. The main contribution is an improvement of the previously best known approximation ratio $\Omega(\frac{1}{\lg^2m})$ to $\Omega(\frac{1}{\lg^*N\lg m})$ where $m$ is the length of an optimal pattern in a string of length $N$ and $\lg^*$ is the iteration of the logarithm base $2$. For a sufficiently large $N$, $\lg^*N$ is practically constant. The experimental results show that our algorithm extracts nearly optimal patterns and achieves a significant improvement in memory consumption compared to the offline algorithm. Comment: 14 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|