Splitting text into n-grams and analyzing statistics on them

I have made the algorithm that split text into n-grams (collocations) and it counts probabilities and other statistics of this collocations. When file is more then 50 megabytes it takes long time to count maybe some one will help to improve it.

import math
import re
import csv
from itertools import zip_longest
from datetime import datetime

def tokenize(input_file, encoding):
lst =[]
with open(input_file, 'r', encoding=encoding) as f:
for sent in f:
sent = sent.lower()
sent = re.sub("[A-z0-9\'\"\|\/\+\#\,\)$$\?\!\B\-\:\=\;\.\«\»\—\@]", '', sent) sent = re.findall('\w+', sent) for word in sent: lst.append(word) return lst def ngrams_split(lst, n): counts = dict() grams = [' '.join(lst[i:i+n]) for i in range(len(lst)-n)] for gram in grams: if gram not in counts: counts[gram] = 1 else: counts[gram] += 1 return counts def list_add(counts): ngrams = [] for key, val in counts.items(): ngrams.append((val, key)) return ngrams def gram_add(lst, n): ng = [] grams = [' '.join(lst[i:i+n]) for i in range(len(lst)-n)] for gram in grams: ng.append(gram) return ng def two_gram_count(input_file, encoding, n_filter, n): output_file = [] lst = tokenize(input_file, encoding) #tokenize n_words = len(lst) counts = ngrams_split(lst, n) #spliting into ngrams ngrams = list_add(counts) #ading ngrmas to list for key, val in ngrams: if int(key) >= n_filter: ngram_freq = math.log(key/n_words) num = key*n_words f1 = lst.count(val.split()[0]) f2 = lst.count(val.split()[1]) mi = math.pow(math.log(num/(f1*f2), 10), 2) ngram_prob = math.log(key/f1, 10) output_file.append((ngram_freq, mi, ngram_prob, key, val)) return output_file def three_gram_count(input_file, encoding, n_filter, n): output_file = [] lst = tokenize(input_file, encoding) #tokenize n_words = len(lst) counts = ngrams_split(lst, n) #spliting into ngrams ngrams = list_add(counts) #ading ngrmas to list ng = gram_add(lst, 2) for key, val in ngrams: if int(key) >= n_filter: ngram_freq = math.log(key/n_words, 10) num = key*n_words c2gram = ng.count(val.split()[0] + " " + val.split()[1]) f1 = lst.count(val.split()[0]) f2 = lst.count(val.split()[1]) f3 = lst.count(val.split()[2]) mi = math.pow(math.log(num/(f1*f2*f3), 10), 2) ngram_prob = math.log(key/c2gram, 10) output_file.append((ngram_freq, mi, ngram_prob, key, val)) return output_file def four_grams_count(input_file, encoding, n_filter, n): output_file = [] lst = tokenize(input_file, encoding) #tokenize n_words = len(lst) counts = ngrams_split(lst, n) #spliting into ngrams ngrams = list_add(counts) #ading ngrmas to list ng2 = gram_add(lst, 2) for key, val in ngrams: if int(key) >= n_filter: ngram_freq = math.log(key/n_words, 10) num = key*n_words c1gram = ng2.count(val.split()[0] + " " + val.split()[1]) c2gram = ng2.count(val.split()[1] + " " + val.split()[2]) c3gram = ng2.count(val.split()[2] + " " + val.split()[3]) f1 = lst.count(val.split()[0]) f2 = lst.count(val.split()[1]) f3 = lst.count(val.split()[2]) f4 = lst.count(val.split()[3]) mi = math.pow(math.log(num/(f1*f2*f3*f4), 10), 2) prob1 = c1gram/f1 prob2 = c2gram/f2 prob3 = c3gram/f3 ngram_prob = math.log(prob1, 10) + math.log(prob2, 10) + math.log(prob3, 10) output_file.append((ngram_freq, mi, ngram_prob, key, val)) return output_file def n_grams_stat(input_file, encoding, n_filter, n): output_file = [] if n == 2: for i in two_gram_count(input_file, encoding, n_filter, n): output_file.append(i) elif n == 3: for i in three_gram_count(input_file, encoding, n_filter, n): output_file.append(i) elif n == 4: for i in four_grams_count(input_file, encoding, n_filter, n): output_file.append(i) return output_file start_time = datetime.now() for a, b, c, d, e in n_grams_stat("/home/yan/PycharmProjects/vk/piidsluhano/men_pidsluhano.txt",'utf-8', n_filter=3, n=4): print(a, b, c, d, e) with open("/home/yan/PycharmProjects/vk/piidsluhano/men_4grams", 'dwwaa') as f: f.write(str(a) +", "+ str(b) + ', '+ str(c) + ", " + str(d) + ", " + str(e) + '\n ') end_time = datetime.now() print('Duration: {}'.format(end_time - start_time))  f - frequency, m - mi shows how strong collocation is, p -probability, n - number of times, t - text output is in csv formst • Something like this might benefit a lot from just seeing how to actually use this code. Could you edit it to include an example? Mar 30, 2016 at 9:12 • You mean show the output of it? – Yan Mar 30, 2016 at 9:16 • Now you can see the output. – Yan Mar 30, 2016 at 9:29 • If you want you can try some texts, but you need to change this line re.sub("[A-z0-9\'\"\|\/\+\#\,)(\?\!\B\-\:\=\;\.\«\»\—\@] because it takes a all Latin letters away. – Yan Mar 30, 2016 at 9:30 • Welcome to CodeReeview.SE. Your indentation seems to be somewhat broken. Mar 30, 2016 at 9:33 2 Answers Code organisation Your code seems to be splitted into small-ish functions which is good. However, there is something that could easily be improved : you could move your code actually doing something (by opposition to merely define things) behind an if __name__ == "__main__": guard. User interface Your code contains hardcoded file paths. Obviously, this doesn't work on my machine without changing the code. The right way to do this is probably to use command-line arguments to be able to provide the path for the input file and for the output file. Alternatively, you could get rid of input and/or output file, just read from standard input and write in standard output and assume that the user knows enough about redirection to use your script. Do not repeat yourself Your code contains a lot of duplicated code which makes it hard to read and/or to maintain. In your code, it may also make it less efficient than it could be because one may read and tokenize the file multiple times instead of only once. For instance, we could imagine providing the list of tokens to the xxx_grams_count functions instead of filename and encoding. This could make things more straightforward but also easier to test. Most of your functions do many things and do not respect the Single Responsability Principle. Variable names Your variables names are in general not very descriptive. lst for a list of tokens is not good especially because you handle multiple other lists, tokens seems to be a better idea. Also output_file for a list of frequencies is a terrible name : it is not even slightly related to file (except for the fact that the value returned might eventually be written in a file). output_tuples or output_freq or ngram_count might be slightly less confusing. You could probably find an even better name as you know more about the code than I do. Comments It is a good thing to have comments in your code but if the comments is just stating the obvious, it doesn't add any value while adding some noise. For instance, this comment lst = tokenize(input_file, encoding) #tokenize doesn't add anything. Also, it may be a good idea to add docstrings to your function describing their input/output/behavior. Useless list manipulation You are performing many useless list manipulations. In: def gram_add(lst, n): ng = [] grams = [' '.join(lst[i:i+n]) for i in range(len(lst)-n)] for gram in grams: ng.append(gram) return ng  you are creating a new list, iterating over each item of that list to add it to an other list that you can return. This could just be: def gram_add(lst, n): return [' '.join(lst[i:i+n]) for i in range(len(lst)-n)]  Pretty similarly, in : def n_grams_stat(input_file, encoding, n_filter, n): ngram_count = [] tokens = tokenize(input_file, encoding) if n == 2: for i in two_gram_count(tokens, n_filter, n): ngram_count.append(i) elif n == 3: for i in three_gram_count(tokens, n_filter, n): ngram_count.append(i) elif n == 4: for i in four_grams_count(tokens, n_filter, n): ngram_count.append(i) return ngram_count  you are getting a list, iterating over each item of that list to add it to an other list that you can return. This could be written: def n_grams_stat(input_file, encoding, n_filter, n): tokens = tokenize(input_file, encoding) if n == 2: return two_gram_count(tokens, n_filter, n) elif n == 3: return three_gram_count(tokens, n_filter, n) elif n == 4: return four_grams_count(tokens, n_filter, n) return []  List comprehension You seem to be aware of the existence of list comprehension but you haven't used them in a few places where it could be quite useful. For instance : def list_add(counts): ngrams = [] for key, val in counts.items(): ngrams.append((val, key)) return ngrams  could just be : def list_add(counts): return [(val, key) for key, val in counts.items()]  also this still has 3 problems: the name of the function seems pretty bad (we don't "add" anything to any list) and the name of the parameter seems just as bad (counts suggest a list of number, not a dictionnary; maybe dict_ would be a better name), the fact that this function can be simplified more. I'll explain the third point which will make the 2 first points irrelevant. What you are actually doing in the function is consuming a list (or a view depending on the Python version but it doesn't matter for you) of (key, val) pairs and returning a list of (val, key) pairs but at the end of the day, you don't really care about the order, you could just swap your variable names when you iterate on the result. Thus, changing : for key, val in ngrams: for for val, key in ngrams:, you could write : def list_add(dict_): return dict_.items()  which makes the function useless. Using the correct data structure There are 2 things that could be improved in the ngrams_split function: • it splits and it counts • the counting part could be improved using the correct data structure. You'll see that collections.Counter handle this task pretty well. We can rewrite ngrams_split so that it only splits and use Counter to count its return: def ngrams_split(lst, n): return [' '.join(lst[i:i+n]) for i in range(len(lst)-n)]  That you use like this : for val, key in Counter(ngrams_split(tokens, n)).items():  Then you can see that you have 2 pretty similar functions: def ngrams_split(lst, n): return [' '.join(lst[i:i+n]) for i in range(len(lst)-n)] def gram_add(lst, n): return [' '.join(lst[i:i+n]) for i in range(len(lst)-n)]  So you can remove gram_add. Variable names again Now, in all the places where key and val are used, it would be more precise to use count and ngram. Useless operations again Now that we have : if int(count) >= n_filter, it is more obvious that we are probably performing some conversion of an int to an int which is pointless. Useless repeated operations You are calling ngram.split() many times even when you know that ngram hasn't changed in the meantime. It would be clearer and more efficient to do this only once. I still have things to say (about duplicated code mostly) but in the meantime, here is my current version of the code : import math import re import csv from itertools import zip_longest from datetime import datetime from collections import Counter def tokenize(input_file, encoding): lst =[] with open(input_file, 'r', encoding=encoding) as f: for sent in f: sent = sent.lower() # Commented for personal reasons : sent = re.sub("[A-z0-9\'\"\|\/\+\#\,$$\(\?\!\B\-\:\=\;\.\Â«\Â»\--\@]", '', sent)
sent = re.findall('\w+', sent)
for word in sent:
lst.append(word)
return lst

def ngrams_split(lst, n):
return [' '.join(lst[i:i+n]) for i in range(len(lst)-n)]

def two_gram_count(tokens, n_filter, n):
ngram_count = []
n_words = len(tokens)
for ngram, count in Counter(ngrams_split(tokens, n)).items():
if count >= n_filter:
splitted_ngram = ngram.split()
ngram_freq = math.log(count/n_words)
num = count*n_words
f1 = tokens.count(splitted_ngram[0])
f2 = tokens.count(splitted_ngram[1])
mi = math.pow(math.log(num/(f1*f2), 10), 2)
ngram_prob = math.log(count/f1, 10)
ngram_count.append((ngram_freq, mi, ngram_prob, count, ngram))
return ngram_count

def three_gram_count(tokens, n_filter, n):
ngram_count = []
n_words = len(tokens)
ng = ngrams_split(tokens, 2)
for ngram, count in Counter(ngrams_split(tokens, n)).items():
if count >= n_filter:
splitted_ngram = ngram.split()
ngram_freq = math.log(count/n_words, 10)
num = count*n_words
c2gram = ng.count(splitted_ngram[0] + " " + splitted_ngram[1])
f1 = tokens.count(splitted_ngram[0])
f2 = tokens.count(splitted_ngram[1])
f3 = tokens.count(splitted_ngram[2])
mi = math.pow(math.log(num/(f1*f2*f3), 10), 2)
ngram_prob = math.log(count/c2gram, 10)
ngram_count.append((ngram_freq, mi, ngram_prob, count, ngram))
return ngram_count

def four_grams_count(tokens, n_filter, n):
ngram_count = []
n_words = len(tokens)
ng2 = ngrams_split(tokens, 2)
for ngram, count in Counter(ngrams_split(tokens, n)).items():
if count >= n_filter:
splitted_ngram = ngram.split()
ngram_freq = math.log(count/n_words, 10)
num = count*n_words
c1gram = ng2.count(splitted_ngram[0] + " " + splitted_ngram[1])
c2gram = ng2.count(splitted_ngram[1] + " " + splitted_ngram[2])
c3gram = ng2.count(splitted_ngram[2] + " " + splitted_ngram[3])
f1 = tokens.count(splitted_ngram[0])
f2 = tokens.count(splitted_ngram[1])
f3 = tokens.count(splitted_ngram[2])
f4 = tokens.count(splitted_ngram[3])
mi = math.pow(math.log(num/(f1*f2*f3*f4), 10), 2)
prob1 = c1gram/f1
prob2 = c2gram/f2
prob3 = c3gram/f3
ngram_prob = math.log(prob1, 10) + math.log(prob2, 10) +    math.log(prob3, 10)
ngram_count.append((ngram_freq, mi, ngram_prob, count, ngram))
return ngram_count

def n_grams_stat(input_file, encoding, n_filter, n):
tokens = tokenize(input_file, encoding)
if n == 2:
return two_gram_count(tokens, n_filter, n)
elif n == 3:
return three_gram_count(tokens, n_filter, n)
elif n == 4:
return four_grams_count(tokens, n_filter, n)
return []

if __name__ == "__main__":
start_time = datetime.now()
s = n_grams_stat("/home/josay/Geekage/review/ngram2.py",'utf-8', n_filter=3, n=4)
for a, b, c, d, e in s:
print(a, b, c, d, e)
end_time = datetime.now()
print('Duration: {}'.format(end_time - start_time))


Edit: More comment :-)

Useless imports

• i will check it out as soon as possible, And will see how faster it is going to work!
– Yan
Mar 30, 2016 at 15:07
• Traceback (most recent call last): File "/home/yan/PycharmProjects/nltk/n.py", line 97, in <module> s = n_grams_stat("/home/yan/woman_final.txt", encoding = "utf-8", n_filter=1, n=2) File "/home/yan/PycharmProjects/nltk/n.py", line 87, in n_grams_stat return two_gram_count(tokens, n_filter, n) File "/home/yan/PycharmProjects/nltk/n.py", line 33, in two_gram_count f2 = tokens.count(splitted_ngram[1]) IndexError: list index out of range
– Yan
Mar 30, 2016 at 15:44
• gave error above.
– Yan
Mar 30, 2016 at 15:45
• Pretty weird. Seems to work for me. In any case, the point of my code review was more the ideas I've used than the resulting code. I think I've detailled the steps well enough so that you can do the same think from your code and see when it starts going wrong. I'd be curious to see which change causes the failure. Mar 30, 2016 at 16:04
• sure will inform you!
– Yan
Mar 30, 2016 at 16:15

The biggest improvement you could make is to generalize the two-gram, three-gram, and four-gram functions, into a single n-gram function. This can be done with using lists instead of manually assigning c1gram, c2gram, and so on.

def n_grams_count(tokens, n_filter, n):
ngram_count = []
word_count = len(tokens)
ng2 = ngrams_split(tokens, 2)
for ngram, count in Counter(ngrams_split(tokens, n)).items():
if count >= n_filter:
split = ngram.split()
ngram_freq = math.log(count/word_count, 10)
num = count*word_count

cgrams = [ng2.count(split[i] + ' ' + split[i+1]) for i in range(n-1)]
freqs = [tokens.count(word) for word in split]
product = reduce(lambda x, y: x*y, freqs)

mi = math.pow(math.log(num/(product), 10), 2)

probs = [cgram/freq for cgram, freq in zip(cgrams, freqs)]
ngram_prob = sum(math.log(prob, 10) for prob in probs)
ngram_count.append((ngram_freq, mi, ngram_prob, count, ngram))

return ngram_count


I don't really understand what this function is doing, but it seems messy and could likely be improved.

Then your n_grams_stat function can be greatly simplified.

def n_grams_stat(input_file, encoding, n_filter, n):
tokens = tokenize(input_file, encoding)
return n_grams_count(tokens, n_filter, n)


With this one change, you've gotten rid of half of your code and now can work with five-grams, six-grams, and so on.

Making some small other changes, many of which are noted above, cleans up the code pretty well.

import math, re, csv

from itertools import zip_longest
from datetime import datetime
from collections import Counter
from functools import reduce

def tokenize(input_file, encoding):
tokens = []
with open(input_file, 'r', encoding=encoding) as f:
for line in f:
words = re.findall('\w+', line.lower())
tokens.extend(words)

def chunk_list(lst, n):
return [tuple(lst[i:i+n]) for i in range(len(lst)-n)]

def count_ngrams(tokens, n_filter, n):
ngram_counts = []
word_count = len(tokens)
two_grams = chunk_list(tokens, 2)

for ngram, count in Counter(chunk_list(tokens, n)).items():
if count >= n_filter:
ngram_freq = math.log(count/word_count, 10)
num = count*word_count

cgrams = [two_grams.count((ngram[i], ngram[i+1])) for i in range(n-1)]
freqs = [tokens.count(word) for word in ngram]
product = reduce(lambda x, y: x*y, freqs)

mi = math.pow(math.log(num/(product), 10), 2)

probs = [cgram/freq for cgram, freq in zip(cgrams, freqs)]
ngram_prob = sum(math.log(prob, 10) for prob in probs)
ngram_counts.append((ngram_freq, mi, ngram_prob, count, ngram))

return ngram_counts

def ngram_stats(input_file, encoding, n_filter, n):
tokens = tokenize(input_file, encoding)
return count_ngrams(tokens, n_filter, n)

if __name__ == '__main__':
start_time = datetime.now()
s = ngram_stats('/home/josay/Geekage/review/ngram2.py','utf-8', n_filter=3, n=4)
for tup in s:
print(*tup)
print('Duration: {}'.format(datetime.now() - start_time))

• Excellent answer handling the part of the review I had no time to perform/test. Your final code shows very interesting points that probably deserve to be explained : you got rid of the join/split operations, you used extend instead of multiple append` Mar 31, 2016 at 8:02
• Did you check if your code working because I've found two mistakes there?
– Yan
Mar 31, 2016 at 8:27
• @Yan I have not (mainly because I don't have test data). Hopefully, the mistakes are minimal enough that you are able to troubleshoot them yourself, but let me know what I need to correct, or if there is anything that just doesn't work. A good amount of renaming was done, which I'd assume is the issue. Mar 31, 2016 at 8:31
• for test data you can use any text file
– Yan
Mar 31, 2016 at 8:34
• File "/home/yan/PycharmProjects/nltk/n.py", line 26, in count_ngrams for ngram, count in Counter(chunk_list(tokens, n)).items(): File "/usr/lib/python3.4/collections/__init__.py", line 475, in init self.update(*args, **kwds) File "/usr/lib/python3.4/collections/__init__.py", line 562, in update _count_elements(self, iterable) TypeError: unhashable type: 'list
– Yan
Mar 31, 2016 at 8:34