0

我需要阅读一个 500 字或更多字的文本文件（来自报纸等的真实世界文章）并像这样定位和标记 <location> word <location/>，然后在屏幕上打印整篇文章。我现在正在使用 boost 正则表达式，它工作正常。我想尝试使用列表或数组或其他一些数据结构来获得州和主要城市的列表，然后搜索这些并与文章进行比较。现在我正在使用一个数组，但我愿意使用任何东西。有什么想法或线索吗？

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

}

4

2 回答 2

1

如果您追求渐近复杂度 - Aho-Corasick 算法提供线性时间复杂度 ( O(n+m))（n并且m是输入字符串的长度）。用于在字符串中搜索字典。

另一种方法是将标记化的单词放在 a 中map（其中值是每个字符串流中位置的列表），并在树中的数据中搜索每个字符串。复杂度将是O(|S| * (nlogn + mlogn) )（m是搜索词n的数量，是字符串中的词数，|S|是平均词的长度）

于 2012-11-27T19:27:04.837 回答
1

您可以使用任何具有.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";
  }
}
于 2012-11-27T19:53:05.070 回答