在字符串列表中搜索某个单词的任何出现的字符串

Question

我想知道如何在 C++ 中搜索字符串以查找字符串列表中 ANY 的第一个实例。 std::string::find_first_of() 的一种全字版本：“在字符串中搜索与参数中指定的任何字符匹配的第一个字符 ”。

我想要一些能够在字符串中搜索与提供的 list/array 中的任何单词匹配的第一个单词的东西。明确地说，我不想在数组中搜索字符串实例。我想在一个字符串中搜索数组中某物的实例。

我的目标是能够提取一个句子，并删除列表中的所有单词。例如，如果我给它列表 {"the" "brown", "over"}; 和句子，"the quick brown fox jumped over the lazy dog"，我希望它输出，" quick fox jumped lazy dog"。如果我愿意，我希望能够给它一个包含 100 个单词的列表；我需要它是可扩展的。

我能想到的唯一解决方案是在我的文本块的 while 循环中使用 std::find(stringArray[0])，并保存找到该词的索引，然后将所有内容放入另一个 for 循环并对数组中的每个单词执行此操作，将每个单词的索引保存到一个巨大的列表中。（可选）然后对该列表进行数字排序，最后遍历并删除该列表中某个位置的每个单词。

我真的希望有一个函数或更简单的方法来实现它，因为我的解决方案看起来很困难而且非常慢，特别是因为我需要在许多不同的字符串上多次使用它来遍历所有50,000 个字符的文本块的句子。任何更好的优化将是首选。

Answer 1

如果您寻找标准函数，并且敢于将句子存储为字符串容器，则有一些可能性：

string input="Hello, world ! I whish you all \na happy new year 2016 !";
vector<string> sentence; 

stringstream sst(input);    // split the string into its pieces 
string tmp; 
while (sst>>tmp) 
    sentence.push_back(tmp);

当然，在现实世界中，您不仅会根据空格进行拆分，还会根据标点符号进行拆分。这只是一个概念证明。

一旦你有了这个表格，就很容易使用 <algorithm> form of find_first_of():

vector<string> search{"We", "You", "I"}; 
auto it =  find_first_of(sentence.begin(), sentence.end(), 
                           search.begin(), search.end()); 

                           // display remaining of the sentence
copy(it , sentence.end(), ostream_iterator<string>(cout,"/"));    
cout<<endl;

从向量中删除单词应该不再是一个问题。我把它作为练习交给你。

一旦你有了清理过的矢量，你就可以重建一个字符串：

stringstream so;
copy(it , sentence.end(), ostream_iterator<string>(so," ")); 
string result = so.str();

这里是online demo。

但是，此解决方案不会解决您的所有性能问题。为此，您需要进一步分析您的性能瓶颈来自何处：您是否制作了很多不必要的对象副本？是不是你自己的算法触发了很多低效的内存分配？或者它真的是纯粹的文本量？

进一步工作的一些想法：

为句子中的单词建立字母索引 (map> 其中无符号
考虑一个 trie 数据结构（trie 而不是树！！）
在<regex>中使用正则表达式

Answer 2

有的人快，有的人慢，所以很难说你指的是哪个快，50000个字听上去也不算多，非得做点什么了不起的事。

唯一应该避免的是操纵输入字符串 in-place（会导致 O(n^2) 运行时间）——只是 return 一个新的结果细绳。为结果字符串保留足够的内存可能是明智的，因为它会为某些输入保存一个常数因子。

有我的提议：

std::string remove_words(const std::string &sentence, const std::set<std::string> &words2remove, const std::string &delimiters){

    std::string result;
    result.reserve(sentence.size());//ensure there is enough place 

    std::string lastDelimiter;//no delimiter so far...
    size_t cur_position=0;
    while(true){
      size_t next=sentence.find_first_of(delimiters, cur_position);
      std::string token=sentence.substr(cur_position, next-cur_position);

      result+=lastDelimiter;
      if(words2remove.find(token)==words2remove.end())
         result+=token;//not forbidden

      if(next==std::string::npos)
        break;

      //prepare for the next iteration:  
      lastDelimiter=sentence[next];
      cur_position=next+1;
    }

    return result;
}

由于更快 look-up，此方法使用一组而不是禁用词列表。作为定界符，可以使用任何一组字符，例如" " 或 " ,.;".

它在 O(n*log(k)) 中运行，其中 n 是句子中的字符数，k 是禁止集中的单词数。

如果您需要更灵活的 tokonizer 并且不想重新发明轮子，您可能需要研究 boost::tokonizer。

如果禁止词数量较多，可以考虑使用std::unordered_set（c++11）或boost::unordered_set代替std::set来减少预期的运行算法时间为 O(n).

在字符串列表中搜索某个单词的任何出现的字符串

Search a string for any occurence of a word in a list of strings

c++

arrays

string

text-search