esa-matchfinder

KO | EN

gitlite — search

#hacktoberfest #react #typescript #go #linux #docker #java #windows #awesome #cli #awesome-list #security #ios #mcp

esa-matchfinder

(★ 28)

The esa-matchfinder is a C99 library for efficient Lempel-Ziv factorization using enhanced suffix array (ESA).

esa-matchfinder 최신버젼 다운로드

최종 버전 다운로드 (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# The esa-matchfinder

The esa-matchfinder is a C99 library for efficient Lempel-Ziv factorization using enhanced suffix array (ESA).

> * The esa-matchfinder is block based algorithm with maximum supported block size of 512 megabytes finding matches in range of 2..64 bytes using 12x bytes of extra memory. ESA_MATCHFINDER_MATCH_BITS definition could be changed to support larger match finding range, but with reduction in maximum supported block size.
> * The esa-matchfinder does not employ any heuristics or search depth limitations and always finds distance optimal matches even on highly repetitive sources. The only exception is matches at beginning at the block; due to implementation details the esa-matchfinder can not find any matches with offset 0.
> * The esa-matchfinder is fast in best, average and worst cases (see [Benchmarks](#benchmarks) below). But the esa-matchfinder is sensitive to fast memory and software prefetching and might not be suitable for some CPU architectures. The esa-matchfinder might also be suboptimal on specific data types (some DNA sequences in particular), so please benchmark yourself.
> * The esa-matchfinder works with compilers from Microsoft and GNU, but I recommend Clang for best performance. Additionally, the esa-matchfinder is designed for 64-bit systems and will work suboptimally on 32-bit system.

## Algorithm 
> The esa-matchfinder uses methodology of bottom-up traversal of the Longest Common Prefix (LCP) interval tree written in 2014-2015 by Eric Biggers <ebiggers3@gmail.com> and dedicated to the public domain worldwide.

The esa-matchfinder finds all distance optimal matches (between min_match_length and max_match_length inclusive) for every position of the input block using following algorithm:

1. Suffix (SA) and longest common prefix (LCP) arrays are constructed for the input block. Next, interval tree is constructed on top of SA and LCP arrays.
> * The data structure consisting of SA and LCP is often referred as enhanced suffix array (ESA). Hence the name of the match finder.

2. Each interval is a maximum range (could not be further extended to the left or right) of suffixes in SA with common prefix of certain length (LCP). This intervals represent internal nodes of suffix tree.
3. Using interval tree we can now traverse up or down to either wider interval with smaller common prefix or narrower intervals with larger common prefixes.
4. For purpose of Lempel-Ziv factorization we only need to support bottom-up traversal, so during interval tree construction we only need to capture link to parent interval and length of interval's common prefix.
5. LCP array is also pruned by min_match_length and max_match_length to reduce size and depth of interval tree.
6. Additionally, for each position of input block we capture link to a leaf interval corresponding to that position, so we can start bottom-up traversal during factorization phase.
7. SA, LCP and interval tree construction is done during input block parsing phase in linear time with optional multi-threaded optimization using OpenMP.
8. LZ factorization phase is done from left to right by bottom-up traversal of interval tree for each position from input block by reading and updating each corresponding interval with latest offset.

## License
The esa-matchfinder released under the [Apache License Version 2.0](LICENSE "Apache license") and is considered suitable for production use. However, no warranty or fitness for a particular purpose is expressed or implied.

## Changes
* September 1, 2025 (1.2.2)
  * Updated libsais to v2.10.4.
  * Tuned prefetch distance for improved throughput.
* February 6, 2025 (1.2.1)
  * Resolved strict aliasing violation resulted in invalid code generation by Intel compiler.
* December 2, 2023 (1.2.0)
  * Small performance optimization for esa_matchfinder_advance API.
* November 30, 2023 (1.1.0)
  * New API to find matches within specified sliding window.
* June 19, 2022 (1.0.1)
  * Improved cache coherence for ARMv8 architecture.
* June 12, 2022 (1.0.0)
  * Initial public release of the esa-matchfinder.

## Example of usage (See [esa_matchfinder.h](esa_matchfinder.h) for complete APIs list)
```c
#include "esa_matchfinder.h"

long long multi_pass_optimal_parse(const unsigned char * buffer, int size)
{
    long long total_matches = 0;

void * mf = esa_matchfinder_create(size, /*min_match_length*/ 2, /*max_match_length*/ 64);
    if (mf != NULL && esa_matchfinder_parse(mf, buffer, size) == ESA_MATCHFINDER_NO_ERROR)
    {
        for (int pass = 0; pass < 2; pass += 1)
        {
            ESA_MATCHFINDER_MATCH matches[ESA_MATCHFINDER_MAX_MATCH_LENGTH];

esa_matchfinder_rewind(mf, /*position*/ 0);

for (int position = 0; position < size; position += 1)
            {
                total_matches += esa_matchfinder_find_all_matches(mf, matches) - matches;
            }
        }
    }

esa_matchfinder_destroy(mf);

return total_matches;
}
```

---

# Benchmarks #
  
## Methodology ##
  * Input files were capped at 510MB for tests on x86-64 architecture and 128MB for tests on ARMv8 architecture
  * For all match finders maximum match length was set to 64 bytes (other parameters were not changed)
  * Optimality is defined as percentage of optimal matches (longest possible length) found across all possible matches
  * The timings are minimum of five runs measuring single-threaded performance in *optimal* parsing mode

## Specification (x86-64 architecture) ##
  * OS: Microsoft Windows 10 Pro 64-Bit
  * CPU: Intel Core i7-9700K Processor (12M Cache, 5GHz)
  * RAM: 2x8 GB dual-channel DDR4 (4133 MHz, 17-17-17-37)
  * Compiler: Microsoft Visual C++ compiler v14.32 
  * Optimizations: /MD /DNDEBUG /O2 /GL /arch:AVX2

### Silesia Corpus (x86-64 architecture) ###

### Large Canterbury Corpus (x86-64 architecture) ###

### Manzini Corpus (x86-64 architecture) ###

### Large Text Compression Benchmark Corpus (x86-64 architecture) ###

### The Gauntlet Corpus (x86-64 architecture) ###

### Pizza & Chilli Corpus (x86-64 architecture) ###

### Pizza & Chilli Repetitive Corpus (x86-64 architecture) ###

| file | size | esa-matchfinder v1.0.0 | optimality | LZMA HC4 v21.07 | optimality | LZMA BT4 v21.07 | optimality |
|:----:|:----:|:----------------------:|:----------:|:---------------:|:----------:|:---------------:|:----------:|
| cere | 461286644 | **68.413 sec (6.74 MB/s)** | 100.00% | 77.037 sec (5.99 MB/s) | 7.30% | 266.363 sec (1.73 MB/s) | 94.04% |
| coreutils | 205281778 | **18.967 sec (10.82 MB/s)** | 100.00% | 54.280 sec (3.78 MB/s) | 34.14% | 40.171 sec (5.11 MB/s) | 87.59% |
| einstein.de.txt | 92758441 | **6.620 sec (14.01 MB/s)** | 100.00% | 10.236 sec (9.06 MB/s) | 80.28% | 9.088 sec (10.21 MB/s) | 96.82% |
| einstein.en.txt | 467626544 | **39.117 sec (11.95 MB/s)** | 100.00% | 56.046 sec (8.34 MB/s) | 77.54% | 48.619 sec (9.62 MB/s) | 97.64% |
| Escherichia_Coli | 112689515 | **16.191 sec (6.96 MB/s)** | 100.00% | 19.889 sec (5.67 MB/s) | 0.26% | 63.204 sec (1.78 MB/s) | 96.93% |
| influenza | 154808555 | 44.042 sec (3.52 MB/s) | 100.00% | **25.125 sec (6.16 MB/s)** | 28.19% | 27.703 sec (5.59 MB/s) | 98.49% |
| kernel | 257961616 | **21.931 sec (11.76 MB/s)** | 100.00% | 81.326 sec (3.17 MB/s) | 24.72% | 59.968 sec (4.30 MB/s) | 93.18% |
| para | 429265758 | **69.888 sec (6.14 MB/s)** | 100.00% | 73.130 sec (5.87 MB/s) | 3.94% | 251.836 sec (1.70 MB/s) | 93.09% |
| world_leaders | 46968181 | **5.758 sec (8.16 MB/s)** | 100.00% | 6.124 sec (7.67 MB/s) | 40.96% | 6.126 sec (7.67 MB/s) | 62.59% |
| dblp.xml.00001.1 | 104857600 | **12.065 sec (8.69 MB/s)** | 100.00% | 18.851 sec (5.56 MB/s) | 32.29% | 16.655 sec (6.30 MB/s) | 96.79% |
| dblp.xml.00001.2 | 104857600 | **12.765 sec (8.21 MB/s)** | 100.00% | 18.972 sec (5.53 MB/s) | 32.01% | 16.767 sec (6.25 MB/s) | 96.99% |
| dblp.xml.0001.1 | 104857600 | **13.064 sec (8.03 MB/s)** | 100.00% | 18.952 sec (5.53 MB/s) | 32.36% | 16.712 sec (6.27 MB/s) | 96.76% |
| dblp.xml.0001.2 | 104857600 | **15.651 sec (6.70 MB/s)** | 100.00% | 19.258 sec (5.44 MB/s) | 30.31% | 17.409 sec (6.02 MB/s) | 96.99% |
| dna.001.1 | 104857600 | **16.519 sec (6.35 MB/s)** | 100.00% | 18.601 sec (5.64 MB/s) | 0.23% | 33.080 sec (3.17 MB/s) | 99.49% |
| english.001.2 | 104857600 | **11.087 sec (9.46 MB/s)** | 100.00% | 29.621 sec (3.54 MB/s) | 36.64% | 21.313 sec (4.92 MB/s) | 99.32% |
| proteins.001.1 | 104857600 | 12.562 sec (8.35 MB/s) | 100.00% | 24.271 sec (4.32 MB/s) | 89.70% | **12.411 sec (8.45 MB/s)** | 99.99% |
| sources.001.2 | 104857600 | **10.484 sec (10.00 MB/s)** | 100.00% | 20.817 sec (5.04 MB/s) | 43.87% | 16.775 sec (6.25 MB/s) | 97.24% |
| fib41 | 267914296 | 19.852 sec (13.50 MB/s) | 100.00% | 33.175 sec (8.08 MB/s) | 96.99% | **19.070 sec (14.05 MB/s)** | 100.00% |
| rs.13 | 216747218 | **16.024 sec (13.53 MB/s)** | 100.00% | 30.276 sec (7.16 MB/s) | 95.65% | 17.824 sec (12.16 MB/s) | 100.00% |
| tm29 | 268435456 | **19.926 sec (13.47 MB/s)** | 100.00% | 51.541 sec (5.21 MB/s) | 89.58% | 26.480 sec (10.14 MB/s) | 100.00% |

## Specification (ARMv8 architecture) ##
  * OS: Ubuntu 20.04 LTS 64-Bit
  * CPU: ODROID-N2+ Amlogic S922X (Cortex-A73 2.4Ghz)
  * RAM: 4GB LPDDR4 (2666 MHz) 
  * Compiler: Clang v10.0.0
  * Optimizations: -DNDEBUG -O3 -flto=thin -mcpu=native

### Silesia Corpus (ARMv8 architecture) ###

### Large Canterbury Corpus (ARMv8 architecture) ###

### Manzini Corpus (ARMv8 architecture) ###

### Large Text Compression Benchmark Corpus (ARMv8 architecture) ###

### The Gauntlet Corpus (ARMv8 architecture) ###

esa-matchfinder

esa-matchfinder 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

esa-matchfinder

esa-matchfinder 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

Download README