5 ms·
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
by fginionio 8y ago
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.
- doxos 8y agoDoesn't every word in a given definition have an "outgoing edge?"
- fwip 8y agoYes, 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.
- excalibur 8y agoBut 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.
- oh_sigh 8y agoIt 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.
- clhodapp 8y agoThat 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.
- cpeterso 8y agoI'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 https://en.wikipedia.org/wiki/WordNet
- rijoja 8y agoCame here to say exactly the same! Great minds think alike!
- xiler 8y agoYou could try this using WordNet https://wordnet.princeton.edu/ https://wordnet.princeton.edu/
- rasz 8y agoand word2vec
- hairtuq 8y agoThis 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 https://arxiv.org/abs/0911.5703
- fginionio 8y agoLooks like you found our answer! Someone's already done the hard work.
- zuminator 8y agoThis is not necessarily the answer. It's an upper-bound for the answer.
- titanix2 8y agoI checked the comments to check if this paper was mentioned anywhere. Good recommendation.
- deleted 8y ago[deleted]
- heyitsguay 8y agoLooks like somebody made txt and json versions of the Oxford Unabridged English Dictionary here: https://github.com/adambom/dictionary https://github.com/adambom/dictionary. The json version should let build up the graph structures you're talking about pretty easily.