在文本文件中找到並標記單詞

Question

我需要閱讀500字或更多的文本文件（來自報紙等的真實世界文章），然後找到並標記爲<location> word <location/>，然後打印整篇文章屏幕上。即時使用boost正則表達式，它的工作正常。我想嘗試使用一個列表或數組或其他數據結構來獲得州和主要城市的列表，然後搜索這些列表並與aticle進行比較。現在我正在使用一個數組，但我願意使用任何東西。任何想法或線索？

#include <boost/regex.hpp> 
#include <iostream> 
#include <string> 
#include <boost/iostreams/filter/regex.hpp> 
#include <fstream> 


using namespace std; 

int main() 
{ 
string cities[389]; 
string states [60]; 
string filename, line,city,state; 
ifstream file,cityfile, statefile; 
int i=0; 
int j=0; 
cityfile.open("c:\\cities.txt"); 
while (!cityfile.eof()) 
{ 

    getline(cityfile,city); 
     cities[i]=city; 
     i++; 
    //for (int i=0;i<500;i++) 
     //file>>cities[i]; 
} 
cityfile.close(); 

statefile.open("c:\\states.txt"); 
while (!statefile.eof()) 
{ 
    getline(statefile,state); 
     states[j]=state; 
    //for (int i=0;i<500;i++) 
    //cout<<states[j]; 
    j++; 
} 
statefile.close(); 
//4cout<<cities[4]; 






cout<<"Please enter the path and file name "<<endl; 
cin>>filename; 
file.open(filename); 

while (!file.eof()) 
{ 
     while(getline(file, line) 
     { 


     } 




     while(getline(file, line)) 
     { 


     //string text = "Hello world"; 
     boost::regex re("[A-Z/]\.[A-Z\]\.|[A-Z/].*[:space:][A-Z/]|C........a"); 
     //boost::regex re(
     string fmt = "<locations>$&<locations\>"; 
     if(boost::regex_search(line, re)) 
      { 
       string result = boost::regex_replace(line, re, fmt); 
       cout << result << endl; 
      } 
     /*else 
      { 
       cout << "Found Nothing" << endl; 
      }*/ 

     } 
} 
file.close(); 

cin.get(),cin.get(); 
return 0; 

}

Answer 1

如果你是後漸進複雜 - Aho-Corasick algorithm提供了一個線性時間複雜度（O(n+m)）（n和m是輸入字符串的長度）。用於在字符串中搜索字典。

另一種方法是將標記化單詞放入map（其中值是列表到每個字符串的流中的位置），然後搜索樹中數據中的每個字符串。的複雜性將是O(|S| * (nlogn + mlogn))（m是的搜索詞的數量，n是字符串中的字的數量，並|S|是平均字的長度）

Answer 2

可以使用具有.find()方法或支撐的任何容器std::find()。我會使用set，因爲set::find()的運行時間少於線性時間。

這是一個程序，它可以完成您所說的內容。請注意，解析不起作用，但這不是我想要演示的。您可以繼續使用解析器查找單詞，並使用set::find()的調用來確定它們是否是位置。

#include <set> 
#include <string> 
#include <iostream> 
#include <sstream> 

const std::set<std::string> locations { "Springfield", "Illinois", "Pennsylvania" }; 

int main() { 
    std::string line; 
    while(std::getline(std::cin, line)) { 
    std::istringstream iss(line); 
    std::string word; 
    while(iss >> word) { 
     if(locations.find(word) == locations.end()) 
     std::cout << word << " "; 
     else 
     std::cout << "<location>" << word << "</location> "; 
    } 
    std::cout << "\n"; 
    } 
}