Wolfram Cloud Document

In part 1 of Edit Distance we learned how to code the distance metric and the corresponding NNG (Nearest Neighbor Graph) and conceptualized this graph as a space for the words to reside within. Now in part 2, learn how to code to extend this NNG into a Path Category NNG and construct codexplanations for the properties of a category. Finally we learn to construct an EndoFunctor called StringTrim, from the new word-Path category to itself, such that its Identity Natural Transformation is actually a single familiar computational function which trims off repeated tokens from the beginning and the end of a word. We hope the programmers can code a Eureka moment to understand that all that which we program are actually natural transformations between some categories.

codexplain: code explain as in explain something by its construction code.

Part 2: NNG graph of words with Edit Distance form a Path Category

 To find hidden scripts, click on either vertical bars to toggle to view or hide the code. See below.

In[]:=

Clear[editDistance];myEditDistance[s0_,t0_]:=Module[{m,n,s,t,d,d2,substitutionCost},(*foralliandj,d[i,j]willholdthedistancebetweenthefirsticharactersofsandthefirstjcharactersoftnotethatdhas(m+1)*(n+1)values*)m=StringLength[s0];n=StringLength[t0];d=ConstantArray[0,{m+1,n+1}];(*1-indexedarrays*)s=StringSplit[s0,""];t=StringSplit[t0,""];(*sourceprefixescanbetransformedintoemptystringbydroppingallcharacters*)(*1-indexedmatrix*)Do[d[[i,1]]=i-1,{i,2,m+1}];(*targetprefixescanbereachedfromemptysourceprefixbyinsertingeverycharacter*)Do[d[[1,j]]=j-1,{j,2,n+1}];substitutionCost=0;Do[If[s[[i-1]]==t[[j-1]],substitutionCost=0,substitutionCost=1];d[[i,j]]=Min@{(d[[i-1,j]]+1),(*deletion*)(d[[i,j-1]]+1),(*insertion*)(d[[i-1,j-1]]+substitutionCost)(*substitution*)},{j,2,n+1},{i,2,m+1}];d2=Prepend[Transpose@d,Join[{""},StringSplit[s0,""]]];d2=Prepend[Transpose@d2,Join[{"",""},StringSplit[t0,""]]];d2[[Dimensions[d2][[1]],Dimensions[d2][[2]]]]=(Highlighted@d2[[Dimensions[d2][[1]],Dimensions[d2][[2]]]]);Clear[];=d2//MatrixForm;d[[m+1,n+1]]];

NearestNeighborGraph[ ]

Words, and their similars reside in graphs called the Nearest Neighbor Graphs (NNG) [3]. Let us construct one for one single base word namely

"mesh"

(*CommentouttheSeedRandomtovariatethewordselections*)SeedRandom[ToString@myEditDistance];dict=DeleteDuplicates@Join[RandomSample[Nearest[DictionaryLookup[]]["mesh",1000],10],{"mesh","me"}];nng=NearestNeighborGraph[dict,{3,3},VertexLabels->"Name",DistanceFunction->myEditDistance,ImageSize->500,DirectedEdgesTrue,GraphLayout->{"SpringEmbedding","Rotation"0Degree}]

Out[]=

In[]:=

edges=EdgeList@nng

Out[]=

{dimesekes,dimesmesh,dimesme,beyseff,beysheed,beysbean,effbeys,effheed,effgas,heedbeys,heedmend,heedheap,gasbeys,gaseff,gasheap,mendheed,mendmesh,mendme,heapbeys,heapheed,heapbean,mushedmesh,beanbeys,beaneff,beanheap,ekesdimes,ekesbeys,ekeseff,meshdimes,meshmend,meshme,medimes,memend,memesh}

In[]:=

nnglables=Table[edges[[i]]Subscript["→",i],{i,1,Length@edges}]

Out[]=

{dimesekes

→

,dimesmesh

→

,dimesme

→

,beyseff

→

,beysheed

→

,beysbean

→

,effbeys

→

,effheed

→

,effgas

→

,heedbeys

→

,heedmend

→

,heedheap

→

,gasbeys

→

,gaseff

→

,gasheap

→

,mendheed

→

,mendmesh

→

,mendme

→

,heapbeys

→

,heapheed

→

,heapbean

→

,mushedmesh

→

,beanbeys

→

,beaneff

→

,beanheap

→

,ekesdimes

→

,ekesbeys

→

,ekeseff

→

,meshdimes

→

,meshmend

→

,meshme

→

,medimes

→

,memend

→

,memesh

→

}

In[]:=

nng2=Graph[DeleteDuplicates@Flatten@Map[{#[[1]],#[[2]]}&,edges],edges,VertexLabels->"Name",EdgeLabelsnnglables,GraphLayout->{"SpringEmbedding","Rotation"0Degree},ImageSize->550]

Out[]=

Q: Why

"mushed"

has no incoming edges/arrows?

Write a tiny bit of code to codexplanation the answer this question:

In[]:=

VertexInComponent[nng,{"mushed"},{1}]

Out[]=

{}

codexplain: code explain as in explain something with its construction code.

In[]:=

VertexOutComponent[nng,{"mushed"},{1}]

Out[]=

{mesh}

● Recall the definition of an edge between two vertices in a NNG graph:

NearestNeighborGraph

[{

elem

,…},{k,r}]

gives a graph connecting each vertex

elem

to at most

nearest vertices within the radius

elem

.
In our case:

NearestNeighborGraph[dict,{3,3}...withk=3andr=3

.

K: refers to the number of edges in a path in the NNG graph and has no idea about the myEditDistance [ ] metric.
r : refers to the distance computed by myEditDistance [ ] metric, in this case between two vertices.

Now compute the distance metric between the

"mushed"and"mesh"

In[]:=

myEditDistance["mushed","mesh"]

Out[]=

This number is less than or equal to

r=3

therefore there is an edge extended from

"mushed"to"mesh"

Now the other way around compute the distance between the

"mesh"and"mushed"

In[]:=

myEditDistance["mesh","mushed"]

Out[]=

Huh? The same number 3 so why there is there no edge extended from

"mesh"to"mushed"

?! While the radius is valid for an edge the requirement for the

nearest vertices is not valid for

"mesh"

since it has already been assigned 3 immediate neighbors

"me","mend","dimes"

and no more neighbors are allowed:

In[]:=

VertexOutComponent[nng,{"mesh"},{1}]

{1} here indicates the distance in the number of edges in nng.

and the particular implementation of the NNG used these 3 and discarded the rest.

Visualizations: Subgraphs

Visualizations: Paths

Visualizations: All Path between two vertices

Categorification

Digression: T, ξ

Example

The usual bracketed expressions:

Why? Move away from Function Paradigm

This is how a Piecewise [ ] function is used; try to use it for hundreds to thousands of terms e.g. solutions to FEM equations:

Vector Dot Product Paradigm

Compute two vectors 1 and v2:

Compute their dot product and that computes an algebraic product like version of the piecewise function!

Mecha Ref[13].

Let us codexplain a few examples.

ξ : Expressions

ξ : Strings

● You already know these functions in Wolfram programming language namely for Expressions or Strings:

T is Level[ ] or StringSplit[ ]
ξ is Total[ ] or StringJoin[ ]

Write a bit of code to study ϕ :

● For strings we introduce a bit of tease which surprisingly is not provided in the Wolfram language! As it should have been:

Treat String like an Array

NNG Categorification: Path Category

Example

Sample Morphisms (paths)

Composition

Bird’s Eye View

Corollary: myEditDistance [ ] metric and corresponding NNG graph form a Path Category.

● This indicates that these particular Path Categories are similar structures appearing independent of how the strings and their metrics were defined.

● Post construction, the sets actually do not play any roles.

We call this categorification of words.

Functors

● A Functor, between two categories, is a tuple of two maps which combined serve similar to a homomorphism, preserving the similarities between two categories

● An EndoFunctor, from a category to itself, preserves the self-similarity or the category’s inner-symmetries

Definition

● The object function F which assigns to each object X of C an object F(X) of D

η Natural Transformations: StringTrim[ ]

Identity Natural Transformation

You might note the path or morphism is shrunken