c++ - 如何从 STL 容器中按子字符串删除元素

Question

我有一个对象 vector (对象是术语节点，其中包含一个带有术语字符串的字符串字段)

class TermNode {
private:
    std::wstring term;
    double weight;
    ...
public:
    ...
};

经过一些处理和计算分数后，这些对象最终存储在 TermNode 指针 vector 中，例如

std::vector<TermNode *> termlist;

该 vector 的结果列表(最多包含 400 个条目)如下所示:

DEBUG: 'knowledge' term weight=13.5921
DEBUG: 'discovery' term weight=12.3437
DEBUG: 'applications' term weight=11.9476
DEBUG: 'process' term weight=11.4553
DEBUG: 'knowledge discovery' term weight=11.4509
DEBUG: 'information' term weight=10.952
DEBUG: 'techniques' term weight=10.4139
DEBUG: 'web' term weight=10.3733
...

我尝试做的是清理最终列表中也包含在术语列表内的短语中的子字符串。例如，查看上面的列表片段，有短语'知识发现'，因此我想删除单个术语'知识'和' discovery'，因为它们也在列表中，并且在此上下文中是多余的。我想保留包含单个术语的短语。我还在考虑删除所有等于或少于 3 个字符的字符串。但这只是目前的一个想法。

对于这个清理过程，我想使用remove_if/find_if(使用新的C++ lambda)编写一个类，并且最好将该代码放在一个紧凑的类中。

我不太确定如何解决这个问题。问题是，我首先必须通过可能将标志设置为删除标记来确定要删除的字符串。这意味着我必须预处理该列表。我必须找到单个术语以及包含这些单个术语之一的短语。我认为这不是一件容易的事，需要一些先进的算法。使用后缀树来识别子串？

vector 上的另一个循环以及同一 vector 的拷贝可能可以进行清理。我正在寻找最有效的时间方式。

我一直在研究std::list erase incompatible iterator中所示的想法或方向。使用remove_if/find_if和Erasing multiple objects from a std::vector?中使用的想法.

所以问题基本上是有没有一种聪明的方法来做到这一点并避免多个循环，以及如何识别要删除的单个术语？也许我真的错过了一些东西，但可能有人在那里给了我一个很好的提示。

感谢您的想法!

更新

我按照 Scrubbins 推荐的方式实现了删除冗余单项，如下所示:

/**
 * Functor gets the term of each TermNode object, looks if term string
 * contains spaces (ie. term is a phrase), splits phrase by spaces and finally
 * stores thes term tokens into a set. Only term higher than a score of 
 * 'skipAtWeight" are taken tinto account.
 */
struct findPhrasesAndSplitIntoTokens {
private:
    set<wstring> tokens;
    double skipAtWeight;

public:
    findPhrasesAndSplitIntoTokens(const double skipAtWeight)
    : skipAtWeight(skipAtWeight) {
    }

    /**
     * Implements operator()
     */
    void operator()(const TermNode * tn) {
        // --- skip all terms lower skipAtWeight
        if (tn->getWeight() < skipAtWeight)
            return;

        // --- get term
        wstring term = tn->getTerm();
        // --- iterate over term, check for spaces (if this term is a phrase)
        for (unsigned int i = 0; i < term.length(); i++) {
            if (isspace(term.at(i))) {
if (0) {
                wcout << "input term=" << term << endl;
}
                // --- simply tokenze term by space and store tokens into 
                // --- the tokens set
                // --- TODO: check if this really is UTF-8 aware, esp. for
                // --- strings containing umlauts, etc  !!
                wistringstream iss(term);
                copy(istream_iterator<wstring,
                        wchar_t, std::char_traits<wchar_t> >(iss),
                    istream_iterator<wstring,
                        wchar_t, std::char_traits<wchar_t> >(),
                    inserter(tokens, tokens.begin()));
if (0) {
                wcout << "size of token set=" << tokens.size() << endl;
                for_each(tokens.begin(), tokens.end(), printSingleToken());
}
            }
        }
    }

    /**
     * return set of extracted tokens
     */
    set<wstring> getTokens() const {
        return tokens;
    }
};

/**
 * Functor to find terms in tokens set
 */
class removeTermIfInPhraseTokensSet {
private:
    set<wstring> tokens;

public:
    removeTermIfInPhraseTokensSet(const set<wstring>& termTokens)
    : tokens(termTokens) {
    }

    /**
     * Implements operator()
     */
    bool operator()(const TermNode * tn) const {
        if (tokens.find(tn->getTerm()) != tokens.end()) {
            return true;
        }
        return false;
    }
};

...

findPhrasesAndSplitIntoTokens objPhraseTokens(6.5);
objPhraseTokens = std::for_each(
    termList.begin(), termList.end(), objPhraseTokens);
set<wstring> tokens = objPhraseTokens.getTokens();
wcout << "size of tokens set=" << tokens.size() << endl;
for_each(tokens.begin(), tokens.end(), printSingleToken());

// --- remove all extracted single tokens from the final terms list
// --- of similar search terms 
removeTermIfInPhraseTokensSet removeTermIfFound(tokens);
termList.erase(
    remove_if(
        termList.begin(), termList.end(), removeTermIfFound),
    termList.end()
);

for (vector<TermNode *>::const_iterator tl_iter = termList.begin();
      tl_iter != termList.end(); tl_iter++) {
    wcout << "DEBUG: '" << (*tl_iter)->getTerm() << "' term weight=" << (*tl_iter)->getNormalizedWeight() << endl;
    if ((*tl_iter)->getNormalizedWeight() <= 6.5) break;
}

...

我无法使用 C++11 lambda 语法，因为我的 ubuntu 服务器上当前安装了 g++ 4.4.1。无论如何。它暂时完成了这项工作。 解决的方法是检查生成的加权术语与其他搜索结果集的质量，看看如何提高质量并找到一种方法来提高与原始查询术语相关的更相关的术语。这可能不是一件容易的事，我希望有一些“简单的启发式”。 但这可能是另一个新问题，当更进一步时:-)

感谢大家的丰富思想贡献!

Answer 1

您需要做的是首先迭代列表并将所有多单词值拆分为单个单词。如果您允许 Unicode，这意味着您将需要类似于 ICU 的 BreakIterators 的东西，否则您可以使用简单的标点符号/空格分割。当每个字符串被分割成它的组成词时，然后使用 HashMap 来保留所有当前单词的列表。当您达到多单词值时，您可以检查它的单词是否已经找到。这应该是识别重复项的最简单方法。