trie-search

Trie-search is a package for text pattern search using marisa-trie.

Installation

$ pip install trie-search

Usage

Create trie dictionary

Before using this package, you need to create trie dictionary, or prepare a list of patterns.

The following example simply creates trie dictionary of marisa_trie.Trie from list of article titles in English version of Wikipedia, and saves it to ./example/triedict.

$ cd ./example
$ curl https://dumps.wikimedia.org/enwiki/latest/enwiki-latest-all-titles-in-ns0.gz | gzcat | python create_triedict.py

NOTICE : This script will consume more than 2GB memory.

trie_search.TrieSearch

Create an instance, and load dictionary:

>>> import trie_search
>>> trie = trie_search.TrieSearch(filepath='./example/triedict')

If you have list or tuple object of patterns, you can create an instance as follows:

>>> patterns = ['pattern1', 'pattern2', 'pattern3']
>>> trie = trie_search.TrieSearch(patterns)

TrieSearch.search_all_patterns

Search all patterns in an input text:

>>> text = ('in computer science , a trie , also called digital tree and '
...         'sometimes radix tree or prefix tree ( as they can be searched '
...         'by prefixes ) , is a kind of search tree - an ordered tree data '
...         'structure that is used to store a dynamic set or associative array '
...         'where the keys are usually strings .')
>>> for pattern, start_idx in trie.search_all_patterns(text):
...     print pattern, start_idx
...
in 0
computer 3
computer science 3
science 12
, 20
a 22
trie 24
, 29
also 31
called 36
digital 43
... skipped ...
array 246
where 252
where the 252
the 258
the keys 258
keys 262
are 267
usually 271
strings 279

The text is the 1st sentence of https://en.wikipedia.org/wiki/Trie. For normalization, remove capitalizations and add single white space before/after symbols.
search_all_patterns returns an iterator. Each searched pattern is represented as a tuple (pattern_string, pattern_start_index). The results are sorted by the start index. If you want to get the result as a list object, use list function as follow:
```
 >>> patterns = list(trie.search_all_patterns(text))
```

TrieSearch.search_longest_patterns

Search longest patterns in an input text:

>>> for pattern, start_idx in sorted(trie.search_longest_patterns(text), key=lambda x: x[1]):
...     print pattern, start_idx
...
in 0
computer science 3
, 20
a 22
trie 24
, 29
also 31
called 36
digital tree 43
and 56
sometimes 60
radix tree 70
or 81
prefix tree 84
( 96
as 98
they 101
can 106
be 110
by 122
prefixes 125
) 134
, 136
is a 138
kind 143
of 148
search tree 151
- 163
an 165
ordered tree data structure 168
that 196
is 201
used to 204
store 212
a 218
dynamic set 220
or 232
associative array 235
where the 253
the keys 259
are 268
usually 272
strings 280

search_all_patterns also returns an iterator. The result sorted by the length of patterns. In the above example, the result is re-sorted by the start index.

trie_search.RecordTrieSearch

trie_search.RecordTrieSearch is a sub class of marisa_trie.RecordTrie, which maps unicode keys to data tuples.

The functions, search_all_patterns and search_longest_patterns, are also implemented in trie_search.RecordTrieSearch.

joein/trie-search