0 Replies - 579 Views - Last Post: 04 May 2010 - 03:02 PM Rate Topic: -----

#1 C++AsASecondLanguage  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 04-May 10

Full text search using Patricia tree with meta-data on a song database

Posted 04 May 2010 - 03:02 PM

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.

Attached File  Databaseapicode.zip (1.05K)
Number of downloads: 133
Attached File  PTree.zip (1.45K)
Number of downloads: 85

Is This A Good Question/Topic? 0
  • +

Page 1 of 1