6
\$\begingroup\$

I have an NLTK parsing function that I am using to parse a ~2GB text file of a TREC dataset. The goal for this dataset is tokenize the entire collection, perform some calculations (such as calculating TF-IDF weights, etc), and then to run some queries against our collection to use cosine similarity and return the best results.

As it stands, my program works but takes well over an hour (typically between 44-61 minutes) to run. The timing is broken down as follows:

TOTAL TIME TO COMPLETE: 4487.930628299713
TIME TO GRAB SORTED COSINE SIMS: 35.24157094955444
TIME TO CREATE TFIDF BY DOC: 57.06743311882019
TIME TO CREATE IDF LOOKUP: 0.5097501277923584
TIME TO CREATE INVERTED INDEX: 2.5217013359069824
TIME TO TOKENIZE: 4392.5711488723755

So obviously, the tokenization is accounting for ~98% of the time. I am looking for a way to speed that up.

The tokenization code is below:

def get_input(filepath):
    f = open(filepath, 'r')
    content = f.read()
    return content

def remove_nums(arr): 
    pattern = '[0-9]'  
    arr = [re.sub(pattern, '', i) for i in arr]    
    return arr


def get_words(para):   
    stop_words = list(stopwords.words('english'))    
    words = RegexpTokenizer(r'\w+')
    lower = [word.lower() for word in words.tokenize(para)]
    nopunctuation = [nopunc.translate(str.maketrans('', '', string.punctuation)) for nopunc in lower]
    no_integers = remove_nums(nopunctuation)
    dirty_tokens = [data for data in no_integers if data not in stop_words]
    tokens = [data for data in dirty_tokens if data.strip()]

    return tokens

def driver(file):
    #t1 is the start of the file
    t1 = time.time()

    myfile = get_input(file)
    p = r'<P ID=\d+>.*?</P>'       
    paras = RegexpTokenizer(p)   
    document_frequency = collections.Counter()   
    collection_frequency = collections.Counter()   
    all_lists = []    
    currWordCount = 0   
    currList = [] 
    currDocList = []
    all_doc_lists = []
    num_paragraphs = len(paras.tokenize(myfile))  


    print()
    print(" NOW BEGINNING TOKENIZATION ")
    print()
    for para in paras.tokenize(myfile):             
        group_para_id = re.match("<P ID=(\d+)>", para)
        para_id = group_para_id.group(1)       
        tokens = get_words(para)
        tokens = list(set(tokens))     
        collection_frequency.update(tokens)      
        document_frequency.update(set(tokens))       
        para = para.translate(str.maketrans('', '', string.punctuation))     
        currPara = para.lower().split()      
        for token in tokens:          
            currWordCount = currPara.count(token)          
            currList = [token, tuple([para_id, currWordCount])]          
            all_lists.append(currList)

            currDocList = [para_id, tuple([token, currWordCount])]
            all_doc_lists.append(currDocList)

    d = {}
    termfreq_by_doc = {}    
    for key, new_value in all_lists:       
        values = d.setdefault(key, [])       
        values.append(new_value)

    for key, new_value in all_doc_lists:
        values = termfreq_by_doc.setdefault(key, [])
        values.append(new_value)

# t2 is after the tokenization
    t2 = time.time()

    inverted_index = {word:(document_frequency[word], d[word]) for word in d}

    # t3 is after creating the index
    t3 = time.time()
    print("Number of Paragraphs Processed: {}".format(num_paragraphs))
    print("Number of Unique Words (Vocabulary Size): {}".format(vocabulary_size(document_frequency)))
    print("Number of Total Words (Collection Size): {}".format(sum(collection_frequency.values())))

    """
        1. First, create a lookup hash of the IDFs for each term in the dictionary.
        2. Then, compute the tfxidf for each term in every document.
        3. Then, calculate the lengths of each document.
        4. Now you can process a query.
    """    
    idf_lookup = create_idf_lookup(inverted_index, num_paragraphs)
    #t4 is after creating the lookup
    t4 = time.time()
    tfidf_by_doc = {a:[(c, int(idf_lookup[c]*d)) for c, d in b] for a, b in termfreq_by_doc.items()}
    #t5 is after creating the tfidf by doc
    t5 = time.time()
    lengths = calculateLength(tfidf_by_doc, idf_lookup)    

     #Now, process the query:
     # Read in the query
    query_results = process_query(local_file_path)
    # Create tfxidf 
    query_vector = {a:[(c, int(idf_lookup[c]*d)) for c, d in b] for a, b in query_results.items()}

    # Grab length
    queryLengthDict = calculateLength(query_vector, idf_lookup)
    queryLength = next(iter(queryLengthDict.values()))

    result = {}
    for k, v in tfidf_by_doc.items():
        for se in query_vector.values():
            result[k] = dot_prod(dict(v), dict(se))

    print()

    cosine_sims = {k:v / (lengths[k] * queryLength) if lengths[k] != 0 else 0 for k, v in result.items()}   
    #https://stackoverflow.com/questions/613183/how-do-i-sort-a-dictionary-by-value
    sorted_sims = sort_dictionary(cosine_sims)
    top_100 = take(100, sorted_sims)
    #t6 is grabbing the sorted sims
    t6 = time.time()
    print()
    print("Cosine Sims")
    print(top_100)

    t7 = time.time()
    print()
    print()

    print("TOTAL TIME TO COMPLETE: {}".format(t7-t1))
    print("TIME TO GRAB SORTED COSINE SIMS: {}".format(t6-t5))
    print("TIME TO CREATE TFIDF BY DOC: {}".format(t5-t4))
    print("TIME TO CREATE IDF LOOKUP: {}".format(t4-t3))
    print("TIME TO CREATE INVERTED INDEX: {}".format(t3-t2))
    print("TIME TO TOKENIZE: {}".format(t2-t1))

    print("PROGRAM COMPLETED")

I am pretty new to optimization, and am looking for some feedback. I did see this post which condemns a lot of my list comprehensions as "evil", but I can't think of a way around what I am doing.

The code is not well commented, so if for some reason it is not understandable, that is okay. I see other questions on this forum re: speeding up NLTK tokenization without a lot of feedback, so I am hoping for a positive thread about tokenization optimization programming practices.

Here is an example (~a little bit of one document in the overall corpus). There are about ~58,000 scientific articles (I measure 57,982).

<P ID=2630932>
Background
Adrenal cortex oncocytic carcinoma (AOC) represents an exceptional pathological entity, since only 22 cases have been documented in the literature so far.
Case presentation
Our case concerns a 54-year-old man with past medical history of right adrenal excision with partial hepatectomy, due to an adrenocortical carcinoma. The patient was admitted in our hospital to undergo surgical resection of a left lung mass newly detected on chest Computed Tomography scan. The histological and immunohistochemical study revealed a metastatic AOC. Although the patient was given mitotane orally in adjuvant basis, he experienced relapse with multiple metastases in the thorax twice in the next year and was treated with consecutive resections. Two and a half years later, a right hip joint metastasis was found and concurrent chemoradiation was given. Finally, approximately five years post disease onset, the patient died due to massive metastatic disease. A thorough review of AOC and particularly all diagnostic difficulties are extensively stated.
Conclusion
Histological classification of adrenocortical oncocytic tumours has been so far a matter of debate. There is no officially established histological scoring system regarding these rare neoplasms and therefore many diagnostic difficulties occur for pathologists.
Background
Hamperl introduced the term "oncocyte" in 1931 referring to a cell with abundant, granular, eosinophilic cytoplasm []. Electron microscopic studies revealed that this granularity was due to mitochondria accumulation in the oncocyte cytoplasm []. Neoplasms composed predominantly or exclusively of this kind of cells are called "oncocytic" []. Such tumours have been described in the overwhelming majority of organs: kidney, thyroid and pituitary gland, salivary, adrenal, parathyroid and lacrimal glands, paraganglia, respiratory tract, paranasal sinuses and pleura, liver, pancreatobiliary system, stomach, colon and rectum, central nervous system, female and male genital tracts, skin and soft tissues [-]. Adrenocortical oncocytic neoplasms (AONs) represent unusual lesions and three histological categories are included: oncocytoma (AO), oncocytic neoplasm of uncertain malignant potential (AONUMP) and oncocytic carcinoma (AOC) []. In our study, we add to the 22 cases found in the literature a new AOC with peculiar clinical presentation [-].
Case presentation
A 54-year-old man was admitted in the Thoracic and Vascular Surgery Department of our hospital with a 2 cm mass at the upper lobe of the left lung detected on Computed Tomography (CT) scan to undergo complete surgical resection. He had a past medical history of adrenocortical carcinoma (AC) treated surgically with right adrenalectomy and partial hepatectomy en block 2 years ago (Figure ). He was a mild 3 pack year smoker and a moderate drinker (1/2 kgr wine/day).
 Figure 1 Abdominal MRI showing the hepatic invasion, which was submitted to en block resection with the right adrenal .
 Overall physical examination showed neither specific abnormality, nor any signs of endocrinopathy. All laboratory tests including cortisol, 17-ketosteroids and 17-hydrocorticosteroids serum levels and dexamethasone test, full blood count and complete biochemical hepatic plus renal function tests were in normal rates. The patient was subjected to wedge resection. Histological examination revealed a tumour with an oxyphilic cell population, moderate nuclear atypia, diffuse, rosette-like and papillary growth pattern and focal necroses (Figure ). A number of 4 mitotic figures/50 high power fields (HPFs) were documented. The proliferative index Ki-67 (MIB-1, 1:50, DAKO) was in a value range of 1020% and p53 oncoprotein (DO-7, 1:20, DAKO) was weakly expressed in a few cells. Immunohistochemical examination revealed positivity for Vimentin (V9, 1:2000, DAKO), Melan-A (A103, 1:40, DAKO), Calretinin with a fried-egg-like specific staining pattern (Rabbit anti-human polyclonal antibody, 1:150, DAKO) and Synaptophysin (SY38, 1:20, DAKO). Both Cytokeratins CK8,18 (UCD/PR 10.11, 1:80, ZYMED) and AE1/AE3 (MNF116, 1:100, DAKO) showed a dot-like paranuclear expression. Inhibin-a (R1, 1:40, SEROTEC) and CD56 (123C3, 1:50, ZYMED) were *expressed focally (Figures and ). CK7 (OV-TL 12/30, 1:60, DAKO), CK20 (K S 20.8, 1:20, DAKO), EMA (E29, 1:50, DAKO), CEAm (12-140-10, 1:50, NOVOCASTRA), CEAp (Rabbit anti-human polyclonal antibody, 1:4000, DAKO), TTF-1 (8G7G3/1 1:40, ZYMED), Chromogranin (DAK-A3, 1:20, DAKO) and S-100 (Rabbit anti-human polyclonal antibody, 1:1000, DAKO) were negative. Based on the morphological and immunohistochemical features of the neoplasm and the patient's past medical history, other oncocytic tumours were excluded and the diagnosis of a metastatic AOC was supported. Mitotane oral medication was given in adjuvant setting (2 g/d).*
...
</P>
\$\endgroup\$
  • \$\begingroup\$ Is the document XML? If so, can you show a closing tag in your example? \$\endgroup\$ – Reinderien Oct 9 at 1:09
  • \$\begingroup\$ It is not XML, it is SGML. Closing tag is simply </P>, and so the regex defines an article (since the entire corpus is a large body of many scientific articles) as everything within the tag. \$\endgroup\$ – Jerry M. Oct 9 at 1:12
  • \$\begingroup\$ Please show more of the code, particularly get_input. \$\endgroup\$ – Reinderien Oct 9 at 1:17
  • \$\begingroup\$ More code posted. Majority of which takes less than ~2 minutes to complete. \$\endgroup\$ – Jerry M. Oct 9 at 1:20
5
\$\begingroup\$

Regex compilation

If performance is a concern, this:

arr = [re.sub(pattern, '', i) for i in arr]

is a problem. You're re-compiling your regex on every function call - and every loop iteration! Instead, move the regex to a re.compile()d symbol outside of the function.

The same applies to re.match("<P ID=(\d+)>", para). In other words, you should be issuing something like

group_para_re = re.compile(r"<P ID=(\d+)>")

outside of the loop, and then

group_para_id = group_para_re.match(para)

inside the loop.

Premature generator materialization

That same line has another problem - you're forcing the return value to be a list. Looking at your no_integers usage, you just iterate over it again, so there's no value to holding onto the entire result in memory. Instead, keep it as a generator - replace your brackets with parentheses.

The same thing applies to nopunctuation.

Set membership

stop_words should not be a list - it should be a set. Read about its performance here. Lookup is average O(1), instead of O(n) for a list.

Variable names

nopunctuation should be no_punctuation.

\$\endgroup\$
  • \$\begingroup\$ I copied segments of the overall code body over, please allow me to edit. For example, get_words returns tokens and driver is parseable, I just copied it funky. \$\endgroup\$ – Jerry M. Oct 9 at 1:08
  • \$\begingroup\$ Funkiness fixed! Let me know if this looks like it makes more sense now... \$\endgroup\$ – Jerry M. Oct 9 at 1:11
  • \$\begingroup\$ Today is my not day...if you can't tell, I'm frazzled. Thanks for the catch. \$\endgroup\$ – Jerry M. Oct 9 at 1:13
  • \$\begingroup\$ The same applies to re.match("<P ID=(\d+)>", para). The goal of that line is to figure out the current document ID being parsed, so I can capture that for metric evaluation later on. How can I compile the regular expression outside of the loop to be used to capture the ID inside of the loop? \$\endgroup\$ – Jerry M. Oct 9 at 1:21
  • 1
    \$\begingroup\$ As an update -- this showed about a 10 minute improvement in time! Which is good. Thanks. \$\endgroup\$ – Jerry M. Oct 9 at 12:28
1
\$\begingroup\$

Not a code reviewer, your code looks good though.

Your regular expression can be slightly optimized for edge cases. For instance,

(?i)<p\s+id=[0-9]+\s*>(.+?)</p>

or,

(?i)<p\s+id=[0-9]+\s*>.+?</p>

with i modifier would safely cover some edge cases, if you would have had any.

Demo 1

  • [0-9] might be, not very sure, slightly more efficient than \d construct.
  • (.+?) is very very slightly more efficient than (.*?).

If your text content in the p tag for sure does not have any <, then we would safely simplify our expression to:

(?i)<p\s+id=[0-9]+\s*>([^<]+)</p> 

or

(?i)<p\s+id=[0-9]+\s*>[^<]+</p> 

which are much faster than the previous expressions because of [^<]+.

Demo 2


Demo

If you wish to simplify/modify/explore the expression, it's been explained on the top right panel of regex101.com. If you'd like, you can also watch in this link, how it would match against some sample inputs.


RegEx Circuit

jex.im visualizes regular expressions:

enter image description here

Test

import re

regex = r'(?i)<p\s+id=[0-9]+\s*>([^<]+)<\/p>'
string = '''
<P 
ID=2630932>
Background 
Adrenal cortex oncocytic carcinoma (AOC) represents an exceptional pathological entity, since only 22 cases have been documented in the literature so far.
</P>

<P  ID=2630932>
Background
Adrenal cortex oncocytic carcinoma (AOC) represents an exceptional pathological entity, since only 22 cases have been documented in the literature so far.
</P>

<P  ID=2630932 >
Background
Adrenal cortex oncocytic carcinoma (AOC) represents an exceptional pathological entity, since only 22 cases have been documented in the literature so far.
</P>

'''

print(re.findall(regex, string, re.DOTALL))

Output

['\nBackground \nAdrenal cortex oncocytic carcinoma (AOC) represents an exceptional pathological entity, since only 22 cases have been documented in the literature so far.\n', '\nBackground\nAdrenal cortex oncocytic carcinoma (AOC) represents an exceptional pathological entity, since only 22 cases have been documented in the literature so far.\n', '\nBackground\nAdrenal cortex oncocytic carcinoma (AOC) represents an exceptional pathological entity, since only 22 cases have been documented in the literature so far.\n']


You can also remove the capturing groups if your code doesn't need those.

\$\endgroup\$

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.