Weighted Prefix Search | DSA in C++ - Software Development PDF Download

Introduction

Weighted prefix search is a powerful algorithm that allows you to efficiently search for strings based on their prefixes while considering weights assigned to each string. This article will provide a step-by-step explanation of weighted prefix search, along with code examples in C++ to help beginners understand and implement this algorithm.

What is Weighted Prefix Search?

Weighted prefix search is a technique used to efficiently search for strings based on their prefixes while taking into account the weights associated with each string. It is commonly used in applications such as autocomplete suggestions, spell checkers, and search engines.
The algorithm uses a data structure called a trie, which organizes the strings in a tree-like structure. Each node in the trie represents a prefix, and the edges connecting the nodes represent individual characters. By traversing the trie, we can find all the strings that match a given prefix and retrieve them in a weighted order.

Implementation in C++

Trie Data Structure

To implement weighted prefix search, we first need to construct a trie data structure. A trie consists of nodes, where each node contains a character, a flag to mark the end of a string, a weight value, and pointers to its child nodes.

Here's a simplified implementation of the TrieNode structure in C++:

struct TrieNode {

    bool isEndOfWord;

    int weight;

    unordered_map<char, TrieNode*> children;

};

Weighted Prefix Search Algorithm

The weighted prefix search algorithm involves the following steps:

• Build a trie by inserting strings along with their associated weights.
• Traverse the trie based on the given prefix, collecting all the matching strings and their weights.
• Sort the collected strings based on their weights in descending order.
• Return the sorted list of strings.

Code Examples:

Building a Trie

Let's start by implementing a function to insert strings into a trie:

void insertString(TrieNode* root, const string& word, int weight) {

    TrieNode* current = root;

    for (char ch : word) {

        if (!current->children[ch]) {

            current->children[ch] = new TrieNode();

        }

        current = current->children[ch];

    }

    current->isEndOfWord = true;

    current->weight = weight;

}

Performing a Weighted Prefix Search

Now, let's implement the weighted prefix search algorithm:

vector<pair<string, int>> weightedPrefixSearch(TrieNode* root, const string& prefix) {

    vector<pair<string, int>> results;

    TrieNode* current = root;

    // Traverse the trie based on the prefix

    for (char ch : prefix) {

        if (!current->children[ch]) {

            return results; // No matching strings found

        }

        current = current->children[ch];

    }

    // Collect all matching strings and their weights

    if (current->isEndOfWord) {

        results.push_back({prefix, current->weight});

    }

    for (auto& [ch, child] : current->children) {

        string currentPrefix = prefix + ch;

        vector<pair<string, int>> childResults = weightedPrefixSearch(child, currentPrefix);

        results.insert(results.end(), childResults.begin(), childResults.end());

    }

    // Sort results based on weights in descending order

    sort(results.begin(), results.end(), [](const auto& a, const auto& b) {

        return a.second > b.second;

    });

    return results;

}

Sample Problems with Solutions

Problem 1: Given a list of cities and their populations, perform a weighted prefix search to find cities with a population greater than a given threshold.

int main() {

    TrieNode* root = new TrieNode();

    // Insert cities and their populations into the trie

    insertString(root, "New York", 8537673);

    insertString(root, "Los Angeles", 3979576);

    insertString(root, "Chicago", 2693976);

    insertString(root, "Houston", 2320268);

    // Perform weighted prefix search

    string prefix = "N";

    int populationThreshold = 3000000;

    vector<pair<string, int>> results = weightedPrefixSearch(root, prefix);

    // Display cities with a population greater than the threshold

    for (const auto& result : results) {

        if (result.second > populationThreshold) {

            cout << result.first << ": " << result.second << endl;

        }

    }

    return 0;

}

Output:

New York: 8537673

Conclusion

Weighted prefix search is a useful algorithm for efficiently searching for strings based on prefixes while considering associated weights. By utilizing the trie data structure and a step-by-step approach, we can implement this algorithm in C++. With the provided code examples and explanations, beginners can now understand and apply weighted prefix search in their own projects.