Python - Find a phrase inside a long text

What's the most efficient way of finding a phrase inside a longer text with python?
What I would like to do is finding the complete phrase, but if it's not found, split it into smaller parts and try to find them, down to single words.

For example, I have a text:

> Paragraphs are the building blocks of papers. Many students define paragraphs in terms of length: a paragraph is a group of at least five sentences, a paragraph is half a page long, etc...There are many techniques for brainstorming; whichever one you choose, this stage of paragraph development cannot be skipped.

I want to find the phrase: there is a group of students

The entire phrase as it is will not be found, but its smaller parts yes. So it will find:

• there
• is a group of
• students

Is this even possible? if so, what's the most efficient algorithm to achieve so?

I tried with some recursive functions but they are not able to find these sub-parts of the phrase, either they find the entire phrase or they just find the single words.

If you want a robust approach that works on the word level but can also capture, e.g., "...That" vs. "that", I'd recommend some basic NLP with NLTK.
That is if you're working with a small to medium sized data set.

from nltk import ngrams, word_tokenize

text = "..."  # your text
query = "there is a group of students"

def preprocess(raw):
    return [token.lower() for token in word_tokenize(raw)]
    
def extract_ngrams(tokens, min_n, max_n):
    return set(ngram for n in range(min_n, max_n + 1) for ngram in ngrams(tokens, n))


min_n = 1
max_n = len(query)

text_ngrams = extract_ngrams(preprocess(text), min_n, max_n)
query_ngrams = extract_ngrams(preprocess(query), min_n, max_n)

print(text_ngrams & query_ngrams)

Output:

{('a',),
 ('a', 'group'),
 ('a', 'group', 'of'),
 ('group',),
 ('group', 'of'),
 ('is',),
 ('is', 'a'),
 ('is', 'a', 'group'),
 ('is', 'a', 'group', 'of'),
 ('of',),
 ('students',),
 ('there',)}

The simplest approach would be by generating all possible subsets of the phrase that you want to find and simply check if the text contains them using if phrase_slice in paragraph.

To get the subsets you can use a double loop - first determines how many words from phrase to include and second offsets the words. An example would be something like that:

text = "Paragraphs are the building blocks of papers. Many students define paragraphs in terms of length: a paragraph is a group of at least five sentences, a paragraph is half a page long, etc...There are many techniques for brainstorming; whichever one you choose, this stage of paragraph development cannot be skipped."
phrase = ["there", "is", "a", "group", "of", "students"]

for i in range(len(phrase)):
    n_words = len(phrase) - i
    for j in range(len(phrase)-i):
        phrase_slice = phrase[j:n_words+j]
        if " ".join(phrase_slice) in text:
            # Do stuff

Would something like this work?

from itertools import combinations

#Load up paragraph and phrase to be searched
paragraph = "Paragraphs are the building blocks of papers. Many students define paragraphs in terms of length: a paragraph is a group of at least five sentences, a paragraph is half a page long, etc...There are many techniques for brainstorming; whichever one you choose, this stage of paragraph development cannot be skipped."

phrase = "there is a group of students"

phrase_words = phrase.split()

#Generate all possible iterations of the words in the phrase
phrase_sections = []
for i in range(1,len(phrase_words)):
    for combination in combinations(phrase_words, i):
        phrase_sections.append(', '.join(combination).replace(',', ''))

#Search for phrase in paragraph (searching in phrase is a quick and dirty way to maintain order of words)
for section in phrase_sections:
    if (section in phrase) & (section in paragraph):
        print(section)

This outputs:

is
a
group
of
students
is a
a group
group of
is a group
a group of
is a group of

TEXT = "Paragraphs are the building blocks of papers. Many students define paragraphs in terms of length: a paragraph is a group of at least five sentences, a paragraph is half a page long, etc... There are many techniques for brainstorming; whichever one you choose, this stage of paragraph development cannot be skipped."

TO_FIND = "there is a group of students"

dict = {}

def preprocess_text():
    TEXT.lower()
    TEXT.replace(".", "")
    TEXT.replace(",", "")
    TEXT.replace(";", "")
    TEXT.replace(":", "")
    TEXT.replace("!", "")
    TEXT.replace("?", "")
    TEXT.replace("...", "")

def find_groups(occurences):
    groups = []
    for i in range(len(occurences) - 1):
        group = []
        while occurences[i][0] + 1 == occurences[i + 1][0]:
            group.append(occurences[i])
            i += 1
            if i == len(occurences) - 1:
                if group is not None:
                    group.append(occurences[i])
                break
        if len(group) > 0:
            groups.append(group)
    return groups

def make_dict():
    idx = 0
    for word in TEXT.lower().split():
        dict[idx] = word
        idx += 1

def find_words():
    occurences = [(k, v) for k, v in dict.items() if v in TO_FIND.split()]
    return occurences

if __name__ == "__main__":
    make_dict()
    occurences = find_words()
    groups = find_groups(occurences)
    solutions = []
    for group in groups:
        tmp = []
        for elem in group:
            tmp.append(elem[1])
        tmp = " ".join(tmp)
        solutions.append(tmp)
    for occurence in occurences:
        if occurence[1] not in solutions:
            solutions.append(occurence[1])
    for solution in solutions:
        print(solution)

The code is a bit complex but it works nicely, 54ms execution time on my machine.

The code first slices the input text and gets all the words that are in the text to find. It then tries to recombine the adjacent words into groups, finds the remaining words that have not been grouped together and prints everything.

I hope that can help !