8
\$\begingroup\$

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))

Output: https://docs.google.com/spreadsheets/d/1jebMM6gZUMV0Ig6SPcveVYvccB6W9WBr_Yk8Zi2J72I/edit?usp=sharing

f - frequency, m - mi shows how strong collocation is, p -probability, n - number of times, t - text output is in csv formst

\$\endgroup\$
  • \$\begingroup\$ Something like this might benefit a lot from just seeing how to actually use this code. Could you edit it to include an example? \$\endgroup\$ – user9993 Mar 30 '16 at 9:12
  • \$\begingroup\$ You mean show the output of it? \$\endgroup\$ – Yan Mar 30 '16 at 9:16
  • \$\begingroup\$ Now you can see the output. \$\endgroup\$ – Yan Mar 30 '16 at 9:29
  • \$\begingroup\$ 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. \$\endgroup\$ – Yan Mar 30 '16 at 9:30
  • \$\begingroup\$ Welcome to CodeReeview.SE. Your indentation seems to be somewhat broken. \$\endgroup\$ – SylvainD Mar 30 '16 at 9:33
8
\$\begingroup\$

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

Do I have to say more about this ?

\$\endgroup\$
  • \$\begingroup\$ i will check it out as soon as possible, And will see how faster it is going to work! \$\endgroup\$ – Yan Mar 30 '16 at 15:07
  • \$\begingroup\$ 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 \$\endgroup\$ – Yan Mar 30 '16 at 15:44
  • \$\begingroup\$ gave error above. \$\endgroup\$ – Yan Mar 30 '16 at 15:45
  • \$\begingroup\$ 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. \$\endgroup\$ – SylvainD Mar 30 '16 at 16:04
  • \$\begingroup\$ sure will inform you! \$\endgroup\$ – Yan Mar 30 '16 at 16:15
2
\$\begingroup\$

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)
    return tokens


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))
\$\endgroup\$
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – SylvainD Mar 31 '16 at 8:02
  • \$\begingroup\$ Did you check if your code working because I've found two mistakes there? \$\endgroup\$ – Yan Mar 31 '16 at 8:27
  • \$\begingroup\$ @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. \$\endgroup\$ – Jared Goguen Mar 31 '16 at 8:31
  • \$\begingroup\$ for test data you can use any text file \$\endgroup\$ – Yan Mar 31 '16 at 8:34
  • \$\begingroup\$ 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 \$\endgroup\$ – Yan Mar 31 '16 at 8:34

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.