7
\$\begingroup\$

I wrote a script to calculate document distance. It seems working but I couldn't be sure. (I tried for the small strings and it seems working) Also I am not sure that its fast enough for large texts.

Here is the Document Distance formula:

document distance forumla

The frequency is the number of occurrences for each object. Such as for "D1: be or not to be" the frequency will be freq$$(D_1) = {be=2, not=1, or=1, to=2}$$ and $$||D_1|| = \sqrt{2^2 + 1^2 + 1^2 + 2^2}$$

from math import sqrt
from string import ascii_lowercase

alphanumerics = ascii_lowercase + "0123456789"

file1 = open("document1.txt", "r")
file2 = open("document2.txt", "r")
print(file1)

document1 = ""
for line in file1:
    document1 += line + ""


document2 = ""
for line in file2:
    document2 += line + ""

if document1 == "":
    print("---  The document1.txt file is empty! ---")
    raise ValueError
elif document2 == "":
    print("---  The document2.txt file is empty!! ---")
    raise ValueError

print(document1, document2)

def word_processor(document):
    '''returns an array that only contains the words in the text'''
    doc_word = []
    word = ""
    count_space = 0
    for char in document.lower():
        if char in alphanumerics:
            word += char
            count_space = 0
        elif char == " " and count_space == 0:
            doc_word.append(word)
            word = ""
            count_space += 1
    doc_word.append(word)
    return doc_word


doc1_words = word_processor(document1) 
doc2_words = word_processor(document2)

dot_product = 0
doc1_word_freq = {i: doc1_words.count(i)
                for i in doc1_words}  # the doc1 vector
doc2_word_freq = {i: doc2_words.count(i)
                for i in doc2_words}  # the doc2 vector
for key, value in doc1_word_freq.items():
    if key in doc2_word_freq.keys():
        dot_product += doc2_word_freq[key] * value # the dot product of the two doc vectors

doc1_mag = sqrt(sum([value**2 for value in doc1_word_freq.values()])) # the magnitude of the each document
doc2_mag = sqrt(sum([value**2 for value in doc2_word_freq.values()]))

similarity = dot_product / (doc1_mag * doc2_mag) * 100 
print("The similarity between 2 document is", similarity, "percent")

Any ideas ?

I did not use the acos function since I don't think I need it.

\$\endgroup\$
  • 1
    \$\begingroup\$ Take a look at ocw.mit.edu/courses/electrical-engineering-and-computer-science/… -> Unit 1 - Introduction - 2 - Lecture code (ZIP). He has a variety of 8 different py files solving your same task but the first version takes 228 seconds and the most efficient one 0.2 seconds to process two 1 MB-ish files. \$\endgroup\$ – JnxF Aug 21 at 23:05
  • 2
    \$\begingroup\$ You should explain in more detail what "document distance" means in your post. It's an important part of the review so we can know what the code is supposed to do. \$\endgroup\$ – IEatBagels Aug 22 at 17:59
  • 1
    \$\begingroup\$ @IEatBagels I edited my post \$\endgroup\$ – Reign Aug 22 at 22:04
  • \$\begingroup\$ You've tried it with smaller strings, but what's keeping you from testing with larger strings as well? \$\endgroup\$ – Mast Aug 23 at 5:41
5
\$\begingroup\$

Most of your code can be greatly reduced.

Doing string addition is often a bad idea in Python, especially if you are doing it in a loop. Also note that a + "" == a for any string a. I would replace your mix of global code and the word_processor function with this short function:

import string

WHITELIST = set(string.ascii_letters + string.digits + string.whitespace)

def get_words(file_name):
    with open(file_name) as f:
        for line in f:
            line = "".join(c for c in line.casefold() if c in WHITELIST)
            yield from line.split()

This filters each line of the file to only contain ASCII letters and whitespace and splits it by whitespace afterwards (the default behavior of str.split). The yield from effectively flattens the output into a stream of words (the whole function is a generator, so you can consume the output one at a time without keeping the whole list in memory). It also uses the with keyword to ensure your files are closed, even in the event of an exception interrupting the program. I used str.casefold instead of str.lower, as recommended by @AJNeufeld in the comments.

You should put the actual code into a function as well. I would call it similarity, since it does not actually measure distance, but similarity (from 0 to 100). For this you can use collections.Counter instead of using list.count repeatedly (each of which is \$\mathcal{O}(n)\$).

from collections import Counter
from math import sqrt

def similarity(words1, words2):
    words1, words2 = Counter(words1), Counter(words2)
    dot = sum(words1[k] * words2[k] for k in words1.keys() & words2.keys())
    norm1 = sqrt(sum(v**2 for v in words1.values()))
    norm2 = sqrt(sum(v**2 for v in words2.values()))
    return dot / (norm1 * norm2)

Here I used the fact that Counter can take any iterable (like the output of get_words) and counts how often each item occurs (it returns a kind of dictionary). Also, dictionary keys behave like sets, so we can do a set intersection so we don't have to check for every key if it is also in the second words counter. I would also leave scaling the similarity to the caller.

Use it within a if __name__ == "__main__": guard to allow importing from the module. You might want to add a simple CLI interface with sys.argv (or do it properly and use argparse if you want more functionality). Throw in a f-string to make formatting the output to the user easier (and make it a percent with not too many digits shown).

import sys

if __name__ == "__main__":
    file1, file2 = sys.argv[1:3]
    sim = similarity(get_words(file1), get_words(file2))
    print(f"Similarity of {file1} and {file2}: {sim:.2%}")

Usage:

python3 similarity.py file.txt file_old.txt
# Similarity of file.txt and file_old.txt: 92.19%

For these two small files (21KiB), your code takes 0.3s, whereas my code only takes 0.05s on my machine.

\$\endgroup\$
  • \$\begingroup\$ Your first code Its kind of hard for me to understand (the syntax), is it works even when theres two (or more) spaces or commas between the spaces such as some grammer errors etc ? For instance I need to, buy a headphone. I think that split will ot work in this case ? \$\endgroup\$ – Reign Aug 22 at 22:13
  • 1
    \$\begingroup\$ I liked the Counter and casefold method thanks a lot for that. \$\endgroup\$ – Reign Aug 22 at 22:19
  • \$\begingroup\$ If we assume that each word is seperated by space its more logical to use split. But if its not how can we use split ? Thats why I have count_space = 0. But I am sure that there can be found some more clever way to do that \$\endgroup\$ – Reign Aug 22 at 22:21
  • 2
    \$\begingroup\$ @Reign Well, if in doubt, try it ;) With line = "I need to, buy a headphone\n", "".join(filter(WHITELIST.__contains__, line.casefold())).split() returns ['i', 'need', 'to', 'buy', 'a', 'headphone'], which is the correct interpretation, as far as I can tell. One error that will mess it up a bit is missing spaces, i.e. foo,bar will be interpreted as the word foobar, because there is no whitespace left after the filtering. \$\endgroup\$ – Graipher Aug 22 at 22:21
  • 1
    \$\begingroup\$ @Reign It splits on any amount of whitespace, not only spaces. So extra spaces are fine, missing spaces not so much. But I guess your code also cannot deal with missing spaces. I would say no code can, because there are ambiguous words, which are made up of multiple other words. \$\endgroup\$ – Graipher Aug 22 at 22:22
1
\$\begingroup\$

This bit of your code that is trying to vectorize text into count vector

doc2_words = word_processor(document2)

doc1_word_freq = {i: doc1_words.count(i)
                for i in doc1_words}  # the doc1 vector
doc2_word_freq = {i: doc2_words.count(i)
                for i in doc2_words}  # the doc2 vector

can be replaced by scikit-learn's CountVectorizer

vectorizer=sklearn.feature_extraction.text.CountVectorizer()
vectorizer.fit([document1, document2])
doc1_word_freq = vectorizer.transform([document1])
doc2_word_freq = vectorizer.transform([document2])

This can be loaded directly from files with vectorizer=sklearn.feature_extraction.text.CountVectorizer(content='file')

For even large text I would use Keras keras.preprocessing.text.Tokenizer

and then this bit of the code

for key, value in doc1_word_freq.items():
    if key in doc2_word_freq.keys():
        dot_product += doc2_word_freq[key] * value # the dot product of the two doc vectors

doc1_mag = sqrt(sum([value**2 for value in doc1_word_freq.values()])) # the magnitude of the each document
doc2_mag = sqrt(sum([value**2 for value in doc2_word_freq.values()]))

similarity = dot_product / (doc1_mag * doc2_mag) * 100 
print("The similarity between 2 document is", similarity, "percent")

is recommended to use Numpy or even Scikit-learn for matrix operation

similarity = sklearn.metrics.pairwise.cosine_similarity(doc1_word_freq, doc2_word_freq)
\$\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.