<commit_before>sparseMEM
=========

[![Build Status](https://travis-ci.org/reisub/sparseMEM.svg?branch=master)](https://travis-ci.org/reisub/sparseMEM)

An implementation of an algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays

## Terminology

`S` - a string of `n` characters stored in an array

`$` - the termination character of the string, the unique lexicographically smallest character in the alphabet which contains the possible characters in `S`

`suf(S, i)` - a suffix of the string `S` starting with the character `S[i]` all the way to the termination character `$`

`SA` - suffix array, a sorted array of all suffixes of a string

### S-type an L-type

A suffix `suf(S, i)` is said to be S-type or L-type if `suf(S, i) < suf(S, i+1)` or `suf(S, i) > suf(S, i+1)`, respectively.

The last suffix `suf(S, n-1)`, consisting of only a single termination character `$` is defined as S-type.

A character `S[i]` is S-type or L-type if the suffix `suf(S, i)` is S-type or L-type, respectively.

### Buckets and sub-buckets

a `bucket` is a sub-array of the `SA` for all the suffixes starting with the same character. It can be further split into two sub-buckets with respect to the types of the suffixes inside: the L- and S-type buckets, where the L- type bucket is on the left of the S-type bucket.

### LMS

`LMS` - left-most S-type

A character `S[i]` i called LMS if `S[i]` i S-type and `S[i+i]` is L-type. A suffix `suf(S, i)` is called LMS is `S[i]` is a LMS character.

A LMS-substring is a substring S[i..j] with both S[i] and S[j] being LMS characters and there is no other LMS character in the substring. The termination character `$` is also a LMS-substring.

### Graphical example

S - `cccagaaaactaccacctccggccagta$`
<commit_msg>Fixed some keywords in readme<commit_after>sparseMEM
=========

[![Build Status](https://travis-ci.org/reisub/sparseMEM.svg?branch=master)](https://travis-ci.org/reisub/sparseMEM)

An implementation of an algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays

## Terminology

`S` - a string of `n` characters stored in an array

`$` - the termination character of the string, the unique lexicographically smallest character in the alphabet which contains the possible characters in `S`

`suf(S, i)` - a suffix of the string `S` starting with the character `S[i]` all the way to the termination character `$`

`SA` - suffix array, a sorted array of all suffixes of a string

### S-type an L-type

A suffix `suf(S, i)` is said to be S-type or L-type if `suf(S, i) < suf(S, i+1)` or `suf(S, i) > suf(S, i+1)`, respectively.

The last suffix `suf(S, n-1)`, consisting of only a single termination character `$` is defined as S-type.

A character `S[i]` is S-type or L-type if the suffix `suf(S, i)` is S-type or L-type, respectively.

### Buckets and sub-buckets

a `bucket` is a sub-array of the `SA` for all the suffixes starting with the same character. It can be further split into two sub-buckets with respect to the types of the suffixes inside: the L- and S-type buckets, where the L- type bucket is on the left of the S-type bucket.

### LMS

`LMS` - left-most S-type

A character `S[i]` i called LMS if `S[i]` i S-type and `S[i+i]` is L-type. A suffix `suf(S, i)` is called LMS is `S[i]` is a LMS character.

A LMS-substring is a substring `S[i..j]` with both `S[i]` and `S[j]` being LMS characters and there is no other LMS character in the substring. The termination character `$` is also a LMS-substring.

### Graphical example

S - `cccagaaaactaccacctccggccagta$`

{'fraction_non_alphanumeric': 0.11572535991140642, 'fraction_numerical': 0.0016611295681063123, 'mean_word_length': 4.0673211781206176, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6825186', 'n_tokens_mistral': 1238, 'n_tokens_neox': 1209, 'n_words': 532}