Hi everyone, I am working on a project that requires me to write a program which given a single word will search a database of thousands of songs and will return the artist, title, and the context in which the word appears in the song. Each song has a SongId and other meta data details and the whole database is in the form of one huge text file with a single space between two songs. I have attached an example.
I am attaching the header and cpp file containing my code to sift through the database.I have come up with a design that uses patricia trie containing all the words and array/linked list which contains all the song ids with each word in the tree referring to the SongId(s) in linked list/array that contains that word. I was also contemplating using a hash table as the song database is static. For the patricia trie I have two more linked lists containing maps of the nodes of the trees with the information regarding if the given node is a leaf or not and if it is an internal node how many eliminated nodes (as it is a patricia trie) does it store. I then intent to do a binary search on this structure to make the search even faster. I am attaching the code to my patricia tree too.
I think I know how my code is going to work but am having trouble implementing it beyond a point. I am in a roadblock and am not able to bring everything together. Hence I would truly appreciate if someone can help me with this.
Let me know if there's any other info that you want. Alternative ideas of the algorithm are welcome, though I am heavily constrained by time.