I'm having trouble with a current algorithm I'm writing that takes a corpa, a list of characters in sets (1 one or larger) with a frequency number attached to it. Against another list of character sets that need to be created using the most frequent occurrences of the combined sets... if that makes sense. I'll explain with an example. So lets say your corpa looks like this. (Just note that case does not matter as the actual data is in Korean, hence each character represents a Korean character.)A   56AB  7342ABC 3BC  116C   5CD  10BCD 502ABCD    23D   132DD  6The wordlist is (ignore the number):AAB     1123DCDD    83So the output of the script would be:Original    Pois        Makeup                      Freq_Max_DeltaAAB         A AB        [AB, 7342][A, 56]           7398DCDD        D C DD      [D, 132][DD, 6][C, 5]       143Currently I am basically doing this by ordering the corpa, then grabbing each individual line, getting all the combinations of each letter (this is redundant as it produces combinations which are not positionally correct) and then pulls out which combinations can make up the word. Then adds up the frequency of the set of combinations and then outputs the one with Freq_Max_Delta.I'm thinking that a large part of the problem is the number of nested loops that I'm using and the fact we are creating redundant data. I'm also looking into the possibility of cython and even using multiple threads for the tokenisation. The problem is some what similar to the Knapsack ProblemBelow is my code, also a portion of the inputs are located on my gist if you are interested in running it with what I'm using. The wordlist and the corpafrom argparse import ArgumentParserfrom collections import OrderedDictfrom itertools import combinationsdef order_worlist(corpa):    dict_corpa = dict()    print 'ordering corpa....'    with open(corpa, 'r') as open_wordlist:        for line in open_wordlist:             line_arr = line.rstrip().split('\t')            count = line_arr[-1]            tx = line_arr[0]            dict_corpa[tx] = int(count)    open_wordlist.close()    return OrderedDict(sorted(dict_corpa.items(), key=lambda t: t[1], reverse=True))def create_cominations(tx_dict, original_tx):    tx_list = list()    for k, v in tx_dict.items():        tx_list.append(k)    output = list()    for k, v in tx_dict.items():        y = lambda : sum([map(list, combinations(tx_list, i)) for i in range(len(tx_list) + 1)], [])        output.append( y())    final_li = None    try:        for i in output[0]:            if sorted(''.join(i)) == sorted(original_tx):                if len(''.join(i)) == len(original_tx):                    sub = list()                    total = 0                    for v in i:                        total += tx_dict[v]                        sub.append([v, tx_dict[v]])                    if final_li is None:                        final_li = []                        final_li.append([i, [sub], total])                          if total > final_li[0][2]:                        final_li = []                        final_li.append([i, [sub], total])                    else:                        pass        part_final = ''        for part in final_li[0][1]:            for v in part:                part_final += '[' + v[0] + ', ' +  str(v[1]) + ']'        print '\t\t'.join(['For: ',original_tx ,' '.join(final_li[0][0]), part_final, str(final_li[0][2])])    except:        print '\t\t'.join(['For: ', original_tx, '\t\tNothing Found']) def contains(small, big):    for i in xrange(len(big)-len(small)+1):        for j in xrange(len(small)):            if big[i+j] != small[j]:                break        else:            return (i, i+len(small))    return Falsedef find_best(original_tx, freq_tx, dict_corpa, results):       for k, v in dict_corpa.items():        try_tx = k        try_tx_freq = v        containment = contains(try_tx, original_tx)         if containment:            start, end = containment            results[.join(original_tx[start : end])] = try_tx_freq    return OrderedDict(sorted(results.items(), key=lambda t: t[1], reverse=True))def main():    parser = ArgumentParser(description=__doc__)    parser.add_argument(-w, --wordlist, help=, required=True)    parser.add_argument(-c, --corpa, help=, required=True)    agrs = parser.parse_args()    corpa_dict = order_worlist(agrs.corpa)    with open(agrs.wordlist) as txs:        for tx in txs:            freq_tx = tx.rstrip().split('\t')[1]            tx = tx.rstrip().split('\t')[0]            find_best_dict = find_best(tx, freq_tx, corpa_dict, dict())            create_cominations(find_best_dict, tx) if __name__ == '__main__':    main()
Improving Speeds of Tokenisation of large word list for distinct combinations
python;combinatorics;set