def build_trie(pattern_filename, pattern_format, encoding, on_word_boundaries):
    '''
    Constructs a finite state machine for performing string rewriting.
    Arguments:
    - `pattern_filename`:
    - `pattern_format`:
    - `encoding`:
    - `on_word_boundaries`:
    '''
    boundaries = on_word_boundaries
    if pattern_format == 'auto' or not on_word_boundaries:
        tsv, boundaries = detect_pattern_format(pattern_filename, encoding,
                                                on_word_boundaries)
    if pattern_format == 'auto':
        if tsv:
            pattern_format = 'tsv'
        else:
            pattern_format = 'sed'
    trie = fsed.ahocorasick.AhoCorasickTrie()
    num_candidates = 0
    with open_file(pattern_filename) as pattern_file:
        for lineno, line in enumerate(pattern_file):
            line = line.decode(encoding).rstrip('\n')
            if not line.strip():
                continue
            if pattern_format == 'tsv':
                fields = line.split('\t')
                if len(fields) != 2:
                    LOGGER.warning(('skipping line {} of pattern file (not '
                                    'in tab-separated format): {}').format(lineno, line))
                    continue
                before, after = fields
            elif pattern_format == 'sed':
                before = after = None
                line = line.lstrip()
                if line[0] == 's':
                    delim = line[1]
                    if delim in '.^$*+?[](){}|\\':
                        delim = '\\' + delim
                    fields = re.split(r'(?<!\\){}'.format(delim), line)
                    if len(fields) == 4:
                        before, after = fields[1], fields[2]
                        before = re.sub(r'(?<!\\)\\{}'.format(delim), delim, before)
                        after = re.sub(r'(?<!\\)\\{}'.format(delim), delim, after)
                if before is None or after is None:
                    LOGGER.warning(('skipping line {} of pattern file (not '
                                    'in sed format): {}').format(lineno, line))
                    continue
            num_candidates += 1
            if on_word_boundaries and before != before.strip():
                LOGGER.warning(('before pattern on line {} padded whitespace; '
                                'this may interact strangely with the --words '
                                'option: {}').format(lineno, line))
            before = sub_escapes(before)
            after = sub_escapes(after)
            if boundaries:
                before = fsed.ahocorasick.boundary_transform(before, on_word_boundaries)
            trie[before] = after
    LOGGER.info('{} patterns loaded from {}'.format(num_candidates,
                                                    pattern_filename))
    return trie, boundaries