Visualizing Lexical Distance in Three Dimensions

If you do not know Stephan Steinbach’s blog Alternative Transport, check it out. Among subjects that interest me, Stephan covers data visualization. At one time, a picture from his post on lexical distance among languages of Europe went viral. Since then, he has been pondering ways to improve the illustration by including more languages, positioning them more scientifically, and going into the third dimension. Eventually, we decided to co-operate in this endeavour. Yesterday, Stephan published his article on the dimensional limits of graphs and today, I am publishing this post.

Without more ado, here is the visualization of lexical distance among 210 living and extinct languages coming mainly from the Old World.

210-Languages

Here is what it took to make this visualization:

  • Get Vincent Beaufils’s list of 18 most stable word stems: “eye”, “ear”, “nose”, “hand”, “tongue”, “tooth”, “death”, “water”, “sun”, “wind”, “night”, “two”, “three”, “four”, “I”, “you”, “who”, and “name” for the languages in question.
  • For each pair of languages, add up the Brown–Holman–Wichmann distance between all pairs of corresponding words. This kind of distance takes into account 692 correspondences between consonants and vowels that recur among world’s languages.
  • Apply multidimensional scaling to the matrix of distances. This approach minimizes the sum of squared differences between the input and output distances. Take three initial dimensions of the result.
  • Using Matplotlib, draw the labels of the languages in three dimensions. Move the viewpoint with uniform speed along the tennis ball seam as defined parametrically by López-López:
    x(t) = (1 − b)sin t + b sin 3t
    y(t) = (1 − b)cos t − b cos 3t
    z(t) = √4(1 − b)b cos 2t
    Following López-López, set b = 0.20.
  • The closer the label of a language is to the viewpoint, the less transparent make the label. Concretely, vary the alpha channel of the labels from 0.05 far away from the viewpoint to 1.0 close to it.

As a bonus, here are visualizations of lexical distance among languages of the Indo–European family and its Germanic, Italic, and Romance branches.

Indo-European
Germanic

Italic-and-Romance

The colors come from Ethan Schoonover’s Solarized palette. The elegant narrow font is Delicious, a free font from exljbris Font Foundry.

Advertisements
Visualizing Lexical Distance in Three Dimensions

PageRank in 600 words and 60 lines of Python

I was unable to find a simple and efficient implementation of PageRank. As a consequence, I wrote this post and my own Python code that within ten seconds can compute the PageRank of the Polish Wikipedia containing 17,880,897 links between 1,113,939 articles. For the curious, here are the top ten articles.

Title of the article PageRank Equivalent English title
Polska 0.00349 Poland
Francja 0.00343 France
Stany Zjednoczone 0.00341 United States
Język angielski 0.00257 English language
Łacina 0.00225 Latin
Niemcy 0.00205 Germany
Włochy 0.00162 Italy
Wieś 0.00156 Village
Wielka Brytania 0.00131 United Kingdom
Podział administracyjny Polski 1975–1998 0.00124 Voivodeships of Poland (1975–98)

The random surfer

The PageRank of a page is the probability of visiting the page at a fixed distant moment during a random surf through the web. Before each of her actions, the ideal random surfer tosses a biased coin.

  1. If the toss is a head, she clicks a random link on the current page, provided that the page has any outbound links.
  2. If the toss is a tail, she gets bored and jumps to a random page.
  3. If the toss is a head and the current page has no outbound links, she also jumps to a random page.

The original papers recommend setting the head probability c to 0.85.

Linear algebra

Number the pages from 1 to n. Store the probabilities of visiting each page at a given moment in an n-element vector p. The actions of the random surfer correspond to linear transformations of vector p. To express these transformations, we need three building blocks:

  1. A sparse n×n matrix H that reflects the following of links. When page i has fi outbound links, among them a link to page j, then the hij element of matrix H is equal to 1/fi. When there are no links from page i to page j, then hij = 0. The vector cHTp contains the probabilities of visiting each page after action 1 above.
  2. A vector with n elements equal to 1/n, which we denote as (1/n)1, that reflects jumping to a random page. For a scalar a or a 1×1 matrix A = [a], each element of the vector a(1/n)1 or (1/n)1A contains the same number a/n. In particular, the vector (1 − c)(1/n)1 contains the probabilities after action 2.
  3. A sparse vector d that reflects dead ends. Its element di has value 1 when page i has no outbound links. If there is a link from page i somewhere else, then di = 0. The 1×1 matrix dTp contains the probability that the surfer is visiting the end of the Internet so the vector c(1/n)1dTp corresponds to action 3.

The PageRank vector p can be computed iteratively. Start with any initial vector p0 of probabilities that add to one, for instance the vector (1/n)1. Repeat the step

\mathbf{p}_{k+1} := c \big(\mathbf{H}^\mathrm{T}\mathbf{p}_k + (1/n)\mathbf{1}\mathbf{d}^\mathrm{T}\mathbf{p}_k\big) + (1 - c)(1/n)\mathbf{1}\qquad(1)

until, say, the sum of absolute differences |pk+1 – pk| is smaller than a given threshold ϵ. Do not worry, the sequence (pk) does converge whenever c < 1.

The dominant operation in step (1) is the multiplication HTpk. For a sparse matrix H, it takes time proportional to the number of nonzero elements in H, which in our case is the total number of links. While it is possible to express step (1) in a simpler form pk+1 := Gpk, the matrix G = c(HT + (1/n)1dT) + (1 − c)(1/n)1T1 would be dense. The multiplication would take much longer time, proportional to the square of the number of pages.

Note that you can use the dot product d·pk to write (d·pk)(1/n)1 instead of (1/n)1dTpk and that often you can see step (1) above written equivalently as

\mathbf{p}_{k+1}^\mathrm{T} := c \big(\mathbf{p}_k^\mathrm{T}\mathbf{H} + \mathbf{p}_k^\mathrm{T}\mathbf{d}(1/n)\mathbf{1}^\mathrm{T}\big) + (1 - c)(1/n)\mathbf{1}^\mathrm{T}.

An example

Let us work with a concrete graph:


\hfill \mathbf{H} = \begin{pmatrix} 0 & 1/3 & 1/3 & 1/3 & 0   \\ 0 & 0   & 1/2 & 1/2 & 0   \\ 0 & 1   & 0   & 0   & 0   \\ 0 & 0   & 1/2 & 0   & 1/2 \\ 0 & 0   & 0   & 0   & 0 \end{pmatrix}, (1/n)\mathbf{1} = \begin{pmatrix} 1/5 \\ 1/5 \\ 1/5 \\ 1/5 \\ 1/5 \end{pmatrix}, \mathbf{d} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}, \mathbf{p}_0 = \begin{pmatrix} 1/5 \\ 1/5 \\ 1/5 \\ 1/5 \\ 1/5 \end{pmatrix}.

Repeatedly computing

\begin{pmatrix} p_1 \\ p_2 \\ p_3 \\ p_4 \\ p_5 \end{pmatrix}_{k+1} := 0.85 \left( \begin{pmatrix} 0 & 1/3 & 1/3 & 1/3 & 0   \\ 0 & 0   & 1/2 & 1/2 & 0   \\ 0 & 1   & 0   & 0   & 0   \\ 0 & 0   & 1/2 & 0   & 1/2 \\ 0 & 0   & 0   & 0   & 0 \end{pmatrix}^\mathrm{T} \begin{pmatrix} p_1 \\ p_2 \\ p_3 \\ p_4 \\ p_5 \end{pmatrix}_k + \begin{pmatrix} 1/5 \\ 1/5 \\ 1/5 \\ 1/5 \\ 1/5 \end{pmatrix} \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}^\mathrm{T} \begin{pmatrix} p_1 \\ p_2 \\ p_3 \\ p_4 \\ p_5 \end{pmatrix}_k \right) + 0.15 \begin{pmatrix} 1/5 \\ 1/5 \\ 1/5 \\ 1/5 \\ 1/5 \end{pmatrix} ,

for instance

\begin{pmatrix} p_1 \\ p_2 \\ p_3 \\ p_4 \\ p_5 \end{pmatrix}_1 := 0.85 \left( \begin{pmatrix} 0 \\ 1/3\times1/5+1\times1/5 \\ 1/3\times1/5+1/2\times1/5+1/2\times1/5 \\ 1/3\times1/5+1/2\times1/5 \\ 1/2\times1/5 \end{pmatrix} + \begin{pmatrix} 1/5 \\ 1/5 \\ 1/5 \\ 1/5 \\ 1/5 \end{pmatrix} \begin{pmatrix} 1/5 \end{pmatrix} \right) + 0.15 \begin{pmatrix} 1/5 \\ 1/5 \\ 1/5 \\ 1/5 \\ 1/5 \end{pmatrix} ,

we obtain

\mathbf{p}_0 = \begin{pmatrix} 0.200 \\ 0.200 \\ 0.200 \\ 0.200 \\ 0.200 \end{pmatrix}, \mathbf{p}_1 = \begin{pmatrix} 0.064 \\ 0.291 \\ 0.291 \\ 0.205 \\ 0.149 \end{pmatrix}, \mathbf{p}_2 = \begin{pmatrix} 0.055 \\ 0.321 \\ 0.284 \\ 0.197 \\ 0.143 \end{pmatrix}, \mathbf{p}_3 = \begin{pmatrix} 0.054 \\ 0.315 \\ 0.289 \\ 0.201 \\ 0.141 \end{pmatrix}
\mathbf{p}_4 = \begin{pmatrix} 0.054 \\ 0.315 \\ 0.289 \\ 0.203 \\ 0.139 \end{pmatrix}, \mathbf{p}_5 = \begin{pmatrix} 0.054 \\ 0.315 \\ 0.289 \\ 0.203 \\ 0.139 \end{pmatrix}, \mathbf{p}_6 = \begin{pmatrix} 0.054 \\ 0.314 \\ 0.289 \\ 0.203 \\ 0.140 \end{pmatrix}, \mathbf{p}_7 = \begin{pmatrix} 0.054 \\ 0.315 \\ 0.289 \\ 0.202 \\ 0.140 \end{pmatrix}.

The sum of absolute differences between pk+1 and pk decreases exponentially:

|\mathbf{p}_1 - \mathbf{p}_0| = 0.374 \\ |\mathbf{p}_2 - \mathbf{p}_1| = 0.060 \\ |\mathbf{p}_3 - \mathbf{p}_2| = 0.029 \\ |\mathbf{p}_4 - \mathbf{p}_3| = 0.013 \\ |\mathbf{p}_5 - \mathbf{p}_4| = 0.005 \\ |\mathbf{p}_6 - \mathbf{p}_5| = 0.002 \\ |\mathbf{p}_7 - \mathbf{p}_6| = 0.001

The code

#!/usr/bin/python3

import scipy
from scipy import sparse


def ComputePageRank(links, c=0.85, epsilon=0.001):
  """Computes the PageRank for given |links|.

  The source or target elements of |links|
  are numbered from zero upwards. Gaps in
  the numbering represent pages having neither
  inbound nor outbound links. Note that with
  normal settings, such pages still get a
  nonzero PageRank.

  Args:
    links: A list of ⟨source, target⟩ pairs.
      Source and target must be integers >= 0.
    c: The probability that the random surfer
      follows a link, if there are any links.
    epsilon: The desired accuracy.

  Returns:
    A scipy.array whose ith element is the PageRank
    of the ith page.
  """
  ones = scipy.ones(len(links))
  sources = [x[0] for x in links]
  targets = [x[1] for x in links]
  n = max(max(sources), max(targets)) + 1
  # |HT| is sparse, so store it in COOrdinate
  # format: a list of ⟨source, target, probability⟩
  # triples.  Make it explicitly square in case
  # the last target has no outbound links or the
  # last source has no inbound links.
  HT = sparse.coo_matrix(
      (ones, (targets, sources)), shape=(n, n))
  # Count the outbound links for each source.
  num_outlinks = scipy.array(HT.sum(axis=0)).flatten()
  # Divide each nonzero element of |HT|,
  # so far equal to one, by the number
  # of outbound links in its source.
  HT.data /= num_outlinks[sources]
  d_indices = scipy.where(num_outlinks == 0)[0]
 
  r = scipy.ones(n) / n
  while True:
    previous_r = r
    r = c * (HT * r + sum(r[d_indices])/n) + (1.0 - c)/n
    # r.sum() ≈ 1 but prevent errors from adding up.
    r /= r.sum()
    if scipy.absolute(r - previous_r).sum() < epsilon:
      return r


if __name__ == '__main__':
  print(PageRank(
      [(0, 1), (0, 2), (0, 3), (1, 2),
       (1, 3), (2, 1), (3, 2), (3, 4)]))
PageRank in 600 words and 60 lines of Python

More Perfect Polish Pangrams

Stróż pchnął kość w quiz gędźb vel fax myjń.

As far as I can tell, you have just read the first perfect pangram ever made from Polish words with the letters q, v, and x that live on the outskirts of Polish spelling. You can get eleven similar pangrams by permuting the words {kość, quiz, fax} and {gędźb, myjń}. Thanks to Piotr Wieczorek who asked me about finding such pangrams after a previous blog post of mine.

My brute-force program can cover the alphabet with four or five words in acceptable time but it would run for years while searching for a nine- or ten-word cover. Therefore, I wrote a new version that solves the problem with Donald Knuth’s dancing links technique. On my laptop, it finds 3646 exact covers of the 35-letter extended alphabet with 388,866 candidate word forms within 34 seconds. There are:

  • 41 seven-word covers,
  • 1081 eight-word covers,
  • 1989 nine-word covers,
  • 535 ten-word covers,

and no covers with fewer than seven or more than ten words.

Out of them, 231 covers have exactly one verb form:

  • 24 covers have a third-person form,
  • 72 covers have an infinitive form,
  • 135 covers have other verb forms.

I list these covers below. If you permute any of them to make an acceptable sentence, please leave it in a comment. But first, a bonus: twelve three-word perfect Polish pangrams that cover the 23-letter alphabet deprived of letters specific to Polish.

fragment bujd szpilkowych
blefuj gwicht szpadrynkom
frygnij chleb paskudztwom
frygnij paskudztw chlebom
gnij bukszpryt feldwachom
grzybkuj wschodni pamflet
persyfluj gwicht dzbankom
podfarbuj gwicht szynklem
podlinkuj wf grabsztychem
pstrzyj buking feldwachom
zamknij gryf podchlebstwu
zgarnijmy fuk podchlebstw

Covers with a third-person form:

quap hex volt myjń fiks:fisk:skif część dźgnął wróżb
quap hex volt myjń sfór dźgnął żbik część w
quest fax vin myjń pchlość gędźb krzów żął:łżą
quest fax vin myjń pchlość gędźb krów z żął:łżą
quest fax vin myjń pchlość gędźb krów zżął
quest fax vin myjń pchlość gędźb krzą żółw
quest fax vin myjń pchlość gędźb krzą łóż w
quest fax vin myjń pchlość gędźb kłów:włók z rżą:żrą
quest fax vin myjń pchlość gędźb kół z rżą:żrą w
quest fax vin myjń pchlość łódź brzęk gżą:żgą w
quiz vectr fax myjń shop lśkną żółć gędźb w
quiz vel fax myjń gędźb kość pchnął stróż w
quiz vent fax schroń wyjść ględźb mókł żąp
quiz vent fax myjń pchlość gędźb skór wżął
quiz vent fax myjń pchlość gędźb skór żął:łżą w
quiz vent fax myjń pchlość gędźb wrósł kąż
quiz vent fax myjń pchlość gędźb rósł kąż w
quiz vet fax myjń ględźb wskroś pchną żółć
quiz vet fax myjń ględźb skroś pchną żółć w
quiz vet fax myjń gędźb pchlość rżnął sków
quiz vet fax myjń wóźb pchlość skrę dżgnął
quiz vet fax myjń dźgnął pchlość kęs:sęk wróżb
quiz vet fax myjń dźgną pchlość skrę żłób w
quiz volt fax myjń żeść pchnął skór gędźb w

Covers with an infinitive form:

squat hex vin cyfr:fryc kłoń pójść mąż ględźb w z
squat hex vin ryf kłoń pójść ględźb mżąc:żmąc w z
squat hex vin fryz kłoń pójść w ględźb mżąc:żmąc
squaw hex vin kłoń tymf pójść ględźb rżąc:żrąc z
squaw hex vin kłoń fryt:ryft ględźb pójść mżąc:żmąc z
quest fax vlog świń młódź jęk pchnąć bryż z
quest fax vlog myjń chnę wprząść łódź żbik
quest fax vlog myjń chnę prząść łódź żbik w
quest fax vlog myjń pchłę bździn wróść kąż
quest fax vlog myjń pchłę bździn róść kąż w
quest fax vin gońb przyjść węch młódź kląż
quest fax vin myjń zbość pchłę gródź kląż w
quest fax vin myjń bość pchłę gródź kląż w z
quest fax vin myjń zbóść grodź pchłę kląż w
quest fax vin myjń bóść grodź pchłę kląż w z
quest fax vin myjń prząść kwoch ględźb łóż
quest fax vin myjń wzróść ględźb chłop:pchło:płoch kąż
quest fax vin myjń wzróść gędźb chłop:pchło:płoch kląż
quest fax vin myjń wróść ględźb chłop:pchło:płoch kąż z
quest fax vin myjń wróść gędźb chłop:pchło:płoch z kląż
quest fax vin myjń zróść ględźb chłop:pchło:płoch kąż w
quest fax vin myjń zróść gędźb chłop:pchło:płoch kląż w
quest fax vin myjń róść chłop:pchło:płoch kląż gędźb w z
quest fax vin myjń róść chłop:pchło:płoch kąż ględźb w z
quest fax vin kłoń chryzm pójść wąż ględźb
quest fax vin kłoń mchy:mych pójść ględźb z rżą w
quest fax vin kłoń chmyz pójść ględźb rżą w
quest fax vin kłoń rychw pójść ględźb z mąż
quest fax vin kłoń chyr pójść mąż ględźb w z
quest fax vin kłoń chów przyjść ględźb mąż
quest fax vin kłoń hyr pójść ględźb mżąc:żmąc w z
quest fax vin koń chryzm pójść w ględźb łżą
quest fax vin koń mchów ględźb przyjść łżą
quest fax vin woń mkłych pójść ględźb z rżą
quest fax vin ryń ględźb pójść kmoch w z łżą
quiz van hex wrońsk tymf pójść łżąc ględźb
quiz van hex skroń tymf pójść łżąc ględźb w
quiz vectr fax myjń shop lśknąć żółw gędźb
quiz vectr fax myjń shop lśknąć łóż gędźb w
quiz vectr fax słoń hymn pójść kląż gędźb w
quiz vectr fax słoń hymn pójść kąż ględźb w
quiz vel fax myjń dźgnąć kośb pchłę stróż w
quiz vent fax schroń pójść ględźb mykw łżą
quiz vent fax schroń pójść ględźb mkły wąż
quiz vent fax schroń pójść ględźb mąk łyżw
quiz vent fax schroń pójść ględźb mąk łyż:łży:żył w
quiz vent fax schroń pójść ględźb mkłą wyż:żyw
quiz vent fax schroń pójść ględźb kły:łyk w mąż
quiz vent fax myjń wżąć skróś chłop:pchło:płoch ględźb
quiz vent fax myjń żąć wskróś chłop:pchło:płoch ględźb
quiz vent fax myjń żąć skróś chłop:pchło:płoch ględźb w
quiz vent fax wrońsk mchy:mych pójść ględźb łżą
quiz vent fax wrońsk chył:łych pójść ględźb mąż
quiz vent fax skroń pójść mchy:mych w ględźb łżą
quiz vent fax skroń pójść chył:łych w ględźb mąż
quiz vet fax schroń pójść ględźb młyn kąż w
quiz vet fax schroń pójść ględźb nyż w mkłą
quiz vet fax schroń pójść gędźb kląż młyn w
quiz vet fax schroń lśknąć pój gędźb żymł w
quiz vet fax myjń ględźb wskroś pchnąć łóż
quiz vet fax myjń ględźb skroś pchnąć żółw
quiz vet fax myjń ględźb skroś pchnąć łóż w
quiz vet fax wrońsk pójść chną ględźb żymł
quiz vet fax wrońsk pójść hymn łżąc ględźb
quiz vet fax skroń pójść chną ględźb żymł w
quiz vet fax skroń pójść hymn łżąc ględźb w
quiz volt fax drżeń źgnąć bęś mkłych spój w
quiz volt fax rżeń bęś dźgnąć mkłych spój w
quiz volt fax myjń wskróś pchnąć gędźb łeż:łże
quiz volt fax myjń wskróś dźgnąć pchłę beż
quiz volt fax myjń skróś pchnąć gędźb łeż:łże w
quiz volt fax myjń skróś dźgnąć beż pchłę w

Covers with other verb forms:

quap hex vis myjń fort:frot:torf lśknąc zżółć gędźb w
quap hex vis myjń fort:frot:torf lśknąc żółć gędźb w z
quap hex volt myjń fiś skłóć gędźb rżnąc w z
quap mix vent sfór chłoń wyjść kląż gędźb z
quap mix vent sfór chłoń wyjść kąż ględźb z
squat hex virg fob myjń lśknąc żółć wpędź z
squat hex virg fob myjń lśknąc żółć pędź w z
quest fax virg błoń część hymn pójdź kląż w
quest fax virg boń wyjść młódź pchnę z kląż
quest fax virg myjń zbódź pchlość wnęk łżą
quest fax virg myjń zbłądź pchlość nóżkę w
quest fax virg myjń zbądź pchlość wnęk łóż
quest fax virg myjń zbądź pchlość nóż łęk w
quest fax virg myjń bódź pchlość wnęk z łżą
quest fax virg myjń błądź nóżkę w pchlość z
quest fax virg myjń bądź pchlość wnęk z łóż
quest fax virg myjń bądź pchlość wnęk złóż
quest fax virg myjń bądź pchlość zżółknę w
quest fax virg myjń bądź pchlość żółknę w z
quest fax virg myjń bądź pchlość żnę kłów:włók z
quest fax virg myjń bądź pchlość żnę kół w z
quest fax virg myjń bądź żółć lśknę pochw z
quest fax virg myjń bądź pchlość wnęk z łóż
quest fax virg myjń bądź pchlość wnęk złóż
quest fax virg myjń bądź pchlość nóż łęk w z
quest fax virg myjń nędź kośb pchlą żółć w z
quest fax virg myjń nędź pchlość bąk z żółw
quest fax virg myjń nędź pchlość bąk z łóż w
quest fax virg myjń nędź pchlość bąk złóż w
quest fax virg myjń nędź pchlość łąk zbóż w
quest fax virg myjń nędź pchlość kąż łbów z
quest fax virg myjń nędź pchlość kąż złób w
quest fax virg myjń nędź kość pchlą żłób w z
quest fax virg myjń zwędź pchlość nóż kłąb
quest fax virg myjń wódź pchlość żnę z kłąb
quest fax virg myjń wędź pchlość nóż z kłąb
quest fax virg myjń złódź pchlość bąk żnę w
quest fax virg myjń łódź pchlość bąk żnę w z
quest fax virg myjń nóź pchlość kłęb żądz w
quest fax vlog chyń wnijść młódź brzęk żąp
quest fax vlog chyń wnijść przędź żłób mąk
quest fax vlog świń przyjdź chnę młóćb kąż
quest fax vlog myjń chłódź wniść brzęk żąp
quest fax vlog myjń chłódź śnić żąp brzęk w
quest fax vlog myjń śpichrz żółć bądź wnęk
quest fax vlog myjń śpichrz żółć nędź bąk w
quest fax vlog myjń śpichrz żółć bądź wnęk
quest fax vlog myjń pchnę świrk żółć bądź z
quest fax vlog myjń chną kiść wprzędź żłób
quest fax vlog myjń chną kiść przędź wżłób
quest fax vlog myjń chną kiść przędź żłób w
quest fax vlog myjń chną kiść przędź żłób w
quest fax vlog myjń chnę kiść wprządź żłób
quest fax vlog myjń chnę kiść prządź żłób w
quest fax vlog myjń pchłą kiść nędź wróżb z
quest fax vlog myjń pchłę zbródź wniść kąż
quest fax vlog myjń pchłę zbródź śnić kąż w
quest fax vlog myjń pchłę bródź wniść kąż z
quest fax vlog myjń pchłę bródź śnić kąż w z
quest fax vlog myjń chrzęść bądź żółw kpin:pink
quest fax vlog myjń chrzęść bądź łóż w kpin:pink
quest fax vlog myjń chrzęść pindź bąk żółw
quest fax vlog myjń chrzęść pindź bąk łóż w
quest fax vlog myjń chrzęść pindź łbów kąż
quest fax vlog myjń chrzęść nóź dżip w kłąb
quest fax vin chyń mgłość kląż przędź bój w
quest fax vin chyń mkłość pój ględźb z rżą w
quest fax vin chyń mkłość rój żąp ględźb w z
quest fax vin myjń pchlość gędźb kórz łżą w
quest fax vin myjń pchlość gędźb krą:rąk z włóż
quest fax vin myjń pchlość gędźb krą:rąk z łóż w
quest fax vin myjń pchlość gędźb krą:rąk złóż w
quest fax vin myjń pchlość gędźb krąż wół:łów z
quest fax vin myjń pchlość gędźb krąż zół:łóz w
quest fax vin myjń pchlość gędźb łąk wróż z
quest fax vin myjń pchlość zbródź w łęg kąż
quest fax vin myjń pchlość bródź kąż łęg w z
quest fax vin myjń pchlość zbódź łżą kręg w
quest fax vin myjń pchlość zbądź kręg żółw
quest fax vin myjń pchlość zbądź kręg łóż w
quest fax vin myjń pchlość bódź łżą kręg w z
quest fax vin myjń pchlość bądź włóż kręg z
quest fax vin myjń pchlość bądź złóż kręg w
quest fax vin myjń pchlość bądź łóż kręg w z
quest fax vin myjń pchlość bądź żółw kręg z
quest fax vin myjń pchlość bądź złóż kręg w
quest fax vin myjń pchlość bądź łóż kręg w z
quest fax vin myjń pchlość gróźb łęk zdąż w
quest fax vin myjń pchlość gróźb łęk dąż w z
quest fax vin myjń pchlość gródź bąk łżę w z
quest fax vin myjń pchlość gródź kłęb wąż z
quest fax vin myjń pchlość zgłódź ręb kąż w
quest fax vin myjń pchlość głódź brzęk wąż
quest fax vin myjń pchlość głódź kąż zręb w
quest fax vin myjń pchlość głódź kąż ręb w z
quest fax vin myjń pchlość gódź łżą brzęk w
quest fax vin myjń pchlość gędź krób w z łżą
quest fax vin myjń pchlość gędź kłąb wróż z
quest fax vin myjń pchlość gędź kłąb róż w z
quest fax vin myjń pchlość gędź krą:rąk żłób w z
quest fax vin myjń pchlość gędź łąk wróżb z
quest fax vin myjń pchlość zwędź krąg żłób
quest fax vin myjń pchlość wędź krąg żłób z
quest fax vin myjń pchlość złódź krąż gęb w
quest fax vin myjń pchlość łódź krąż zgęb w
quest fax vin myjń pchlość łódź krąż gęb w z
quest fax vin myjń chęć próśb zgłodź kląż w
quest fax vin myjń chęć próśb głodź kląż w z
quest fax vin myjń gość pchłę kląż zbródź w
quest fax vin myjń gość pchłę kląż bródź w z
quest fax vin myjń kość pchłą wróżb z ględź
quest fax vin myjń kość pchłą wróż ględźb z
quest fax vin myjń kość pchłę żądl gróźb w z
quiz vent fax gońb wyjść pchłę smródź kląż
quiz vent fax schroń wyjść ględźb mąk płóż
quiz vent fax schyń mkłość pój ględźb rżą w
quiz vent fax schyń mkłość rój żąp ględźb w
quiz vent fax chyń ględźb mkłość rżą spój w
quiz vent fax myjń pchlość gędźb skrą włóż
quiz vent fax myjń pchlość gędźb skrą łóż w
quiz vent fax myjń pchlość gędźb skrąż wół:łów
quiz vent fax myjń pchlość gędźb słów krąż
quiz vent fax myjń pchlość gróźb skąd łżę w
quiz vent fax myjń pchlość gródź wąż skłęb
quiz vent fax myjń pchlość gędź skrą żłób w
quiz vent fax myjń pchlość swędź krąg żłób
quiz vent fax myjń pchlość sądź kręg żłób w
quiz vent fax myjń pchlość łódź skrąż gęb w
quiz vent fax myjń żółć wskroś pchlą gędźb
quiz vent fax myjń żółć skroś pchlą gędźb w
quiz vent fax skroń wyjść pchłą ględźb móż
quiz vent fax słyń pchlość gędźb krój w mąż
quiz vent fax słyń pchlość gędźb mjrów kąż
quiz vet fax myjń dźgnę pchlość skrą żłób w
quiz vet fax skroń wyjść pchłą ględźb mnóż

More Perfect Polish Pangrams

Do dziewki

I have translated Jan Kochanowski‘s bawdy epigram quoted on my other blog into English and French.

To a Lass

My pretty lass, don’t run away.
You’ve rosy cheeks; my beard is grey
To match them. Look, when wreaths are tied,
One puts a rose by lily’s side.

My pretty lass, don’t run away.
My heart stays young though beard grows grey.
While grey’s my beard, I do not lean.
White’s garlic head; the haulm is green.

Don’t run away. If you regard
A riper cat, his tail is hard.
A wrinkled oak whose leaves turned fawn
Stands mighty since its trunk has brawn.

À une servante

Ne me rejette pas, ma servante mignonne.
Ton visage a rougi ; ma barbe qui grisonne
Le conviendra très bien. Quand on tresse des fleurs,
La rose près du lys on range par couleurs.

Ne me rejette pas, ma servante mignonne.
Mon cœur ne vieillit point quand ma barbe grisonne.
Ma barbe a grisonné, mais je suis sans chagrin.
Blanche est la tête d’ail, vert est pourtant son brin.

Ne me rejette pas : aux chats plus mûrs en âge
Les queues — comme on sait — durcissent davantage.
Ridé, feuillage ambré, un chêne sans effort
Se lève vigoureux, car il a un tronc fort.

Do dziewki

Polish Word Rectangles

In typical Polish crosswords, only nouns in their base form are allowed. These are the only four 7 × 7 squares whose rows and columns are Polish common nouns:

 C  E  R  A  M  I  K
 E  F  E  M  E  R  A
 R  E  K  E  T  E  R
 A  M  E J/B O  Z  A
 M  E  T  O  D  Y  K
 I  R  E  Z  Y  N  A
 K  A  R  A  K  A L/N

Add to them these twenty-five 7 × 7 squares that contain proper nouns. Like the word square above, all of them are symmetric.

 A  T  A  P  A  S  K     H  A  M  M  O  N  D
 T Y/E B  I  N  K  A     A  L  E  U  K  I  A
 A  B  I  A  T  A  R     M  E  I  S  T  E  R
 P  I  A  N  O  L  A     M  U  S  T  A  N  G
 A  N  T  O N/S I  K     O  K  T  A  W  I  A
 S  K  A  L  I N/C A     N  I  E  N  I  E  C
 K  A  R  A  K  A L/N    D  A  R  G  A  C  Z

 J  U  R  A  S  I  K     G  L  O  B  I  S  Z
 U  L  I  C  Z  K  A     L  U  B  A  N  I  A
 R  I  C  H  T  E  R     O  B  E  R  W  U  S
 A  C  H  T  U  B  A     B  A  R  K  A  S  A
 S  Z  T  U  B  A  K     I  N  W  A  L  I  D
 I  K  E  B  A  N  A     S  I  U  S  I  A  K
 K  A  R  A  K  A L/N    Z  A  S  A  D  K  A

 B  O  C  H  N  A  K     S  A  F  O  N  K  A
 O  C  H  R  A  N  A     A  B  E  L  A  R  D
 C  H  L  O  T  A  R     F  E  D  E  R  E  R
 H  R  O  M  A  D  A     O  L  E  D  Z  K  I
 N  A  T  A  N  E  K     N  A  R  Z  U  T  A
 A  N  A  D  E  M  A     K  R  E  K  T  U  N
 K  A  R  A  K  A L/N    A  D  R  I  A  N  A

G/H R  O  M  A  D  A
 R  Y  B  A  K  O  W
 O  B  S  Ł  O  N  A
 M  A  Ł  O  L  A  T
 A  K  O  L  I  T  A
 D  O  N  A  T  O  R
 A  W  A  T  A  R  A

Out of 2699 6 × 6 word squares, only two contain twelve different nouns:

K O M A S K    O S E M K A
U M A R Ł A    S Z K A R P
R E Z N O R    T E O N A S
A R G O N A    A R N I K A
S T A L I N    S Z O F E R
Z A J D K A    Z A M A N A

These are the only five 7 × 5 word rectangles:

 S  K  R  A  J  K  A     M  U  T  A  C  J  A
 A  L  O  Z  A  U  R     A  L  O  Z  A  U  R
M/P O  D  E  S  T  A     Z  A  G  O  Z  D  A
 K  W  A  K  I  E  R     E  M  A  L  I  E  R
 A  N  K  A  R  K  A     K  A  T  A  N  K  A

 H  E  L  A  N  I  N     Ł  A  W  K  A  R  Z
 U  P  A  D  O  W  A     A  B  S  A  L  O  N
 D  O  M  A  W  I  T     P  R  O  M  E  S  A
 A  D  E  N  I  N  A     K  A  L  I  N  I  N
 K  A  R  A  K  A  N     A  M  A  L  A  K  A

Out of 1275 6 × 5 word rectangles, this is the sole rectangle composed of common nouns only:

S H A R A N
Z A W O R A
E F E N D I
M I N I E R
A S A N N A

Tools used: Polimorfologik, where I extracted the nouns from, and Donald Knuth’s backtracking program back-mxn-words-new.w, modified by me to handle non-ASCII input. See the Bitbucket repository.

Polish Word Rectangles

Perfect Polish Pangrams

1. Zbłaźń mżystość ględów hiperfunkcją.
2. Napełńmyż fuksją tchórzliwość gędźb.
3. Pół figlując, krzywdźże smętność hańb.
4. Wzbudźże frygijką półsmętność chlań.
5. Znałem już pysk świń, chęć flot bądź gór.
6. Pójdźmyż haftnąć z wklęsłości guberń.
7. Mąć, schyl, traf, zgłęb, [ożeń, wódź, (kuś, pnij)
                                         (kup, śnij)]
                            [żeń, (odkup, śnij, wóź)
                                  (kpij, unoś, wódź)].

Tools used:

  • The list of Polish word forms from Polimorfologik by Marcin Miłkowski and Dawid Weiss.
  • The frequency list of Polish words by Jerzy Kazojć: the word forms in sentence 5 come from 3500 most frequent words; the imperative verb forms in sentence 7 — from 1000 most frequent verbs.
  • The Polish valence dictionary Walenty: “pójdźmyż” in sentence 6 is a form of a verb that can govern another verb in infinitive form.
  • Brute-force C++ programs for finding exact covers of the Polish alphabet with word forms: in sentences 1–5, using exactly one verb; in sentence 6 — using two verbs, the first one belonging to a special subclass and the second one in infinitive form; in sentence 7 — using only verbs in the second person singular imperative form.
  • A Python script for rejecting exact covers that cannot form a sentence: most of the exact covers are ungrammatical, like “Frunąłby mglistość pójdźkach zwężeń.”
  • Common sense to filter out the vast majority of pangrams, which contain ultra-rare word forms, like “Przybliżę jadźńą mgłość fusknechtów” or “Zwędźmyż ghańskość, płótnując ferbli.”

Update of December 17, 2018: I wrote another post on perfect Polish pangrams.

Perfect Polish Pangrams