The theoretical situation is this:
Let’s say that we have a digital dictionary (by which I mean a traditional list of words and definitions, not an associative array). For the sake of simplicity, let’s also say that each word can be replaced by its exact definition, and still make sense in a sentence; for example, if this dictionary holds the definition of the word “ocean” to be “large body of salt water”, then the following passage:
"We ourselves feel that what we are doing is just a drop in the ocean."
could be modified to:
"We ourselves feel that what we are doing is just a drop in the large body of salt water."
without any loss of logic or meaning. Now my question is this: given a dictionary with all of the words in the English language, what is an algorithm that could be applied to compress the dictionary, through the replacement of all the occurrences of a given word with its definition, and in doing so find a base set of words through which all of the meanings of the original language could be expressed?
To clarify even more; if “sadness” is defined as “an unhappy emotion”, then the word sadness can be completely removed from the dictionary by replacing all instances of the word “sadness” that occur in the definitions of other words with its definition. The definition of “depression”, for example, might change from “a sustained period of sadness” to “a sustained period of an unhappy emotion”. In this way, the algorithm would eventually arrive at a base set of words from which all other words could be represented.
Are there any algorithms that exist that can do this, or something similar? How might this be done programmatically, without using brute force? Any insight is appreciated.
2
You can model this is a directed graph. Each vertex in the graph represents a word, an outgoing edge represents the words used to define the word, and an incoming edge represents other words that uses this word in their definition.
You can eliminate non-recursive vertex by connecting the vertices from incoming edges to the vertices in the outgoing edges. In pseudocode:
all_words = ...
current = select_node_to_eliminate(all_words)
for n1 in current.incoming_edges:
for n2 in current.outgoing_edges:
if n1 != n2:
add_edge(n1, n2)
remove_edge(n1, current)
remove_edge(current, n2)
if len(current.incoming_edges) == 0 and len(current.outoing_edges) == 0:
all_words.remove(current)
The problem is that the end result of “a base set of words from which all other words could be represented” would be highly dependent on how you write select_node_to_eliminate().
You would need to define additional criteria for “minimal dictionary”. Do you want the smallest dictionary as in the smallest number of words, even at the cost of lengthy, incomprehensible definitions; or do you want to include the size of the definitions when calculating the size of the dictionary.