# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # Python Sequitur (Nevill-Manning) algorithm

# For the algorithm reference see:
#
# 1. http://arxiv.org/abs/cs/9709102
# 2. https://en.wikipedia.org/wiki/Sequitur_algorithm
# 3. http://www.sequitur.info/
#
# I'm testing the pysequitur library against the web interface provided by sequitur.info.
#
# ## Background
#
# Main reason to make a new library is that I needed to have the Sequitur algorithm to work with "any" object pairs (digram), not just textual input. This is best achieved by working with list indexes rather than rudimentary text replacements on the algorithm.
#
# Other reason was to test efficiency of two different approaches for the algorithm:
#
# 1. array slicing method
# 2. digram storage method
#
# I was quessing array slicer is an easier way, but searching digrams from existing rules might take longer time and concequently have a downside effect to the performance of the algorithm. Thus the second way, "digram storage method" was implemented. Trivial tests show that the latter is a faster implementation indeed.
#
# Other Python libraries for the algorithm can be found from GitHub:
#
# 1. https://github.com/mspandit/sequitur-python
# 2. https://github.com/raysaagar/parallel-sequitur
#
# The latter provides both serial and parallel versions of the algorithm. Unexpectively the parallel version is slower on small data sets on my tests. Both algos work slower than the "digram storage method". I found _sequitur-python_ just recently so performance and features of that library are yet to be tested.
#
#
# ## Array slicing method
#
# I'm not going to the deep details of the source code on these two implementations. Basicly on array slicing method every rule is a plain list of sequence items. So finding and comparing digrams needs to loop over all rules and then slice root sequence to parts, which are two items long. Comparison is thus made like this:
#
# <pre><code class="python">rule[i:i+2] == digram</code></pre>
#
# This is one of the most resource eating part on the algorithm. Of cource the rule utility is another similar loop over loop over loop place which takes most of the time on the algo:
#
# <pre><code class="python">for rule1 in self:
#     for rule2 in self:
#         l = len(rule2)
#         ind = 0
#         while ind < l:
#             c = rule2[ind+1:]
#             del rule2[ind:]
#             rule2 += rule1 + c
#             ind += 1
# </code></pre>
#
# ## Digram storage method
#
# On the digram storage method array slicing is eliminated by storing every item with the previous item. In this case digrams are stored on memory, which causes approximately twice the memory consumption but then, at least trice the performance increase. On Digram storage method comparison can be done with more efficient way:
#
# <pre><code class="python">digram in rule</code></pre>
#
# Also the rule utility is behaving a bit different way after this data structure change. Still I coudn't find a way to eliminate loops over loops, but rule modification method seems to be more efficient, because there is no need to delete and reinstantiate the list of rule items. Simplified it looks like this:
#
# <pre><code class="python">for rule1 in self:
#     for rule2 in self:
#         l = len(rule2)
#         ind = 0
#         while ind < l:
#             self[ind:ind] = rule[:]
# </code></pre>
#
# All code with comments can be found from GitHub directory: https://github.com/markomanninen/pysequitur/blob/master/pysequitur/main.py
#
# ## Using library
#
# Library offers these two implementations of the algorithm with dedicated classes:
#
# - Sequencer
# - Sequencer2
#
# For nice output print_grammar function is provided. Five different constants can be used to alter output and representation of the classes used on the library's print utility:
#
# - **RULE_INDEX_STR**<br/>
#   How to represent rule indexes on output, default is "^%s" where %s is replaced with a rule index number
# - **SEQUENCE_KEY**<br/>
#   Define special key to be used to mark the main root sequence, default is "S"
# - **ARROW**<br/>
#   Special character to be used as a separator between rule indices and rules, default "→"
# - **NEWLINE_REPLACEMENT**<br/>
#   What to do with newlines on output, default replacement is "↵"
# - **SPACE_REPLACEMENT**<br/>
#   What to do with space characters on output, default replacement is "_"
#
# ## Comparison
#
# Let's compare these two different sequencers and print_grammar utility with an example children nursery rhyme:

# +
from pysequitur import Sequencer, Sequencer2, print_grammar

seq = """pease porridge hot,
pease porridge cold,
pease porridge in the pot,
nine days old.

some like it hot,
some like it cold,
some like it in the pot,
nine days old."""
# -

print (Sequencer(seq).get())

print (Sequencer2(seq).get())

# As we can notice, data structures are different, latter is somewhat easier to understand, more straightforward. Now let's compare grammar generated by sequencers:

print_grammar(Sequencer(seq))

print_grammar(Sequencer2(seq))

# They should give similar output, just index numbers should be different. Then let's make some trivial efficiency check with __%%timeit__ notebook magics:

# %%timeit
Sequencer(seq)

# %%timeit
Sequencer2(seq)


# Sequencer 2 takes more than twice longer to create the grammar. Before trying with longer text samples, let's try a trivial tester, which compares generated sequence to the expected output. If they don't match, function will output error.
#
# ### Test output

def test(sequence, expect, sequencer_class):
    """ Test sequence if result is as expected. This is a very trivial tester. """
    s = sequencer_class()
    for c in sequence:
        s.stream(c)
    try:
        assert str(s) == expect
        print ("Test ok!")
    except AssertionError:
        print ('Assertion error!', 'Sequence "%s" gave: "%s". Expected: "%s"' % (sequence, str(s), expect))


test('abcdbcabcd', '^3^1^3', Sequencer)

test('abcdbcabcdbc', '^3^1^3', Sequencer)

# ### Longer text sample
#
# Now it is time to compare longer text with sequencers. I'm using samples found from: http://www.sequitur.info/ to double check everything works as expeted. First import Genesis text from file:

input_string = open('genesis1.txt', 'r').read()

# Then processing with two different sequencers:

# %%timeit
Sequencer(input_string)

# %%timeit
Sequencer2(input_string)

# Result is that "digram storage method" seems to be trice faster than simpler "array slicing method".
#
# Other long text sample ("I am Sam" poem) looks like this when converted to a grammar:

input_string = open('IamSam.txt', 'r').read()
s = Sequencer(input_string)
print_grammar(s)

# ### Stream sequence
#
# So far we have provided a input sequence as a single pass as a class constructor argument. Let's assume, that sequencer is used to find out repeating hierarchal structures from a constant stream of a numeric input data. On the next code block I will emulate constant data flow within a while loop. A small delay is used on a loop to create an effect of a continuous stream of timely data.
#
# To differentiate rule indexes and numeric data I will change RULE_INDEX_STR constant to the more approriate one so that rule index numbers will be wrapped with curly brackets. Also because index numbers in Python are in a form of integer types, we need to make sure that Rule Indices and input values are not mixed on the process. Class Int is presented here for that reason.
#
# _Use Kernel->Interrupt from the main menu to stop while loop in case of infinite recursion!_

# +
import time
from IPython.display import clear_output
import pysequitur

class Int(int):
    def __repr__(self):
        return str(self)
    def __eq__(self, v):
        return isinstance(v, Int) and int.__eq__(self, v)

# reinstantiate default rule index string: ^%s with: {%s}
pysequitur.main.RULE_INDEX_STR = "{%s}"
# init sequencer
s = Sequencer()
# init delay, 0.5 seconds
delay = 0.5
# init numeric data and map them to Int type
a = [1,2,3,4,2,3,1,2,3,4,1,2,3,4,2,3,1,2,3,4]
a = list(map(Int, a))

try:
    l = len(a)
    i = 0
    while i < l:
        s.stream(a[i])
        print_grammar(s)
        time.sleep(delay)
        clear_output(wait=True)
        i+=1
except KeyboardInterrupt:
    pass
# -

# ## Resolve
#
# When sequencer is used to generate (which also means same as compress the data), we can use resolve method of the Sequencer class to decode main rule back to original sequence:

input_string = open('peaseporridge.txt', 'r').read()
s = Sequencer(input_string)
print (''.join(s.resolve()))

# ## Random sequence
#
# One more final case just to demonstrate sequencer in working is to use random letter pattern and see how it is processed by the library:

# +
import time
from random import shuffle, randint as rand
from IPython.display import clear_output

def test_random_seq(f=5, delay=0.1):
    abc = 'abcdefghijklmnopqrstuvwyz'
    l = len(abc)-1
    s = ''
    i = l*f
    # to stop script execution on Jupyter notebook: Kernel -> Interrupt
    try:
        s = Sequencer(abc[rand(0, l)])
        while i > 0:
            i -= 1
            s.stream(abc[rand(0, l)])
            print ('sequence:', s)
            print ('grammar:', s.get()[0])
            print ('rules:', s.get()[1:])
            print ('resolve:', s.resolve())
            time.sleep(delay)
            clear_output(wait=True)
    except KeyboardInterrupt:
        pass


# -

test_random_seq()

# ## The [MIT](https://github.com/markomanninen/pysequitur/blob/master/LICENSE) License
#
# Copyright &copy; 2016 <NAME>

StarcoderdataJupyterScriptsDedupFiltered