Updated September 2021

Introduction

This is a brief look at how document similarity, especially cosine similarity, is calculated, how it can be used to compare documents, and the impact of term weighting procedures, including tf-idf.

Within quanteda , the dfm_weight and dfm_tfidf commands provide easy access to various weighting schemes. Within the quanteda ecosystem, the quanteda.textstats package provides easy access to efficient calculation of similarities with its dfm objects. Both of these maintain the computational advantages of the underlying sparse matrix objects. We will also calculate some of these less efficiently "by hand" using dense matrices to show the component steps.

It is worth noting that the quanteda.textstats package provides a variety of other statistics, such as Fleischman readability scores, which I don't discuss here but which you may find of use.

To keep things simple, we'll again use the inaugural speech corpus that comes with quanteda.

If you need to, run this chunk to install quanteda and quanteda.textstats:

# install.packages("quanteda", dependencies = TRUE)
# install.packages("quanteda.textstats", dependencies = TRUE)

Now load them:

library(quanteda)
library(quanteda.textstats)

Lets again load in the corpus of presidential inaugural addresses and see what it looks like:

corp <- quanteda::data_corpus_inaugural
summary(corp)
Corpus consisting of 59 documents, showing 59 documents:

            Text Types Tokens Sentences Year
 1789-Washington   625   1537        23 1789
 1793-Washington    96    147         4 1793
      1797-Adams   826   2577        37 1797
  1801-Jefferson   717   1923        41 1801
  1805-Jefferson   804   2380        45 1805
    1809-Madison   535   1261        21 1809
    1813-Madison   541   1302        33 1813
     1817-Monroe  1040   3677       121 1817
     1821-Monroe  1259   4886       131 1821
      1825-Adams  1003   3147        74 1825
    1829-Jackson   517   1208        25 1829
    1833-Jackson   499   1267        29 1833
   1837-VanBuren  1315   4158        95 1837
   1841-Harrison  1898   9123       210 1841
       1845-Polk  1334   5186       153 1845
     1849-Taylor   496   1178        22 1849
     1853-Pierce  1165   3636       104 1853
   1857-Buchanan   945   3083        89 1857
    1861-Lincoln  1075   3999       135 1861
    1865-Lincoln   360    775        26 1865
      1869-Grant   485   1229        40 1869
      1873-Grant   552   1472        43 1873
      1877-Hayes   831   2707        59 1877
   1881-Garfield  1021   3209       111 1881
  1885-Cleveland   676   1816        44 1885
   1889-Harrison  1352   4721       157 1889
  1893-Cleveland   821   2125        58 1893
   1897-McKinley  1232   4353       130 1897
   1901-McKinley   854   2437       100 1901
  1905-Roosevelt   404   1079        33 1905
       1909-Taft  1437   5821       158 1909
     1913-Wilson   658   1882        68 1913
     1917-Wilson   549   1652        59 1917
    1921-Harding  1169   3719       148 1921
   1925-Coolidge  1220   4440       196 1925
     1929-Hoover  1090   3860       158 1929
  1933-Roosevelt   743   2057        85 1933
  1937-Roosevelt   725   1989        96 1937
  1941-Roosevelt   526   1519        68 1941
  1945-Roosevelt   275    633        27 1945
     1949-Truman   781   2504       116 1949
 1953-Eisenhower   900   2743       119 1953
 1957-Eisenhower   621   1907        92 1957
    1961-Kennedy   566   1541        52 1961
    1965-Johnson   568   1710        93 1965
      1969-Nixon   743   2416       103 1969
      1973-Nixon   544   1995        68 1973
     1977-Carter   527   1369        52 1977
     1981-Reagan   902   2780       129 1981
     1985-Reagan   925   2909       123 1985
       1989-Bush   795   2673       141 1989
    1993-Clinton   642   1833        81 1993
    1997-Clinton   773   2436       111 1997
       2001-Bush   621   1806        97 2001
       2005-Bush   772   2312        99 2005
      2009-Obama   938   2689       110 2009
      2013-Obama   814   2317        88 2013
      2017-Trump   582   1660        88 2017
  2021-Biden.txt   811   2766       216 2021
  President       FirstName                 Party
 Washington          George                  none
 Washington          George                  none
      Adams            John            Federalist
  Jefferson          Thomas Democratic-Republican
  Jefferson          Thomas Democratic-Republican
    Madison           James Democratic-Republican
    Madison           James Democratic-Republican
     Monroe           James Democratic-Republican
     Monroe           James Democratic-Republican
      Adams     John Quincy Democratic-Republican
    Jackson          Andrew            Democratic
    Jackson          Andrew            Democratic
  Van Buren          Martin            Democratic
   Harrison   William Henry                  Whig
       Polk      James Knox                  Whig
     Taylor         Zachary                  Whig
     Pierce        Franklin            Democratic
   Buchanan           James            Democratic
    Lincoln         Abraham            Republican
    Lincoln         Abraham            Republican
      Grant      Ulysses S.            Republican
      Grant      Ulysses S.            Republican
      Hayes   Rutherford B.            Republican
   Garfield        James A.            Republican
  Cleveland          Grover            Democratic
   Harrison        Benjamin            Republican
  Cleveland          Grover            Democratic
   McKinley         William            Republican
   McKinley         William            Republican
  Roosevelt        Theodore            Republican
       Taft  William Howard            Republican
     Wilson         Woodrow            Democratic
     Wilson         Woodrow            Democratic
    Harding       Warren G.            Republican
   Coolidge          Calvin            Republican
     Hoover         Herbert            Republican
  Roosevelt     Franklin D.            Democratic
  Roosevelt     Franklin D.            Democratic
  Roosevelt     Franklin D.            Democratic
  Roosevelt     Franklin D.            Democratic
     Truman        Harry S.            Democratic
 Eisenhower       Dwight D.            Republican
 Eisenhower       Dwight D.            Republican
    Kennedy         John F.            Democratic
    Johnson   Lyndon Baines            Democratic
      Nixon Richard Milhous            Republican
      Nixon Richard Milhous            Republican
     Carter           Jimmy            Democratic
     Reagan          Ronald            Republican
     Reagan          Ronald            Republican
       Bush          George            Republican
    Clinton            Bill            Democratic
    Clinton            Bill            Democratic
       Bush       George W.            Republican
       Bush       George W.            Republican
      Obama          Barack            Democratic
      Obama          Barack            Democratic
      Trump       Donald J.            Republican
      Biden       Joseph R.            Democratic

As before, we can use quanteda's tokens command to tokenize and the dfm command to generate a document-term matrix from this tokens object, e.g.:

inaugural_tokens <- quanteda::tokens(corp,
                       what = "word",
                       remove_punct = TRUE, # default FALSE
                       remove_symbols = TRUE, # default FALSE
                       remove_numbers = FALSE,
                       remove_url = TRUE, # default FALSE
                       remove_separators = TRUE,
                       split_hyphens = FALSE,
                       include_docvars = TRUE,
                       padding = FALSE,
                       verbose = quanteda_options("verbose")
                       )
dtm <- quanteda::dfm(inaugural_tokens,
                                 tolower = TRUE    # casefold
)

The most frequent terms can be seen a couple of ways. One is the textstat_frequency command, which calculates overall (i.e., corpus) frequency and also shows document frequencies (the number of documents in which it appears).

dtm %>%
  textstat_frequency() %>% 
  head(10)
   feature frequency rank docfreq group
1      the     10183    1      59   all
2       of      7180    2      59   all
3      and      5406    3      59   all
4       to      4591    4      59   all
5       in      2827    5      59   all
6        a      2292    6      58   all
7      our      2224    7      58   all
8       we      1827    8      58   all
9     that      1813    9      59   all
10      be      1502   10      59   all

The most frequent terms are essentially the "stop words." Most of these terms are used in every inaugural, although there are exceptions ("a", "our", and "we" are left out of one each).

You can, of course, remove words on a stopwords list and get a more substantive-sounding list of most frequent terms:

inaugural_tokens_nostop <- inaugural_tokens %>%
                            tokens_tolower() %>%
                          tokens_remove(stopwords('en'))
dtm_nostop <- dfm(inaugural_tokens_nostop)
dtm_nostop %>%
  textstat_frequency() %>% 
  head(10)
      feature frequency rank docfreq group
1      people       584    1      57   all
2  government       564    2      52   all
3          us       505    3      56   all
4         can       487    4      56   all
5        must       376    5      52   all
6        upon       371    6      47   all
7       great       344    7      56   all
8         may       343    8      54   all
9      states       334    9      47   all
10      world       319   10      53   all

Document representation and weighting

The variable dtm as calculated above, represents each document as a row of the document-term matrix, with values equal to the raw count of the term indexed by each column.

For example, the 601st to 610th entry in the representation of Obama's 2009 inaugural (document 56) are:

dtm[56,601:610]
Document-feature matrix of: 1 document, 10 features (70.00% sparse) and 4 docvars.
            features
docs         endeavor express high sense entertain
  2009-Obama        0       0    1     0         0
            features
docs         honor reposed america previous
  2009-Obama     1       0       8        0
            features
docs         execution
  2009-Obama         0

Document-incidence matrix

You may for some purposes, wish to represent a document just by the presence or absence of terms. This is sometimes called a document-incidence matrix and often makes sense for a corpus of short documents, like tweets.

dim <- dfm_weight(dtm, scheme="boolean")
dim[56,601:610]
Document-feature matrix of: 1 document, 10 features (70.00% sparse) and 4 docvars.
            features
docs         endeavor express high sense entertain
  2009-Obama        0       0    1     0         0
            features
docs         honor reposed america previous
  2009-Obama     1       0       1        0
            features
docs         execution
  2009-Obama         0

Here, the corpus frequency and document frequency of a given term will be the same.

dim %>%
  textstat_frequency() %>%
  head(10)
   feature frequency rank docfreq group
1       of        59    1      59   all
2      the        59    1      59   all
3      and        59    1      59   all
4       to        59    1      59   all
5     have        59    1      59   all
6     that        59    1      59   all
7       by        59    1      59   all
8       in        59    1      59   all
9       it        59    1      59   all
10      be        59    1      59   all

You can see that the entry for "america" is now simply "1", indicating that the term is present at least once, but not keeping the information that it appears eight times in the speech.

We can think of both the original document-frequency matrix and the document-incidence matrix as "weighted" representations, in which terms are weighted by frequency in the former case, and equally in the latter.

In the document-frequency matrix, the most heavily weighted terms are obviously the most common terms:

dtm %>%
  dfm_subset(subset= docid(dtm)=="2009-Obama") %>%
  textstat_frequency() %>% 
  head(10)
   feature frequency rank docfreq group
1      the       135    1       1   all
2      and       111    2       1   all
3       of        82    3       1   all
4       to        70    4       1   all
5      our        67    5       1   all
6       we        62    6       1   all
7     that        49    7       1   all
8        a        47    8       1   all
9       is        36    9       1   all
10      in        25   10       1   all

In the document-incidence matrix, all terms are weighted equally and the "most frequent" terms list is essentially random (in this case it is the order in which the terms are encountered in the corpus):

dim %>%
  dfm_subset(subset= docid(dim)=="2009-Obama") %>%
  textstat_frequency() %>% 
  head(10)
   feature frequency rank docfreq group
1       of         1    1       1   all
2      the         1    1       1   all
3      and         1    1       1   all
4       to         1    1       1   all
5     life         1    1       1   all
6       no         1    1       1   all
7    could         1    1       1   all
8     have         1    1       1   all
9   filled         1    1       1   all
10    with         1    1       1   all

Term frequency and logged term frequency

For many purposes, it makes sense to transform count data to logged count data. This can be done here with the dfm_weight command as well. Note that \(\log (f_{dw})\) is ill-defined where counts equal zero. Smoothing, or addition of a prior, solves this problem, but at the expense of needing to create a dense matrix. A common approach to maintain sparsity is to calculate either \(\log(1+f_{dw})\), which equals zero when the count equals zero, or \(1+\log(f_{dw})\) only for non-zero values, leaving zero counts as zeros. The "logcount" weighting scheme in the dfm_weight command does the latter. (Note that if a base isn't specified, it assumes base 10, whereas the generic log function would assume natural logarithm, i.e., base=exp(1).)

dtm %>%
  dfm_weight(scheme="logcount",base=exp(1)) %>%
  dfm_subset(subset= docid(dim)=="2009-Obama") %>%
  textstat_frequency() %>% 
  head(10)
   feature frequency rank docfreq group
1      the  5.905275    1       1   all
2      and  5.709530    2       1   all
3       of  5.406719    3       1   all
4       to  5.248495    4       1   all
5      our  5.204693    5       1   all
6       we  5.127134    6       1   all
7     that  4.891820    7       1   all
8        a  4.850148    8       1   all
9       is  4.583519    9       1   all
10      in  4.218876   10       1   all

Document frequency and tf-idf

The most commonly used weighting scheme is tf-idf. The general idea is to take a term frequency or logged term frequency and downweight that according to (logged) document frequency. The intuition is that the most important words are those that are used a lot in a given document but relatively rare in the corpus overall.

Note that many sources allow for a wide variety of interpretations of both "tf" and "idf." In particular, Manning & Schutze are inconsistent about the "default" for "tf", stating \(\log(1+f_{dw})\) in some instances and \(1+\log(f_{dw})\) (for \(f_{dw} > 0\)) in others. The most common implmentation of "df" is \(log\frac{D}{d_w}\), where \(d_w\) is the number of documents in which word \(w\) appears, and \(D\) is the total number of documents. These implementations maintain or even increase sparsity, with zero counts remaining zeros, and new zeros for any words that appear in all documents.

The little run from the Obama speech is then:

dtm.w <- dfm_tfidf(dtm)
dtm.w[56,601:610]
Document-feature matrix of: 1 document, 10 features (70.00% sparse) and 4 docvars.
            features
docs         endeavor express      high sense
  2009-Obama        0       0 0.1910684     0
            features
docs         entertain     honor reposed  america
  2009-Obama         0 0.2523381       0 2.235923
            features
docs         previous execution
  2009-Obama        0         0

The most heavily weighted words in the Obama speech become:

dtm.w %>%
  dfm_subset(subset= docid(dtm)=="2009-Obama") %>%
  textstat_frequency(force=TRUE) %>%
  head(10)
      feature frequency rank docfreq group
1         icy  3.541704    1       1   all
2        jobs  2.978102    2       1   all
3      waters  2.939644    3       1   all
4      storms  2.939644    3       1   all
5  generation  2.702015    5       1   all
6      father  2.603286    6       1   all
7     journey  2.603286    6       1   all
8    traveled  2.587462    8       1   all
9      winter  2.587462    8       1   all
10        you  2.517024   10       1   all
# force=TRUE is needed for quanteda to summarize "frequencies" that have been weighted

You may wish to access the weighted values more directly, without using the textstat_frequency command.

obama_tfidf <- dtm.w %>%
  dfm_subset(subset= docid(dtm)=="2009-Obama") %>%
  as.numeric()
names(obama_tfidf) <- colnames(dtm)
sort(obama_tfidf,dec=T)[1:10]
       icy       jobs     waters     storms 
  3.541704   2.978102   2.939644   2.939644 
generation     father    journey   traveled 
  2.702015   2.603286   2.603286   2.587462 
    winter        you 
  2.587462   2.517024 

Cosine similarity

With quanteda

You can calculate cosine similarity efficiently with the textstat_simil command:

cos_dtm <- textstat_simil(dtm, method="cosine")
dim(cos_dtm)
[1] 59 59

This is a \(D \times D\) symmetric matrix.

You can find the most similar documents to a given document using the given row (or column) of the similarity matrix. For example, the most similar speeches to Kennedy's (1961) inaugural are as follows:

sort(cos_dtm[,"1961-Kennedy"],dec=T)
   1961-Kennedy   1925-Coolidge 1953-Eisenhower 
      1.0000000       0.9341794       0.9335726 
     1969-Nixon  1937-Roosevelt    1997-Clinton 
      0.9234509       0.9220879       0.9205719 
1957-Eisenhower   1889-Harrison  1933-Roosevelt 
      0.9176332       0.9167532       0.9163688 
  1837-VanBuren  1941-Roosevelt     1949-Truman 
      0.9162733       0.9161075       0.9155213 
    1981-Reagan     1985-Reagan     1929-Hoover 
      0.9154402       0.9153323       0.9150125 
   1921-Harding     1853-Pierce  1801-Jefferson 
      0.9139960       0.9132859       0.9124118 
     2009-Obama       1909-Taft   1857-Buchanan 
      0.9115104       0.9095213       0.9084186 
 1905-Roosevelt   1897-McKinley     1817-Monroe 
      0.9052003       0.9046669       0.9040922 
      2005-Bush       1845-Polk      1877-Hayes 
      0.9033540       0.9029782       0.9029498 
    1913-Wilson     1917-Wilson  1893-Cleveland 
      0.9017107       0.9012049       0.9006467 
     1973-Nixon   1901-McKinley   1841-Harrison 
      0.9001845       0.8988335       0.8967638 
   1965-Johnson    1833-Jackson   1881-Garfield 
      0.8947204       0.8941043       0.8933200 
   1809-Madison      1873-Grant     1821-Monroe 
      0.8932276       0.8908578       0.8900598 
 1805-Jefferson    1829-Jackson    1813-Madison 
      0.8898084       0.8890661       0.8889099 
 1885-Cleveland      1825-Adams      2013-Obama 
      0.8870841       0.8866805       0.8865157 
      1989-Bush    1861-Lincoln      1797-Adams 
      0.8859851       0.8850230       0.8835635 
 2021-Biden.txt     1849-Taylor    1993-Clinton 
      0.8799674       0.8782968       0.8770482 
    1977-Carter      1869-Grant  1945-Roosevelt 
      0.8711636       0.8663567       0.8614835 
   1865-Lincoln 1789-Washington       2001-Bush 
      0.8591446       0.8559081       0.8481015 
     2017-Trump 1793-Washington 
      0.8316804       0.7518340 

This doesn't make much sense. Let's see what happens if we use tf-idf.

cos_dtm.w <- textstat_simil(dtm.w, method="cosine")
sort(cos_dtm.w[,"1961-Kennedy"],dec=T)
   1961-Kennedy     1981-Reagan       2005-Bush 
     1.00000000      0.13913142      0.12881338 
     2009-Obama    1993-Clinton      1973-Nixon 
     0.12204132      0.12106314      0.12010097 
1957-Eisenhower 1953-Eisenhower       1989-Bush 
     0.11332337      0.11302037      0.11283880 
     1969-Nixon    1997-Clinton     1985-Reagan 
     0.11090511      0.10903508      0.10842288 
     2013-Obama    1965-Johnson       2001-Bush 
     0.10561653      0.10163961      0.10023038 
 2021-Biden.txt     1977-Carter   1925-Coolidge 
     0.09247814      0.08895975      0.08326778 
    1949-Truman     1853-Pierce   1881-Garfield 
     0.08180853      0.08041863      0.07808556 
    1929-Hoover  1801-Jefferson      2017-Trump 
     0.07759004      0.07758295      0.07561688 
  1841-Harrison  1933-Roosevelt  1941-Roosevelt 
     0.07446879      0.07191991      0.07089801 
 1905-Roosevelt    1921-Harding    1861-Lincoln 
     0.06938615      0.06522225      0.06379865 
  1837-VanBuren     1917-Wilson       1909-Taft 
     0.06353748      0.06256859      0.06071223 
  1857-Buchanan  1937-Roosevelt     1913-Wilson 
     0.06065495      0.05901388      0.05847482 
     1825-Adams      1877-Hayes     1817-Monroe 
     0.05746515      0.05724274      0.05602361 
 1805-Jefferson       1845-Polk     1821-Monroe 
     0.05581724      0.05576344      0.05554536 
  1889-Harrison   1897-McKinley 1789-Washington 
     0.05467709      0.05401196      0.05309571 
 1945-Roosevelt    1813-Madison    1865-Lincoln 
     0.05287510      0.05286289      0.05226755 
     1797-Adams  1885-Cleveland    1833-Jackson 
     0.04893401      0.04764906      0.04674641 
   1829-Jackson   1901-McKinley      1869-Grant 
     0.04560525      0.04557633      0.04063747 
     1873-Grant  1893-Cleveland     1849-Taylor 
     0.04021104      0.03742261      0.03704218 
   1809-Madison 1793-Washington 
     0.03101232      0.01493663 

It's still not completely intuitive -- Kennedy and Reagan don't seem superficially to be similar -- but note that the similarities are greater with every post-war (WWII) president, except Trump, than with any pre-war president. We'll look in more detail at the calculation to determine what's going on.

Cosine similarity step by step

Let's again calculate the cosine similarity between documents using just counts, but this time doing it step by step. First, let's make a regular matrix object out of our dtm. (It's easier to understand what's going on if we make this a "dense" matrix, but it's not something we would normally do.)

dtmat <- as.matrix(dtm)

The L2-norm

Now let's "norm" the documents to length 1 using the \(L_2\) norm. The \(L_2\) norm is the square root of the sum of squares for each document -- the "length" of the document vector, or the "Euclidean distance" of its tip from the origin:

 l2.dtmat <- sqrt(rowSums(dtmat^2))

Now divide the rows by the norm. The row sum of squares should now be one.

dtmat.l2normed <- sweep(dtmat,1,l2.dtmat,"/")
summary(rowSums(dtmat.l2normed^2))

The dot product

To find the cosine similarity between any two, calculate the dot product of these vectors (multiply the two vectors element by element, and then sum those up).

cos.obama1.obama2 <- sum(dtmat.l2normed["2009-Obama",]*dtmat.l2normed["2013-Obama",])
cos.obama1.obama2
[1] 0.9604997
cos.obama1.trump1 <- sum(dtmat.l2normed["2009-Obama",]*dtmat.l2normed["2017-Trump",])
cos.obama1.trump1
[1] 0.9112379

To find the cosine similarity for all pairs, take the matrix crossproduct. (That is, calculate the dot product of every row / document with every other row / document -- this will result in a 58 \(\times\) 58 matrix.) This matrix has all ones on its diagonal -- why? This matrix is symmetric -- why?

cos.dtmat <- dtmat.l2normed %*% t(dtmat.l2normed)
dim(cos.dtmat)
[1] 59 59
sort(cos.dtmat[,"1961-Kennedy"],dec=T)
   1961-Kennedy   1925-Coolidge 1953-Eisenhower 
      1.0000000       0.9341794       0.9335726 
     1969-Nixon  1937-Roosevelt    1997-Clinton 
      0.9234509       0.9220879       0.9205719 
1957-Eisenhower   1889-Harrison  1933-Roosevelt 
      0.9176332       0.9167532       0.9163688 
  1837-VanBuren  1941-Roosevelt     1949-Truman 
      0.9162733       0.9161075       0.9155213 
    1981-Reagan     1985-Reagan     1929-Hoover 
      0.9154402       0.9153323       0.9150125 
   1921-Harding     1853-Pierce  1801-Jefferson 
      0.9139960       0.9132859       0.9124118 
     2009-Obama       1909-Taft   1857-Buchanan 
      0.9115104       0.9095213       0.9084186 
 1905-Roosevelt   1897-McKinley     1817-Monroe 
      0.9052003       0.9046669       0.9040922 
      2005-Bush       1845-Polk      1877-Hayes 
      0.9033540       0.9029782       0.9029498 
    1913-Wilson     1917-Wilson  1893-Cleveland 
      0.9017107       0.9012049       0.9006467 
     1973-Nixon   1901-McKinley   1841-Harrison 
      0.9001845       0.8988335       0.8967638 
   1965-Johnson    1833-Jackson   1881-Garfield 
      0.8947204       0.8941043       0.8933200 
   1809-Madison      1873-Grant     1821-Monroe 
      0.8932276       0.8908578       0.8900598 
 1805-Jefferson    1829-Jackson    1813-Madison 
      0.8898084       0.8890661       0.8889099 
 1885-Cleveland      1825-Adams      2013-Obama 
      0.8870841       0.8866805       0.8865157 
      1989-Bush    1861-Lincoln      1797-Adams 
      0.8859851       0.8850230       0.8835635 
 2021-Biden.txt     1849-Taylor    1993-Clinton 
      0.8799674       0.8782968       0.8770482 
    1977-Carter      1869-Grant  1945-Roosevelt 
      0.8711636       0.8663567       0.8614835 
   1865-Lincoln 1789-Washington       2001-Bush 
      0.8591446       0.8559081       0.8481015 
     2017-Trump 1793-Washington 
      0.8316804       0.7518340 

As we should, we get the same answer for the speeches most similar to the Kennedy inaugural.

Now let's focus on the strangeness. It looks like most inaugurals are relatively similar to one another (.8 + seems like a pretty high number) and it seems odd that Coolidge would be the most similar to Kennedy. Let's break down what words are contributing the most to the similarity rankings by looking at the contributions of individual words to the dot-product:

sort(dtmat.l2normed["1961-Kennedy",]*dtmat.l2normed["1925-Coolidge",], dec=T)[1:20]
        the          of         and          to 
0.323609353 0.193983954 0.086301594 0.083692074 
         we           a          in        that 
0.038061512 0.032193695 0.026614224 0.018742411 
        not         our         but          is 
0.016709580 0.016651911 0.007684389 0.006559844 
        for          be          it         are 
0.006458923 0.005651558 0.005420882 0.004930696 
        can       which         all        this 
0.003373634 0.003128541 0.002984369 0.002941117 

Ahhhh! The cosine similarity is being driven by the relative use of common words ... the, of, and, to, and so on. This is arguably what we want in some applications like stylometry, where we are trying to guess authorship for example, but almost definitely not what we're after here.

Let's look instead at the tf-idf cosine similarities.

dtmat.w <- as.matrix(dtm.w)
l2.dtmat.w <- sqrt(rowSums(dtmat.w^2))
dtmat.w.l2normed <- sweep(dtmat.w,1,l2.dtmat.w,"/")
cos.dtmat.w <- dtmat.w.l2normed %*% t(dtmat.w.l2normed)
dim(cos.dtmat.w)
[1] 59 59
sort(cos.dtmat.w[,"1961-Kennedy"],dec=T)
   1961-Kennedy     1981-Reagan       2005-Bush 
     1.00000000      0.13913142      0.12881338 
     2009-Obama    1993-Clinton      1973-Nixon 
     0.12204132      0.12106314      0.12010097 
1957-Eisenhower 1953-Eisenhower       1989-Bush 
     0.11332337      0.11302037      0.11283880 
     1969-Nixon    1997-Clinton     1985-Reagan 
     0.11090511      0.10903508      0.10842288 
     2013-Obama    1965-Johnson       2001-Bush 
     0.10561653      0.10163961      0.10023038 
 2021-Biden.txt     1977-Carter   1925-Coolidge 
     0.09247814      0.08895975      0.08326778 
    1949-Truman     1853-Pierce   1881-Garfield 
     0.08180853      0.08041863      0.07808556 
    1929-Hoover  1801-Jefferson      2017-Trump 
     0.07759004      0.07758295      0.07561688 
  1841-Harrison  1933-Roosevelt  1941-Roosevelt 
     0.07446879      0.07191991      0.07089801 
 1905-Roosevelt    1921-Harding    1861-Lincoln 
     0.06938615      0.06522225      0.06379865 
  1837-VanBuren     1917-Wilson       1909-Taft 
     0.06353748      0.06256859      0.06071223 
  1857-Buchanan  1937-Roosevelt     1913-Wilson 
     0.06065495      0.05901388      0.05847482 
     1825-Adams      1877-Hayes     1817-Monroe 
     0.05746515      0.05724274      0.05602361 
 1805-Jefferson       1845-Polk     1821-Monroe 
     0.05581724      0.05576344      0.05554536 
  1889-Harrison   1897-McKinley 1789-Washington 
     0.05467709      0.05401196      0.05309571 
 1945-Roosevelt    1813-Madison    1865-Lincoln 
     0.05287510      0.05286289      0.05226755 
     1797-Adams  1885-Cleveland    1833-Jackson 
     0.04893401      0.04764906      0.04674641 
   1829-Jackson   1901-McKinley      1869-Grant 
     0.04560525      0.04557633      0.04063747 
     1873-Grant  1893-Cleveland     1849-Taylor 
     0.04021104      0.03742261      0.03704218 
   1809-Madison 1793-Washington 
     0.03101232      0.01493663 

Same answer as before. Similarities are lower, but they reflect similarity among distinctive content. That is, they are similar in what makes them different from the others. So, why is Reagan the most similar to Kennedy?

sort(dtmat.w.l2normed["1961-Kennedy",]*dtmat.w.l2normed["1981-Reagan",], dec=T)[1:20]
      begin   americans       sides     loyalty 
0.008795749 0.007535292 0.006083563 0.004495064 
      deeds   negotiate         let         you 
0.003817306 0.003817306 0.003538579 0.003354278 
         mr        help        back        prey 
0.003273326 0.003020558 0.002930115 0.002463591 
  unleashed      burden       price        your 
0.002463591 0.002420332 0.001968381 0.001932147 
   cultural     special        vice     freedom 
0.001908653 0.001780228 0.001780228 0.001679748 

This suggests they both framed their presidencies as an opportunity to "begin" something new, for example, and were relatively unusual in doing so.

kwic(inaugural_tokens,"begin", window=4)
Keyword-in-context with 12 matches.                                               
 [1953-Eisenhower, 5]     My friends before I |
  [1961-Kennedy, 665] request that both sides |
  [1961-Kennedy, 773]           war So let us |
 [1961-Kennedy, 1009]       planet But let us |
   [1981-Reagan, 395]         we are going to |
   [1981-Reagan, 761]          world So as we |
  [1981-Reagan, 1137]      our command let us |
  [1985-Reagan, 1381]      budget We can then |
 [1993-Clinton, 1510]     21st Century let us |
      [2001-Bush, 37]     new beginnings As I |
    [2009-Obama, 722]  dust ourselves off and |
   [2009-Obama, 1376] between nations We will |
                                   
 begin | the expression of those   
 begin | anew the quest for        
 begin | anew remembering on both  
 begin | In your hands my          
 begin | to act beginning today    
 begin | let us take inventory     
 begin | an era of national        
 begin | reducing the national debt
 begin | anew with energy and      
 begin | I thank President Clinton 
 begin | again the work of         
 begin | to responsibly leave Iraq 

PMI, Fightin' Words, and "keyness" approaches to weighting

Finally, I will note that an alternative approach to tf-idf weighting is to represent each document by a vector of "keyness" statistics. The textstat_keyness command provides several, such as chi-squared and PMI (pointwise mutual information). I personally often use the "Fightin' Words" statistic (zeta), calculated with each document as a "group" to be compared to the others. In this example, this gives results that are correlated with tf-idf, but with some minor qualitative differences.

LS0tCnRpdGxlOiAiVGVybSBXZWlnaHRpbmcgKGluY2x1ZGluZyB0Zi1pZGYpIGFuZCBDb3NpbmUgU2ltaWxhcml0eSIKc3VidGl0bGU6ICJQTFNDIDU5NywgVGV4dCBhcyBEYXRhLCBQZW5uIFN0YXRlIgphdXRob3I6ICJCdXJ0IEwuIE1vbnJvZSIKb3V0cHV0OgogIGh0bWxfZG9jdW1lbnQ6CiAgICB0b2M6IHllcwogICAgZGZfcHJpbnQ6IHBhZ2VkCiAgaHRtbF9ub3RlYm9vazoKICAgIGNvZGVfZm9sZGluZzogc2hvdwogICAgaGlnaGxpZ2h0OiB0YW5nbwogICAgdGhlbWU6IHVuaXRlZAogICAgdG9jOiB5ZXMKICAgIGRmX3ByaW50OiBwYWdlZAotLS0KVXBkYXRlZCBTZXB0ZW1iZXIgMjAyMQoKIyBJbnRyb2R1Y3Rpb24KClRoaXMgaXMgYSBicmllZiBsb29rIGF0IGhvdyBkb2N1bWVudCBzaW1pbGFyaXR5LCBlc3BlY2lhbGx5IGNvc2luZSBzaW1pbGFyaXR5LCBpcyBjYWxjdWxhdGVkLCBob3cgaXQgY2FuIGJlIHVzZWQgdG8gY29tcGFyZSBkb2N1bWVudHMsIGFuZCB0aGUgaW1wYWN0IG9mIHRlcm0gd2VpZ2h0aW5nIHByb2NlZHVyZXMsIGluY2x1ZGluZyB0Zi1pZGYuCgpXaXRoaW4gIGBxdWFudGVkYWAgLCB0aGUgYGRmbV93ZWlnaHRgIGFuZCBgZGZtX3RmaWRmYCBjb21tYW5kcyBwcm92aWRlIGVhc3kgYWNjZXNzIHRvIHZhcmlvdXMgd2VpZ2h0aW5nIHNjaGVtZXMuIFdpdGhpbiB0aGUgYHF1YW50ZWRhYCBlY29zeXN0ZW0sIHRoZSBgcXVhbnRlZGEudGV4dHN0YXRzYCBwYWNrYWdlIHByb3ZpZGVzIGVhc3kgYWNjZXNzIHRvIGVmZmljaWVudCBjYWxjdWxhdGlvbiBvZiBzaW1pbGFyaXRpZXMgd2l0aCBpdHMgYGRmbWAgb2JqZWN0cy4gQm90aCBvZiB0aGVzZSBtYWludGFpbiB0aGUgY29tcHV0YXRpb25hbCBhZHZhbnRhZ2VzIG9mIHRoZSB1bmRlcmx5aW5nIHNwYXJzZSBtYXRyaXggb2JqZWN0cy4gV2Ugd2lsbCBhbHNvIGNhbGN1bGF0ZSBzb21lIG9mIHRoZXNlIGxlc3MgZWZmaWNpZW50bHkgImJ5IGhhbmQiIHVzaW5nIGRlbnNlIG1hdHJpY2VzIHRvIHNob3cgdGhlIGNvbXBvbmVudCBzdGVwcy4KCkl0IGlzIHdvcnRoIG5vdGluZyB0aGF0IHRoZSBgcXVhbnRlZGEudGV4dHN0YXRzYCBwYWNrYWdlIHByb3ZpZGVzIGEgdmFyaWV0eSBvZiBvdGhlciBzdGF0aXN0aWNzLCBzdWNoIGFzIEZsZWlzY2htYW4gcmVhZGFiaWxpdHkgc2NvcmVzLCB3aGljaCBJIGRvbid0IGRpc2N1c3MgaGVyZSBidXQgd2hpY2ggeW91IG1heSBmaW5kIG9mIHVzZS4KClRvIGtlZXAgdGhpbmdzIHNpbXBsZSwgd2UnbGwgYWdhaW4gdXNlIHRoZSBpbmF1Z3VyYWwgc3BlZWNoIGNvcnB1cyB0aGF0IGNvbWVzIHdpdGggYHF1YW50ZWRhYC4KCklmIHlvdSBuZWVkIHRvLCBydW4gdGhpcyBjaHVuayB0byBpbnN0YWxsIGBxdWFudGVkYWAgYW5kIGBxdWFudGVkYS50ZXh0c3RhdHNgOgoKYGBge3J9CiMgaW5zdGFsbC5wYWNrYWdlcygicXVhbnRlZGEiLCBkZXBlbmRlbmNpZXMgPSBUUlVFKQojIGluc3RhbGwucGFja2FnZXMoInF1YW50ZWRhLnRleHRzdGF0cyIsIGRlcGVuZGVuY2llcyA9IFRSVUUpCmBgYAoKTm93IGxvYWQgdGhlbToKYGBge3J9CmxpYnJhcnkocXVhbnRlZGEpCmxpYnJhcnkocXVhbnRlZGEudGV4dHN0YXRzKQpgYGAKCkxldHMgYWdhaW4gbG9hZCBpbiB0aGUgY29ycHVzIG9mIHByZXNpZGVudGlhbCBpbmF1Z3VyYWwgYWRkcmVzc2VzIGFuZCBzZWUgd2hhdCBpdCBsb29rcyBsaWtlOgoKYGBge3J9CmNvcnAgPC0gcXVhbnRlZGE6OmRhdGFfY29ycHVzX2luYXVndXJhbAoKc3VtbWFyeShjb3JwKQpgYGAKCkFzIGJlZm9yZSwgd2UgY2FuIHVzZSBxdWFudGVkYSdzIGB0b2tlbnNgIGNvbW1hbmQgdG8gdG9rZW5pemUgYW5kIHRoZSBgZGZtYCBjb21tYW5kIHRvIGdlbmVyYXRlIGEgZG9jdW1lbnQtdGVybSBtYXRyaXggZnJvbSB0aGlzIHRva2VucyBvYmplY3QsIGUuZy46CgpgYGB7cn0KaW5hdWd1cmFsX3Rva2VucyA8LSBxdWFudGVkYTo6dG9rZW5zKGNvcnAsCiAgICAgICAgICAgICAgICAgICAgICAgd2hhdCA9ICJ3b3JkIiwKICAgICAgICAgICAgICAgICAgICAgICByZW1vdmVfcHVuY3QgPSBUUlVFLCAjIGRlZmF1bHQgRkFMU0UKICAgICAgICAgICAgICAgICAgICAgICByZW1vdmVfc3ltYm9scyA9IFRSVUUsICMgZGVmYXVsdCBGQUxTRQogICAgICAgICAgICAgICAgICAgICAgIHJlbW92ZV9udW1iZXJzID0gRkFMU0UsCiAgICAgICAgICAgICAgICAgICAgICAgcmVtb3ZlX3VybCA9IFRSVUUsICMgZGVmYXVsdCBGQUxTRQogICAgICAgICAgICAgICAgICAgICAgIHJlbW92ZV9zZXBhcmF0b3JzID0gVFJVRSwKICAgICAgICAgICAgICAgICAgICAgICBzcGxpdF9oeXBoZW5zID0gRkFMU0UsCiAgICAgICAgICAgICAgICAgICAgICAgaW5jbHVkZV9kb2N2YXJzID0gVFJVRSwKICAgICAgICAgICAgICAgICAgICAgICBwYWRkaW5nID0gRkFMU0UsCiAgICAgICAgICAgICAgICAgICAgICAgdmVyYm9zZSA9IHF1YW50ZWRhX29wdGlvbnMoInZlcmJvc2UiKQogICAgICAgICAgICAgICAgICAgICAgICkKCmR0bSA8LSBxdWFudGVkYTo6ZGZtKGluYXVndXJhbF90b2tlbnMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHRvbG93ZXIgPSBUUlVFICAgICMgY2FzZWZvbGQKKQpgYGAKClRoZSBtb3N0IGZyZXF1ZW50IHRlcm1zIGNhbiBiZSBzZWVuIGEgY291cGxlIG9mIHdheXMuIE9uZSBpcyB0aGUgYHRleHRzdGF0X2ZyZXF1ZW5jeWAgY29tbWFuZCwgd2hpY2ggY2FsY3VsYXRlcyBvdmVyYWxsIChpLmUuLCBjb3JwdXMpIGZyZXF1ZW5jeSBhbmQgYWxzbyBzaG93cyBkb2N1bWVudCBmcmVxdWVuY2llcyAodGhlIG51bWJlciBvZiBkb2N1bWVudHMgaW4gd2hpY2ggaXQgYXBwZWFycykuCgpgYGB7cn0KZHRtICU+JQogIHRleHRzdGF0X2ZyZXF1ZW5jeSgpICU+JSAKICBoZWFkKDEwKQpgYGAKClRoZSBtb3N0IGZyZXF1ZW50IHRlcm1zIGFyZSBlc3NlbnRpYWxseSB0aGUgCiJzdG9wIHdvcmRzLiIgTW9zdCBvZiB0aGVzZSB0ZXJtcyBhcmUgdXNlZCBpbiBldmVyeSBpbmF1Z3VyYWwsIGFsdGhvdWdoIHRoZXJlIGFyZSBleGNlcHRpb25zICgiYSIsICJvdXIiLCBhbmQgIndlIiBhcmUgbGVmdCBvdXQgb2Ygb25lIGVhY2gpLgoKWW91IGNhbiwgb2YgY291cnNlLCByZW1vdmUgd29yZHMgb24gYSBzdG9wd29yZHMgbGlzdCBhbmQgZ2V0IGEgbW9yZSBzdWJzdGFudGl2ZS1zb3VuZGluZyBsaXN0IG9mIG1vc3QgZnJlcXVlbnQgdGVybXM6CgpgYGB7cn0KaW5hdWd1cmFsX3Rva2Vuc19ub3N0b3AgPC0gaW5hdWd1cmFsX3Rva2VucyAlPiUKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHRva2Vuc190b2xvd2VyKCkgJT4lCiAgICAgICAgICAgICAgICAgICAgICAgICAgdG9rZW5zX3JlbW92ZShzdG9wd29yZHMoJ2VuJykpCmR0bV9ub3N0b3AgPC0gZGZtKGluYXVndXJhbF90b2tlbnNfbm9zdG9wKQoKZHRtX25vc3RvcCAlPiUKICB0ZXh0c3RhdF9mcmVxdWVuY3koKSAlPiUgCiAgaGVhZCgxMCkKYGBgCgoKIyBEb2N1bWVudCByZXByZXNlbnRhdGlvbiBhbmQgd2VpZ2h0aW5nCgpUaGUgdmFyaWFibGUgYGR0bWAgYXMgY2FsY3VsYXRlZCBhYm92ZSwgcmVwcmVzZW50cyBlYWNoIGRvY3VtZW50IGFzIGEgcm93IG9mIHRoZSBkb2N1bWVudC10ZXJtIG1hdHJpeCwgd2l0aCB2YWx1ZXMgZXF1YWwgdG8gdGhlIHJhdyBjb3VudCBvZiB0aGUgdGVybSBpbmRleGVkIGJ5IGVhY2ggY29sdW1uLgoKRm9yIGV4YW1wbGUsIHRoZSA2MDFzdCB0byA2MTB0aCBlbnRyeSBpbiB0aGUgcmVwcmVzZW50YXRpb24gb2YgT2JhbWEncyAyMDA5IGluYXVndXJhbCAoZG9jdW1lbnQgNTYpIGFyZToKCmBgYHtyfQpkdG1bNTYsNjAxOjYxMF0KYGBgCgojIyBEb2N1bWVudC1pbmNpZGVuY2UgbWF0cml4CgpZb3UgbWF5IGZvciBzb21lIHB1cnBvc2VzLCB3aXNoIHRvIHJlcHJlc2VudCBhIGRvY3VtZW50IGp1c3QgYnkgdGhlIHByZXNlbmNlIG9yIGFic2VuY2Ugb2YgdGVybXMuIFRoaXMgaXMgc29tZXRpbWVzIGNhbGxlZCBhICoqZG9jdW1lbnQtaW5jaWRlbmNlIG1hdHJpeCoqIGFuZCBvZnRlbiBtYWtlcyBzZW5zZSBmb3IgYSBjb3JwdXMgb2Ygc2hvcnQgZG9jdW1lbnRzLCBsaWtlIHR3ZWV0cy4gCgpgYGB7cn0KZGltIDwtIGRmbV93ZWlnaHQoZHRtLCBzY2hlbWU9ImJvb2xlYW4iKQpkaW1bNTYsNjAxOjYxMF0KYGBgCgpIZXJlLCB0aGUgY29ycHVzIGZyZXF1ZW5jeSBhbmQgZG9jdW1lbnQgZnJlcXVlbmN5IG9mIGEgZ2l2ZW4gdGVybSB3aWxsIGJlIHRoZSBzYW1lLgoKYGBge3J9CmRpbSAlPiUKICB0ZXh0c3RhdF9mcmVxdWVuY3koKSAlPiUKICBoZWFkKDEwKQpgYGAKICAKWW91IGNhbiBzZWUgdGhhdCB0aGUgZW50cnkgZm9yICJhbWVyaWNhIiBpcyBub3cgc2ltcGx5ICIxIiwgaW5kaWNhdGluZyB0aGF0IHRoZSB0ZXJtIGlzIHByZXNlbnQgYXQgbGVhc3Qgb25jZSwgYnV0IG5vdCBrZWVwaW5nIHRoZSBpbmZvcm1hdGlvbiB0aGF0IGl0IGFwcGVhcnMgZWlnaHQgdGltZXMgaW4gdGhlIHNwZWVjaC4KCldlIGNhbiB0aGluayBvZiBib3RoIHRoZSBvcmlnaW5hbCBkb2N1bWVudC1mcmVxdWVuY3kgbWF0cml4IGFuZCB0aGUgZG9jdW1lbnQtaW5jaWRlbmNlIG1hdHJpeCBhcyAid2VpZ2h0ZWQiIHJlcHJlc2VudGF0aW9ucywgaW4gd2hpY2ggdGVybXMgYXJlIHdlaWdodGVkIGJ5IGZyZXF1ZW5jeSBpbiB0aGUgZm9ybWVyIGNhc2UsIGFuZCBlcXVhbGx5IGluIHRoZSBsYXR0ZXIuCgpJbiB0aGUgZG9jdW1lbnQtZnJlcXVlbmN5IG1hdHJpeCwgdGhlIG1vc3QgaGVhdmlseSB3ZWlnaHRlZCB0ZXJtcyBhcmUgb2J2aW91c2x5IHRoZSBtb3N0IGNvbW1vbiB0ZXJtczoKCmBgYHtyfQpkdG0gJT4lCiAgZGZtX3N1YnNldChzdWJzZXQ9IGRvY2lkKGR0bSk9PSIyMDA5LU9iYW1hIikgJT4lCiAgdGV4dHN0YXRfZnJlcXVlbmN5KCkgJT4lIAogIGhlYWQoMTApCmBgYAoKSW4gdGhlIGRvY3VtZW50LWluY2lkZW5jZSBtYXRyaXgsIGFsbCB0ZXJtcyBhcmUgd2VpZ2h0ZWQgZXF1YWxseSBhbmQgdGhlICJtb3N0IGZyZXF1ZW50IiB0ZXJtcyBsaXN0IGlzIGVzc2VudGlhbGx5IHJhbmRvbSAoaW4gdGhpcyBjYXNlIGl0IGlzIHRoZSBvcmRlciBpbiB3aGljaCB0aGUgdGVybXMgYXJlIGVuY291bnRlcmVkIGluIHRoZSBjb3JwdXMpOgoKYGBge3J9CmRpbSAlPiUKICBkZm1fc3Vic2V0KHN1YnNldD0gZG9jaWQoZGltKT09IjIwMDktT2JhbWEiKSAlPiUKICB0ZXh0c3RhdF9mcmVxdWVuY3koKSAlPiUgCiAgaGVhZCgxMCkKYGBgCgojIyBUZXJtIGZyZXF1ZW5jeSBhbmQgbG9nZ2VkIHRlcm0gZnJlcXVlbmN5CgpGb3IgbWFueSBwdXJwb3NlcywgaXQgbWFrZXMgc2Vuc2UgdG8gdHJhbnNmb3JtIGNvdW50IGRhdGEgdG8gbG9nZ2VkIGNvdW50IGRhdGEuIFRoaXMgY2FuIGJlIGRvbmUgaGVyZSB3aXRoIHRoZSBkZm1fd2VpZ2h0IGNvbW1hbmQgYXMgd2VsbC4gTm90ZSB0aGF0ICRcbG9nIChmX3tkd30pJCBpcyBpbGwtZGVmaW5lZCB3aGVyZSBjb3VudHMgZXF1YWwgemVyby4gU21vb3RoaW5nLCBvciBhZGRpdGlvbiBvZiBhIHByaW9yLCBzb2x2ZXMgdGhpcyBwcm9ibGVtLCBidXQgYXQgdGhlIGV4cGVuc2Ugb2YgbmVlZGluZyB0byBjcmVhdGUgYSBkZW5zZSBtYXRyaXguIEEgY29tbW9uIGFwcHJvYWNoIHRvIG1haW50YWluIHNwYXJzaXR5IGlzIHRvIGNhbGN1bGF0ZSBlaXRoZXIgJFxsb2coMStmX3tkd30pJCwgd2hpY2ggZXF1YWxzIHplcm8gd2hlbiB0aGUgY291bnQgZXF1YWxzIHplcm8sIG9yICQxK1xsb2coZl97ZHd9KSQgKm9ubHkgZm9yIG5vbi16ZXJvIHZhbHVlcyosIGxlYXZpbmcgemVybyBjb3VudHMgYXMgemVyb3MuIFRoZSAibG9nY291bnQiIHdlaWdodGluZyBzY2hlbWUgaW4gdGhlIGBkZm1fd2VpZ2h0YCBjb21tYW5kIGRvZXMgdGhlIGxhdHRlci4gKE5vdGUgdGhhdCBpZiBhIGJhc2UgaXNuJ3Qgc3BlY2lmaWVkLCBpdCBhc3N1bWVzIGJhc2UgMTAsIHdoZXJlYXMgdGhlIGdlbmVyaWMgYGxvZ2AgZnVuY3Rpb24gd291bGQgYXNzdW1lIG5hdHVyYWwgbG9nYXJpdGhtLCBpLmUuLCBgYmFzZT1leHAoMSlgLikKCmBgYHtyfQpkdG0gJT4lCiAgZGZtX3dlaWdodChzY2hlbWU9ImxvZ2NvdW50IixiYXNlPWV4cCgxKSkgJT4lCiAgZGZtX3N1YnNldChzdWJzZXQ9IGRvY2lkKGRpbSk9PSIyMDA5LU9iYW1hIikgJT4lCiAgdGV4dHN0YXRfZnJlcXVlbmN5KCkgJT4lIAogIGhlYWQoMTApCmBgYAoKIyMgRG9jdW1lbnQgZnJlcXVlbmN5IGFuZCB0Zi1pZGYKClRoZSBtb3N0IGNvbW1vbmx5IHVzZWQgd2VpZ2h0aW5nIHNjaGVtZSBpcyAqKnRmLWlkZioqLiBUaGUgZ2VuZXJhbCBpZGVhIGlzIHRvIHRha2UgYSB0ZXJtIGZyZXF1ZW5jeSBvciBsb2dnZWQgdGVybSBmcmVxdWVuY3kgYW5kICpkb3dud2VpZ2h0KiB0aGF0IGFjY29yZGluZyB0byAobG9nZ2VkKSBkb2N1bWVudCBmcmVxdWVuY3kuIFRoZSBpbnR1aXRpb24gaXMgdGhhdCB0aGUgbW9zdCBpbXBvcnRhbnQgd29yZHMgYXJlIHRob3NlIHRoYXQgYXJlIHVzZWQgYSBsb3QgaW4gYSBnaXZlbiBkb2N1bWVudCBidXQgcmVsYXRpdmVseSByYXJlIGluIHRoZSBjb3JwdXMgb3ZlcmFsbC4KCk5vdGUgdGhhdCBtYW55IHNvdXJjZXMgYWxsb3cgZm9yIGEgd2lkZSB2YXJpZXR5IG9mIGludGVycHJldGF0aW9ucyBvZiBib3RoICJ0ZiIgYW5kICJpZGYuIiBJbiBwYXJ0aWN1bGFyLCBNYW5uaW5nICYgU2NodXR6ZSAgYXJlIGluY29uc2lzdGVudCBhYm91dCB0aGUgImRlZmF1bHQiIGZvciAidGYiLCBzdGF0aW5nICRcbG9nKDErZl97ZHd9KSQgaW4gc29tZSBpbnN0YW5jZXMgYW5kICQxK1xsb2coZl97ZHd9KSQgKGZvciAkZl97ZHd9ID4gMCQpIGluIG90aGVycy4gVGhlIG1vc3QgY29tbW9uIGltcGxtZW50YXRpb24gb2YgImRmIiBpcyAkbG9nXGZyYWN7RH17ZF93fSQsIHdoZXJlICRkX3ckIGlzIHRoZSBudW1iZXIgb2YgZG9jdW1lbnRzIGluIHdoaWNoIHdvcmQgJHckIGFwcGVhcnMsIGFuZCAkRCQgaXMgdGhlIHRvdGFsIG51bWJlciBvZiBkb2N1bWVudHMuIFRoZXNlIGltcGxlbWVudGF0aW9ucyBtYWludGFpbiBvciBldmVuIGluY3JlYXNlIHNwYXJzaXR5LCB3aXRoIHplcm8gY291bnRzIHJlbWFpbmluZyB6ZXJvcywgYW5kIG5ldyB6ZXJvcyBmb3IgYW55IHdvcmRzIHRoYXQgYXBwZWFyIGluIGFsbCBkb2N1bWVudHMuCgpUaGUgbGl0dGxlIHJ1biBmcm9tIHRoZSBPYmFtYSBzcGVlY2ggaXMgdGhlbjoKYGBge3J9CmR0bS53IDwtIGRmbV90ZmlkZihkdG0pCmR0bS53WzU2LDYwMTo2MTBdCmBgYAoKVGhlIG1vc3QgaGVhdmlseSB3ZWlnaHRlZCB3b3JkcyBpbiB0aGUgT2JhbWEgc3BlZWNoIGJlY29tZToKCmBgYHtyfQpkdG0udyAlPiUKICBkZm1fc3Vic2V0KHN1YnNldD0gZG9jaWQoZHRtKT09IjIwMDktT2JhbWEiKSAlPiUKICB0ZXh0c3RhdF9mcmVxdWVuY3koZm9yY2U9VFJVRSkgJT4lCiAgaGVhZCgxMCkKCiMgZm9yY2U9VFJVRSBpcyBuZWVkZWQgZm9yIHF1YW50ZWRhIHRvIHN1bW1hcml6ZSAiZnJlcXVlbmNpZXMiIHRoYXQgaGF2ZSBiZWVuIHdlaWdodGVkCmBgYAoKWW91IG1heSB3aXNoIHRvIGFjY2VzcyB0aGUgd2VpZ2h0ZWQgdmFsdWVzIG1vcmUgZGlyZWN0bHksIHdpdGhvdXQgdXNpbmcgdGhlIGB0ZXh0c3RhdF9mcmVxdWVuY3lgIGNvbW1hbmQuCmBgYHtyfQpvYmFtYV90ZmlkZiA8LSBkdG0udyAlPiUKICBkZm1fc3Vic2V0KHN1YnNldD0gZG9jaWQoZHRtKT09IjIwMDktT2JhbWEiKSAlPiUKICBhcy5udW1lcmljKCkKbmFtZXMob2JhbWFfdGZpZGYpIDwtIGNvbG5hbWVzKGR0bSkKCnNvcnQob2JhbWFfdGZpZGYsZGVjPVQpWzE6MTBdCmBgYAoKIyBDb3NpbmUgc2ltaWxhcml0eQoKIyMgV2l0aCBxdWFudGVkYQoKWW91IGNhbiBjYWxjdWxhdGUgY29zaW5lIHNpbWlsYXJpdHkgZWZmaWNpZW50bHkgd2l0aCB0aGUgYHRleHRzdGF0X3NpbWlsYCBjb21tYW5kOgoKYGBge3J9CmNvc19kdG0gPC0gdGV4dHN0YXRfc2ltaWwoZHRtLCBtZXRob2Q9ImNvc2luZSIpCmRpbShjb3NfZHRtKQpgYGAKClRoaXMgaXMgYSAkRCBcdGltZXMgRCQgc3ltbWV0cmljIG1hdHJpeC4KCllvdSBjYW4gZmluZCB0aGUgbW9zdCBzaW1pbGFyIGRvY3VtZW50cyB0byBhIGdpdmVuIGRvY3VtZW50IHVzaW5nIHRoZSBnaXZlbiByb3cgKG9yIGNvbHVtbikgb2YgdGhlIHNpbWlsYXJpdHkgbWF0cml4LiBGb3IgZXhhbXBsZSwgdGhlIG1vc3Qgc2ltaWxhciBzcGVlY2hlcyB0byBLZW5uZWR5J3MgKDE5NjEpIGluYXVndXJhbCBhcmUgYXMgZm9sbG93czoKCmBgYHtyfQpzb3J0KGNvc19kdG1bLCIxOTYxLUtlbm5lZHkiXSxkZWM9VCkKYGBgCgpUaGlzIGRvZXNuJ3QgbWFrZSBtdWNoIHNlbnNlLiBMZXQncyBzZWUgd2hhdCBoYXBwZW5zIGlmIHdlIHVzZSB0Zi1pZGYuCgpgYGB7cn0KY29zX2R0bS53IDwtIHRleHRzdGF0X3NpbWlsKGR0bS53LCBtZXRob2Q9ImNvc2luZSIpCnNvcnQoY29zX2R0bS53WywiMTk2MS1LZW5uZWR5Il0sZGVjPVQpCmBgYAoKSXQncyBzdGlsbCBub3QgY29tcGxldGVseSBpbnR1aXRpdmUgLS0gS2VubmVkeSBhbmQgUmVhZ2FuIGRvbid0IHNlZW0gc3VwZXJmaWNpYWxseSB0byBiZSBzaW1pbGFyIC0tIGJ1dCBub3RlIHRoYXQgdGhlIHNpbWlsYXJpdGllcyBhcmUgZ3JlYXRlciB3aXRoICpldmVyeSogcG9zdC13YXIgKFdXSUkpIHByZXNpZGVudCwgZXhjZXB0IFRydW1wLCB0aGFuIHdpdGggKmFueSogcHJlLXdhciBwcmVzaWRlbnQuIFdlJ2xsIGxvb2sgaW4gbW9yZSBkZXRhaWwgYXQgdGhlIGNhbGN1bGF0aW9uIHRvIGRldGVybWluZSB3aGF0J3MgZ29pbmcgb24uCgojIyBDb3NpbmUgc2ltaWxhcml0eSBzdGVwIGJ5IHN0ZXAKCkxldCdzIGFnYWluIGNhbGN1bGF0ZSB0aGUgY29zaW5lIHNpbWlsYXJpdHkgYmV0d2VlbiBkb2N1bWVudHMgdXNpbmcganVzdCBjb3VudHMsIGJ1dCB0aGlzIHRpbWUgZG9pbmcgaXQgc3RlcCBieSBzdGVwLiBGaXJzdCwgbGV0J3MgbWFrZSBhIHJlZ3VsYXIgbWF0cml4IG9iamVjdCBvdXQgb2Ygb3VyIGR0bS4gKEl0J3MgZWFzaWVyIHRvIHVuZGVyc3RhbmQgd2hhdCdzIGdvaW5nIG9uIGlmIHdlIG1ha2UgdGhpcyBhICJkZW5zZSIgbWF0cml4LCBidXQgaXQncyBub3Qgc29tZXRoaW5nIHdlIHdvdWxkIG5vcm1hbGx5IGRvLikKCmBgYHtyfQpkdG1hdCA8LSBhcy5tYXRyaXgoZHRtKQpgYGAKCiMjIyBUaGUgTDItbm9ybQoKTm93IGxldCdzICJub3JtIiB0aGUgZG9jdW1lbnRzIHRvIGxlbmd0aCAxIHVzaW5nIHRoZSAkTF8yJCBub3JtLiBUaGUgJExfMiQgbm9ybSBpcyB0aGUgc3F1YXJlIHJvb3Qgb2YgdGhlIHN1bSBvZiBzcXVhcmVzIGZvciBlYWNoIGRvY3VtZW50IC0tIHRoZSAibGVuZ3RoIiBvZiB0aGUgZG9jdW1lbnQgdmVjdG9yLCBvciB0aGUgIkV1Y2xpZGVhbiBkaXN0YW5jZSIgb2YgaXRzIHRpcCBmcm9tIHRoZSBvcmlnaW46CgpgYGB7cn0KIGwyLmR0bWF0IDwtIHNxcnQocm93U3VtcyhkdG1hdF4yKSkKYGBgCgpOb3cgZGl2aWRlIHRoZSByb3dzIGJ5IHRoZSBub3JtLiBUaGUgcm93IHN1bSBvZiBzcXVhcmVzIHNob3VsZCBub3cgYmUgb25lLgoKYGBge3J9CmR0bWF0Lmwybm9ybWVkIDwtIHN3ZWVwKGR0bWF0LDEsbDIuZHRtYXQsIi8iKQpzdW1tYXJ5KHJvd1N1bXMoZHRtYXQubDJub3JtZWReMikpCmBgYAoKIyMjIFRoZSBkb3QgcHJvZHVjdAoKVG8gZmluZCB0aGUgY29zaW5lIHNpbWlsYXJpdHkgYmV0d2VlbiBhbnkgdHdvLCBjYWxjdWxhdGUgdGhlIGRvdCBwcm9kdWN0IG9mIHRoZXNlIHZlY3RvcnMgKG11bHRpcGx5IHRoZSB0d28gdmVjdG9ycyBlbGVtZW50IGJ5IGVsZW1lbnQsIGFuZCB0aGVuIHN1bSB0aG9zZSB1cCkuCgpgYGB7cn0KY29zLm9iYW1hMS5vYmFtYTIgPC0gc3VtKGR0bWF0Lmwybm9ybWVkWyIyMDA5LU9iYW1hIixdKmR0bWF0Lmwybm9ybWVkWyIyMDEzLU9iYW1hIixdKQpjb3Mub2JhbWExLm9iYW1hMgoKY29zLm9iYW1hMS50cnVtcDEgPC0gc3VtKGR0bWF0Lmwybm9ybWVkWyIyMDA5LU9iYW1hIixdKmR0bWF0Lmwybm9ybWVkWyIyMDE3LVRydW1wIixdKQpjb3Mub2JhbWExLnRydW1wMQpgYGAKClRvIGZpbmQgdGhlIGNvc2luZSBzaW1pbGFyaXR5IGZvciBhbGwgcGFpcnMsIHRha2UgdGhlIG1hdHJpeCBjcm9zc3Byb2R1Y3QuIChUaGF0IGlzLCBjYWxjdWxhdGUgdGhlIGRvdCBwcm9kdWN0IG9mIGV2ZXJ5IHJvdyAvIGRvY3VtZW50IHdpdGggZXZlcnkgb3RoZXIgcm93IC8gZG9jdW1lbnQgLS0gdGhpcyB3aWxsIHJlc3VsdCBpbiBhIDU4ICRcdGltZXMkIDU4IG1hdHJpeC4pIFRoaXMgbWF0cml4IGhhcyBhbGwgb25lcyBvbiBpdHMgZGlhZ29uYWwgLS0gd2h5PyBUaGlzIG1hdHJpeCBpcyBzeW1tZXRyaWMgLS0gd2h5PwoKCgpgYGB7cn0KY29zLmR0bWF0IDwtIGR0bWF0Lmwybm9ybWVkICUqJSB0KGR0bWF0Lmwybm9ybWVkKQpkaW0oY29zLmR0bWF0KQoKc29ydChjb3MuZHRtYXRbLCIxOTYxLUtlbm5lZHkiXSxkZWM9VCkKYGBgCgpBcyB3ZSBzaG91bGQsIHdlIGdldCB0aGUgc2FtZSBhbnN3ZXIgZm9yIHRoZSBzcGVlY2hlcyBtb3N0IHNpbWlsYXIgdG8gdGhlIEtlbm5lZHkgaW5hdWd1cmFsLgoKTm93IGxldCdzIGZvY3VzIG9uIHRoZSBzdHJhbmdlbmVzcy4gSXQgbG9va3MgbGlrZSBtb3N0IGluYXVndXJhbHMgYXJlIHJlbGF0aXZlbHkgc2ltaWxhciB0byBvbmUgYW5vdGhlciAoLjggKyBzZWVtcyBsaWtlIGEgcHJldHR5IGhpZ2ggbnVtYmVyKSBhbmQgaXQgc2VlbXMgb2RkIHRoYXQgQ29vbGlkZ2Ugd291bGQgYmUgdGhlIG1vc3Qgc2ltaWxhciB0byBLZW5uZWR5LiBMZXQncyBicmVhayBkb3duIHdoYXQgd29yZHMgYXJlIGNvbnRyaWJ1dGluZyB0aGUgbW9zdCB0byB0aGUgc2ltaWxhcml0eSByYW5raW5ncyBieSBsb29raW5nIGF0IHRoZSBjb250cmlidXRpb25zIG9mIGluZGl2aWR1YWwgd29yZHMgdG8gdGhlIGRvdC1wcm9kdWN0OgoKYGBge3J9CnNvcnQoZHRtYXQubDJub3JtZWRbIjE5NjEtS2VubmVkeSIsXSpkdG1hdC5sMm5vcm1lZFsiMTkyNS1Db29saWRnZSIsXSwgZGVjPVQpWzE6MjBdCmBgYAoKQWhoaGghIFRoZSBjb3NpbmUgc2ltaWxhcml0eSBpcyBiZWluZyBkcml2ZW4gYnkgdGhlIHJlbGF0aXZlIHVzZSBvZiBjb21tb24gd29yZHMgLi4uIHRoZSwgb2YsIGFuZCwgdG8sIGFuZCBzbyBvbi4gVGhpcyBpcyBhcmd1YWJseSB3aGF0IHdlIHdhbnQgaW4gc29tZSBhcHBsaWNhdGlvbnMgbGlrZSBzdHlsb21ldHJ5LCB3aGVyZSB3ZSBhcmUgdHJ5aW5nIHRvIGd1ZXNzIGF1dGhvcnNoaXAgZm9yIGV4YW1wbGUsIGJ1dCBhbG1vc3QgZGVmaW5pdGVseSBub3Qgd2hhdCB3ZSdyZSBhZnRlciBoZXJlLgoKTGV0J3MgbG9vayBpbnN0ZWFkIGF0IHRoZSB0Zi1pZGYgY29zaW5lIHNpbWlsYXJpdGllcy4KCmBgYHtyfQpkdG1hdC53IDwtIGFzLm1hdHJpeChkdG0udykKCmwyLmR0bWF0LncgPC0gc3FydChyb3dTdW1zKGR0bWF0LndeMikpCmR0bWF0LncubDJub3JtZWQgPC0gc3dlZXAoZHRtYXQudywxLGwyLmR0bWF0LncsIi8iKQoKY29zLmR0bWF0LncgPC0gZHRtYXQudy5sMm5vcm1lZCAlKiUgdChkdG1hdC53Lmwybm9ybWVkKQpkaW0oY29zLmR0bWF0LncpCgpzb3J0KGNvcy5kdG1hdC53WywiMTk2MS1LZW5uZWR5Il0sZGVjPVQpCmBgYAoKU2FtZSBhbnN3ZXIgYXMgYmVmb3JlLiBTaW1pbGFyaXRpZXMgYXJlIGxvd2VyLCBidXQgdGhleSByZWZsZWN0IHNpbWlsYXJpdHkgYW1vbmcgZGlzdGluY3RpdmUgY29udGVudC4gVGhhdCBpcywgdGhleSBhcmUgc2ltaWxhciBpbiB3aGF0IG1ha2VzIHRoZW0gZGlmZmVyZW50IGZyb20gdGhlIG90aGVycy4gU28sIHdoeSBpcyBSZWFnYW4gdGhlIG1vc3Qgc2ltaWxhciB0byBLZW5uZWR5PwoKYGBge3J9CnNvcnQoZHRtYXQudy5sMm5vcm1lZFsiMTk2MS1LZW5uZWR5IixdKmR0bWF0LncubDJub3JtZWRbIjE5ODEtUmVhZ2FuIixdLCBkZWM9VClbMToyMF0KYGBgCgpUaGlzIHN1Z2dlc3RzIHRoZXkgYm90aCBmcmFtZWQgdGhlaXIgcHJlc2lkZW5jaWVzIGFzIGFuIG9wcG9ydHVuaXR5IHRvICJiZWdpbiIgc29tZXRoaW5nIG5ldywgZm9yIGV4YW1wbGUsIGFuZCB3ZXJlIHJlbGF0aXZlbHkgdW51c3VhbCBpbiBkb2luZyBzby4KCmBgYHtyfQprd2ljKGluYXVndXJhbF90b2tlbnMsImJlZ2luIiwgd2luZG93PTQpCmBgYAoKCiMjIyBQTUksIEZpZ2h0aW4nIFdvcmRzLCBhbmQgImtleW5lc3MiIGFwcHJvYWNoZXMgdG8gd2VpZ2h0aW5nCgpGaW5hbGx5LCBJIHdpbGwgbm90ZSB0aGF0IGFuIGFsdGVybmF0aXZlIGFwcHJvYWNoIHRvIHRmLWlkZiB3ZWlnaHRpbmcgaXMgdG8gcmVwcmVzZW50IGVhY2ggZG9jdW1lbnQgYnkgYSB2ZWN0b3Igb2YgImtleW5lc3MiIHN0YXRpc3RpY3MuIFRoZSBgdGV4dHN0YXRfa2V5bmVzc2AgY29tbWFuZCBwcm92aWRlcyBzZXZlcmFsLCBzdWNoIGFzIGNoaS1zcXVhcmVkIGFuZCBQTUkgKHBvaW50d2lzZSBtdXR1YWwgaW5mb3JtYXRpb24pLiBJIHBlcnNvbmFsbHkgb2Z0ZW4gdXNlIHRoZSAiRmlnaHRpbicgV29yZHMiIHN0YXRpc3RpYyAoemV0YSksIGNhbGN1bGF0ZWQgd2l0aCBlYWNoIGRvY3VtZW50IGFzIGEgImdyb3VwIiB0byBiZSBjb21wYXJlZCB0byB0aGUgb3RoZXJzLiBJbiB0aGlzIGV4YW1wbGUsIHRoaXMgZ2l2ZXMgcmVzdWx0cyB0aGF0IGFyZSBjb3JyZWxhdGVkIHdpdGggdGYtaWRmLCBidXQgd2l0aCBzb21lIG1pbm9yIHF1YWxpdGF0aXZlIGRpZmZlcmVuY2VzLgo=