CODEWITHSUNDEEP
databasestringsearchdata-structuresprefix
Raj Vichare
Raj Vichare

Reputation: 19

What is the most suitable data structure for efficient prefix searching?

I am working on a database for songs. So I'm thinking of creating a data structure which will store all the songs as strings. The operations that will be performed are insert, delete, update and search(full and prefix). But I'm confused as to which is the best data structure for prefix searching.

Upvotes: 1

Views: 286

Answers (1)

Rubén Colomina Citoler
Rubén Colomina Citoler

Reputation: 95

A simple data structure you may use are generic N-ary trees, in order to perform prefix searching.

These have O(log(N)) in theory, with N the length of characters of the string to search.

Notice that in your case, due to N is normally small, because you store song titles, you actually will end up having constant access O(1) as a hash table.

As follows, an example of the C-struct to store your data:

//Node declaration
struct Node{
   int data;
   vector<Node*> children;
}

Now, let's see what we will get for a real list of song titles:

"Alarm - Single - Anne-Marie" "Alejandro - Lady Gaga" "All My Life - Foo Fighters" "American Idiot - Green Day" "Beat it - Michael Jackson" "Black in Black - AD/DC"

The list of songs of above the structure will be stored as a N-ary try as follows:

"Root" -> ["a" -> 
               ["l" -> 
                    [
                     "a" -> "Alarm - Single - Anne-Marie",
                     "e" -> "Alejandro - Lady Gaga",
                     "l" -> "All My Life - Foo Fighters"
                    ]
               ]
           ]
           "b" -> 
               [
                "e" -> "Beat it - Michael Jackson",
                "l" -> "Black in Black - AD/DC" 
               ]
         ]

This struct covers both cases, full and prefix search in very efficient manner. due to assumption on title songs length

With that struct, you may implement a program to list all songs starting with a prefix. On the example of above

"al" -> ["Alarm - Single - Anne-Marie"
"Alejandro - Lady Gaga"
"All My Life - Foo Fighters"]

You should limit the number of outcomes, if you plan to put this on a user interface. As soon as the user starts typing, you can already present results on the fly.

Upvotes: 1

Related Questions