Stop words: Common words that carry little (or perhaps no) meaningful information are called stop words. It is common advice and practice to remove stop words for various NLP tasks, but the task of stop word removal is more nuanced than many resources may lead you to believe.
knitr::opts_chunk$set(warning = F, message = F)
suppressWarnings(if (!require("pacman"))install.packages("pacman"))
pacman::p_load(tidyverse, tidytext, tokenizers, hcandersenr, here, stopwords)
3.1 Using premade stop word lists
A quick option for using stop words is to get a list that has already been created. You should always inspect and verify the list you are using, both to make sure it hasn’t changed since you used it last, and also to check that it is appropriate for your use case.
The stopwords package contains a comprehensive collection of stop word lists in one place for ease of use in analysis and other packages.
Before we start delving into the content inside the lists, let’s take a look at how many words are included in each.
library(stopwords)
stopwords_getsources()
## [1] "snowball" "stopwords-iso" "misc" "smart"
## [5] "marimo" "ancient" "nltk" "perseus"
# Number of words
length(stopwords(source = "snowball"))
## [1] 175
length(stopwords(source = "smart"))
## [1] 571
length(stopwords(source = "stopwords-iso"))
## [1] 1298
The lengths of these lists are quite different, with the longest list being over seven times longer than the shortest!
# Finding words in snowball but not in smart list
setdiff(x = stopwords(source = "snowball"),
y = stopwords(source = "smart"))
## [1] "she's" "he'd" "she'd" "he'll" "she'll" "shan't" "mustn't"
## [8] "when's" "why's" "how's"
All these words are contractions. This is not because the SMART lexicon doesn’t include contractions; if we look, there are almost 50 of them.
str_detect: returns TRUE/FALSE– good in dplyr::filter
str_subset: returns the detected string
# Contractions in smart lexicon
str_subset(string = stopwords(source = "smart"),
pattern = "'")
## [1] "a's" "ain't" "aren't" "c'mon" "c's" "can't"
## [7] "couldn't" "didn't" "doesn't" "don't" "hadn't" "hasn't"
## [13] "haven't" "he's" "here's" "i'd" "i'll" "i'm"
## [19] "i've" "isn't" "it'd" "it'll" "it's" "let's"
## [25] "shouldn't" "t's" "that's" "there's" "they'd" "they'll"
## [31] "they're" "they've" "wasn't" "we'd" "we'll" "we're"
## [37] "we've" "weren't" "what's" "where's" "who's" "won't"
## [43] "wouldn't" "you'd" "you'll" "you're" "you've"
We seem to have stumbled upon an inconsistency: why does SMART include "he's"
but not "she's"
🤷?
This is once again a reminder that we should always look carefully at any pre-made word list or another artifact we use to make sure it works well with our needs.
It is perfectly acceptable to start with a premade word list and remove or append additional words according to your particular use case.
3.1.1 Stop word removal in R
Now that we have seen stop word lists, we can move forward with removing these words. The particular way we remove stop words depends on the shape of our data.
If you have your text in a tidy format with one word per row, you can use filter()
from dplyr with a negated %in%
if you have the stop words as a vector
or you can use anti_join()
from dplyr if the stop words are in a tibble()
.
Like in our previous chapter, let’s examine the text of “The Fir-Tree” by Hans Christian Andersen, and use tidytext to tokenize the text into words.
library(hcandersenr)
library(tidytext)
library(tidyverse)
# Tibble of the fir tree book
fir_tree <- hca_fairytales() %>%
filter(book == "The fir tree", language == "English")
# Tokenize into words
tidy_fir_tree <- fir_tree %>%
unnest_tokens(input = text, output = word, token = "words")
Let’s use the Snowball stop word list as an example. Since the stop words return from this function as a vector, we will use filter()
.
# Remove stop words using filter
tidy_fir_tree %>%
filter(!(word %in% stopwords(source = "snowball"))) %>%
slice_head(n = 10)
If we use the get_stopwords()
function from tidytext instead, then we can use the anti_join()
function.
anti_join() return all rows from x without a match in y.
# “Filtering” joins keep cases from the LHS
# Remove stop words using anti_join since tidytext returns a tibble
tidy_fir_tree %>%
anti_join(get_stopwords(source = "snowball")) %>%
slice_head(n = 10)
3.2 Creating your own stop words list
Another way to get a stop word list is to create one yourself. Let’s explore a few different ways to find appropriate words to use. We will use the tokenized data from “The Fir-Tree” as a first example. Let’s take the words and rank them by their count or frequency.
# Most frequent words in the fir tree
tidy_fir_tree %>%
count(word, sort = TRUE) %>%
slice_head(n = 23)
We recognize many of what we would consider stop words in the first column here, with three big exceptions. We see "tree"
at 3, "fir"
at 12, and "little"
at 22. These words appear high on our list, but they do provide valuable information as they all reference the main character. What went wrong with this approach?
Creating a stop word list using high-frequency words works best when it is created on a corpus of documents, not an individual document. This is because the words found in a single document will be document-specific and the overall pattern of words will not generalize that well.
The word "tree"
does seem important as it is about the main character, but it could also be appearing so often that it stops providing any information.
Let’s try a different approach, extracting high-frequency words from the corpus of all English fairy tales by H.C. Andersen.
hca_fairytales() %>%
filter(language == "English") %>%
unnest_tokens(output = word, input = text) %>%
count(word, sort = TRUE) %>%
slice_head(n = 25)
This list is more appropriate for our concept of stop words, and now it is time for us to make some choices.
Which words should we add and/or remove based on prior information? Selecting the number of words to remove is best done by a case-by-case basis as it can be difficult to determine a priori how many different “meaningless” words appear in a corpus. Our suggestion is to start with a low number like 20 and increase by 10 words until you get to words that are not appropriate as stop words for your analytical purpose.
It is worth keeping in mind that such a list is not perfect. Depending on how your text was generated or processed, strange tokens can surface as possible stop words due to encoding or optical character recognition errors. Further, these results are based on the corpus of documents we have available, which is potentially biased. In our example here, all the fairy tales were written by the same European white man from the early 1800s.
Try an inverse document frequency (IDF) of each word. The IDF of a word is a quantity that is low for commonly-used words in a collection of documents and high for words not used often in a collection of documents. It is typically defined as
\[
idf(term)= ln(\frac{n_{documents}}{n_{documents containing term}})
\]
If the word “dog” appears in 4 out of 100 documents then it would have an idf("dog") = log(100/4) = 3.22
, and if the word “cat” appears in 99 out of 100 documents then it would have an idf("cat") = log(100/99) = 0.01
. Notice how the idf values goes to zero (as a matter of fact when a term appears in all the documents then the idf of that word is 0 log(100/100) = log(1) = 0
), the more documents it is contained in. What happens if we create a stop word list based on words with the lowest IDF? The following function takes a tokenized dataframe and returns a dataframe with a column for each word and a column for the IDF.
#library(rlang)
df <- hca_fairytales() %>%
filter(language == "English") %>%
unnest_tokens(output = word, input = text)
# Unique words in the whole corpus
words <- df %>%
pull(word) %>%
unique()
# Number of books in the corpus
n_docs <- df %>%
pull(book) %>%
unique() %>%
length()
# Unique words in the corpus found in each book
n_words <- (df %>%
nest(data = c(word)) %>%
pull(data) %>%
map_dfc(~ words %in% unique(pull(.x, word))) %>%
rowSums())
tibble(word = words,
idf = log(n_docs / n_words)) %>%
arrange((idf)) %>%
slice_head(n = 25)
This can be put in a functions as:
calc_idf <- function(df, word, document) {
words <- df %>% pull({{word}}) %>% unique()
n_docs <- length(unique(pull(df, {{document}})))
n_words <- df %>%
nest(data = c({{word}})) %>%
pull(data) %>%
map_dfc(~ words %in% unique(pull(.x, {{word}}))) %>%
rowSums()
tibble(word = words,
idf = log(n_docs / n_words))
}
{{ }}
allows you to use tidyverse functions in user defined function to access df variables? -ish..
See: https://www.tidyverse.org/blog/2019/06/rlang-0-4-0/#a-simpler-interpolation-pattern-with-
This time we get better results. The list starts with “a,” “the,” “and,” and “to” and continues with many more reasonable choices of stop words. We need to look at these results manually to turn this into a list. We need to go as far down in rank as we are comfortable with. You as a data practitioner are in full control of how you want to create the list. If you don’t want to include “little” you are still able to add “are” to your list even though it is lower on the list.
3.3 All stop word lists are context-specific
Context is important in text modeling, so it is important to ensure that the stop word lexicon you use reflects the word space that you are planning on using it in. One common concern to consider is how pronouns bring information to your text. Pronouns are included in many different stop word lists (although inconsistently), but they will often not be noise in text data
On the other hand, sometimes you will have to add in words yourself, depending on the domain. If you are working with texts for dessert recipes, certain ingredients (sugar, eggs, water) and actions (whisking, baking, stirring) may be frequent enough to pass your stop word threshold, but you may want to keep them as they may be informative. Throwing away “eggs” as a common word would make it harder or downright impossible to determine if certain recipes are vegan or not while whisking and stirring may be fine to remove as distinguishing between recipes that do and don’t require a whisk might not be that big of a deal.
3.4 What happens when you remove stop words
larger stop word lists remove more words than shorter stop word lists. In this example with fairy tales, over half of the words have been removed, with the largest list removing over 80% of the words.
Handling misspellings when using premade lists can be done by manually adding common misspellings. You could imagine creating all words that are a certain string distance away from the stop words, but we do not recommend this as you would quickly include informative words this way.
One of the downsides of creating your own stop word lists using frequencies is that you are limited to using words that you have already observed. It could happen that “she’d” is included in your training corpus but the word “he’d” did not reach the threshold. This is a case where you need to look at your words and adjust accordingly. Here the large premade stop word lists can serve as inspiration for missing words.
Given the right list of words, we see no harm to the model performance, and sometimes find improvement due to noise reduction (Feldman, and Sanger 2007).
3.6 Summary
In many standard NLP workflows, the removal of stop words is presented as a default or the correct choice without comment. Although removing stop words can improve the accuracy of your machine learning using text data, choices around such a step are complex. The content of existing stop word lists varies tremendously, and the available strategies for building your own can have subtle to not-so-subtle effects on your model results.
LS0tDQp0aXRsZTogJ05hdHVyYWwgTGFuZ3VhZ2UgRmVhdHVyZXM6IENoYXB0ZXIgMyBTdG9wIFdvcmRzJw0Kb3V0cHV0Og0KICBodG1sX2RvY3VtZW50Og0KICAgIGNzczogc3R5bGVfNy5jc3MNCiAgICBkZl9wcmludDogcGFnZWQNCiAgICB0aGVtZTogZmxhdGx5DQogICAgaGlnaGxpZ2h0OiBicmVlemVkYXJrDQogICAgdG9jOiB5ZXMNCiAgICB0b2NfZmxvYXQ6IHllcw0KICAgIGNvZGVfZG93bmxvYWQ6IHllcw0KLS0tDQoNCioqU3RvcCB3b3JkcyoqOiBDb21tb24gd29yZHMgdGhhdCBjYXJyeSBsaXR0bGUgKG9yIHBlcmhhcHMgbm8pIG1lYW5pbmdmdWwgaW5mb3JtYXRpb24gYXJlIGNhbGxlZCAqc3RvcCB3b3JkcyouIEl0IGlzIGNvbW1vbiBhZHZpY2UgYW5kIHByYWN0aWNlIHRvIHJlbW92ZSBzdG9wIHdvcmRzIGZvciB2YXJpb3VzIE5MUCB0YXNrcywgYnV0IHRoZSB0YXNrIG9mIHN0b3Agd29yZCByZW1vdmFsIGlzIG1vcmUgbnVhbmNlZCB0aGFuIG1hbnkgcmVzb3VyY2VzIG1heSBsZWFkIHlvdSB0byBiZWxpZXZlLg0KDQpgYGB7ciBzZXR1cH0NCmtuaXRyOjpvcHRzX2NodW5rJHNldCh3YXJuaW5nID0gRiwgbWVzc2FnZSA9IEYpDQoNCmBgYA0KDQpgYGB7cn0NCnN1cHByZXNzV2FybmluZ3MoaWYgKCFyZXF1aXJlKCJwYWNtYW4iKSlpbnN0YWxsLnBhY2thZ2VzKCJwYWNtYW4iKSkNCg0KcGFjbWFuOjpwX2xvYWQodGlkeXZlcnNlLCB0aWR5dGV4dCwgdG9rZW5pemVycywgaGNhbmRlcnNlbnIsIGhlcmUsIHN0b3B3b3JkcykNCmBgYA0KDQojIyAqKjMuMSBVc2luZyBwcmVtYWRlIHN0b3Agd29yZCBsaXN0cyoqDQoNCkEgcXVpY2sgb3B0aW9uIGZvciB1c2luZyBzdG9wIHdvcmRzIGlzIHRvIGdldCBhIGxpc3QgdGhhdCBoYXMgYWxyZWFkeSBiZWVuIGNyZWF0ZWQuIFlvdSBzaG91bGQgYWx3YXlzIGluc3BlY3QgYW5kIHZlcmlmeSB0aGUgbGlzdCB5b3UgYXJlIHVzaW5nLCBib3RoIHRvIG1ha2Ugc3VyZSBpdCBoYXNuJ3QgY2hhbmdlZCBzaW5jZSB5b3UgdXNlZCBpdCBsYXN0LCBhbmQgYWxzbyB0byBjaGVjayB0aGF0IGl0IGlzIGFwcHJvcHJpYXRlIGZvciB5b3VyIHVzZSBjYXNlLg0KDQo+IFRoZSAqKnN0b3B3b3JkcyoqIHBhY2thZ2UgY29udGFpbnMgYSBjb21wcmVoZW5zaXZlIGNvbGxlY3Rpb24gb2Ygc3RvcCB3b3JkIGxpc3RzIGluIG9uZSBwbGFjZSBmb3IgZWFzZSBvZiB1c2UgaW4gYW5hbHlzaXMgYW5kIG90aGVyIHBhY2thZ2VzLg0KDQpCZWZvcmUgd2Ugc3RhcnQgZGVsdmluZyBpbnRvIHRoZSBjb250ZW50IGluc2lkZSB0aGUgbGlzdHMsIGxldCdzIHRha2UgYSBsb29rIGF0IGhvdyBtYW55IHdvcmRzIGFyZSBpbmNsdWRlZCBpbiBlYWNoLg0KDQpgYGB7cn0NCmxpYnJhcnkoc3RvcHdvcmRzKQ0Kc3RvcHdvcmRzX2dldHNvdXJjZXMoKQ0KDQojIE51bWJlciBvZiB3b3Jkcw0KbGVuZ3RoKHN0b3B3b3Jkcyhzb3VyY2UgPSAic25vd2JhbGwiKSkNCmxlbmd0aChzdG9wd29yZHMoc291cmNlID0gInNtYXJ0IikpDQpsZW5ndGgoc3RvcHdvcmRzKHNvdXJjZSA9ICJzdG9wd29yZHMtaXNvIikpDQpgYGANCg0KVGhlIGxlbmd0aHMgb2YgdGhlc2UgbGlzdHMgYXJlIHF1aXRlIGRpZmZlcmVudCwgd2l0aCB0aGUgbG9uZ2VzdCBsaXN0IGJlaW5nIG92ZXIgc2V2ZW4gdGltZXMgbG9uZ2VyIHRoYW4gdGhlIHNob3J0ZXN0IQ0KDQotICAgSW50ZXJwcmV0ICoqVXBzZXQgcGxvdCoqDQoNCmBgYHtyfQ0KIyBGaW5kaW5nIHdvcmRzIGluIHNub3diYWxsIGJ1dCBub3QgaW4gc21hcnQgbGlzdA0Kc2V0ZGlmZih4ID0gc3RvcHdvcmRzKHNvdXJjZSA9ICJzbm93YmFsbCIpLA0KICAgICAgICB5ID0gc3RvcHdvcmRzKHNvdXJjZSA9ICJzbWFydCIpKQ0KYGBgDQoNCkFsbCB0aGVzZSB3b3JkcyBhcmUgY29udHJhY3Rpb25zLiBUaGlzICoqaXMgKm5vdCogYmVjYXVzZSoqIHRoZSBTTUFSVCBsZXhpY29uIGRvZXNuJ3QgaW5jbHVkZSBjb250cmFjdGlvbnM7IGlmIHdlIGxvb2ssIHRoZXJlIGFyZSBhbG1vc3QgNTAgb2YgdGhlbS4NCg0KPiAqKnN0cl9kZXRlY3QqKjogcmV0dXJucyBUUlVFL0ZBTFNFLS0gZ29vZCBpbiBkcGx5cjo6ZmlsdGVyDQo+DQo+ICoqc3RyX3N1YnNldCoqOiByZXR1cm5zIHRoZSBkZXRlY3RlZCBzdHJpbmcNCg0KYGBge3J9DQojIENvbnRyYWN0aW9ucyBpbiBzbWFydCBsZXhpY29uDQpzdHJfc3Vic2V0KHN0cmluZyA9IHN0b3B3b3Jkcyhzb3VyY2UgPSAic21hcnQiKSwNCiAgICAgICAgICAgcGF0dGVybiA9ICInIikNCmBgYA0KDQpXZSBzZWVtIHRvIGhhdmUgc3R1bWJsZWQgdXBvbiBhbiBpbmNvbnNpc3RlbmN5OiB3aHkgZG9lcyBTTUFSVCBpbmNsdWRlIGAiaGUncyJgIGJ1dCBub3QgYCJzaGUncyJgIPCfpLc/DQoNClRoaXMgaXMgb25jZSBhZ2FpbiBhIHJlbWluZGVyIHRoYXQgd2Ugc2hvdWxkIGFsd2F5cyBsb29rIGNhcmVmdWxseSBhdCBhbnkgcHJlLW1hZGUgd29yZCBsaXN0IG9yIGFub3RoZXIgYXJ0aWZhY3Qgd2UgdXNlIHRvIG1ha2Ugc3VyZSBpdCB3b3JrcyB3ZWxsIHdpdGggb3VyIG5lZWRzLg0KDQo+ICoqSXQgaXMgcGVyZmVjdGx5IGFjY2VwdGFibGUgdG8gc3RhcnQgd2l0aCBhIHByZW1hZGUgd29yZCBsaXN0IGFuZCByZW1vdmUgb3IgYXBwZW5kIGFkZGl0aW9uYWwgd29yZHMgYWNjb3JkaW5nIHRvIHlvdXIgcGFydGljdWxhciB1c2UgY2FzZS4qKg0KDQojIyMgMy4xLjEgU3RvcCB3b3JkIHJlbW92YWwgaW4gUg0KDQpOb3cgdGhhdCB3ZSBoYXZlIHNlZW4gc3RvcCB3b3JkIGxpc3RzLCB3ZSBjYW4gbW92ZSBmb3J3YXJkIHdpdGggcmVtb3ZpbmcgdGhlc2Ugd29yZHMuIFRoZSBwYXJ0aWN1bGFyIHdheSB3ZSByZW1vdmUgc3RvcCB3b3JkcyBkZXBlbmRzIG9uIHRoZSAqKnNoYXBlIG9mIG91ciBkYXRhKiouDQoNCi0gICBJZiB5b3UgaGF2ZSB5b3VyIHRleHQgaW4gYSB0aWR5IGZvcm1hdCB3aXRoIG9uZSB3b3JkIHBlciByb3csIHlvdSBjYW4gdXNlIGBmaWx0ZXIoKWAgZnJvbSAqKmRwbHlyKiogd2l0aCBhIG5lZ2F0ZWQgYCVpbiVgIGlmIHlvdSBoYXZlIHRoZSBzdG9wIHdvcmRzIGFzIGEgdmVjdG9yDQoNCi0gICBvciB5b3UgY2FuIHVzZSBgYW50aV9qb2luKClgIGZyb20gKipkcGx5cioqIGlmIHRoZSBzdG9wIHdvcmRzIGFyZSBpbiBhIGB0aWJibGUoKWAuDQoNCkxpa2UgaW4gb3VyIHByZXZpb3VzIGNoYXB0ZXIsIGxldCdzIGV4YW1pbmUgdGhlIHRleHQgb2YgIlRoZSBGaXItVHJlZSIgYnkgSGFucyBDaHJpc3RpYW4gQW5kZXJzZW4sIGFuZCB1c2UgKip0aWR5dGV4dCoqIHRvIHRva2VuaXplIHRoZSB0ZXh0IGludG8gd29yZHMuDQoNCmBgYHtyfQ0KbGlicmFyeShoY2FuZGVyc2VucikNCmxpYnJhcnkodGlkeXRleHQpDQpsaWJyYXJ5KHRpZHl2ZXJzZSkNCg0KIyBUaWJibGUgb2YgdGhlIGZpciB0cmVlIGJvb2sNCmZpcl90cmVlIDwtIGhjYV9mYWlyeXRhbGVzKCkgJT4lIA0KICBmaWx0ZXIoYm9vayA9PSAiVGhlIGZpciB0cmVlIiwgbGFuZ3VhZ2UgPT0gIkVuZ2xpc2giKQ0KDQojIFRva2VuaXplIGludG8gd29yZHMNCnRpZHlfZmlyX3RyZWUgPC0gZmlyX3RyZWUgJT4lIA0KICB1bm5lc3RfdG9rZW5zKGlucHV0ID0gdGV4dCwgb3V0cHV0ID0gd29yZCwgdG9rZW4gPSAid29yZHMiKQ0KDQoNCmBgYA0KDQpMZXQncyB1c2UgdGhlIFNub3diYWxsIHN0b3Agd29yZCBsaXN0IGFzIGFuIGV4YW1wbGUuIFNpbmNlIHRoZSBzdG9wIHdvcmRzIHJldHVybiBmcm9tIHRoaXMgZnVuY3Rpb24gYXMgYSB2ZWN0b3IsIHdlIHdpbGwgdXNlIGBmaWx0ZXIoKWAuDQoNCmBgYHtyfQ0KIyBSZW1vdmUgc3RvcCB3b3JkcyB1c2luZyBmaWx0ZXINCnRpZHlfZmlyX3RyZWUgJT4lIA0KICBmaWx0ZXIoISh3b3JkICVpbiUgc3RvcHdvcmRzKHNvdXJjZSA9ICJzbm93YmFsbCIpKSkgJT4lIA0KICBzbGljZV9oZWFkKG4gPSAxMCkNCmBgYA0KDQpJZiB3ZSB1c2UgdGhlIGBnZXRfc3RvcHdvcmRzKClgIGZ1bmN0aW9uIGZyb20gKip0aWR5dGV4dCoqIGluc3RlYWQsIHRoZW4gd2UgY2FuIHVzZSB0aGUgYGFudGlfam9pbigpYCBmdW5jdGlvbi4NCg0KPiAqKmFudGlfam9pbigpIHJldHVybiBhbGwgcm93cyBmcm9tIHggd2l0aG91dCBhIG1hdGNoIGluIHkuKioNCj4NCj4gXCMgIkZpbHRlcmluZyIgam9pbnMga2VlcCBjYXNlcyBmcm9tIHRoZSBMSFMNCg0KYGBge3J9DQojIFJlbW92ZSBzdG9wIHdvcmRzIHVzaW5nIGFudGlfam9pbiBzaW5jZSB0aWR5dGV4dCByZXR1cm5zIGEgdGliYmxlDQp0aWR5X2Zpcl90cmVlICU+JSANCiAgYW50aV9qb2luKGdldF9zdG9wd29yZHMoc291cmNlID0gInNub3diYWxsIikpICU+JSANCiAgc2xpY2VfaGVhZChuID0gMTApDQpgYGANCg0KIyMgKiozLjIgQ3JlYXRpbmcgeW91ciBvd24gc3RvcCB3b3JkcyBsaXN0KioNCg0KQW5vdGhlciB3YXkgdG8gZ2V0IGEgc3RvcCB3b3JkIGxpc3QgaXMgdG8gY3JlYXRlIG9uZSB5b3Vyc2VsZi4gTGV0J3MgZXhwbG9yZSBhIGZldyBkaWZmZXJlbnQgd2F5cyB0byBmaW5kIGFwcHJvcHJpYXRlIHdvcmRzIHRvIHVzZS4gV2Ugd2lsbCB1c2UgdGhlIHRva2VuaXplZCBkYXRhIGZyb20gIlRoZSBGaXItVHJlZSIgYXMgYSBmaXJzdCBleGFtcGxlLiBMZXQncyB0YWtlIHRoZSB3b3JkcyBhbmQgcmFuayB0aGVtIGJ5IHRoZWlyIGNvdW50IG9yIGZyZXF1ZW5jeS4NCg0KYGBge3J9DQojIE1vc3QgZnJlcXVlbnQgd29yZHMgaW4gdGhlIGZpciB0cmVlDQp0aWR5X2Zpcl90cmVlICU+JSANCiAgY291bnQod29yZCwgc29ydCA9IFRSVUUpICU+JSANCiAgc2xpY2VfaGVhZChuID0gMjMpDQpgYGANCg0KV2UgcmVjb2duaXplIG1hbnkgb2Ygd2hhdCB3ZSB3b3VsZCBjb25zaWRlciBzdG9wIHdvcmRzIGluIHRoZSBmaXJzdCBjb2x1bW4gaGVyZSwgd2l0aCB0aHJlZSBiaWcgZXhjZXB0aW9ucy4gV2Ugc2VlIGAidHJlZSJgIGF0IDMsIGAiZmlyImAgYXQgMTIsIGFuZCBgImxpdHRsZSJgIGF0IDIyLiBUaGVzZSB3b3JkcyBhcHBlYXIgaGlnaCBvbiBvdXIgbGlzdCwgYnV0IHRoZXkgZG8gcHJvdmlkZSB2YWx1YWJsZSBpbmZvcm1hdGlvbiBhcyB0aGV5IGFsbCByZWZlcmVuY2UgdGhlIG1haW4gY2hhcmFjdGVyLiBXaGF0IHdlbnQgd3Jvbmcgd2l0aCB0aGlzIGFwcHJvYWNoPw0KDQo+IC0gICAqKkNyZWF0aW5nIGEgc3RvcCB3b3JkIGxpc3QgdXNpbmcgaGlnaC1mcmVxdWVuY3kgd29yZHMgd29ya3MgYmVzdCB3aGVuIGl0IGlzIGNyZWF0ZWQgb24gYSBjb3JwdXMgb2YgZG9jdW1lbnRzLCBub3QgYW4gaW5kaXZpZHVhbCBkb2N1bWVudC4gVGhpcyBpcyBiZWNhdXNlIHRoZSB3b3JkcyBmb3VuZCBpbiBhIHNpbmdsZSBkb2N1bWVudCB3aWxsIGJlIGRvY3VtZW50LXNwZWNpZmljIGFuZCB0aGUgb3ZlcmFsbCBwYXR0ZXJuIG9mIHdvcmRzIHdpbGwgbm90IGdlbmVyYWxpemUgdGhhdCB3ZWxsLioqDQo+DQo+IC0gICBUaGUgd29yZCBgInRyZWUiYCBkb2VzIHNlZW0gaW1wb3J0YW50IGFzIGl0IGlzIGFib3V0IHRoZSBtYWluIGNoYXJhY3RlciwgYnV0IGl0IGNvdWxkIGFsc28gYmUgYXBwZWFyaW5nIHNvIG9mdGVuIHRoYXQgaXQgc3RvcHMgcHJvdmlkaW5nIGFueSBpbmZvcm1hdGlvbi4NCg0KTGV0J3MgdHJ5IGEgZGlmZmVyZW50IGFwcHJvYWNoLCBleHRyYWN0aW5nIGhpZ2gtZnJlcXVlbmN5IHdvcmRzIGZyb20gdGhlICoqY29ycHVzIG9mICphbGwqIEVuZ2xpc2ggZmFpcnkgdGFsZXMgYnkgSC5DLiBBbmRlcnNlbi4qKg0KDQpgYGB7cn0NCmhjYV9mYWlyeXRhbGVzKCkgJT4lIA0KICBmaWx0ZXIobGFuZ3VhZ2UgPT0gIkVuZ2xpc2giKSAlPiUgDQogIHVubmVzdF90b2tlbnMob3V0cHV0ID0gd29yZCwgaW5wdXQgPSB0ZXh0KSAlPiUgDQogIGNvdW50KHdvcmQsIHNvcnQgPSBUUlVFKSAlPiUgDQogIHNsaWNlX2hlYWQobiA9IDI1KQ0KYGBgDQoNClRoaXMgbGlzdCBpcyBtb3JlIGFwcHJvcHJpYXRlIGZvciBvdXIgY29uY2VwdCBvZiBzdG9wIHdvcmRzLCBhbmQgbm93IGl0IGlzIHRpbWUgZm9yIHVzIHRvIG1ha2Ugc29tZSBjaG9pY2VzLg0KDQpXaGljaCB3b3JkcyBzaG91bGQgd2UgYWRkIGFuZC9vciByZW1vdmUgYmFzZWQgb24gcHJpb3IgaW5mb3JtYXRpb24/IFNlbGVjdGluZyB0aGUgbnVtYmVyIG9mIHdvcmRzIHRvIHJlbW92ZSBpcyBiZXN0IGRvbmUgYnkgYSBjYXNlLWJ5LWNhc2UgYmFzaXMgYXMgaXQgY2FuIGJlIGRpZmZpY3VsdCB0byBkZXRlcm1pbmUgYSBwcmlvcmkgaG93IG1hbnkgZGlmZmVyZW50ICJtZWFuaW5nbGVzcyIgd29yZHMgYXBwZWFyIGluIGEgY29ycHVzLiBPdXIgc3VnZ2VzdGlvbiBpcyB0byBzdGFydCB3aXRoIGEgbG93IG51bWJlciBsaWtlIDIwIGFuZCBpbmNyZWFzZSBieSAxMCB3b3JkcyB1bnRpbCB5b3UgZ2V0IHRvIHdvcmRzIHRoYXQgYXJlIG5vdCBhcHByb3ByaWF0ZSBhcyBzdG9wIHdvcmRzIGZvciB5b3VyIGFuYWx5dGljYWwgcHVycG9zZS4NCg0KSXQgaXMgd29ydGgga2VlcGluZyBpbiBtaW5kIHRoYXQgc3VjaCBhIGxpc3QgaXMgbm90IHBlcmZlY3QuIERlcGVuZGluZyBvbiBob3cgeW91ciB0ZXh0IHdhcyBnZW5lcmF0ZWQgb3IgcHJvY2Vzc2VkLCBzdHJhbmdlIHRva2VucyBjYW4gc3VyZmFjZSBhcyBwb3NzaWJsZSBzdG9wIHdvcmRzIGR1ZSB0byBlbmNvZGluZyBvciBvcHRpY2FsIGNoYXJhY3RlciByZWNvZ25pdGlvbiBlcnJvcnMuIEZ1cnRoZXIsIHRoZXNlIHJlc3VsdHMgYXJlIGJhc2VkIG9uIHRoZSBjb3JwdXMgb2YgZG9jdW1lbnRzIHdlIGhhdmUgYXZhaWxhYmxlLCB3aGljaCBpcyBwb3RlbnRpYWxseSBiaWFzZWQuIEluIG91ciBleGFtcGxlIGhlcmUsIGFsbCB0aGUgZmFpcnkgdGFsZXMgd2VyZSB3cml0dGVuIGJ5IHRoZSBzYW1lIEV1cm9wZWFuIHdoaXRlIG1hbiBmcm9tIHRoZSBlYXJseSAxODAwcy4NCg0KKipUcnkgYW4gWyppbnZlcnNlIGRvY3VtZW50IGZyZXF1ZW5jeSpdKGh0dHBzOi8vd3d3LnRpZHl0ZXh0bWluaW5nLmNvbS90ZmlkZi5odG1sKSAoSURGKSBvZiBlYWNoIHdvcmQuKiogVGhlIElERiBvZiBhIHdvcmQgaXMgYSBxdWFudGl0eSB0aGF0IGlzIGxvdyBmb3IgY29tbW9ubHktdXNlZCB3b3JkcyBpbiBhIGNvbGxlY3Rpb24gb2YgZG9jdW1lbnRzIGFuZCBoaWdoIGZvciB3b3JkcyBub3QgdXNlZCBvZnRlbiBpbiBhIGNvbGxlY3Rpb24gb2YgZG9jdW1lbnRzLiBJdCBpcyB0eXBpY2FsbHkgZGVmaW5lZCBhcw0KDQokJA0KaWRmKHRlcm0pPSBsbihcZnJhY3tuX3tkb2N1bWVudHN9fXtuX3tkb2N1bWVudHMgY29udGFpbmluZyB0ZXJtfX0pDQokJA0KDQpJZiB0aGUgd29yZCAiZG9nIiBhcHBlYXJzIGluIDQgb3V0IG9mIDEwMCBkb2N1bWVudHMgdGhlbiBpdCB3b3VsZCBoYXZlIGFuIGBpZGYoImRvZyIpID0gbG9nKDEwMC80KSA9IDMuMjJgLCBhbmQgaWYgdGhlIHdvcmQgImNhdCIgYXBwZWFycyBpbiA5OSBvdXQgb2YgMTAwIGRvY3VtZW50cyB0aGVuIGl0IHdvdWxkIGhhdmUgYW4gYGlkZigiY2F0IikgPSBsb2coMTAwLzk5KSA9IDAuMDFgLiBOb3RpY2UgaG93IHRoZSBpZGYgdmFsdWVzIGdvZXMgdG8gemVybyAoYXMgYSBtYXR0ZXIgb2YgZmFjdCB3aGVuIGEgdGVybSBhcHBlYXJzIGluIGFsbCB0aGUgZG9jdW1lbnRzIHRoZW4gdGhlIGlkZiBvZiB0aGF0IHdvcmQgaXMgMCBgbG9nKDEwMC8xMDApID0gbG9nKDEpID0gMGApLCB0aGUgbW9yZSBkb2N1bWVudHMgaXQgaXMgY29udGFpbmVkIGluLiBXaGF0IGhhcHBlbnMgaWYgd2UgY3JlYXRlIGEgc3RvcCB3b3JkIGxpc3QgYmFzZWQgb24gd29yZHMgd2l0aCB0aGUgbG93ZXN0IElERj8gVGhlIGZvbGxvd2luZyBmdW5jdGlvbiB0YWtlcyBhIHRva2VuaXplZCBkYXRhZnJhbWUgYW5kIHJldHVybnMgYSBkYXRhZnJhbWUgd2l0aCBhIGNvbHVtbiBmb3IgZWFjaCB3b3JkIGFuZCBhIGNvbHVtbiBmb3IgdGhlIElERi4NCg0KYGBge3J9DQojbGlicmFyeShybGFuZykNCmRmIDwtIGhjYV9mYWlyeXRhbGVzKCkgJT4lIA0KICBmaWx0ZXIobGFuZ3VhZ2UgPT0gIkVuZ2xpc2giKSAlPiUgDQogIHVubmVzdF90b2tlbnMob3V0cHV0ID0gd29yZCwgaW5wdXQgPSB0ZXh0KSANCg0KDQoNCiMgVW5pcXVlIHdvcmRzIGluIHRoZSB3aG9sZSBjb3JwdXMNCndvcmRzIDwtIGRmICU+JQ0KICBwdWxsKHdvcmQpICU+JSANCiAgdW5pcXVlKCkNCg0KIyBOdW1iZXIgb2YgYm9va3MgaW4gdGhlIGNvcnB1cw0Kbl9kb2NzIDwtIGRmICU+JSANCiAgcHVsbChib29rKSAlPiUgDQogIHVuaXF1ZSgpICU+JSANCiAgbGVuZ3RoKCkNCg0KIyBVbmlxdWUgd29yZHMgaW4gdGhlIGNvcnB1cyBmb3VuZCBpbiBlYWNoIGJvb2sNCm5fd29yZHMgPC0gKGRmICU+JSANCiAgbmVzdChkYXRhID0gYyh3b3JkKSkgJT4lIA0KICAgIHB1bGwoZGF0YSkgJT4lIA0KICAgIG1hcF9kZmMofiB3b3JkcyAlaW4lIHVuaXF1ZShwdWxsKC54LCB3b3JkKSkpICU+JSANCiAgICByb3dTdW1zKCkpDQoNCnRpYmJsZSh3b3JkID0gd29yZHMsDQogICAgICAgICBpZGYgPSBsb2cobl9kb2NzIC8gbl93b3JkcykpICU+JSANCiAgYXJyYW5nZSgoaWRmKSkgJT4lIA0KICBzbGljZV9oZWFkKG4gPSAyNSkgDQoNCmBgYA0KDQpUaGlzIGNhbiBiZSBwdXQgaW4gYSBmdW5jdGlvbnMgYXM6DQoNCmBgYHtyfQ0KY2FsY19pZGYgPC0gZnVuY3Rpb24oZGYsIHdvcmQsIGRvY3VtZW50KSB7DQogIHdvcmRzIDwtIGRmICU+JSBwdWxsKHt7d29yZH19KSAlPiUgdW5pcXVlKCkNCiAgbl9kb2NzIDwtIGxlbmd0aCh1bmlxdWUocHVsbChkZiwge3tkb2N1bWVudH19KSkpDQogIG5fd29yZHMgPC0gZGYgJT4lDQogICAgbmVzdChkYXRhID0gYyh7e3dvcmR9fSkpICU+JQ0KICAgIHB1bGwoZGF0YSkgJT4lDQogICAgbWFwX2RmYyh+IHdvcmRzICVpbiUgdW5pcXVlKHB1bGwoLngsIHt7d29yZH19KSkpICU+JQ0KICAgIHJvd1N1bXMoKQ0KICANCiAgdGliYmxlKHdvcmQgPSB3b3JkcywNCiAgICAgICAgIGlkZiA9IGxvZyhuX2RvY3MgLyBuX3dvcmRzKSkNCn0NCmBgYA0KDQo+IGB7eyB9fWAgYWxsb3dzIHlvdSB0byB1c2UgdGlkeXZlcnNlIGZ1bmN0aW9ucyBpbiB1c2VyIGRlZmluZWQgZnVuY3Rpb24gdG8gYWNjZXNzIGRmIHZhcmlhYmxlcz8gLWlzaC4uDQo+DQo+IFNlZTogPGh0dHBzOi8vd3d3LnRpZHl2ZXJzZS5vcmcvYmxvZy8yMDE5LzA2L3JsYW5nLTAtNC0wLyNhLXNpbXBsZXItaW50ZXJwb2xhdGlvbi1wYXR0ZXJuLXdpdGgtPg0KDQpUaGlzIHRpbWUgd2UgZ2V0IGJldHRlciByZXN1bHRzLiBUaGUgbGlzdCBzdGFydHMgd2l0aCAiYSwiICJ0aGUsIiAiYW5kLCIgYW5kICJ0byIgYW5kIGNvbnRpbnVlcyB3aXRoIG1hbnkgbW9yZSByZWFzb25hYmxlIGNob2ljZXMgb2Ygc3RvcCB3b3Jkcy4gV2UgbmVlZCB0byBsb29rIGF0IHRoZXNlIHJlc3VsdHMgbWFudWFsbHkgdG8gdHVybiB0aGlzIGludG8gYSBsaXN0LiBXZSBuZWVkIHRvIGdvIGFzIGZhciBkb3duIGluIHJhbmsgYXMgd2UgYXJlIGNvbWZvcnRhYmxlIHdpdGguIFlvdSBhcyBhIGRhdGEgcHJhY3RpdGlvbmVyIGFyZSBpbiBmdWxsIGNvbnRyb2wgb2YgaG93IHlvdSB3YW50IHRvIGNyZWF0ZSB0aGUgbGlzdC4gSWYgeW91IGRvbid0IHdhbnQgdG8gaW5jbHVkZSAibGl0dGxlIiB5b3UgYXJlIHN0aWxsIGFibGUgdG8gYWRkICJhcmUiIHRvIHlvdXIgbGlzdCBldmVuIHRob3VnaCBpdCBpcyBsb3dlciBvbiB0aGUgbGlzdC4NCg0KIyMgKiozLjMgQWxsIHN0b3Agd29yZCBsaXN0cyBhcmUgY29udGV4dC1zcGVjaWZpYyoqDQoNCioqQ29udGV4dCBpcyBpbXBvcnRhbnQgaW4gdGV4dCBtb2RlbGluZyoqLCBzbyBpdCBpcyBpbXBvcnRhbnQgdG8gZW5zdXJlIHRoYXQgdGhlIHN0b3Agd29yZCBsZXhpY29uIHlvdSB1c2UgcmVmbGVjdHMgdGhlIHdvcmQgc3BhY2UgdGhhdCB5b3UgYXJlIHBsYW5uaW5nIG9uIHVzaW5nIGl0IGluLiBPbmUgY29tbW9uIGNvbmNlcm4gdG8gY29uc2lkZXIgaXMgaG93IHByb25vdW5zIGJyaW5nIGluZm9ybWF0aW9uIHRvIHlvdXIgdGV4dC4gUHJvbm91bnMgYXJlIGluY2x1ZGVkIGluIG1hbnkgZGlmZmVyZW50IHN0b3Agd29yZCBsaXN0cyAoYWx0aG91Z2ggaW5jb25zaXN0ZW50bHkpLCBidXQgdGhleSB3aWxsIG9mdGVuICpub3QqIGJlIG5vaXNlIGluIHRleHQgZGF0YQ0KDQpPbiB0aGUgb3RoZXIgaGFuZCwgc29tZXRpbWVzIHlvdSB3aWxsIGhhdmUgdG8gYWRkIGluIHdvcmRzIHlvdXJzZWxmLCBkZXBlbmRpbmcgb24gdGhlIGRvbWFpbi4gSWYgeW91IGFyZSB3b3JraW5nIHdpdGggdGV4dHMgZm9yIGRlc3NlcnQgcmVjaXBlcywgY2VydGFpbiBpbmdyZWRpZW50cyAoc3VnYXIsIGVnZ3MsIHdhdGVyKSBhbmQgYWN0aW9ucyAod2hpc2tpbmcsIGJha2luZywgc3RpcnJpbmcpIG1heSBiZSBmcmVxdWVudCBlbm91Z2ggdG8gcGFzcyB5b3VyIHN0b3Agd29yZCB0aHJlc2hvbGQsIGJ1dCB5b3UgbWF5IHdhbnQgdG8ga2VlcCB0aGVtIGFzIHRoZXkgbWF5IGJlIGluZm9ybWF0aXZlLiBUaHJvd2luZyBhd2F5ICJlZ2dzIiBhcyBhIGNvbW1vbiB3b3JkIHdvdWxkIG1ha2UgaXQgaGFyZGVyIG9yIGRvd25yaWdodCBpbXBvc3NpYmxlIHRvIGRldGVybWluZSBpZiBjZXJ0YWluIHJlY2lwZXMgYXJlIHZlZ2FuIG9yIG5vdCB3aGlsZSB3aGlza2luZyBhbmQgc3RpcnJpbmcgbWF5IGJlIGZpbmUgdG8gcmVtb3ZlIGFzIGRpc3Rpbmd1aXNoaW5nIGJldHdlZW4gcmVjaXBlcyB0aGF0IGRvIGFuZCBkb24ndCByZXF1aXJlIGEgd2hpc2sgbWlnaHQgbm90IGJlIHRoYXQgYmlnIG9mIGEgZGVhbC4NCg0KIyMgDQoNCioqMy40IFdoYXQgaGFwcGVucyB3aGVuIHlvdSByZW1vdmUgc3RvcCB3b3JkcyoqDQoNCi0gICBsYXJnZXIgc3RvcCB3b3JkIGxpc3RzIHJlbW92ZSBtb3JlIHdvcmRzIHRoYW4gc2hvcnRlciBzdG9wIHdvcmQgbGlzdHMuIEluIHRoaXMgZXhhbXBsZSB3aXRoIGZhaXJ5IHRhbGVzLCBvdmVyIGhhbGYgb2YgdGhlIHdvcmRzIGhhdmUgYmVlbiByZW1vdmVkLCB3aXRoIHRoZSBsYXJnZXN0IGxpc3QgcmVtb3Zpbmcgb3ZlciA4MCUgb2YgdGhlIHdvcmRzLg0KDQotICAgSGFuZGxpbmcgbWlzc3BlbGxpbmdzIHdoZW4gdXNpbmcgcHJlbWFkZSBsaXN0cyBjYW4gYmUgZG9uZSBieSBtYW51YWxseSBhZGRpbmcgY29tbW9uIG1pc3NwZWxsaW5ncy4gWW91IGNvdWxkIGltYWdpbmUgY3JlYXRpbmcgYWxsIHdvcmRzIHRoYXQgYXJlIGEgY2VydGFpbiBzdHJpbmcgZGlzdGFuY2UgYXdheSBmcm9tIHRoZSBzdG9wIHdvcmRzLCBidXQgd2UgZG8gbm90IHJlY29tbWVuZCB0aGlzIGFzIHlvdSB3b3VsZCBxdWlja2x5IGluY2x1ZGUgaW5mb3JtYXRpdmUgd29yZHMgdGhpcyB3YXkuDQoNCi0gICBPbmUgb2YgdGhlIGRvd25zaWRlcyBvZiBjcmVhdGluZyB5b3VyIG93biBzdG9wIHdvcmQgbGlzdHMgdXNpbmcgZnJlcXVlbmNpZXMgaXMgdGhhdCB5b3UgYXJlIGxpbWl0ZWQgdG8gdXNpbmcgd29yZHMgdGhhdCB5b3UgaGF2ZSBhbHJlYWR5IG9ic2VydmVkLiBJdCBjb3VsZCBoYXBwZW4gdGhhdCAic2hlJ2QiIGlzIGluY2x1ZGVkIGluIHlvdXIgdHJhaW5pbmcgY29ycHVzIGJ1dCB0aGUgd29yZCAiaGUnZCIgZGlkIG5vdCByZWFjaCB0aGUgdGhyZXNob2xkLiBUaGlzIGlzIGEgY2FzZSB3aGVyZSB5b3UgbmVlZCB0byBsb29rIGF0IHlvdXIgd29yZHMgYW5kIGFkanVzdCBhY2NvcmRpbmdseS4gSGVyZSB0aGUgbGFyZ2UgcHJlbWFkZSBzdG9wIHdvcmQgbGlzdHMgY2FuIHNlcnZlIGFzIGluc3BpcmF0aW9uIGZvciBtaXNzaW5nIHdvcmRzLg0KDQotICAgR2l2ZW4gdGhlIHJpZ2h0IGxpc3Qgb2Ygd29yZHMsIHdlIHNlZSBubyBoYXJtIHRvIHRoZSBtb2RlbCBwZXJmb3JtYW5jZSwgYW5kIHNvbWV0aW1lcyBmaW5kIGltcHJvdmVtZW50IGR1ZSB0byBub2lzZSByZWR1Y3Rpb24gKFtGZWxkbWFuLCBhbmQgU2FuZ2VyIDIwMDddKGh0dHBzOi8vc21sdGFyLmNvbS9zdG9wd29yZHMuaHRtbCNyZWYtRmVsZG1hbjIwMDcpKS4NCg0KIyMgKiozLjYgU3VtbWFyeSoqDQoNCkluIG1hbnkgc3RhbmRhcmQgTkxQIHdvcmtmbG93cywgdGhlIHJlbW92YWwgb2Ygc3RvcCB3b3JkcyBpcyBwcmVzZW50ZWQgYXMgYSBkZWZhdWx0IG9yIHRoZSBjb3JyZWN0IGNob2ljZSB3aXRob3V0IGNvbW1lbnQuIEFsdGhvdWdoIHJlbW92aW5nIHN0b3Agd29yZHMgY2FuIGltcHJvdmUgdGhlIGFjY3VyYWN5IG9mIHlvdXIgbWFjaGluZSBsZWFybmluZyB1c2luZyB0ZXh0IGRhdGEsIGNob2ljZXMgYXJvdW5kIHN1Y2ggYSBzdGVwIGFyZSBjb21wbGV4LiBUaGUgY29udGVudCBvZiBleGlzdGluZyBzdG9wIHdvcmQgbGlzdHMgdmFyaWVzIHRyZW1lbmRvdXNseSwgYW5kIHRoZSBhdmFpbGFibGUgc3RyYXRlZ2llcyBmb3IgYnVpbGRpbmcgeW91ciBvd24gY2FuIGhhdmUgc3VidGxlIHRvIG5vdC1zby1zdWJ0bGUgZWZmZWN0cyBvbiB5b3VyIG1vZGVsIHJlc3VsdHMuDQoNCmBgYHtyIGV2YWw9RkFMU0UsIGluY2x1ZGU9RkFMU0V9DQojIHBhbGV0dGVlcjo6cGFsZXR0ZWVyX2QoImdnc2NpOjpjYXRlZ29yeTEwX2QzIikNCmBgYA0K