# frequent-substring
## Overview
`subs` is a tool for identifying frequent substrings in a text file, and substituting them for something else.
It is implemented in Haskell.
With the `-l` option, it can find the most frequent subsequence of a specified length.
With the `-r` option, it can find the longest subsequence that repeats at least the specified number of times.
With the `-s` option, in concert with the others, it can substitute the specified string for the subsequence found.
It works by hashing the subsequences that it's counting, to reduce memory consumption.
The motivating use-case was to aid in simplifying long mathematical expressions, too long for ordinary algebra systems (e.g. sage, mathematica) to simplify without exhausting memory.
It has successfully found a longest-substring on a >2.5M character sequence, which led to memory exhaustion on those ordinary algebra systems (on a system with 11Gi of ram).
## Get Started
1. Run `make`. This will build via stack and also copy the `subs` executable to `build/subs`.
2. Place `subs` to within your path.
3. You are ready to use `subs`.
## Help Doc
```
$ subs --help
frequent-substring help:
Usage: subs [-i|--filepath FilePath] [-l|--length INT] [-r|--repeats INT]
[-s|--substitute String] [-v|--verbose]
find frequent subsequences in a text file
Available options:
-i,--filepath FilePath path to input file containing the text sequence
-l,--length INT find the most frequent subsequence of a specified
length
-r,--repeats INT find the longest subsequence which repeats this many
times
-s,--substitute String replace the subsequence found with a specified string
-v,--verbose whether to display counts, etc.
-h,--help Show this help text
```
## Typical Workflow
The longest-subsequence function (`-r`) uses a binary search.
A typical workflow on a long file might be to run with `-l` (and `-v`) a few times,
to get an idea of what number of repeats to specify.
```
$ subs -i res/formula -l 100 -v
Finding the most frequent subsequence of length 100 in the content of res/formula
content has length: 2500530
number of subsequences of exact length 100: 2500431
substring:
*d^2*e^2*g*h - 24*e^4*g*h + 192*c^2*g^3*h - 12*d^2*g^3*h - 60*e^2*g^3*h + 12*g^5*h - 24*c^4*h^2 - 72
length: 100
repeats: 189
```
Then use `-r` with that number of repeats, to find the longest substring that repeats at least that many times:
```
$ subs -i res/formula -r 189 > substring-that-repeats-at-least-189-times.txt
```
or, obtain the original formula but with a specified substitution applied:
```
$ subs -i res/formula -r 189 -s substituteTerm > original-with-substitution-applied.txt
```
## Examples
### Searching by length:
```
$ subs -i res/formula -l 17
*sqrt(e^2 - h^2)*
```
with verbose:
```
$ subs -i res/formula -l 17 -v
Finding the most frequent subsequence of length 17 in the content of res/formula
content has length: 13209
number of subsequences of exact length 17: 13193
substring:
*sqrt(e^2 - h^2)*
length: 17
repeats: 190
```
### Performing a substitution when searching by length:
```
$ subs -i res/formula -l 17 -s "*eMinusH*"
(16*c^6 + 24*c^4*d^2 + 12*c^2*d^4 + 2*d^6 - 24*c^4*e^2 + 24*c^2*d^2*e^2 + 18*d^4*e^2 + 12*c^2*e^4 - 18*d^2*e^4 - 2*e^6 - 84*c^4*g^2 - 30*c^2*d^2*g^2 + 6*d^4*g^2 + 66*c^2*e^2*g^2 - 42*d^2*e^2*g^2 - 12*e^4*g^2 + 66*c^2*g^4 + 6*d^2*g^4 + 12*e^2*g^4 + 2*g^6 - 96*c^4*g*h - 96*c^2*d^2*g*h - 24*d^4*g*h + 96*c^2*e^2*g*h - 48*d^2*e^2*g*h - 24*e^4*g*h + 192*c^2*g^3*h - 12*d^2*g^3*h - 60*e^2*g^3*h + 12*g^5*h - 24*c^4*h^2 - 72*c^2*d^2*h^2 - 30*d^4*h^2 + 24*c^2*e^2*h^2 + 12*d^2*e^2*h^2 - 6*e^4*h^2 + 222*c^2*g^2*h^2 + 132*d^2*g^2*h^2 - 102*e^2*g^2*h^2 - 54*g^4*h^2 + 96*c^2*g*h^3 + 144*d^2*g*h^3 - 48*e^2*g*h^3 - 116*g^3*h^3 + 12*c^2*h^4 + 30*d^2*h^4 - 6*e^2*h^4 - 90*g^2*h^4 - 24*g*h^5 - 2*h^6 + 48*eMinusH*c^4*d + 48*eMinusH*c^2*d^3 + 12*eMinusH*d^5 - 156*eMinusH*c^2*d*e^2 + 120*eMinusH*d^3*e^2 +
...
```
### Searching by number of repeats:
```
$ subs -i res/formula -r 150
*sqrt(e^2 - h^2)*
```
with verbose:
```
$ subs -i res/formula -r 150 -v
Finding the longest subsequence that repeats 150 times, in the content of res/formula
content has length: 13209
number of subsequences with length at least 0: 87258655
substring:
*sqrt(e^2 - h^2)*
length: 17
repeats: 190
```
### Performing a substitution when searching by number of repeats:
```
$ subs -i res/formula -r 150 -s "*eMinusH*"
(16*c^6 + 24*c^4*d^2 + 12*c^2*d^4 + 2*d^6 - 24*c^4*e^2 + 24*c^2*d^2*e^2 + 18*d^4*e^2 + 12*c^2*e^4 - 18*d^2*e^4 - 2*e^6 - 84*c^4*g^2 - 30*c^2*d^2*g^2 + 6*d^4*g^2 + 66*c^2*e^2*g^2 - 42*d^2*e^2*g^2 - 12*e^4*g^2 + 66*c^2*g^4 + 6*d^2*g^4 + 12*e^2*g^4 + 2*g^6 - 96*c^4*g*h - 96*c^2*d^2*g*h - 24*d^4*g*h + 96*c^2*e^2*g*h - 48*d^2*e^2*g*h - 24*e^4*g*h + 192*c^2*g^3*h - 12*d^2*g^3*h - 60*e^2*g^3*h + 12*g^5*h - 24*c^4*h^2 - 72*c^2*d^2*h^2 - 30*d^4*h^2 + 24*c^2*e^2*h^2 + 12*d^2*e^2*h^2 - 6*e^4*h^2 + 222*c^2*g^2*h^2 + 132*d^2*g^2*h^2 - 102*e^2*g^2*h^2 - 54*g^4*h^2 + 96*c^2*g*h^3 + 144*d^2*g*h^3 - 48*e^2*g*h^3 - 116*g^3*h^3 + 12*c^2*h^4 + 30*d^2*h^4 - 6*e^2*h^4 - 90*g^2*h^4 - 24*g*h^5 - 2*h^6 + 48*eMinusH*c^4*d + 48*eMinusH*c^2*d^3 + 12*eMinusH*d^5 - 156*eMinusH*c^2*d*e^2 + 120*eMinusH*d^3*e^2 +
```
### Reading from standard input:
```
$ cat res/formula | subs -l 17
*sqrt(e^2 - h^2)*
```
```
$ cat res/formula | subs -r 150
*sqrt(e^2 - h^2)*
```