'Return k samples (beams) and their NLL scores.
Each sample is a sequence of labels, either ending with `eos` or
truncated to length of `maxsample`. `use_unk` allow usage of `oov`
(out-of-vocabulary) label in samples'

def search(self, oov, eos, k=1, maxsample=4000, use_unk=False):

    probs = []
    prime_sample = []
    prime_score = 0
    prime_state = self.initial_state
    for (i, label) in enumerate(self.prime_labels):
        prime_sample.append(label)
        if (i > 0):
            prime_score = (prime_score - np.log(probs[(0, label)]))
        (probs, prime_state) = self.predict(prime_sample, prime_state)
    dead_k = 0
    dead_samples = []
    dead_scores = []
    dead_states = []
    live_k = 1
    live_samples = [prime_sample]
    live_scores = [prime_score]
    live_states = [prime_state]
    while (live_k and (dead_k < k)):
        cand_scores = (np.array(live_scores)[:, None] - np.log(probs))
        if ((not use_unk) and (oov is not None)):
            cand_scores[:, oov] = 1e+20
        cand_flat = cand_scores.flatten()
        ranks_flat = cand_flat.argsort()[:(k - dead_k)]
        live_scores = cand_flat[ranks_flat]
        voc_size = probs.shape[1]
        live_samples = [(live_samples[(r // voc_size)] + [(r % voc_size)]) for r in ranks_flat]
        live_states = [live_states[(r // voc_size)] for r in ranks_flat]
        zombie = [((s[(-1)] == eos) or (len(s) >= maxsample)) for s in live_samples]
        dead_samples += [s for (s, z) in zip(live_samples, zombie) if z]
        dead_scores += [s for (s, z) in zip(live_scores, zombie) if z]
        dead_states += [s for (s, z) in zip(live_states, zombie) if z]
        dead_k = len(dead_samples)
        live_samples = [s for (s, z) in zip(live_samples, zombie) if (not z)]
        live_scores = [s for (s, z) in zip(live_scores, zombie) if (not z)]
        live_states = [s for (s, z) in zip(live_states, zombie) if (not z)]
        live_k = len(live_samples)
        (probs, live_states) = self.predict_samples(live_samples, live_states)
    return ((dead_samples + live_samples), (dead_scores + live_scores))
