Python LCS dynamic programming implementation

main.py

"""
Project: A plagiarism detection tool based on the LCS algorithm

optional arguments:
  -h, --help            show this help message and exit
  -p file file, --parse file file
                        Compare two files
  -t dirname, --tabular dirname
                        Produce a table for each distinct .txt files

"""
from collections import defaultdict, namedtuple
from itertools import product
import string
import argparse
import sys
import os


def lcs(x, y):
    """
    A function which calculates the longest common substring of X and Y
    
    Args:
        X - The first string.
        Y - The second string.
        
    Returns:
        A table containing the length of the longest common substring and a move.
    """
    cell = namedtuple("cell", "len move")
    matrix = defaultdict(lambda: cell(0, False))

    for (i, x), (j, y) in product(enumerate(x), enumerate(y)):
        if x == y:
            entry = cell(matrix[(j - 1, i - 1)].len + 1, "W")
        elif matrix[(j, i - 1)].len < matrix[(j - 1, i)].len:
            entry = cell(matrix[(j - 1, i)].len, "^")
        else:
            entry = cell(matrix[(j, i - 1)].len, "<")
        matrix[(j, i)] = entry

    return matrix


def lcs_string(matrix, text, i, j):
    """
    It computes and longest common substring from a table.

    Args:
        matrix - The table which should contain the lengths and moves. See lcs()
        text - The first string that has been used in lcs()
        i - The length of the first string minus one.
        j - The length of the second string minus two.
    
    Returns:
        The longest common substring as a string.
    """
    lst = list()

    for move in iter(lambda: matrix[(j, i)].move, False):  # Make an iterator till you found False
        if move == 'W':
            lst.append(text[i])
            i -= 1
            j -= 1
        elif move == '^':
            j -= 1
        elif move == '<':
            i -= 1

    lst.reverse()
    return lst


def clean_word(word):
    """
    Removes all non-letter characters from a word.
    
    Returns:
        A clean word.
    """
    new_word = (character for character in word if character in string.ascii_letters)
    return "".join(new_word)


def clean_text(text):
    """
    Takes a text and removes all whitespaces and characters which are not part of the ascii letter set.
    """
    words = text.split()  # Remove whitespace
    cleaned_text = [clean_word(w) for w in words]
    # cleaned_text =[''.join(character for character in w if character in string.ascii_letters) for w in text.split()]

    return list(cleaned_text)


def load_files(first_file, second_file):
    """
    Opens and reads two files and returns their content
    
    Args:
        first_file: The filename for the first file.
        second_file: The filename for the second file.
    
    Returns:
        A tuple of two elements containing the text of the first and second file.
    """
    file_one = open(first_file, "r")
    file_two = open(second_file, "r")

    text_one = file_one.read()
    text_two = file_two.read()

    return text_one, text_two


def plagiarized(original, lcs_text):
    """
    Compares the longest common substring text to the original text.
    
    Returns:
        How much the text has been plagiarised in percents.
    """
    len_original = len(original)
    len_lcs = len(lcs_text)

    return (len_lcs * 100) / len_original


def generate_report(original_text, plagiarized_text, filename_one=None, filename_two=None, stream=sys.stdout):
    """
    Prints the report.
    
    Args:
        original_text: The original text, from the first file.
        plagiarized_text: The LCS or the lists of words that are in common.
        filename_one:  The filename for the first file, if both file names are provided 
        they will be included in the report.
        filename_two: The filename for the second file.
        stream: The stream where print will print too. Default: stdout
    """
    if filename_one and filename_two:
        print("Files: {} - {}".format(filename_one, filename_two), file=stream)

    print("Plagiarized: {:.2f}%, {:d} words"
          .format(plagiarized(original_text, plagiarized_text), len(plagiarized_text)), file=stream)

    print("Common text:", file=stream)
    print(*plagiarized_text, file=stream)
    print(file=stream)  # Newline


def parse_files(arg_list, outfile=None, filename_one=None, filename_two=None):
    """
    Receives a list two file descriptors and calculates the amount of plagiarised text between the files.
    """
    try:
        text_one = arg_list[0].read()
        text_two = arg_list[1].read()
    except UnicodeDecodeError as e:
        print("Error: ", str(e))
        return

    x = clean_text(text_one)
    y = clean_text(text_two)

    table = lcs(x, y)
    plagiarized_text = lcs_string(table, x, len(x) - 1, len(y) - 1)

    generate_report(x, plagiarized_text, stream=outfile, filename_one=filename_one, filename_two=filename_two)


def parse_files_filename(file_one, file_two, outfile=None):
    """
    Creates a report from the files it receives.
    
    Args:
        file_one: The filename for the first file.
        file_two: The filename for the second file.
        outfile: If this argument is specified the report is generated in an external file.
    """
    file_list = list()
    try:
        # Ignore characters if they can't be decoded using utf-8.
        fd_one = open(file_one, 'r', encoding='utf-8', errors='ignore')
        fd_two = open(file_two, 'r', encoding='utf-8', errors='ignore')
    except IOError as e:
        print(str(e))
        return

    file_list.append(fd_one)
    file_list.append(fd_two)

    parse_files(file_list, outfile=outfile, filename_one=file_one, filename_two=file_two)


def has_txt(filename):
    """
    Checks if the file has the txt extension.
    
    Returns:
        True: if the file has txt extension.
        False: if the files doesn't have txt extension
    """
    return filename[-3:] == 'txt'


def make_table_report(dir_path, outfile=None):
    """
    Reads all .txt files from the provided directory path and for each file, it generates a plagiarism report.
    
    Args:
        dir_path: A list containing as the first element the path of the directory.
    """
    directory_tree = os.walk(dir_path)

    for root, dirs, files in directory_tree:
        valid_files = list(filter(has_txt, files))
        total_valid_files = len(valid_files)

        for i in range(total_valid_files):
            for j in range(i, total_valid_files):
                if i != j:
                    path_one = os.path.join(root, valid_files[i])
                    path_two = os.path.join(root, valid_files[j])
                    parse_files_filename(path_one, path_two, outfile=outfile)
        break

if __name__ == "__main__":
    parser = argparse.ArgumentParser("python main.py",
                                     description="A simple plagiarism detection tool based on LCS algorithm.")
    parser.add_argument('-p', '--parse', nargs=2, help='Compare two files', type=argparse.FileType('r'), metavar='file')
    parser.add_argument('-t', '--tabular', help='Produce a table for each distinct .txt files',
                        metavar='dirname')
    parser.add_argument('-o', '--out', default=None, help="Specify the out filename", metavar='filename',
                        type=argparse.FileType('w'))
    args = parser.parse_args()

    if args.parse is not None:
        parse_files(args.parse, args.out)
    elif args.tabular is not None:
        make_table_report(args.tabular, args.out)
    else:
        parser.print_help()