Поиск слов в очень большом файле

Question

Учитывая большой файл, нам нужно сохранить слова, чтобы поиск слова выполнялся в постоянное время. Также как мы найдем 10% наиболее часто встречающихся слов в файле?

То, что я достиг до сих пор, выполняет поиск слова через реализацию trie. Пожалуйста, предложите способ найти 10% самых частых слов.

#include<iostream> 
#include<cstdio> 
using namespace std; 
class Node 
{ 
    public: 
    char value; 
    Node* right; 
    Node* down; 
    Node() 
    { 
     right=down=NULL; 
    } 
}; 
class Trie 
{ 
    public: 
    Node* head; 
    Trie() 
    { 
     head=NULL; 
    } 
    void insert(string s); 
    void search(string s); 
}; 
void Trie::insert(string s) 
{ 
    if(head==NULL) 
    { 
     Node* f=new Node(); 
     head=f; 
     Node* temp=f; 
     f->value=s[0]; 
     for(int i=1;i<s.length();i++) 
     { 
      Node* n=new Node(); 
      n->value=s[i]; 
      temp->down=n; 
      temp=n; 
      if(i==s.length()-1) 
      n->down=NULL; 
     } 
    } 
    else 
    { 
     Node* ptr=head; 
     int i=0; 
     while(1) 
     { 
      if(i==s.length())break; 
      if(ptr->value==s[i]) 
      { 
       i++; 
       if(ptr->down) 
       ptr=ptr->down; 
       else 
       { 
        Node* temp=new Node(); 
        ptr->down=temp; 
        temp->value=s[i]; 
        ptr=temp; 
       } 
      } 
      else if(ptr->value!=s[i]) 
      { 
       if(ptr->right) 
       ptr=ptr->right; 
       else 
       { 
        Node*temp=new Node(); 
        ptr->right=temp; 
        temp->value=s[i]; 
        ptr=temp; 
       } 
      } 
     }  
    } 
} 
void Trie::search(string s) 
{ 
    Node* ptr=head; 
    int i=0; 
    while(1) 
    { 
     if(ptr->value==s[i]) 
     { 
      //cout<<ptr->value<<endl; 
      ptr=ptr->down; 
      i++; 
     } 
     else if(ptr->value!=s[i]) 
     { 
      ptr=ptr->right; 
     } 
     if(ptr==NULL)break; 
    } 

    if(i==s.length()+1)cout<<"String found\n"; 
    else cout<<"String not found\n"; 
} 
int main() 
{ 
    Trie t; 
    FILE* input; 
    char s[100]; 
    input=fopen("big.txt","r"); 
    int i=0; 
    while( (fgets(s,sizeof(s),input)) !=NULL) 
    { 
     int i=0; int j=0; 
     char str[47]; 
     while(s[i]!='\0') 
     { 
      if(s[i]==' ' || s[i+1]=='\0') 
      { 
       str[j]='\0'; 
       j=0; 
       t.insert(str); 
       i++; 
       continue; 
      } 
      str[j]=s[i]; 
      j++; 
      i++; 
     } 
    } 


    t.search("Dates"); 
    //t.search("multinational"); 
    fclose(input); 
} 

Answer 1

Хэш позволит вам искать слова в постоянное время.

Возможно, вы можете использовать какое-то разделение, подобное тому, которое используется в quicksort, чтобы найти слово, которое происходит не менее 10% от файла.

Answer 2

Очевидным решением является сохранение содержимого файла в соответствующем контейнере STL, таком как std::set, а затем запуск find() на этом контейнере.

Если вы настаиваете на том, чтобы делать это вручную, бинарное дерево будет становиться все медленнее, чем больше данных, которые вы вставляете в него. Кроме того, вы должны поддерживать равновесие. A hash table с цепочки будет более эффективным ADT для огромного количества данных.

Answer 3

Если вы используете дерево, вы не можете получить постоянное время. Бинарное дерево, которое вы строите, имеет логарифмическую временную сложность.

Если можно построить индекс, рассмотрите inverted index. Это все равно не поможет вам с постоянным временем (я не вижу, как вы можете это достичь), но может помочь вам понять, какие слова используются больше всего, поскольку для каждого слова он сохраняет позиции в файле, где слово найдено. Вы можете объединить это в свое дерево.