Поиск строки для любого вхождения слова в списке строк

Я хочу знать, как в C++ искать строку для первого экземпляра ЛЮБОГО списка строк. Этакая версия полного слова std::string::find_first_of(): "Поиск в строке первого символа, который соответствует любому из символов, указанных в его аргументах".

Я хочу что-то, что будет искать строку для первого слова, которое соответствует любому из слов в предоставленном списке / массиве. Чтобы было ясно, я не хочу искать в массиве экземпляр строки. Я хочу найти строку, например, что-то в массиве.

Моя цель - взять предложение и удалить все слова из списка. Например, если я дам ему список {"the" "brown", "over"};и предложение, "the quick brown fox jumped over the lazy dog"Я хочу, чтобы это вывело, " quick fox jumped lazy dog", И я хочу быть в состоянии дать ему список даже из 100 слов, если я хочу; Мне нужно, чтобы это было расширяемым.

Единственное решение, которое я могу придумать, это использовать std::find(stringArray[0]) в while Зациклите мой блок текста и сохраните индексы, в которых найдено это слово, затем поместите все это в другое for сделайте цикл и сделайте это для каждого слова в моем массиве, сохранив индексы каждого слова в один огромный список. При желании можно затем численно отсортировать этот список, и, наконец, затем пройти и удалить каждое слово, которое находится в позиции в этом списке.

Я действительно надеюсь, что есть функция или более простой способ сделать это, потому что мое решение кажется трудным и ОЧЕНЬ медленным, тем более, что мне нужно использовать его много раз, на разных строках, чтобы просмотреть все предложения 50000 символов. блок текста. Все, что лучше оптимизировано, будет предпочтительным.

Источник

2 ответа

Решение

Если вы ищете стандартные функции, есть некоторые возможности, если вы решите хранить свои предложения в виде контейнера строк:

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> форма 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();

Здесь онлайн демо.

Однако это решение не решит все ваши проблемы с производительностью. Для этого вам необходимо проанализировать, откуда возникает ваше узкое место в производительности: вы делаете много ненужных копий объектов? Это то, что ваш собственный алгоритм вызывает много неэффективного распределения памяти? Или это действительно объем текста?

Некоторые идеи для дальнейшей работы:

  • построить алфавитный указатель на слова в предложении (карта> где неподписанные
  • рассмотрим структуру данных Trie (Trie, а не дерево!)
  • Используйте регулярные выражения в <regex>
Источник

Быстродействие некоторых людей - это замедление других людей, поэтому трудно сказать, какой быстрый вы имеете в виду, и 50000 символов не кажутся такими большими, что нужно делать что-то необычное.

Единственное, чего следует избегать - это манипулировать входной строкой на месте (это приведет к времени выполнения O(n^2)) - просто вернуть новую результирующую строку. Вероятно, разумно зарезервировать достаточно памяти для полученной строки, потому что это сохранит постоянный коэффициент для некоторых входных данных.

Есть мое предложение:

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;
}

Этот метод использует набор, а не список запрещенных слов из-за более быстрого поиска. В качестве разделителей можно использовать любой набор символов, например " " или же " ,.;",

Он выполняется в O(n*log(k)), где n - количество символов в предложении, а k - количество слов в запрещенном наборе.

Возможно, вы захотите заглянуть в boost::tokonizer, если вам нужен более гибкий токонизатор и вы не хотите изобретать велосипед.

Если количество запрещенных слов велико, вы можете использовать std::unordered_set (C++11) или boost::unordered_set вместо std::set, чтобы уменьшить ожидаемое время работы алгоритма до O(n),

Источник
Другие вопросы по тегам