Tokenization: Representing raw text into meaningful units of text (tokens) so we can perform computations on them.

suppressWarnings(if (!require("pacman"))install.packages("pacman"))
## Loading required package: pacman
pacman::p_load(tidyverse, tidytext, tokenizers, hcandersenr, here)

2.1 What is a token?

In R, text is represented with the character data type similar to strings in other languages.

Exploring text from fairy tales written by Hans Christian Andersen

# Load required packages
library(tokenizers)
library(tidyverse)
library(tidytext)
library(hcandersenr)

# Narrow to a single book
the_fir_tree <- hcandersen_en %>% 
  filter(book == "The fir tree") %>% 
  pull(text)

the_fir_tree %>% 
  head(n = 9)
## [1] "Far down in the forest, where the warm sun and the fresh air made a sweet"    
## [2] "resting-place, grew a pretty little fir-tree; and yet it was not happy, it"   
## [3] "wished so much to be tall like its companions– the pines and firs which grew" 
## [4] "around it. The sun shone, and the soft air fluttered its leaves, and the"     
## [5] "little peasant children passed by, prattling merrily, but the fir-tree heeded"
## [6] "them not. Sometimes the children would bring a large basket of raspberries or"
## [7] "strawberries, wreathed on a straw, and seat themselves near the fir-tree, and"
## [8] "say, \"Is it not a pretty little tree?\" which made it feel more unhappy than"
## [9] "before."

In tokenization, we take an input (a string) and a token (eg a word) and split the input into tokens. Most commonly, the meaningful token we want to split text into is a word.

To understand the process of tokenization, let’s start with an overly simple definition for a word: any selection of alphanumeric (letter and numbers) symbols

base::strsplit() - Split the elements of a character vector x into substrings according to the matches to substring split within them.

the_fir_tree[1:2]
## [1] "Far down in the forest, where the warm sun and the fresh air made a sweet" 
## [2] "resting-place, grew a pretty little fir-tree; and yet it was not happy, it"
strsplit(the_fir_tree[1:2], split = "[^a-zA-Z0-9]+")
## [[1]]
##  [1] "Far"    "down"   "in"     "the"    "forest" "where"  "the"    "warm"  
##  [9] "sun"    "and"    "the"    "fresh"  "air"    "made"   "a"      "sweet" 
## 
## [[2]]
##  [1] "resting" "place"   "grew"    "a"       "pretty"  "little"  "fir"    
##  [8] "tree"    "and"     "yet"     "it"      "was"     "not"     "happy"  
## [15] "it"

At first sight, this result looks pretty decent. However, we have lost all punctuation, which may or may not be helpful for our modeling goal, and the hero of this story ("fir-tree") was split in half.

Better way?

Tokenization with tokenizers package

library(tokenizers)
the_fir_tree[1:2]
## [1] "Far down in the forest, where the warm sun and the fresh air made a sweet" 
## [2] "resting-place, grew a pretty little fir-tree; and yet it was not happy, it"
# Basic tokenization into words
tokenize_words(the_fir_tree[1:2])
## [[1]]
##  [1] "far"    "down"   "in"     "the"    "forest" "where"  "the"    "warm"  
##  [9] "sun"    "and"    "the"    "fresh"  "air"    "made"   "a"      "sweet" 
## 
## [[2]]
##  [1] "resting" "place"   "grew"    "a"       "pretty"  "little"  "fir"    
##  [8] "tree"    "and"     "yet"     "it"      "was"     "not"     "happy"  
## [15] "it"

We see sensible single-word results here; the tokenize_words() function uses the stringi package (Gagolewski 2020) and C++ under the hood, making it very fast + it is many times more sophisticated than our initial approach of splitting on non-alphanumeric characters.

2.2 Types of tokens

Thinking of a token as a word is a useful way to start understanding tokenization, even if it is hard to implement concretely in software. We can generalize the idea of a token beyond only a single word to other units of text. We can tokenize text at a variety of units including:

  • characters,

  • words,

  • sentences,

  • lines,

  • paragraphs, and

  • n-grams.

In the following sections, we will explore how to tokenize text using the tokenizers package. These functions take a character vector as the input and return lists of character vectors as output. This same tokenization can also be done using the tidytext (Silge and Robinson 2016) package, for workflows using tidy data principles where the input and output are both in a dataframe.

Let’s see this in action:

# Character vector
sample_vector <- c("Far down in the forest",
                   "grew a pretty little fir-tree")

sample_vector
## [1] "Far down in the forest"        "grew a pretty little fir-tree"
# Tibble vector
sample_tibble <- tibble(text = sample_vector)

sample_tibble

Tokenization achieved by tokenizers::tokenize_words() on character vector:

tokenize_words(sample_vector)
## [[1]]
## [1] "far"    "down"   "in"     "the"    "forest"
## 
## [[2]]
## [1] "grew"   "a"      "pretty" "little" "fir"    "tree"

will yield the same results as using tidytext::unnest_tokens() on sample_tibble; the only difference is the data structure, and thus how we might use the result moving forward in our analysis.

unnest_tokens(tbl = sample_tibble, output = word, input = text, token = "words")

Arguments eg strip_punct used in tokenizers::tokenize_words() can be passed through tidytext::unnest_tokens() using the “the dots”, ....

# Passing arguements from tokenizers package to tidytext package
sample_tibble %>% 
  unnest_tokens(output = words, input = text, token = "words", strip_punct = FALSE)

Tidytext - More Tidyverse oriented?

2.2.1 Character tokens

Simplest tokenization which splits text into characters.

Let’s use tokenize_characters() with its default parameters; this function has arguments to convert to lowercase and to strip all non-alphanumeric characters. These defaults will reduce the number of different tokens that are returned.

# Split text into characters
tft_token_characters <- tokenize_characters(
  x = the_fir_tree,
  lowercase = TRUE,
  strip_non_alphanum = TRUE,
  simplify = FALSE
)

head(tft_token_characters) %>% 
  glimpse()
## List of 6
##  $ : chr [1:57] "f" "a" "r" "d" ...
##  $ : chr [1:57] "r" "e" "s" "t" ...
##  $ : chr [1:61] "w" "i" "s" "h" ...
##  $ : chr [1:56] "a" "r" "o" "u" ...
##  $ : chr [1:64] "l" "i" "t" "t" ...
##  $ : chr [1:64] "t" "h" "e" "m" ...

We don’t have to stick with the defaults. We can keep the punctuation and spaces by setting strip_alphanum = FALSE

# Keep punctuation and white spaces
the_fir_tree %>% 
  tokenize_characters(strip_non_alphanum = F) %>% 
  head() %>% 
  glimpse()
## List of 6
##  $ : chr [1:73] "f" "a" "r" " " ...
##  $ : chr [1:74] "r" "e" "s" "t" ...
##  $ : chr [1:76] "w" "i" "s" "h" ...
##  $ : chr [1:72] "a" "r" "o" "u" ...
##  $ : chr [1:77] "l" "i" "t" "t" ...
##  $ : chr [1:77] "t" "h" "e" "m" ...

Depending on the format you have your text data in, it might contain ligatures. Ligatures are when multiple graphemes or letters are combined as a single character The graphemes “f” and “l” are combined into “fl,” or “s” and “t” into “st.” When we apply normal tokenization rules the ligatures will not be split up.

2.2.2 Word tokens

Tokenizing at the word level is perhaps the most common and widely used tokenization.

# Word tokenization
tft_token_words <- tokenize_words(
  x = the_fir_tree,
  lowercase = T,
  stopwords = NULL,
  strip_punct = T,
  strip_numeric = F
)

# Results
tft_token_words %>% 
  head() %>% 
  glimpse()
## List of 6
##  $ : chr [1:16] "far" "down" "in" "the" ...
##  $ : chr [1:15] "resting" "place" "grew" "a" ...
##  $ : chr [1:15] "wished" "so" "much" "to" ...
##  $ : chr [1:14] "around" "it" "the" "sun" ...
##  $ : chr [1:12] "little" "peasant" "children" "passed" ...
##  $ : chr [1:13] "them" "not" "sometimes" "the" ...

Let’s create a tibble with two fairy tales, “The Fir-Tree” and “The Little Mermaid.” Then we can use unnest_tokens() together with some dplyr verbs to find the most commonly used words in each.

# A dance with data
hcandersen_en %>% 
  filter(book %in% c("The fir tree", "The little mermaid")) %>% 
  unnest_tokens(output = word, input = text, token = "words") %>% 
  group_by(book) %>% 
  count(word) %>% 
  arrange(desc(n)) %>% 
  slice(1:5)

The five most common words in each fairy tale are fairly uninformative, with the exception being "tree" in the “The Fir-Tree.”

These uninformative words are called stop words

2.2.3 Tokenize by n-grams

Can be defined loosely as a continuous sequence of n items from a given sequence of text or speech e.g a group of n words

Some example n-grams are:

  • unigram: “Hello,” “day,” “my,” “little”

  • bigram: “fir tree,” “fresh air,” “to be,” “Robin Hood”

  • trigram: “You and I,” “please let go,” “no time like,” “the little mermaid”

The benefit of using n-grams compared to words is that n-grams capture word order that would otherwise be lost. Similarly, when we use character n-grams, we can model the beginning and end of words.

# n_gram tokenization
tft_token_ngram <- tokenize_ngrams(x = the_fir_tree,
                                   lowercase = TRUE,
                  # The number of words in the n-gram
                                   n = 3L,
                  # Min n.o of ngrams to include
                                   n_min = 3L,
                                   stopwords = character(),
                  # Separator between words in an ngram
                                   ngram_delim = " ",
                                   simplify = F)

# First line
the_fir_tree[1]
## [1] "Far down in the forest, where the warm sun and the fresh air made a sweet"
# Ngram for first line
tft_token_ngram[[1]]
##  [1] "far down in"      "down in the"      "in the forest"    "the forest where"
##  [5] "forest where the" "where the warm"   "the warm sun"     "warm sun and"    
##  [9] "sun and the"      "and the fresh"    "the fresh air"    "fresh air made"  
## [13] "air made a"       "made a sweet"
  • N-gram tokenization slides along the text to create overlapping sets of tokens.

  • It is important to choose the right value for n (n.o of words in n-gram) when using n-grams for the question we want to answer. Using unigrams is faster and more efficient, but we don’t capture information about word order. Using a higher value for n keeps more information, but the vector space of tokens increases dramatically, corresponding to a reduction in token counts.

  • Good place is 3 but 2 can work if you don’t have a large vocabulary in your data set

  • Combining different degrees of n-grams can allow you to extract different levels of detail from text data. Unigrams tell you which individual words have been used a lot of times; some of these words could be overlooked in bigram or trigram counts if they don’t co-appear with other words often.

  • Unigrams alone don’t capture much info

# Different degrees of n-grams
tft_token_ngram2 <- tokenize_ngrams(
  x = the_fir_tree,
  n = 2L,
  n_min = 1
)

# Display
the_fir_tree[1]
## [1] "Far down in the forest, where the warm sun and the fresh air made a sweet"
tft_token_ngram2[[1]]
##  [1] "far"          "far down"     "down"         "down in"      "in"          
##  [6] "in the"       "the"          "the forest"   "forest"       "forest where"
## [11] "where"        "where the"    "the"          "the warm"     "warm"        
## [16] "warm sun"     "sun"          "sun and"      "and"          "and the"     
## [21] "the"          "the fresh"    "fresh"        "fresh air"    "air"         
## [26] "air made"     "made"         "made a"       "a"            "a sweet"     
## [31] "sweet"

2.2.4 Lines, sentences and paragraph tokens

Tokenizers to split text into larger units of text like lines, sentences, and paragraphs are rarely used directly for modeling purposes, as the tokens produced tend to be fairly unique. It is very uncommon for multiple sentences in a text to be identical!

However, these tokenizers are useful for preprocessing and labeling.

For example, Jane Austen’s novel Northanger Abbey (as available in the janeaustenr package) is already preprocessed with each line being at most 80 characters long. However, it might be useful to split the data into chapters and paragraphs instead.

  • Let’s create a function that takes a dataframe containing a variable called text and turns it into a dataframe where the text is transformed into paragraphs.

  • First, we can collapse the text into one long string using collapse = "\n" to denote line breaks,

  • and then next we can use tokenize_paragraphs() to identify the paragraphs and put them back into a dataframe. We can add a paragraph count with row_number().

paste0(…, collapse) is equivalent to paste(…, sep = ““, collapse), slightly more efficiently.

If a value is specified for collapse, the values in the result are then concatenated into a single string, with the elements being separated by the value of collapse.

# Return paragraphs function
add_paragraphs <- function(data){
  data %>% pull(text) %>% 
    # collapse output into a single string 
    paste(collapse = "\n") %>% 
    tokenize_paragraphs() %>% 
    # Flatten to produce a vector
    unlist() %>% 
    tibble(text = .) %>% 
    mutate(paragraph = row_number())
  
}

Now we take the raw text data and add the chapter count by detecting when the characters "CHAPTER" appears at the beginning of a line. Then we nest() the text column, apply our add_paragraphs() function, and then unnest() again.

Nest(): combines columns and outputs 1 row for each non-nested column

map and variants: similar to lapply etc–further reading

And in filter: & or ,

# Make paragraphs
library(janeaustenr)

northangerabbey_paragraphed <- tibble(text = northangerabbey) %>% 
       mutate(chapter = cumsum(text %>% str_detect("^CHAPTER "))) %>%
       filter(chapter > 0, !str_detect(text, "^CHAPTER ")) %>% 
       nest(data = text) %>%
       mutate(data = map(data, add_paragraphs)) %>% 
       unnest(cols = c(data))

glimpse(northangerabbey_paragraphed)
## Rows: 1,020
## Columns: 3
## $ chapter   <int> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, ~
## $ text      <chr> "No one who had ever seen Catherine Morland in her infancy w~
## $ paragraph <int> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 1~

It can be useful to be able to reshape text data to get a different observational unit. As an example, if you wanted to build a sentiment classifier that would classify sentences as hostile or not, then you need to work with and train your model on sentences of text. Turning pages or paragraphs into sentences is a necessary step in your workflow.

Let us look at how we can turn the_fir_tree from a “one line per element” vector to a “one sentence per element.” the_fir_tree comes as a vector so we start by using paste() to combine the lines back together. We use a space as the separator, and then we pass it to the tokenize_sentences() function from the tokenizers package, which will perform sentence splitting.

# One sentence per element
the_fir_tree_sentences <- the_fir_tree %>% 
  paste(collapse = " ") %>% 
  tokenize_sentences()

the_fir_tree_sentences[[1]] %>% 
  head()
## [1] "Far down in the forest, where the warm sun and the fresh air made a sweet resting-place, grew a pretty little fir-tree; and yet it was not happy, it wished so much to be tall like its companions– the pines and firs which grew around it."
## [2] "The sun shone, and the soft air fluttered its leaves, and the little peasant children passed by, prattling merrily, but the fir-tree heeded them not."                                                                                       
## [3] "Sometimes the children would bring a large basket of raspberries or strawberries, wreathed on a straw, and seat themselves near the fir-tree, and say, \"Is it not a pretty little tree?\""                                                  
## [4] "which made it feel more unhappy than before."                                                                                                                                                                                                
## [5] "And yet all this while the tree grew a notch or joint taller every year; for by the number of joints in the stem of a fir-tree we can discover its age."                                                                                     
## [6] "Still, as it grew, it complained."

If you have lines from different categories as we have in the hcandersen_en dataframe, which contains all the lines of the fairy tales in English, then we would like to be able to turn these lines into sentences while preserving the book column in the data set. To do this we use nest() and map_chr() to create a dataframe where each fairy tale is its own element and then we use the unnest_sentences() function from the tidytext package to split the text into sentences.

used tidytext::nnest_sentences() and not tokenizers::tokenize_sentencesbecause the data is a tibble

# Split text into sentences
hcandersen_sentences <- hcandersen_en %>%
       nest(data = c(text)) %>% 
       mutate(data = map_chr(data, ~paste(.x$text, collapse = " "))) %>% 
       unnest_sentences(input = data, output = sentences)

Now that we have turned the text into “one sentence per element,” we can analyze on the sentence level.

2.3 Where does tokenization break down?

Tokenization will generally be one of the first steps when building a model or any kind of text analysis, so it is important to consider carefully what happens in this step of data preprocessing. As with most software, there is a trade-off between speed and customizability, as demonstrated in Section 2.6. The fastest tokenization methods give us less control over how it is done.

While the defaults work well in many cases, we encounter situations where we want to impose stricter rules to get better or different tokenized results.

2.4 Build your own tokenizer

  • Sometimes the out-of-the-box tokenizers won’t be able to do what you need them to do. In this case, we will have to wield stringi/stringr and regular expressions

  • There are two main approaches to tokenization.

    1. Split the string up according to some rule.

    2. Extract tokens based on some rule.

  • We can reach complex outcomes by chaining together many smaller rules.

2.4.1 Tokenize to characters, only keeping letters

Here we want to modify what tokenize_characters() does, such that we only keep letters. There are two main options. We can use tokenize_characters() and remove anything that is not a letter, or we can extract the letters one by one. Let’s try the latter option. This is an extract task, and we will use str_extract_all() as each string has the possibility of including more than one token. Since we want to extract letters we can use the letters character class [:alpha:] to match letters and the quantifier {1} to only extract the first one.

stringi::stringi-search-regex

?regex()

[pattern] - Match any one character from the set.

{n} - Match exactly n times

regular expressions list: https://smltar.com/regexp.html#tab:characterclasses

string <- "This sentence includes 2 numbers and 1 period."

str_extract_all(string = string,
            pattern = "[:alpha:]{1}")
## [[1]]
##  [1] "T" "h" "i" "s" "s" "e" "n" "t" "e" "n" "c" "e" "i" "n" "c" "l" "u" "d" "e"
## [20] "s" "n" "u" "m" "b" "e" "r" "s" "a" "n" "d" "p" "e" "r" "i" "o" "d"
  • We may be tempted to specify the character class as something like [a-zA-Z]{1}. This option would run faster, but we would lose non-English letter characters.
danish_sentence <- "Så mødte han en gammel heks på landevejen"

str_extract_all(danish_sentence, "[:alpha:]{1}")
## [[1]]
##  [1] "S" "å" "m" "ø" "d" "t" "e" "h" "a" "n" "e" "n" "g" "a" "m" "m" "e" "l" "h"
## [20] "e" "k" "s" "p" "å" "l" "a" "n" "d" "e" "v" "e" "j" "e" "n"
str_extract_all(danish_sentence, "[a-zA-z]{1}")
## [[1]]
##  [1] "S" "m" "d" "t" "e" "h" "a" "n" "e" "n" "g" "a" "m" "m" "e" "l" "h" "e" "k"
## [20] "s" "p" "l" "a" "n" "d" "e" "v" "e" "j" "e" "n"

Choosing between [:alpha:] and [a-zA-Z] may seem quite similar, but the resulting differences can have a big impact on your analysis.

2.4.2 Allow for hyphenated words

In our examples so far, we have noticed that the string “fir-tree” is typically split into two tokens. Let’s explore two different approaches for how to handle this hyphenated word as one token.

  • First, let’s split on white space (Space, tab, vertical tab, newline, form feed, carriage return) ; this is a decent way to identify words in English and some other languages, and it does not split hyphenated words as the hyphen character isn’t considered a white-space.

  • Second, let’s find a regex to match words with a hyphen and extract those.

Splitting by white space is not too difficult because we can use character classes, as shown in Table A.2. We will use the white space character class [:space:] to split our sentence.

str_split(string = "This isn't a sentence with hyphanated-words..",
          pattern = "[:space:]")
## [[1]]
## [1] "This"               "isn't"              "a"                 
## [4] "sentence"           "with"               "hyphanated-words.."

This worked pretty well. This version doesn’t drop punctuation, but we can achieve this by removing punctuation characters at the beginning and end of words.

str_split("This isn't a sentence with hyphenated-words.",
          pattern = "[:space:]") %>% 
  map(~ str_remove_all(.x, "^[:punct:]+|[:punct:]+$"))
## [[1]]
## [1] "This"             "isn't"            "a"                "sentence"        
## [5] "with"             "hyphenated-words"

This regex used to remove the punctuation is a little complicated, so let’s discuss it piece by piece.

  • The regex ^[:punct:]+ will look at the beginning of the string (^) to match any punctuation characters ([:punct:]), where it will select one or more (+).

  • The other regex [:punct:]+$ will look for punctuation characters ([:punct:]) that appear one or more times (+) at the end of the string ($).

  • These will alternate (|) so that we get matches from both sides of the words.

  • The reason we use the quantifier + is that there are cases where a word is followed by multiple characters we don’t want, such as "okay..." and "Really?!!!".

  • We can specify how many times we expect something to occur using quantifiers eg +(one or more times)

Now let’s see if we can get the same result using extraction. We will start by constructing a regular expression that will capture hyphenated words; our definition here is a word with one hyphen located inside it. Since we want the hyphen to be inside the word, we will need to have a non-zero number of characters on either side of the hyphen.

str_extract_all(
  string = "This isn't a sentence with hyphenated-words.",
  pattern = "[:alpha:]+-[:alpha:]+")
## [[1]]
## [1] "hyphenated-words"

[:alpha:]: extracts letters

[:alpha:]+ : extracts words

[:alpha:]+[:alpha:]: ensures that each word is more than a character long so words like a are not included

Wait, this only matched the hyphenated word! This happened because we are only matching words with hyphens. If we add the quantifier ? then we can match 0 or 1 occurrences.

str_extract_all(
  string = "This isn't a sentence with hyphenated-words.",
  pattern = "[:alpha:]+-?[:alpha:]+")
## [[1]]
## [1] "This"             "isn"              "sentence"         "with"            
## [5] "hyphenated-words"

Now we are getting more words, but the ending of "isn't" is not there anymore and we lost the word "a".

  • We can get matches for the whole contraction by expanding the character class [:alpha:] to include the character '. We do that by using [[:alpha:]'].
# Eric's approach
str_extract_all(
  string = "This isn't a sentence with hyphenated-words.",
  pattern = "[[:alpha:]'-]+")
## [[1]]
## [1] "This"             "isn't"            "a"                "sentence"        
## [5] "with"             "hyphenated-words"
# Emil's approach
str_extract_all(
  string = "This isn't sentence with hyphenated-words.",
  pattern = "[[:alpha:]']+-?[[:alpha:]']+")
## [[1]]
## [1] "This"             "isn't"            "sentence"         "with"            
## [5] "hyphenated-words"

Next, we need to find out why "a" wasn’t matched. If we look at the regular expression, we remember that we imposed the restriction that a non-zero number of characters needed to surround the hyphen to avoid matching words that start or end with a hyphen. This means that the smallest possible pattern matched is two characters long. We can fix this by using an alternation with |. We will keep our previous match on the left-hand side, and include [:alpha:]{1} on the right-hand side to match the single length words that won’t be picked up by the left-hand side. Notice how we aren’t using [[:alpha:]'] since we are not interested in matching single ' characters.

str_extract_all(
  string = "This isn't a sentence with hyphenated-words.",
  pattern = "[[:alpha:]']+-?[[:alpha:]']+|[:alpha:]{1}"
)
## [[1]]
## [1] "This"             "isn't"            "a"                "sentence"        
## [5] "with"             "hyphenated-words"

2.4.3 Wrapping it in a function

We have shown how we can use regular expressions to extract the tokens we want, perhaps to use in modeling. So far, the code has been rather unstructured. We would ideally wrap these tasks into functions that can be used the same way tokenize_words() is used.

Let’s start with the example with hyphenated words. To make the function a little more flexible, let’s add an option to transform all the output to lowercase.

# Function to hyphenate words
tokenize_hyphenated_words <- function(x, lowercase = TRUE){
  if (lowercase) x = str_to_lower(x)
  
  str_split(x, "[:space:]") %>% 
    map(~ str_remove_all(.x, "^[:punct:]+|[:punct:]+$"))
}


# Book extract
the_fir_tree[1:3]
## [1] "Far down in the forest, where the warm sun and the fresh air made a sweet"   
## [2] "resting-place, grew a pretty little fir-tree; and yet it was not happy, it"  
## [3] "wished so much to be tall like its companions– the pines and firs which grew"
# Call function
tokenize_hyphenated_words(x = the_fir_tree[1:3])
## [[1]]
##  [1] "far"    "down"   "in"     "the"    "forest" "where"  "the"    "warm"  
##  [9] "sun"    "and"    "the"    "fresh"  "air"    "made"   "a"      "sweet" 
## 
## [[2]]
##  [1] "resting-place" "grew"          "a"             "pretty"       
##  [5] "little"        "fir-tree"      "and"           "yet"          
##  [9] "it"            "was"           "not"           "happy"        
## [13] "it"           
## 
## [[3]]
##  [1] "wished"     "so"         "much"       "to"         "be"        
##  [6] "tall"       "like"       "its"        "companions" "the"       
## [11] "pines"      "and"        "firs"       "which"      "grew"


Notice how we transformed to lowercase first because the rest of the operations are case insensitive.

Next let’s turn our character n-gram tokenizer into a function, with a variable n argument.

Little idea of what is going on below

tokenize_character_ngram <- function(x, n) {
  ngram_loc <- str_locate_all(x, paste0("(?=(\\w{", n, "}))"))

  map2(ngram_loc, x, ~str_sub(.y, .x[, 1], .x[, 1] + n - 1))
}

tokenize_character_ngram(the_fir_tree[1:3], n = 3)
## [[1]]
##  [1] "Far" "dow" "own" "the" "for" "ore" "res" "est" "whe" "her" "ere" "the"
## [13] "war" "arm" "sun" "and" "the" "fre" "res" "esh" "air" "mad" "ade" "swe"
## [25] "wee" "eet"
## 
## [[2]]
##  [1] "res" "est" "sti" "tin" "ing" "pla" "lac" "ace" "gre" "rew" "pre" "ret"
## [13] "ett" "tty" "lit" "itt" "ttl" "tle" "fir" "tre" "ree" "and" "yet" "was"
## [25] "not" "hap" "app" "ppy"
## 
## [[3]]
##  [1] "wis" "ish" "she" "hed" "muc" "uch" "tal" "all" "lik" "ike" "its" "com"
## [13] "omp" "mpa" "pan" "ani" "nio" "ion" "ons" "the" "pin" "ine" "nes" "and"
## [25] "fir" "irs" "whi" "hic" "ich" "gre" "rew"

We can use paste0() in this function to construct an actual regex.

2.5 Tokenization for non-Latin alphabets

Our discussion of tokenization so far has focused on text where words are separated by white space and punctuation. For such text, even a quite basic tokenizer can give decent results. However, many written languages don’t separate words in this way.

One of these languages is Chinese where each “word” can be represented by one or more consecutive characters. Splitting Chinese text into words is called “word segmentation” and is still an active area of research (Ma, Ganchev, and Weiss 2018; Huang et al. 2020).

We are not going to go into depth in this area, but we want to showcase that word segmentation is indeed possible with R as well. We use the jiebaR package (Wenfeng and Yanyi 2019). It is conceptually similar to the tokenizers package, but we need to create a worker that is passed into segment() along with the string we want to segment.

library(jiebaR)
## Loading required package: jiebaRD
words <- c("下面是不分行输出的结果", "下面是不输出的结果")

engine1 <- worker(bylines = T)

segment(words, engine1)
## [[1]]
##  [1] "U"    "4"    "E0B"  "U"    "9762" "U"    "662"  "F"    "U"    "4"   
## [11] "E0D"  "U"    "5206" "U"    "884"  "C"    "U"    "8"    "F93"  "U"   
## [21] "51"   "FA"   "U"    "7684" "U"    "7"    "ED3"  "U"    "679"  "C"   
## 
## [[2]]
##  [1] "U"    "4"    "E0B"  "U"    "9762" "U"    "662"  "F"    "U"    "4"   
## [11] "E0D"  "U"    "8"    "F93"  "U"    "51"   "FA"   "U"    "7684" "U"   
## [21] "7"    "ED3"  "U"    "679"  "C"

2.7 Summary

  • To build a predictive model, text data needs to be split into meaningful units, called tokens.

  • Fast and consistent tokenizers are available, but understanding how they behave and in what circumstances they work best will set you up for success.

  • Once text data is tokenized, a common next preprocessing step is to consider how to handle very common words that are not very informative— stop words.

LS0tDQp0aXRsZTogJ05hdHVyYWwgTGFuZ3VhZ2UgRmVhdHVyZXM6IENoYXB0ZXIgMiBUb2tlbml6YXRpb24nDQpvdXRwdXQ6DQogIGh0bWxfZG9jdW1lbnQ6DQogICAgY3NzOiBzdHlsZV83LmNzcw0KICAgIGRmX3ByaW50OiBwYWdlZA0KICAgIHRoZW1lOiBmbGF0bHkNCiAgICBoaWdobGlnaHQ6IGJyZWV6ZWRhcmsNCiAgICB0b2M6IHllcw0KICAgIHRvY19mbG9hdDogeWVzDQogICAgY29kZV9kb3dubG9hZDogeWVzDQotLS0NCg0KKipUb2tlbml6YXRpb24qKjogUmVwcmVzZW50aW5nIHJhdyB0ZXh0IGludG8gbWVhbmluZ2Z1bCB1bml0cyBvZiB0ZXh0ICh0b2tlbnMpIHNvIHdlIGNhbiBwZXJmb3JtIGNvbXB1dGF0aW9ucyBvbiB0aGVtLg0KDQpgYGB7cn0NCnN1cHByZXNzV2FybmluZ3MoaWYgKCFyZXF1aXJlKCJwYWNtYW4iKSlpbnN0YWxsLnBhY2thZ2VzKCJwYWNtYW4iKSkNCg0KcGFjbWFuOjpwX2xvYWQodGlkeXZlcnNlLCB0aWR5dGV4dCwgdG9rZW5pemVycywgaGNhbmRlcnNlbnIsIGhlcmUpDQpgYGANCg0KIyMgMi4xIFdoYXQgaXMgYSB0b2tlbj8NCg0KSW4gUiwgdGV4dCBpcyByZXByZXNlbnRlZCB3aXRoIHRoZSAqY2hhcmFjdGVyKiBkYXRhIHR5cGUgc2ltaWxhciB0byBzdHJpbmdzIGluIG90aGVyIGxhbmd1YWdlcy4NCg0KPiBFeHBsb3JpbmcgdGV4dCBmcm9tIGZhaXJ5IHRhbGVzIHdyaXR0ZW4gYnkgSGFucyBDaHJpc3RpYW4gQW5kZXJzZW4NCg0KYGBge3J9DQojIExvYWQgcmVxdWlyZWQgcGFja2FnZXMNCmxpYnJhcnkodG9rZW5pemVycykNCmxpYnJhcnkodGlkeXZlcnNlKQ0KbGlicmFyeSh0aWR5dGV4dCkNCmxpYnJhcnkoaGNhbmRlcnNlbnIpDQoNCiMgTmFycm93IHRvIGEgc2luZ2xlIGJvb2sNCnRoZV9maXJfdHJlZSA8LSBoY2FuZGVyc2VuX2VuICU+JSANCiAgZmlsdGVyKGJvb2sgPT0gIlRoZSBmaXIgdHJlZSIpICU+JSANCiAgcHVsbCh0ZXh0KQ0KDQp0aGVfZmlyX3RyZWUgJT4lIA0KICBoZWFkKG4gPSA5KQ0KDQpgYGANCg0KSW4gdG9rZW5pemF0aW9uLCB3ZSB0YWtlIGFuIGlucHV0IChhIHN0cmluZykgYW5kIGEgdG9rZW4gKGVnIGEgd29yZCkgYW5kIHNwbGl0IHRoZSBpbnB1dCBpbnRvIHRva2Vucy4gTW9zdCBjb21tb25seSwgdGhlIG1lYW5pbmdmdWwgdG9rZW4gd2Ugd2FudCB0byBzcGxpdCB0ZXh0IGludG8gaXMgYSAqKndvcmQqKi4NCg0KVG8gdW5kZXJzdGFuZCB0aGUgcHJvY2VzcyBvZiB0b2tlbml6YXRpb24sIGxldCdzIHN0YXJ0IHdpdGggYW4gb3Zlcmx5IHNpbXBsZSBkZWZpbml0aW9uIGZvciBhIHdvcmQ6ICphbnkgc2VsZWN0aW9uIG9mIGFscGhhbnVtZXJpYyAobGV0dGVyIGFuZCBudW1iZXJzKSBzeW1ib2xzKg0KDQo+IGJhc2U6OnN0cnNwbGl0KCkgLSBTcGxpdCB0aGUgZWxlbWVudHMgb2YgYSBjaGFyYWN0ZXIgdmVjdG9yIHggaW50byBzdWJzdHJpbmdzIGFjY29yZGluZyB0byB0aGUgbWF0Y2hlcyB0byBzdWJzdHJpbmcgc3BsaXQgd2l0aGluIHRoZW0uDQoNCmBgYHtyIHN0cl9zcGxpdH0NCnRoZV9maXJfdHJlZVsxOjJdDQpzdHJzcGxpdCh0aGVfZmlyX3RyZWVbMToyXSwgc3BsaXQgPSAiW15hLXpBLVowLTldKyIpDQoNCmBgYA0KDQpBdCBmaXJzdCBzaWdodCwgdGhpcyByZXN1bHQgbG9va3MgcHJldHR5IGRlY2VudC4gSG93ZXZlciwgd2UgaGF2ZSBsb3N0IGFsbCBwdW5jdHVhdGlvbiwgd2hpY2ggbWF5IG9yIG1heSBub3QgYmUgaGVscGZ1bCBmb3Igb3VyIG1vZGVsaW5nIGdvYWwsIGFuZCB0aGUgaGVybyBvZiB0aGlzIHN0b3J5IChgImZpci10cmVlImApIHdhcyBzcGxpdCBpbiBoYWxmLg0KDQoqKkJldHRlciB3YXk/KioNCg0KLSAgICoqdG9rZW5pemVycyoqIChbTXVsbGVuIGV0IGFsLiAyMDE4XShodHRwczovL3NtbHRhci5jb20vdG9rZW5pemF0aW9uLmh0bWwjcmVmLU11bGxlbjE4KSkNCg0KLSAgICoqc3BhQ3kqKiAoW0hvbm5pYmFsIGV0IGFsLiAyMDIwXShodHRwczovL3NtbHRhci5jb20vdG9rZW5pemF0aW9uLmh0bWwjcmVmLXNwYWN5MikpIGltcGxlbWVudCBmYXN0LCBjb25zaXN0ZW50IHRva2VuaXplcnMgd2UgY2FuIHVzZS4NCg0KVG9rZW5pemF0aW9uIHdpdGggYHRva2VuaXplcnNgIHBhY2thZ2UNCg0KYGBge3IgdG9rZW5pemVyc30NCmxpYnJhcnkodG9rZW5pemVycykNCnRoZV9maXJfdHJlZVsxOjJdDQojIEJhc2ljIHRva2VuaXphdGlvbiBpbnRvIHdvcmRzDQp0b2tlbml6ZV93b3Jkcyh0aGVfZmlyX3RyZWVbMToyXSkNCg0KYGBgDQoNCldlIHNlZSBzZW5zaWJsZSBzaW5nbGUtd29yZCByZXN1bHRzIGhlcmU7IHRoZSBgdG9rZW5pemVfd29yZHMoKWAgZnVuY3Rpb24gdXNlcyB0aGUgKipzdHJpbmdpKiogcGFja2FnZSAoW0dhZ29sZXdza2kgMjAyMF0oaHR0cHM6Ly9zbWx0YXIuY29tL3Rva2VuaXphdGlvbi5odG1sI3JlZi1HYWdvbGV3c2tpMTkpKSBhbmQgQysrIHVuZGVyIHRoZSBob29kLCBtYWtpbmcgaXQgdmVyeSBmYXN0ICsgaXQgaXMgbWFueSB0aW1lcyBtb3JlIHNvcGhpc3RpY2F0ZWQgdGhhbiBvdXIgaW5pdGlhbCBhcHByb2FjaCBvZiBzcGxpdHRpbmcgb24gbm9uLWFscGhhbnVtZXJpYyBjaGFyYWN0ZXJzLg0KDQojIyAyLjIgVHlwZXMgb2YgdG9rZW5zDQoNClRoaW5raW5nIG9mIGEgdG9rZW4gYXMgYSB3b3JkIGlzIGEgdXNlZnVsIHdheSB0byBzdGFydCB1bmRlcnN0YW5kaW5nIHRva2VuaXphdGlvbiwgZXZlbiBpZiBpdCBpcyBoYXJkIHRvIGltcGxlbWVudCBjb25jcmV0ZWx5IGluIHNvZnR3YXJlLiBXZSBjYW4gZ2VuZXJhbGl6ZSB0aGUgaWRlYSBvZiBhIHRva2VuIGJleW9uZCBvbmx5IGEgc2luZ2xlIHdvcmQgdG8gb3RoZXIgdW5pdHMgb2YgdGV4dC4gV2UgY2FuIHRva2VuaXplIHRleHQgYXQgYSB2YXJpZXR5IG9mIHVuaXRzIGluY2x1ZGluZzoNCg0KLSAgIGNoYXJhY3RlcnMsDQoNCi0gICB3b3JkcywNCg0KLSAgIHNlbnRlbmNlcywNCg0KLSAgIGxpbmVzLA0KDQotICAgcGFyYWdyYXBocywgYW5kDQoNCi0gICBuLWdyYW1zLg0KDQpJbiB0aGUgZm9sbG93aW5nIHNlY3Rpb25zLCB3ZSB3aWxsIGV4cGxvcmUgaG93IHRvIHRva2VuaXplIHRleHQgdXNpbmcgdGhlICoqdG9rZW5pemVycyoqIHBhY2thZ2UuIFRoZXNlIGZ1bmN0aW9ucyB0YWtlIGEgY2hhcmFjdGVyIHZlY3RvciBhcyB0aGUgaW5wdXQgYW5kIHJldHVybiBsaXN0cyBvZiBjaGFyYWN0ZXIgdmVjdG9ycyBhcyBvdXRwdXQuIFRoaXMgc2FtZSB0b2tlbml6YXRpb24gY2FuIGFsc28gYmUgZG9uZSB1c2luZyB0aGUgKip0aWR5dGV4dCoqIChbU2lsZ2UgYW5kIFJvYmluc29uIDIwMTZdKGh0dHBzOi8vc21sdGFyLmNvbS90b2tlbml6YXRpb24uaHRtbCNyZWYtU2lsZ2UxNikpIHBhY2thZ2UsIGZvciB3b3JrZmxvd3MgdXNpbmcgdGlkeSBkYXRhIHByaW5jaXBsZXMgd2hlcmUgdGhlICoqaW5wdXQgYW5kIG91dHB1dCBhcmUgYm90aCBpbiBhIGRhdGFmcmFtZSoqLg0KDQpMZXQncyBzZWUgdGhpcyBpbiBhY3Rpb246DQoNCmBgYHtyIHRva2VuaXplcnNfdGlkeXRleHR9DQojIENoYXJhY3RlciB2ZWN0b3INCnNhbXBsZV92ZWN0b3IgPC0gYygiRmFyIGRvd24gaW4gdGhlIGZvcmVzdCIsDQogICAgICAgICAgICAgICAgICAgImdyZXcgYSBwcmV0dHkgbGl0dGxlIGZpci10cmVlIikNCg0Kc2FtcGxlX3ZlY3Rvcg0KDQojIFRpYmJsZSB2ZWN0b3INCnNhbXBsZV90aWJibGUgPC0gdGliYmxlKHRleHQgPSBzYW1wbGVfdmVjdG9yKQ0KDQpzYW1wbGVfdGliYmxlDQoNCmBgYA0KDQpUb2tlbml6YXRpb24gYWNoaWV2ZWQgYnkgYHRva2VuaXplcnM6OnRva2VuaXplX3dvcmRzKClgIG9uIGBjaGFyYWN0ZXIgdmVjdG9yYDoNCg0KYGBge3J9DQp0b2tlbml6ZV93b3JkcyhzYW1wbGVfdmVjdG9yKQ0KYGBgDQoNCndpbGwgeWllbGQgdGhlIHNhbWUgcmVzdWx0cyBhcyB1c2luZyBgdGlkeXRleHQ6OnVubmVzdF90b2tlbnMoKWAgb24gYHNhbXBsZV90aWJibGVgOyB0aGUgb25seSBkaWZmZXJlbmNlIGlzIHRoZSBgZGF0YSBzdHJ1Y3R1cmVgLCBhbmQgdGh1cyBob3cgd2UgbWlnaHQgdXNlIHRoZSByZXN1bHQgbW92aW5nIGZvcndhcmQgaW4gb3VyIGFuYWx5c2lzLg0KDQpgYGB7cn0NCnVubmVzdF90b2tlbnModGJsID0gc2FtcGxlX3RpYmJsZSwgb3V0cHV0ID0gd29yZCwgaW5wdXQgPSB0ZXh0LCB0b2tlbiA9ICJ3b3JkcyIpDQpgYGANCg0KPiBBcmd1bWVudHMgZWcgKipzdHJpcF9wdW5jdCoqIHVzZWQgaW4gYHRva2VuaXplcnM6OnRva2VuaXplX3dvcmRzKClgIGNhbiBiZSBwYXNzZWQgdGhyb3VnaCBgdGlkeXRleHQ6OnVubmVzdF90b2tlbnMoKWAgdXNpbmcgdGhlIFsidGhlIGRvdHMiXShodHRwczovL2Fkdi1yLmhhZGxleS5uei9mdW5jdGlvbnMuaHRtbCNmdW4tZG90LWRvdC1kb3QpLCBgLi4uYC4NCg0KYGBge3J9DQojIFBhc3NpbmcgYXJndWVtZW50cyBmcm9tIHRva2VuaXplcnMgcGFja2FnZSB0byB0aWR5dGV4dCBwYWNrYWdlDQpzYW1wbGVfdGliYmxlICU+JSANCiAgdW5uZXN0X3Rva2VucyhvdXRwdXQgPSB3b3JkcywgaW5wdXQgPSB0ZXh0LCB0b2tlbiA9ICJ3b3JkcyIsIHN0cmlwX3B1bmN0ID0gRkFMU0UpDQpgYGANCg0KKioqVGlkeXRleHQqKiogLSBNb3JlIFRpZHl2ZXJzZSBvcmllbnRlZD8NCg0KIyMjIDIuMi4xIENoYXJhY3RlciB0b2tlbnMNCg0KU2ltcGxlc3QgdG9rZW5pemF0aW9uIHdoaWNoIHNwbGl0cyB0ZXh0IGludG8gY2hhcmFjdGVycy4NCg0KTGV0J3MgdXNlIGB0b2tlbml6ZV9jaGFyYWN0ZXJzKClgIHdpdGggaXRzIGRlZmF1bHQgcGFyYW1ldGVyczsgdGhpcyBmdW5jdGlvbiBoYXMgYXJndW1lbnRzIHRvIGNvbnZlcnQgdG8gbG93ZXJjYXNlIGFuZCB0byBzdHJpcCBhbGwgbm9uLWFscGhhbnVtZXJpYyBjaGFyYWN0ZXJzLiBUaGVzZSBkZWZhdWx0cyB3aWxsIHJlZHVjZSB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCB0b2tlbnMgdGhhdCBhcmUgcmV0dXJuZWQuDQoNCmBgYHtyfQ0KIyBTcGxpdCB0ZXh0IGludG8gY2hhcmFjdGVycw0KdGZ0X3Rva2VuX2NoYXJhY3RlcnMgPC0gdG9rZW5pemVfY2hhcmFjdGVycygNCiAgeCA9IHRoZV9maXJfdHJlZSwNCiAgbG93ZXJjYXNlID0gVFJVRSwNCiAgc3RyaXBfbm9uX2FscGhhbnVtID0gVFJVRSwNCiAgc2ltcGxpZnkgPSBGQUxTRQ0KKQ0KDQpoZWFkKHRmdF90b2tlbl9jaGFyYWN0ZXJzKSAlPiUgDQogIGdsaW1wc2UoKQ0KYGBgDQoNCldlIGRvbid0IGhhdmUgdG8gc3RpY2sgd2l0aCB0aGUgZGVmYXVsdHMuIFdlIGNhbiBrZWVwIHRoZSBwdW5jdHVhdGlvbiBhbmQgc3BhY2VzIGJ5IHNldHRpbmcgYHN0cmlwX2FscGhhbnVtID0gRkFMU0VgDQoNCmBgYHtyfQ0KIyBLZWVwIHB1bmN0dWF0aW9uIGFuZCB3aGl0ZSBzcGFjZXMNCnRoZV9maXJfdHJlZSAlPiUgDQogIHRva2VuaXplX2NoYXJhY3RlcnMoc3RyaXBfbm9uX2FscGhhbnVtID0gRikgJT4lIA0KICBoZWFkKCkgJT4lIA0KICBnbGltcHNlKCkNCmBgYA0KDQo+IERlcGVuZGluZyBvbiB0aGUgZm9ybWF0IHlvdSBoYXZlIHlvdXIgdGV4dCBkYXRhIGluLCBpdCBtaWdodCBjb250YWluIGxpZ2F0dXJlcy4gYExpZ2F0dXJlc2AgYXJlIHdoZW4gbXVsdGlwbGUgZ3JhcGhlbWVzIG9yIGxldHRlcnMgYXJlIGNvbWJpbmVkIGFzIGEgc2luZ2xlIGNoYXJhY3RlciBUaGUgZ3JhcGhlbWVzICJmIiBhbmQgImwiIGFyZSBjb21iaW5lZCBpbnRvICLvrIIsIiBvciAicyIgYW5kICJ0IiBpbnRvICLvrIYuIiBXaGVuIHdlIGFwcGx5IG5vcm1hbCB0b2tlbml6YXRpb24gcnVsZXMgdGhlIGxpZ2F0dXJlcyB3aWxsIG5vdCBiZSBzcGxpdCB1cC4NCg0KIyMjIDIuMi4yIFdvcmQgdG9rZW5zDQoNClRva2VuaXppbmcgYXQgdGhlIHdvcmQgbGV2ZWwgaXMgcGVyaGFwcyB0aGUgbW9zdCBjb21tb24gYW5kIHdpZGVseSB1c2VkIHRva2VuaXphdGlvbi4NCg0KYGBge3J9DQojIFdvcmQgdG9rZW5pemF0aW9uDQp0ZnRfdG9rZW5fd29yZHMgPC0gdG9rZW5pemVfd29yZHMoDQogIHggPSB0aGVfZmlyX3RyZWUsDQogIGxvd2VyY2FzZSA9IFQsDQogIHN0b3B3b3JkcyA9IE5VTEwsDQogIHN0cmlwX3B1bmN0ID0gVCwNCiAgc3RyaXBfbnVtZXJpYyA9IEYNCikNCg0KIyBSZXN1bHRzDQp0ZnRfdG9rZW5fd29yZHMgJT4lIA0KICBoZWFkKCkgJT4lIA0KICBnbGltcHNlKCkNCmBgYA0KDQpMZXQncyBjcmVhdGUgYSB0aWJibGUgd2l0aCB0d28gZmFpcnkgdGFsZXMsICJUaGUgRmlyLVRyZWUiIGFuZCAiVGhlIExpdHRsZSBNZXJtYWlkLiIgVGhlbiB3ZSBjYW4gdXNlIGB1bm5lc3RfdG9rZW5zKClgIHRvZ2V0aGVyIHdpdGggc29tZSAqKmRwbHlyKiogdmVyYnMgdG8gZmluZCB0aGUgbW9zdCBjb21tb25seSB1c2VkIHdvcmRzIGluIGVhY2guDQoNCmBgYHtyfQ0KIyBBIGRhbmNlIHdpdGggZGF0YQ0KaGNhbmRlcnNlbl9lbiAlPiUgDQogIGZpbHRlcihib29rICVpbiUgYygiVGhlIGZpciB0cmVlIiwgIlRoZSBsaXR0bGUgbWVybWFpZCIpKSAlPiUgDQogIHVubmVzdF90b2tlbnMob3V0cHV0ID0gd29yZCwgaW5wdXQgPSB0ZXh0LCB0b2tlbiA9ICJ3b3JkcyIpICU+JSANCiAgZ3JvdXBfYnkoYm9vaykgJT4lIA0KICBjb3VudCh3b3JkKSAlPiUgDQogIGFycmFuZ2UoZGVzYyhuKSkgJT4lIA0KICBzbGljZSgxOjUpDQpgYGANCg0KVGhlIGZpdmUgbW9zdCBjb21tb24gd29yZHMgaW4gZWFjaCBmYWlyeSB0YWxlIGFyZSBmYWlybHkgdW5pbmZvcm1hdGl2ZSwgd2l0aCB0aGUgZXhjZXB0aW9uIGJlaW5nIGAidHJlZSJgIGluIHRoZSAiVGhlIEZpci1UcmVlLiINCg0KPiBUaGVzZSB1bmluZm9ybWF0aXZlIHdvcmRzIGFyZSBjYWxsZWQgKipzdG9wIHdvcmRzKioNCg0KIyMjIDIuMi4zIFRva2VuaXplIGJ5IG4tZ3JhbXMNCg0KQ2FuIGJlIGRlZmluZWQgbG9vc2VseSBhcyBhIGNvbnRpbnVvdXMgc2VxdWVuY2Ugb2YgKm4gaXRlbXMqIGZyb20gYSBnaXZlbiBzZXF1ZW5jZSBvZiB0ZXh0IG9yIHNwZWVjaCBlLmcgKmEgZ3JvdXAgb2YgbiB3b3JkcyoNCg0KU29tZSBleGFtcGxlIG4tZ3JhbXMgYXJlOg0KDQotICAgKip1bmlncmFtOioqICJIZWxsbywiICJkYXksIiAibXksIiAibGl0dGxlIg0KDQotICAgKipiaWdyYW06KiogImZpciB0cmVlLCIgImZyZXNoIGFpciwiICJ0byBiZSwiICJSb2JpbiBIb29kIg0KDQotICAgKip0cmlncmFtOioqICJZb3UgYW5kIEksIiAicGxlYXNlIGxldCBnbywiICJubyB0aW1lIGxpa2UsIiAidGhlIGxpdHRsZSBtZXJtYWlkIg0KDQpUaGUgYmVuZWZpdCBvZiB1c2luZyBuLWdyYW1zIGNvbXBhcmVkIHRvIHdvcmRzIGlzIHRoYXQgbi1ncmFtcyAqKmNhcHR1cmUgd29yZCBvcmRlciB0aGF0IHdvdWxkIG90aGVyd2lzZSBiZSBsb3N0KiouIFNpbWlsYXJseSwgd2hlbiB3ZSB1c2UgY2hhcmFjdGVyIG4tZ3JhbXMsIHdlIGNhbiAqKm1vZGVsIHRoZSBiZWdpbm5pbmcgYW5kIGVuZCBvZiB3b3JkcyoqLg0KDQpgYGB7cn0NCiMgbl9ncmFtIHRva2VuaXphdGlvbg0KdGZ0X3Rva2VuX25ncmFtIDwtIHRva2VuaXplX25ncmFtcyh4ID0gdGhlX2Zpcl90cmVlLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBsb3dlcmNhc2UgPSBUUlVFLA0KICAgICAgICAgICAgICAgICAgIyBUaGUgbnVtYmVyIG9mIHdvcmRzIGluIHRoZSBuLWdyYW0NCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbiA9IDNMLA0KICAgICAgICAgICAgICAgICAgIyBNaW4gbi5vIG9mIG5ncmFtcyB0byBpbmNsdWRlDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG5fbWluID0gM0wsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHN0b3B3b3JkcyA9IGNoYXJhY3RlcigpLA0KICAgICAgICAgICAgICAgICAgIyBTZXBhcmF0b3IgYmV0d2VlbiB3b3JkcyBpbiBhbiBuZ3JhbQ0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBuZ3JhbV9kZWxpbSA9ICIgIiwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc2ltcGxpZnkgPSBGKQ0KDQojIEZpcnN0IGxpbmUNCnRoZV9maXJfdHJlZVsxXQ0KDQojIE5ncmFtIGZvciBmaXJzdCBsaW5lDQp0ZnRfdG9rZW5fbmdyYW1bWzFdXQ0KYGBgDQoNCi0gICBOLWdyYW0gdG9rZW5pemF0aW9uIHNsaWRlcyBhbG9uZyB0aGUgdGV4dCB0byBjcmVhdGUgb3ZlcmxhcHBpbmcgc2V0cyBvZiB0b2tlbnMuDQoNCi0gICBJdCBpcyBpbXBvcnRhbnQgdG8gY2hvb3NlIHRoZSByaWdodCB2YWx1ZSBmb3IgYG5gIChuLm8gb2Ygd29yZHMgaW4gbi1ncmFtKSB3aGVuIHVzaW5nIG4tZ3JhbXMgZm9yIHRoZSBxdWVzdGlvbiB3ZSB3YW50IHRvIGFuc3dlci4gVXNpbmcgdW5pZ3JhbXMgaXMgZmFzdGVyIGFuZCBtb3JlIGVmZmljaWVudCwgYnV0IHdlIGRvbid0IGNhcHR1cmUgaW5mb3JtYXRpb24gYWJvdXQgd29yZCBvcmRlci4gVXNpbmcgYSBoaWdoZXIgdmFsdWUgZm9yIGBuYCBrZWVwcyBtb3JlIGluZm9ybWF0aW9uLCBidXQgdGhlIHZlY3RvciBzcGFjZSBvZiB0b2tlbnMgaW5jcmVhc2VzIGRyYW1hdGljYWxseSwgY29ycmVzcG9uZGluZyB0byBhIHJlZHVjdGlvbiBpbiB0b2tlbiBjb3VudHMuDQoNCi0gICBHb29kIHBsYWNlIGlzIDMgYnV0IDIgY2FuIHdvcmsgaWYgeW91IGRvbid0IGhhdmUgYSBsYXJnZSB2b2NhYnVsYXJ5IGluIHlvdXIgZGF0YSBzZXQNCg0KLSAgIENvbWJpbmluZyBkaWZmZXJlbnQgZGVncmVlcyBvZiBuLWdyYW1zIGNhbiBhbGxvdyB5b3UgdG8gZXh0cmFjdCBkaWZmZXJlbnQgbGV2ZWxzIG9mIGRldGFpbCBmcm9tIHRleHQgZGF0YS4gVW5pZ3JhbXMgdGVsbCB5b3Ugd2hpY2ggaW5kaXZpZHVhbCB3b3JkcyBoYXZlIGJlZW4gdXNlZCBhIGxvdCBvZiB0aW1lczsgc29tZSBvZiB0aGVzZSB3b3JkcyBjb3VsZCBiZSBvdmVybG9va2VkIGluIGJpZ3JhbSBvciB0cmlncmFtIGNvdW50cyBpZiB0aGV5IGRvbid0IGNvLWFwcGVhciB3aXRoIG90aGVyIHdvcmRzIG9mdGVuLg0KDQotICAgVW5pZ3JhbXMgYWxvbmUgZG9uJ3QgY2FwdHVyZSBtdWNoIGluZm8NCg0KYGBge3J9DQojIERpZmZlcmVudCBkZWdyZWVzIG9mIG4tZ3JhbXMNCnRmdF90b2tlbl9uZ3JhbTIgPC0gdG9rZW5pemVfbmdyYW1zKA0KICB4ID0gdGhlX2Zpcl90cmVlLA0KICBuID0gMkwsDQogIG5fbWluID0gMQ0KKQ0KDQojIERpc3BsYXkNCnRoZV9maXJfdHJlZVsxXQ0KdGZ0X3Rva2VuX25ncmFtMltbMV1dDQpgYGANCg0KIyMgDQoNCiMjIyAyLjIuNCBMaW5lcywgc2VudGVuY2VzIGFuZCBwYXJhZ3JhcGggdG9rZW5zDQoNClRva2VuaXplcnMgdG8gc3BsaXQgdGV4dCBpbnRvIGxhcmdlciB1bml0cyBvZiB0ZXh0IGxpa2UgbGluZXMsIHNlbnRlbmNlcywgYW5kIHBhcmFncmFwaHMgYXJlICoqcmFyZWx5IHVzZWQgZGlyZWN0bHkgZm9yIG1vZGVsaW5nIHB1cnBvc2VzKiosIGFzIHRoZSB0b2tlbnMgcHJvZHVjZWQgdGVuZCB0byBiZSBmYWlybHkgdW5pcXVlLiBJdCBpcyB2ZXJ5IHVuY29tbW9uIGZvciBtdWx0aXBsZSBzZW50ZW5jZXMgaW4gYSB0ZXh0IHRvIGJlIGlkZW50aWNhbCENCg0KKipIb3dldmVyLCB0aGVzZSB0b2tlbml6ZXJzIGFyZSB1c2VmdWwgZm9yIHByZXByb2Nlc3NpbmcgYW5kIGxhYmVsaW5nLioqDQoNCkZvciBleGFtcGxlLCBKYW5lIEF1c3RlbidzIG5vdmVsICpOb3J0aGFuZ2VyIEFiYmV5KiAoYXMgYXZhaWxhYmxlIGluIHRoZSAqKmphbmVhdXN0ZW5yKiogcGFja2FnZSkgaXMgYWxyZWFkeSBwcmVwcm9jZXNzZWQgd2l0aCBlYWNoIGxpbmUgYmVpbmcgYXQgbW9zdCA4MCBjaGFyYWN0ZXJzIGxvbmcuIEhvd2V2ZXIsIGl0IG1pZ2h0IGJlIHVzZWZ1bCB0byBzcGxpdCB0aGUgZGF0YSBpbnRvIGNoYXB0ZXJzIGFuZCBwYXJhZ3JhcGhzIGluc3RlYWQuDQoNCi0gICBMZXQncyBjcmVhdGUgYSBmdW5jdGlvbiB0aGF0IHRha2VzIGEgZGF0YWZyYW1lIGNvbnRhaW5pbmcgYSB2YXJpYWJsZSBjYWxsZWQgYHRleHRgIGFuZCB0dXJucyBpdCBpbnRvIGEgZGF0YWZyYW1lIHdoZXJlIHRoZSB0ZXh0IGlzIHRyYW5zZm9ybWVkIGludG8gcGFyYWdyYXBocy4NCg0KLSAgIEZpcnN0LCB3ZSBjYW4gY29sbGFwc2UgdGhlIHRleHQgaW50byBvbmUgbG9uZyBzdHJpbmcgdXNpbmcgYGNvbGxhcHNlID0gIlxuImAgdG8gZGVub3RlIGxpbmUgYnJlYWtzLA0KDQotICAgYW5kIHRoZW4gbmV4dCB3ZSBjYW4gdXNlIGB0b2tlbml6ZV9wYXJhZ3JhcGhzKClgIHRvIGlkZW50aWZ5IHRoZSBwYXJhZ3JhcGhzIGFuZCBwdXQgdGhlbSBiYWNrIGludG8gYSBkYXRhZnJhbWUuIFdlIGNhbiBhZGQgYSBwYXJhZ3JhcGggY291bnQgd2l0aCBgcm93X251bWJlcigpYC4NCg0KPiBwYXN0ZTAoLi4uLCBjb2xsYXBzZSkgaXMgZXF1aXZhbGVudCB0byBwYXN0ZSguLi4sIHNlcCA9ICIiLCBjb2xsYXBzZSksIHNsaWdodGx5IG1vcmUgZWZmaWNpZW50bHkuDQo+DQo+ICoqSWYgYSB2YWx1ZSBpcyBzcGVjaWZpZWQgZm9yIGNvbGxhcHNlLCB0aGUgdmFsdWVzIGluIHRoZSByZXN1bHQgYXJlIHRoZW4gY29uY2F0ZW5hdGVkIGludG8gYSBzaW5nbGUgc3RyaW5nLCB3aXRoIHRoZSBlbGVtZW50cyBiZWluZyBzZXBhcmF0ZWQgYnkgdGhlIHZhbHVlIG9mIGNvbGxhcHNlLioqDQoNCmBgYHtyfQ0KIyBSZXR1cm4gcGFyYWdyYXBocyBmdW5jdGlvbg0KYWRkX3BhcmFncmFwaHMgPC0gZnVuY3Rpb24oZGF0YSl7DQogIGRhdGEgJT4lIHB1bGwodGV4dCkgJT4lIA0KICAgICMgY29sbGFwc2Ugb3V0cHV0IGludG8gYSBzaW5nbGUgc3RyaW5nIA0KICAgIHBhc3RlKGNvbGxhcHNlID0gIlxuIikgJT4lIA0KICAgIHRva2VuaXplX3BhcmFncmFwaHMoKSAlPiUgDQogICAgIyBGbGF0dGVuIHRvIHByb2R1Y2UgYSB2ZWN0b3INCiAgICB1bmxpc3QoKSAlPiUgDQogICAgdGliYmxlKHRleHQgPSAuKSAlPiUgDQogICAgbXV0YXRlKHBhcmFncmFwaCA9IHJvd19udW1iZXIoKSkNCiAgDQp9DQpgYGANCg0KTm93IHdlIHRha2UgdGhlIHJhdyB0ZXh0IGRhdGEgYW5kIGFkZCB0aGUgY2hhcHRlciBjb3VudCBieSBkZXRlY3Rpbmcgd2hlbiB0aGUgY2hhcmFjdGVycyBgIkNIQVBURVIiYCBhcHBlYXJzIGF0IHRoZSBiZWdpbm5pbmcgb2YgYSBsaW5lLiBUaGVuIHdlIGBuZXN0KClgIHRoZSB0ZXh0IGNvbHVtbiwgYXBwbHkgb3VyIGBhZGRfcGFyYWdyYXBocygpYCBmdW5jdGlvbiwgYW5kIHRoZW4gYHVubmVzdCgpYCBhZ2Fpbi4NCg0KPiAqKk5lc3QoKTogY29tYmluZXMgY29sdW1ucyBhbmQgb3V0cHV0cyAxIHJvdyBmb3IgZWFjaCBub24tbmVzdGVkIGNvbHVtbioqDQo+DQo+ICoqbWFwIGFuZCB2YXJpYW50czogc2ltaWxhciB0byBsYXBwbHkgZXRjLS1mdXJ0aGVyIHJlYWRpbmcqKg0KPg0KPiAqKkFuZCoqIGluIGZpbHRlcjogKiomKiogb3IgKiosKioNCg0KYGBge3J9DQojIE1ha2UgcGFyYWdyYXBocw0KbGlicmFyeShqYW5lYXVzdGVucikNCg0Kbm9ydGhhbmdlcmFiYmV5X3BhcmFncmFwaGVkIDwtIHRpYmJsZSh0ZXh0ID0gbm9ydGhhbmdlcmFiYmV5KSAlPiUgDQogICAgICAgbXV0YXRlKGNoYXB0ZXIgPSBjdW1zdW0odGV4dCAlPiUgc3RyX2RldGVjdCgiXkNIQVBURVIgIikpKSAlPiUNCiAgICAgICBmaWx0ZXIoY2hhcHRlciA+IDAsICFzdHJfZGV0ZWN0KHRleHQsICJeQ0hBUFRFUiAiKSkgJT4lIA0KICAgICAgIG5lc3QoZGF0YSA9IHRleHQpICU+JQ0KICAgICAgIG11dGF0ZShkYXRhID0gbWFwKGRhdGEsIGFkZF9wYXJhZ3JhcGhzKSkgJT4lIA0KICAgICAgIHVubmVzdChjb2xzID0gYyhkYXRhKSkNCg0KZ2xpbXBzZShub3J0aGFuZ2VyYWJiZXlfcGFyYWdyYXBoZWQpDQoNCmBgYA0KDQpJdCBjYW4gYmUgdXNlZnVsIHRvIGJlIGFibGUgdG8gcmVzaGFwZSB0ZXh0IGRhdGEgdG8gZ2V0IGEgZGlmZmVyZW50IG9ic2VydmF0aW9uYWwgdW5pdC4gQXMgYW4gZXhhbXBsZSwgaWYgeW91IHdhbnRlZCB0byBidWlsZCBhIHNlbnRpbWVudCBjbGFzc2lmaWVyIHRoYXQgd291bGQgY2xhc3NpZnkgc2VudGVuY2VzIGFzIGhvc3RpbGUgb3Igbm90LCB0aGVuIHlvdSBuZWVkIHRvIHdvcmsgd2l0aCBhbmQgdHJhaW4geW91ciBtb2RlbCBvbiBzZW50ZW5jZXMgb2YgdGV4dC4gKipUdXJuaW5nIHBhZ2VzIG9yIHBhcmFncmFwaHMgaW50byBzZW50ZW5jZXMgaXMgYSBuZWNlc3Nhcnkgc3RlcCBpbiB5b3VyIHdvcmtmbG93LioqDQoNCkxldCB1cyBsb29rIGF0IGhvdyB3ZSBjYW4gdHVybiBgdGhlX2Zpcl90cmVlYCBmcm9tIGEgIm9uZSBsaW5lIHBlciBlbGVtZW50IiB2ZWN0b3IgdG8gYSAib25lIHNlbnRlbmNlIHBlciBlbGVtZW50LiIgYHRoZV9maXJfdHJlZWAgY29tZXMgYXMgYSB2ZWN0b3Igc28gd2Ugc3RhcnQgYnkgdXNpbmcgYHBhc3RlKClgIHRvIGNvbWJpbmUgdGhlIGxpbmVzIGJhY2sgdG9nZXRoZXIuIFdlIHVzZSBhIHNwYWNlIGFzIHRoZSBzZXBhcmF0b3IsIGFuZCB0aGVuIHdlIHBhc3MgaXQgdG8gdGhlIGB0b2tlbml6ZV9zZW50ZW5jZXMoKWAgZnVuY3Rpb24gZnJvbSB0aGUgKip0b2tlbml6ZXJzKiogcGFja2FnZSwgd2hpY2ggd2lsbCBwZXJmb3JtIHNlbnRlbmNlIHNwbGl0dGluZy4NCg0KYGBge3J9DQojIE9uZSBzZW50ZW5jZSBwZXIgZWxlbWVudA0KdGhlX2Zpcl90cmVlX3NlbnRlbmNlcyA8LSB0aGVfZmlyX3RyZWUgJT4lIA0KICBwYXN0ZShjb2xsYXBzZSA9ICIgIikgJT4lIA0KICB0b2tlbml6ZV9zZW50ZW5jZXMoKQ0KDQp0aGVfZmlyX3RyZWVfc2VudGVuY2VzW1sxXV0gJT4lIA0KICBoZWFkKCkNCmBgYA0KDQpJZiB5b3UgaGF2ZSBsaW5lcyBmcm9tIGRpZmZlcmVudCBjYXRlZ29yaWVzIGFzIHdlIGhhdmUgaW4gdGhlIGBoY2FuZGVyc2VuX2VuYCBkYXRhZnJhbWUsIHdoaWNoIGNvbnRhaW5zIGFsbCB0aGUgbGluZXMgb2YgdGhlIGZhaXJ5IHRhbGVzIGluIEVuZ2xpc2gsIHRoZW4gd2Ugd291bGQgbGlrZSB0byBiZSBhYmxlIHRvIHR1cm4gdGhlc2UgbGluZXMgaW50byBzZW50ZW5jZXMgd2hpbGUgcHJlc2VydmluZyB0aGUgYGJvb2tgIGNvbHVtbiBpbiB0aGUgZGF0YSBzZXQuIFRvIGRvIHRoaXMgd2UgdXNlIGBuZXN0KClgIGFuZCBgbWFwX2NocigpYCB0byBjcmVhdGUgYSBkYXRhZnJhbWUgd2hlcmUgZWFjaCBmYWlyeSB0YWxlIGlzIGl0cyBvd24gZWxlbWVudCBhbmQgdGhlbiB3ZSB1c2UgdGhlIGB1bm5lc3Rfc2VudGVuY2VzKClgIGZ1bmN0aW9uIGZyb20gdGhlIHRpZHl0ZXh0IHBhY2thZ2UgdG8gc3BsaXQgdGhlIHRleHQgaW50byBzZW50ZW5jZXMuDQoNCj4gKip1c2VkIGB0aWR5dGV4dDo6bm5lc3Rfc2VudGVuY2VzKClgIGFuZCBub3QgYHRva2VuaXplcnM6OnRva2VuaXplX3NlbnRlbmNlc2BiZWNhdXNlIHRoZSBkYXRhIGlzIGEgdGliYmxlKioNCg0KYGBge3J9DQojIFNwbGl0IHRleHQgaW50byBzZW50ZW5jZXMNCmhjYW5kZXJzZW5fc2VudGVuY2VzIDwtIGhjYW5kZXJzZW5fZW4gJT4lDQogICAgICAgbmVzdChkYXRhID0gYyh0ZXh0KSkgJT4lIA0KICAgICAgIG11dGF0ZShkYXRhID0gbWFwX2NocihkYXRhLCB+cGFzdGUoLngkdGV4dCwgY29sbGFwc2UgPSAiICIpKSkgJT4lIA0KICAgICAgIHVubmVzdF9zZW50ZW5jZXMoaW5wdXQgPSBkYXRhLCBvdXRwdXQgPSBzZW50ZW5jZXMpDQpgYGANCg0KTm93IHRoYXQgd2UgaGF2ZSB0dXJuZWQgdGhlIHRleHQgaW50byAib25lIHNlbnRlbmNlIHBlciBlbGVtZW50LCIgd2UgY2FuIGFuYWx5emUgb24gdGhlIHNlbnRlbmNlIGxldmVsLg0KDQojIyAyLjMgV2hlcmUgZG9lcyB0b2tlbml6YXRpb24gYnJlYWsgZG93bj8NCg0KVG9rZW5pemF0aW9uIHdpbGwgZ2VuZXJhbGx5IGJlIG9uZSBvZiB0aGUgZmlyc3Qgc3RlcHMgd2hlbiBidWlsZGluZyBhIG1vZGVsIG9yIGFueSBraW5kIG9mIHRleHQgYW5hbHlzaXMsIHNvIGl0IGlzIGltcG9ydGFudCB0byBjb25zaWRlciBjYXJlZnVsbHkgd2hhdCBoYXBwZW5zIGluIHRoaXMgc3RlcCBvZiBkYXRhIHByZXByb2Nlc3NpbmcuIEFzIHdpdGggbW9zdCBzb2Z0d2FyZSwgdGhlcmUgaXMgYSB0cmFkZS1vZmYgYmV0d2VlbiBzcGVlZCBhbmQgY3VzdG9taXphYmlsaXR5LCBhcyBkZW1vbnN0cmF0ZWQgaW4gU2VjdGlvbiBbMi42XShodHRwczovL3NtbHRhci5jb20vdG9rZW5pemF0aW9uLmh0bWwjdG9rZW5pemF0aW9uLWJlbmNobWFyaykuIFRoZSBmYXN0ZXN0IHRva2VuaXphdGlvbiBtZXRob2RzIGdpdmUgdXMgbGVzcyBjb250cm9sIG92ZXIgaG93IGl0IGlzIGRvbmUuDQoNCldoaWxlIHRoZSBkZWZhdWx0cyB3b3JrIHdlbGwgaW4gbWFueSBjYXNlcywgd2UgZW5jb3VudGVyIHNpdHVhdGlvbnMgd2hlcmUgd2Ugd2FudCB0byBpbXBvc2Ugc3RyaWN0ZXIgcnVsZXMgdG8gZ2V0IGJldHRlciBvciBkaWZmZXJlbnQgdG9rZW5pemVkIHJlc3VsdHMuDQoNCiMjIDIuNCBCdWlsZCB5b3VyIG93biB0b2tlbml6ZXINCg0KLSAgIFNvbWV0aW1lcyB0aGUgb3V0LW9mLXRoZS1ib3ggdG9rZW5pemVycyB3b24ndCBiZSBhYmxlIHRvIGRvIHdoYXQgeW91IG5lZWQgdGhlbSB0byBkby4gSW4gdGhpcyBjYXNlLCB3ZSB3aWxsIGhhdmUgdG8gd2llbGQgKipzdHJpbmdpKiovKipzdHJpbmdyKiogYW5kIHJlZ3VsYXIgZXhwcmVzc2lvbnMNCg0KLSAgIFRoZXJlIGFyZSB0d28gbWFpbiBhcHByb2FjaGVzIHRvIHRva2VuaXphdGlvbi4NCg0KICAgIDEuICAqU3BsaXQqIHRoZSBzdHJpbmcgdXAgYWNjb3JkaW5nIHRvIHNvbWUgcnVsZS4NCg0KICAgIDIuICAqRXh0cmFjdCogdG9rZW5zIGJhc2VkIG9uIHNvbWUgcnVsZS4NCg0KLSAgIFdlIGNhbiByZWFjaCBjb21wbGV4IG91dGNvbWVzIGJ5IGNoYWluaW5nIHRvZ2V0aGVyIG1hbnkgc21hbGxlciBydWxlcy4NCg0KIyMjIDIuNC4xIFRva2VuaXplIHRvIGNoYXJhY3RlcnMsIG9ubHkga2VlcGluZyBsZXR0ZXJzDQoNCkhlcmUgd2Ugd2FudCB0byBtb2RpZnkgd2hhdCBgdG9rZW5pemVfY2hhcmFjdGVycygpYCBkb2VzLCBzdWNoIHRoYXQgd2Ugb25seSBrZWVwIGxldHRlcnMuIFRoZXJlIGFyZSB0d28gbWFpbiBvcHRpb25zLiBXZSBjYW4gdXNlIGB0b2tlbml6ZV9jaGFyYWN0ZXJzKClgIGFuZCByZW1vdmUgYW55dGhpbmcgdGhhdCBpcyBub3QgYSBsZXR0ZXIsIG9yIHdlIGNhbiBleHRyYWN0IHRoZSBsZXR0ZXJzIG9uZSBieSBvbmUuIExldCdzIHRyeSB0aGUgbGF0dGVyIG9wdGlvbi4gVGhpcyBpcyBhbiAqKmV4dHJhY3QqKiB0YXNrLCBhbmQgd2Ugd2lsbCB1c2UgYHN0cl9leHRyYWN0X2FsbCgpYCBhcyBlYWNoIHN0cmluZyBoYXMgdGhlIHBvc3NpYmlsaXR5IG9mIGluY2x1ZGluZyBtb3JlIHRoYW4gb25lIHRva2VuLiAqKlNpbmNlIHdlIHdhbnQgdG8gZXh0cmFjdCBsZXR0ZXJzIHdlIGNhbiB1c2UgdGhlIGxldHRlcnMgY2hhcmFjdGVyIGNsYXNzIGBbOmFscGhhOl1gIHRvIG1hdGNoIGxldHRlcnMgYW5kIHRoZSBxdWFudGlmaWVyIGB7MX1gIHRvIG9ubHkgZXh0cmFjdCB0aGUgZmlyc3Qgb25lLioqDQoNCj4gc3RyaW5naTo6c3RyaW5naS1zZWFyY2gtcmVnZXgNCj4NCj4gP3JlZ2V4KCkNCj4NCj4gW3BhdHRlcm5dIC0gTWF0Y2ggYW55IG9uZSBjaGFyYWN0ZXIgZnJvbSB0aGUgc2V0Lg0KPg0KPiB7bn0gLSBNYXRjaCBleGFjdGx5IG4gdGltZXMNCj4NCj4gcmVndWxhciBleHByZXNzaW9ucyBsaXN0OiA8aHR0cHM6Ly9zbWx0YXIuY29tL3JlZ2V4cC5odG1sI3RhYjpjaGFyYWN0ZXJjbGFzc2VzPg0KDQpgYGB7ciBzdHJfZXh0cmFjdH0NCnN0cmluZyA8LSAiVGhpcyBzZW50ZW5jZSBpbmNsdWRlcyAyIG51bWJlcnMgYW5kIDEgcGVyaW9kLiINCg0Kc3RyX2V4dHJhY3RfYWxsKHN0cmluZyA9IHN0cmluZywNCiAgICAgICAgICAgIHBhdHRlcm4gPSAiWzphbHBoYTpdezF9IikNCmBgYA0KDQotICAgV2UgbWF5IGJlIHRlbXB0ZWQgdG8gc3BlY2lmeSB0aGUgY2hhcmFjdGVyIGNsYXNzIGFzIHNvbWV0aGluZyBsaWtlIGBbYS16QS1aXXsxfWAuICoqVGhpcyBvcHRpb24gd291bGQgcnVuIGZhc3RlciwgYnV0IHdlIHdvdWxkIGxvc2Ugbm9uLUVuZ2xpc2ggbGV0dGVyIGNoYXJhY3RlcnMuKioNCg0KYGBge3J9DQpkYW5pc2hfc2VudGVuY2UgPC0gIlPDpSBtw7hkdGUgaGFuIGVuIGdhbW1lbCBoZWtzIHDDpSBsYW5kZXZlamVuIg0KDQpzdHJfZXh0cmFjdF9hbGwoZGFuaXNoX3NlbnRlbmNlLCAiWzphbHBoYTpdezF9IikNCg0Kc3RyX2V4dHJhY3RfYWxsKGRhbmlzaF9zZW50ZW5jZSwgIlthLXpBLXpdezF9IikNCmBgYA0KDQo+IENob29zaW5nIGJldHdlZW4gYFs6YWxwaGE6XWAgYW5kIGBbYS16QS1aXWAgbWF5IHNlZW0gcXVpdGUgc2ltaWxhciwgYnV0IHRoZSByZXN1bHRpbmcgZGlmZmVyZW5jZXMgY2FuIGhhdmUgYSBiaWcgaW1wYWN0IG9uIHlvdXIgYW5hbHlzaXMuDQoNCiMjIyAyLjQuMiBBbGxvdyBmb3IgaHlwaGVuYXRlZCB3b3Jkcw0KDQpJbiBvdXIgZXhhbXBsZXMgc28gZmFyLCB3ZSBoYXZlIG5vdGljZWQgdGhhdCB0aGUgc3RyaW5nICoqImZpci10cmVlIiBpcyB0eXBpY2FsbHkgc3BsaXQgaW50byB0d28gdG9rZW5zLioqIExldCdzIGV4cGxvcmUgdHdvIGRpZmZlcmVudCBhcHByb2FjaGVzIGZvciBob3cgdG8gaGFuZGxlIHRoaXMgaHlwaGVuYXRlZCB3b3JkIGFzIG9uZSB0b2tlbi4NCg0KLSAgIEZpcnN0LCBsZXQncyBzcGxpdCBvbiB3aGl0ZSBzcGFjZSAoKipTcGFjZSwgdGFiLCB2ZXJ0aWNhbCB0YWIsIG5ld2xpbmUsIGZvcm0gZmVlZCwgY2FycmlhZ2UgcmV0dXJuKiopIDsgdGhpcyBpcyBhIGRlY2VudCB3YXkgdG8gaWRlbnRpZnkgd29yZHMgaW4gRW5nbGlzaCBhbmQgc29tZSBvdGhlciBsYW5ndWFnZXMsIGFuZCBpdCBkb2VzIG5vdCBzcGxpdCBoeXBoZW5hdGVkIHdvcmRzIGFzIHRoZSBoeXBoZW4gY2hhcmFjdGVyIGlzbid0IGNvbnNpZGVyZWQgYSB3aGl0ZS1zcGFjZS4NCg0KLSAgIFNlY29uZCwgbGV0J3MgZmluZCBhIHJlZ2V4IHRvIG1hdGNoIHdvcmRzIHdpdGggYSBoeXBoZW4gYW5kIGV4dHJhY3QgdGhvc2UuDQoNClNwbGl0dGluZyBieSB3aGl0ZSBzcGFjZSBpcyBub3QgdG9vIGRpZmZpY3VsdCBiZWNhdXNlIHdlIGNhbiB1c2UgY2hhcmFjdGVyIGNsYXNzZXMsIGFzIHNob3duIGluIFRhYmxlIFtBLjJdKGh0dHBzOi8vc21sdGFyLmNvbS9yZWdleHAuaHRtbCN0YWI6Y2hhcmFjdGVyY2xhc3NlcykuIFdlIHdpbGwgdXNlIHRoZSB3aGl0ZSBzcGFjZSBjaGFyYWN0ZXIgY2xhc3MgYFs6c3BhY2U6XWAgdG8gc3BsaXQgb3VyIHNlbnRlbmNlLg0KDQpgYGB7cn0NCnN0cl9zcGxpdChzdHJpbmcgPSAiVGhpcyBpc24ndCBhIHNlbnRlbmNlIHdpdGggaHlwaGFuYXRlZC13b3Jkcy4uIiwNCiAgICAgICAgICBwYXR0ZXJuID0gIls6c3BhY2U6XSIpDQpgYGANCg0KVGhpcyB3b3JrZWQgcHJldHR5IHdlbGwuIFRoaXMgdmVyc2lvbiBkb2Vzbid0IGRyb3AgcHVuY3R1YXRpb24sIGJ1dCB3ZSBjYW4gYWNoaWV2ZSB0aGlzIGJ5IHJlbW92aW5nIHB1bmN0dWF0aW9uIGNoYXJhY3RlcnMgYXQgdGhlIGJlZ2lubmluZyBhbmQgZW5kIG9mIHdvcmRzLg0KDQpgYGB7cn0NCnN0cl9zcGxpdCgiVGhpcyBpc24ndCBhIHNlbnRlbmNlIHdpdGggaHlwaGVuYXRlZC13b3Jkcy4iLA0KICAgICAgICAgIHBhdHRlcm4gPSAiWzpzcGFjZTpdIikgJT4lIA0KICBtYXAofiBzdHJfcmVtb3ZlX2FsbCgueCwgIl5bOnB1bmN0Ol0rfFs6cHVuY3Q6XSskIikpDQpgYGANCg0KVGhpcyByZWdleCB1c2VkIHRvIHJlbW92ZSB0aGUgcHVuY3R1YXRpb24gaXMgYSBsaXR0bGUgY29tcGxpY2F0ZWQsIHNvIGxldCdzIGRpc2N1c3MgaXQgcGllY2UgYnkgcGllY2UuDQoNCi0gICBUaGUgcmVnZXggYF5bOnB1bmN0Ol0rYCB3aWxsIGxvb2sgYXQgdGhlIGJlZ2lubmluZyBvZiB0aGUgc3RyaW5nIChgXmApIHRvIG1hdGNoIGFueSBwdW5jdHVhdGlvbiBjaGFyYWN0ZXJzIChgWzpwdW5jdDpdYCksIHdoZXJlIGl0IHdpbGwgc2VsZWN0IG9uZSBvciBtb3JlIChgK2ApLg0KDQotICAgVGhlIG90aGVyIHJlZ2V4IGBbOnB1bmN0Ol0rJGAgd2lsbCBsb29rIGZvciBwdW5jdHVhdGlvbiBjaGFyYWN0ZXJzIChgWzpwdW5jdDpdYCkgdGhhdCBhcHBlYXIgb25lIG9yIG1vcmUgdGltZXMgKGArYCkgYXQgdGhlIGVuZCBvZiB0aGUgc3RyaW5nIChgJGApLg0KDQotICAgVGhlc2Ugd2lsbCBhbHRlcm5hdGUgKGB8YCkgc28gdGhhdCB3ZSBnZXQgbWF0Y2hlcyBmcm9tIGJvdGggc2lkZXMgb2YgdGhlIHdvcmRzLg0KDQotICAgVGhlIHJlYXNvbiB3ZSB1c2UgdGhlIHF1YW50aWZpZXIgYCtgIGlzIHRoYXQgdGhlcmUgYXJlIGNhc2VzIHdoZXJlIGEgd29yZCBpcyBmb2xsb3dlZCBieSBtdWx0aXBsZSBjaGFyYWN0ZXJzIHdlIGRvbid0IHdhbnQsIHN1Y2ggYXMgYCJva2F5Li4uImAgYW5kIGAiUmVhbGx5PyEhISJgLg0KDQotICAgV2UgY2FuIHNwZWNpZnkgaG93IG1hbnkgdGltZXMgd2UgZXhwZWN0IHNvbWV0aGluZyB0byBvY2N1ciB1c2luZyBxdWFudGlmaWVycyBlZyAqKisqKigqKm9uZSBvciBtb3JlIHRpbWVzKiopDQoNCk5vdyBsZXQncyBzZWUgaWYgd2UgY2FuIGdldCB0aGUgc2FtZSByZXN1bHQgdXNpbmcgZXh0cmFjdGlvbi4gV2Ugd2lsbCBzdGFydCBieSBjb25zdHJ1Y3RpbmcgYSByZWd1bGFyIGV4cHJlc3Npb24gdGhhdCB3aWxsIGNhcHR1cmUgaHlwaGVuYXRlZCB3b3Jkczsgb3VyIGRlZmluaXRpb24gaGVyZSBpcyBhIHdvcmQgd2l0aCBvbmUgaHlwaGVuIGxvY2F0ZWQgaW5zaWRlIGl0LiBTaW5jZSB3ZSB3YW50IHRoZSBoeXBoZW4gdG8gYmUgaW5zaWRlIHRoZSB3b3JkLCB3ZSB3aWxsIG5lZWQgdG8gaGF2ZSBhIG5vbi16ZXJvIG51bWJlciBvZiBjaGFyYWN0ZXJzIG9uIGVpdGhlciBzaWRlIG9mIHRoZSBoeXBoZW4uDQoNCmBgYHtyfQ0Kc3RyX2V4dHJhY3RfYWxsKA0KICBzdHJpbmcgPSAiVGhpcyBpc24ndCBhIHNlbnRlbmNlIHdpdGggaHlwaGVuYXRlZC13b3Jkcy4iLA0KICBwYXR0ZXJuID0gIls6YWxwaGE6XSstWzphbHBoYTpdKyIpDQpgYGANCg0KPiAqKls6YWxwaGE6XSoqOiBleHRyYWN0cyBsZXR0ZXJzDQo+DQo+ICoqWzphbHBoYTpdKyoqIDogZXh0cmFjdHMgd29yZHMNCj4NCj4gKipbOmFscGhhOl0rWzphbHBoYTpdKio6IGVuc3VyZXMgdGhhdCBlYWNoIHdvcmQgaXMgbW9yZSB0aGFuIGEgY2hhcmFjdGVyIGxvbmcgc28gd29yZHMgbGlrZSAqKmEqKiBhcmUgbm90IGluY2x1ZGVkDQoNCldhaXQsIHRoaXMgb25seSBtYXRjaGVkIHRoZSBoeXBoZW5hdGVkIHdvcmQhIFRoaXMgaGFwcGVuZWQgYmVjYXVzZSB3ZSBhcmUgb25seSBtYXRjaGluZyB3b3JkcyB3aXRoIGh5cGhlbnMuIElmIHdlIGFkZCB0aGUgcXVhbnRpZmllciBgP2AgdGhlbiB3ZSBjYW4gbWF0Y2ggMCBvciAxIG9jY3VycmVuY2VzLg0KDQpgYGB7cn0NCnN0cl9leHRyYWN0X2FsbCgNCiAgc3RyaW5nID0gIlRoaXMgaXNuJ3QgYSBzZW50ZW5jZSB3aXRoIGh5cGhlbmF0ZWQtd29yZHMuIiwNCiAgcGF0dGVybiA9ICJbOmFscGhhOl0rLT9bOmFscGhhOl0rIikNCmBgYA0KDQpOb3cgd2UgYXJlIGdldHRpbmcgbW9yZSB3b3JkcywgYnV0IHRoZSBlbmRpbmcgb2YgYCJpc24ndCJgIGlzIG5vdCB0aGVyZSBhbnltb3JlIGFuZCB3ZSBsb3N0IHRoZSB3b3JkIGAiYSJgLg0KDQotICAgKipXZSBjYW4gZ2V0IG1hdGNoZXMgZm9yIHRoZSB3aG9sZSBjb250cmFjdGlvbiBieSBleHBhbmRpbmcgdGhlIGNoYXJhY3RlciBjbGFzcyBgWzphbHBoYTpdYCB0byBpbmNsdWRlIHRoZSBjaGFyYWN0ZXIgYCdgLiBXZSBkbyB0aGF0IGJ5IHVzaW5nIGBbWzphbHBoYTpdJ11gLioqDQoNCmBgYHtyfQ0KIyBFcmljJ3MgYXBwcm9hY2gNCnN0cl9leHRyYWN0X2FsbCgNCiAgc3RyaW5nID0gIlRoaXMgaXNuJ3QgYSBzZW50ZW5jZSB3aXRoIGh5cGhlbmF0ZWQtd29yZHMuIiwNCiAgcGF0dGVybiA9ICJbWzphbHBoYTpdJy1dKyIpDQoNCiMgRW1pbCdzIGFwcHJvYWNoDQpzdHJfZXh0cmFjdF9hbGwoDQogIHN0cmluZyA9ICJUaGlzIGlzbid0IHNlbnRlbmNlIHdpdGggaHlwaGVuYXRlZC13b3Jkcy4iLA0KICBwYXR0ZXJuID0gIltbOmFscGhhOl0nXSstP1tbOmFscGhhOl0nXSsiKQ0KYGBgDQoNCk5leHQsIHdlIG5lZWQgdG8gZmluZCBvdXQgd2h5IGAiYSJgIHdhc24ndCBtYXRjaGVkLiBJZiB3ZSBsb29rIGF0IHRoZSByZWd1bGFyIGV4cHJlc3Npb24sIHdlIHJlbWVtYmVyIHRoYXQgd2UgaW1wb3NlZCB0aGUgcmVzdHJpY3Rpb24gdGhhdCBhIG5vbi16ZXJvIG51bWJlciBvZiBjaGFyYWN0ZXJzIG5lZWRlZCB0byBzdXJyb3VuZCB0aGUgaHlwaGVuIHRvIGF2b2lkIG1hdGNoaW5nIHdvcmRzIHRoYXQgc3RhcnQgb3IgZW5kIHdpdGggYSBoeXBoZW4uICoqVGhpcyBtZWFucyB0aGF0IHRoZSBzbWFsbGVzdCBwb3NzaWJsZSBwYXR0ZXJuIG1hdGNoZWQgaXMgdHdvIGNoYXJhY3RlcnMgbG9uZy4qKiBXZSBjYW4gZml4IHRoaXMgYnkgdXNpbmcgYW4gYWx0ZXJuYXRpb24gd2l0aCBgfGAuIFdlIHdpbGwga2VlcCBvdXIgcHJldmlvdXMgbWF0Y2ggb24gdGhlIGxlZnQtaGFuZCBzaWRlLCBhbmQgaW5jbHVkZSBgWzphbHBoYTpdezF9YCBvbiB0aGUgcmlnaHQtaGFuZCBzaWRlIHRvIG1hdGNoIHRoZSBzaW5nbGUgbGVuZ3RoIHdvcmRzIHRoYXQgd29uJ3QgYmUgcGlja2VkIHVwIGJ5IHRoZSBsZWZ0LWhhbmQgc2lkZS4gTm90aWNlIGhvdyB3ZSBhcmVuJ3QgdXNpbmcgYFtbOmFscGhhOl0nXWAgc2luY2Ugd2UgYXJlIG5vdCBpbnRlcmVzdGVkIGluIG1hdGNoaW5nIHNpbmdsZSBgJ2AgY2hhcmFjdGVycy4NCg0KYGBge3J9DQpzdHJfZXh0cmFjdF9hbGwoDQogIHN0cmluZyA9ICJUaGlzIGlzbid0IGEgc2VudGVuY2Ugd2l0aCBoeXBoZW5hdGVkLXdvcmRzLiIsDQogIHBhdHRlcm4gPSAiW1s6YWxwaGE6XSddKy0/W1s6YWxwaGE6XSddK3xbOmFscGhhOl17MX0iDQopDQoNCmBgYA0KDQojIyMgMi40LjMgV3JhcHBpbmcgaXQgaW4gYSBmdW5jdGlvbg0KDQpXZSBoYXZlIHNob3duIGhvdyB3ZSBjYW4gdXNlIHJlZ3VsYXIgZXhwcmVzc2lvbnMgdG8gZXh0cmFjdCB0aGUgdG9rZW5zIHdlIHdhbnQsIHBlcmhhcHMgdG8gdXNlIGluIG1vZGVsaW5nLiBTbyBmYXIsIHRoZSBjb2RlIGhhcyBiZWVuIHJhdGhlciB1bnN0cnVjdHVyZWQuIFdlIHdvdWxkIGlkZWFsbHkgd3JhcCB0aGVzZSB0YXNrcyBpbnRvIGZ1bmN0aW9ucyB0aGF0IGNhbiBiZSB1c2VkIHRoZSBzYW1lIHdheSBgdG9rZW5pemVfd29yZHMoKWAgaXMgdXNlZC4NCg0KTGV0J3Mgc3RhcnQgd2l0aCB0aGUgZXhhbXBsZSB3aXRoIGh5cGhlbmF0ZWQgd29yZHMuIFRvIG1ha2UgdGhlIGZ1bmN0aW9uIGEgbGl0dGxlIG1vcmUgZmxleGlibGUsIGxldCdzIGFkZCBhbiBvcHRpb24gdG8gdHJhbnNmb3JtIGFsbCB0aGUgb3V0cHV0IHRvIGxvd2VyY2FzZS4NCg0KYGBge3IgZnVuY3Rpb25faHlwaGVufQ0KIyBGdW5jdGlvbiB0byBoeXBoZW5hdGUgd29yZHMNCnRva2VuaXplX2h5cGhlbmF0ZWRfd29yZHMgPC0gZnVuY3Rpb24oeCwgbG93ZXJjYXNlID0gVFJVRSl7DQogIGlmIChsb3dlcmNhc2UpIHggPSBzdHJfdG9fbG93ZXIoeCkNCiAgDQogIHN0cl9zcGxpdCh4LCAiWzpzcGFjZTpdIikgJT4lIA0KICAgIG1hcCh+IHN0cl9yZW1vdmVfYWxsKC54LCAiXls6cHVuY3Q6XSt8WzpwdW5jdDpdKyQiKSkNCn0NCg0KDQojIEJvb2sgZXh0cmFjdA0KdGhlX2Zpcl90cmVlWzE6M10NCg0KIyBDYWxsIGZ1bmN0aW9uDQp0b2tlbml6ZV9oeXBoZW5hdGVkX3dvcmRzKHggPSB0aGVfZmlyX3RyZWVbMTozXSkNCmBgYA0KDQpcDQpOb3RpY2UgaG93IHdlIHRyYW5zZm9ybWVkIHRvIGxvd2VyY2FzZSBmaXJzdCBiZWNhdXNlIHRoZSByZXN0IG9mIHRoZSBvcGVyYXRpb25zIGFyZSBjYXNlIGluc2Vuc2l0aXZlLg0KDQpOZXh0IGxldCdzIHR1cm4gb3VyIGNoYXJhY3RlciBuLWdyYW0gdG9rZW5pemVyIGludG8gYSBmdW5jdGlvbiwgd2l0aCBhIHZhcmlhYmxlIGBuYCBhcmd1bWVudC4NCg0KPiBMaXR0bGUgaWRlYSBvZiB3aGF0IGlzIGdvaW5nIG9uIGJlbG93DQoNCmBgYHtyfQ0KdG9rZW5pemVfY2hhcmFjdGVyX25ncmFtIDwtIGZ1bmN0aW9uKHgsIG4pIHsNCiAgbmdyYW1fbG9jIDwtIHN0cl9sb2NhdGVfYWxsKHgsIHBhc3RlMCgiKD89KFxcd3siLCBuLCAifSkpIikpDQoNCiAgbWFwMihuZ3JhbV9sb2MsIHgsIH5zdHJfc3ViKC55LCAueFssIDFdLCAueFssIDFdICsgbiAtIDEpKQ0KfQ0KDQp0b2tlbml6ZV9jaGFyYWN0ZXJfbmdyYW0odGhlX2Zpcl90cmVlWzE6M10sIG4gPSAzKQ0KYGBgDQoNCldlIGNhbiB1c2UgYHBhc3RlMCgpYCBpbiB0aGlzIGZ1bmN0aW9uIHRvIGNvbnN0cnVjdCBhbiBhY3R1YWwgcmVnZXguDQoNCiMjICoqMi41IFRva2VuaXphdGlvbiBmb3Igbm9uLUxhdGluIGFscGhhYmV0cyoqDQoNCk91ciBkaXNjdXNzaW9uIG9mIHRva2VuaXphdGlvbiBzbyBmYXIgaGFzIGZvY3VzZWQgb24gdGV4dCB3aGVyZSB3b3JkcyBhcmUgc2VwYXJhdGVkIGJ5IHdoaXRlIHNwYWNlIGFuZCBwdW5jdHVhdGlvbi4gRm9yIHN1Y2ggdGV4dCwgZXZlbiBhIHF1aXRlIGJhc2ljIHRva2VuaXplciBjYW4gZ2l2ZSBkZWNlbnQgcmVzdWx0cy4gSG93ZXZlciwgbWFueSB3cml0dGVuIGxhbmd1YWdlcyBkb24ndCBzZXBhcmF0ZSB3b3JkcyBpbiB0aGlzIHdheS4NCg0KT25lIG9mIHRoZXNlIGxhbmd1YWdlcyBpcyBDaGluZXNlIHdoZXJlIGVhY2ggIndvcmQiIGNhbiBiZSByZXByZXNlbnRlZCBieSBvbmUgb3IgbW9yZSBjb25zZWN1dGl2ZSBjaGFyYWN0ZXJzLiBTcGxpdHRpbmcgQ2hpbmVzZSB0ZXh0IGludG8gd29yZHMgaXMgY2FsbGVkICJ3b3JkIHNlZ21lbnRhdGlvbiIgYW5kIGlzIHN0aWxsIGFuIGFjdGl2ZSBhcmVhIG9mIHJlc2VhcmNoIChbTWEsIEdhbmNoZXYsIGFuZCBXZWlzcyAyMDE4XShodHRwczovL3NtbHRhci5jb20vdG9rZW5pemF0aW9uLmh0bWwjcmVmLW1hLWV0YWwtMjAxOC1zdGF0ZSk7IFtIdWFuZyBldCBhbC4gMjAyMF0oaHR0cHM6Ly9zbWx0YXIuY29tL3Rva2VuaXphdGlvbi5odG1sI3JlZi1IdWFuZzIwMTkpKS4NCg0KV2UgYXJlIG5vdCBnb2luZyB0byBnbyBpbnRvIGRlcHRoIGluIHRoaXMgYXJlYSwgYnV0IHdlIHdhbnQgdG8gc2hvd2Nhc2UgdGhhdCB3b3JkIHNlZ21lbnRhdGlvbiBpcyBpbmRlZWQgcG9zc2libGUgd2l0aCBSIGFzIHdlbGwuIFdlIHVzZSB0aGUgKipqaWViYVIqKiBwYWNrYWdlIChbV2VuZmVuZyBhbmQgWWFueWkgMjAxOV0oaHR0cHM6Ly9zbWx0YXIuY29tL3Rva2VuaXphdGlvbi5odG1sI3JlZi1SLWppZWJhUikpLiBJdCBpcyBjb25jZXB0dWFsbHkgc2ltaWxhciB0byB0aGUgKip0b2tlbml6ZXJzKiogcGFja2FnZSwgYnV0IHdlIG5lZWQgdG8gY3JlYXRlIGEgd29ya2VyIHRoYXQgaXMgcGFzc2VkIGludG8gYHNlZ21lbnQoKWAgYWxvbmcgd2l0aCB0aGUgc3RyaW5nIHdlIHdhbnQgdG8gc2VnbWVudC4NCg0KYGBge3J9DQpsaWJyYXJ5KGppZWJhUikNCg0Kd29yZHMgPC0gYygi5LiL6Z2i5piv5LiN5YiG6KGM6L6T5Ye655qE57uT5p6cIiwgIuS4i+mdouaYr+S4jei+k+WHuueahOe7k+aenCIpDQoNCmVuZ2luZTEgPC0gd29ya2VyKGJ5bGluZXMgPSBUKQ0KDQpzZWdtZW50KHdvcmRzLCBlbmdpbmUxKQ0KYGBgDQoNCiMjICoqMi43IFN1bW1hcnkqKg0KDQotICAgVG8gYnVpbGQgYSBwcmVkaWN0aXZlIG1vZGVsLCB0ZXh0IGRhdGEgbmVlZHMgdG8gYmUgc3BsaXQgaW50byBtZWFuaW5nZnVsIHVuaXRzLCBjYWxsZWQgdG9rZW5zLg0KDQotICAgRmFzdCBhbmQgY29uc2lzdGVudCB0b2tlbml6ZXJzIGFyZSBhdmFpbGFibGUsIGJ1dCB1bmRlcnN0YW5kaW5nIGhvdyB0aGV5IGJlaGF2ZSBhbmQgaW4gd2hhdCBjaXJjdW1zdGFuY2VzIHRoZXkgd29yayBiZXN0IHdpbGwgc2V0IHlvdSB1cCBmb3Igc3VjY2Vzcy4NCg0KLSAgIE9uY2UgdGV4dCBkYXRhIGlzIHRva2VuaXplZCwgYSBjb21tb24gbmV4dCBwcmVwcm9jZXNzaW5nIHN0ZXAgaXMgdG8gY29uc2lkZXIgaG93IHRvIGhhbmRsZSB2ZXJ5IGNvbW1vbiB3b3JkcyB0aGF0IGFyZSBub3QgdmVyeSBpbmZvcm1hdGl2ZS0tLSBzdG9wIHdvcmRzLg0KDQpgYGB7ciBldmFsPUZBTFNFLCBpbmNsdWRlPUZBTFNFfQ0Kc3BsPSAiSSBhbSBncm9vdCAxIg0KdG9rZW5pemVfY2hhcmFjdGVycyhzcGwpDQpgYGANCg0KYGBge3IgZXZhbD1GQUxTRSwgaW5jbHVkZT1GQUxTRX0NCnJmIDwtIGZ1bmN0aW9uKHgpew0KICBzYW1wbGUoeCwgMSkNCn0NCg0KZGZjPSB0aWJibGUoDQogIHIgPSBjKDEsMiksDQogIGMgPSBjKDIsMykNCikNCm1hcF9kZnIoZGZjLCByZikNCmBgYA0KDQpgYGB7ciBldmFsPUZBTFNFLCBpbmNsdWRlPUZBTFNFfQ0KVmlldyhociAlPiUgDQogICAgICAgcGFzdGUoY29sbGFwc2UgPSAiXG4iKSAlPiUgDQogICAgICAgdG9rZW5pemVfcGFyYWdyYXBocygpICU+JSANCiAgICAgICB1bmxpc3QoKSAlPiUgDQogICAgICAgdGliYmxlKHRleHQgPSAuKSAlPiUgDQogICAgICAgbXV0YXRlKG4gPSByb3dfbnVtYmVyKCkpDQogICAgICkNCmBgYA0KDQpgYGB7ciBldmFsPUZBTFNFLCBpbmNsdWRlPUZBTFNFfQ0KaHIgPC0gYygiRGVhciBEciBOZ2V0aGEiLA0KICAgICAgICAiSSB3aWxsIG1pc3MgeW91IGV2ZXJ5ZGF5IiwNCiAgICAgICAgIkhvdyBjYW4gSSBnZXQgdGhyb3VnaCB0aGlzPyIsDQogICAgICAgICJcbiIsDQogICAgICAgICJUaGFuayB5b3UgZm9yIGJlbGlldmluZyBpbiBtZSEiKQ0KYGBgDQo=