# Fuzzy grep for fuzzy bears in pure Python

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")
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
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

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:

# 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")
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:

# 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:
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,
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,
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.

• yeah, a context man would definitely be better -- at least I'm not writing fct = open(fname, "r").read(). The variables are assigned like that because I want it to be one line, but identifiers are apparently for humans and so have to be wordy. fname and idx are far quicker to type than filename and index, at least for me, and they're pretty obvious what they represent (except hstk -- I was almost gonna go with length_of_the_current_line` but I decided against) – cat Mar 15 '16 at 1:00
• @tac It is nice to have easy to type variables, but if you have an editor that supports autocomplete (even something just as simple as Notepad++), long variable names generally shouldn't be too much of an issue. – Ethan Bierlein Mar 15 '16 at 1:03
• @that edit about function arguments: I definitely see your point, but how can you read that without the whitespace lined up? – cat Mar 15 '16 at 1:07
• @tac It doesn't matter either way really. I usually prefer compacting them like I did above, but aligning them is fine. I'll edit my answer with an alternate version – Ethan Bierlein Mar 15 '16 at 1:09