c++ - 在文本文件中定位和标记单词

Question

我需要阅读一个 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;

Answer 1

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

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