3

我正在寻找有关如何查找其字符可能具有多个变体的字符串的所有可能版本的一些提示。

一个简单的例子：“Macao”是起始字符串。字符“a”具有变体“ä”，字符“o”具有变体“ö”。

目标是从上述信息中获得以下列表：

Macao
Mäcao
Macäo
Mäcäo
Macaö
Mäcaö
Macäö
Mäcäö

到目前为止，我的方法是识别和提取带有变体的字符以简化事情。我们的想法是处理各个字符而不是整个单词。

aao
äao
aäo
ääo
aaö
äaö
aäö
ääö

以下代码查找我们正在使用的变体。

std::vector<std::string> variants;
variants.push_back("aä");
variants.push_back("oö");

std::string word = "Macao";
std::vector<std::string> results;
for (auto &variant : variants) {
    for (auto &character : word) {
        if (variant.front() == character) {
            results.push_back(variant);
        }
    }
}

std::cout << "The following characters have variants: ";
for (auto &i : results) {
    std::cout << i.front();
}
std::cout << std::endl;

下一步是找到各个字符的所有可能组合。为此，我编写了以下函数。它从results.

std::string read_results(std::vector<std::string> &results)
{
    std::string s;
    for (auto &c : results) {
        s.push_back(c.front());
    }
    return s;
}

这个想法是然后更改存储在其中的字符串results以获得所有可能的组合，这就是我被卡住的地方。我注意到这std::rotate似乎会有所帮助。

4

1 回答 1

0

倒排索引可能有用。

您可以将所有具有多个变体的字母按顺序存储在一个向量中，并为每个字母设置一个分组索引的向量，以便第 i 个字母属于该组I[i]，并且所有索引相同的字母I[i]是同一个字母的变体：

string L = "aoäöâô"; // disclaimer: i don't know if this is really in order
unsigned int I[]  = {0,1,0,1,0,1};
// this means that "aäâ" belong to group 0, and "oöô" belong to group 1

L您可以为以前的索引构建倒排索引，I如下所示：

vector<vector<unsigned int> > groups;
// groups[k] stores the indices in L of the letters that belongs to the k-th group.
// do groups.reserve to make this operation more efficient
for(size_t i = 0; i < L.size(); ++i)
{
  unsigned int idx = I[i];
  if(idx <= groups.size()) groups.resize(idx+1);
  groups[idx].push_back(i);
}

重要的是，字母按L顺序排列，因此您可以稍后对其进行二进制搜索，O(logn)而不是O(n)通常的循环。然后，一旦你有了你的字母组，你就可以找到它的倒排索引变体：

char letter = 'a';
string::iterator it = std::lower_bound(L.begin(), L.end(), letter);
if(it != L.end() && *it == letter)
{
  unsigned int idx = I[ it - L.begin() ];
  // the letter has variants because it belongs to group idx
  const vector<unsigned int>& group = groups[idx];
  for(vector<unsigned int>::const_iterator git = group.begin();
    git != group.end(); ++git)
  {
    // now, L[*git] is one of the variants of letter
    ...
  }
}
于 2013-10-03T10:51:08.080 回答