Closest match algorithm for strings/sentences not working?

Question

I wrote a program that takes a question from a user. It then matches that question with a list of pre-defined questions and returns an answer. It is supposed to be accurate and match only with questions that are close to (fuzzy matches) or exactly what the user entered.

My SSSCE:

http://ideone.com/JTcF73

The code:

#include <iostream>
#include <cstdint>
#include <algorithm>
#include <numeric>
#include <functional>

int min_index(const std::vector<int>& list)
{
    int index = 0;
    int smallest = list[0];

    for (size_t i = 0; i < list.size(); ++i) {
        if (list[i] < smallest) {
            smallest = list[i];
            index = i;
        }
    }
    return index;
}

std::uint32_t LevenshteinDistance(const std::string &First, const std::string &Second)
{
    const std::size_t FirstLength = First.size();
    const std::size_t SecondLength = Second.size();

    std::vector<std::uint32_t> Current(SecondLength + 1);
    std::vector<std::uint32_t> Previous(SecondLength + 1);

    std::size_t I = 0;
    std::generate(Previous.begin(), Previous.end(), [&] {return I++; });

    for (I = 0; I < FirstLength; ++I)
    {
        Current[0] = I + 1;

        for (std::size_t J = 0; J < SecondLength; ++J)
        {
            auto Cost = First[I] == Second[J] ? 0 : 1;
            Current[J + 1] = std::min(std::min(Current[J] + 1, Previous[J + 1] + 1), Previous[J] + Cost);
        }

        Current.swap(Previous);
    }
    return Previous[SecondLength];
}

std::vector<std::string> questions = 
{
    "What is the most popular program at GBC?",
    "How much is the tuition at GBC?",
    "Do I have to pay my fees before I can register?",
    "What are my fee payment options?",
    "How do I know when I'm allowed to register?",
    "How do I add and/or drop courses from my timetable?",
    "What do I do if I can't find my PASSWORD?",
    "How do I withdraw from a program?",
    "What are the college policies?",
    "How much math do I need to know?",
    "What is the program code for computer programming?",
    "What is stu-view?",
    "What is the college best known for?",
    "How easy is it to find work after program completion?",
    "What if I plan to continue my education after?"
};

std::vector<std::string> answers =
{
    "Fashion",
    "3000 a semester",
    "Yes you have to pay the fees before registering",
    "You may pay online on your student account through the student portal",
    "You may register two weeks or more before the start of the program",
    "You may drop courses from online through the student portal",
    "You can call ... and an agent will assist you",
    "You may withdraw using the student portal online",
    "They are located at the following link...",
    "It depends on the program you are entering",
    "T127 is the code for computer science",
    "Stu-View is a student portal to manage student account and view marks.",
    "The cafeteria food",
    "Depends on the field of work and timing",
    "You may do so within three years after program completion"
};

int main()
{
    std::string user_question = "program";

    std::vector<int> distances = std::vector<int>(questions.size(), 0);

    for (size_t I = 0; I < questions.size(); ++I)
    {
        int dist = LevenshteinDistance(user_question, questions[I]);
        distances[I] = dist;
    }

    std::cout<<"Distance:      "<<distances[min_index(distances)]<<"\n";
    std::cout<<"User-Question: "<<user_question<<"\n";
    std::cout<<"Question-Key:  "<<questions[min_index(distances)]<<"\n";
    std::cout<<"Answer-Value:  "<<answers[min_index(distances)]<<"\n";

    return 0;
}

So in the above, the user enters "program".. It is supposed to find the closest match from the list of questions and return the corresponding answer..

However, it prints:

Distance:      17
User-Question: program
Question-Key:  What is stu-view?
Answer-Value:  Stu-View is a student portal to manage student account and view marks.

It should have had way better results or accuracy but it doesn't seem to care whether or not a sentence has the keywords the user entered :S It works for small cases but for a large database or the above where there is more than 5 sentences, it has a hard time.. Especially with little keywords ;l

What am I doing wrong? Any ideas how I can fix it and make it more accurate? I tried HammingDistance, similar results..

Answer 1

Both "program" and "What is stu-view?" are quite short compared to the other strings. It's easier to transform "program" to "What is stu-view?" than to transform "program" to "What is the most popular program at GBC?" despite the fact that the word "program" is common.

What am I doing wrong?

I don't think you're doing something wrong. If you're not satisfied with the result, this means that your current formalism (minimizing the Levenshtein distance) is not the one you want.

You can go for more local solutions: e.g. Tokenizing the strings, compute pairwise Levenshtein distance between the words then merge the results (average, sup inf...)

Better solutions would require doing some bibliography (probably the unsupervised machine learning topic)