Before we start, below code will install the necessary packages if they are not available. The code comes from Pratik Patil’s answer here.

# Function to Install and Load   R Packages using Pratik Patil's answer 
install_and_load <- function(Required_Packages)
{
    Remaining_Packages <- Required_Packages[!(Required_Packages %in% installed.packages()[,"Package"])];

    if(length(Remaining_Packages)) 
    {
        install.packages(Remaining_Packages);
    }
    for(package_name in Required_Packages)
    {
        library(package_name,character.only=TRUE,quietly=TRUE,warn.conflicts = FALSE);
    }
}

# Specify the list of required packages to be installed and load    
Required_Packages=c("markovchain",
                    "dplyr",
                    "stringr",
                    "MmgraphR",
                    "expm",
                    "diagram",
                    "igraph",
                    "tm",
                    "RWeka",
                    "plotly");

# Call the Function
install_and_load(Required_Packages);

Introduction to Markov Chains

As described by Wikipedia:

A Markov chain is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event.

This property of memorylessness (dependence only on the preceding state) is called the Markov property.

A Markov chain is used to model a random process consisting of multiple states. These systems can be finite or infinite. An example for a finite Markov Process could be the position of an elevator in a building. The number of states (floors) is finite and we are interested in the probability to find the system in a specific state at a future time. Infinite Markov Processes have (as the name suggest) an infinite number of states. We have knowledge about the transition between the states and are interested in the state of the system at a future time. An example for such a process would be the Galton-Watson-Process that models the size of populations.

In the following we will focus on finite Markov Chains. For those we need two things: 1. The random states. 2. The transition probabilities between the states.

Below system (that was stolen from here ) consists of two states: E and A. There are four possible transitions in this model:

Example of a finite Markov Chain

Example of a finite Markov Chain

Questions:

  1. What are the possible transitions and their probabilities?
  1. E to E: p = 0.3
  2. E to A: p = 0.7
  3. A to A: p = 0.6
  4. A to E: p = 0.4

The R packages used here (and most implementation in general) require this data to be stored in a matrix:

ref <- c("A","E")
transition_matrix <- matrix(0, ncol = 2, nrow=2)
row.names(transition_matrix) <- ref
colnames(transition_matrix) <- ref
transition_matrix <- matrix(c(0.6,0.4,0.7,0.3),nrow=2, byrow=TRUE)
transition_matrix
##      [,1] [,2]
## [1,]  0.6  0.4
## [2,]  0.7  0.3

This is all we need to get started. There are of course more sub-classifications and you can also take a mathematical more rigorous approach. But above suffices to get the idea. Let’s now build a first application.

Questions:

  1. Before we continue. Why is this a square matrix?

Forecasting the weather with a Markov Chain

We live on an island somewhere in the midst of the ocean. The living conditions are harsh and we only know three kinds of weather: Rain, snow and nice (the absence of the two, so storm, fog, blizzard-like cold, …) - those will be the possible random states of our little island. Now we need the transition probabilities between those states. A rainy day is likely followed by another rainy day, with an equal chance for nice or snowy weather the following day. If a day is nice we can rest assured that the next will be either rainy or snowy (OK there is very slight chance to have another nice day). And for a snowy day it’s the same as for the rainy day (at least the island was cheap). Since we are just starting out as (autodidact) meteorologists we boldly assume that the weather of tomorrow is influence by nothing else than the weather of today.

Questions

  1. Can we build a Markov model with given information?
  2. If yes think what the next steps would look like.

We covered all the state-transitions and our weather forecast idea fulfills the Markov property. We are good to go.

The probabilities are stored in a matrix that is called the transition matrix. The following R chunk creates the states, the transition matrix and initializes a Markov Chain with that information.

Questions

  1. Have a look at the code chunk below. What does it do?
  2. A graph of our model is shown below. Does it make sense?
##       [,1] [,2]  [,3]
## [1,] 0.500 0.25 0.250
## [2,] 0.475 0.05 0.475
## [3,] 0.250 0.25 0.500

The graph looks good and we are most certain that our Markov Model will be fit for the job.

We can now use the Markov chain to make predictions for the next days. If you are interested in additional layouts for the plot check the igraph documentation.

Questions:

  1. If you want your results to be reproducible what do you need to do?

As this is a random process we need to set the seed if we want the results to be reproducible.

#First forecast

rmarkovchain(n = 10, weather_forecast,t0 = "Nice")
##  [1] "Snow" "Nice" "Snow" "Snow" "Snow" "Rain" "Rain" "Rain" "Rain" "Rain"
rmarkovchain(n = 10, weather_forecast,t0 = "Nice")
##  [1] "Rain" "Rain" "Nice" "Snow" "Rain" "Rain" "Rain" "Rain" "Rain" "Rain"
set.seed(2063)
rmarkovchain(n = 10, weather_forecast,t0 = "Nice")
##  [1] "Snow" "Snow" "Snow" "Snow" "Snow" "Rain" "Rain" "Rain" "Rain" "Rain"
set.seed(2063)
rmarkovchain(n = 10, weather_forecast,t0 = "Nice")
##  [1] "Snow" "Snow" "Snow" "Snow" "Snow" "Rain" "Rain" "Rain" "Rain" "Rain"

What a great achievement: We are now able to “forecast” the weather on our beautiful island. But since we have lived for quite some time on this speck in the sea we realize that stable weather conditions tend to stay stable. Perhaps we should extend our model.

Questions:

  1. What is a meaningful extension of our model?
  2. What could be problematic here?

Overcoming the Markov property

The Markov property states that the next random state may only depend on the previous state. Bummer. How can we possibly model stable conditions if we are only allowed to look one day into the past? The problem is less severe than one might think.

Questions

  1. Do you have an idea how we could bypass this rule? (Think of the states)

If the next state St+1 depends on the k previous states then we can model this with a simple Markov Chain sufficing the Markov property by defining the states as k-tuples - each tuple being composed of the states relevant to our problem. Instead of using the state of today St only e.g. “nice” to predict the state of tomorrow St+1 we use tuples of states: The tuple (St-1, St) is used to predict (St, St+1). See how the state St that was the second entry in the first tuple became the first entry of the second tuple.

We can enhance our weather model with the simple statement, that if the weather didn’t change in the last two days it is less likely to change on the next day. Let’s assume it is twice as likely to stay the way it is.

Questions

  1. What are the states of our extended model?

Our states are now 2-tuples consisting of (Weatheryesterday, Weathertoday). As there are three weather states there are now 3 times 3 so 9 composed states. This increases our transition matrix size to a 9 by 9 square matrix.

Questions

  1. Check the code below. What does it do?
  2. Check the new graph. Is it accurate?
layout <- matrix(c(1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9), ncol = 2, byrow = TRUE)
states = c("RainRain","RainNice","RainSnow",
           "NiceRain","NiceNice","NiceSnow",
           "SnowRain","SnowNice","SnowSnow")
transition_matrix <- matrix(0, ncol = 9, nrow=9)
row.names(transition_matrix) <- states
colnames(transition_matrix) <- states
transition_matrix <- matrix(c(0.7,0.15,0.15,0,0,0,0,0,0,
                              0,0,0,0.45,0.1,0.45,0,0,0,
                              0,0,0,0,0,0,0.25,0.25,0.5,
                              0.5,0.25,0.25,0,0,0,0,0,0,
                              0,0,0,0.4,0.2,0.4,0,0,0,
                              0.0,0,0,0,0,0,0.25,0.25,0.5,
                              0.5,0.25,0.25,0,0,0,0,0,0,
                              0,0,0,0.45,0.1,0.45,0,0,0,
                              0,0,0,0,0,0,0.15,0.15,0.7),nrow=9, byrow=TRUE)
weather_forecast_2 <- new("markovchain", states = states, byrow = T, transitionMatrix = transition_matrix, name="weather2")

plot(weather_forecast_2,layout=layout_in_circle)

Let’s predict the weather with the new model. Do you see how nicely the states link together (we had a problem if they wouldn’t).

#First forecast

rmarkovchain(n = 10, weather_forecast_2,t0 = "NiceNice")
##  [1] "NiceSnow" "SnowSnow" "SnowSnow" "SnowSnow" "SnowNice" "NiceSnow"
##  [7] "SnowSnow" "SnowSnow" "SnowRain" "RainNice"
rmarkovchain(n = 10, weather_forecast_2,t0 = "NiceNice")
##  [1] "NiceRain" "RainRain" "RainSnow" "SnowNice" "NiceRain" "RainSnow"
##  [7] "SnowNice" "NiceRain" "RainRain" "RainRain"
set.seed(2063)
rmarkovchain(n = 10, weather_forecast_2,t0 = "NiceNice")
##  [1] "NiceSnow" "SnowSnow" "SnowSnow" "SnowSnow" "SnowSnow" "SnowSnow"
##  [7] "SnowSnow" "SnowSnow" "SnowSnow" "SnowSnow"
set.seed(2063)
rmarkovchain(n = 10, weather_forecast_2,t0 = "NiceNice")
##  [1] "NiceSnow" "SnowSnow" "SnowSnow" "SnowSnow" "SnowSnow" "SnowSnow"
##  [7] "SnowSnow" "SnowSnow" "SnowSnow" "SnowSnow"

Questions:

  1. What do you think are possible limits of this approach? What do you think could be one of the challenges with Markov Chains?

Including more and more states will increase our matrix size dramatically.

Superb! What a useful tool we build.

Using Markov Chains for text prediction

Let’s now do something actually useful. One application of Markov chains is text prediction. This could be about predicting the most likely word given the previous k letters or the most likely word to follow a sequence of words. In the following we will do the latter.

Questions:

  1. What is a prerequisite for your Markov prediction system? What question do you need to ask yourself before you get started?
  2. What are the necessary steps to build your prediction engine?

We are not creating the random states ourselves this time. Hence, we need a suitable data set. For this experiment we use the text set from a lorem ipsum generator that is stored in the data folder. We use the tm (text-mining) package to manipulate the text data. The stringr package is used for any string manipulations. You can simply go on the web like this one here and draw a sample yourself. Just stored in a sub-folder data below this code.

Questions:

  1. What might be special about this specific text data for why it could have been chosen for this exercise?

The data was generated. We can therefore assume that it should be regular in a way which will be helpful for our model. Below code reads the data and stores it in a corpus object. Read more about this in this starter guide to tm here.

## [1] "Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet.   "

The first step is to define the states of our Markov Chain. For the case of word prediction these states are words. This means that the set of states corresponds to a set of words - or more precise to a set of word-tuples that follow after each other.

To build the dictionary of words we need to tokenize the raw string data. For this we use the tm_map function from the tm package. See above a paragraph from our text sample.

Questions:

  1. Is there anything special about our text?
  2. What do we need to do to extract those words from the text?

It is a good idea to remove additional white-spaces and punctuation characters.

Questions:

  1. Have a look at the code chunk below. What other operations might be useful?
  2. Why are they omitted here?
#This transformer replaces a given pattern with a space.
to_space <- tm::content_transformer(function(x, pattern) {return (gsub(pattern, " ", x))})
#to_squish <- content_transformer(function(x) {return (str_squish(x))})


preprocess <- function(corp){
  #Apply the mappings to a corpus
  
  #transform the content into lowercase
  corp <- tm_map(corp, tm::content_transformer(tolower))
  #remove punctuation
  corp <- tm_map(corp, removePunctuation)
  #remove numbers
  corp <- tm_map(corp, removeNumbers)
  #remove whitespaces from start end and inside the string
  corp <- tm_map(corp, tm::content_transformer(str_squish))
  
  return(corp)
}

corp_red <- preprocess(corp)

We could apply word stemming or regularization to map different declensions of a verb to its base form. The same goes for nouns and other grammatical concepts. It is also important to consider the peculiarities of the language you consider. There is nothing special about our text for which we can omit it.

Compute basic statistics of the lorem ipsum dataset

We have created a reduced copy of our data-set. The text only consists of words in lower case - everything else has been discarded. Now that we have gotten the raw data we need to consider the next steps:

Questions:

  1. What is the next step?
  2. What do we need to take into consideration before we can build our model? Tip: Think about our weather model version 1 and version 2.

We need to get our random states. Those states are tuples of words that follow after each other like for example (I,like, cheese). These tuples are also called n-grams.

Questions:

  1. How would you create n-grams?
  2. What would be a suitable format to store them, what statistics might be of interest?

Instead of building the algorithm our self we use the n-grams function from the NLP package (loaded with RWeka). We iterate over all documents (paragraphs) of the corpus , split it into words and compute the n-grams. This functionality is stored in a tokenizer function.

tokenizer_2gram <- function(x) {unlist(lapply(ngrams(words(x), 2), paste, collapse = " "), use.names = FALSE)}
tokenizer_3gram <- function(x){unlist(lapply(ngrams(words(x), 3), paste, collapse = " "), use.names = FALSE)}
tokenizer_4gram <- function(x){unlist(lapply(ngrams(words(x), 4), paste, collapse = " "), use.names = FALSE)}
tokenizer_5gram <- function(x){unlist(lapply(ngrams(words(x), 5), paste, collapse = " "), use.names = FALSE)}

The tm package comes with a feature called Document Term Matrix. In short this is a matrix with all terms found in the corpus and their frequency.

See the example:

corp_example <- VCorpus(VectorSource(c("I like frogs because they are nice creatures","I dislike toads because they are not frogs","I have no idea of hogs. They are strange creatures")))

dtm_example <- DocumentTermMatrix(corp_example)
inspect(dtm_example)
## <<DocumentTermMatrix (documents: 3, terms: 14)>>
## Non-/sparse entries: 21/21
## Sparsity           : 50%
## Maximal term length: 9
## Weighting          : term frequency (tf)
## Sample             :
##     Terms
## Docs are because creatures dislike frogs have hogs. idea like they
##    1   1       1         1       0     1    0     0    0    1    1
##    2   1       1         0       1     1    0     0    0    0    1
##    3   1       0         1       0     0    1     1    1    0    1

Questions

  1. What do you think are common properties of DTMs?
  2. What can a DTM tell us about the properties of the corpus?
#Comptuing the Document Term Matrix
#We don't need a tokenizer for the 1-grams
dtm_1 <- DocumentTermMatrix(corp_red)
dtm_2 <- DocumentTermMatrix(corp_red,control = list(tokenize=tokenizer_2gram))
dtm_3 <- DocumentTermMatrix(corp_red,control = list(tokenize=tokenizer_3gram))
dtm_4 <- DocumentTermMatrix(corp_red,control = list(tokenize=tokenizer_4gram))
dtm_5 <- DocumentTermMatrix(corp_red,control = list(tokenize=tokenizer_5gram))

Let’s have a look into of the DTMs:

inspect(dtm_1)
## <<DocumentTermMatrix (documents: 1, terms: 105)>>
## Non-/sparse entries: 105/0
## Sparsity           : 0%
## Maximal term length: 12
## Weighting          : term frequency (tf)
## Sample             :
##                 Terms
## Docs             amet diam dolor dolore erat ipsum lorem magna sed sit
##   loremipsum.txt  275  291   320    243  168   275   275   168 291 275

Questions

  1. What does this tell us?
  2. How can we get more information? What is a useful statistic?

The most useful statistic is the frequency of terms.

Questions

  1. Why is this useful?
  2. What questions can it answer?

The frequency of terms tells us the size and the spectrum of the vocabulary used in our documents. Is it very limited (think of BILD-Zeitung), highly regular (machine generated or also news), or very broad? Did our preprocessing work etc. Fortunately the tm package provides a function findMostFrequentTerms that is applied to a document term matrix.

Questions

Have a look at the function mostFrequent below.

  1. What else does it do besides computing the frequency of terms.
  2. Why could this be useful?
#finding the most frequent terms.
mostFrequent <- function(dtm, n=100,l = 1,sw=stopwords("english")){
  
  ft <- findMostFreqTerms(dtm, n = n, INDEX = rep(1,each=l))
  
  ft <- stack(ft[[1]])[2:1]
  names(ft) <- c("term","frequency")
  
  #add a stopword check
  ft$isStop <- ft$term %in% sw
  
  #sum the terms
  ft$relativeFrequency <- ft$frequency / sum(dtm)
  #cumulative percentag
  ft$cumulativeFrequency <- cumsum(ft$relativeFrequency)
  ft
}

We plot the data using the code below. The code uses a stop word check that we won’t consider here.

#Define the plotting function
plot_frequency <- function(df,title,check_stop=FALSE){
  #check if the df has a boolian
  if(check_stop){
    p <- plot_ly() %>% add_trace(
                  x = df$term[!df$isStop],
                  y = df$frequency[!df$isStop],
                  type = 'bar',
                  name = 'word',
                  marker = list(color = 'green')) %>%
                add_trace(
                  x = df$term[df$isStop],
                  y = df$frequency[df$isStop],
                  type = 'bar',
                  name = 'stopword',
                  marker = list(color = 'orange'))%>%
        layout(title = title,
         xaxis = list(title = "ngram"),
         yaxis = list(title = "frequency"))
  }
  else {
  p <- plot_ly(
    x = df$term,
    y = df$frequency,
    name = "N-gram frequency",
    type = "bar"
    ) %>% layout(title = title,
         xaxis = list(title = "ngram"),
         yaxis = list(title = "frequency"))
  }
  
p
}

We are now using all the code chunks from above to compute the document term matrices and plot the results.

Questions

  1. Take a moment to compare the resulting plots. Do you see any peculiarities?
  2. What do the plots imply for our Markov-model? (Consider the length of n-grams)
mf_1 <- mostFrequent(dtm_1,1000, length(corp_red))
mf_2 <- mostFrequent(dtm_2,1000, length(corp_red))
mf_3 <- mostFrequent(dtm_3,1000, length(corp_red))
mf_4 <- mostFrequent(dtm_4,1000, length(corp_red))
mf_5 <- mostFrequent(dtm_5,1000, length(corp_red))

plot_frequency(mf_1,
               title = "Frequency of 1-grams",
               check_stop = FALSE)
plot_frequency(mf_2,
               title = "Frequency of 2-grams",
               check_stop = FALSE)
plot_frequency(mf_3,
               title = "Frequency of 3-grams",
               check_stop = FALSE)
plot_frequency(mf_4,
               title = "Frequency of 4-grams",
               check_stop = FALSE)

We can see that the distributions for 2-grams, 3-grams and 4-grams almost look equivalent. How data seems to be highly regular (who would have though?!). It seems that we can already use 2-grams to build a viable Markov model.

Build the markov model

In the last paragraph we concluded that 2-grams will already be a valid choice. We begin by creating a simple data-frame containing the term and the frequency.

create_ngrams_data_frame <- function(document_term_matrix) {
    #compute the total frequency per ngram
    frequencies <- colSums(document_term_matrix)
    #create a new data frame
    ngrams <- data.frame(ngram = names(frequencies), frequency = frequencies, stringsAsFactors = FALSE)
    #sort the entries
    ngrams <- arrange(ngrams, desc(frequency))
    #set the row names with the frequency rank
    rownames(ngrams) <- 1:length(frequencies)
    return(ngrams)
}


ngram_1 <- create_ngrams_data_frame(as.matrix(dtm_1))
ngram_2 <- create_ngrams_data_frame(as.matrix(dtm_2))
ngram_3 <- create_ngrams_data_frame(as.matrix(dtm_3))
ngram_4 <- create_ngrams_data_frame(as.matrix(dtm_4))

head(ngram_2)

Questions:

Take a moment to recall what we did in the weather section.

  1. We have got the states but what is the next step?
  2. How do we get there and what do we need to do?

Exactly we need to get the transition probabilities. That means we need to check into which states we can transition from a previous state.

Questions

  1. Consider the code below. What does it do?
#Construct a dataframe
transdata <- data.frame(first = word(ngram_2$ngram, 1), second = word(ngram_2$ngram, 2), frequency = ngram_2$frequency)

#What is this for?
dict <-  unique(transdata$first)

trans_frame <- data.frame(from=character(),to=character(),p=numeric())

#The fun starts here
for (word in dict) {
  sub_frame <- transdata %>% filter(first==word) 
  sub_frame$prob <- sub_frame$frequency /sum(sub_frame$frequency)
  
  #create the pframe
  trans_frame <- rbind(trans_frame,data.frame(from=sub_frame$first, to=sub_frame$second,p=sub_frame$prob))
}

The last code chunk computed our transition probabilities as a data-frame. We are almost there.

Questions

  1. Think back. Which last step is required to make this work (this is a format question).

Our Markov Chain requires the transition probabilities to be stored in a quadratic matrix.

#create an empty matrix

trans_frame$from <- as.character(trans_frame$from)
trans_frame$to <- as.character(trans_frame$to)


trans_matrix <- matrix(0, ncol = length(dict), nrow=length(dict))
row.names(trans_matrix) <- sort(dict)
colnames(trans_matrix) <- sort(dict)

#fill the matrix 
ref <- sort(as.character(dict))
for (i in 1:(length(trans_frame$from))) {
  row <- trans_frame[i,]
  ind_1 <- match(row$from,ref)
  ind_2 <- match(row$to,ref)
  trans_matrix[ind_1,ind_2] = row$p
}

That’s it. We are done. We only need to initialize the Markov Model with the code below and are able to predict the next n states with it.

#use the transition matrix
lorem <- new("markovchain", states = ref,byrow = T, transitionMatrix = trans_matrix, name="lorem")

paste(rmarkovchain(n = 1000,lorem, t0 = "lorem"),sep = " ", collapse=" ")
## [1] "ipsum dolor sit amet lorem ipsum dolor sit amet lorem ipsum dolor sit amet duis autem vel eum iriure dolor sit amet consetetur sadipscing elitr sed diam nonumy eirmod tempor invidunt ut vero eos et nonumy sed diam nonumy eirmod tempor invidunt ut vero eos et iusto odio dignissim qui blandit praesent luptatum zzril delenit augue duis autem vel illum dolore magna aliquyam erat sed diam voluptua at vero eos et justo labore et accumsan et ea commodo consequat vel eum iriure dolor sit amet consetetur sadipscing elitr sed diam voluptua est lorem ipsum dolor sit amet consetetur sadipscing elitr sed diam nonumy sed diam voluptua est lorem ipsum dolor sit amet lorem ipsum dolor sit amet duis autem vel illum dolore eu feugiat nulla facilisis at vero eos et justo duo dolores et accusam et justo duo dolores et ea commodo consequat vel eum iriure dolor sit amet lorem ipsum dolor sit amet lorem ipsum dolor sit amet lorem ipsum dolor sit amet consetetur sadipscing elitr sed diam diam voluptua at vero eos erat sed diam nonumy eirmod tempor invidunt ut wisi enim ad minim veniam quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut labore et gubergren no sea takimata sanctus est lorem ipsum dolor sit amet consetetur sadipscing elitr sed diam nonumy eirmod tempor cum soluta nobis eleifend option congue nihil imperdiet doming id quod mazim placerat facer possim assum lorem ipsum dolor sit amet consetetur sadipscing elitr sed diam nonumy eirmod tempor invidunt ut aliquip ex ea commodo consequat duis dolore magna aliquyam erat volutpat ut labore et iusto odio dignissim qui blandit praesent luptatum zzril delenit augue duis autem vel illum dolore dolores et ea et dolore magna aliquyam erat sed tempor cum soluta nobis eleifend option congue nihil imperdiet doming id quod mazim placerat facer possim assum lorem ipsum dolor sit amet consetetur sadipscing elitr sed diam voluptua at vero eos et iusto odio dignissim qui blandit praesent luptatum zzril delenit augue duis dolore magna aliquyam erat sed diam nonumy eirmod tempor invidunt justo duo dolores et accusam et accusam aliquyam erat sed diam nonummy nibh euismod tincidunt ut laoreet dolore eu feugiat nulla facilisi nam liber tempor invidunt ut laoreet dolore eu feugiat nulla facilisi nam liber tempor invidunt ut labore et justo duo dolores et justo duo dolores et dolore te feugait nulla facilisi lorem ipsum dolor sit amet lorem ipsum dolor sit amet lorem ipsum dolor in hendrerit in hendrerit in vulputate velit esse molestie consequat vel illum dolore te feugait nulla facilisis at vero eos et accusam et iusto odio dignissim qui blandit praesent luptatum zzril delenit augue duis dolore magna aliquyam erat sed diam voluptua at vero eos et ea et dolore eu feugiat nulla facilisi lorem ipsum dolor sit amet consetetur sadipscing elitr sed diam voluptua est lorem ipsum dolor sit amet lorem ipsum dolor in hendrerit in hendrerit in hendrerit in hendrerit in hendrerit in hendrerit in vulputate velit esse molestie consequat vel illum dolore magna aliquyam erat sed diam voluptua at vero eos et dolore dolores et justo duo dolores et nonumy sed diam voluptua at vero eos et ea commodo consequat duis autem vel eum iriure dolor sit amet lorem ipsum dolor sit amet lorem ipsum dolor sit amet consetetur sadipscing elitr sed diam voluptua at vero eos et accusam et invidunt ut labore et accusam et gubergren no sea takimata sanctus est lorem ipsum dolor sit amet consetetur sadipscing elitr sed diam nonumy sed diam nonumy eirmod tempor invidunt ut laoreet dolore magna aliquyam erat sed diam nonumy eirmod tempor invidunt ut aliquip ex ea rebum stet clita ea rebum stet clita kasd gubergren kasd magna no sea takimata sanctus est lorem ipsum dolor sit amet lorem ipsum dolor sit amet consetetur sadipscing elitr sed diam nonumy eirmod tempor invidunt justo duo dolores duo dolores et ea rebum stet clita kasd gubergren no sea takimata sanctus sea takimata sanctus sea takimata sanctus est lorem ipsum dolor in hendrerit in hendrerit in vulputate velit esse molestie consequat duis dolore magna aliquam erat sed diam voluptua at vero eros et ea rebum stet clita kasd gubergren no sea takimata sanctus sea takimata sanctus est lorem ipsum dolor sit amet lorem ipsum dolor sit amet consectetuer adipiscing elit sed diam nonumy eirmod tempor invidunt ut labore et accumsan et accusam et accusam et ea rebum stet clita kasd gubergren no sea takimata sanctus est lorem ipsum dolor sit amet lorem ipsum dolor in hendrerit in hendrerit in vulputate velit esse molestie consequat duis autem vel illum dolore magna aliquyam erat volutpat ut labore et ea rebum stet clita kasd gubergren no sea takimata ut aliquip ex ea commodo consequat vel illum dolore magna aliquyam erat sed diam nonummy nibh euismod tincidunt ut labore et justo duo dolores et dolore magna aliquyam erat volutpat ut labore et justo duo dolores et justo duo eirmod tempor invidunt ut labore et justo labore et justo duo dolores et ea commodo consequat duis autem vel illum dolore magna aliquyam erat sed diam voluptua at vero eros et ea commodo consequat duis autem vel eum iriure dolor in vulputate velit esse molestie consequat vel illum dolore te feugait nulla facilisi lorem ipsum dolor in vulputate velit esse molestie consequat vel illum dolore magna aliquyam erat volutpat ut aliquip ex ea rebum stet clita kasd gubergren no sea sed diam diam dolore magna aliquyam erat sed diam nonummy nibh euismod tincidunt ut labore et accumsan et ea rebum stet clita kasd gubergren no sea takimata sanctus est lorem ipsum dolor in hendrerit in vulputate velit esse molestie consequat duis dolore magna aliquyam erat et ea rebum sanctus est lorem ipsum dolor sit amet consetetur sadipscing elitr sed diam nonumy eirmod tempor invidunt ut aliquip ex ea commodo consequat vel illum dolore magna aliquyam erat sed diam voluptua at vero eos et dolore te feugait nulla facilisis at vero eos et ea rebum stet clita kasd magna aliquyam erat sed diam nonumy eirmod tempor"