ahocorasick -- search for matches with a keyword tree

Downloads

Introduction

There was a thread in March 2005 where Andre Soereng mentioned that he wanted something to search text for a set of keywords:

Usage

>>> import ahocorasick
>>> tree = ahocorasick.KeywordTree()
>>> tree.add("alpha")          
>>> tree.add("alpha beta")
>>> tree.add("gamma")
>>>
>>> tree.make()
>>>
>>> tree.search("I went to alpha beta the other day to pick up some spam")
(10, 15)
>>> tree.search_long("I went to alpha beta the other day to pick up some spam")
(10, 20)
>>> tree.search("and also got some alphabet soup")
(18, 23)
>>> tree.search("but no waffles")
>>> 
>>> tree.search_long("oh, gamma rays are not tasty")
(4, 9)
>>>
>>> tree.findall("I went to alpha beta to pick up alphabet soup")

>>> for match in tree.findall("I went to alpha beta to pick up alphabet soup"):
...     print match
... 
(10, 15)
(32, 37)

The 'ahocorasick' module provides a single class called KeywordTree. KeywordTree has the following methods:

• add(keyword)

  Adds a new keyword to the automaton. The keyword must be nonempty. If the empty string is passed, raises AssertionError.

• make()

  Finalizes construction of the automaton.

  This must be called before doing any searching, and can only be done if at least one keyword has been added. If called before adding at least one keyword, we'll raise an AssertionError.

• search(query, [startpos])

  Searches the query for the leftmost occuring keyword that the automaton knows. If a match is made, returns the 2-tuple (startIndex, endIndex). If no match can be found, returns None.

  If the optional startpos argument is given, starts the search at that position in the query.

  Note that this matches as quickly as it can: if you want the longest leftmost occuring keyword match, use search_long.

  (startpos added in Release 0.7.)

• search_long(query, [startpos])

  Same as search(), except that this searches for the longest leftmost keyword that matches.

  (startpos added in Release 0.7.)

• findall(query, [allow_overlaps=0])

  Returns an iterator of 2-tuples, of all nonoverlapping matches, using search(). (Added in Release 0.8.)

  If the optional argument allow_overlaps is set to True, then subsequent maches are allowed to to overlap previous ones. (Added in Release 0.9)

• findall_long(query, [allow_overlaps=0])

  Returns an iterator of 2-tuples, of all nonoverlapping matches, using search_long(). (Added in Release 0.8.)

  If the optional argument allow_overlaps is set to True, then subsequent maches are allowed to to overlap previous ones. (Added in Release 0.9)

• chases(source_stream)

  Given an iterator of text blocks, returns an iterator of matches, using search(). Each match result is a 2-tuple (text_block, (start, end)).

  (Added in Release 0.8.)

• chases_long(source_stream)

  Given an iterator of text blocks, returns an iterator of matches, using search_long(). Each match result is a 2-tuple (text_block, (start, end)).

  (Added in Release 0.8.)

Development details

The Aho-Corasick automaton is a data structure that can quickly do a multiple-keyword search across text. It's described in the classic paper 'Efficient string matching: an aid to bibliographic search':

Related Modules

Bugs / Changelog