Cryptocurrency Names

from collections import Counter
from itertools import chain, islice, repeat
import json
import os.path

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd

from sklearn.preprocessing import  normalize

from scipy.stats import chi2, chi2_contingency, poisson
import seaborn as sns

coin_df = load_df_from_json(r'path/to/coin_attributes.json')
coin_df.head()

coin_df['clean_name'] = coin_df['CoinName'].apply(lambda x: x.strip().upper())

if coin_df['clean_name'].isnull().values.any():
    print("Warning: Missing name.")
else:
    print("No missing names")

n_name = coin_df['clean_name'].size
n_char = sum(map(lambda x: len(x), coin_df['clean_name']))
print("Number of names: {0}".format(n_name))
print("Number of characters: {0}".format(n_char))

raw_char_frequency = Counter(chain(*coin_df['clean_name'].values))
n_letter = len(raw_char_frequency)
raw_chars, raw_freqs = zip(*raw_char_frequency.most_common())

n_top = 5
n_top_freq = np.array(raw_freqs[:n_top], dtype = np.float)
cutoff_freq = 2 * np.dot(np.sqrt(n_top_freq), n_top_freq) / np.sum(n_top_freq) 

discard_chars, _  = zip(*filter(lambda x: x[1] < cutoff_freq, raw_char_frequency.items()))
names = list(filter(lambda x: not any(map(lambda y: y in x, discard_chars)), coin_df['clean_name']))     

name_df = pd.DataFrame({'name' : names})
name_df['name_len'] = name_df['name'].apply(lambda x: len(x))

print("Number of names kept: {0}".format(name_df.shape[0]))
print("Number of characters kept: {0}".format(name_df['name_len'].sum()))

char_frequency = Counter(chain(*names))
chars, freqs = zip(*char_frequency.most_common())

p_freqs = np.asarray(freqs, dtype = np.float) / sum(freqs)
r_raw_freqs = np.asarray(raw_freqs, dtype = np.float) / sum(raw_freqs)

f_obs = np.asarray([freqs, raw_freqs[:len(freqs)]])
chi2_, p, dof, f_epx = chi2_contingency(f_obs)

print("P-value: {0}".format(p))

with open('char_freq.json', 'r') as fproc:
    ref_letter_frequency = json.load(fproc)
    
ref_letter_frequency = {x.upper() : float(y) / 100.0 for x, y in ref_letter_frequency.items()}

letter_frequency =  dict(filter(lambda x: x[0] in ref_letter_frequency, char_frequency.items()))  

sum_ = sum(letter_frequency.values())
letter_frequency = {x : float(y) / sum_ for x, y in letter_frequency.items()}    # normalise

missing_letters = set(ref_letter_frequency.keys() - letter_frequency.keys())     # letters not in names
letter_frequency.update({x : 0 for x in missing_letters})

name_len_histo = np.bincount(name_df['name_len'].values) * 1.0
name_len_histo /= max(1.0, np.sum(name_len_histo)) # dirty, I know -- but we also know that the lengths are 0< integers

name_df['trf_vals'] = name_df['name_len'].apply(lambda x: np.sqrt(x + 0.375))
trf_vals = name_df['trf_vals'] - name_df['trf_vals'].sum()

chisq = np.dot(trf_vals,trf_vals)  
print(chi2.sf(chisq, name_df.shape[0]))

make_doublets = lambda x: zip(x[:-1], x[1:])
make_doublet_histo = lambda x: Counter(chain(*map(lambda x: make_doublets(x), x)))

pair_histo = make_doublet_histo(name_df['name'].values)

for pair, cnt in pair_histo.most_common(15):
    print("{0}\t:\t{1}".format(pair, cnt))
 

histo, decoder = counter_to_np_array(pair_histo, with_decoder = True)
xlabels = ylabels = decoder.values()

is_terminal = np.any(histo.sum(axis = 1) == 0.0)
is_starting = np.any(histo.sum(axis = 0) == 0.0)
is_standalone = is_terminal & is_starting

chooser = lambda x: 'yes' if x else 'No-o'

print("-Are there standalone characters? \n-The computer says {0}.".format(chooser(is_standalone)))
print("-Are there start only characters? \n-The computer says {0}.".format(chooser(is_starting)))
print("-Are there terminal only characters? \n-The computer says {0}.".format(chooser(is_terminal)))

class MarkovSequenceGenerator(object):
    """
    Class to generate Markov sequences.
    
    Attributes:
        decoder ({int:object}) : dictionary that decodes the states
        encoder ({object:int}) : dictionary that assigns a unique index to every state
        transition_matrix (np.ndarray) : row normalised transition probability matrix
        
    Methods:
        create_sequence_generator (generator.object) : a generator which yields Markov sequences. 
        Each returned item is a generator of a Markov sequence.
    """
    
    def __init__(self, transition_matrix, decoder, random_state = None):
        """
        transition_matrix (np.ndarray) : row normalised transition probability matrix
        decoder ({int:object}) : dictionary that decodes the states
        """
        
        self._decoder = decoder
        self._encoder = dict(zip(decoder.values(), decoder.keys()))
        self._transition_matrix = transition_matrix
        
        # calculate cumulative probabilities for sampling
        self.__cumprob_matrix = np.cumsum(self.transition_matrix, axis = 1)

    @property
    def decoder(self):
        return self._decoder
    
    @property
    def encoder(self):
        return self._encoder
            
    @property
    def transition_matrix(self):
        return self._transition_matrix
    
    def create_sequence_generator(self, start):
        """
        Creates a generator of a Markov sequence.
        Parameters:
            start (object) : starting state
        Returns:
            sequence_generator (generator) : a generator object of a Markov sequence
        """
        
        if start not in self.encoder.keys():
            raise KeyError("Start value not in known states. Got: {0}".format(start))
 
        self.__idx = self._encoder[start]

        def sequence_generator(start_index):
            """
            A Markov sequence. 
                Returns the state at `start_index`
                Propagates the chain by one step.
            Parameters:
                start_index (int) : index of the starting Markov state. 
            """
            
            idx = start_index

            while True:
                
                if idx is None:
                    return
                
                symbol = self._decoder[idx]
                idx = self._propagate_one_step(idx)  
                
                yield symbol
                
        return sequence_generator(self.__idx)
    
    def _propagate_one_step(self, idx):
        """
        Propagates the Markov chain by one step.
        Parameters:
            idx (int) : index of the current Markov state.
        Returns:
            next_idx (int) or None: the index of the next Markov state. None if the chain ended.
        """
        
        x = np.random.rand()
        
        # nowhere to go
        if self.__cumprob_matrix[idx, -1] == 0.0:
            return
        else:
            next_idx = int(np.argwhere(self.__cumprob_matrix[idx] - x > 0.0)[0])

        return next_idx

msqg = MarkovSequenceGenerator(tmat, decoder)

n_seq_len = 50
seqs = (msqg.create_sequence_generator(start) for start in ['C', 'C', 'Y'])

for seq in seqs:
    print("".join(islice(seq, n_seq_len)))

start_symbol = '^'
end_symbol = '$'
name_df['aug_name'] = name_df['name'].apply(lambda x: start_symbol + x + end_symbol)

# create histogram with decoder
pair_histo_aug = make_doublet_histo(name_df['aug_name'].values)
histo_aug, decoder_aug = counter_to_np_array(pair_histo_aug, with_decoder = True)

# transition matrix and labels
tmat_aug = normalize(histo_aug, norm = 'l1', axis = 1)
xlabels = ylabels = decoder_aug.values()

msqg_aug = MarkovSequenceGenerator(tmat_aug, decoder_aug)
seqs =  (msqg_aug.create_sequence_generator(x) for x in repeat(start_symbol))

n_seqs = 10
for idx, seq in enumerate(islice(seqs, n_seqs)):
    print(idx, "\t:\t", "".join(seq))

generated_words = np.asarray(["".join(seq) for seq in islice(seqs, 20000)])

sample_specs = {100 : 10, 500 : 10, 1000 : 10, 2000 : 10, 5000 : 10, 10000 : 10}
encoder_aug = dict(zip(decoder_aug.values(), decoder_aug.keys()))

sample_size_log, diff_log = [], []

for sample_size, repeats in sample_specs.items():
    
    for idx in range(repeats):
        # sample names and create transition matrix
        sample = np.random.choice(generated_words, size = sample_size)
        sample_histo = fill_np_array_with_counter(make_doublet_histo(sample), encoder_aug)
        
        # calculate difference
        diff = normalised_l2_diff(sample_histo, histo_aug)
        diff_log.append(diff) 
        sample_size_log.append(sample_size)

word_lengths = np.array([len(x) for x in generated_words])
max_len = np.max(word_lengths)

bins = np.arange(max_len + 1)
bstr = SlimBootstrap(func = sample_to_distribution, func_kwargs = {'bins' : bins})
wl_dist = bstr.fit_predict(word_lengths)

ref_word_lengths = name_df['name_len'].values
ref_bstr = SlimBootstrap(func = sample_to_distribution, func_kwargs = {'bins' : bins})
ref_wl_dist = bstr.fit_predict(ref_word_lengths)

def counter_to_np_array(counter, with_decoder = False):
    """
    Creates a numpy array based on a counter.
    Parameters:
        counter (collection.Counter) : a counter of length 2 keys
        with_decoder (bool) : if True returns a decoder dictionary. Default: False.
    Returns:
        array (np.ndarray) : 2D numpy array where each index corresponds to a key in counter. 
        The value at a certain index is the corresponding count
        decoder ({:}) : a index : key dictionary if `with_decoder` is True
    """
    
    # key must be an iterable of length two
    key, count = counter.most_common(1)[0]
    key = list(key)
    
    if len(key) != 2:
        raise KeyError("counter key must be of length 2. Got: {0}".format(len(key)))
        
    # decompose to key count pairs
    keys, counts = counter.keys(), counter.values()
    
    # encode keys
    unique_symbols = set(chain(*keys))
    encoder = dict(zip(unique_symbols, range(len(unique_symbols))))
    xy = np.asarray([encoder[x] for x in chain(*keys)])
    xy = np.reshape(xy, (xy.shape[0] // 2, 2))

    # create histogram
    bins = np.arange(np.max(xy) + 2)
    weights = np.array(list(counts))
    array, _, _ = np.histogram2d(xy[:,0], xy[:,1], bins = [bins, bins], weights = weights)
    
    # add decoder if requested
    if with_decoder:
        decoder = dict(zip(encoder.values(), encoder.keys()))
        
        return array, decoder
    else:
        return array

def fill_np_array_with_counter(counter, encoder):
    """
    Fills a numpy array with a counter. It performs a *key --> *index transformation.
    Parameters:
        counter (collections.Counter) : a counter where all keys are of equal length.
        encoder ({}) : the keys are the keys of the counter (or a superset thereof) the values are integer indices.
    Returns:
        array (np.ndarray) : numpy array with counts.
    """
    
    n_size = len(encoder)
    mat = np.zeros(shape = (n_size, n_size), dtype = np.float)
    
    for (kx, ky), count in counter.items():
        mat[encoder[kx], encoder[ky]] = count
        
    return mat

def normalised_l2_diff(p, q):
    """
    Calculates the normalised L2 difference between two arrays.
    Parameters:
        p (np.ndarray) : first distribution
        q (np.ndarray) : second distribution
    Returns:
        diff (np.float) : the L2 difference between the normalised p, and q distributions
    """
    
    p_ = normalize(p)
    q_ = normalize(q)
    
    denominator = (np.square(p_) + np.square(q_))
    if not np.any(denominator):
        raise ValueError("Both distributions are zero.")
        
    diff = np.sum(np.square(p_ - q_)) / np.sum(denominator)
    
    return diff

def sample_to_distribution(arr, *args, **kwargs):
    hist =  np.histogram(arr, *args, **kwargs)[0]
     
    sum_ = np.sum(hist)
    if sum_ == 0.0:
        hist = np.zeros(hist.shape)
    else:
        hist = hist * 1.0 / sum_ 
    
    return hist

def load_df_from_json(path_to_file, orient = 'index'):
    """
    Loads a pandas dataframe from a json file.
    Parameters:
        path_to_file (str) : **full** path to the json storage
        orient (str) : orientation of the json (see pandas.read_json for details)
    Returns:
        df (pandas.DataFrame) : a dataframe
    """
    with open(path_to_file, 'r') as fproc:
        df = pd.read_json(fproc, orient = orient)        
    return df

def plot_histomat(mat, ax = None, xlabels = None, ylabels = None):
    
    if ax is None:
        fig, ax = plt.subplots(1,1)
        fig.set_size_inches(8,8)
        
    n_xticks, n_yticks = mat.shape
    
    extent = (0, n_xticks, n_yticks, 0)
    
    ax.grid(color  = 'black', linestyle='--', linewidth = 0.1)
    
    ax.set_xticks(np.arange(n_xticks))
    ax.set_yticks(np.arange(n_yticks))
    
    if xlabels is not None:
        ax.set_xticklabels(xlabels)
    
    if ylabels is not None:
        ax.set_yticklabels(ylabels)
    
    ax.imshow(mat, extent = extent, cmap = 'Greens', vmin = 0)

class SlimBootstrap(object):
    """
    Simple percentile bootstrap class.
    Attributes:
        n_resample (int) : number of samples
        sample_size (int) : sample size -- number of elements taken from the population.
        alpha (float) : significance level at which the confidence interval is calculated
    
    Methods:
        fit() : calculates the percentile bootstrap estimate and confidence bands
        fit_predict() : returns the calculated estimate and confidence bands
    """
    
    def __init__(self, n_resample = 2000, sample_size = 1000, alpha = 0.05,
                 func = lambda x: x, func_args = [], func_kwargs = {}):
        """
        Parameters:
            n_resample (int) : number of samples. Default 2000.
            sample_size (int) : sample size -- number of elements taken from the population. Default 1000.
            alpha (float) : significance level at which the confidence interval is calculated. Default 0.05.
            func (callable) : function which is applied to the samples. The result of this function is bootstrapped.
                The bootstrap function can return any object as long as it can be cast to a regular np.ndarray.
                Default : identity function
            func_args ([]) : positional arguments of func. Default [].
            func_kwargs ({:}) : keyword arguments of func. Default {}.
        """
        
        self._n_resample = n_resample
        self._sample_size = sample_size
        self._alpha = alpha
        self._func = func
        self._func_args = func_args
        self._func_kwargs = func_kwargs
    
    @property
    def alpha(self):
        return self._alpha
    
    @property
    def n_resample(self):
        return self._n_resample
    
    @property
    def sample_size(self):
        return self._sample_size
    
    def _generate_samples(self):
        self.__samples = (np.random.choice(self.__population, self.sample_size) 
                              for i in range(self.n_resample))
    
    def _set_population(self, population):
        self.__population = population
            
    def fit(self, population):
        """
        Calculates the bootstrap estimate and confidence bands. 
        Parameters:
            population (indexable) : the population to be sampled.
        Returns:
            self
        Notes:
            The return values of the function are sorted along the first axis.
        """
    
        self._set_population(population)
        
        self._generate_samples()
    
        # 1) It would be better to apply the function to the entire population
        # simultaneously. However, it is not granted that the function is written that way.
        
        # 2) consume the generator here, so it can be cast as an array quicker
        measurements = list(self._func(x, *self._func_args, **self._func_kwargs) 
                                for x in self.__samples)

        store = np.array(measurements)
        
        # sort in place along first axis
        store.sort(axis = -store.ndim)
        
        # bootstrap estimate
        estimate = np.mean(store, axis = -store.ndim)
        
        # confidence bands
        i_low = int(self._alpha / 2.0 * self._n_resample)
        i_up = int((1.0 - self._alpha / 2.0) * self._n_resample)
        
        cb_low = store[i_low]
        cb_up = store[i_up]
        
        self._result = np.array((estimate, cb_low, cb_up))
        
        return self
    
    def fit_predict(self, population):
        """
        Convenience wrapper around the `fit` method.
        Parameters:
            population (indexable) : population to be sampled
        Returns:
            self._result (np.ndarray) : the estimate and confidence bands
            _result[0] : estimate
            _result[1] : lower bound of confidence band
            _result[2] : upper bound of confidence band
        """
        return self.fit(population)._result