# ahocorasick-py

**Repository Path**: wanglingxiao26/ahocorasick-py

## Basic Information

- **Project Name**: ahocorasick-py
- **Description**: AC自动机（Aho-Corasick Automation）的Python实现版本。
- **Primary Language**: Python
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-09-29
- **Last Updated**: 2022-05-25

## Categories & Tags

**Categories**: Uncategorized

**Tags**: Aho, auto

## README

# Aho-Corasick Automation (AC自动机)

AC自动机是最一种**多模式匹配算法**，
它由贝尔实验室的两位研究人员 Alfred V. Aho 和Margaret J.Corasick 于1975年发明，
几乎与KMP算法同时问世，
至今仍然在模式匹配领域被广泛应用。

## 项目特点

1. 基于有序链表的实现

目前许多开源的AC自动机实现方案使用字符串数组作为前缀树的底层数据结构，
这种实现方法通常预分配一个长度固定的字符数组，
并且利用ASCII转码进行字符数组的定位。

上述的AC自动机实现方法比较简单易懂，
但是只能适用于英语、法语、西班牙语、俄语等基于字母文字的语种。
在这些语言中，
64位或者128位长度的字符数组就足够囊括所有的字符集，
然而中日韩语言的字符集数量远大于此。

如果在中日韩语言的AC自动机中依然使用字符数组作为数据结构，就会造成极大的内存开销。
本项目的实现方案用有序链表代替了数组，
既保证了基本的功能，又支持了中文的匹配。

2. 实现简单

通过代码和数据结构的优化，使得程序的主体结构仅仅有80行左右。

## 使用帮助

项目的主体内容是`pattern`文件中的`Pattern`类。
在进行多模式文本匹配之前，需要载入`Pattern`类并进行模式编译。

模式编译的方法是调用`compile`函数，向其输入一个字符串列表，列表中的内容就是需要匹配的字符串模式。

多模式匹配的方法有`findall`和`search`。
- `findall`返回所有被匹配的模式，内容包括文本内容、起始位置和终止位置。
- `search`返回第一个被匹配的模式，内容包括文本内容、起始位置和终止位置。

```python3
from multire.linked_ac_node import Pattern

if __name__ == '__main__':
    pattern = Pattern()
    pattern.compile(["北京", "北京市", "北京大学", "天津上海"])
    print(pattern.findall("北京师范大学位于北京市"))
    print(pattern.search("北京师范大学位于北京市"))
```

下面是运行的结果

```
findall: [(Match text='北京', span=[0, 2]), (Match text='北京', span=[8, 10]), (Match text='北京市', span=[8, 11])]
search: (Match text='北京', span=[0, 2])
```