Python string occurence count regex performance

Question

I was asked to find the total number of substring (case insensitive with/without punctuations) occurrences in a given string. Some examples:

count_occurrences("Text with", "This is an example text with more than +100 lines") # Should return 1
count_occurrences("'example text'", "This is an 'example text' with more than +100 lines") # Should return 1
count_occurrences("more than", "This is an example 'text' with (more than) +100 lines") # Should return 1
count_occurrences("clock", "its 3o'clock in the morning") # Should return 0

I chose regex over .count() as I needed an exact match, and ended up with:

def count_occurrences(word, text):
    pattern = f"(?<![a-z])((?<!')|(?<='')){word}(?![a-z])((?!')|(?=''))"
    return len(re.findall(pattern, text, re.IGNORECASE))

and I've got every matching count but my code took 0.10secs while expected time is 0.025secs. Am I missing something? is there any better (performance optimised) way to do this?

Answer 1

OK, I was struggling to make it work without regexes, as we all know that regexes are slow. Here is what I came up with:

def count_occurrences(word, text):
    spaces = [' ', '\n', '(', '«', '\u201d', '\u201c', ':', "''", "__"]
    endings = spaces + ['?', '.', '!', ',', ')', '"', '»']
    s = text.lower().split(word.lower())
    l = len(s)
    return sum((
            (i == 0 and (s[0] == '' or any(s[i].endswith(t) for t in spaces)) and (s[1] == '' or any(s[i+1].startswith(t) for t in endings))) 
            or (i == l - 2 and any(s[i].endswith(t) for t in spaces) and (s[i+1] == '' or any(s[i+1].startswith(t) for t in endings)))
            or (i != 0 and i != l - 2 and any(s[i].endswith(t) for t in spaces) and any(s[i+1].startswith(t) for t in endings))
        ) for i in range(l - 1))

The whole file runs in ideone:

Ran 1 test in 0.025s

OK

Which is what the question is asking for.

The logic is pretty simple. Let's split the text by word, both lower cased. Now let's look at each couple of neighbours. If, for example index 0 finished with a valid delimiter, and index 1 starts with a valid delimiter, let's count it as an occurrence. Let's do that up to the last couple of the split.

Since performance is important here, we have to be aware to the order of spaces and endings. We are basically looking for the first in the list to fulfil the condition. So it is important to locate the variables that are more common first. For example, If I declare:

spaces = ['(', '«', '\u201d', '\u201c', ':', "''", "__", '\n', ' ']

instead of what I have in my solution, I get a run of 0.036 seconds.

If for example I declare one array:

spaces = [' ', '\n', '(', '«', '\u201d', '\u201c', ':', "''", "__", '?', '.', '!', ',', ')', '"', '»']

which has all delimiters and use only that, I get 0.053 seconds. Which is 60% more than my solution.

It is probably possible that there is a better solution with declaring the delimiters in another order.

Answer 2

If the words are you searching is defined and finite, regex pre-compilation through re.compile could help to make things faster. Something like:

search_words = [
  'foo',
  'bar',
  'baz',
]

words_to_re = {w: re.compile(f"(?<![a-z])((?<!')|(?<='')){w}(?![a-z])((?!')|(?=''))") for w in search_words}

def count_occurrences(word, text):
    regex = words_to_re[word]
    return len(regex.findall(text))

Answer 3

You can turn all word to lowercase manually using string.lower() function. Check this maybe this will help you:

def count_occurrences2(word, text):
    text = text.lower()
    word = word.lower()
    pattern = f"(?<![a-z])((?<!')|(?<='')){word}(?![a-z])((?!')|(?=''))"
    return len(re.findall(pattern, text))

I have inspected execution time using timeit library:

import timeit

def checkTime(word, text, function):
  now = timeit.default_timer()
  function("more than", lines)
  return timeit.default_timer()-now

text = "This is an example 'text' with (more than) +100 lines "*1000
word = "more than"
time_0 = checkTime("more than",text, count_occurrences)
time_1 = checkTime("more than",text, count_occurrences2)
print(time_0)
print(time_1)
print(time_1 < time_0) //true

Edit:

This is another way:

def count_occurences_in_text(word, text):
    pattern = r"(?<![a-z])((?<!')|(?<=''))"+str(word.lower())+"(?![a-z])((?!')|(?=''))"
    line_now = text.lower()
    count = 0
    search = re.search(pattern, line_now)
    while search:
        count +=1
        line_now = line_now[search.span()[1]:]
        search = re.search(pattern,line_now)
    return count

Edit 2:

This function will pass all assertion in your code(considering execution time):

def count_occurences_in_text(word, text):
    text = text.lower()
    word = word.lower()
    word_len = len(word)
    text_len = len(text)
    if not (word[0] >= 'a' and word[0] <= 'z') :
        word = word[1:word_len]
        if not (word[len(word) - 1] >= 'a' and word[len(word) - 1] <= 'z') :
            word = word[1:len(word)-1]
    count = 0
    index = 0
    have = [' ', ",","!","?",".","\n",":"]
    haveP = [' ',':']
    if word_len > text_len:
        return 0;
    while index < text_len-word_len+1:
        if text[index:index+word_len] == word:
            if index != 0:
                prev_word = text[index-1]
                # if (prev_word >= 'a' and prev_word <= 'z') or prev_word == "'":
                if prev_word not in haveP:
                    if index > 1 and text[index-1] =="'" and text[index-2]=="'":
                        count+=1
                        index += word_len+1
                        continue
                    if index > 1 and text[index-1] =="_" and text[index-2]=="_":
                        count+=1
                        index += word_len+1
                        continue
                    else:
                        index += 1
                        continue
            if index + word_len <= text_len-1:
                last_word = text[index+word_len]
                # if (last_word >= 'a' and last_word <= 'z') or last_word == "'":
                if last_word not in have:
                    if index+word_len <= text_len-2 and last_word =="'" and text[index+word_len+1]=="'":
                        count +=1
                        index += word_len+1
                        continue
                    if index+word_len <= text_len-2 and last_word =="_" and text[index+word_len+1]=="_":
                        count +=1
                        index += word_len+1
                        continue
                    else:
                        index += 1
                        continue
            count += 1
            index += word_len+1
        index += 1
    return count

Answer 4

use a regular expression split

def count_occurrences(search_word,text):
    alist=re.split(r'\s+',text)
    matches=[word for word in alist if word==search_word]
    return len(matches)

count_occurrences("clock", "its 3o'clock in the morning")

output

0

Answer 5

The first error was using the words "Python" and "Performance" in the same sentence. Python is heavily oriented in the direction of "cheap--develop code quickly" with "good--runs as expected" as doable. Fast is right out. Any advice here is strictly implementation-dependent.

1. You can clean up your regular expressions. I recommend using the group shortcut \b (word boundary). In all cases, I strongly recommend playing with your regex interactively in regex101 or equivalent.

2. You can write your own search function in Python. It will be slower by running in Python and faster by skipping storage of matches and other generality.

3. You can compare your speeds against simple string .count(). You will need to use lower() and decide if the word "this" matches "sthisany" or not.

4. You can modify your test function to actually have a hundred lines, e.g., text = (text + '\n')*100.

5. You can use PyPi, which will generally speed up your execution by trading away some start-uptime and some meta-programming flexiblity.

6. You can write a small snippet of C code and learn to call it from Python. Fun on its own.

I recommend you keep notes and comparisons and turn those in with your homework, not just the final product.