<jupyter_start><jupyter_text>Part 2<jupyter_code># df structure: 
#{'bits': parent node}

def make_graph(file):
    df = dict()
    df2 = set()
    rank = dict()
    length= 0
    i = 0
    with open(file) as f:
        for line in f.readlines():
            if i == 0:
                length = int(line.strip('\n').split(' ')[1])
                i += 1
            else:
                val = line.strip('\n').replace(' ', '')
                df[val] = val #set parent to itself - automatically omits identical vals
                rank[val] = 0
                df2.add(val)
                i+=1
    return df, df2, rank, length

def one_off(string, position):
    if string[position] == '1':
        return string[0:position]+'0'+string[position+1:]
    else:
        return string[0:position]+'1'+string[position+1:]
#function for generating one and two off values
## can be further improved 
def two_off(string, length):
    test = set()
    for i in range(length):
        one = one_off(string,i)
        test.add(one_off(string,i))
        for j in range(length):
            two = one_off(one, j)
            if two != string:
                test.add(two)
    return test
def find(node):
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]

def union(node1, node2):
    root1 = find(node1)
    root2 = find(node2)
    if root1 == root2:
        return
    if rank[root1] > rank[root2]: # if root1 is part of larger tree
        parent[root2] = root1
        nodes.remove(root2)
    else: # root2 has an equal or larger tree
        parent[root1] = root2
        nodes.remove(root1) # remove node from clusters        
    if rank[root1] == rank[root2]: # if trees equaal in size
        rank[root2] += 1 # increase rank size
# generate {node: parent (self)} with file generate set of unique nodes, ranks = 0

##parent, nodes, rank, length = make_graph('clustering_big.txt')

def clustering_big(parent, nodes, rank, length):
    # for each node generate a set of values that are two-off
    working_set = list(nodes)
    while len(working_set) > 0:
        node = working_set.pop()
        findlist = two_off(node, length)
    # for each value in two-off set, extract root from hash table,
        for simnode in findlist:
            if simnode in nodes:
        # perform union-by-rank, update hashtable with new parents,
        # delete node from set (containing only root nodes)
                    #print(len(nodes))    
                union(node, simnode)
            else:
                continue
        
        
    # count number of items in parent nodes when loop ends: answer
    return len(nodes)
parent, nodes, rank, length = make_graph('clustering_big.txt')
len(nodes)
clustering_big(parent, nodes, rank, length)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11099252934898612, 'fraction_numerical': 0.014941302027748132, 'mean_word_length': 2.2100456621004567, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '363772', 'license': 'MIT', 'n_tokens_mistral': 877, 'n_tokens_neox': 849, 'n_words': 272, 'path': 'greedy_algorithms/Kruskal-max spacing k clustering.ipynb', 'repo_name': 'liujj90/algorithm_practice', 'size': '2811'}