News for hackers. Stuff that matters.

A comment on What's the minimum number of words you'd need to define all other words? (2012).

Re:What's the minimum number of words you'd need to define a... by fginionio on Thursday March 07, 2019 @03:31PM (#19332041)
I think the approach I would use is as follows:

0. Get a dictionary.

1. Form a directed graph, with an edge from each word to every word that uses that word in its definition.

2. Remove all words that have no outgoing edges.

3. If you removed some words, go to step 1. Otherwise, all words left in the dictionary are minimal.

EDIT: If anyone knows of a machine-readable dictionary, I'd love to actually do this.

[ Parent | on HN ]
Re:What's the minimum number of words you'd need to define a... by hairtuq on Thursday March 07, 2019 @04:24PM (#19332621)
This will not yield a minimal set; in a cycle, it is only necessary to remove at least one word. The problem is thus to delete the minimum number of vertices to remove all cycles. This is the NP-hard Feedback Vertex Set problem. Here's a paper that solves it for a dictionary (there is some more): https://arxiv.org/abs/0911.5703
[ Parent | on HN ]
Re:What's the minimum number of words you'd need to define a... by titanix2 on Thursday March 07, 2019 @05:39PM (#19333319)
I checked the comments to check if this paper was mentioned anywhere. Good recommendation.
[ Parent | on HN ]
Re:What's the minimum number of words you'd need to define a... by fginionio on Thursday March 07, 2019 @04:45PM (#19332805)
Looks like you found our answer! Someone's already done the hard work.
[ Parent | on HN ]
Re:What's the minimum number of words you'd need to define a... by zuminator on Thursday March 07, 2019 @06:19PM (#19333659)
This is not necessarily the answer. It's an upper-bound for the answer.
[ Parent | on HN ]
Re:What's the minimum number of words you'd need to define a... by heyitsguay on Thursday March 07, 2019 @04:26PM (#19332635)
Looks like somebody made txt and json versions of the Oxford Unabridged English Dictionary here: https://github.com/adambom/dictionary. The json version should let build up the graph structures you're talking about pretty easily.
[ Parent | on HN ]
Re:What's the minimum number of words you'd need to define a... by excalibur on Thursday March 07, 2019 @03:41PM (#19332133)
But you will come across a lot of words used in definitions that could easily be replaced with more common words. In some cases the change to the definition would be tiny, in others it might be more significant.
[ Parent | on HN ]
Re:What's the minimum number of words you'd need to define a... by cpeterso on Thursday March 07, 2019 @03:55PM (#19332295)
I'd like to see a DAG of WordNet, a database of English synonyms. Mapping single word synonyms solves the problem of common words in definitions.

https://en.wikipedia.org/wiki/WordNet

[ Parent | on HN ]
Re:What's the minimum number of words you'd need to define a... by rijoja on Friday March 08, 2019 @07:17AM (#19336886)
Came here to say exactly the same! Great minds think alike!
[ Parent | on HN ]
Re:What's the minimum number of words you'd need to define a... by oh_sigh on Thursday March 07, 2019 @03:52PM (#19332262)
It seems like a good start. Once you do that, you could start finding vertices with large amounts of incoming edges, attempt to redefine the word as a phrase composed of only words still in the graph, remove that vertex, and repeat.
[ Parent | on HN ]
Re:What's the minimum number of words you'd need to define a... by clhodapp on Thursday March 07, 2019 @03:58PM (#19332347)
That will get you much closer but it does ignore the ability to apply creativity to definitions to further reduce them. In the end, a machine-driven technique can give an approximate answer to this problem but it will never be the "perfect" answer.
[ Parent | on HN ]
Re:What's the minimum number of words you'd need to define a... by xiler on Thursday March 07, 2019 @04:04PM (#19332420)
You could try this using WordNet

https://wordnet.princeton.edu/

[ Parent | on HN ]
Re:What's the minimum number of words you'd need to define a... by rasz on Thursday March 07, 2019 @04:47PM (#19332840)
and word2vec
[ Parent | on HN ]
Re:What's the minimum number of words you'd need to define a... by doxos on Thursday March 07, 2019 @04:12PM (#19332502)
Doesn't every word in a given definition have an "outgoing edge?"
[ Parent | on HN ]
Re:What's the minimum number of words you'd need to define a... by fwip on Thursday March 07, 2019 @05:04PM (#19333003)
Yes, but not all words defined in the dictionary are used in a definition.

So if "multitudinous" isn't used in a definition of another word, you remove it from the set. Maybe you then find out that "myriad" was only used in the definition of multitudinous, so you can take myriad out, and so on.

[ Parent | on HN ]