Identifying “Matching Bigrams” in Large Text Collection

Question

I have a large number of plain text files (north of 20 GB), and I wish to find all "matching" "bigrams" between any two texts in this collection. More specifically, my workflow looks like this: for each text, for each sentence in that text, for each possible combination of two non-stop-words ("bigram") in that sentence, identify all texts in which that "bigram" appears within a single sentence. (I am working on fuzzy plagiarism detection.)

Because I wish to know whether two given authors in my corpus share a given "bigram," I am currently pursuing the following approach:

'''This script reads in a directory of files, and for each of that files, for each sentence in that file, for each non-stop-word in that sentence, for each combination of those words, creates a bigram entry in a table. Each bigram in the bigram table corresponds to a sentence id value,
and these sentence id values correspond to a text id value, which in turn correspond to a filename id value. Using separate tables for each of these values allows us to compress our bigram csv enormously'''

def create_bigram_tables():

    #define the name of authors_and_texts_file and specify its sep
    authors_and_texts = "authors_and_paths_reduced.csv"
    sep = "\t"

    from collections import Counter
    import string, codecs, nltk, glob, re, itertools, os, errno

    tokenizer = nltk.data.load('tokenizers/punkt/english.pickle')
    #b = tokenizer.tokenize("sample string")

    def clean_text(s):
        #to preserve contractions:
        s = s.replace("'","")

        #re1 = match all consecutive non-alpha, non-space strings of length 1 or more.
        re1 = re.compile( "[^a-zA-Z ]+" )
        #re2 = match all strings of 2 or more spaces.
        re2 = re.compile( "  +" )
        p = re2.sub( " ", re1.sub( " ", s ) )
        p = p.split()
        return p

    def make_sure_path_exists(path):
        try:
            os.makedirs(path)
        except OSError as exception:
            if exception.errno != errno.EEXIST:
                raise

    make_sure_path_exists(os.getcwd() + "\\tables")
    make_sure_path_exists(os.getcwd() + "\\author_bigrams")
    make_sure_path_exists(os.getcwd() + "\\error_logs")

    with open(os.getcwd() + "\\tables\\" + "bigram_ids.txt","w") as bigram_id_out:
        with open(os.getcwd() + "\\tables\\" +"sentence_ids.txt","w") as sentence_id_out:
            with open(os.getcwd() + "\\tables\\" +"sentence_to_bigram_mapping.txt","w") as sentence_to_bigram_mapping_out:
                with open(os.getcwd() + "\\tables\\" +"text_id_to_sentence_mapping.txt","w") as text_id_to_sentence_mapping_out:
                    with open(os.getcwd() + "\\tables\\" +"filename_to_text_id_mapping.txt","w") as filename_to_text_id_out:

                        #read in our authors and paths file (we assume each row consists of a tab-separated author--path_to_text pair, in that order; e.g. Daniel_Defoe [tab] C:\moll_flanders)
                        with open(os.getcwd() + "\\author_to_file_paths\\" + authors_and_texts ,"r") as authors_and_paths_in:

                            #create a variable "text_id" we'll use to assign a unique id to each text we ingest
                            text_id = 0

                            #create a variable "sentence_id" we'll use to assign a unique id to each sentence we ingest
                            sentence_id = 0

                            #create a variable "bigram_id" we'll use to assign a unique id to each bigram we ingest
                            bigram_id = 0

                            #create a dummy variable "last_author" and set its initial value to ''
                            last_author = ""

                            #create empty dictionary in which we'll store each author's bigrams
                            author_bigram_dictionary = {}

                            #we want to take a look at our author/text file, the first column of which contains author name, second column of which contains text by author in the same row (e.g. Dickens [tab] Hard Times).
                            #for each line, if we're still looking at the same author we were looking at last time, then keep adding to the same author dictionary. Otherwise, we want to write contents of current dictionary
                            #to disk and create a new dictionary. Let's assume that the author-text file is sorted by author, so after we've read all of the 'Daniel_Defoe' lines we'll reach a new author, and at that point
                            #we'll write the Defoe bigram dictionary to disk.
                            authors_and_paths_in = authors_and_paths_in.readlines()

                            #it's super kludgy, but add one last list object Nul, Nul to authors_and_paths_in in case the last line is an author who only exists once in the database
                            authors_and_paths_in.append("Nul" + sep + "Nul")

                            #now iterate through each line of the authors_and_paths_in file
                            for i in authors_and_paths_in:

                                #use try/except in case something strange happens
                                try:
                                    i_s = i.split(sep)
                                    current_author = i_s[0]
                                    path_to_author_text = i_s[1].replace("\n","").replace("\\","\\\\")

                                    if current_author != last_author:
                                        #check to see if the current author_bigram_dictionary is non-empty (it should only be empty the first time through this code block, because our initial dict is empty)
                                        if author_bigram_dictionary:
                                            with open(os.getcwd() + "\\author_bigrams\\" + str(last_author) + "_bigram_counts.txt","w") as author_bigram_dictionary_out:
                                                for q in sorted(author_bigram_dictionary):
                                                    author_bigram_dictionary_out.write(" ".join(q) + "\t" + str( author_bigram_dictionary[q]["count"] ) + "\n")

                                    last_author = current_author    

                                    #read in text itself
                                    with open(path_to_author_text) as open_i:

                                        ##############################
                                        # identify stopwords in text #
                                        ##############################

                                        read_i = open_i.read()

                                        #strips string of all non-alphabetic characters
                                        i_words = clean_text( read_i.lower() )

                                        raw_counts = Counter( i_words ).most_common(100)

                                        stopwords = []

                                        for j in raw_counts:
                                            stopwords.append(j[0])

                                        #now split the raw text with punctuation into a list of sentences
                                        sentences = tokenizer.tokenize(read_i)

                                        ####################################
                                        # strip each sentence of stopwords #
                                        ####################################

                                        for k in sentences:

                                            #create a clean list representation of the string k. Include only words longer than one letter that are not in the stopwords list in this clean representation
                                            clean_k = [l for l in clean_text( k.lower() ) if l not in stopwords and len(l) > 1]

                                            if len(clean_k) > 1:

                                                #create a variable n with which we'll break the ordered list of non-function words with len > 1 in k into bigrams
                                                n = 0

                                                #now we want to find all combinations between the words in clean_k, and create each as a bigram in our bigram database (of course most of these pairs won't actually be neighboring words in the files themselves). NB: To get trigrams, just change the second parameter to 3.
                                                for m in itertools.combinations(clean_k, 2):

                                                    #data structure for bigram table: bigram_id [tab] bigram[0] bigram[1]
                                                    bigram_id_out.write( str(bigram_id) + "\t" + " ".join(m) + "\n" )

                                                    #after writing our bigram_id to bigram[0] + bigram[1] line, write the mapping from sentence_id to bigram_id
                                                    sentence_to_bigram_mapping_out.write( str(sentence_id) + "\t" + str(bigram_id) + "\n" )

                                                    #then increase bigram value
                                                    bigram_id += 1

                                                    #once we've written this mapping, let's add the bigram to our author_bigram_dictionary
                                                    if m in author_bigram_dictionary.keys():
                                                        author_bigram_dictionary[m]["count"] += 1

                                                    else:
                                                        author_bigram_dictionary[m] = {}
                                                        author_bigram_dictionary[m]["count"] = 1

                                                #now write the mapping from the current sentence id to the current sentence
                                                sentence_id_out.write( str(sentence_id) + "\t" + " ".join(clean_text(k)) + "\n" )

                                                #once we reach the end of the given sentence, record the text in which the current sentence occurs and then increase the sentence_id variable by one to ensure that each sentence has a unique id field
                                                text_id_to_sentence_mapping_out.write( str(text_id) + "\t" + str(sentence_id)  + "\n" )

                                                #now that we've reached the end of the sentence, increase the sentence_id value by one
                                                sentence_id += 1

                                    #now that you've reached the end of the text, record the filename-to-text-id mapping and then increase the variable tied to the text field by one (so the first text we ingest has text_id = 0, next = 1, etc.)                    
                                    filename_to_text_id_out.write( i.split("\\")[-1][:-4] + "\t" + str(text_id) + "\n" )

                                    text_id += 1

                                except Exception as e:

                                    #find an unused error log message and write the message to that filename

                                    with open(os.getcwd() + "\\error_logs\\" + "error_log.txt","w") as error_out:
                                        error_out.write( str(e) )

#use cProfile to determine how long it takes to run the code; write the results of the profiling to a file prof.ile
import cProfile
cProfile.run('create_bigram_tables()', 'prof.ile1')

This is terribly slow, though. Do any of you see opportunities for speed boosts here? I'm open to any and all suggestions others might have.

Answer 1

1. Introduction

This code is not ready to be optimized because it is such a mess. It is hard to read, hard to follow and hard to understand. I've written some detailed comments below, but really I've just scratched the surface.

Your best bet is to rewrite the code so that the algorithm and dataflow are clear, and then you might find it easier to speed it up. If you are still stuck at that point, submit the revised code for review.

(If you resubmit, it would be helpful if you could include enough information for us to be able to run your code: we'll need example data, and your tokenizer.)

2. Review

1. The top level of your script consists of a call to cProfile.run. This can't be right: why would the user of your script want to profile it? I can only presume you put this in there to help you during development and forgot to take it out again. But that's a very error-prone approach: you should get out of the habit of modifying code to debug it, and instead learn how to use the tools. In this case you can run the profiler from the command line:

   python -m cProfile -o output_file myscript.py
   

2. The code is hard to follow because the lines are so long that we have to scroll the window horizontally to read it. You should endeavour to follow the Python style guide (PEP8), which says,

   Limit all lines to a maximum of 79 characters.

   For flowing long blocks of text with fewer structural restrictions (docstrings or comments), the line length should be limited to 72 characters.

   Limiting the required editor window width makes it possible to have several files open side-by-side, and works well when using code review tools that present the two versions in adjacent columns.

3. You have nested all your functions inside the create_bigram_tables function. This makes it hard to write unit tests (or test the code interactively) because there's no way to call clean_text and so on. You should move nested function definitions to top level, unless there's a good reason not to.

4. There are no docstrings for your functions. What do they do and how are they supposed to be called? Having well-written specifications of the behaviour of functions makes them easier to use, review and modify. So I'd expect something like:

   def clean_text(s):
       """Return a list of the words in the string s, where a "word" is a
       consecutive sequence of ASCII letters and apostrophes in s, from
       which the apostrophes have been removed.
   
       """
   

5. I think a better name for this function would be words: naming a function after the thing it returns often makes code easier to understand.

6. Do you really mean to restrict words to ASCII letters? Won't that become a problem later if you want to analyze languages other than English?

7. There's no point in calling re.compile unless you're going to use the compiled regular expression more than once. Instead of:

   re1 = re.compile("regexp")
   re1.sub(s)
   

   just write:

   re.sub("regexp", s)
   

8. You manipulate the text by repeatedly calling str.replace and re.sub. But this is an expensive operation: Python has to build a whole new string in memory each time, and if s is long then so are the replaced strings. It would be more efficient to extract the words you want rather than replacing the non-words. So I would write the function like this:

   def words(s):
       """Return a list of the words in the string s, where a "word" is a
       consecutive sequence of ASCII letters and apostrophes in s, from
       which the apostrophes have been removed.
   
       """
       return re.findall(r"[a-zA-Z]+", s.replace("'", ""))
   

   This is about 25% faster than clean_text:

   >>> s = open('pg2600.txt', encoding='utf8').read()
   >>> len(s)
   3226622
   >>> from timeit import timeit
   >>> timeit(lambda:clean_text(s), number=1)
   0.39841552218422294
   >>> timeit(lambda:words(s), number=1)
   timeit(lambda:words(s), number=1)
   0.30522726010531187
   

9. In make_sure_path_exists, you catch all OSError exceptions and re-raise the ones you don't want:

   try:
       os.makedirs(path)
   except OSError as exception:
       if exception.errno != errno.EEXIST:
           raise
   

   In Python 3, you could catch FileExistsError:

   try:
       os.makedirs(path)
   except FileExistsError:
       pass
   

   But it would be even better to pass the keyword argument exist_ok=True to os.makedirs.

10. You don't need to write:

    make_sure_path_exists(os.getcwd() + "\\tables")
    

    because file operations are relative to the current directory. Just write:

    make_sure_path_exists("tables")
    

    This would also have the advantage of being portable to operating systems other than Microsoft Windows.

11. Similarly, instead of:

    os.getcwd() + "\\tables\\" + "bigram_ids.txt"
    

    write:

    os.path.join("tables", "bigram_ids.txt")
    

12. All those nested with open(...) as ...: statements push the actual code so far over to the right that it is unreadable in an 80-column window. One way to fix this would be to open them all in just one with statement:

    with open(os.path.join("tables", "bigram_ids.txt"), "w") as     bigram_id_out, \
         open(os.path.join("tables", "sentence_ids.txt"), "w") as sentence_id_out, \
         ...
    

    but I think it would be better just to keep it simple:

    bigram_id_out = open(os.path.join("tables", "bigram_ids.txt"), "w")
    sentence_id_out = open(os.path.join("tables", "sentence_ids.txt"), "w")
    ...
    

    Using open inside with is a convenience (that ensures that the file is closed promptly on exit of the with statement), not a necessity. Here the cost of the with statement (in reduced readability) is so high that it's not worth it. The files will be closed automatically in any case when the function returns and the names go out of scape.

13. In this comment:

    # create a variable "text_id" we'll use to assign a unique id to
    # each text we ingest
    text_id = 0
    

    the words "create a variable text_id we'll use to" are unnecessary. Any reader can see that you're initializing a variable called text_id. I would write:

    text_id = 0           # Unique id for the current text.
    

14. Here, you know that it's "super kludgy" but you do it anyway:

    # it's super kludgy, but add one last list object Nul, Nul to
    # authors_and_paths_in in case the last line is an author who only
    # exists once in the database
    authors_and_paths_in.append("Nul" + sep + "Nul")
    

    Python has a built-in function itertools.groupby for splitting an iterator into groups. So you can write:

    from itertools import groupby
    from operator import itemgetter
    
    authors_and_paths = (i.split(sep) for i in authors_and_paths_in)
    for author, group in groupby(authors_and_paths, itemgetter(0)):
        # set up for author here
        for i in group:
            path_to_author_text = ...