2
\$\begingroup\$

I have the written the following (crude) code to find the association strengths among the words in a given piece of text.

import re

## The first paragraph of Wikipedia's article on itself - you can try with other pieces of text with preferably more words (to produce more meaningful word pairs)
text = "Wikipedia was launched on January 15, 2001, by Jimmy Wales and Larry Sanger.[10] Sanger coined its name,[11][12] as a portmanteau of wiki[notes 3] and 'encyclopedia'. Initially an English-language encyclopedia, versions in other languages were quickly developed. With 5,748,461 articles,[notes 4] the English Wikipedia is the largest of the more than 290 Wikipedia encyclopedias. Overall, Wikipedia comprises more than 40 million articles in 301 different languages[14] and by February 2014 it had reached 18 billion page views and nearly 500 million unique visitors per month.[15] In 2005, Nature published a peer review comparing 42 science articles from Encyclopadia Britannica and Wikipedia and found that Wikipedia's level of accuracy approached that of Britannica.[16] Time magazine stated that the open-door policy of allowing anyone to edit had made Wikipedia the biggest and possibly the best encyclopedia in the world and it was testament to the vision of Jimmy Wales.[17] Wikipedia has been criticized for exhibiting systemic bias, for presenting a mixture of 'truths, half truths, and some falsehoods',[18] and for being subject to manipulation and spin in controversial topics.[19] In 2017, Facebook announced that it would help readers detect fake news by suitable links to Wikipedia articles. YouTube announced a similar plan in 2018."
text = re.sub("[\[].*?[\]]", "", text)     ## Remove brackets and anything inside it.
text=re.sub(r"[^a-zA-Z0-9.]+", ' ', text)  ## Remove special characters except spaces and dots
text=str(text).lower()                     ## Convert everything to lowercase
## Can add other preprocessing steps, depending on the input text, if needed.







from nltk.corpus import stopwords
import nltk

stop_words = stopwords.words('english')

desirable_tags = ['NN'] # We want only nouns - can also add 'NNP', 'NNS', 'NNPS' if needed, depending on the results

word_list = []

for sent in text.split('.'):
    for word in sent.split():
        '''
        Extract the unique, non-stopword nouns only
        '''
        if word not in word_list and word not in stop_words and nltk.pos_tag([word])[0][1] in desirable_tags:
            word_list.append(word)





'''
Construct the association matrix, where we count 2 words as being associated 
if they appear in the same sentence.

Later, I'm going to define associations more properly by introducing a 
window size (say, if 2 words seperated by at most 5 words in a sentence, 
then we consider them to be associated)
'''

import numpy as np
import pandas as pd

table = np.zeros((len(word_list),len(word_list)), dtype=int)

for sent in text.split('.'):
    for i in range(len(word_list)):
        for j in range(len(word_list)):
            if word_list[i] in sent and word_list[j] in sent:
                table[i,j]+=1

df = pd.DataFrame(table, columns=word_list, index=word_list)







# Count the number of occurrences of each word in word_list

all_words = pd.DataFrame(np.zeros((len(df), 2)), columns=['Word', 'Count'])
all_words.Word = df.index

for sent in text.split('.'):
    count=0
    for word in sent.split():
        if word in word_list:
            all_words.loc[all_words.Word==word,'Count'] += 1







# Sort the word pairs in decreasing order of their association strengths

df.values[np.triu_indices_from(df, 0)] = 0 # Make the upper triangle values 0

assoc_df = pd.DataFrame(columns=['Word 1', 'Word 2', 'Association Strength (Word 1 -> Word 2)'])
for row_word in df:
    for col_word in df:
        '''
        If Word1 occurs 10 times in the text, and Word1 & Word2 occur in the same sentence 3 times,
        the association strength of Word1 and Word2 is 3/10 - Please correct me if this is wrong.
        '''
        assoc_df = assoc_df.append({'Word 1': row_word, 'Word 2': col_word, 
                                        'Association Strength (Word 1 -> Word 2)': df[row_word][col_word]/all_words[all_words.Word==row_word]['Count'].values[0]}, ignore_index=True)

assoc_df.sort_values(by='Association Strength (Word 1 -> Word 2)', ascending=False)

This produces the word associations like so:

        Word 1          Word 2          Association Strength (Word 1 -> Word 2)
330     wiki            encyclopedia    3.0
895     encyclopadia    found           1.0
1317    anyone          edit            1.0
754     peer            science         1.0
755     peer            encyclopadia    1.0
756     peer            britannica      1.0
...
...
...

However, the code contains a lot of for loops which hampers its running time. Specially the last part (sort the word pairs in decreasing order of their association strengths) consumes a lot of time as it computes the association strengths of n^2 word pairs/combinations, where n is the number of words we are interested in (those in word_list in my code above).

So, the following are what I would like some help on:

  1. How do I vectorize the code, or otherwise make it more efficient?

  2. Instead of producing n^2 combinations/pairs of words in the last step, is there any way to prune some of them before producing them? I am going to prune some of the useless/meaningless pairs by inspection after they are produced anyway.

  3. Also, and I know this does not really fall into the purview of code review, but I would love to know if there's any mistake in my logic, specially when calculating the word association strengths.

\$\endgroup\$
  • \$\begingroup\$ @Ludisposed Oops, my bad. Added them. \$\endgroup\$ – Kristada673 Feb 26 at 9:05
3
\$\begingroup\$

Review

  • Styling

    1. Import should be at the top of the file
    2. Use a if __name__ == '__main__:' guard
    3. Split some functionality into function, keeping everything in the global namespace is considered bad form
  • Use str.translate for cleaning texts

    This should faster compared to regex substitution

    Secondly you can use string.punctuation which in is in the standard library, making your first code block:

    trans_table = str.maketrans('', '', string.punctuation.replace('.', ''))
    trans_text = text.translate(trans_table).lower()
    

    You'd still need to clean the wiki references [15]...etc from the text though

  • Why do you import nltk 2 times?

    Just import nltk once

  • Using set lookup is O(0)

    Instead of checking if a variable is in a list you should compare against a set, this will improve performance, see Python time complexity

    stop_words = set(nltk.corpus.stopwords.words('english'))
    
  • Use list comprehension

    List comprehension should be a bit faster compared to appending in a for loop, and it is considered Pythonic,

    Secondly you can pre-process the text to hold a list of sentences, instead of calculating it everytime

    word_list = set(
        word for sent in trans_text.split('.') for word in sent.split() 
        if word not in stop_words and nltk.pos_tag([word])[0][1] in desirable_tags
    )
    sentences = [
        set(sentence.split()) for sentence in trans_text.split('.')
    ]
    
  • Use enumerate if you need both the item and the index

    table = np.zeros((len(word_list), len(word_list)), dtype=int)
    for sent in sentences:
        for i, e in enumerate(word_list):
            for j, f in enumerate(word_list):
                if e in sent and f in sent:
                    table[i,j] += 1
    
  • Use collections.Counter() for counting words

    And you can create a dataframe from Counter in one go with

    count_words = pd.DataFrame.from_dict(Counter(word_list), orient='index').reset_index()
    

    But you don't need to convert it to a dataframe at all, since you can get the word count by just reading the Dictionary

    count_words = Counter(word_list)
    ...
    assoc_df = assoc_df.append({'Word 1': row_word, 
                                'Word 2': col_word, 
                                'Association Strength (Word 1 -> Word 2)': df[row_word][col_word]/count_words[row_word]}, 
                                ignore_index=True)
    

Note that I am not really into Pandas/Preprocessing so I might have missed a few things :)

\$\endgroup\$
  • \$\begingroup\$ I'll definitely try these suggestions. The biggest problem seems be in the last segment - all the other code blocks finish within a minute or two each, at max. But the last segment for calculating word pair association strengths, with a different piece of input text that produces 800 odd words in word_list, is going on running for the last 2 hours. So, that's the more urgent part. \$\endgroup\$ – Kristada673 Feb 26 at 9:55
  • \$\begingroup\$ I might take another stab at it when I have some time again. Or maybe someone else will pick that up. \$\endgroup\$ – Ludisposed Feb 26 at 10: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.