Registered S3 methods overwritten by 'htmltools':
  method               from         
  print.html           tools:rstudio
  print.shiny.tag      tools:rstudio
  print.shiny.tag.list tools:rstudio

1. Introducción al Aprendizaje Profundo

Según Norvig y Russell (2019), el aprendizaje profundo, como un subcampo del aprendizaje automático y de la inteligencia artificial toma un nuevo enfoque sobre la tarea de aprender los patrones de distintas representaciones de datos. Dentro del procesamiento del lenguaje natural, el aprendizaje profundo también ha logrado generar nuevas oportunidades para resolver distintos tipos de problemas, y entre ellos se encuentran los modelos secuencia a secuencia, de los cuales haremos una brevísima introducción a continuación.

2. Introducción a los modelos secuencia a secuencia

El aprendizaje secuencia a secuencia, acorde a la página de Keras se trata de entrenar modelos que conviertan secuencias de un dominio en secuencias de otro dominio. Esto se aplica por ejemplo en la traducción automática, la respuesta rápida a preguntas y la predicción de texto.

Para llevar a cabo tal tarea, existen muchas maneras de manejarlas, sea a través del uso de redes neuronales recurrentes o convolucionales de una sola dimensión. En el caso de estudio que tenemos utilizaremos redes neuronales recurrentes.

3. Caso de estudio

Y para la predicción de texto, usaremos los relatos de Howard Phillips Lovecraft, ya visitados en capítulos anteriores.

En primer lugar, cargaremos los datos y tokenizaremos las oraciones, para identificar cada una de ellas como un documento. Si quisieramos podríamos tokenizar por cualquier tipo de n-grama y ver cómo los resultados varían (así como su tiempo de computación).

library(keras)
library(tm)
library(tidyverse)
library(tidytext)

# Carga de datos
necronomicon_df = readRDS("Caso2_Literatura/NecronomiconDF.RDS") %>% 
  mutate(Historia=removeNumbers(Historia)) %>% 
  mutate(Historia=str_squish(Historia)) %>% 
  filter(!is.na(Historia), Historia!="") %>% 
  filter(Titulo %in% c("La Sombra Sobre Insmouth", "La Ciudad Sin Nombre","La Llamada De Cthulhu")) %>% 
  unnest_tokens(token, Historia, token = "sentences")
necronomicon_df %>% head()

Una vez separados los datos en la unidad de análisis necesaria, crearemos secuencias numéricas con estos textos a través de la creación de un diccionario de palabras.

# Función de tokenizado y creación de secuencias
get_sequence_tokens = function(corpus){
  # Inicialización de tokenizador
  tokenizer = text_tokenizer()
  # Tokenizado
  fit_text_tokenizer(tokenizer, corpus)
  # Total de palabras
  total_words = length(tokenizer$word_index)+1 
  # Parámetros de iteración para cada línea del corpus
  input_sequences = list()
  total = corpus %>% length()
  n = 0
  for (line in corpus){
    n = n+1
    if((round(n/total,4)*100)%%10==0){cat(round(n/total,4)*100,"% avanzado\n")}
    # Paso del texto a secuencia numérica
    token_list = texts_to_sequences(tokenizer, line)[[1]]
    # Poblado de la lista de secuencias
    input_sequences = c(input_sequences,map(1:(length(token_list)-1),function(x)tok_vec = token_list[1:(x+1)]))
  }
  result = list("input_sequences"=input_sequences, "total_words"=total_words, "tokenizer"=tokenizer)
  return(result)
}

# Ejecución de función
inp_seq_tot_words = get_sequence_tokens(necronomicon_df$token)
10 % avanzado
20 % avanzado
30 % avanzado
40 % avanzado
50 % avanzado
60 % avanzado
70 % avanzado
80 % avanzado
90 % avanzado
100 % avanzado
inp_seq_tot_words$input_sequences[1]
[[1]]
[1]   19 1546

Con las secuencias elaborados creamos un arreglo de dos dimensiones tanto para las variables explicativas (el inicio de la secuencia) como para la variable output (el último paso de la secuencia), rellenando con cero cada vector, a fin de que todas las secuencias tengan el mismo largo.

# Función para padding de secuencias y transformación en array
gen_padded_sequences = function(input_sequences, total_words){
  # Largo máximo de secuencia (palabras en un tweet)
  max_sequence_len = max(map_int(input_sequences, length))
  # Creación de array con padding (llenado de ceros para crear secuencias del mismo largo)
  padded_input_sequences = array(pad_sequences(input_sequences, maxlen = max_sequence_len, padding = "pre"), 
                                 dim = c(length(input_sequences),max_sequence_len))
  # Creación de variables predictoras (hasta la penúltima columna de la secuencia)
  predictors = padded_input_sequences[,1:(ncol(padded_input_sequences)-1)]
  # Creación de variable a predecir (última columna de la secuencia)
  label = padded_input_sequences[,(ncol(padded_input_sequences)-1),drop=F]
  label = to_categorical(label, num_classes = total_words)
  result = list("predictors"=predictors, "label"=label, "max_sequence_len"=max_sequence_len)
  return(result)
}

# Ejecución de función
pad_seq = gen_padded_sequences(inp_seq_tot_words$input_sequences, inp_seq_tot_words$total_words)
pad_seq$predictors[1:6,1:6]
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    0    0    0    0    0    0
[2,]    0    0    0    0    0    0
[3,]    0    0    0    0    0    0
[4,]    0    0    0    0    0    0
[5,]    0    0    0    0    0    0
[6,]    0    0    0    0    0    0

Una vez creados los arreglos creamos un modelo con una capa de embedding, una capa recurrente del tipo LSTM y algunas capas densas que afinen la predicción.

# Función para creación de modelo
create_model = function(max_sequence_len, total_words){
  input_len = max_sequence_len - 1
  # Inicialización del modelo
  model = keras_model_sequential() %>% 
    # Capa de embedding (vectores densos)
    layer_embedding(input_dim = total_words, output_dim = 10, input_length = input_len) %>% 
    # Capa recurrente LSTM
    layer_lstm(units = 100) %>% 
    # Capa densa
    layer_dense(units = 100, activation = "relu") %>% 
    # Capa de salida
    layer_dense(units = total_words, activation = "softmax") %>% 
    # Compilación
    compile(loss="categorical_crossentropy", optimizer = "adam")
  return(model)
}

# Ejecución de función
model = create_model(pad_seq$max_sequence_len, inp_seq_tot_words$total_words)
model
Model
Model: "sequential_1"
_____________________________________________________________________________________________________________________________________
Layer (type)                                               Output Shape                                          Param #             
=====================================================================================================================================
embedding_1 (Embedding)                                    (None, 98, 10)                                        84060               
_____________________________________________________________________________________________________________________________________
lstm_1 (LSTM)                                              (None, 100)                                           44400               
_____________________________________________________________________________________________________________________________________
dense_3 (Dense)                                            (None, 100)                                           10100               
_____________________________________________________________________________________________________________________________________
dense_2 (Dense)                                            (None, 8406)                                          849006              
=====================================================================================================================================
Total params: 987,566
Trainable params: 987,566
Non-trainable params: 0
_____________________________________________________________________________________________________________________________________

Luego entrenamos el modelo hasta que este converja.

# Entrenamiento del modelo
fit(model, x = pad_seq$predictors, y = pad_seq$label, epochs=130, batch_size=1024, verbose = 2)
Epoch 1/130
44/44 - 50s - loss: 7.9144
44/44 - 51s - loss: 7.9144
Epoch 2/130
44/44 - 53s - loss: 6.7565
44/44 - 54s - loss: 6.7565
Epoch 3/130
44/44 - 55s - loss: 6.6429
44/44 - 55s - loss: 6.6429
Epoch 4/130
44/44 - 62s - loss: 6.5144
44/44 - 63s - loss: 6.5144
Epoch 5/130
44/44 - 56s - loss: 6.3300
44/44 - 57s - loss: 6.3300
Epoch 6/130
44/44 - 55s - loss: 6.1860
44/44 - 56s - loss: 6.1860
Epoch 7/130
44/44 - 55s - loss: 6.0721
44/44 - 56s - loss: 6.0721
Epoch 8/130
44/44 - 54s - loss: 5.9488
44/44 - 55s - loss: 5.9488
Epoch 9/130
44/44 - 55s - loss: 5.8163
44/44 - 55s - loss: 5.8163
Epoch 10/130
44/44 - 55s - loss: 5.6814
44/44 - 55s - loss: 5.6814
Epoch 11/130
44/44 - 55s - loss: 5.5556
44/44 - 56s - loss: 5.5556
Epoch 12/130
44/44 - 57s - loss: 5.4385
44/44 - 58s - loss: 5.4385
Epoch 13/130
44/44 - 55s - loss: 5.3292
44/44 - 56s - loss: 5.3292
Epoch 14/130
44/44 - 55s - loss: 5.2289
44/44 - 55s - loss: 5.2289
Epoch 15/130
44/44 - 55s - loss: 5.1253
44/44 - 56s - loss: 5.1253
Epoch 16/130
44/44 - 57s - loss: 4.9936
44/44 - 58s - loss: 4.9936
Epoch 17/130
44/44 - 57s - loss: 4.7963
44/44 - 57s - loss: 4.7963
Epoch 18/130
44/44 - 57s - loss: 4.5773
44/44 - 57s - loss: 4.5773
Epoch 19/130
44/44 - 56s - loss: 4.3704
44/44 - 57s - loss: 4.3704
Epoch 20/130
44/44 - 53s - loss: 4.1887
44/44 - 53s - loss: 4.1887
Epoch 21/130
44/44 - 54s - loss: 4.0299
44/44 - 54s - loss: 4.0299
Epoch 22/130
44/44 - 53s - loss: 3.8860
44/44 - 53s - loss: 3.8860
Epoch 23/130
44/44 - 52s - loss: 3.7602
44/44 - 52s - loss: 3.7602
Epoch 24/130
44/44 - 52s - loss: 3.6459
44/44 - 53s - loss: 3.6459
Epoch 25/130
44/44 - 52s - loss: 3.5480
44/44 - 52s - loss: 3.5480
Epoch 26/130
44/44 - 52s - loss: 3.4518
44/44 - 52s - loss: 3.4518
Epoch 27/130
44/44 - 55s - loss: 3.3678
44/44 - 55s - loss: 3.3678
Epoch 28/130
44/44 - 52s - loss: 3.2865
44/44 - 53s - loss: 3.2865
Epoch 29/130
44/44 - 52s - loss: 3.2115
44/44 - 52s - loss: 3.2115
Epoch 30/130
44/44 - 52s - loss: 3.1455
44/44 - 53s - loss: 3.1455
Epoch 31/130
44/44 - 53s - loss: 3.0741
44/44 - 53s - loss: 3.0741
Epoch 32/130
44/44 - 52s - loss: 3.0034
44/44 - 53s - loss: 3.0034
Epoch 33/130
44/44 - 53s - loss: 2.9222
44/44 - 53s - loss: 2.9222
Epoch 34/130
44/44 - 53s - loss: 2.8389
44/44 - 53s - loss: 2.8389
Epoch 35/130
44/44 - 53s - loss: 2.7516
44/44 - 53s - loss: 2.7516
Epoch 36/130
44/44 - 53s - loss: 2.6695
44/44 - 54s - loss: 2.6695
Epoch 37/130
44/44 - 53s - loss: 2.5956
44/44 - 53s - loss: 2.5956
Epoch 38/130
44/44 - 53s - loss: 2.5280
44/44 - 53s - loss: 2.5280
Epoch 39/130
44/44 - 59s - loss: 2.4695
44/44 - 60s - loss: 2.4695
Epoch 40/130
44/44 - 62s - loss: 2.4154
44/44 - 62s - loss: 2.4154
Epoch 41/130
44/44 - 54s - loss: 2.3586
44/44 - 54s - loss: 2.3586
Epoch 42/130
44/44 - 52s - loss: 2.3077
44/44 - 52s - loss: 2.3077
Epoch 43/130
44/44 - 71s - loss: 2.2556
44/44 - 72s - loss: 2.2556
Epoch 44/130
44/44 - 64s - loss: 2.2026
44/44 - 65s - loss: 2.2026
Epoch 45/130
44/44 - 59s - loss: 2.1489
44/44 - 60s - loss: 2.1489
Epoch 46/130
44/44 - 60s - loss: 2.0947
44/44 - 61s - loss: 2.0947
Epoch 47/130
44/44 - 60s - loss: 2.0423
44/44 - 60s - loss: 2.0423
Epoch 48/130
44/44 - 62s - loss: 1.9822
44/44 - 62s - loss: 1.9822
Epoch 49/130
44/44 - 67s - loss: 1.9299
44/44 - 68s - loss: 1.9299
Epoch 50/130
44/44 - 65s - loss: 1.8750
44/44 - 66s - loss: 1.8750
Epoch 51/130
44/44 - 61s - loss: 1.8223
44/44 - 61s - loss: 1.8223
Epoch 52/130
44/44 - 62s - loss: 1.7732
44/44 - 62s - loss: 1.7732
Epoch 53/130
44/44 - 63s - loss: 1.7231
44/44 - 63s - loss: 1.7231
Epoch 54/130
44/44 - 62s - loss: 1.6800
44/44 - 63s - loss: 1.6800
Epoch 55/130
44/44 - 61s - loss: 1.6341
44/44 - 61s - loss: 1.6341
Epoch 56/130
44/44 - 62s - loss: 1.5937
44/44 - 63s - loss: 1.5937
Epoch 57/130
44/44 - 61s - loss: 1.5530
44/44 - 61s - loss: 1.5530
Epoch 58/130
44/44 - 61s - loss: 1.5125
44/44 - 61s - loss: 1.5125
Epoch 59/130
44/44 - 61s - loss: 1.4746
44/44 - 62s - loss: 1.4746
Epoch 60/130
44/44 - 62s - loss: 1.4426
44/44 - 63s - loss: 1.4426
Epoch 61/130
44/44 - 75s - loss: 1.4051
44/44 - 76s - loss: 1.4051
Epoch 62/130
44/44 - 79s - loss: 1.3744
44/44 - 80s - loss: 1.3744
Epoch 63/130
44/44 - 80s - loss: 1.3411
44/44 - 80s - loss: 1.3411
Epoch 64/130
44/44 - 80s - loss: 1.3113
44/44 - 81s - loss: 1.3113
Epoch 65/130
44/44 - 81s - loss: 1.2823
44/44 - 81s - loss: 1.2823
Epoch 66/130
44/44 - 80s - loss: 1.2516
44/44 - 80s - loss: 1.2516
Epoch 67/130
44/44 - 80s - loss: 1.2246
44/44 - 81s - loss: 1.2246
Epoch 68/130
44/44 - 81s - loss: 1.1986
44/44 - 82s - loss: 1.1986
Epoch 69/130
44/44 - 81s - loss: 1.1734
44/44 - 81s - loss: 1.1734
Epoch 70/130
44/44 - 82s - loss: 1.1486
44/44 - 82s - loss: 1.1486
Epoch 71/130
44/44 - 81s - loss: 1.1240
44/44 - 81s - loss: 1.1240
Epoch 72/130
44/44 - 80s - loss: 1.1007
44/44 - 80s - loss: 1.1007
Epoch 73/130
44/44 - 80s - loss: 1.0793
44/44 - 80s - loss: 1.0793
Epoch 74/130
44/44 - 80s - loss: 1.0536
44/44 - 81s - loss: 1.0536
Epoch 75/130
44/44 - 80s - loss: 1.0334
44/44 - 80s - loss: 1.0334
Epoch 76/130
44/44 - 80s - loss: 1.0124
44/44 - 81s - loss: 1.0124
Epoch 77/130
44/44 - 81s - loss: 0.9920
44/44 - 81s - loss: 0.9920
Epoch 78/130
44/44 - 79s - loss: 0.9705
44/44 - 80s - loss: 0.9705
Epoch 79/130
44/44 - 83s - loss: 0.9507
44/44 - 83s - loss: 0.9507
Epoch 80/130
44/44 - 81s - loss: 0.9302
44/44 - 81s - loss: 0.9302
Epoch 81/130
44/44 - 80s - loss: 0.9104
44/44 - 81s - loss: 0.9104
Epoch 82/130
44/44 - 82s - loss: 0.8923
44/44 - 82s - loss: 0.8923
Epoch 83/130
44/44 - 82s - loss: 0.8721
44/44 - 82s - loss: 0.8721
Epoch 84/130
44/44 - 82s - loss: 0.8521
44/44 - 82s - loss: 0.8521
Epoch 85/130
44/44 - 82s - loss: 0.8342
44/44 - 82s - loss: 0.8342
Epoch 86/130
44/44 - 69s - loss: 0.8141
44/44 - 69s - loss: 0.8141
Epoch 87/130
44/44 - 69s - loss: 0.7965
44/44 - 69s - loss: 0.7965
Epoch 88/130
44/44 - 66s - loss: 0.7751
44/44 - 66s - loss: 0.7751
Epoch 89/130
44/44 - 67s - loss: 0.7577
44/44 - 68s - loss: 0.7577
Epoch 90/130
44/44 - 64s - loss: 0.7357
44/44 - 64s - loss: 0.7357
Epoch 91/130
44/44 - 63s - loss: 0.7200
44/44 - 63s - loss: 0.7200
Epoch 92/130
44/44 - 66s - loss: 0.6992
44/44 - 67s - loss: 0.6992
Epoch 93/130
44/44 - 65s - loss: 0.6848
44/44 - 65s - loss: 0.6848
Epoch 94/130
44/44 - 66s - loss: 0.6673
44/44 - 66s - loss: 0.6673
Epoch 95/130
44/44 - 75s - loss: 0.6509
44/44 - 75s - loss: 0.6509
Epoch 96/130
44/44 - 72s - loss: 0.6343
44/44 - 73s - loss: 0.6343
Epoch 97/130
44/44 - 54s - loss: 0.6200
44/44 - 55s - loss: 0.6200
Epoch 98/130
44/44 - 55s - loss: 0.6028
44/44 - 55s - loss: 0.6028
Epoch 99/130
44/44 - 55s - loss: 0.5866
44/44 - 55s - loss: 0.5866
Epoch 100/130
44/44 - 55s - loss: 0.5735
44/44 - 55s - loss: 0.5735
Epoch 101/130
44/44 - 58s - loss: 0.5600
44/44 - 58s - loss: 0.5600
Epoch 102/130
44/44 - 55s - loss: 0.5442
44/44 - 55s - loss: 0.5442
Epoch 103/130
44/44 - 54s - loss: 0.5291
44/44 - 54s - loss: 0.5291
Epoch 104/130
44/44 - 58s - loss: 0.5155
44/44 - 58s - loss: 0.5155
Epoch 105/130
44/44 - 57s - loss: 0.5017
44/44 - 57s - loss: 0.5017
Epoch 106/130
44/44 - 56s - loss: 0.4890
44/44 - 57s - loss: 0.4890
Epoch 107/130
44/44 - 56s - loss: 0.4772
44/44 - 56s - loss: 0.4772
Epoch 108/130
44/44 - 70s - loss: 0.4621
44/44 - 71s - loss: 0.4621
Epoch 109/130
44/44 - 63s - loss: 0.4530
44/44 - 63s - loss: 0.4530
Epoch 110/130
44/44 - 71s - loss: 0.4414
44/44 - 71s - loss: 0.4414
Epoch 111/130
44/44 - 65s - loss: 0.4295
44/44 - 65s - loss: 0.4295
Epoch 112/130
44/44 - 65s - loss: 0.4180
44/44 - 66s - loss: 0.4180
Epoch 113/130
44/44 - 67s - loss: 0.4059
44/44 - 68s - loss: 0.4059
Epoch 114/130
44/44 - 71s - loss: 0.3955
44/44 - 71s - loss: 0.3955
Epoch 115/130
44/44 - 72s - loss: 0.3837
44/44 - 72s - loss: 0.3837
Epoch 116/130
44/44 - 88s - loss: 0.3757
44/44 - 89s - loss: 0.3757
Epoch 117/130
44/44 - 92s - loss: 0.3650
44/44 - 93s - loss: 0.3650
Epoch 118/130
44/44 - 91s - loss: 0.3540
44/44 - 92s - loss: 0.3540
Epoch 119/130
44/44 - 90s - loss: 0.3459
44/44 - 91s - loss: 0.3459
Epoch 120/130
44/44 - 86s - loss: 0.3370
44/44 - 86s - loss: 0.3370
Epoch 121/130
44/44 - 87s - loss: 0.3275
44/44 - 88s - loss: 0.3275
Epoch 122/130
44/44 - 86s - loss: 0.3191
44/44 - 87s - loss: 0.3191
Epoch 123/130
44/44 - 85s - loss: 0.3093
44/44 - 86s - loss: 0.3093
Epoch 124/130
44/44 - 86s - loss: 0.3015
44/44 - 86s - loss: 0.3015
Epoch 125/130
44/44 - 88s - loss: 0.2923
44/44 - 88s - loss: 0.2923
Epoch 126/130
44/44 - 86s - loss: 0.2833
44/44 - 87s - loss: 0.2833
Epoch 127/130
44/44 - 88s - loss: 0.2756
44/44 - 89s - loss: 0.2756
Epoch 128/130
44/44 - 85s - loss: 0.2678
44/44 - 86s - loss: 0.2678
Epoch 129/130
44/44 - 87s - loss: 0.2601
44/44 - 88s - loss: 0.2601
Epoch 130/130
44/44 - 83s - loss: 0.2538
44/44 - 83s - loss: 0.2538

Y observamos sus resultados.

# Ejecución
gen_text("Lejos de la superstición delirante", 5, model, pad_seq$max_sequence_len, inp_seq_tot_words$tokenizer)
[1] "Lejos de la superstición delirante árabe “culto hijas abandono observado"

3. Bibliografía

Norvig, S. & Russell, P. (2019), Artificial Intelligence A Modern Approach.
LS0tDQp0aXRsZTogIkFuw6FsaXNpcyBkZSBjb21wb3J0YW1pZW50byBlbiByZWRlcyBzb2NpYWxlcyB1c2FuZG8gUHJvY2VzYW1pZW50byBkZWwgTGVuZ3VhamUgTmF0dXJhbCINCnN1YnRpdGxlOiAnQ2Fww610dWxvIDEwOiBJbnRyb2R1Y2Npw7NuIGFsIGFwcmVuZGl6YWplIHByb2Z1bmRvIGRlbnRybyBkZWwgUExOJw0KYXV0aG9yOiBIdWdvIFBvcnJhcw0Kb3V0cHV0Og0KICBodG1sX25vdGVib29rOg0KICAgIGNzczogRXN0aWxvcy5jc3MNCiAgICB0b2M6IHRydWUNCiAgICB0b2NfZGVwdGg6IDINCiAgICB0b2NfZmxvYXQ6DQogICAgICBjb2xsYXBzZWQ6IHRydWUNCiAgICAgIHNtb290aF9zY3JvbGw6IGZhbHNlDQpiaWJsaW9ncmFwaHk6IEJpYmxpb2dyYWZpYS5iaWINCmNzbDogY2VwYWwueG1sDQotLS0NCg0KYGBge3IgZWNobz1GLCBtZXNzYWdlPUYsIHdhcm5pbmc9RiwgZXJyb3I9RkFMU0V9DQpsaWJyYXJ5KGthYmxlRXh0cmEpDQpgYGANCg0KDQojICoqMS4gSW50cm9kdWNjacOzbiBhbCBBcHJlbmRpemFqZSBQcm9mdW5kbyoqDQoNClNlZ8O6biBATm9ydmlnMjAxOSwgZWwgYXByZW5kaXphamUgcHJvZnVuZG8sIGNvbW8gdW4gc3ViY2FtcG8gZGVsIGFwcmVuZGl6YWplIGF1dG9tw6F0aWNvIHkgZGUgbGEgaW50ZWxpZ2VuY2lhIGFydGlmaWNpYWwgdG9tYSB1biBudWV2byBlbmZvcXVlIHNvYnJlIGxhIHRhcmVhIGRlIGFwcmVuZGVyIGxvcyBwYXRyb25lcyBkZSBkaXN0aW50YXMgcmVwcmVzZW50YWNpb25lcyBkZSBkYXRvcy4gRGVudHJvIGRlbCBwcm9jZXNhbWllbnRvIGRlbCBsZW5ndWFqZSBuYXR1cmFsLCBlbCBhcHJlbmRpemFqZSBwcm9mdW5kbyB0YW1iacOpbiBoYSBsb2dyYWRvIGdlbmVyYXIgbnVldmFzIG9wb3J0dW5pZGFkZXMgcGFyYSByZXNvbHZlciBkaXN0aW50b3MgdGlwb3MgZGUgcHJvYmxlbWFzLCB5IGVudHJlIGVsbG9zIHNlIGVuY3VlbnRyYW4gbG9zIG1vZGVsb3Mgc2VjdWVuY2lhIGEgc2VjdWVuY2lhLCBkZSBsb3MgY3VhbGVzIGhhcmVtb3MgdW5hIGJyZXbDrXNpbWEgaW50cm9kdWNjacOzbiBhIGNvbnRpbnVhY2nDs24uDQoNCiFbXShmaWdzLzEwX2RsbmxwLnBuZykNCg0KIyAqKjIuIEludHJvZHVjY2nDs24gYSBsb3MgbW9kZWxvcyBzZWN1ZW5jaWEgYSBzZWN1ZW5jaWEqKg0KDQpFbCBhcHJlbmRpemFqZSBzZWN1ZW5jaWEgYSBzZWN1ZW5jaWEsIGFjb3JkZSBhIGxhIHDDoWdpbmEgZGUgW0tlcmFzXShodHRwczovL2Jsb2cua2VyYXMuaW8vYS10ZW4tbWludXRlLWludHJvZHVjdGlvbi10by1zZXF1ZW5jZS10by1zZXF1ZW5jZS1sZWFybmluZy1pbi1rZXJhcy5odG1sKSBzZSB0cmF0YSBkZSBlbnRyZW5hciBtb2RlbG9zIHF1ZSBjb252aWVydGFuIHNlY3VlbmNpYXMgZGUgdW4gZG9taW5pbyBlbiBzZWN1ZW5jaWFzIGRlIG90cm8gZG9taW5pby4gRXN0byBzZSBhcGxpY2EgcG9yIGVqZW1wbG8gZW4gbGEgdHJhZHVjY2nDs24gYXV0b23DoXRpY2EsIGxhIHJlc3B1ZXN0YSByw6FwaWRhIGEgcHJlZ3VudGFzIHkgbGEgcHJlZGljY2nDs24gZGUgdGV4dG8uDQoNClBhcmEgbGxldmFyIGEgY2FibyB0YWwgdGFyZWEsIGV4aXN0ZW4gbXVjaGFzIG1hbmVyYXMgZGUgbWFuZWphcmxhcywgc2VhIGEgdHJhdsOpcyBkZWwgdXNvIGRlIHJlZGVzIG5ldXJvbmFsZXMgcmVjdXJyZW50ZXMgbyBjb252b2x1Y2lvbmFsZXMgZGUgdW5hIHNvbGEgZGltZW5zacOzbi4gRW4gZWwgY2FzbyBkZSBlc3R1ZGlvIHF1ZSB0ZW5lbW9zIHV0aWxpemFyZW1vcyByZWRlcyBuZXVyb25hbGVzIHJlY3VycmVudGVzLg0KDQohW10oZmlncy8xMF90ZXh0cHJlZGljdC5wbmcpDQoNCiMgKiozLiBDYXNvIGRlIGVzdHVkaW8qKg0KDQpZIHBhcmEgbGEgcHJlZGljY2nDs24gZGUgdGV4dG8sIHVzYXJlbW9zIGxvcyByZWxhdG9zIGRlIEhvd2FyZCBQaGlsbGlwcyBMb3ZlY3JhZnQsIHlhIHZpc2l0YWRvcyBlbiBjYXDDrXR1bG9zIGFudGVyaW9yZXMuDQoNCkVuIHByaW1lciBsdWdhciwgY2FyZ2FyZW1vcyBsb3MgZGF0b3MgeSB0b2tlbml6YXJlbW9zIGxhcyBvcmFjaW9uZXMsIHBhcmEgaWRlbnRpZmljYXIgY2FkYSB1bmEgZGUgZWxsYXMgY29tbyB1biBkb2N1bWVudG8uIFNpIHF1aXNpZXJhbW9zIHBvZHLDrWFtb3MgdG9rZW5pemFyIHBvciBjdWFscXVpZXIgdGlwbyBkZSBuLWdyYW1hIHkgdmVyIGPDs21vIGxvcyByZXN1bHRhZG9zIHZhcsOtYW4gKGFzw60gY29tbyBzdSB0aWVtcG8gZGUgY29tcHV0YWNpw7NuKS4NCg0KYGBge3J9DQpsaWJyYXJ5KGtlcmFzKQ0KbGlicmFyeSh0bSkNCmxpYnJhcnkodGlkeXZlcnNlKQ0KbGlicmFyeSh0aWR5dGV4dCkNCg0KIyBDYXJnYSBkZSBkYXRvcw0KbmVjcm9ub21pY29uX2RmID0gcmVhZFJEUygiQ2FzbzJfTGl0ZXJhdHVyYS9OZWNyb25vbWljb25ERi5SRFMiKSAlPiUgDQogIG11dGF0ZShIaXN0b3JpYT1yZW1vdmVOdW1iZXJzKEhpc3RvcmlhKSkgJT4lIA0KICBtdXRhdGUoSGlzdG9yaWE9c3RyX3NxdWlzaChIaXN0b3JpYSkpICU+JSANCiAgZmlsdGVyKCFpcy5uYShIaXN0b3JpYSksIEhpc3RvcmlhIT0iIikgJT4lIA0KICBmaWx0ZXIoVGl0dWxvICVpbiUgYygiTGEgU29tYnJhIFNvYnJlIEluc21vdXRoIiwgIkxhIENpdWRhZCBTaW4gTm9tYnJlIiwiTGEgTGxhbWFkYSBEZSBDdGh1bGh1IikpICU+JSANCiAgdW5uZXN0X3Rva2Vucyh0b2tlbiwgSGlzdG9yaWEsIHRva2VuID0gInNlbnRlbmNlcyIpDQpuZWNyb25vbWljb25fZGYgJT4lIGhlYWQoKQ0KYGBgDQoNClVuYSB2ZXogc2VwYXJhZG9zIGxvcyBkYXRvcyBlbiBsYSB1bmlkYWQgZGUgYW7DoWxpc2lzIG5lY2VzYXJpYSwgY3JlYXJlbW9zIHNlY3VlbmNpYXMgbnVtw6lyaWNhcyBjb24gZXN0b3MgdGV4dG9zIGEgdHJhdsOpcyBkZSBsYSBjcmVhY2nDs24gZGUgdW4gZGljY2lvbmFyaW8gZGUgcGFsYWJyYXMuDQoNCmBgYHtyfQ0KIyBGdW5jacOzbiBkZSB0b2tlbml6YWRvIHkgY3JlYWNpw7NuIGRlIHNlY3VlbmNpYXMNCmdldF9zZXF1ZW5jZV90b2tlbnMgPSBmdW5jdGlvbihjb3JwdXMpew0KICAjIEluaWNpYWxpemFjacOzbiBkZSB0b2tlbml6YWRvcg0KICB0b2tlbml6ZXIgPSB0ZXh0X3Rva2VuaXplcigpDQogICMgVG9rZW5pemFkbw0KICBmaXRfdGV4dF90b2tlbml6ZXIodG9rZW5pemVyLCBjb3JwdXMpDQogICMgVG90YWwgZGUgcGFsYWJyYXMNCiAgdG90YWxfd29yZHMgPSBsZW5ndGgodG9rZW5pemVyJHdvcmRfaW5kZXgpKzEgDQogICMgUGFyw6FtZXRyb3MgZGUgaXRlcmFjacOzbiBwYXJhIGNhZGEgbMOtbmVhIGRlbCBjb3JwdXMNCiAgaW5wdXRfc2VxdWVuY2VzID0gbGlzdCgpDQogIHRvdGFsID0gY29ycHVzICU+JSBsZW5ndGgoKQ0KICBuID0gMA0KICBmb3IgKGxpbmUgaW4gY29ycHVzKXsNCiAgICBuID0gbisxDQogICAgaWYoKHJvdW5kKG4vdG90YWwsNCkqMTAwKSUlMTA9PTApe2NhdChyb3VuZChuL3RvdGFsLDQpKjEwMCwiJSBhdmFuemFkb1xuIil9DQogICAgIyBQYXNvIGRlbCB0ZXh0byBhIHNlY3VlbmNpYSBudW3DqXJpY2ENCiAgICB0b2tlbl9saXN0ID0gdGV4dHNfdG9fc2VxdWVuY2VzKHRva2VuaXplciwgbGluZSlbWzFdXQ0KICAgICMgUG9ibGFkbyBkZSBsYSBsaXN0YSBkZSBzZWN1ZW5jaWFzDQogICAgaW5wdXRfc2VxdWVuY2VzID0gYyhpbnB1dF9zZXF1ZW5jZXMsbWFwKDE6KGxlbmd0aCh0b2tlbl9saXN0KS0xKSxmdW5jdGlvbih4KXRva192ZWMgPSB0b2tlbl9saXN0WzE6KHgrMSldKSkNCiAgfQ0KICByZXN1bHQgPSBsaXN0KCJpbnB1dF9zZXF1ZW5jZXMiPWlucHV0X3NlcXVlbmNlcywgInRvdGFsX3dvcmRzIj10b3RhbF93b3JkcywgInRva2VuaXplciI9dG9rZW5pemVyKQ0KICByZXR1cm4ocmVzdWx0KQ0KfQ0KDQojIEVqZWN1Y2nDs24gZGUgZnVuY2nDs24NCmlucF9zZXFfdG90X3dvcmRzID0gZ2V0X3NlcXVlbmNlX3Rva2VucyhuZWNyb25vbWljb25fZGYkdG9rZW4pDQppbnBfc2VxX3RvdF93b3JkcyRpbnB1dF9zZXF1ZW5jZXNbMV0NCmBgYA0KDQpDb24gbGFzIHNlY3VlbmNpYXMgZWxhYm9yYWRvcyBjcmVhbW9zIHVuIGFycmVnbG8gZGUgZG9zIGRpbWVuc2lvbmVzIHRhbnRvIHBhcmEgbGFzIHZhcmlhYmxlcyBleHBsaWNhdGl2YXMgKGVsIGluaWNpbyBkZSBsYSBzZWN1ZW5jaWEpIGNvbW8gcGFyYSBsYSB2YXJpYWJsZSBvdXRwdXQgKGVsIMO6bHRpbW8gcGFzbyBkZSBsYSBzZWN1ZW5jaWEpLCByZWxsZW5hbmRvIGNvbiBjZXJvIGNhZGEgdmVjdG9yLCBhIGZpbiBkZSBxdWUgdG9kYXMgbGFzIHNlY3VlbmNpYXMgdGVuZ2FuIGVsIG1pc21vIGxhcmdvLg0KDQpgYGB7cn0NCiMgRnVuY2nDs24gcGFyYSBwYWRkaW5nIGRlIHNlY3VlbmNpYXMgeSB0cmFuc2Zvcm1hY2nDs24gZW4gYXJyYXkNCmdlbl9wYWRkZWRfc2VxdWVuY2VzID0gZnVuY3Rpb24oaW5wdXRfc2VxdWVuY2VzLCB0b3RhbF93b3Jkcyl7DQogICMgTGFyZ28gbcOheGltbyBkZSBzZWN1ZW5jaWEgKHBhbGFicmFzIGVuIHVuIHR3ZWV0KQ0KICBtYXhfc2VxdWVuY2VfbGVuID0gbWF4KG1hcF9pbnQoaW5wdXRfc2VxdWVuY2VzLCBsZW5ndGgpKQ0KICAjIENyZWFjacOzbiBkZSBhcnJheSBjb24gcGFkZGluZyAobGxlbmFkbyBkZSBjZXJvcyBwYXJhIGNyZWFyIHNlY3VlbmNpYXMgZGVsIG1pc21vIGxhcmdvKQ0KICBwYWRkZWRfaW5wdXRfc2VxdWVuY2VzID0gYXJyYXkocGFkX3NlcXVlbmNlcyhpbnB1dF9zZXF1ZW5jZXMsIG1heGxlbiA9IG1heF9zZXF1ZW5jZV9sZW4sIHBhZGRpbmcgPSAicHJlIiksIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZGltID0gYyhsZW5ndGgoaW5wdXRfc2VxdWVuY2VzKSxtYXhfc2VxdWVuY2VfbGVuKSkNCiAgIyBDcmVhY2nDs24gZGUgdmFyaWFibGVzIHByZWRpY3RvcmFzIChoYXN0YSBsYSBwZW7Dumx0aW1hIGNvbHVtbmEgZGUgbGEgc2VjdWVuY2lhKQ0KICBwcmVkaWN0b3JzID0gcGFkZGVkX2lucHV0X3NlcXVlbmNlc1ssMToobmNvbChwYWRkZWRfaW5wdXRfc2VxdWVuY2VzKS0xKV0NCiAgIyBDcmVhY2nDs24gZGUgdmFyaWFibGUgYSBwcmVkZWNpciAow7psdGltYSBjb2x1bW5hIGRlIGxhIHNlY3VlbmNpYSkNCiAgbGFiZWwgPSBwYWRkZWRfaW5wdXRfc2VxdWVuY2VzWywobmNvbChwYWRkZWRfaW5wdXRfc2VxdWVuY2VzKS0xKSxkcm9wPUZdDQogIGxhYmVsID0gdG9fY2F0ZWdvcmljYWwobGFiZWwsIG51bV9jbGFzc2VzID0gdG90YWxfd29yZHMpDQogIHJlc3VsdCA9IGxpc3QoInByZWRpY3RvcnMiPXByZWRpY3RvcnMsICJsYWJlbCI9bGFiZWwsICJtYXhfc2VxdWVuY2VfbGVuIj1tYXhfc2VxdWVuY2VfbGVuKQ0KICByZXR1cm4ocmVzdWx0KQ0KfQ0KDQojIEVqZWN1Y2nDs24gZGUgZnVuY2nDs24NCnBhZF9zZXEgPSBnZW5fcGFkZGVkX3NlcXVlbmNlcyhpbnBfc2VxX3RvdF93b3JkcyRpbnB1dF9zZXF1ZW5jZXMsIGlucF9zZXFfdG90X3dvcmRzJHRvdGFsX3dvcmRzKQ0KcGFkX3NlcSRwcmVkaWN0b3JzWzE6NiwxOjZdDQpgYGANCg0KVW5hIHZleiBjcmVhZG9zIGxvcyBhcnJlZ2xvcyBjcmVhbW9zIHVuIG1vZGVsbyBjb24gdW5hIGNhcGEgZGUgZW1iZWRkaW5nLCB1bmEgY2FwYSByZWN1cnJlbnRlIGRlbCB0aXBvIExTVE0geSBhbGd1bmFzIGNhcGFzIGRlbnNhcyBxdWUgYWZpbmVuIGxhIHByZWRpY2Npw7NuLg0KDQpgYGB7cn0NCiMgRnVuY2nDs24gcGFyYSBjcmVhY2nDs24gZGUgbW9kZWxvDQpjcmVhdGVfbW9kZWwgPSBmdW5jdGlvbihtYXhfc2VxdWVuY2VfbGVuLCB0b3RhbF93b3Jkcyl7DQogIGlucHV0X2xlbiA9IG1heF9zZXF1ZW5jZV9sZW4gLSAxDQogICMgSW5pY2lhbGl6YWNpw7NuIGRlbCBtb2RlbG8NCiAgbW9kZWwgPSBrZXJhc19tb2RlbF9zZXF1ZW50aWFsKCkgJT4lIA0KICAgICMgQ2FwYSBkZSBlbWJlZGRpbmcgKHZlY3RvcmVzIGRlbnNvcykNCiAgICBsYXllcl9lbWJlZGRpbmcoaW5wdXRfZGltID0gdG90YWxfd29yZHMsIG91dHB1dF9kaW0gPSAxMCwgaW5wdXRfbGVuZ3RoID0gaW5wdXRfbGVuKSAlPiUgDQogICAgIyBDYXBhIHJlY3VycmVudGUgTFNUTQ0KICAgIGxheWVyX2xzdG0odW5pdHMgPSAxMDApICU+JSANCiAgICAjIENhcGEgZGVuc2ENCiAgICBsYXllcl9kZW5zZSh1bml0cyA9IDEwMCwgYWN0aXZhdGlvbiA9ICJyZWx1IikgJT4lIA0KICAgICMgQ2FwYSBkZSBzYWxpZGENCiAgICBsYXllcl9kZW5zZSh1bml0cyA9IHRvdGFsX3dvcmRzLCBhY3RpdmF0aW9uID0gInNvZnRtYXgiKSAlPiUgDQogICAgIyBDb21waWxhY2nDs24NCiAgICBjb21waWxlKGxvc3M9ImNhdGVnb3JpY2FsX2Nyb3NzZW50cm9weSIsIG9wdGltaXplciA9ICJhZGFtIikNCiAgcmV0dXJuKG1vZGVsKQ0KfQ0KDQojIEVqZWN1Y2nDs24gZGUgZnVuY2nDs24NCm1vZGVsID0gY3JlYXRlX21vZGVsKHBhZF9zZXEkbWF4X3NlcXVlbmNlX2xlbiwgaW5wX3NlcV90b3Rfd29yZHMkdG90YWxfd29yZHMpDQptb2RlbA0KYGBgDQoNCkx1ZWdvIGVudHJlbmFtb3MgZWwgbW9kZWxvIGhhc3RhIHF1ZSBlc3RlIGNvbnZlcmphLg0KDQpgYGB7cn0NCiMgRW50cmVuYW1pZW50byBkZWwgbW9kZWxvDQpmaXQobW9kZWwsIHggPSBwYWRfc2VxJHByZWRpY3RvcnMsIHkgPSBwYWRfc2VxJGxhYmVsLCBlcG9jaHM9MTMwLCBiYXRjaF9zaXplPTEwMjQsIHZlcmJvc2UgPSAyKQ0KYGBgDQoNClkgb2JzZXJ2YW1vcyBzdXMgcmVzdWx0YWRvcy4NCg0KYGBge3J9DQojIEZ1bmNpw7NuIGRlIHByZWRpY2Npw7NuIGRlIHRleHRvIGEgcGFydGlyIGRlIHVuYSBzZWN1ZW5jaWENCmdlbl90ZXh0ID0gZnVuY3Rpb24odGV4dG9fc2VtaWxsYSwgbmV4dF93b3JkcywgbW9kZWwsIG1heF9zZXF1ZW5jZV9sZW4sIHRva2VuaXplcil7DQogIGZvciAoaSBpbiAxOm5leHRfd29yZHMpew0KICAgIHRva2VuX2xpc3QgPSB0ZXh0c190b19zZXF1ZW5jZXModG9rZW5pemVyLCB0ZXh0b19zZW1pbGxhKQ0KICAgIHRva2VuX2xpc3QgPSBwYWRfc2VxdWVuY2VzKHRva2VuX2xpc3QsIG1heGxlbiA9IG1heF9zZXF1ZW5jZV9sZW4tMSwgcGFkZGluZyA9ICJwcmUiKQ0KICAgIHByZWRpY3RlZCA9IHByZWRpY3RfY2xhc3Nlcyhtb2RlbCwgeCA9IHRva2VuX2xpc3QsIHZlcmJvc2UgPSAwKS0xDQogICAgd29yZHMgPSB0b2tlbml6ZXIkd29yZF9pbmRleCAlPiUgbmFtZXMoKQ0KICAgIGluZGV4ZXMgPSBtYXBfaW50KHRva2VuaXplciR3b3JkX2luZGV4LGZ1bmN0aW9uKHgpeFsxXSkNCiAgICBvdXRwdXRfd29yZCA9IHdvcmRzW2luZGV4ZXM9PWFzLnZlY3RvcihwcmVkaWN0ZWQpXQ0KICAgIEVuY29kaW5nKG91dHB1dF93b3JkKSA9ICJVVEYtOCINCiAgICB0ZXh0b19zZW1pbGxhID0gcGFzdGUwKHRleHRvX3NlbWlsbGEsIiAiLG91dHB1dF93b3JkKQ0KICB9DQogIHJldHVybih0ZXh0b19zZW1pbGxhKQ0KfQ0KDQojIEVqZWN1Y2nDs24NCmdlbl90ZXh0KCJMZWpvcyBkZSBsYSBzdXBlcnN0aWNpw7NuIGRlbGlyYW50ZSIsIDUsIG1vZGVsLCBwYWRfc2VxJG1heF9zZXF1ZW5jZV9sZW4sIGlucF9zZXFfdG90X3dvcmRzJHRva2VuaXplcikNCmBgYA0KDQoNCiMgKiozLiBCaWJsaW9ncmFmw61hKioNCg==