Поиск строки в нормальном файле

Question

В программе на C мне нужно найти точную строку в обычном файле (я использую Linux). Как мне сделать, чтобы искать?

Мое первое предположение состояло в перемещении каждой строки файла в ОЗУ (через fgets()), и после каждого шага проверьте, была ли эта строка правильной строкой. Если это не так, цикл перезвонит fgets() и проверит строки до EOF.

Но что происходит с файлом с 150 миллионами строк? Случается, что такой последовательный поиск кажется неэффективным вообще.

Однако я думал о каком-то двоичном поиске, используя сортировку вставки, чтобы сортировать строки, которые моя программа добавляет в файл (она добавляет одну строку каждые 3 секунды сразу же после проверки того, что эта строка не работает 't появляется в файле строк). Но потом я сдался, потому что мне сначала нужно было переместить строки в ОЗУ, используя то же самое время, которое я использовал бы для последовательного поиска. Таким образом, я выбрал последовательный поиск.

Действительно ли это предположение? Или есть лучший способ? Я очень на это надеюсь.

Answer 1

Вы можете использовать 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); 

Answer 2

Используйте mmap, чтобы отобразить файл в память, затем выполните стандартный memmem. Ваша ОС позаботится о чтении файла по мере необходимости.

Answer 3

Не могли бы вы предоставить более подробную информацию? Что означает обычный файл? Какой максимальный размер файла вам нужно продолжить?

Если это будет большим файл, и вы должны выполнить быстрый поиск следовать следующему прототипу алгоритма:

• создает индекс вами файл
• выполнять поиск в индексе
процесса индексации
• запуска после новой информации будет добавлен в файл. (будет создан дельта-индекс)
• добавить индекс дельта с текущим индексом Примечание: вам нужна дополнительная информация о кеше, чтобы обеспечить лучшую производительность.

Ваш алгоритм поиска будет, зависит от типов индекса вы будете использовать. (Это может быть, шило деревья, бинарные деревья и т.д.)

Для получения дополнительной информации, которую нужно прочитать об индексации, поиска в индексе, с открытым исходным кодом системы поиска которые существуют, например: apache lucene и sphinx.

UPD: это будет полезно ссылки:Implementing a index for text file content

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

Answer 4

При попытке сопоставить строки над большими данными, трюк, чтобы закрепить процесс, возможно, создает фильтры быстрого доступа. Этот метод фактически используется расширением firefox AdBlock Plus для проверки входящих запросов страниц и сопоставления с большим списком фильтров.Затем он блокирует согласованные фильтры (объявления). Но я отвлекся.

Когда вы подходите строку с, скажем из п литер, алгоритмически это занимает O (N) времени в best case scenario Хитрость, чтобы уменьшить затраты времени для согласования строки, чтобы уменьшить размер п. Концепция быстрых фильтров заключается в том, что вы создаете короткие шаблоны, которые содержатся в соответствующей строке. Таким образом, вы тратите меньше времени на проверку правильности каждой строки. Если фильтр соответствует строке, то вы проверяете полную строку.

В принципе позволяет сказать, что у меня есть 3 строки:

1) ABCDABCD 2) DCBABCDA 3) ABDEFGHI

Пусть у меня есть образец "ABC". В то время как итерация, первая и вторая строки возвращают совпадение. Третья строка отклоняется. Затем вы проверяете только те строки, которые соответствуют шаблону для правильной строки. С другой стороны. образец «EFG» отклоняет 1 и 2 (за меньшее время) и соответствует 3.

Соответствие подстроки может быть улучшено далее с помощью таблицы хешей. Здесь вы можете исправить размер подстроки, например 3, как указано выше. Затем для каждой строки вы вычисляете хэши для всех подстрок длины 3. Таким образом, вы можете быстро определить (в O (1) время), какой из шаблонов соответствует строке.