Efficient Trie-based regex unions for blacklist/whitelist filtering and one-pass mapping-based string replacing
Project description
retrie
retrie offers fast methods to match and replace (sequences of) strings based on efficient Trie-based regex unions.
Trie
Instead of matching against a simple regex union, which becomes slow for large sets of words, a more efficient regex pattern can be compiled using a Trie structure:
from retrie.trie import Trie
trie = Trie()
trie.add("abc", "foo", "abs")
assert trie.pattern() == "(?:ab[cs]|foo)" # equivalent to but faster than "(?:abc|abs|foo)"
trie.add("absolute")
assert trie.pattern() == "(?:ab(?:c|s(?:olute)?)|foo)"
trie.add("abx")
assert trie.pattern() == "(?:ab(?:[cx]|s(?:olute)?)|foo)"
trie.add("abxy")
assert trie.pattern() == "(?:ab(?:c|s(?:olute)?|xy?)|foo)"
A Trie may be populated with zero or more strings at instantiation or via .add
, from which method chaining is possible. Two Trie may be merged with the +
and +=
operators and will compare equal if their data dictionaries are equal.
trie = Trie()
trie += Trie("abc")
assert (
trie + Trie().add("foo")
== Trie("abc", "foo")
== Trie(*["abc", "foo"])
== Trie().add(*["abc", "foo"])
== Trie().add("abc", "foo")
== Trie().add("abc").add("foo")
)
Installation
This pure-Python, OS independent package is available on PyPI:
$ pip install retrie
Usage
For documentation, see retrie.readthedocs.io.
The following objects are all subclasses of retrie.retrie.Retrie
, which handles filling the Trie and compiling the corresponding regex pattern.
Blacklist
The Blacklist
object can be used to filter out bad occurences in a text or a sequence of strings:
from retrie.retrie import Blacklist
# check out docstrings and methods
help(Blacklist)
blacklist = Blacklist(["abc", "foo", "abs"], match_substrings=False)
blacklist.compiled
# re.compile(r'(?<=\b)(?:ab[cs]|foo)(?=\b)', re.IGNORECASE|re.UNICODE)
assert not blacklist.is_blacklisted("a foobar")
assert tuple(blacklist.filter(("good", "abc", "foobar"))) == ("good", "foobar")
assert blacklist.cleanse_text(("good abc foobar")) == "good foobar"
blacklist = Blacklist(["abc", "foo", "abs"], match_substrings=True)
blacklist.compiled
# re.compile(r'(?:ab[cs]|foo)', re.IGNORECASE|re.UNICODE)
assert blacklist.is_blacklisted("a foobar")
assert tuple(blacklist.filter(("good", "abc", "foobar"))) == ("good",)
assert blacklist.cleanse_text(("good abc foobar")) == "good bar"
Whitelist
Similar methods are available for the Whitelist
object:
from retrie.retrie import Whitelist
# check out docstrings and methods
help(Whitelist)
whitelist = Whitelist(["abc", "foo", "abs"], match_substrings=False)
whitelist.compiled
# re.compile(r'(?<=\b)(?:ab[cs]|foo)(?=\b)', re.IGNORECASE|re.UNICODE)
assert not whitelist.is_whitelisted("a foobar")
assert tuple(whitelist.filter(("bad", "abc", "foobar"))) == ("abc",)
assert whitelist.cleanse_text(("bad abc foobar")) == "abc"
whitelist = Whitelist(["abc", "foo", "abs"], match_substrings=True)
whitelist.compiled
# re.compile(r'(?:ab[cs]|foo)', re.IGNORECASE|re.UNICODE)
assert whitelist.is_whitelisted("a foobar")
assert tuple(whitelist.filter(("bad", "abc", "foobar"))) == ("abc", "foobar")
assert whitelist.cleanse_text(("bad abc foobar")) == "abcfoo"
Replacer
The Replacer
object does a fast single-pass search & replace for occurrences of replacement_mapping.keys()
with corresponding values.
from retrie.retrie import Replacer
# check out docstrings and methods
help(Replacer)
replacement_mapping = dict(zip(["abc", "foo", "abs"], ["new1", "new2", "new3"]))
replacer = Replacer(replacement_mapping, match_substrings=True)
replacer.compiled
# re.compile(r'(?:ab[cs]|foo)', re.IGNORECASE|re.UNICODE)
assert replacer.replace("ABS ...foo... foobar") == "new3 ...new2... new2bar"
replacer = Replacer(replacement_mapping, match_substrings=False)
replacer.compiled
# re.compile(r'\b(?:ab[cs]|foo)\b', re.IGNORECASE|re.UNICODE)
assert replacer.replace("ABS ...foo... foobar") == "new3 ...new2... foobar"
replacer = Replacer(replacement_mapping, match_substrings=False, re_flags=None)
replacer.compiled # on py3, re.UNICODE is always enabled
# re.compile(r'\b(?:ab[cs]|foo)\b')
assert replacer.replace("ABS ...foo... foobar") == "ABS ...new2... foobar"
replacer = Replacer(replacement_mapping, match_substrings=False, word_boundary=" ")
replacer.compiled
# re.compile(r'(?<= )(?:ab[cs]|foo)(?= )', re.IGNORECASE|re.UNICODE)
assert replacer.replace(". ABS ...foo... foobar") == ". new3 ...foo... foobar"
Development
Run make help
for options like installing for development, linting and testing.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for retrie-0.3.0-py2.py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 81f475145ab91831a49a8c89d886f33cdc4d30d14fe5baeb05c74fa6bce9256f |
|
MD5 | c7dd6d79da0d537b80457e35deec68a2 |
|
BLAKE2b-256 | 411cabb28397ae9886e07776fcd11f826fac3d03aefb477da51540d9df9fc889 |