c++ - 非常に大きなファイルで単語を検索する

Question

ファイルが大きい場合、単語の検索を一定時間で実行できるように、単語を保存する必要があります。また、ファイル内で最も頻繁に出現する 10% の単語をどのように見つけるのでしょうか?

私がこれまでに達成したことは、トライ実装を通じて単語を検索することです。最も頻繁に使用される 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

ハッシュを使用すると、単語を一定時間で検索できます。

おそらく、クイックソートで使用されるような何らかのパーティショニングを使用して、ファイルから少なくとも 10% 出現する単語を見つけることができます。

Answer 2

ツリーを使用すると、一定の時間が得られません。あなたが構築している二分木は、対数時間の複雑さを持っています。

索引を作成できる場合は、逆索引を検討してください。これはまだ一定の時間の助けにはなりません (とにかくそれを達成する方法はわかりません) が、どの単語が最も使用されているかを把握するのに役立ちます。単語が見つかりました。実際にそれをツリーに組み合わせることができます。

Answer 3

プライオリティ キュー、マップ、およびトライを使用した同様の C++ コードを次に示します。簡単にするために、ベクトル文字列から読み取りますが、ファイルから単語を読み取るように簡単に変更できます。

// ファイルまたはストリーム内の上位 K 個の頻出単語を検索、C++

//これは、参照用のpriority_queueの実用的なソリューションです。

    #include <iostream>
    #include <vector>
    #include <queue>
    #include <unordered_map>
    using namespace std;

    #define K_TH 3


    class TrieNode;
    typedef struct HeapNode
    {
        string word;
        int frequency;
        HeapNode(): frequency(0), word(""){} ;
        TrieNode *trieNode;

    }HeapNode;


    class TrieNode
    {
        private:
            int frequency = 0;
            bool m_isLeaf = false;
            string word = "";
            unordered_map<char, TrieNode*> children;
            HeapNode *heapNode = NULL;

        public:
            TrieNode() {}
            TrieNode(char c)
            {
                children[c] = new TrieNode();
                this->m_isLeaf = false;
            }

            void setWord(string word)
            {
                this->word = word;
            }
            string getWord()
            {
                return this->word;
            }
            bool isLeaf(void)
            {
                return this->m_isLeaf;
            }
            void setLeaf(bool leaf)
            {
                this->m_isLeaf = leaf;
            }
            TrieNode* getChild(char c)
            {
                if (children[c] != NULL)
                    return children[c];
                return NULL;
            }
            void insert(char c)
            {
                children[c] = new TrieNode();
            }
            int getFrequency()
            {
                return this->frequency;
            }
            void setFrequency(int frequency)
            {
                this->frequency = frequency;
            }
            void setHeapNode(HeapNode *heapNode)
            {
                this->heapNode = heapNode;
            }
            HeapNode* getHeapNode()
            {
                return heapNode;
            }
            bool operator()(HeapNode* &a, HeapNode* &b)
            {
                return (a->frequency > b->frequency);
            }
    };

    class Trie
    {
        private:
            TrieNode *root = NULL;

        public:
            Trie()
            {
                if (!root)
                {
                    this->root = new TrieNode();
                }
            }
            TrieNode* insert(string word)
            {
                if (!root)
                    root = new TrieNode();
                TrieNode* current = root;
                int length = word.length();
                //insert "abc"
                for(int i = 0; i < length; ++i)
                {
                    if (current->getChild(word.at(i)) == NULL)
                    {
                        current->insert(word.at(i));
                    }
                    current = current->getChild(word.at(i));
                }
                current->setLeaf(true);
                current->setWord(word);
                current->setFrequency(current->getFrequency() + 1);
                return current;
            }
    };



    struct cmp
    {
        bool operator()(HeapNode* &a, HeapNode* &b)
        {
            return (a->frequency > b->frequency);
        }
    };
    typedef priority_queue<HeapNode*, vector<HeapNode*>, cmp > MinHeap;


    void insertUtils(Trie *root, MinHeap &pq, string word )
    {
        if (!root)
            return;

        TrieNode* current = root->insert(word);
        HeapNode *heapNode = current->getHeapNode();
        if(heapNode)// if word already present in heap 
        {
            heapNode->frequency += 1;
        }else if (pq.empty() || pq.size() < K_TH)
        {// if word not present in heap and heap is not full;
            heapNode = new HeapNode();
            heapNode->word = word;
            heapNode->frequency = 1;
            heapNode->trieNode = current;
            current->setHeapNode(heapNode);
            pq.push(heapNode);
        }else if (pq.top()->frequency < current->getFrequency())
        {   // if word is not present and heap is full;
            HeapNode *temp = pq.top();
            //remove first element and add current word
            pq.pop();
            delete temp;
            heapNode = new HeapNode();
            current->setHeapNode(heapNode);
            pq.push(heapNode);
        }
    }


    void printKMostFrequentWords(vector<std::string> input)
    {

        Trie *root = new Trie();
        MinHeap minHeap;
        for (vector<string>::iterator it = input.begin(); it != input.end(); ++it)
        {
            insertUtils(root, minHeap, *it);
        }

        while(!minHeap.empty())
        {
            HeapNode *heapNode = minHeap.top();
            cout << heapNode->word << ":" << heapNode->frequency << endl;
            minHeap.pop();
        }


    }

    int main() {

    vector<std::string>input( {
        "abc", "def", "ghi",
        "jkl", "abc", "def",
        "mno", "xyz", "abc"

    } ) ;
    printKMostFrequentWords(input);
    }