1
\$\begingroup\$

I have the following text dataset:

4 million paragraphs of length between (10-60 words each).

paragraphs = ['yarrow heart lamium bleeding daisy pea',  'sweet shasta sedum daisy yarrow rhododendron',  'rhododendron pea shasta daisy gladiolus heart',  'gladiolus lamium rhododendron heart pea shasta',  'heart daisy yarrow gladiolus rhododendron sedum',  'pea sedum sweet shasta yarrow bleeding', 
 'yarrow sedum lamium sweet daisy gladiolus',  'heart daisy sweet bleeding pea shasta',  'daisy sweet lamium rhododendron pea bleeding',  'daisy lamium rhododendron gladiolus yarrow',  'rhododendron daisy lamium yarrow sedum',  'bleeding sedum pea heart daisy yarrow', 
 'pea sweet yarrow gladiolus lamium shasta',  'pea rhododendron sweet daisy bleeding yarrow',  'gladiolus daisy bleeding lamium sedum shasta',  'bleeding yarrow pea sedum daisy sweet',  'lamium sweet gladiolus heart rhododendron daisy',  'lamium yarrow sedum pea heart shasta',  'shasta lamium pea heart sedum yarrow',  'lamium bleeding daisy rhododendron gladiolus pea', 
 'lamium yarrow shasta heart sweet gladiolus',  'pea shasta heart sweet yarrow gladiolus',  'sedum shasta rhododendron daisy pea bleeding',  'sedum rhododendron shasta daisy lamium sweet',  'sweet rhododendron yarrow heart sedum daisy',  'bleeding sedum heart gladiolus daisy', 
 'lamium yarrow gladiolus pea sweet rhododendron',  'pea sedum bleeding daisy rhododendron',  'shasta pea rhododendron daisy sedum sweet',  'lamium yarrow bleeding pea shasta sedum']

Also I have a set of 30,000 unique sentences:

set_sentences = {'bleeding daisy yarrow',  'bleeding lamium shasta',  'bleeding sweet daisy',  'daisy lamium',  'daisy shasta yarrow',  'gladiolus lamium daisy',  'gladiolus shasta',  'heart daisy lamium',  'heart shasta lamium', 
 'heart sweet daisy',  'heart sweet lamium',  'lamium daisy shasta',  'lamium sweet pea',  'lamium yarrow',  
 'pea daisy rhododendron',  'pea shasta sweet',  'pea sweet gladiolus',
  'rhododendron bleeding sedum',  'rhododendron daisy',  'rhododendron gladiolus shasta',  'sedum bleeding yarrow',  'sedum lamium bleeding',  'sweet bleeding pea',  'sweet lamium daisy',  'sweet shasta',  'yarrow gladiolus',  'yarrow sedum heart',  'yarrow sedum rhododendron',  'yarrow sedum shasta',  'yarrow sedum sweet'}

I want to check if ANY of the sentences in the set are in those 4 million paragraphs. If any of those 30,000 sentences are in one of those paragraphs I want to keep that particular paragraph, else I should discard it.

Here is my implementation, which works but for that amount of data it's very slow.

def membership_testing(para, set_item):
    for item in set_item:
        if item in para:
            return 'VALID'

df = pd.DataFrame(data={'PARAGRAPH': paragraphs})
df['VALIDITY'] = df['PARAGRAPH'].apply(lambda x: membership_testing(x, set_sentences))
df['VALIDITY'] = df['VALIDITY'].fillna('INVALID')
df = df[df['VALIDITY'] == 'VALID'].reset_index(drop=True)

How could I improve my code? I tried using swifter, it's estimated that it will take around 5 hours for that amount of data!

Is there a way to speed things up, like dask? I'm open to the idea of using a different file format like CSV etc, for example, if reading data from disk.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ How many unique words are there? How many words in the shortest sentence? Do the paragraphs/sentences have punctuation? Is the sample data truly representative of your data? 4M paragraphs * 30K = 120G string searches. Pruning the search space is one way to get meaningful speed ups. But good pruning will likely depend on having representative test data. For example, if sentences end with periods, etc., then as soon as a mismatch occurs, we can skip to the next sentence in the paragraph instead of only skipping ahead a few characters or a word. \$\endgroup\$
    – RootTwo
    Jul 17 at 7:09
  • \$\begingroup\$ @RootTwo The paragraphs are quite unique since I removed any duplicates using pandas. They contain punctuations. The dataset was preprocessed using FastText so that only English paragraphs (90% probability) are left. Could you elaborate on what you mean by pruning? \$\endgroup\$ Jul 17 at 7:19
  • \$\begingroup\$ @RootTwo Yes, the 30k is representative of the whole dataset. I mean originally they were part of it, they're not foreign to it at all. \$\endgroup\$ Jul 17 at 7:27
  • 1
    \$\begingroup\$ By "pruning", I mean figuring out a way to reduce the number of sentences than need to be tested. If each paragraph only needs to be tested against 100 sentences instead of 30K sentences, that could speed things up. \$\endgroup\$
    – RootTwo
    Jul 17 at 21:19

1 Answer 1

1
\$\begingroup\$

The key to solving this quickly is to focus at the right level. Doing string searches is basically looking at the level of the characters that make up the sentences and paragraphs. When I asked the questions in the comments, I was looking at words, because the example data you gave sentences and paragraphs as a series of words. But, after your answers to my questions, I realized the right level is to look at the sentences. By focusing at the sentence level, it's possible to filter 4M paragraphs and 30K sentences in 20 seconds (as reported by %%timeit in a Jupyter notebook)

In a comment you said the sentences came from a paragraph, so I presume that you can split a paragraph into its sentences. In my test data each sentence ends with a '.'. So I can split paragraphs into sentences using a simple regex:

sentences = re.split(r"(?<=\.) ", paragraph)

If we put the 30K sentences into a set(),

set_of_sentences = set(sentences)

then we can check each sentence in a paragraph to see if it is in the set. If any sentences are in the set, then the paragraph is valid.

for para in paragraphs:
    if any(sentence in set_of_sentences for sentence in regex.split(para)):
        valid.append(para)

Putting it all together:

import re

set_of_sentences = set(sentences)

valid = []

regex = re.compile(r"(?<=\.) ")

for para in paragraphs:
    if any(sentence in set_of_sentences for sentence in regex.split(para)):
        valid.append(para)

Using Faker, I created a data set of 4M paragraphs of 10-60 words and 30K sentences. Approximately 2M paragraphs contained at least one sentence from the 30K set. Filtering out the paragraphs that did not contain at least one sentence took about 20 seconds.

The same approach can be used with pandas:

import pandas as pd

set_of_sentences = set(sentences)

regex = re.compile(r"(?<=\.) ")

def test(para):
    return any(sentence in set_of_sentences for sentence in regex.split(para))

df = pd.DataFrame(data={'PARAGRAPH': paragraphs})

criterion = df['PARAGRAPH'].map(test)

valid = df[criterion].reset_index(drop=True)

This also takes about 20 seconds.

For the sake of completeness, here's the code to generate the test data:

from faker import Faker
from random import choice, randrange, sample, shuffle

NUMBER_OF_PARAGRAPHS = 4_000_000
NUMBER_OF_SENTENCES  = 30_000
PERCENT_VALID = 50
NUMBER_VALID = NUMBER_OF_PARAGRAPHS*PERCENT_VALID//100

fake = Faker('en_US')

# generate the sentences to test against
sentences = [fake.sentence() for _ in range(NUMBER_OF_SENTENCES)]

# initialize empty paragraphs
paragraphs = [[] for _ in range(NUMBER_OF_PARAGRAPHS)]

# assign a random sample of paragraphs one of the sentences
for i in sample(range(NUMBER_OF_PARAGRAPHS), k=NUMBER_VALID):
    paragraphs[i].append(choice(sentences))

# Pick a random minimum size for each paragraph. Then add new sentences
# until the paragraph is longer than its minimum size.
for i, para in enumerate(paragraphs):
    word_count = para[0].count(' ') + 1 if para else 0
        
    min_word_count = randrange(10, 60)
    while word_count < min_word_count:
        sentence = fake.sentence()
        para.append(sentence)
        word_count += sentence.count(' ') + 1
            
    shuffle(para)
    paragraphs[i] = ' '.join(para)
\$\endgroup\$
1
  • \$\begingroup\$ Thanks for your help, I will study your solution, and I will get back to you in a few days. \$\endgroup\$ Jul 19 at 12:00

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.