如何在C++Map中找到与字符串键最接近的匹配项？

ubof19bj  于 2023-01-15  发布在  其他
关注(0)|答案(1)|浏览(130)

我正在编写一个程序，我想实现的一个特性是一个错误检查类型的东西，如果C++程序在程序中搜索，* 没有 * 找到匹配，它将返回最接近的匹配字符串。
我目前的设置如下所示：

help_data["invite"] = "**How to use?**\n `/invite` - *No other parameters* \n **Purpose** \n To generate an invite for Beyond!";
help_data["help"] = "**How to use?** \n `/help [command]` \n **Purpose** \n To generate an embed on how a specific command works, and its' syntax.";
std::string command = std::get<std::string>(event.get_parameter("command"));
    std::transform(command.begin(), command.end(), command.begin(), ::tolower); //lowercase
    if (help_data.find(command) == help_data.end()) {
        // Not Found
        event.reply(dpp::ir_channel_message_with_source, dpp::message().set_content("Unable to find help data for command `" + command + "`"));
    }
    else {
        // Found
}

谢谢!

c++

1条答案

按热度按时间
wn9m85ua

wn9m85ua1#

    • 第1部分**（见下文第2和第3部分）

正如@BasileStarynkevitch所建议的，可以实现Levenstein distance，它测量两个字符串之间的编辑距离（插入、删除、替换的次数），或者换句话说，两个字符串有多相似，Levenstein距离的值越接近0，相似的字符串越多。
刚才我用C++从头开始实现了这个距离计算，并展示了一个使用这个距离函数在给定的字符串中找到与查询字符串最接近的字符串的例子。
函数Levenstein()根据Wikipedia实现（链接见上），并且不是为了便于阅读和理解而优化的，只是为了教育目的。在生产代码中使用Memoization技术可以使它更快（缓存相同函数调用结果），因为正如您所看到的，对于较大的字符串，我的实现将相当慢，对于相同的两个字符串，它将执行大量冗余的相同函数调用。另一种加速计算的方法是使用Dynamic programming方法来缓存和重用数组中以前的结果。
Try it online!

#include <string>
#include <string_view>
#include <algorithm>
#include <vector>
#include <tuple>
#include <iostream>

size_t Levenstein(std::string_view const & a, std::string_view const & b) {
    // https://en.wikipedia.org/wiki/Levenshtein_distance
    if (b.size() == 0)
        return a.size();
    if (a.size() == 0)
        return b.size();
    if (a[0] == b[0])
        return Levenstein(a.substr(1), b.substr(1));
    return 1 + std::min(
        std::min(
            Levenstein(a          , b.substr(1)),
            Levenstein(a.substr(1), b          )
        ),  Levenstein(a.substr(1), b.substr(1))
    );
}

std::tuple<size_t, size_t> FindClosest(
        std::vector<std::string> const & strs, std::string const & query) {
    size_t minv = size_t(-1), mini = size_t(-1);
    for (size_t i = 0; i < strs.size(); ++i) {
        size_t const dist = Levenstein(strs[i], query);
        if (dist < minv) {
            minv = dist;
            mini = i;
        }
    }
    return std::make_tuple(mini, minv);
}

int main() {
    std::vector<std::string> const strs = {"world", "worm", "work"};
    std::string const query = "word";
    auto const [idx, dist] = FindClosest(strs, query);
    std::cout << "Closest to '" << query << "' is '"
        << strs[idx] << "', distance " << dist << std::endl;
}

输出：

Closest to 'word' is 'world', distance 1
    • 第二部分**

正如答案的第1部分所建议的，我决定使用Memoization技术实现Levenstein distance的优化版本，以便在数组中存储和重用相同的结果。
这个版本有点难理解，读起来也比较长，但是运行起来要快得多。
Try it online!

#include <string>
#include <string_view>
#include <algorithm>
#include <vector>
#include <tuple>
#include <iostream>
#include <functional>

size_t Levenstein(std::string_view const & a, std::string_view const & b) {
    // https://en.wikipedia.org/wiki/Levenshtein_distance
    std::vector<size_t> d_((a.size() + 1) * (b.size() + 1), size_t(-1));
    auto d = [&](size_t ia, size_t ib) -> size_t & {
        return d_[ia * (b.size() + 1) + ib];
    };
    std::function<size_t(size_t, size_t)> LevensteinInt =
        [&](size_t ia, size_t ib) -> size_t {
            if (d(ia, ib) != size_t(-1))
                return d(ia, ib);
            size_t dist = 0;
            if (ib >= b.size())
                dist = a.size() - ia;
            else if (ia >= a.size())
                dist = b.size() - ib;
            else if (a[ia] == b[ib])
                dist = LevensteinInt(ia + 1, ib + 1);
            else
                dist = 1 + std::min(
                    std::min(
                        LevensteinInt(ia,     ib + 1),
                        LevensteinInt(ia + 1, ib    )
                    ),  LevensteinInt(ia + 1, ib + 1)
                );
            d(ia, ib) = dist;
            return dist;
        };
    return LevensteinInt(0, 0);
}

std::tuple<size_t, size_t> FindClosest(
        std::vector<std::string> const & strs, std::string const & query) {
    size_t minv = size_t(-1), mini = size_t(-1);
    for (size_t i = 0; i < strs.size(); ++i) {
        size_t const dist = Levenstein(strs[i], query);
        if (dist < minv) {
            minv = dist;
            mini = i;
        }
    }
    return std::make_tuple(mini, minv);
}

int main() {
    std::vector<std::string> const strs = {"world", "worm", "work"};
    std::string const query = "word";
    auto const [idx, dist] = FindClosest(strs, query);
    std::cout << "Closest to '" << query << "' is '"
        << strs[idx] << "', distance " << dist << std::endl;
}

输出：

Closest to 'word' is 'world', distance 1
    • 第三部分**

我使用200 most common English words比较了计时。
比较了第1部分和第2部分中的慢速和快速（带记忆）Levenstein实现。
对于5个字母的字符串，慢速版本比快速版本慢8倍，对于10个字母的字符串，慢5000倍，这是非常非常慢的。这种缓慢的发生仅仅是因为许多重复的纯递归性质。
所有计时均低于代码（微秒）。
此外，在这里我提供了完整的代码，没有测量。
Try it online!

#include <string>
#include <string_view>
#include <algorithm>
#include <vector>
#include <tuple>
#include <iostream>
#include <iomanip>
#include <functional>
#include <chrono>

size_t Levenstein(std::string_view const & a, std::string_view const & b) {
    // https://en.wikipedia.org/wiki/Levenshtein_distance
    if (b.size() == 0)
        return a.size();
    if (a.size() == 0)
        return b.size();
    if (a[0] == b[0])
        return Levenstein(a.substr(1), b.substr(1));
    return 1 + std::min(
        std::min(
            Levenstein(a          , b.substr(1)),
            Levenstein(a.substr(1), b          )
        ),  Levenstein(a.substr(1), b.substr(1))
    );
}

size_t LevensteinFast(std::string_view const & a, std::string_view const & b) {
    // https://en.wikipedia.org/wiki/Levenshtein_distance
    thread_local std::vector<size_t> d_;
    d_.clear();
    d_.resize((a.size() + 1) * (b.size() + 1), size_t(-1));
    auto d = [&](size_t ia, size_t ib) -> size_t & {
        return d_[ia * (b.size() + 1) + ib];
    };
    std::function<size_t(size_t, size_t)> LevensteinInt =
        [&](size_t ia, size_t ib) -> size_t {
            if (d(ia, ib) != size_t(-1))
                return d(ia, ib);
            size_t dist = 0;
            if (ib >= b.size())
                dist = a.size() - ia;
            else if (ia >= a.size())
                dist = b.size() - ib;
            else if (a[ia] == b[ib])
                dist = LevensteinInt(ia + 1, ib + 1);
            else
                dist = 1 + std::min(
                    std::min(
                        LevensteinInt(ia,     ib + 1),
                        LevensteinInt(ia + 1, ib    )
                    ),  LevensteinInt(ia + 1, ib + 1)
                );
            d(ia, ib) = dist;
            return dist;
        };
    return LevensteinInt(0, 0);
}

std::tuple<size_t, size_t> FindClosest(std::vector<std::string> const & strs,
        std::string const & query, bool fast = true) {
    size_t minv = size_t(-1), mini = size_t(-1);
    for (size_t i = 0; i < strs.size(); ++i) {
        size_t const dist = (fast ? LevensteinFast : Levenstein)(strs[i], query);
        if (dist < minv) {
            minv = dist;
            mini = i;
        }
    }
    return std::make_tuple(mini, minv);
}

double Time() {
    static auto const gtb = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::duration<double>>(
        std::chrono::high_resolution_clock::now() - gtb).count();
}

int main() {
    // https://1000mostcommonwords.com/1000-most-common-english-words/
    // 600 most common English words
    std::vector<std::string> const strs = {
        "as", "I", "his", "that", "he", "was", "for", "on", "are", "with", "they", "be", "at", "one", "have",
        "this", "from", "by", "hot", "word", "but", "what", "some", "is", "it", "you", "or", "had", "the", "of",
        "to", "and", "a", "in", "we", "can", "out", "other", "were", "which", "do", "their", "time", "if", "will",
        "how", "said", "an", "each", "tell", "does", "set", "three", "want", "air", "well", "also", "play", "small", "end",
        "put", "home", "read", "hand", "port", "large", "spell", "add", "even", "land", "here", "must", "big", "high", "such",
        "follow", "act", "why", "ask", "men", "change", "went", "light", "kind", "off", "need", "house", "picture", "try", "us",
        "again", "animal", "point", "mother", "world", "near", "build", "self", "earth", "father", "any", "new", "work", "part", "take",
        "get", "place", "made", "live", "where", "after", "back", "little", "only", "round", "man", "year", "came", "show", "every",
        "good", "me", "give", "our", "under", "name", "very", "through", "just", "form", "sentence", "great", "think", "say", "help",
        "low", "line", "differ", "turn", "cause", "much", "mean", "before", "move", "right", "boy", "old", "too", "same", "she",
        "all", "there", "when", "up", "use", "your", "way", "about", "many", "then", "them", "write", "would", "like", "so",
        "these", "her", "long", "make", "thing", "see", "him", "two", "has", "look", "more", "day", "could", "go", "come",
        "did", "number", "sound", "no", "most", "people", "my", "over", "know", "water", "than", "call", "first", "who", "may",
        "down", "side", "been", "now", "find", "head", "stand", "own", "page", "should", "country", "found", "answer", "school", "grow",
        "study", "still", "learn", "plant", "cover", "food", "sun", "four", "between", "state", "keep", "eye", "never", "last", "let",
        "thought", "city", "tree", "cross", "farm", "hard", "start", "might", "story", "saw", "far", "sea", "draw", "left", "late",
        "run", "don’t", "while", "press", "close", "night", "real", "life", "few", "north", "book", "carry", "took", "science", "eat",
        "room", "friend", "began", "idea", "fish", "mountain", "stop", "once", "base", "hear", "horse", "cut", "sure", "watch", "color",
        "face", "wood", "main", "open", "seem", "together", "next", "white", "children", "begin", "got", "walk", "example", "ease", "paper",
        "group", "always", "music", "those", "both", "mark", "often", "letter", "until", "mile", "river", "car", "feet", "care", "second",
        "enough", "plain", "girl", "usual", "young", "ready", "above", "ever", "red", "list", "though", "feel", "talk", "bird", "soon",
        "body", "dog", "family", "direct", "pose", "leave", "song", "measure", "door", "product", "black", "short", "numeral", "class", "wind",
        "question", "happen", "complete", "ship", "area", "half", "rock", "order", "fire", "south", "problem", "piece", "told", "knew", "pass",
        "since", "top", "whole", "king", "street", "inch", "multiply", "nothing", "course", "stay", "wheel", "full", "force", "blue", "object",
        "decide", "surface", "deep", "moon", "island", "foot", "system", "busy", "test", "record", "boat", "common", "gold", "possible", "plane",
        "stead", "dry", "wonder", "laugh", "thousand", "ago", "ran", "check", "game", "shape", "equate", "hot", "miss", "brought", "heat",
        "snow", "tire", "bring", "yes", "distant", "fill", "east", "paint", "language", "among", "unit", "power", "town", "fine", "certain",
        "fly", "fall", "lead", "cry", "dark", "machine", "note", "wait", "plan", "figure", "star", "box", "noun", "field", "rest",
        "correct", "able", "pound", "done", "beauty", "drive", "stood", "contain", "front", "teach", "week", "final", "gave", "green", "oh",
        "quick", "develop", "ocean", "warm", "free", "minute", "strong", "special", "mind", "behind", "clear", "tail", "produce", "fact", "space",
        "heard", "best", "hour", "better", "true", "during", "hundred", "five", "remember", "step", "early", "hold", "west", "ground", "interest",
        "reach", "fast", "verb", "sing", "listen", "six", "table", "travel", "less", "morning", "ten", "simple", "several", "vowel", "toward",
        "war", "lay", "against", "pattern", "slow", "center", "love", "person", "money", "serve", "appear", "road", "map", "rain", "rule",
        "govern", "pull", "cold", "notice", "voice", "energy", "hunt", "probable", "bed", "brother", "egg", "ride", "cell", "believe", "perhaps",
        "pick", "sudden", "count", "square", "reason", "length", "represent", "art", "subject", "region", "size", "vary", "settle", "speak", "weight",
        "general", "ice", "matter", "circle", "pair", "include", "divide", "syllable", "felt", "grand", "ball", "yet", "wave", "drop", "heart",
        "am", "present", "heavy", "dance", "engine", "position", "arm", "wide", "sail", "material", "fraction", "forest", "sit", "race", "window",
        "store", "summer", "train", "sleep", "prove", "lone", "leg", "exercise", "wall", "catch", "mount", "wish", "sky", "board", "joy",
        "winter", "sat", "written", "wild", "instrument", "kept", "glass", "grass", "cow", "job", "edge", "sign", "visit", "past", "soft",
        "fun", "bright", "gas", "weather", "month", "million", "bear", "finish", "happy", "hope", "flower", "clothe", "strange", "gone", "trade",
    };
    for (size_t K: {1, 2, 3, 5, 10, 20}) {
        size_t const query_str_cnt = 10, total_str_cnt = 20;
        double avg_len = 0;
        std::vector<std::string> strK;
        for (size_t i = 0; (i + 1) * K <= strs.size(); ++i) {
            std::string s;
            for (size_t j = 0; j < K; ++j)
                s += strs[i * K + j] + " ";
            strK.push_back(s);
            avg_len += s.size();
        }
        avg_len /= strK.size();
        std::vector<std::string> strs_search(strK.begin(),
            strK.begin() + std::min<size_t>(total_str_cnt, strK.size()));
        
        for (size_t ifast = K <= 2 ? 0 : 1; ifast < 2; ++ifast) {
            double tim = 1000;
            for (size_t itest = 0; itest < (1 << 0); ++itest) {
                auto tb = Time();
                for (size_t i = 0; i < query_str_cnt; ++i) {
                    auto volatile t = FindClosest(strs_search, strK.at(strK.size() - 1 - i), ifast);
                }
                tb = Time() - tb;
                tim = std::min<double>(tim, tb / query_str_cnt / strs_search.size());
            }
            std::cout << std::fixed << "Avg time " << std::setprecision(2) << std::setw(9) << tim * 1'000'000
                << " mc-sec per " << (ifast ? "Fast" : "Slow") << " Levenstein distance of " << std::setprecision(1)
                << std::setw(5) << avg_len << " symbol strings" << std::endl;
        }
        std::cout << std::endl;
    }
}

计时的控制台输出：

Avg time     10.41 mc-sec per Slow Levenstein distance of   4.8 symbol strings
Avg time      1.58 mc-sec per Fast Levenstein distance of   4.8 symbol strings

Avg time  30444.71 mc-sec per Slow Levenstein distance of   9.6 symbol strings
Avg time      5.54 mc-sec per Fast Levenstein distance of   9.6 symbol strings

Avg time     12.56 mc-sec per Fast Levenstein distance of  14.4 symbol strings

Avg time     38.44 mc-sec per Fast Levenstein distance of  24.1 symbol strings

Avg time    154.76 mc-sec per Fast Levenstein distance of  48.1 symbol strings

Avg time    659.87 mc-sec per Fast Levenstein distance of 110.6 symbol strings
赞(0）分享  回复(0）举报  2023-01-15
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com