<commit_before># Parallel Wavelet Tree and Wavelet Matrix Construction

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

## What is it?
We implemented different simple but very fast sequential and parallel wavelet tree (WT) and wavelet matrix (WM) construction algorithms.
The are based on two ideas, namely *prefix counting* (*pc*) and *prefix sorting* (*ps*).

Using these ideas, we have implemented:
1. a sequential version of the algorithms (*wx_ps* and *wx_ps*),
2. a parallel version of the algorithms (*wx_pps* and *wx_pps*) and
3. a parallel version of the algorithms using *domain decomposition* (*wx_dd_ps* and *wx_dd_ps*).
4. a version of *pc* that scans the text just twice and fills all levels but the first level at once (indicated by an *_ss*-suffix).

In addition, there are also a naive construction algorithms (*wx_naive*).
Replace _wx_ with either _wt_ or _wm_ for the corresponding WT- or WM-construction algorithm.

A detailed description and benchmarks of the implemented algorithms can be found in this [arXiv preprint](https://arxiv.org/abs/1702.07578).

## How to get it?
First clone this repository, then build all executables.
```sh
git clone https://github.com/kurpicz/pwm.git
cd pwm
mkdir build
cd build
cmake ..
make
```
This will create an executable `src/benchmark` which allows you to run all our algorithms.
To this end, we provide a simple command line interface.<commit_msg>Fix readme (replace ps with pc)<commit_after># Parallel Wavelet Tree and Wavelet Matrix Construction

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

## What is it?
We implemented different simple but very fast sequential and parallel wavelet tree (WT) and wavelet matrix (WM) construction algorithms.
The are based on two ideas, namely *prefix counting* (*pc*) and *prefix sorting* (*ps*).

Using these ideas, we have implemented:
1. a sequential version of the algorithms (*wx_pc* and *wx_ps*),
2. a parallel version of the algorithms (*wx_ppc* and *wx_pps*) and
3. a parallel version of the algorithms using *domain decomposition* (*wx_dd_pc* and *wx_dd_ps*).
4. a version of *pc* that scans the text just twice and fills all levels but the first level at once (indicated by an *_ss*-suffix).

In addition, there are also a naive construction algorithms (*wx_naive*).
Replace _wx_ with either _wt_ or _wm_ for the corresponding WT- or WM-construction algorithm.

A detailed description and benchmarks of the implemented algorithms can be found in this [arXiv preprint](https://arxiv.org/abs/1702.07578).

## How to get it?
First clone this repository, then build all executables.
```sh
git clone https://github.com/kurpicz/pwm.git
cd pwm
mkdir build
cd build
cmake ..
make
```
This will create an executable `src/benchmark` which allows you to run all our algorithms.
To this end, we provide a simple command line interface.
{'fraction_non_alphanumeric': 0.09207853757616791, 'fraction_numerical': 0.008801624915368992, 'mean_word_length': 4.771484375, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 8, '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': '6729296', 'n_tokens_mistral': 884, 'n_tokens_neox': 823, 'n_words': 402}