查找文本文件中的关键字

查找文本文件中的关键字，说白了就是以文本文件作为输入，进行字符串匹配，找返回其第一次出现的下标位置。但是由于数据是以文本文件的形式作为输入的，如何存储和进行匹配就成为了一个问题。下面以两种方法来介绍如何操作。注：本文中采用的字符串匹配算法只是普通的字符串匹配算法，重点在对文件处理和分块查找。

一、蛮力法

这种方法非常简单，把文件中的所有数据输入到一个字符数组中，然后以数组作为主串，关键字为模式串，进行字符串匹配即可。

但是这里有一个问题，就是字符数组要多大才合适？由于不同的文件的数据量可能差别非常大，所以我们应该根据文件的大小来动态分配字符数组来存储主串。即我们现在的问题变为如何获得文件的大小。文件的大小可以用如下的方法来获得，首先打开文本文件，保存其文件位置，然后把文件指针定位到文件的末尾，获得其偏移量，然后再把文件指针恢复到原先即可。恢复文件指针是为了不让该调用对文件的其他操作产生影响，从外部看来这个操作调用前与调用后文件的状态并没有变化过。其现实代码如下，返回文件所占的字符总数：

int GetFileLength(ifstream &inputFile)
{//保存文件当前位置streampos pos = inputFile.tellg();//定位到文件尾inputFile.seekg(0, ios::end);//返回文件尾的偏移量，即文件的大小int length = inputFile.tellg();//返回到文件先前的位置inputFile.seekg(pos);return length;
}

则实现字符串匹配的函数如下：

int IndexInFile(const char *fileName, const char *keyWord)
{//以只读方式，打开文件fileNameifstream inputFile(fileName);if(!inputFile){//打开文件失败cerr<<"error: unable to open input file: "<<fileName<<endl;return -1;}//获得文件的长度，即字节数，并开劈一个同样大小的数组保存文件数据int length = GetFileLength(inputFile);char *text = new char[length+1];//把文件的内容讲到数组中inputFile.read(text, length);inputFile.close();text[length] = '\0';//进行模式串匹配，并返回结果int index = IndexOf(text, length, keyWord, strlen(keyWord));delete []text;return index;
}
int IndexOf(const char *text, int textSize,const char *match, int matchSize)
{for(int i = 0; i <= textSize - matchSize; ++i){int j = 0;while(j < matchSize && match[j] == text[i+j])++j;//所有的字符都与文本中的一致，则匹配成功if(j == matchSize)return i;}//匹配失败return -1;
}

其代码非常简单，不再多说了。

二、分治法

注意，这里主要是用到了把文件分成若干大小相同的块，并对各个块进行字符串匹配的方法来处理，并不是指字符串匹配算法使用了分治的思想。

由于文件的数据可能非常巨大，一次性地把文件的所有内容读入到内存时，有时是不可能的，而且这样做也没有什么必要，因为我们要查找的串很可能就在文件的前面部分，而我们却把一个文件的所有内容调入到内存中，浪费了大量的内存空间，而且效率不高。所以我们应该把文件进行分块处理，每次从文件中读取一定的字符到缓冲区中，进行处理。其实现方法如下：

首先把开文件，每次从文件读取指定个数的字符到buffer中，然后以buffer中的字符作为主串，关键字作为模式串进行字符串匹配，若匹配成功把返回其下标，若匹配不成功，则把下标值累加上读到缓冲区中字符的个数，并继续从文件中读取字符到buffer中，继续对buffer进行字符串匹配，直到找到关键字，或文件结束。

这个方法不用把文件的所有内容调入内存中，而是每次都从内存读入一个buffer的内容，可以减少内存的开销，不论文件有多大都可行。然而这个方法的难点在哪里呢，难点就要当关键字在两个缓冲区之间时该如何识别和处理。

下面说说我的想法，为了方便解说，我们假设buffer的大小为6，要查找的关键字为defg，文件的内容为abcdefghijk，我们每次从文件中读取5个字符到buffer中（第6个字符为'\0')，为abcde，可以看到我们要查找的字符串只有一部分在buffer中，它们被分为了两个部分。首先我们判断当在buffer上查找不成功，是否是由于所有的字符都匹配，但是模式串还没匹配完，主串却已经到了尽头，若是，把把之前与模式串匹配的部分字符复杂到buffer的前面，然后再从文件中输入数据，并放到其后面。在这个例子中，就是把de复制到buffer的前面，再从文件中读取数据到de后面的buffer中，读入完毕后，buffer的数据变成defgh，然后再对其进行匹配，即可匹配成功。

其实现代码如下：

int IndexInFile(const char *fileName, const char *keyWord)
{//以只读方式，打开文件fileNameifstream inputFile(fileName);if(!inputFile){//打开文件失败cerr<<"error: unable to open input file: "<<fileName<<endl;return -1;}int keySize = strlen(keyWord);//关键字的长度int index = 0; //记录关键字首次出现的位置int lastMatch = 0;//记录最后一次匹配的位置const int bufferSize = 5;char buffer[bufferSize + 1];while(!inputFile.eof()){//把最后一次比较配置的字符复制到最前面WriteEndToBegin(buffer, bufferSize, lastMatch);//读入数据到缓冲区中lastMatch后的位置中inputFile.read(buffer + lastMatch,bufferSize - lastMatch);buffer[bufferSize] = '\0';cout<<buffer<<endl;int thisIndex = IndexOf(buffer, bufferSize,keyWord, keySize, lastMatch);if(thisIndex != -1){//若查找成功，则下标值为之前查找过的字符数加上此次查找的字符数index += thisIndex;return index;}else{//若查找不成功，则加上新放入到缓冲区的字符数index += (bufferSize - lastMatch);}}return -1;
}
int IndexOf(const char *text, int textSize,const char *match, int matchSize,int &lastMatch)
{for(int i = 0; i < textSize; ++i){lastMatch = 0;while(lastMatch < matchSize && match[lastMatch] == text[i+lastMatch])++lastMatch;//所有的字符都与文本中的一致，则匹配成功if(lastMatch == matchSize)return i;//所有的字符都匹配，但是模式串还没匹配完，主串已经到了尽头if(i + lastMatch == textSize)break;}//匹配失败return -1;
}
void WriteEndToBegin(char *text, int textSize, int writeCount)
{//把字符数组中最后writeCount个字符写到最前面for(int i = 0; i < writeCount; ++i){text[i] = text[textSize - writeCount + i];}
}

代码分析：

这里主要解析一下IndexOf函数中的lastMatch参数，该参数记录了主串中与模式串匹配的字符的个数。当IndexOf函数返回-1时，它尤其有用，因为它让我们知道，在buffer中，有多少个字符已经与模式串（关键字）匹配了，在上面的例子中，就是de两个字符，则其值为2，所以把buffer中最后的两个字符复制到了其前面。

同时还要注意，buffer的大小一定要大小模式串的长度，不然的话，buffer会因为装不下一个模式串而出错。在代码中为了演示而把buffer的大小定为6（5+1），但是在使用时应该把它改变成你想要的大小，通常256或512是一个合适的值。

三、复杂度分析

两个算法的时间复杂度无为O(n*m)，n为文件的字符数，m为关键字的字符数（即模式串的字符数）。空间复杂度第一个算法为O(n),第二个算法为O(1),因为不论文件多大，缓冲区的大小都是确定的。

源代码可以点击这里下载：

http://download.csdn.net/detail/ljianhui/6731885

PS：本人成为了CSDN2013博客之星候选人之一，如果你觉得本人写的博客还可以，请投我一票，支持一下我，我的投票地址是：

http://vote.blog.csdn.net/blogstaritem/blogstar2013/ljianhui