c++ - 字符串/句子的最接近匹配算法不起作用？

Question

我编写了一个程序来接受用户的问题。然后它将该问题与预定义问题列表匹配并返回答案。它应该是准确的，并且只与接近(模糊匹配)或与用户输入的内容完全匹配的问题匹配。

我的 SSSCE:

http://ideone.com/JTcF73

代码:

#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;
}

所以在上面，用户输入“程序”..它应该从问题列表中找到最接近的匹配并返回相应的答案..

但是，它打印:

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.

它应该有更好的结果或准确性，但它似乎并不关心一个句子是否包含用户输入的关键字 :S 它适用于小案例，但适用于大型数据库或上面有更多超过 5 个句子，很难.. 尤其是关键字很少;l

我做错了什么？有什么想法可以修复它并使其更准确吗？我尝试了 HammingDistance，类似的结果..

Answer 1

与其他字符串相比，"program" 和"What is stu-view?" 都非常短。将 "program" 转换为 "What is stu-view?" 比将 "program" 转换为 "What is 更容易GBC 上最受欢迎的程序？” 尽管 “程序” 这个词很常见。

What am I doing wrong?

我不认为你做错了什么。如果您对结果不满意，这意味着您当前的形式主义(最小化 Levenshtein 距离)不是您想要的。

您可以寻求更多本地解决方案:例如标记字符串，计算单词之间的成对 Levenshtein 距离，然后合并结果(平均，sup inf ...)

更好的解决方案需要做一些引用书目(可能是无监督机器学习主题)