https://drive.google.com/drive/folders/1qbO0qFh09IFlg1AH0a0PUiFu8DWzpP6F
- To store information of “synsets” file :
-
A Dictionary “Words” with a string as a key denoting the word, and a list of integers referring to synsets to which the key string belongs. The Dictionary generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O (1) because the Dictionary class is implemented as a hash table. If Count is less than the capacity, this method approaches an O (1) operation. If the capacity must be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count. “Words” helped us to map nouns to synsets in no time.
-
List of List of strings “Synsets” to keep the words belonging to each synset and it takes time O (1) to be accessed. “Synsets” helped with mapping synsets to nouns in no time.
- To store information of “hypernyms” file:
- List of List of integers “Graph” holding data of each synset, and its root and it takes time O (1) to be accessed. “Graph” helped with the Shortest Common Ancestor (SCA) algorithm.
The total Complexity is O(m) where m is the number of the synsets in the way to root from the current two synsets (as shown in the graph below). The Complexity of calculating SCA and Distance between two nouns using this algorithm will be O(ABm) where A and B are the number of synsets that each noun belongs to.
❖ Efficient Distance and SCA between Two Nouns :
The same Algorithm is used to calculate the SCA for two synsets, the difference is in the initialization step, however, this algorithm takes less time to calculate the Distance and SCA between two nouns than the Efficient SCA. The total Complexity is O(m + A*B) where m is the number of the synsets in the way to root from all the synsets used synsets, and (A, B) are the number of synsets that each noun belongs to.
In each line of the code, there is a comment of its complexity.