<jupyter_start><jupyter_text>Let us do a little bit of EDA<jupyter_code>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)<jupyter_output><empty_output><jupyter_text>Let's get our hands dirty<jupyter_code># 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)<jupyter_output><empty_output><jupyter_text><jupyter_code>res1 = []
begin = time.time()
discover1(tuple(), db, 10)
print(f'{time.time() - begin:0.2}')
res1
print(len(res))
print(len(res1))<jupyter_output>36036
36036
{'fraction_non_alphanumeric': 0.12576255279211637, 'fraction_numerical': 0.01767558266854372, 'mean_word_length': 2.1842629482071714, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '652822', 'license': 'MIT', 'n_tokens_mistral': 2138, 'n_tokens_neox': 1993, 'n_words': 595, 'path': 'main.ipynb', 'repo_name': 'Nitro963/prefix-span', 'size': '6393'}