C++, Алгоритм поиска слова в строке в большом файле?

Question

Я пытаюсь найти лучший метод для поиска, какие строки в большом файле содержат определенное слово.

Например, если вы имели следующий файл:

cat dog monkey 
banana chair elephant 
monkey phone platypus cat 

Я хотел бы, чтобы иметь возможность возвращать 0, 2 для «кошек»

Я бы ожидать, что прототип функции, чтобы посмотреть что-то вроде этого:

std::vector<int> FindWords(std::string word); 

Я хотел бы предварительно обработать файл в какой-либо структуры данных, так что зависания может быть сделано быстро, давая номера строк, что слово, содержащиеся в. Я знаю, что std :: map может сделать это, если бы был только один экземпляр этого слова, но их было больше.

Каков наиболее подходящий алгоритм для этого?

Answer 1

Создайте структуру данных trie для всех уникальных слов в файле.

Для каждого слова в trie сохраните список номеров строк, где слово присутствует в файле. Это можно сделать за один проход через файл.

Вы также можете использовать карту, чтобы сохранить список номеров строк для каждого слова, но trie будет более компактным.

C декларации для структуры данных trie, добавленные ниже. Это должно дать вам представление о том, как начать работу, если вы хотите реализовать себя.

/* 
* TRIE data structure defined for lower-case letters(a-z) 
*/ 
typedef struct trie { 
    char c;       /* Letter represented by the trie node */ 
    struct trie *child[26];   /* Child pointers, one for each of the 26 letters of the alphabet */ 
    bool isTerminal;     /* If any word ends at that node, TRUE, else FALSE */ 
    int counts;      /* Number of lines the word ending at node occurs in the text */ 
    int lines[MAX_NUM];    /* Line numbers of the word occurences in the text */ 
} trie; 

/* 
* Insert a word into the trie. 
* word - Word which is being inserted 
* line - Line number of word in the text. 
*/ 
void insertToTrie(trie *node, const char *word, int line); 

Answer 2

Вы также можете использовать станд :: MultiMap или даже лучше станд :: unordered_multimap, как вам не нужно перебирать всю коллекцию карт только на элементах некоторого значения.

Edit: Простого пример:

#include <iostream> 
#include <unordered_map> 

int main() { 
    std::unordered_multimap<std::string, int> mymap; 
    mymap.insert(std::pair<std::string, int>("word", 1)); 
    mymap.insert(std::pair<std::string, int>("anotherword", 2)); 
    mymap.insert(std::pair<std::string, int>("word", 10)); 
    for (auto it = mymap.find("word"); it != mymap.end() && it->first == "word"; it++) { 
     std::cout << it->second << std::endl; 
    } 

} 

Answer 3

Бойер-Мур строки алгоритма поиск быстрее, чем в когда вы синтаксическое дерево ищете одну строку. Скорее всего, вы можете изменить его для нескольких строк.