Metadata-Version: 2.4
Name: daachorse
Version: 0.5.0
Classifier: License :: OSI Approved :: Apache Software License
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Rust
Classifier: Topic :: Software Development :: Libraries
Classifier: Topic :: Text Processing
Requires-Dist: sphinx-rtd-theme ; extra == 'docs'
Provides-Extra: docs
License-File: LICENSE-APACHE
License-File: LICENSE-MIT
Summary: 🐎 A fast implementation of the Aho-Corasick algorithm using the compact double-array data structure
Home-Page: https://github.com/daac-tools/python-daachorse
Requires-Python: >=3.10
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM

# python-daachorse

[daachorse](https://github.com/daac-tools/daachorse) is a fast implementation of the Aho-Corasick algorithm using the compact double-array data structure.
This is a Python wrapper.

[![PyPI](https://img.shields.io/pypi/v/daachorse)](https://pypi.org/project/daachorse/)
[![Build Status](https://github.com/vbkaisetsu/python-daachorse/actions/workflows/CI.yml/badge.svg)](https://github.com/vbkaisetsu/python-daachorse/actions)
[![Documentation Status](https://readthedocs.org/projects/python-daachorse/badge/?version=latest)](https://python-daachorse.readthedocs.io/en/latest/?badge=latest)

## Installation

### Install pre-built package from PyPI

Run the following command:

```shell
pip install daachorse
```

### Build from source

You need to install the Rust compiler following [the documentation](https://www.rust-lang.org/tools/install) beforehand.
daachorse uses `pyproject.toml`, so you also need to upgrade pip to version 19 or later.

```shell
pip install --upgrade pip
```

After setting up the environment, you can install daachorse as follows:

```shell
pip install git+https://github.com/daac-tools/python-daachorse
```

## Example usage

Daachorse contains some search options,
ranging from basic matching with the Aho-Corasick algorithm to trickier matching.
All of them will run very fast based on the double-array data structure and
can be easily plugged into your application as shown below.

### Finding overlapped occurrences

To search for all occurrences of registered patterns
that allow for positional overlap in the input text,
use `find_overlapping()`. When you instantiate a new automaton,
unique identifiers are assigned to each pattern in the input order.
The match result has the byte positions of the occurrence and its identifier.

```python
>>> import daachorse
>>> patterns = [b'bcd', b'ab', b'a']
>>> pma = daachorse.DoubleArrayAhoCorasick(patterns)
>>> pma.find_overlapping(b'abcd')
[(0, 1, 2), (0, 2, 1), (1, 4, 0)]
```

### Finding non-overlapped occurrences with standard matching

If you do not want to allow positional overlap, use `find()` instead.
It performs the search on the Aho-Corasick automaton
and reports patterns first found in each iteration.

```python
>>> import daachorse
>>> patterns = [b'bcd', b'ab', b'a']
>>> pma = daachorse.DoubleArrayAhoCorasick(patterns)
>>> pma.find(b'abcd')
[(0, 1, 2), (1, 4, 0)]
```

### Finding non-overlapped occurrences with longest matching

If you want to search for the longest pattern without positional overlap in each iteration,
use `MATCH_KIND_LEFTMOST_LONGEST` in the construction.

```python
>>> import daachorse
>>> patterns = [b'ab', b'a', b'abcd']
>>> pma = daachorse.DoubleArrayAhoCorasick(patterns, daachorse.MATCH_KIND_LEFTMOST_LONGEST)
>>> pma.find(b'abcd')
[(0, 4, 2)]
```

### Finding non-overlapped occurrences with leftmost-first matching

If you want to find the the earliest registered pattern
among ones starting from the search position,
use `MATCH_KIND_LEFTMOST_FIRST`.

This is so-called *the leftmost first match*, a bit tricky search option.
For example, in the following code,
`ab` is reported because it is the earliest registered one.

```python
>>> import daachorse
>>> patterns = [b'ab', b'a', b'abcd']
>>> pma = daachorse.DoubleArrayAhoCorasick(patterns, daachorse.MATCH_KIND_LEFTMOST_FIRST)
>>> pma.find(b'abcd')
[(0, 2, 0)]
```

### Find patterns on a string

To build an automaton for strings, use `CharwiseDoubleArrayAhoCorasick` instead.

```python
>>> import daachorse
>>> patterns = ['全世界', '世界', 'に']
>>> pma = daachorse.CharwiseDoubleArrayAhoCorasick(patterns)
>>> pma.find('全世界中に')
[(0, 3, 0), (4, 5, 2)]
```

### Profile-Guided Optimization (PGO)

The double array constructed by daachorse is designed to improve CPU cache efficiency. However, it
is not always the optimal layout for every document being scanned.

daachorse addresses this issue by supporting Profile-Guided Optimization (PGO). By providing a
corpus when constructing the automaton, the memory layout is optimized, which may improve
performance on documents similar to the given corpus.

```python
>>> import daachorse
>>> patterns = [b'ab', b'a', b'abcd']
>>> pma = daachorse.DoubleArrayAhoCorasick(patterns, corpus=[b'abcd'])
```

## License

Licensed under either of

 * Apache License, Version 2.0
   ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
 * MIT license
   ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)

at your option.

