如何通过STL容器中的子字符串删除元素

Question

我有一个对象向量(对象是术语节点,其他字段包含字符串字段与术语字符串)

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

经过一些处理和计算得分后,这些对象最终存储在TermNode指针的向量中,例如

std::vector<TermNode *> termlist;

此向量的结果列表(最多包含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
...

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

对于这个清理过程,我想使用remove_if/find_if(使用新的C++ lambdas)编写一个类,并且将该代码放在一个紧凑的类中会很不错.

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

矢量上的另一个循环,也许是相同矢量的副本可以清理.我正在寻找一种最有效的方式.

我一直在玩这个想法或方向,例如在std :: list erase不兼容迭代器中使用remove_if/find_if和从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的东西,否则您可以使用简单的标点符号/空格分割.当每个字符串被分成它的组成单词时,然后使用哈希映射来保存所有当前单词的列表.当您达到多字词值时,您可以检查是否已找到其中的单词.这应该是识别重复项的最简单方法.