0

在 C 程序中，我需要在普通文件中搜索确切的字符串（我使用 Linux）。我该怎么做才能搜索？

我的第一个假设包括将文件的每一行移动到 RAM（通过fgets()），并且在每次移动之后，检查该行是否是正确的字符串。如果不是，循环将重新调用fgets()并检查字符串直到 EOF。

但是一个有 1.5 亿行的文件会发生什么呢？碰巧这种顺序搜索似乎根本无效。

但是，我正在考虑一种二进制搜索，使用插入排序来对我的程序添加到文件中的行进行排序（它每 3 秒左右添加一行，在检查该行没有出现在字符串文件）。但后来我放弃了，因为我首先需要将行移动到 RAM，使用与顺序搜索相同的时间。因此我选择了顺序搜索。

这个假设正确吗？或者，还有更好的方法？我真的希望如此。

4

4 回答 4

2

您可以使用mmap将整个文件映射到内存中，然后进行strnstr搜索：

#include <sys/mman.h>

const char *fileName = "~/test.txt";
long fileLength;

// open file and get it's length
FILE *fptr = fopen(fileName, "r");

if (fptr == NULL || ferror(fptr))
{
    perror("could not open file");
    fclose(fptr);
    return 0;
}

fseek(fptr, 0, SEEK_END);
fileLength = ftell(fptr);
// return to the start of the file
fseek(fptr, 0, SEEK_SET);

// map the file
char *fileData = mmap(NULL, fileLength, PROT_READ, MAP_FILE | MAP_SHARED, fileno(fptr), 0);

if (fileData == MAP_FAILED)
    perror("could not map file");

// scan the file
char stringToSearchFor[] = "this is my string!";
if (strnstr(fileData, stringToSearchFor, fileLength) != NULL)
{
    printf("file contains the string!");
}
else {
    printf("file doesn't contain the string");
}

// clean up our code
munmap(fileData, fileLength);
fclose(fptr);
于 2012-05-15T16:00:39.747 回答
0

你能提供更多信息吗？普通文件是什么意思？您需要进行的最大文件大小是多少？

如果它是大文件并且您需要执行快速搜索，请遵循下一个算法原型：

  • 为您的文件创建索引
  • 在索引中执行搜索
  • 在文件中添加新信息后启动索引过程。（将创建增量索引）
  • 使用当前索引添加增量索引 注意：您需要缓存新信息以提供更好的性能。

您的搜索算法将取决于您将使用的索引类型。（可能是锥树、二叉树等）

有关更多信息，您需要阅读有关索引、在索引中搜索、存在的开源搜索系统，例如：apache lucene 和 sphinx。

UPD：这将是有用的链接： 实现文本文件内容的索引

https://superuser.com/questions/233665/efficient-way-to-index-text-files

于 2012-05-15T15:56:40.973 回答
0

在尝试匹配大数据上的字符串时，加快过程的一个技巧可能是创建快捷过滤器。Firefox 扩展 AdBlock Plus 实际上使用了这种技术来检查传入的页面请求并将这些请求与大量过滤器进行匹配。然后它会阻止匹配的过滤器（广告）。但我离题了。

当您将字符串与 n 字面值匹配时，从算法上讲，在最佳情况下需要 O(n) 时间 减少匹配字符串时间消耗的技巧是减小大小n。快捷过滤器的概念是您创建包含在相关字符串中的短模式。这样，您就可以减少检查每个字符串的正确性的时间。如果过滤器与字符串匹配，则检查完整的字符串。

基本上可以说我有 3 个字符串：

1) ABCDABCD 2) DCBABCDA 3) ABDEFGHI

假设我有一个模式“ABC”。迭代时，第一个和第二个字符串将返回匹配项。第三个字符串被拒绝。然后，您只检查那些与模式匹配的字符串是否有正确的字符串。另一方面。模式“EFG”拒绝 1 和 2（在更短的时间内）并匹配 3。

通过使用哈希表可以进一步改进子串的匹配。在这里，您可以像上面一样固定子字符串的大小，比如 3。然后，对于每个字符串，您计算所有长度为 3 的子字符串的哈希值。这样，您可以快速确定（在 O(1) 时间内）哪些模式与字符串匹配。

于 2012-05-15T16:00:47.623 回答
0

用于mmap将文件映射到内存，然后memmem对其进行标准搜索。您的操作系统将根据需要负责读取文件。

于 2012-05-15T15:46:07.130 回答