矢量搜索押韵词

Question

在我的程序中，我必须提示用户输入一个单词，并报告所有押韵的单词(通过检查最后3个字母是否相同(。
例如，如果用户输入了单词"时间"，我必须返回lime、dime、intime、regime等，形成一个有106000个单词的向量。

所有106000个单词都在向量vector<string>words中，该向量将包含

time, lime, line, dime, intime, abaca, clilica, dog, ball, regime, sentence, return, which, contain, word, pool, etc....

在所有这些中，我需要得到与用户输入的单词有节奏的单词。

如何创建一个函数，通过用户输入的字符串输入来查找所有这些？

Answer 1

您说rhyme=the last 3 letters are the same。矢量中的106 000个单词意味着你有足够的内存，所以建议用下面的方法来交换空间和时间。

unordered_map<string, vector<string>> rhymesMap;
int const rhymesSuffixLength = 3;
void preProcess(vector<string>& words){
for(auto const& word: words){
if(word.size() < rhymesSuffixLength)
continue;
string suffix = word.substr(word.size() - rhymesSuffixLength);
rhymesMap[suffix].push_back(word);
}
}
vector<string> getRhymes(string word){
if(word.size() < rhymesSuffixLength)
return {};
string suffix = word.substr(word.size() - rhymesSuffixLength);
return rhymesMap[suffix];
}

从vector搜索押韵太慢，unordered_map需要查找，而且速度很快。

Answer 2

如果你在处理英语单词，字母表有26个字符。因此只有17576=26³桶。这意味着可以使用具有连续内存的容器进行持续时间查找。

template <auto N, unsigned E>
inline constexpr auto power = N*power<N,E-1>;
template <auto N>
inline constexpr auto power<N,0> = decltype(N)(1);
template <unsigned suffix_len = 3, unsigned alphabet = 'z'-'a'+1>
class Rhyme {
private:
std::vector<std::vector<std::string>> table; // <----
static unsigned serialise(std::string const& s) {
unsigned result = 0;
if (s.size() >= 3) {
result += 1;
for (auto it = std::next(std::begin(s),s.size()-3); it != std::end(s); ++it) {
result *= alphabet;
result += *it-'a';
}
}
return result;
}   
public:
Rhyme(std::vector<std::string> const& dictionary) : table{} {
table.resize(power<alphabet,suffix_len>+1);
for (auto const& s: dictionary) {
if (auto index = serialise(s)) {
table[index].emplace_back(s);
}
}
}   
std::vector<std::string> const& lookup(std::string const& key) const {
return table[serialise(key)];
}   
};

这可以非常直接地使用，并且有保留输入顺序的好处。

std::vector<std::string> input =
{ "time", "lime", "line", "dime", "intime", "abaca", "clilica", "dog", "ball", "regime", "sentence", "return", "which", "contain", "word", "pool" };
Rhyme r(input);
for (auto const& s: r.lookup("slime")) {
std::cout << s << "n";
}

输出：

time
lime
dime
intime
regime

现场演示