Category: Information Technology

DISCO, European Dictionary of Skills and Competences, offers the user a tree to be searched or browsed. Inspecting the tree nodes, we see that concepts are contained in LI elements with an liItem class. Executing $(‘.liItem’).length in the console we get 676. They claim instead to collect more than 104000 concepts. A bold claim?

A better look at the tree structure reveals that some concepts have a data-loaded attribute set to true and some set to false. In particular, true denotes readily available nodes (downloaded with the initial page load) and false denotes nodes that require an AJAX call before being displayed. Leaf nodes are always of the former kind, but internal nodes can be of both kinds. Would we get those 104000 concepts if we unfolded all the false nodes?

We’ll try. Along the way we’ll also store all nodes into a different structure, something more portable than bare HTML. JSON seems a good option. Ironically, DISCO uses getJSON to download HTML snippets. To summarize, we are now going to store all the HTML tree of DISCO into a JSON structure.

As you probably understood by reading some of my last articles, I had decided to scrape the DISCO tree by means of the support provided by jsFiddle. That was before I discovered the existence of Custom JavaScript Snippets in Google Chrome Developer Tools. Apparently they’ve been there for quite some time, now almost two years !

Too bad for me. At least it was fun to make DISCO’s page behave outside of DISCO’s server.

Here is the snippet I came up with:

{[ .snippet | 1.hilite(=javascript=) ]}

There are only a few things to note:

• I’ve put a limit as a guard to safely try things out
  • with recursive structures –like trees– it’s very useful to limit actions to a small amount of nodes before going full monty
  • this limit is just how many nodes to visit, you can start with a low number like 20 or 50 and see how it works
  • you should get quite a long list of messages output to the console, and if all was fine, the last message will be the result
• The result is a hash of node ids as keys and node objects as values
  • for example, window.disco.nodes[16901] is
    {[ .node | 1.hilite(=javascript=) ]}
    which corresponds to this node in DISCO’s page
    
• The functions download(node) and download_children(node, children) are mutually recursive
  • their arguments are coherent, i.e. node is an LI element and children is an array of LI elements
  • the latter is not integrated into the former because we need to provide the same treatment to both children readily available and those that will be in the future
  • they start visiting from the two roots –horizontal_skills and vertical_skills– and drill down into the tree structure
• The UI is never updated by the snippet, instead all the state is automatically kept in memory by the recursive descent
  • if you unfolded aesthetic sensitivity (node 16091) in the tree yourself between two executions with a small number of nodes (say 20), you’d get two different results
  • the first result would (probably) not show aesthetic sensitivity children while the second result would (probably) not show the last two nodes of the first result, thus keeping the number of nodes stuck to the given limit
  • if you want to go back to the initial mint state, a simple reloading won’t be enough without deleting first the session cookie
• Finally, you can run JSON.stringify(window.disco) and get a nice JSON string which you can copy and paste somewhere and save to a file
  • the hash to string conversion is gonna need some minutes… so many in fact that I left the browser working “indefinitely” (half an hour?)
  • the resulting string is humungous too: 3.785.133 bytes (3,8 MB on disk).

Conclusions

The execution of the above snippet with a limit of 105000 nodes takes around 3 minutes on my MacBook Air with 4GB RAM. At the end, you’ll discover that the last node was number 7380 !!

Wow, that’s a huge difference from the claimed “more than 104000 concepts”. How can it be?

Even considering that they provide a multilingual thesauri with 11 languages and they could have inflated 7380 * 11 times = 81180, there is still around 28% of missing concepts. Could they have added the number of phrases? No, because they separately claim “approximately 36000 example phrases”. They could have instead added the number of synonyms.

{[ .synonyms | 1.hilite(=javascript=) ]}

Running the above code we get 3443 synonyms, which added to 7380 concepts make for 10823 terms, which inflated 11 times make for 119053 terms in all languages.

• 7380 * 11 + 3443 + X * 10 = 104000
• X = (104000 – 84623) / 10
• X = 1937.7 = 56% * 3443 = 26% * 7380

Hm, I don’t know. It seems to me that they “confused” concepts with terms and at the same time, while English synonyms count is around 47% of concepts, in all other languages synonyms count is around 26% of concepts, which is ostensibly much less.

All in all, 7380 concepts is a good number but it’s only the 7% of what they claim.

Trees have funny definitions like this:

A tree is either nothing or something creating more trees.

Here is some terminology.

Node.	A structure holding some data.
Edge.	A connection from a parent node to a child node.
Parent of a node X.	Any node that creates X.
Child of a node X.	Any node that is created by X.
Degree of a node X.	Number of children of X.
Sibling of a node X.	Any node which is another child of a parent of X.
Ancestor of a node X.	Any node that is a parent of X or an ancestor of a parent of X.
Descendant of a node X.	Any node that is a child of X or a descendant of a child of X.
Root node.	Any node without parents.
Leaf node.	Any node without children.
Internal node.	Any node which is not a root nor a leaf.
Level of a node X.	1 + Number of edges from a root to X.
Height of a node X.	Number of edges from X to a leaf.

We call simple trees those trees where there is only one root and all other nodes have only one parent. There are many things that would be better represented by trees with multiple roots and multiple parents. Unfortunately their complexity is not really different from directed acyclic graphs, so the former are seen as a special case of the latter and treated accordingly.

Building

In JavaScript, we can build simple trees like this:

{[ .creation | 1.hilite(=javascript=) ]}

whose console output is:

Usually we create trees for storing data together with their hierarchical relationships to other data. For example, a thesaurus easily fits into a tree. In fact, we can even define a thesaurus as a tree-like structure:

A thesaurus is either nothing or something creating a narrower thesaurus, and relating to some other thesaurus.

Thus a thesaurus is just a tree together with an additional generic relationship between its nodes.

Traversing

A tree traversal is maybe the most common operation for a tree, regarded as a collection of nodes. Each node is visited once, and there are many possible ways to do it orderly. One of the most common ways is to traverse in depth first order, i.e. starting from the root, we visit a node and each of its children. For example, in our tree (1(2(5,6),3,4(7))), a depth first traversal would visit in order: 1,2,5,6,3,4,7. It’s easy to understand why it’s a very common traversal. It’s not a coincidence that the order is the same we would get by erasing the structure.

Here is a bit of JavaScript code for traversing a tree in depth first order.

{[ .traversal-each| 1.hilite(=javascript=) ]}

The console output is:

Mapping

There are many possible things we can do while traversing a tree. One of the most common is to map nodes’ contents to some transformation so that we get another tree with same structure but different data.

Here is an updated version of TreeTraversal with a new map method.

{[ .traversal-map| 1.hilite(=javascript=) ]}

The console output is exactly the same as the one we got when building tree.

Note that both .each() and .map() of TreeTraversal share the same signature and functionality with .each() and .map() of jQuery respectively.

Here is a jsFiddle if you want to play around.