Distance of Characters

We look at the effect of a bitwise change in the representation of characters. When transmitting data it might happen that one bit changes during transmission. Here we investigate this effect and calculate sets of “reachable” characters. So, here we look at the German alphabet und make use of the concept of Entities in Mathematica (here the Entity German Language), which can be entered via keyboard by pressing  “Shift”+“Ctrl”+“Enter”

2015 Character_1.png

2015 Character_2.png

These are the letters that can be found on the keybord of a German computer:

2015 Character_3.png

2015 Character_4.gif

But these are only the lowercase letters,  we get the uppercase ones quickly:

2015 Character_5.png

2015 Character_6.png

Now we detect, that there is no oppercase “ß” (by the way such a character exists). So we delete the “SS” whcih can be found in the list of uppercase letters:

2015 Character_7.png

2015 Character_8.png

2015 Character_9.png

Lowercase letters

First we are going to examine the neigborhood in the lowercase letters. We therefore use the lowercase German letters:

2015 Character_10.png

2015 Character_11.png

We start with character “a”:

2015 Character_12.png

The objective is to get a function which can be iterated to determine all characters that are reachable starting with the startcharacter (her the letter “a”), an collecting in each step all direct neighbors, i.e. the ones with a (Hamming-) distance 1 to “a”.

The next function determines all characters of distance 1 from the given character, and delivers al list of neighbors.

2015 Character_13.png

Now we can easily determine the neighbors of “a” and get the result in the form 2015 Character_14.png, where the 2015 Character_15.png are the neighbors of c

2015 Character_16.png

2015 Character_17.png

Visualizing the result (remeber: we take in account only lowercase letters):

2015 Character_18.png

0 1 1 0 0 0 0 1
0 1 1 0 0 0 1 1
0 1 1 0 0 1 0 1
0 1 1 0 1 0 0 1
0 1 1 1 0 0 0 1

The next function takes a list of neighbors and makes a list of neighbors in the same matter as above:

2015 Character_19.png

2015 Character_20.png

2015 Character_21.png

In the last step we process a list of such neighbors (resp. neigborlists), the application of union filters out all duplicates

2015 Character_22.png

Now we can use the built in function Nest to get all neighbors of e.g. degree three

2015 Character_23.png

2015 Character_24.png

In the next step we have to build rules for each neighborhood, to make it possible to plot a corresponding graph. Here we make use of the outer “product”. First we look at one element of our neighbourhoodlist

2015 Character_25.png

2015 Character_26.png

Now we can see how “outer” works:

2015 Character_27.png

2015 Character_28.png

Finally it is easy to built a graph:

2015 Character_29.png

2015 Character_30.png

Do the plotting:

2015 Character_31.png

2015 Character_32.gif

One can brush up the graph using the options “EdgeRenderingFunction” and “VertexRenderingFunction”:

2015 Character_33.png

2015 Character_34.gif

Putting the parts together we build a funtion to plot the graph of desired order directly

2015 Character_35.png

2015 Character_36.png

2015 Character_37.png

2015 Character_38.gif

The reachable characters

Now let´s have a look how many characters are reachable, when doing always a 1-Bit-distance step. This can easily calculated:

2015 Character_39.png

So

2015 Character_40.png

2015 Character_41.png

The number of reachable characters can now easyly visualized:

2015 Character_42.png

2015 Character_43.gif

As we see the process of iteration is going to get stationary at a certain point. But unfortunately not all characters are within reach of “a”. This can easily be seen when looking at the number of characters within reach of “a”:

2015 Character_44.png

2015 Character_45.png

but

2015 Character_46.png

2015 Character_47.png

So we miss two characters. To look a bit closer at this effect we define the (bitwise) Hamming-distance of two characters:

2015 Character_48.png

Now we can calculate the maximum Hamming distance, measured bitwise, in our set of letters. Therefore we build up all pairs of characters, calculate the distance and take the maximum:

2015 Character_49.png

2015 Character_50.png

This may need a word of explantion:

Tuples[letters,2] determines all pairs of letters from the set letters

The command @@@ replaces all the heads inside the list of tuples (which is “List”) with “hammingDistanceChar”, which calculates the Hamming distance between these chars

finally Max does what it should: I calcualtes the maximum of all this numbers

So we hava a maximum distance of 6 between the letters. But as we have seen two characters are missing in the reachable characters. Let´s look what characters these are:

2015 Character_51.png

2015 Character_52.png

So we know that these characters are not reachable from startcharacter “a” when we assume one Bit changes in each step.  This means clearly, that there is “the other way round”, no way outside fom these two characters:

2015 Character_53.png

2015 Character_54.png

The two characters have a distance of three, when bitwise calculated, so these characters are not “reachable” in the case that always (only) one bit changes at a time.

2015 Character_55.png

2015 Character_56.png

Word - Distances

2015 Character_57.png

2015 Character_58.png

2015 Character_59.png

2015 Character_60.gif

Init

Created with the Wolfram Language