Diese Pakete müssen nur beim allerersten Mal installiert werden!

install.packages("SnowballC")
install.packages("tau")
install.packages("tm")
install.packages("readr")
install.packages("tidytext")
install.packages("wordcloud")
install.packages("dplyr")

Hier werden schon mal einige Libraries geladen

library("SnowballC")
library("tm")
Loading required package: NLP
library("tidytext")
library("dplyr")

Attaching package: ‘dplyr’

The following objects are masked from ‘package:stats’:

    filter, lag

The following objects are masked from ‘package:base’:

    intersect, setdiff, setequal, union

Der Stemmer SnowballC stemmt leider nur das letzte Wort eines Ausdrucks; das Problem hatten auch schon andere bemerkt und dann diese kleine Funktion geschrieben, die jedes Wort in einem Ausdruck stemmt. Hier laden wir erst mal nur diese Funktion, sie wird erst später genutzt

require(tau)
Loading required package: tau
stem_text<- function(text) {
  # stem each word in a block of text
  stem_string <- function(str) {
    str <- tokenize(x = str)
    str <- wordStem(str, language = "german")
    str <- paste(str, collapse = "")
    return(str)
  }
 
  # stem each text block in turn
  x <- lapply(X = text, FUN = stem_string)
 
  # return stemed text blocks
  return(unlist(x))
}

Einmal testen, ob das auch funktioniert :-) Du kannst zwischen den Gänsefüschen eintragen was Du willst und dann selber testen

stem_text("erfahrener Programmierer")
[1] "erfahr Programmi"

Jetzt lesen wir unseren Corpus ein

goethe <- read.csv("goethe.csv")

Dies ist eine kleine Funktion, die uns davor bewahrt, dass wir Müll verarbeiten, sie wird später aufgerufen

cleanThis <- function(x) {
  Encoding(x) <- "UTF-8"
  x <- iconv(x, "UTF-8", "UTF-8",sub='')
  return(x)
}

Nun gehts richtig los

goetheCorp <- paste(goethe$title,goethe$gedicht,sep=" ") # Wir schmeißen Titel und Inhalt zusammen
review_corpus = Corpus(VectorSource(goetheCorp)) # lesen das in den Corpus ein
review_corpus = tm_map(review_corpus, cleanThis) # verhindern, dass wir Müll verarbeiten
review_corpus = tm_map(review_corpus, content_transformer(tolower)) # machen alle Begriffe klein
review_corpus = tm_map(review_corpus, removeNumbers) # entfernen Zahlen
review_corpus = tm_map(review_corpus, removePunctuation) # entfernen Punkte etc
review_corpus = tm_map(review_corpus, stripWhitespace) # leere Zeichen werden entfernt
review_corpus = tm_map(review_corpus, removeWords, c(stopwords("german"))) #Stopwörter werden entfernt
#review_corpus = tm_map(review_corpus, stem_text)
inspect(review_corpus[1]) # Was hat das jetzt mit unserem ersten Dokument gemacht?
<<SimpleCorpus>>
Metadata:  corpus specific: 1, document level (indexed): 0
Content:  documents: 1

[1] zweite epistel   leichter geholfen versetz   wohl  andrer denken möchte  mädchen  gut    gerne   schaffen  gib     schlüssel  keller    weine  vaters besorge sobald   winzer   kaufmann geliefert  weiten gewölbe bereichern   schaffen   mädchen  vielen gefäße leere fässer  flaschen  reinlicher ordnung  halten  betrachtet  oft  schäumenden mostes bewegung gießt  fehlende    wallenden blasen leicht  öffnung  fasses erreichen trinkbar  helle endlich  edelste saft  künftigen jahren vollende unermüdet   alsdann  füllen  schöpfen  stets geistig  trunk  rein  tafel belebe laß    küche  reich  gibt  wahrhaftig arbeit genug  tägliche mahl  sommer  winter schmackhaft stets  bereiten   beschwerde  beutels   frühjahr sorget  schon  hofe  küchlein bald  erziehen  bald  schnatternden enten  füttern     jahrszeit gibt  bringt  beizeiten    tisch  weiß  jeglichem tage  speisen klug  wechseln  reift  eben  sommer  früchte denkt   vorrat schon   winter  kühlen gewölbe gärt   kräftige kohl  reifen  essig  gurken   luftige kammer bewahrt   gaben pomonens gerne nimmt   lob  vater   geschwistern  mißlingt    ists  größeres unglück     schuldner entläuft   wechsel zurückläßt immer    mädchen beschäftigt  reifet  stillen häuslicher tugend entgegen  klugen mann  beglücken wünscht   endlich  lesen  wählt  gewißlich  kochbuch deren hunderte schon  eifrigen pressen  gaben  schwester besorget  garten  schwerlich  wildnis  wohnung romantisch  feucht  umgeben verdammt    zierliche beete geteilt  vorhof  küche nützliche kräuter ernährt  jugendbeglückende früchte patriarchalisch erzeuge     kleines gedrängtes königreich  bevölkre  haus  treuem gesinde hast   töchter  mehr  lieber sitzen  stille weibliche arbeit verrichten  ists  besser  nadel ruht  jahre  leicht    häuslich  hause mögen  öffentlich gern  müßige damen erscheinen    nähen  flicken vermehrt  waschen  biegeln hundertfältig seitdem  weißer arkadischer hülle   mädchen gefällt  langen röcken  schleppen gassen kehret  gärten  staub erreget  tanzsaal wahrlich wären    mädchen  dutzend  hause niemals wär  verlegen  arbeit    arbeit selber genug    buch  laufe  jahres   schwelle  kommen  bücherverleiher gesendet    

Aus unserem Corpur wird eine DokumentTermMatrix gebaut

review_dtm <- DocumentTermMatrix(review_corpus)
#review_dtm = removeSparseTerms(review_dtm, 0.95) # wir verzichten darauf, dass die Sparse Terms entfernt werden
review_dtm
<<DocumentTermMatrix (documents: 124, terms: 4567)>>
Non-/sparse entries: 8303/558005
Sparsity           : 99%
Maximal term length: 24
Weighting          : term frequency (tf)

Aus der DokumentTermMatrix bauen wir uns einen Dataframe

DTM <- tidy(review_dtm)

Und nun kommen wir zum spannenden Teil :-) Wir rechnen TF, IDF, WDF etc alles selbst aus :-)

So würde man das in R normalerweise nicht bauen, ABER so ist es zumindest nachvollziehbar für jeden. Der Code ist weder elegant noch performant.

AllWeightings_DTM <- data.frame()
N <- length(unique(DTM$document)) # total number of documents
allUniqueTerms <- unique(DTM$term) #unique terms
docIDs <- unique(DTM$document) # Die Dokumentennummern, die wir haben; wichtig, falls wir doch die Sparse Terms rausnehmen, da dann evtl Dokumente rausfliegen
i <- 1
for (i in docIDs) {
  uniqueTerms <- unique(DTM$term[DTM$document == i]) # eine Liste alle unique Begriffe in diesem Dokument
  numOfTermsInDocument <- sum(DTM[DTM$document == i, "count"])  # eine Liste aller Terme in dem Dokument
  for (term in uniqueTerms) {
    tf <- DTM$count[DTM$document == i & DTM$term == term] # wir berechnen die einfache Termfrequenz
    relDocs <- nrow(DTM[ which(DTM$term == term),]) # wie viele Dokumente im Corpus beinhalten noch diesen Begriff?
    idf <- log2((N/relDocs)) # einmal IDF bitte
    tf_idf <- tf*idf # einfaches tf/idf
    normalized_tf <- (tf/numOfTermsInDocument) #normalisiertes TF 
    normalized_tf_idf <- normalized_tf*idf #TF/IDF mit TF normalsiert
    wdfidf <- (log2(tf+1)/log2(numOfTermsInDocument))*idf # zum Schluß einmal WDF/IDF
    
    # jetzt packen wir noch alles in einen Data Frame
    theWeight <- data.frame(i,term,tf,numOfTermsInDocument,normalized_tf,relDocs,idf,tf_idf,normalized_tf_idf,wdfidf)
    AllWeightings_DTM <- rbind(theWeight,AllWeightings_DTM)
  }
  
}
# wir erstellen mal einen Dataframe für einen Begriff und geben ihn aus
(maedchen <- AllWeightings_DTM %>% # 
  filter(term == "mädchen") %>%
  arrange(desc(wdfidf)))

Jetzt machen wir alles noch mal, aber dieses Mal stemmen wir die Begriffe!

review_corpus = tm_map(review_corpus, stem_text)
review_dtm <- DocumentTermMatrix(review_corpus)
DTM <- tidy(review_dtm)
AllWeightings_DTM_stemmed <- data.frame()
N <- length(unique(DTM$document)) 
allUniqueTerms <- unique(DTM$term)
docIDs <- unique(DTM$document) 
i <- 1
for (i in docIDs) {
  uniqueTerms <- unique(DTM$term[DTM$document == i])
  numOfTermsInDocument <- sum(DTM[DTM$document == i, "count"])
  for (term in uniqueTerms) {
    tf <- DTM$count[DTM$document == i & DTM$term == term]
    relDocs <- nrow(DTM[ which(DTM$term == term),])
    idf <- log2((N/relDocs))
    tf_idf <- tf*idf # einfaches tf/idf
    normalized_tf <- (tf/numOfTermsInDocument)
    normalized_tf_idf <- normalized_tf*idf
    wdfidf <- (log2(tf+1)/log2(numOfTermsInDocument))*idf
    
    theWeight <- data.frame(i,term,tf,numOfTermsInDocument,normalized_tf,relDocs,idf,tf_idf,normalized_tf_idf,wdfidf)
    AllWeightings_DTM_stemmed <- rbind(theWeight,AllWeightings_DTM_stemmed)
  }
  
}
# wir erstellen mal einen Dataframe für den gleichen Begriff
(maedchen_stemmed <- AllWeightings_DTM_stemmed %>% # 
  filter(term == "mädchen") %>%
  arrange(desc(wdfidf)))
LS0tCnRpdGxlOiAiU3RlbW1pbmcgdW5kIFRGL0lERiBpbiBlaW5lbSBrbGVpbmVuIEdvZXRoZS1Db3JwdXMiCm91dHB1dDoKICBodG1sX2RvY3VtZW50OiBkZWZhdWx0CiAgaHRtbF9ub3RlYm9vazogZGVmYXVsdAotLS0KRGllc2UgUGFrZXRlIG3DvHNzZW4gbnVyIGJlaW0gYWxsZXJlcnN0ZW4gTWFsIGluc3RhbGxpZXJ0IHdlcmRlbiEKYGBge3J9Cmluc3RhbGwucGFja2FnZXMoIlNub3diYWxsQyIpCmluc3RhbGwucGFja2FnZXMoInRhdSIpCmluc3RhbGwucGFja2FnZXMoInRtIikKaW5zdGFsbC5wYWNrYWdlcygicmVhZHIiKQppbnN0YWxsLnBhY2thZ2VzKCJ0aWR5dGV4dCIpCmluc3RhbGwucGFja2FnZXMoIndvcmRjbG91ZCIpCmluc3RhbGwucGFja2FnZXMoImRwbHlyIikKYGBgCgpIaWVyIHdlcmRlbiBzY2hvbiBtYWwgZWluaWdlIExpYnJhcmllcyBnZWxhZGVuCmBgYHtyfQpsaWJyYXJ5KCJTbm93YmFsbEMiKQpsaWJyYXJ5KCJ0bSIpCmxpYnJhcnkoInRpZHl0ZXh0IikKbGlicmFyeSgiZHBseXIiKQpgYGAKCkRlciBTdGVtbWVyIFNub3diYWxsQyBzdGVtbXQgbGVpZGVyIG51ciBkYXMgbGV0enRlIFdvcnQgZWluZXMgQXVzZHJ1Y2tzOyBkYXMgUHJvYmxlbSBoYXR0ZW4gYXVjaCBzY2hvbiBhbmRlcmUgYmVtZXJrdCB1bmQgZGFubiBkaWVzZSBrbGVpbmUgRnVua3Rpb24gZ2VzY2hyaWViZW4sIGRpZSBqZWRlcyBXb3J0IGluIGVpbmVtIEF1c2RydWNrIHN0ZW1tdC4gSGllciBsYWRlbiB3aXIgZXJzdCBtYWwgbnVyIGRpZXNlIEZ1bmt0aW9uLCBzaWUgd2lyZCBlcnN0IHNww6R0ZXIgZ2VudXR6dApgYGB7cn0KcmVxdWlyZSh0YXUpCnN0ZW1fdGV4dDwtIGZ1bmN0aW9uKHRleHQpIHsKICAjIHN0ZW0gZWFjaCB3b3JkIGluIGEgYmxvY2sgb2YgdGV4dAogIHN0ZW1fc3RyaW5nIDwtIGZ1bmN0aW9uKHN0cikgewogICAgc3RyIDwtIHRva2VuaXplKHggPSBzdHIpCiAgICBzdHIgPC0gd29yZFN0ZW0oc3RyLCBsYW5ndWFnZSA9ICJnZXJtYW4iKQogICAgc3RyIDwtIHBhc3RlKHN0ciwgY29sbGFwc2UgPSAiIikKICAgIHJldHVybihzdHIpCiAgfQogCiAgIyBzdGVtIGVhY2ggdGV4dCBibG9jayBpbiB0dXJuCiAgeCA8LSBsYXBwbHkoWCA9IHRleHQsIEZVTiA9IHN0ZW1fc3RyaW5nKQogCiAgIyByZXR1cm4gc3RlbWVkIHRleHQgYmxvY2tzCiAgcmV0dXJuKHVubGlzdCh4KSkKfQpgYGAKCkVpbm1hbCB0ZXN0ZW4sIG9iIGRhcyBhdWNoIGZ1bmt0aW9uaWVydCA6LSkgRHUga2FubnN0IHp3aXNjaGVuIGRlbiBHw6Ruc2Vmw7xzY2hlbiBlaW50cmFnZW4gd2FzIER1IHdpbGxzdCB1bmQgZGFubiBzZWxiZXIgdGVzdGVuCmBgYHtyfQpzdGVtX3RleHQoImVyZmFocmVuZXIgUHJvZ3JhbW1pZXJlciIpCmBgYAoKSmV0enQgbGVzZW4gd2lyIHVuc2VyZW4gQ29ycHVzIGVpbgpgYGB7cn0KZ29ldGhlIDwtIHJlYWQuY3N2KCJnb2V0aGUuY3N2IikKYGBgCgpEaWVzIGlzdCBlaW5lIGtsZWluZSBGdW5rdGlvbiwgZGllIHVucyBkYXZvciBiZXdhaHJ0LCBkYXNzIHdpciBNw7xsbCB2ZXJhcmJlaXRlbiwgc2llIHdpcmQgc3DDpHRlciBhdWZnZXJ1ZmVuCmBgYHtyfQpjbGVhblRoaXMgPC0gZnVuY3Rpb24oeCkgewogIEVuY29kaW5nKHgpIDwtICJVVEYtOCIKICB4IDwtIGljb252KHgsICJVVEYtOCIsICJVVEYtOCIsc3ViPScnKQogIHJldHVybih4KQp9CmBgYAoKTnVuIGdlaHRzIHJpY2h0aWcgbG9zCmBgYHtyfQpnb2V0aGVDb3JwIDwtIHBhc3RlKGdvZXRoZSR0aXRsZSxnb2V0aGUkZ2VkaWNodCxzZXA9IiAiKSAjIFdpciBzY2htZWnDn2VuIFRpdGVsIHVuZCBJbmhhbHQgenVzYW1tZW4KcmV2aWV3X2NvcnB1cyA9IENvcnB1cyhWZWN0b3JTb3VyY2UoZ29ldGhlQ29ycCkpICMgbGVzZW4gZGFzIGluIGRlbiBDb3JwdXMgZWluCnJldmlld19jb3JwdXMgPSB0bV9tYXAocmV2aWV3X2NvcnB1cywgY2xlYW5UaGlzKSAjIHZlcmhpbmRlcm4sIGRhc3Mgd2lyIE3DvGxsIHZlcmFyYmVpdGVuCnJldmlld19jb3JwdXMgPSB0bV9tYXAocmV2aWV3X2NvcnB1cywgY29udGVudF90cmFuc2Zvcm1lcih0b2xvd2VyKSkgIyBtYWNoZW4gYWxsZSBCZWdyaWZmZSBrbGVpbgpyZXZpZXdfY29ycHVzID0gdG1fbWFwKHJldmlld19jb3JwdXMsIHJlbW92ZU51bWJlcnMpICMgZW50ZmVybmVuIFphaGxlbgpyZXZpZXdfY29ycHVzID0gdG1fbWFwKHJldmlld19jb3JwdXMsIHJlbW92ZVB1bmN0dWF0aW9uKSAjIGVudGZlcm5lbiBQdW5rdGUgZXRjCnJldmlld19jb3JwdXMgPSB0bV9tYXAocmV2aWV3X2NvcnB1cywgc3RyaXBXaGl0ZXNwYWNlKSAjIGxlZXJlIFplaWNoZW4gd2VyZGVuIGVudGZlcm50CnJldmlld19jb3JwdXMgPSB0bV9tYXAocmV2aWV3X2NvcnB1cywgcmVtb3ZlV29yZHMsIGMoc3RvcHdvcmRzKCJnZXJtYW4iKSkpICNTdG9wd8O2cnRlciB3ZXJkZW4gZW50ZmVybnQKaW5zcGVjdChyZXZpZXdfY29ycHVzWzFdKSAjIFdhcyBoYXQgZGFzIGpldHp0IG1pdCB1bnNlcmVtIGVyc3RlbiBEb2t1bWVudCBnZW1hY2h0PwpgYGAKCkF1cyB1bnNlcmVtIENvcnB1ciB3aXJkIGVpbmUgRG9rdW1lbnRUZXJtTWF0cml4IGdlYmF1dApgYGB7cn0KcmV2aWV3X2R0bSA8LSBEb2N1bWVudFRlcm1NYXRyaXgocmV2aWV3X2NvcnB1cykKI3Jldmlld19kdG0gPSByZW1vdmVTcGFyc2VUZXJtcyhyZXZpZXdfZHRtLCAwLjk1KSAjIHdpciB2ZXJ6aWNodGVuIGRhcmF1ZiwgZGFzcyBkaWUgU3BhcnNlIFRlcm1zIGVudGZlcm50IHdlcmRlbgpyZXZpZXdfZHRtCmBgYAoKQXVzIGRlciBEb2t1bWVudFRlcm1NYXRyaXggYmF1ZW4gd2lyIHVucyBlaW5lbiBEYXRhZnJhbWUKYGBge3J9CkRUTSA8LSB0aWR5KHJldmlld19kdG0pCmBgYAoKVW5kIG51biBrb21tZW4gd2lyIHp1bSBzcGFubmVuZGVuIFRlaWwgOi0pIFdpciByZWNobmVuIFRGLCBJREYsIFdERiBldGMgYWxsZXMgc2VsYnN0IGF1cyA6LSkKClNvIHfDvHJkZSBtYW4gZGFzIGluIFIgbm9ybWFsZXJ3ZWlzZSBuaWNodCBiYXVlbiwgQUJFUiBzbyBpc3QgZXMgenVtaW5kZXN0IG5hY2h2b2xsemllaGJhciBmw7xyIGplZGVuLiBEZXIgQ29kZSBpc3Qgd2VkZXIgZWxlZ2FudCBub2NoIHBlcmZvcm1hbnQuCmBgYHtyfQpBbGxXZWlnaHRpbmdzX0RUTSA8LSBkYXRhLmZyYW1lKCkKCk4gPC0gbGVuZ3RoKHVuaXF1ZShEVE0kZG9jdW1lbnQpKSAjIHRvdGFsIG51bWJlciBvZiBkb2N1bWVudHMKCmFsbFVuaXF1ZVRlcm1zIDwtIHVuaXF1ZShEVE0kdGVybSkgI3VuaXF1ZSB0ZXJtcwoKZG9jSURzIDwtIHVuaXF1ZShEVE0kZG9jdW1lbnQpICMgRGllIERva3VtZW50ZW5udW1tZXJuLCBkaWUgd2lyIGhhYmVuOyB3aWNodGlnLCBmYWxscyB3aXIgZG9jaCBkaWUgU3BhcnNlIFRlcm1zIHJhdXNuZWhtZW4sIGRhIGRhbm4gZXZ0bCBEb2t1bWVudGUgcmF1c2ZsaWVnZW4KCmkgPC0gMQoKZm9yIChpIGluIGRvY0lEcykgewoKICB1bmlxdWVUZXJtcyA8LSB1bmlxdWUoRFRNJHRlcm1bRFRNJGRvY3VtZW50ID09IGldKSAjIGVpbmUgTGlzdGUgYWxsZSB1bmlxdWUgQmVncmlmZmUgaW4gZGllc2VtIERva3VtZW50CiAgbnVtT2ZUZXJtc0luRG9jdW1lbnQgPC0gc3VtKERUTVtEVE0kZG9jdW1lbnQgPT0gaSwgImNvdW50Il0pICAjIGVpbmUgTGlzdGUgYWxsZXIgVGVybWUgaW4gZGVtIERva3VtZW50CgogIGZvciAodGVybSBpbiB1bmlxdWVUZXJtcykgewoKICAgIHRmIDwtIERUTSRjb3VudFtEVE0kZG9jdW1lbnQgPT0gaSAmIERUTSR0ZXJtID09IHRlcm1dICMgd2lyIGJlcmVjaG5lbiBkaWUgZWluZmFjaGUgVGVybWZyZXF1ZW56CgogICAgcmVsRG9jcyA8LSBucm93KERUTVsgd2hpY2goRFRNJHRlcm0gPT0gdGVybSksXSkgIyB3aWUgdmllbGUgRG9rdW1lbnRlIGltIENvcnB1cyBiZWluaGFsdGVuIG5vY2ggZGllc2VuIEJlZ3JpZmY/CiAgICBpZGYgPC0gbG9nMigoTi9yZWxEb2NzKSkgIyBlaW5tYWwgSURGIGJpdHRlCiAgICB0Zl9pZGYgPC0gdGYqaWRmICMgZWluZmFjaGVzIHRmL2lkZgoKICAgIG5vcm1hbGl6ZWRfdGYgPC0gKHRmL251bU9mVGVybXNJbkRvY3VtZW50KSAjbm9ybWFsaXNpZXJ0ZXMgVEYgCiAgICBub3JtYWxpemVkX3RmX2lkZiA8LSBub3JtYWxpemVkX3RmKmlkZiAjVEYvSURGIG1pdCBURiBub3JtYWxzaWVydAoKICAgIHdkZmlkZiA8LSAobG9nMih0ZisxKS9sb2cyKG51bU9mVGVybXNJbkRvY3VtZW50KSkqaWRmICMgenVtIFNjaGx1w58gZWlubWFsIFdERi9JREYKICAgIAogICAgIyBqZXR6dCBwYWNrZW4gd2lyIG5vY2ggYWxsZXMgaW4gZWluZW4gRGF0YSBGcmFtZQogICAgdGhlV2VpZ2h0IDwtIGRhdGEuZnJhbWUoaSx0ZXJtLHRmLG51bU9mVGVybXNJbkRvY3VtZW50LG5vcm1hbGl6ZWRfdGYscmVsRG9jcyxpZGYsdGZfaWRmLG5vcm1hbGl6ZWRfdGZfaWRmLHdkZmlkZikKICAgIEFsbFdlaWdodGluZ3NfRFRNIDwtIHJiaW5kKHRoZVdlaWdodCxBbGxXZWlnaHRpbmdzX0RUTSkKICB9CiAgCn0KCiMgd2lyIGVyc3RlbGxlbiBtYWwgZWluZW4gRGF0YWZyYW1lIGbDvHIgZWluZW4gQmVncmlmZiB1bmQgZ2ViZW4gaWhuIGF1cwoobWFlZGNoZW4gPC0gQWxsV2VpZ2h0aW5nc19EVE0gJT4lICMgCiAgZmlsdGVyKHRlcm0gPT0gIm3DpGRjaGVuIikgJT4lCiAgYXJyYW5nZShkZXNjKHdkZmlkZikpKQpgYGAKCkpldHp0IG1hY2hlbiB3aXIgYWxsZXMgbm9jaCBtYWwsIGFiZXIgZGllc2VzIE1hbCBzdGVtbWVuIHdpciBkaWUgQmVncmlmZmUhCgpgYGB7cn0KcmV2aWV3X2NvcnB1cyA9IHRtX21hcChyZXZpZXdfY29ycHVzLCBzdGVtX3RleHQpCnJldmlld19kdG0gPC0gRG9jdW1lbnRUZXJtTWF0cml4KHJldmlld19jb3JwdXMpCkRUTSA8LSB0aWR5KHJldmlld19kdG0pCgpBbGxXZWlnaHRpbmdzX0RUTV9zdGVtbWVkIDwtIGRhdGEuZnJhbWUoKQoKTiA8LSBsZW5ndGgodW5pcXVlKERUTSRkb2N1bWVudCkpIAoKYWxsVW5pcXVlVGVybXMgPC0gdW5pcXVlKERUTSR0ZXJtKQoKZG9jSURzIDwtIHVuaXF1ZShEVE0kZG9jdW1lbnQpIAoKaSA8LSAxCgpmb3IgKGkgaW4gZG9jSURzKSB7CgogIHVuaXF1ZVRlcm1zIDwtIHVuaXF1ZShEVE0kdGVybVtEVE0kZG9jdW1lbnQgPT0gaV0pCiAgbnVtT2ZUZXJtc0luRG9jdW1lbnQgPC0gc3VtKERUTVtEVE0kZG9jdW1lbnQgPT0gaSwgImNvdW50Il0pCgogIGZvciAodGVybSBpbiB1bmlxdWVUZXJtcykgewoKICAgIHRmIDwtIERUTSRjb3VudFtEVE0kZG9jdW1lbnQgPT0gaSAmIERUTSR0ZXJtID09IHRlcm1dCgogICAgcmVsRG9jcyA8LSBucm93KERUTVsgd2hpY2goRFRNJHRlcm0gPT0gdGVybSksXSkKICAgIGlkZiA8LSBsb2cyKChOL3JlbERvY3MpKQogICAgdGZfaWRmIDwtIHRmKmlkZiAjIGVpbmZhY2hlcyB0Zi9pZGYKCiAgICBub3JtYWxpemVkX3RmIDwtICh0Zi9udW1PZlRlcm1zSW5Eb2N1bWVudCkKICAgIG5vcm1hbGl6ZWRfdGZfaWRmIDwtIG5vcm1hbGl6ZWRfdGYqaWRmCgogICAgd2RmaWRmIDwtIChsb2cyKHRmKzEpL2xvZzIobnVtT2ZUZXJtc0luRG9jdW1lbnQpKSppZGYKICAgIAogICAgdGhlV2VpZ2h0IDwtIGRhdGEuZnJhbWUoaSx0ZXJtLHRmLG51bU9mVGVybXNJbkRvY3VtZW50LG5vcm1hbGl6ZWRfdGYscmVsRG9jcyxpZGYsdGZfaWRmLG5vcm1hbGl6ZWRfdGZfaWRmLHdkZmlkZikKICAgIEFsbFdlaWdodGluZ3NfRFRNX3N0ZW1tZWQgPC0gcmJpbmQodGhlV2VpZ2h0LEFsbFdlaWdodGluZ3NfRFRNX3N0ZW1tZWQpCiAgfQogIAp9CgojIHdpciBlcnN0ZWxsZW4gbWFsIGVpbmVuIERhdGFmcmFtZSBmw7xyIGRlbiBnbGVpY2hlbiBCZWdyaWZmCihtYWVkY2hlbl9zdGVtbWVkIDwtIEFsbFdlaWdodGluZ3NfRFRNX3N0ZW1tZWQgJT4lICMgCiAgZmlsdGVyKHRlcm0gPT0gIm3DpGRjaGVuIikgJT4lCiAgYXJyYW5nZShkZXNjKHdkZmlkZikpKQpgYGAKCg==