# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

import pandas as pd
import numpy as np
import seaborn as sns
from matplotlib import pyplot as plt
# %matplotlib inline

df = pd.read_csv('paths_finished.tsv', sep='\t')

df.shape

df.head()

# ## Let us do a little bit of EDA

df.path[0]

transactions = df['path']

from urllib.parse import unquote
transactions = transactions.apply(unquote)
transactions = transactions.apply(lambda s : s.split(';'))

df = transactions.to_frame()

df['path len'] = transactions.apply(lambda l : len(l))

df['path len'].describe()

sns.scatterplot(y = df['path len'], x = df.index)

# remove outliers
df = df[df['path len'] < 30]

sns.scatterplot(y = df['path len'], x = df.index)

df.shape # we have removed about 300 element, yet the element distribution is way better now

plt.boxplot(x=df['path len'])

lang = {}
for path in df['path']:
    for item in path:
        if item in lang.keys():
            lang[item] = lang[item] + 1
        else:
            lang[item] = 1

lang = pd.DataFrame(index=lang.keys(), data=lang.values(), columns=['count'])
lang.shape

lang.sort_values('count', ascending=False, inplace=True)
lang.head(10)


def plot_freq_bar(x, y, title, scale='linear', figsize=(10, 5), rotation=True, xlabel='', ylabel=''):
    fig, ax = plt.subplots(figsize=figsize)
    plt.title(title)
    sns.barplot(x=x, y=y, ax=ax)
    ax.set(xlabel=xlabel, ylabel=ylabel)
    if rotation:
        plt.setp(ax.get_xticklabels(), rotation=45, horizontalalignment='right')
    plt.yscale(scale)

    plt.grid()


data = lang['count'][:20]
plot_freq_bar(x=data.index, y=data, title='', rotation=True)





# # Let's get our hands dirty
# <img src="imgs/its-a-dirty-6f8c09b7d7.jpg" width="600" height="300">

# +
# we will encode article names for the ease of computation and the work with numbers
# this is faster than using sklearn label encoder (don't know why!)
rev_id_dict = lang.reset_index()['index']
id_dict = lang.reset_index().to_dict()['index']
id_dict = dict(zip(id_dict.values(), id_dict.keys()))

df['path'] = df['path'].apply(lambda x : [id_dict[item] for item in x])
# -

db = df['path'].to_list()


# +
# small test-case data base
# db = [
#     [1, 1, 2, 3, 1, 3, 3],
#     [1, 3, 2, 3],
#     [1, 2, 4, 3, 2, 3],
#     [1, 3, 2, 3],
# ]

# +
# we use the lookup table (list) to calculate the projected DB on the fly
# for each sequence we keep track of it's index and a suffix offset
# this approach is called pseudo-projection (fast and much less memeory consuming)

# this function can't handle brackets yet! but too efficient for our sequence database
def discover(prefix, lookup_table, min_sup):
    items_occurs = dict()

    for seq_idx, current_pointer in lookup_table:
        # for each sequence in the (projected) DB
        seq = db[seq_idx]
        unique = set(seq[current_pointer + 1 :])
    
        for offset in range(current_pointer + 1, len(seq)):
            item = seq[offset]
            # add element occurence only once
            if item in unique:
                
                if item in items_occurs.keys():              
                    items_occurs[item].append((seq_idx, offset))
                else:
                    items_occurs[item] = [(seq_idx, offset)]

                unique.remove(item)
    
    res = [] if not prefix else [(len(lookup_table), prefix)]
    
    for item, occurs in items_occurs.items():
        if len(occurs) >= min_sup:
            # generate the new prefix and recursivly discover patterns
            res.extend(discover(prefix + (item,), occurs, min_sup))
    
    return res


# -

import time
begin = time.time()
res = discover(tuple(), [(i, -1) for i in range(len(db))], 10)
print(f'{time.time() - begin:0.2}')

res.sort(key=lambda x : x[0], reverse=True)

len(res)

# decode names and calcluate reletive support
ans = [(f'{sup*100/len(db):0.3}%', tuple(map(lambda x : rev_id_dict[x], seq))) for sup, seq in res]

ans

db1 = [
    [1, (1, 2, 3), (1, 3), 4, (3, 6)],
    [(1, 4), 3, (2, 3), (1, 5)],
    [(5, 6), (1, 2), (4, 6), 3, 2],
    [5, 7, (1, 6), 3, 2, 3]
]

# +
from collections import defaultdict

# too bad time/memory complelxity!! like it take forever to finish :)
def calc_frequent(sdb, min_sup):
    items_occurs = defaultdict(int)

    frequent_items = []
    
    for seq in sdb:

        se = set()

        for item in seq:
            if isinstance(item, tuple):
                for sub_item in item:
                    if sub_item not in se and sub_item != -1:
                        items_occurs[sub_item] = items_occurs[sub_item] + 1
                        se.add(sub_item)
            else:
                if item not in se:
                    items_occurs[item] = items_occurs[item] + 1
                    se.add(item)

    for item, occurs in items_occurs.items():
        if occurs >= min_sup:
            frequent_items.append((item, occurs))

    return frequent_items


def project(sdb, alpha):
    projection = []
    for seq in sdb:
        pp = []
        for idx, item in enumerate(seq):
            if isinstance(item, tuple):
                if alpha in item:
                    generate = True
                else:
                    generate = False
            else:
                if item == alpha:
                    generate = True
                else:
                    generate = False

            if generate:
                if isinstance(item, tuple):
                    if alpha in item:
                        pp = seq[idx:]
                        x = (-1,)
                        for sub_item in item:
                            if sub_item != alpha:
                                x = x + (sub_item,)
                        pp[0] = x

                        if len(set(x)) == 1:  # all element were taken from the brakets
                            pp = pp[1:]
                        break
                else:
                    pp = seq[idx + 1:]
                    break
        if pp:
            projection.append(pp)
    return projection


res1 = []
def discover1(prefix, sdb, min_sup):
    frequent_items = calc_frequent(sdb, min_sup)
    for item, sup in frequent_items:
        # assemble/append to prefix
        new_prefix = prefix + (item,)

        # project sdb on item
        new_sdb = project(sdb, item)

        # recursively discover patterns
        res1.append((new_prefix, sup))

        discover1(new_prefix, new_sdb, min_sup)


# -

# <img src="imgs/meme.webp" width="350" height="300">

res1 = []
begin = time.time()
discover1(tuple(), db, 10)
print(f'{time.time() - begin:0.2}')
res1

print(len(res))
print(len(res1))

StarcoderdataJupyterScriptsDedupFiltered