Kodowanie metodą gorącej jedynki jest najpopularniejszym podstawowym sposobem zamieniania tokena w wektor. Z metody tej korzystaliśmy w początkowych przykładach przetwarzania zbiorów IMDB i Agencji Reutera przedstawionych w rozdziale 3. (używaliśmy jej do kodowania słów). Polega ona na przypisaniu do każdego słowa unikatowego indeksu będącego wartością całkowitoliczbową i umieszczoną w wektorze binarnym o długości n (rozmiar słownika). Wektor przyjmuje same wartości zerowe poza i-tym elementem, który przyjmuje wartość 1.
Oczywiście metoda ta może być również użyta na poziomie znaków. W celu wyjaśnienia praktycznej implementacji metody kodowania z gorącą jedynką chciałbym zaprezentować dwa przykłady: pierwszy z nich przedstawia kodowanie słów, a drugi kodowanie znaków:
Prosty przykład kodowania słów metodą gorącej jedynki:
r
r # This is our initial data; one entry per
# (in this toy example, a is just a sentence, but # it could be an entire document). samples <- c(cat sat on the mat., dog ate my homework.)
First, build an index of all tokens in the data.
token_index <- list() for (sample in samples) # Tokenizes the samples via the strsplit function. In real life, you’d also # strip punctuation and special characters from the samples. for (word in strsplit(sample, )[[1]]) if (!word %in% names(token_index)) # Assigns a unique index to each unique word. Note that you don’t # attribute index 1 to anything. token_index[[word]] <- length(token_index) + 2 # Vectorizes the samples. You’ll only consider the first max_length # words in each sample. max_length <- 10 # This is where you store the results. results <- array(0, dim = c(length(samples), max_length, max(as.integer(token_index)))) for (i in 1:length(samples)) { sample <- samples[[i]] words <- head(strsplit(sample, )[[1]], n = max_length) for (j in 1:length(words)) { index <- token_index[[words[[j]]]] results[[i, j, index]] <- 1 } }
Prosty przykład kodowania znaków metodą gorącej jedynki:
r
r samples <- c(cat sat on the mat., dog ate my homework.) ascii_tokens <- c(\, sapply(as.raw(c(32:126)), rawToChar)) token_index <- c(1:(length(ascii_tokens))) names(token_index) <- ascii_tokens max_length <- 50 results <- array(0, dim = c(length(samples), max_length, length(token_index))) for (i in 1:length(samples)) { sample <- samples[[i]] characters <- strsplit(sample, \)[[1]] for (j in 1:length(characters)) { character <- characters[[j]] results[i, j, token_index[[character]]] <- 1 } }
Pakiet Keras jest wyposażony w narzędzia przeznaczone do kodowania znaków i słów metodą gorącej jedynki (narzędzia te potrafią przetwarzać surowy tekst). W praktyce warto z nich korzystać, ponieważ wykonują wiele ważnych operacji, takich jak usuwanie znaków specjalnych i branie pod uwagę tylko n słów najczęściej występujących w zbiorze (zwykle stosuje się takie ograniczenie w celu uniknięcia pracy z bardzo dużymi przestrzeniami wektora wejściowego).
Przykład kodowania słów metodą gorącej jedynki przy użyciu gotowych narzędzi pakietu Keras:
r
r library(keras) samples <- c(cat sat on the mat., dog ate my homework.) # Creates a tokenizer, configured to only take into account the 1,000 # most common words, then builds the word index. tokenizer <- text_tokenizer(num_words = 1000) %>% fit_text_tokenizer(samples) # Turns strings into lists of integer indices sequences <- texts_to_sequences(tokenizer, samples) # You could also directly get the one-hot binary representations. Vectorization # modes other than one-hot encoding are supported by this tokenizer. one_hot_results <- texts_to_matrix(tokenizer, samples, mode = ) # How you can recover the word index that was computed word_index <- tokenizer$word_index cat(, length(word_index), tokens.)
Found 9 unique tokens.
Odmianą kodowania metodą gorącej jedynki, która może zostać użyta, gdy liczba unikatowych tokenów w słowniku jest zbyt duża, aby obsłużyć ją w sposób jawny, jest sztuczka haszowania z gorącą jedynką (ang. one-hot hashing trick). Zamiast jawnie przypisywać indeks do każdego ze słów i utrzymywać odwołania do tych indeksów w słowniku, można haszować słowa do formy wektorów o określonym rozmiarze. Zwykle robi się to za pomocą bardzo lekkiej funkcji haszującej. Główną zaletą tej metody jest brak konieczności utrzymywania jawnego indeksu słów, co pozwala oszczędzić przestrzeń pamięci i zakodować dane w locie (możliwe jest natychmiastowe wygenerowanie wektorów tokena, bez potrzeby przyglądania się całości dostępnych danych). Wadą tego rozwiązania jest możliwość wystąpienia konfliktów haszy (ang. hash collisions), polegających na przepisaniu tego samego hasza dwóm różnym słowom (w takim przypadku żaden model uczenia maszynowego analizujący uzyskane hasze nie będzie mógł odróżnić od siebie tych słów). Prawdopodobieństwo wystąpienia konfliktów haszy maleje, gdy przestrzeń haszowania jest o wiele większa od całkowitej liczby unikatowych haszowanych tokenów.
Prosty przykład sztuczki haszowania słów metodą gorącej jedynki:
r
r library(hashFunction) samples <- c(cat sat on the mat., dog ate my homework.) # We will store our words as vectors of size 1000. # Note that if you have close to 1000 words (or more) # you will start seeing many hash collisions, which # will decrease the accuracy of this encoding method. dimensionality <- 1000 max_length <- 10 results <- array(0, dim = c(length(samples), max_length, dimensionality)) for (i in 1:length(samples)) { sample <- samples[[i]] words <- head(strsplit(sample, )[[1]], n = max_length) for (j in 1:length(words)) { # Hash the word into a integer index # that is between 0 and 1,000 index <- abs(spooky.32(words[[i]])) %% dimensionality results[[i, j, index]] <- 1 } }
LS0tDQp0aXRsZTogIktvZG93YW5pZSBzxYLDs3cgaSB6bmFrw7N3IG1ldG9kxIUgZ29yxIVjZWogamVkeW5raSINCm91dHB1dDogDQogIGh0bWxfbm90ZWJvb2s6IA0KICAgIHRoZW1lOiBjZXJ1bGVhbg0KICAgIGhpZ2hsaWdodDogdGV4dG1hdGUNCi0tLQ0KDQpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0NCmtuaXRyOjpvcHRzX2NodW5rJHNldCh3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRSkNCmBgYA0KDQoNCg0KS29kb3dhbmllIG1ldG9kxIUgZ29yxIVjZWogamVkeW5raSBqZXN0IG5hanBvcHVsYXJuaWVqc3p5bSBwb2RzdGF3b3d5bSBzcG9zb2JlbSB6YW1pZW5pYW5pYSB0b2tlbmEgdyB3ZWt0b3IuIFogbWV0b2R5IHRlaiBrb3J6eXN0YWxpxZtteSB3IHBvY3rEhXRrb3d5Y2ggcHJ6eWvFgmFkYWNoIHByemV0d2FyemFuaWEgemJpb3LDs3cgSU1EQiBpIEFnZW5jamkgUmV1dGVyYSBwcnplZHN0YXdpb255Y2ggdyByb3pkemlhbGUgMy4gKHXFvHl3YWxpxZtteSBqZWogZG8ga29kb3dhbmlhIHPFgsOzdykuIFBvbGVnYSBvbmEgbmEgcHJ6eXBpc2FuaXUgZG8ga2HFvGRlZ28gc8WCb3dhIHVuaWthdG93ZWdvIGluZGVrc3UgYsSZZMSFY2VnbyB3YXJ0b8WbY2nEhSBjYcWCa293aXRvbGljemJvd8SFIGkgdW1pZXN6Y3pvbsSFIHcgd2VrdG9yemUgYmluYXJueW0gbyBkxYJ1Z2/Fm2NpIG4gKHJvem1pYXIgc8WCb3duaWthKS4gV2VrdG9yIHByenlqbXVqZSBzYW1lIHdhcnRvxZtjaSB6ZXJvd2UgcG96YSBpLXR5bSBlbGVtZW50ZW0sIGt0w7NyeSBwcnp5am11amUgd2FydG/Fm8SHIDEuDQoNCk9jenl3acWbY2llIG1ldG9kYSB0YSBtb8W8ZSBiecSHIHLDs3duaWXFvCB1xbx5dGEgbmEgcG96aW9taWUgem5ha8Ozdy4gVyBjZWx1IHd5amHFm25pZW5pYSBwcmFrdHljem5laiBpbXBsZW1lbnRhY2ppIG1ldG9keSBrb2Rvd2FuaWEgeiBnb3LEhWPEhSBqZWR5bmvEhSBjaGNpYcWCYnltIHphcHJlemVudG93YcSHIGR3YSBwcnp5a8WCYWR5OiBwaWVyd3N6eSB6IG5pY2ggcHJ6ZWRzdGF3aWEga29kb3dhbmllIHPFgsOzdywgYSBkcnVnaSBrb2Rvd2FuaWUgem5ha8OzdzoNCg0KUHJvc3R5IHByenlrxYJhZCBrb2Rvd2FuaWEgc8WCw7N3IG1ldG9kxIUgZ29yxIVjZWogamVkeW5raToNCg0KYGBge3J9DQojIFBvY3rEhXRrb3dhIGZvcm1hIGRhbnljaDogamVkZW4gZWxlbWVudCBuYSBwcsOzYmvEmSAodyB0eW0gcHJ6eWvFgmFkemllIHByw7Nia8SFIGplc3QgemRhbmllLCANCiMgYWxlIG1vxbxlIG9uYSBiecSHIHLDs3duaWXFvCBjYcWCeW0gZG9rdW1lbnRlbSkuDQpzYW1wbGVzIDwtIGMoIlRoZSBjYXQgc2F0IG9uIHRoZSBtYXQuIiwgIlRoZSBkb2cgYXRlIG15IGhvbWV3b3JrLiIpDQogIA0KIyBaYnVkdWogaW5kZWtzIHdzenlzdGtpY2ggdG9rZW7Ds3cgZGFueWNoLg0KdG9rZW5faW5kZXggPC0gbGlzdCgpDQpmb3IgKHNhbXBsZSBpbiBzYW1wbGVzKQ0KICAjIFRva2VuaXphY2phIHByw7NiZWsgcG9wcnpleiBtZXRvZMSZIHBvZHppYcWCdS4gDQogICMgUG9kY3phcyBwcmFjeSB6IHByYXdkeml3eW1pIGRhbnltaSBwb2R6aWHFgnUgZG9rb251amUgc2nEmSByw7N3bmllxbwgbmEgem5ha2FjaCBpbnRlcnB1bmtjeWpueWNoIGkgc3BlY2phbG55Y2guDQogIGZvciAod29yZCBpbiBzdHJzcGxpdChzYW1wbGUsICIgIilbWzFdXSkNCiAgICBpZiAoIXdvcmQgJWluJSBuYW1lcyh0b2tlbl9pbmRleCkpDQogICAgICAjIFByenlwaXN5d2FuaWUgdW5pa2F0b3dlZ28gaW5kZWtzdSBkbyBrYcW8ZGVnbyB1bmlrYXRvd2VnbyBzxYJvd2EuIA0KICAgICAgIyBad3LDs8SHIHV3YWfEmSBuYSB0bywgxbxlIGluZGVrcyAwIG5pZSBqZXN0IHByenlwaXN5d2FueSBkbyDFvGFkbmVnbyBzxYJvd2EuDQogICAgICB0b2tlbl9pbmRleFtbd29yZF1dIDwtIGxlbmd0aCh0b2tlbl9pbmRleCkgKyAyIA0KDQojIFdla3Rvcnl6YWNqYSBwcsOzYmVrLiANCiMgQmllcnplbXkgcG9kIHV3YWfEmSB0eWxrbyBtYXhfbGVuZ3RoIHBpZXJ3c3p5Y2ggc8WCw7N3IGthxbxkZWogcHLDs2JraS4NCm1heF9sZW5ndGggPC0gMTANCg0KIyBUdSBwcnplY2hvd3VqZW15IHd5bmlraSBvcGVyYWNqaS4NCnJlc3VsdHMgPC0gYXJyYXkoMCwgZGltID0gYyhsZW5ndGgoc2FtcGxlcyksIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1heF9sZW5ndGgsIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1heChhcy5pbnRlZ2VyKHRva2VuX2luZGV4KSkpKQ0KDQpmb3IgKGkgaW4gMTpsZW5ndGgoc2FtcGxlcykpIHsNCiAgc2FtcGxlIDwtIHNhbXBsZXNbW2ldXQ0KICB3b3JkcyA8LSBoZWFkKHN0cnNwbGl0KHNhbXBsZSwgIiAiKVtbMV1dLCBuID0gbWF4X2xlbmd0aCkNCiAgZm9yIChqIGluIDE6bGVuZ3RoKHdvcmRzKSkgew0KICAgIGluZGV4IDwtIHRva2VuX2luZGV4W1t3b3Jkc1tbal1dXV0NCiAgICByZXN1bHRzW1tpLCBqLCBpbmRleF1dIDwtIDENCiAgfQ0KfQ0KYGBgDQoNClByb3N0eSBwcnp5a8WCYWQga29kb3dhbmlhIHpuYWvDs3cgbWV0b2TEhSBnb3LEhWNlaiBqZWR5bmtpOg0KDQpgYGB7cn0NCnNhbXBsZXMgPC0gYygiVGhlIGNhdCBzYXQgb24gdGhlIG1hdC4iLCAiVGhlIGRvZyBhdGUgbXkgaG9tZXdvcmsuIikNCg0KYXNjaWlfdG9rZW5zIDwtIGMoIiIsIHNhcHBseShhcy5yYXcoYygzMjoxMjYpKSwgcmF3VG9DaGFyKSkNCnRva2VuX2luZGV4IDwtIGMoMToobGVuZ3RoKGFzY2lpX3Rva2VucykpKQ0KbmFtZXModG9rZW5faW5kZXgpIDwtIGFzY2lpX3Rva2Vucw0KDQptYXhfbGVuZ3RoIDwtIDUwDQoNCnJlc3VsdHMgPC0gYXJyYXkoMCwgZGltID0gYyhsZW5ndGgoc2FtcGxlcyksIG1heF9sZW5ndGgsIGxlbmd0aCh0b2tlbl9pbmRleCkpKQ0KDQpmb3IgKGkgaW4gMTpsZW5ndGgoc2FtcGxlcykpIHsNCiAgc2FtcGxlIDwtIHNhbXBsZXNbW2ldXQ0KICBjaGFyYWN0ZXJzIDwtIHN0cnNwbGl0KHNhbXBsZSwgIiIpW1sxXV0NCiAgZm9yIChqIGluIDE6bGVuZ3RoKGNoYXJhY3RlcnMpKSB7DQogICAgY2hhcmFjdGVyIDwtIGNoYXJhY3RlcnNbW2pdXQ0KICAgIHJlc3VsdHNbaSwgaiwgdG9rZW5faW5kZXhbW2NoYXJhY3Rlcl1dXSA8LSAxDQogIH0NCn0NCmBgYA0KDQpQYWtpZXQgS2VyYXMgamVzdCB3eXBvc2HFvG9ueSB3IG5hcnrEmWR6aWEgcHJ6ZXpuYWN6b25lIGRvIGtvZG93YW5pYSB6bmFrw7N3IGkgc8WCw7N3IG1ldG9kxIUgZ29yxIVjZWogamVkeW5raSAobmFyesSZZHppYSB0ZSBwb3RyYWZpxIUgcHJ6ZXR3YXJ6YcSHIHN1cm93eSB0ZWtzdCkuIFcgcHJha3R5Y2Ugd2FydG8geiBuaWNoIGtvcnp5c3RhxIcsIHBvbmlld2HFvCB3eWtvbnVqxIUgd2llbGUgd2HFvG55Y2ggb3BlcmFjamksIHRha2ljaCBqYWsgdXN1d2FuaWUgem5ha8OzdyBzcGVjamFsbnljaCBpIGJyYW5pZSBwb2QgdXdhZ8SZIHR5bGtvIG4gc8WCw7N3IG5hamN6xJnFm2NpZWogd3lzdMSZcHVqxIVjeWNoIHcgemJpb3J6ZSAoend5a2xlIHN0b3N1amUgc2nEmSB0YWtpZSBvZ3JhbmljemVuaWUgdyBjZWx1IHVuaWtuacSZY2lhIHByYWN5IHogYmFyZHpvIGR1xbx5bWkgcHJ6ZXN0cnplbmlhbWkgd2VrdG9yYSB3ZWrFm2Npb3dlZ28pLg0KDQpQcnp5a8WCYWQga29kb3dhbmlhIHPFgsOzdyBtZXRvZMSFIGdvcsSFY2VqIGplZHlua2kgcHJ6eSB1xbx5Y2l1IGdvdG93eWNoIG5hcnrEmWR6aSBwYWtpZXR1IEtlcmFzOg0KDQpgYGB7cn0NCmxpYnJhcnkoa2VyYXMpDQoNCnNhbXBsZXMgPC0gYygiVGhlIGNhdCBzYXQgb24gdGhlIG1hdC4iLCAiVGhlIGRvZyBhdGUgbXkgaG9tZXdvcmsuIikNCg0KIyBUd29yenkgbWVjaGFuaXptIHRva2VuaXphY2ppIHNrb25maWd1cm93YW55IHRhaywgYWJ5IGJyYcWCIHBvZCB1d2FnxJkgdHlsa28gMTAwMCBuYWpjesSZxZtjaWVqIHd5c3TEmXB1asSFY3ljaCBzxYLDs3cuDQp0b2tlbml6ZXIgPC0gdGV4dF90b2tlbml6ZXIobnVtX3dvcmRzID0gMTAwMCkgJT4lDQogIGZpdF90ZXh0X3Rva2VuaXplcihzYW1wbGVzKQ0KDQojIFphbWllbmlhIMWCYcWEY3VjaHkgbmEgbGlzdHkgaW5kZWtzw7N3ICh3YXJ0b8WbY2kgY2HFgmtvd2l0b2xpY3pib3dlKS4NCnNlcXVlbmNlcyA8LSB0ZXh0c190b19zZXF1ZW5jZXModG9rZW5pemVyLCBzYW1wbGVzKQ0KDQojIE1vxbxsaXdlIGplc3QgcsOzd25pZcW8IHV6eXNrYW5pZSBiZXpwb8WbcmVkbmllaiBiaW5hcm5laiByZXByZXplbnRhY2ppIGtvZG93YW5pYSBtZXRvZMSFIGdvcsSFY2VqIGplZHlua2kuDQojIFRlbiBnZW5lcmF0b3IgdG9rZW7Ds3cgb2JzxYJ1Z3VqZSB0YWvFvGUgaW5uZSB0cnlieSB3ZWt0b3J5emFjamkuDQpvbmVfaG90X3Jlc3VsdHMgPC0gdGV4dHNfdG9fbWF0cml4KHRva2VuaXplciwgc2FtcGxlcywgbW9kZSA9ICJiaW5hcnkiKQ0KDQojIFByenlrxYJhZCBrb2R1IHBvendhbGFqxIVjZWdvIG5hIHV6eXNrYW5pZSBkb3N0xJlwdSBkbyBpbmRla3N1IHPFgsOzdy4NCndvcmRfaW5kZXggPC0gdG9rZW5pemVyJHdvcmRfaW5kZXgNCg0KY2F0KCJabmFsZXppb25vIiwgbGVuZ3RoKHdvcmRfaW5kZXgpLCAidW5pa2F0b3d5Y2ggdG9rZW7Ds3cuXG4iKQ0KYGBgDQoNCk9kbWlhbsSFIGtvZG93YW5pYSBtZXRvZMSFIGdvcsSFY2VqIGplZHlua2ksIGt0w7NyYSBtb8W8ZSB6b3N0YcSHIHXFvHl0YSwgZ2R5IGxpY3piYSB1bmlrYXRvd3ljaCB0b2tlbsOzdyB3IHPFgm93bmlrdSBqZXN0IHpieXQgZHXFvGEsIGFieSBvYnPFgnXFvHnEhyBqxIUgdyBzcG9zw7NiIGphd255LCBqZXN0IHN6dHVjemthIGhhc3pvd2FuaWEgeiBnb3LEhWPEhSBqZWR5bmvEhSAoYW5nLiBvbmUtaG90IGhhc2hpbmcgdHJpY2spLiBaYW1pYXN0IGphd25pZSBwcnp5cGlzeXdhxIcgaW5kZWtzIGRvIGthxbxkZWdvIHplIHPFgsOzdyBpIHV0cnp5bXl3YcSHIG9kd2/FgmFuaWEgZG8gdHljaCBpbmRla3PDs3cgdyBzxYJvd25pa3UsIG1vxbxuYSBoYXN6b3dhxIcgc8WCb3dhIGRvIGZvcm15IHdla3RvcsOzdyBvIG9rcmXFm2xvbnltIHJvem1pYXJ6ZS4gWnd5a2xlIHJvYmkgc2nEmSB0byB6YSBwb21vY8SFIGJhcmR6byBsZWtraWVqIGZ1bmtjamkgaGFzenVqxIVjZWouIEfFgsOzd27EhSB6YWxldMSFIHRlaiBtZXRvZHkgamVzdCBicmFrIGtvbmllY3pub8WbY2kgdXRyenlteXdhbmlhIGphd25lZ28gaW5kZWtzdSBzxYLDs3csIGNvIHBvendhbGEgb3N6Y3rEmWR6acSHIHByemVzdHJ6ZcWEIHBhbWnEmWNpIGkgemFrb2Rvd2HEhyBkYW5lIHcgbG9jaWUgKG1vxbxsaXdlIGplc3QgbmF0eWNobWlhc3Rvd2Ugd3lnZW5lcm93YW5pZSB3ZWt0b3LDs3cgdG9rZW5hLCBiZXogcG90cnplYnkgcHJ6eWdsxIVkYW5pYSBzacSZIGNhxYJvxZtjaSBkb3N0xJlwbnljaCBkYW55Y2gpLiBXYWTEhSB0ZWdvIHJvendpxIV6YW5pYSBqZXN0IG1vxbxsaXdvxZvEhyB3eXN0xIVwaWVuaWEga29uZmxpa3TDs3cgaGFzenkgKGFuZy4gaGFzaCBjb2xsaXNpb25zKSwgcG9sZWdhasSFY3ljaCBuYSBwcnplcGlzYW5pdSB0ZWdvIHNhbWVnbyBoYXN6YSBkd8OzbSByw7PFvG55bSBzxYJvd29tICh3IHRha2ltIHByenlwYWRrdSDFvGFkZW4gbW9kZWwgdWN6ZW5pYSBtYXN6eW5vd2VnbyBhbmFsaXp1asSFY3kgdXp5c2thbmUgaGFzemUgbmllIGLEmWR6aWUgbcOzZ8WCIG9kcsOzxbxuacSHIG9kIHNpZWJpZSB0eWNoIHPFgsOzdykuIFByYXdkb3BvZG9iaWXFhHN0d28gd3lzdMSFcGllbmlhIGtvbmZsaWt0w7N3IGhhc3p5IG1hbGVqZSwgZ2R5IHByemVzdHJ6ZcWEIGhhc3pvd2FuaWEgamVzdCBvIHdpZWxlIHdpxJlrc3phIG9kIGNhxYJrb3dpdGVqIGxpY3pieSB1bmlrYXRvd3ljaCBoYXN6b3dhbnljaCB0b2tlbsOzdy4NCg0KUHJvc3R5IHByenlrxYJhZCBzenR1Y3praSBoYXN6b3dhbmlhIHPFgsOzdyBtZXRvZMSFIGdvcsSFY2VqIGplZHlua2k6DQoNCmBgYHtyfQ0KbGlicmFyeShoYXNoRnVuY3Rpb24pDQoNCnNhbXBsZXMgPC0gYygiVGhlIGNhdCBzYXQgb24gdGhlIG1hdC4iLCAiVGhlIGRvZyBhdGUgbXkgaG9tZXdvcmsuIikNCg0KIyBTxYJvd2Egc8SFIHphcGlzeXdhbmUgdyBwb3N0YWNpIHdla3RvcsOzdyBvIGTFgnVnb8WbY2kgMTAwMC4gDQojIEplxbxlbGkgcHJ6ZXR3b3J6eW15IHByenlrxYJhZCwgdyBrdMOzcnltIHpuYWpkdWplIHNpxJkgb2tvxYJvIDEwMDAgcsOzxbxueWNoIHPFgsOzdywgdG8gemF1d2HFvHlteSB3aWVsZSBrb25mbGlrdMOzdyANCiMgaGFzenksIGt0w7NyZSBkb3Byb3dhZHrEhSBkbyBwb2dvcnN6ZW5pYSBkb2vFgmFkbm/Fm2NpIHRlaiBtZXRvZHkga29kb3dhbmlhLg0KDQpkaW1lbnNpb25hbGl0eSA8LSAxMDAwDQptYXhfbGVuZ3RoIDwtIDEwDQoNCnJlc3VsdHMgPC0gYXJyYXkoMCwgZGltID0gYyhsZW5ndGgoc2FtcGxlcyksIG1heF9sZW5ndGgsIGRpbWVuc2lvbmFsaXR5KSkNCg0KZm9yIChpIGluIDE6bGVuZ3RoKHNhbXBsZXMpKSB7DQogIHNhbXBsZSA8LSBzYW1wbGVzW1tpXV0NCiAgd29yZHMgPC0gaGVhZChzdHJzcGxpdChzYW1wbGUsICIgIilbWzFdXSwgbiA9IG1heF9sZW5ndGgpDQogIGZvciAoaiBpbiAxOmxlbmd0aCh3b3JkcykpIHsNCiAgICAjIFPFgm93b20gcHJ6eXBpc3l3YW5lIHPEhSBsb3Nvd2Ugd2FydG/Fm2NpIGNhxYJrb3dpdGUgaW5kZWtzdSB6IHpha3Jlc3Ugb2QgMCBkbyAxMDAwLg0KICAgIGluZGV4IDwtIGFicyhzcG9va3kuMzIod29yZHNbW2ldXSkpICUlIGRpbWVuc2lvbmFsaXR5DQogICAgcmVzdWx0c1tbaSwgaiwgaW5kZXhdXSA8LSAxDQogIH0NCn0NCmBgYA0KDQoNCg==