4
\$\begingroup\$

Goal:

Look for a substring match within a text for given Keywords. Keep the substring match if the levenshtein distance is smaller than the length of the Keyword divided by (x=10), else return an empty list.

(First of all my apologies if the code is of lower quality. I am quite good in R but very new to Python.)

Current implementation:

from fuzzywuzzy import process
from fuzzysearch import find_near_matches
import math

def fuzzy_extract(qs, ls, threshold, max_dist):
    ret = []
    for word, _ in process.extractBests(qs, (ls,), score_cutoff = threshold):
        for match in find_near_matches(qs, word, max_l_dist = max_dist):
            word = word[match.start:match.end]
            ret.append({"kw": qs, "word": word, "dist": match.dist})
    return(ret)

def get_match(text, keywords, treshold):
    keywords = [keyword.lower() for keyword in keywords]
    text = text.lower()
    
    candidates = []
    for li in [fuzzy_extract(query_string, text, 0, 1) for query_string in keywords]:
        if len(li) > 0:
            for di in li:
                if di["dist"] <= math.ceil(len(di["word"])/treshold):
                    candidates.append(di)
    
    if(len(candidates) == 0):
        return([])

    out = str(candidates[0]["kw"])
    return(out)

keywords = ["apple", "banana", "cherry"]
text = "nana is Looking for an aple."

print(get_match(text, keywords, 10))

For me the part in the middle looks neither efficient and also not very declarative. With part in the middle i mean the Code following:

for li in [fuzzy_extract(query_string, text, 0, 1) for query_string in keywords]:

I started with something longer but more declarative:

candidates = [fuzzy_extract(query_string, ocr_text, 0, 1) for query_string in keywords_ordering]
lens = [len(candidate) > 0 for candidate in candidates]
candidate_lengths = list(compress(candidates, lens))
filtered = [candidate_length[0]["dist"] < math.ceil(len(candidate_length[0]["word"])/10) for candidate_length in candidate_lengths] 
candidate_filtered = list(compress(candidate_lengths, filtered))

In R i would make usage of pipes for These cases to avoid the undeclarative variables in between.

Similar Topics:

Find a best fuzzy match for a string

(Difference is that in this question match candidates are compared to a single word and to a substring of a text).

https://stackoverflow.com/a/36132391/3502164

Custom implementation, rather long.

\$\endgroup\$
5
\$\begingroup\$

Unnecessary parentheses

Switch the following:

return(...) -> return ...
if(...) -> if ...

You switch between the two, probably due to coming from another language. Just try to be consistent and don't use parentheses if you don't have to.

Type Hints

You can use type hints to display what types of parameters are accepted, and what types of values are returned, if any.

def fuzzy_extract(query_string: str, match_string: str, threshold: int, max_dist: int):
def get_match(text: str, keywords: List[str], threshold: int):

The List is imported by from typing import List

Simplify your loops

Instead of checking if len(li) > = 0, you can do that check inside the list comprehension. Also, I would move that outside of the loop into its own variable.

extracted = [fuzzy_extract(query_string, text, 0, 1) for query_string in keywords if len(query_string) > 0]

Empty lists

Instead of checking if the length of the list is 0, simply check if the list is None. An empty list is implicitly None.

if not candidates:

Default Parameters

When passing default parameters, there shouldn't be a space before or after the =.

for word, _ in process.extractBests(query_string, (match_string,), score_cutoff=threshold):
        for match in find_near_matches(query_string, word, max_l_dist=max_dist):

Final Code

from fuzzywuzzy import process
from fuzzysearch import find_near_matches
import math

from typing import List

def fuzzy_extract(query_string: str, match_string: str, threshold: int, max_dist: int):
    matches = []
    for word, _ in process.extractBests(query_string, (match_string,), score_cutoff=threshold):
        for match in find_near_matches(query_string, word, max_l_dist=max_dist):
            word = word[match.start:match.end]
            matches.append({"kw": query_string, "word": word, "dist": match.dist})
    return matches

def get_match(text: str, keywords: List[str], threshold: int):
    keywords = [keyword.lower() for keyword in keywords]
    text = text.lower()

    canidates = []
    extracted = [fuzzy_extract(query_string, text, 0, 1) for query_string in keywords if len(query_string) > 0]
    for item in extracted:
        for di in item:
            if di["dist"] <= math.ceil(len(di["word"]) / threshold):
                canidates.append(di)

    if not canidates:
        return []

    result = str(canidates[0]["kw"])
    return result

keywords = ["apple", "banana", "cherry"]
text = "nana is Looking for an aple."

print(get_match(text, keywords, 10))
\$\endgroup\$
1
  • \$\begingroup\$ I would make extracted a generator instead of a list. Also, it seems odd to return [] for no match. I'd return None or an empty str. \$\endgroup\$
    – RootTwo
    Sep 30 '20 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.