Fuzzy grep for fuzzy bears in pure Python

Question

^{I am aware of the Python modules galore to do this, but this was partially a learning experience and partially all the functionality I need and no more.}

I'm writing a simple interpreter for a Forth-like language, and because my CLIs are of the most high quality,^{[citation needed]} I need to make the entire source (docstrings especially, but the rest of it too) searchable on a whim from within the interpreter.

To do this, I cooked up a little script I'm quite pleased with, which finds a bunch of possible matches of varying relevance and returns them as a populus structure.

Its fuzziness is sometimes wayy too fuzzy, due to the extremely simplistic way in which it's implemented. Mess around with the constants and kwargs to see what you get. Docs or (its own) source code make good test material.

from __future__ import division
from string  import punctuation as punc
from difflib import SequenceMatcher as seqmat

DEBUG = True

class Match():

    def __init__(self, line, line_no, match_type,
                 prectxt, postctxt, misc=None):
        (self.line, self.line_no,
            self.match_type, self.prectxt,
                self.postctxt, self.misc_data) = (line, line_no,
                                    match_type, prectxt, postctxt, misc)

        self.matchinfo = (self.line, self.line_no, self.match_type,
                          self.prectxt, self.postctxt, self.misc_data)

    def match(self): return self.matchinfo

    def misc(self):  return self.misc_data


def fuzzy_files(needle, file_haystack, **kwargs):
    """fuzzy grep in files. turns kwargs in to fuzzy_files"""

    metamatches = {}

    for fname in file_haystack:

        fio = open(fname, "r")
        fct = fio.read()
        fio.close()

        metamatches[fname] = fuzzy_grep(needle, fct, **kwargs)

    return metamatches


def fuzzy_grep(needle,            haystack,
        TOLERANCE_BASE   = .3,    CONTEXT_LINES = 2,
        PUNC_IS_JUNK     = True,  JUNK_FUNC     = None,
        CONSIDER_CASE    = False, ADJUST_BYLEN  = True,
        APPROX_THRESHOLD = .5
        ):
    """fuzzily grep, finding needle in haystack.split('\n')
    warn: if these aren't properly tweaked, results will be 2fuzzy4u

    KWARG_CONSTANT   = description                          type  = default
    TOLERANCE_BASE   = base tolerance for seqmat ratio      float = .4
    CONTEXT_LINES    = lines surrounding each match to give int   = 2
    PUNC_IS_JUNK     = consider punctuation in fuzziness    bool  = True
    JUNK_FUNC        = a caller-supplied junk-decider       func  = None
    CONSIDER_CASE    = consider case in matches             bool  = False
    ADJUST_BYLEN     = adjust using line len                bool  = True
    APPROX_THRESHOLD = fuzziness threshold; tweak me!       float = .5?
    """

    from collections import Counter

    matches = []

    # case-preserver, for printing lines of context.
    PCASE = {
        "needle": needle,
        "haystack": haystack,
        "haystack_spl": haystack.split("\n"),
    }

    # caching
    # the length of the needle won't change,
    # but the length of the line will,
    # and the same input line len will yield the same output
    ndl_len = len(needle)
    bylen_vals = {}

    # human-usability - the range is from 1 to n, so increment n.
    R_CONTEXT_LINES = range(1, CONTEXT_LINES + 1)

    if PUNC_IS_JUNK:
        junk = (lambda x: set(punc) & set(x))
    elif JUNK_FUNC is not None:
        junk = JUNK_FUNC
    else:
        junk = (lambda x: False)

    if not CONSIDER_CASE:
        needle   = needle.lower()
        haystack = haystack.lower()

    ls = haystack.split("\n")

    for idx, line in enumerate(ls):

        tolerance = TOLERANCE_BASE

        if ADJUST_BYLEN and ndl_len:
            hstk = len(line)
            # caching
            if hstk in bylen_vals.keys():
                tolerance = bylen_vals[hstk]
            elif hstk:
                # seems to be a good algorithm for adjustment based on line len
                tolerance = round(tolerance + tolerance * ((ndl_len / hstk) * 4), 2)
                bylen_vals[hstk] = tolerance

        # nondeduplicating membership tester, like set()
        fuzziness = list((Counter(needle) & Counter(line)).elements())

        s = seqmat(junk, line, needle)

        ratio = s.ratio()
        exact = (needle in line) or ("".join(sorted(needle)) in "".join(sorted(line)))
        apprx = ratio + tolerance
        found = exact or apprx > APPROX_THRESHOLD
        inlin = sorted(fuzziness) == sorted(needle)
        if found and inlin:

            # object-existence insurance; not pointless
            prectxt, postctxt = ([""], [""])

            if (idx - 1) >= 0:
                prectxt = []
                for i in R_CONTEXT_LINES:
                    if idx - i >= 0:
                        prectxt.append(PCASE["haystack_spl"][idx - i])

            if (idx + 1) <= len(ls):
                postctxt = []
                for i in R_CONTEXT_LINES:
                    if idx + i <= len(ls):
                        postctxt.append(PCASE["haystack_spl"][idx + i])

            matches.append(
                Match(
                    line, idx,
                    "exact" if exact else "fuzzy",
                    prectxt, postctxt,
                    misc = {
                        "seqmat": {"self": s, "ratio": ratio, "tolerance": tolerance, "tolerance_base": TOLERANCE_BASE},
                        "misc": locals()
                    }
                )
            )

    return matches

def demo():
    output = []
    needle, haystacks = argv[1], argv[2:]
    results = fuzzy_files(needle, haystacks)  # a string as arg #1 and filenames as the rest

    for idx, fname in enumerate(results):
        ms = results[fname]

        for item in ms:

            output.append(
                "\n{}\nline {} of file {}: match type = {}\n"
                .format(
                    "-" * 100, item.line_no, fname, item.match_type
                ) + "\n" +
                "\t" + "\n\t".join(item.prectxt) + "\n"
                "\x1b[1;31m>>>\t" + item.line + "\x1b[m\n" +
                "\t" + "\n\t".join(item.postctxt) + "\n"
            )

    print("".join(output), "\n{}\nprocessed {} matches".format("-" * 100, len(output)))

if __name__ == '__main__' and DEBUG:
    from sys import argv
    #print(argv[1], argv[2:])
    demo()

On github.

I think it well achieves its goal of being a simple data-dumper with an easily-handled API.

I'm sure there's stuff I could do better, but the duplication is really bothering me.

For example, the last two if statements in fuzzy_grep are identical except in the direction of three operators; they can't be made into a function because they rely too heavily on local variables and a function which takes locals() as an argument incurs even more overhead than right now, with the locals() in the Match object, because of debugging and being able to inspect alll the data is nice.

---

Written in Python 3, but completely maintains backwards compatibility to Py2. Yay!

---

You may notice I replaced the code in this post with a much newer, much better version. Per these meta posts, it's apparently ok:

• Is it okay to modify code in a post if we've discovered a bug, before receiving an answer?
• Can I edit the code of my question if I haven't received any answers and comments yet?

Answer 1

Opening files

While it's a small nitpick, it was bothering me a little. On these three lines, you're opening a file, reading it and then closing it:

fio = open(fname, "r")
fct = fio.read()
fio.close()

While this is a small chunk of code, if an exception occurs between the file opening, or closing (while the file is being read, for example), the resources used to open the file are not released. If you want to ensure that the resources are properly released, you need to use a context manager by writing out a with statement. Your above code would become this:

with open(fname, "r") as fio:
    fct = fio.read()

# continue to do things with `fct`

If you need to support pre-Python 2.5 for some reason, then you'd have to write some hacky code using try and finally. You'd end up with something looking like this:

fio = open(fname, "r")

try:
    fct = fio.read()
finally:
    fio.close()

# Do more stuff with `fct

---

Style nitpicks

This line of code is particularly nasty:

(self.line, self.line_no,
    self.match_type, self.prectxt,
        self.postctxt, self.misc_data) = (line, line_no,
                            match_type, prectxt, postctxt, misc)

Is there a reason you need to assign these values like this? If you assign them separately and in a more readable manner, as I did below, the behaviour of your code should remain the same.

self.line = line
self.line_no = line_no
self.match_type = match_type
self.prectxt = prectxt
self.postctxt = postctxt
self.misc = misc

I also found this chunk of code as well:

def fuzzy_grep(needle,            haystack,
    TOLERANCE_BASE   = .3,    CONTEXT_LINES = 2,
    PUNC_IS_JUNK     = True,  JUNK_FUNC     = None,
    CONSIDER_CASE    = False, ADJUST_BYLEN  = True,
    APPROX_THRESHOLD = .5
    ):

It's hard to write function definitions with that many arguments in Python, and as far as I can tell, there's no real "correct" way of writing these. I usually just write them out like this:

def fuzzy_grep(
    needle,            
    haystack,
    TOLERANCE_BASE=0.3,    
    CONTEXT_LINES=2,
    PUNC_IS_JUNK=True,  
    JUNK_FUNC=None,
    CONSIDER_CASE=False, 
    ADJUST_BYLEN=True,
    APPROX_THRESHOLD=0.5):
    ...

In addition, if you want to align the parameter value assignments, you can do it like this:

def fuzzy_grep(
    needle,            
    haystack,
    TOLERANCE_BASE   = 0.3,    
    CONTEXT_LINES    = 2,
    PUNC_IS_JUNK     = True,  
    JUNK_FUNC        = None,
    CONSIDER_CASE    = False, 
    ADJUST_BYLEN     = True,
    APPROX_THRESHOLD = 0.5):

While it takes up much more space, it's quite easier to read, and much, much more clean overall.

There are a number of places where you're shortening your variable names when they don't need to be shortened. A few examples might be:

• fname versus filename
• idx versus index
• hstk versus haystack

There are other examples. In general, you shouldn't shorten variable names when they don't need to be shortened. It only takes away from the readability and maintainability of your code.

Other than that, I don't see much else that's too much of an issue.