Re: [Sheflug] Weird algorithm question

[Adam Funk <a.funk@xxxxxxxxxxxxxx>]

[25/06/10 16:37] Adam Funk wrote:

(hyponym chains)

> I also posted this to the corpora mailing list (related to natural
> language processing) and got some interesting suggestions about graph
> search algorithms.
> 
> I'll post my conclusions when I get this sorted out, in case anyone is
> interested.

It turned out not to be too difficult, once I approached it as a graph
problem.  I wrote a Java program to read all the lines in and represent
the data a Set<Node>, where each Node has a name and a set of parent and
daughter nodes.  Then it found the roots (nodes with no parents) and for
each one, recursively extended chains with all possible daughters of the
tail end.  It ran in a few seconds and the results look right.

Interestingly, I found 45 chains that had "loops" in them (I planned for
this, and the program stops extending a chain when it adds a node that
is already higher up the chain), and they all refer to one circularity
in WordNet (inhibit -> restrain -> inhibit), which someone on the corpus
linguistics list had mentioned as an example.

_______________________________________________
Sheffield Linux User's Group
http://sheflug.org.uk/mailman/listinfo/sheflug_sheflug.org.uk
FAQ at: http://www.sheflug.org.uk/mailfaq.html

GNU - The Choice of a Complete Generation