string-algorithms

Collection of algorithms for String Algorithms course (summer semesters 2019/20, 2021/22) at Jagiellonian University, Theoretical Computer Science Department.

Algorithms

Text decomposition

Maximum suffix

1. Algorithm based on prefix-suffix array
2. Algorithm in constant space, based on critical factorization
3. Algorithm based on suffix array
4. Adamczyk-Rytter algorithm

Critical factorization

1. Constant-space algorithm based on maximal suffixes

Lyndon factorization

1. Duval algorithm

Exact string matching

1. Morris-Pratt and Knuth-Morris-Pratt algorithms
2. Boyer-Moore algorithm with many variants (weak-shift, bad-character, Horspool, Quick Search, Galil)
3. Boyer-Moore-Apostolico-Giancarlo algorithm
4. Galil-Seiferas algorithm
5. Constant space two-way (Crochemore-Perrin) algorithm
6. fast-on-average (Crochemore et al.) algorithm
7. Turbo Boyer-Moore (Crochemore et al.) algorithm
8. Bitap Shift-Add (Baeza-Yates-Gonnet) algorithm
9. Hashing-based (Karp-Rabin) algorithm
10. FFT-based algorithm
11. Crochemore algorithm for ordered alphabets

String indexing

Suffix tree

1. Weiner algorithm
2. McCreight algorithm
3. Ukkonen on-line algorithm
4. Farach algorithm

Suffix array

1. Prefix doubling (Karp-Miller-Rosenberg) algorithm
2. Larsson-Sadakane algorithm
3. Skew (Kärkkäinen-Sanders) algorithm
4. Farach algorithm
5. Induced sorting (Zhang-Nong-Chan) algorithm
6. Small-large (Ko-Aluru) algorithm

Suffix array search

1. $O(m \log{n})$ naive algorithm
2. Manber-Myers $O(m + \log{n})$ algorithm

Other index structures

1. FM index (Ferragina-Manzini)
2. LZ index
3. Wavelet tree for rank and range queries

Longest common prefix

1. Kasai et al. algorithm
2. Farach algorithm
3. $\phi$ array-based (Kärkkäinen-Manzini-Puglisi) algorithm
4. Irreducible LCPs-based (Kärkkäinen-Manzini-Puglisi) algorithm
5. Wee LCP (Fischer) algorithm

Longest previous factor

1. Crochemore-Ilie-Smyth algorithm

Multiple exact string matching

1. Aho-Corasick algorithm
2. Commentz-Walter algorithm
3. Fast-on-average algorithm (Crochemore et al.)

Approximate string matching

String distance

1. Wagner-Fischer algorithm
2. Four Russians (Masek-Paterson) algorithm

Longest common subsequence

1. Needleman-Wunsch algorithm
2. Hirschberg algorithm
3. Four Russians (Masek-Paterson) algorithm
4. Myers algorithm
5. Kumar-Rangan algorithm
6. Hunt-Szymanski algorithm
7. Hunt-Szymanski-Apostolico algorithm

Approximate string matching with Hamming distance

1. Landau-Vishkin algorithm
2. Bitap Shift-Add (Baeza-Yates-Gonnet) algorithm
3. Grossi-Luccio algorithm

Approximate string matching with edit distance

1. Approximate Boyer-Moore (Tarhio-Ukkonen) algorithm

String matching with wildcards

1. Basic algorithm based on FFT
2. Clifford-Clifford algorithm
3. Naive brute-force algorithm
4. Fischer-Paterson bitwise algorithm
5. Sperner optimization (Muthukrishnan-Palem) algorithm
6. Indyk randomized binary projections algorithm (with FFT or GF(2) boolean convolution)
7. Kalai randomized fingerprinting algorithm

Approximate string matching with wildcards and Hamming distance

1. Nonrecursive randomised algorithm (Clifford, Eremenko et al.)
2. Recursive randomised algorithm (Clifford, Eremenko et al.)
3. Nonrecursive deterministic algorithm (Clifford, Eremenko et al.)

Other problems

1. Approximate matching of string permutation algorithm (Grossi-Luccio)

Shortest common superstring

1. $\log{n}$-approximation (Li-Jiang) algorithm
2. $4$- and $3$-approximation (Blum et al.) algorithms based on overlaps
3. Greedy overlap algorithm
4. Teng-Yao algorithm
5. Paluch-Elbassioni-van Zuylen algorithm
6. Breslauer-Jiang-Jiang algorithms

Compression

Burrows-Wheeler transform

1. Naive inverse transform

Lempel-Ziv 77 (LZ77) compression and factorization

1. Naive Lempel-Ziv compression algorithm
2. Sliding-window Lempel-Ziv compression algorithm
3. Chen-Puglisi-Smyth (CPS1a) factorization algorithm
4. Kärkkäinen-Kempa-Puglisi (KKP3) factorization algorithm
5. Crochemore-Ilie-Smyth factorization algorithm

Lempel-Ziv 78 (LZ78) compression

1. Block-based compression with bounded dictionary
2. Compression and decompression with greedy or optimal parsing

Lempel-Ziv-Welch (LZW) compression

1. Compression and decompression with greedy or optimal parsing

Installation

Install the Python runtime, test, and dependencies from the repository root:

  python -m pip install -r requirements.txt

To install the optional C++ benchar extension using pybind11 run:

  git submodule update --init --recursive lib/pybind11
  bash lib/benchar/cbenchar_build.sh

The Python benchar implementation and the other algorithms do not require the optional C++ extension.

Testing

Run all small tests:

  python -B -m unittest discover test -v

Run example large test:

  LARGE=1 python -B -m unittest test.test_exact_string_matching.TestExactStringMatching -v

To enable the C++ benchar extension-backed comparison tests run:

  CBENCHAR=1 python -B -m unittest test.test_benchar -v