<jupyter_start><jupyter_text>CKY parser with string copying This parser was written by Meaghan. It implements copying through a special category and placeholder string which has the effect of copying some amount of material from the end of the sentence so far and adding it to the end.This implementation allows copies to overlap, and does not require that copies be constituents.The grammar actually generates strings in Lex+"copy", where "copy" is a special string. There is then a second grammar that generates the real string from a string that includes instances of "copy" by copying some amount of material from before "copy" and replacing "copy" with it. The amount of material to be copied is determined by that second grammar. For the parser, we don't have to worry about it; we just need to find potential copies.The grammar may have one rule set with the LHS Copy and the RHS copy (ie Copy->copy). if this rule set is present, the parser will check, for every cell, whether the string it represents is identical to the preceding string of the same length. If it is, it puts the Copy category in the cell and the "copy" lexical item in the backpointers. Otherwise, the parser proceeds like a normal CKY parser.<jupyter_code>import cky
from IPython.display import Image
from IPython.display import display<jupyter_output><empty_output><jupyter_text>We make a toy grammar. None of these rules are copy rules.<jupyter_code>grammar = [("S",  [(["NP","VP"])]),
               ("VP", [(["VP","PP"]),
                       (["V","NP"]),
                       (["eats"])]),
               ("PP", [(["P","NP"])]),
               ("NP", [(["NP","PP"]),
                       (["Det","N"]),
                       (["she"])]),
               ("V" , [(["eats"])]),
               ("P" , [(["with"])]),
               ("N" , [(["fish"]),
                       (["fork"])]),
               ("Det",[(["a"])])]<jupyter_output><empty_output><jupyter_text>A second grammar that generates full binary trees<jupyter_code>grammar_ambig = [("S",[(["S","S"]),(["a"])])]
grammar_ambig_probs = [("S",[(["S","S"],0.5),(["a"],0.5)])]

print(cky.grammar2string(grammar_ambig))<jupyter_output><empty_output><jupyter_text>A third grammar with copying<jupyter_code>grammar_ambig_copy = [("S",[["S","S"],["a"],["S","Copy"],["Copy","S"]]),("Copy",[["copy"]])]
grammar_ambig_copy_probs = [("S",[(["S","S"],0.2),(["a"],0.3),(["S","Copy"],0.2),(["Copy","S"],0.3)]),("Copy",[(["copy"],1.)])]
print(cky.grammar2string(grammar_ambig_copy))<jupyter_output><empty_output><jupyter_text>Let's run some examples<jupyter_code>s = "she eats a fish with a fork".split(" ")
g = grammar<jupyter_output><empty_output><jupyter_text>Parse s with g<jupyter_code>chart,backpointers = cky.parse(s,g)
cky.print_chart(chart)
cky.pretty_print_backpointers(backpointers,g)<jupyter_output><empty_output><jupyter_text>Collect the trees<jupyter_code>parses = cky.collect_trees("S",chart,backpointers,g,s)<jupyter_output><empty_output><jupyter_text>Print the trees to files<jupyter_code>for i,parse in enumerate(parses):    
    cky.tree_to_png(parse,"parse_%i.png"%i)
x=Image(filename='parse_0.png')
y=Image(filename='parse_1.png')
display(x,y)<jupyter_output><empty_output><jupyter_text>Count the trees<jupyter_code>cky.n_parses("S",chart,backpointers,g,s)<jupyter_output><empty_output><jupyter_text>Calculate probabilities<jupyter_code>grammar_probs = [("S",  [(["NP","VP"],1.)]),
               ("VP", [(["VP","PP"],0.3),
                       (["V","NP"],0.4),
                       (["eats"],0.3)]),
               ("PP", [(["P","NP"],1.)]),
               ("NP", [(["NP","PP"],0.5),
                       (["Det","N"],0.3),
                       (["she"],0.2)]),
               ("V" , [(["eats"],1.)]),
               ("P" , [(["with"],1.)]),
               ("N" , [(["fish"],0.6),
                       (["fork"],0.4)]),
               ("Det",[(["a"],1.)])]
g_probs = cky.make_rule_probs(grammar_probs)
print(cky.grammar2string_probs(grammar_probs))

(probs,s_prob)=cky.probability("S",chart,backpointers,g,s,g_probs)<jupyter_output><empty_output><jupyter_text>The log probability of the sentence is the second element<jupyter_code>s_prob<jupyter_output><empty_output><jupyter_text>Let's un-log it just to get a look<jupyter_code>cky.np.exp(s_prob)<jupyter_output><empty_output><jupyter_text>Full binary tree grammars  Using the binary tree grammar without copying<jupyter_code>g = grammar_ambig
s = ["a"]*3
chart,backpointers = cky.parse(s,g)
cky.print_chart(chart)
cky.pretty_print_backpointers(backpointers,g)
# cky.print_backpointers(backpointers)  ## in case there are so many pointers in a cell that pretty_print won't show them
cky.n_parses("S",chart,backpointers,g,s)
parses = cky.collect_trees("S",chart,backpointers,g,s)
for i,parse in enumerate(parses):    
    cky.tree_to_png(parse,"parse_%i.png"%i)
x=Image(filename='parse_0.png')
y=Image(filename='parse_1.png')
display(x,y)<jupyter_output><empty_output><jupyter_text>Probability of sentence<jupyter_code>g_probs = cky.make_rule_probs(grammar_ambig_probs)
(probs,s_prob)=cky.probability("S",chart,backpointers,g,s,g_probs)<jupyter_output><empty_output><jupyter_text>The log probability of the sentence is the second element<jupyter_code>s_prob<jupyter_output><empty_output><jupyter_text>Let's un-log it just to get a look<jupyter_code>cky.np.exp(s_prob)<jupyter_output><empty_output><jupyter_text>Computing Catalan numbers We're interested in Catalan numbers because they provide an easy check on the basic behaviour of the parser, sans copying. the nth Catalan number is the number of parses of a full binary tree with n leaves.<jupyter_code>def a_sent(n): return ["a"]*n

#catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430,
#4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 
#35357670, 129644790, 477638700, 1767263190, 6564120420,
#24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 

def catalan(n):
    """calculates the first n catalan numbers (except 0th) extremely inefficiently"""
    for i in range(1,n):
        s=a_sent(i)
        chart,backpoints = cky.parse(s,grammar_ambig)
        print(cky.n_parses("S",chart,backpoints,grammar_ambig,s))


def catalan_probs(n):
    """calculates the probabilities of fully ambiguous trees, with both rules p=0.5"""
    for i in range(1,n):
        s=a_sent(i)
        chart,backpoints = cky.parse(s,grammar_ambig)
        print(cky.probability("S",chart,backpoints,grammar_ambig,s,g_probs)[1])
    

catalan(7) ## the first 7 Catalan numbers
catalan_probs(7) ## log probabilities of the first 7 Catalan numbers using the grammar with even probabilities for the 2 rules<jupyter_output><empty_output><jupyter_text>Using the binary tree grammar with copying<jupyter_code>g = grammar_ambig_copy
s = ["a"]*3
chart,backpointers = cky.parse(s,g)
cky.print_chart(chart)
cky.pretty_print_backpointers(backpointers,g) 
cky.n_parses("S",chart,backpointers,g,s)
parses = cky.collect_trees("S",chart,backpointers,g,s)
for i,parse in enumerate(parses):    
    cky.tree_to_png(parse,"parse_%i.png"%i)
a=Image(filename='parse_0.png')
b=Image(filename='parse_1.png')
c=Image(filename='parse_2.png')
d=Image(filename='parse_3.png')
e=Image(filename='parse_4.png')
f=Image(filename='parse_5.png')
h=Image(filename='parse_6.png')


display(a,b,c,d,e,f,h)<jupyter_output><empty_output><jupyter_text>Probability of sentence<jupyter_code>g_probs = cky.make_rule_probs(grammar_ambig_copy_probs)
(probs,s_prob)=cky.probability("S",chart,backpointers,g,s,g_probs)<jupyter_output><empty_output><jupyter_text>The log probability of the sentence is the second element<jupyter_code>s_prob<jupyter_output><empty_output><jupyter_text>Let's un-log it just to get a look<jupyter_code>cky.np.exp(s_prob)<jupyter_output><empty_output><jupyter_text>Let's try with sentence aaaa<jupyter_code>s = ["a"]*4
chart,backpointers = cky.parse(s,g)
cky.print_chart(chart)
cky.print_backpointers(backpointers) 
cky.n_parses("S",chart,backpointers,g,s) ## 35 PARSES!
parses = cky.collect_trees("S",chart,backpointers,g,s)
for i,parse in enumerate(parses[:5]):    ## let's just look at the first 5
    cky.tree_to_png(parse,"parse_%i.png"%i)
a=Image(filename='parse_0.png')
b=Image(filename='parse_1.png')
c=Image(filename='parse_2.png')
d=Image(filename='parse_3.png')
e=Image(filename='parse_4.png')

display(a,b,c,d,e)<jupyter_output><empty_output><jupyter_text>Probability of sentence<jupyter_code>g_probs = cky.make_rule_probs(grammar_ambig_copy_probs)
(probs,s_prob)=cky.probability("S",chart,backpointers,g,s,g_probs)<jupyter_output><empty_output><jupyter_text>The log probability of the sentence is the second element<jupyter_code>s_prob<jupyter_output><empty_output><jupyter_text>Let's un-log it just to get a look<jupyter_code>cky.np.exp(s_prob)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.15522894290559638, 'fraction_numerical': 0.026568682871678916, 'mean_word_length': 5.547742413027387, 'pattern_counts': {'":': 0, '<': 101, '<?xml version=': 0, '>': 102, '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': '25', 'dir': 'jupyter-structured-clean-dedup', 'id': '499905', 'license': 'BSD-3-Clause-Clear', 'n_tokens_mistral': 3431, 'n_tokens_neox': 3203, 'n_words': 641, 'path': 'ckypy/cky.ipynb', 'repo_name': 'megodoonch/birdsong', 'size': '8845'}