wroberts / fsed

Aho-Corasick string replacement utility

fsed - Aho-Corasick string replacement utility

Copyright (c) 2015 Will Roberts <[email protected]>

Licensed under the MIT License (see file LICENSE.rst for details).

Search and replace on file(s), with matching on fixed strings.

fsed is a tool specially designed for situations where you have to do many string search-and-replace operations with fixed strings (that is, fsed doesn't do regular expressions). By doing all the searching and replacing on all the patterns at the same time, fsed can be much faster than tools that do string rewriting one pattern at a time (like one-liners in sed or perl).

To do its searching, fsed uses the Aho-Corasick algorithm, which is a very clever way of matching multiple patterns at the same time, and was used to implement the original fgrep Unix utility (now accessed as grep -F). This algorithm is capable of finding matches which overlap each other, and in these cases, fsed must choose which matches to rewrite. The policy adopted by fsed is to be greedy, and always rewrite the shortest, leftmost match first.

For illustration, imagine a situation where we would like to rewrite a with b, aa with c, and aaa with d. What should we do when we see the input string aaa? Should we produce bbb, bc, cb, or d? fsed produces bbb in this case.

Install

fsed is written in Python; you can install it with pip:

pip install fsed

Usage

fsed [OPTIONS] PATTERN_FILE [INPUT_FILE [INPUT_FILE2 ...]]

If one or more INPUT_FILEs are specified, fsed reads and concatenates these as its input; otherwise, fsed reads the standard input.

Options:

--pattern-format=FMT

Set FMT to tsv or sed (default is sed) to specify the format of PATTERN_FILE.

-o/--output=OUTFILE

Specifies that the program output should be written to OUTFILE. If this option is not used, fsed writes to standard output.

-w/--words

Makes fsed match only on word boundaries; this flag instructs fsed to append \b to the beginning and end of every pattern in PATTERN_FILE.

--by-line/--across-lines

Sets whether fsed should process the input line by line or character by character; the default is --across-lines.

--slow

Indicates that fsed should try very hard to always find the longest matches on the input; this is very slow, and forces --by-line to be on.

-q

Quiet operation, do not emit warnings.

-v/--verbose

Turns on debugging output.

Note: fsed runs even faster using PyPy:

pypy -m fsed.fsed [OPTIONS] PATTERN_FILE [INPUT_FILE [INPUT_FILE2 ...]]

Pattern File

PATTERN_FILE contains a list of patterns to search and replace in the input; each pattern is listed on a separate line. fsed supports two formats for specifying patterns. The default, sed, specifies strings and their replacements the way the sed utility does:

s/SEARCH/REPLACE/

The character following the s character is the pattern delimiter, and can be any character (it does not have to be a forward slash).

The other format, tsv, specifies patterns using <TAB> characters as delimiters:

SEARCH<TAB>REPLACE

In this format, there must be only one <TAB> character per line.

Patterns can contain escape characters:

\\

Backslash (\)

\a

ASCII bell (BEL)

\b

Word boundary

\f

ASCII formfeed (FF)

\n

ASCII linefeed (LF)

\r

Carriage Return (CR)

\t

Horizontal Tab (TAB)

\v

ASCII vertical tab (VT)

fsed's Issues

end2end failure

I am looking at packaging this for openSUSE, and ran into the following test failure on Python 2 and 3
https://build.opensuse.org/package/show/home:jayvdb:py-new/python-fsed

[   18s] FAIL: test_end2end (fsed.tests.test_fsed.TestFsed)
[   18s] ----------------------------------------------------------------------
[   18s] Traceback (most recent call last):
[   18s]   File "/home/abuild/rpmbuild/BUILD/fsed-0.5.3/fsed/tests/test_fsed.py", line 172, in test_end2end
[   18s]     self.assertEqual(exit_code, 0)
[   18s] AssertionError: 2 != 0

All other tests pass, as can be seen at the logs in the openSUSE build systems URL above.

code is trying to get length of generator object

from fsed.fsed import build_trie
from fsed.fsed import rewrite_str_with_trie
from __future__ import unicode_literals

word_separation = True
word_encoding = 'utf-8'
slow_match = True

trie, boundaries = build_trie('synonyms.txt', 'sed', 'utf-8', word_separation)


line = unclean_doc.decode(word_encoding).rstrip('\n').lower()
line = rewrite_str_with_trie(line, trie, boundaries, slow_match)

error message:

TypeError                                 Traceback (most recent call last)
<ipython-input-6-daf73fb3cd97> in <module>()
     12     print(datetime.now(), doc)
     13     return unclean_doc, doc
---> 14 print(process_doc(doc))

<ipython-input-6-daf73fb3cd97> in process_doc(doc)
      8     print(datetime.now(), unclean_doc)
      9     line = unclean_doc.decode(word_encoding).rstrip('\n').lower()
---> 10     line = rewrite_str_with_trie(line, trie, boundaries, slow_match)
     11     doc = (line).encode(word_encoding)
     12     print(datetime.now(), doc)

/home/vikash/anaconda3/envs/python2.7/lib/python2.7/site-packages/fsed/fsed.pyc in rewrite_str_with_trie(sval, trie, boundaries, slow)
    173         sval = fsed.ahocorasick.boundary_transform(sval)
    174     if slow:
--> 175         sval = trie.replace(sval)
    176     else:
    177         sval = trie.greedy_replace(sval)

/home/vikash/anaconda3/envs/python2.7/lib/python2.7/site-packages/fsed/ahocorasick.pyc in replace(self, seq)
    282         #    each cell gets assigned (0, char), where char is the character at
    283         #    the corresponding position in the input string
--> 284         chart = [ [None for _i in range(len(seq)) ] for _i in range(len(seq)) ]
    285         chart[0] = [(0, char) for char in seq]
    286         # now we fill in the chart using the results from the aho-corasick

TypeError: object of type 'generator' has no len()