Подсчет количества вхождений слов в текстовый файл

Вы можете использовать хеш-таблицу, и каждая запись в хеш-таблице должна указывать на структуру, содержащую слово и количество раз, которое оно было найдено до сих пор.

Да, словарь с парами слово-вхождение будет работать нормально, и обычный способ реализовать такой словарь - использовать хеш-таблицу (или, иногда, двоичное дерево поиска).

Вы также можете использовать три (или его сжатую версию, "Патрисия Три" / Radix trie), сложность которого асимптотически оптимальна для этой проблемы, хотя я подозреваю, что на практике это может быть медленнее, чем (хорошая) реализация хеш-таблицы.

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

ПРЕДУПРЕЖДЕНИЕ непроверенный код:

#include <stdio.h>

struct LLNode
{
    LLNode* Next;    
    char*   Word;
    int     Count;
};

void PushWord(LLNode** list, const char* word)
{
    LLNode* node = NULL;
    unsigned int len = 0;
    if (*list == NULL) 
    {
        $list = new LLNode;
        $list = "\0";
    }
    node = *list;
    while ((node = node->Next) != NULL) // yes we are skipping the first node
    {
        if (!strcmp(node->Word, word))
        {
            node->Count++;
            break;
        }

        if (!node->Next)
        {
            LLNode* nnode = new LLNode;
            nnode->Count = 1;
            node->Next = nnode;
            len = strlen(word);
            node->Word = new char[len + 1];
            strcpy(node->Word, word);
            break;
        }
    }
}

void GetCounts(LLNode* list)
{
    if (!list)
        return;
    LLNode* node = list;
    while ((node = node->Next) != NULL) // yes we are skipping the first node
    {
        printf("Word: %s, Count: %i", node->Word, node->Count);
    }
}

void PushWords(LLNode** list, const char* words)
{
    char ch = '\0';
    unsigned int len = strlen(words);
    char buff[len]; // to be sure we have no buffer ovverunes. May consume too much memery for your application though.
    int index = 0;
    for (unsigned int i = 0; i < len; i++)
    {
        ch = words[i];
        if (index > 0 && ch == ' ')
        {
            ch[index + 1] = '\0';
            PushWords(list, buff);
            index = 0;
        }
        else if (ch != ' ')
        {
            ch[index++] = ch;
        }
    }

    if (index > 0 && ch == ' ')
    {
        ch[index + 1] = '\0';
        PushWords(list, buff);
        index = 0;
    }
}

int main()
{
    LLNode* list = NULL;
    PushWords(&list, "Hello world this is a hello world test bla");
    GetCount(list);
    // release out memery here
}

Я написал это только сейчас, так что, вероятно, это не сработает, но это общая идея.

Еще один черновик на этот раз на C++ (примечание: у std :: map довольно хорошее время поиска):

#include <iostream>
#include <string>
#include <map>

using namespace std;

typedef map<string, int> CountMap;

void PushWords(CountMap& list, const char* words)
{
    char ch = '\0';
    unsigned int len = strlen(words);
    string str;
    int index = 0;
    for (unsigned int i = 0; i < len; i++)
    {
        ch = words[i];
        if (index > 0 && ch == ' ')
        {
            list[str] = list[str] + 1;
            index = 0;
        }
        else if (ch != ' ')
        {
            str += ch;
            index++;
        }
    }

    if (index > 0 && ch == ' ')
    {
        list[str] = list[str] + 1;
    }
}

void PrintCount(CountMap& list)
{
    CountMap::iterator iter = list.begin(), end = list.end();
    for (; iter != end; ++iter)
    {
        cout << (*iter).first << " : " << (*iter).second;
    }
}


int main()
{
    CountMap map;
    PushWords(map, "Hello world this is a hello world test bla");
    PrintCount(map);
}

Для любопытных вот простое решение проблемы подсчета слов на Ruby. Это должен быть в основном тот же алгоритм на C, только с гораздо большим количеством кода.

h = Hash.new(0)
File.read("filename.txt").split.each do |w|
  h[w] += 1
end
p h

Это считается?

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv)
{
    char buffer[2048];
    if (argc != 2)
    {
        fprintf(stderr, "Usage: %s file\n", argv[0]);
        exit(EXIT_FAILURE);
    }
    snprintf(buffer, sizeof(buffer), "tr -cs '[a-z][A-Z]' '[\\n*]' < %s |"
                                     " sort | uniq -c | sort -n", argv[1]);
    return(system(buffer));
}

Он в основном инкапсулирует канонический сценарий, показывающий, как считать слова в Unix в качестве сценария оболочки.

Команда 'tr' переводит все, что не является алфавитным символом, в новую строку и вытесняет дубликаты. Первый "sort" группирует все вхождения каждого слова вместе. uniq -c подсчитывает количество последовательных появлений каждого слова, печатает слово и его количество. Второй «sort» размещает их в порядке увеличения повторов. Возможно, вам придется поработать с опциями для «tr»; это не самая стабильная команда от системы к системе, и ей удается регулярно заставлять меня выполнять ручные взломы. В Solaris 10 с использованием / usr / bin / tr приведенный выше код создает (из собственного источника):

   1
   1 A
   1 EXIT
   1 FAILURE
   1 Usage
   1 Z
   1 a
   1 c
   1 cs
   1 exit
   1 file
   1 fprintf
   1 if
   1 main
   1 return
   1 sizeof
   1 snprintf
   1 stderr
   1 stdio
   1 stdlib
   1 system
   1 tr
   1 uniq
   1 z
   2 argc
   2 char
   2 h
   2 include
   2 int
   2 s
   2 sort
   3 argv
   3 n
   4 buffer

Для отдельных слов вообще нет необходимости писать программу, если она не является частью чего-то большего:

sed -e 's/[[:space:]]/\n/g' < file.txt | grep -c WORD

#include <conio.h>
#include <iostream.h>
#include <fstream.h>
#include <cstdlib>

struct stdt
{
       char name[20] ;
       int id ;

}; //std

int main()
{
      stdt boy ;
      int a = 0 ;
      ofstream TextFile ;
      cout << "Begin File Creation \n" ;
      TextFile.open("F:\\C++ Book Chapter Program\\Ch  7\\File.txt" );
      if ( !TextFile)
      {
           cerr <<"Erro 100 Openoing File.DAT" ;
           exit(100);     
      }//end if
      while ( a < 3 )
      {
            TextFile.write( (char*) &boy , sizeof (boy) ) ;
            cout << "\nEnter Name : " ;
            cin  >> boy.name;
            cout << "\nEnter ID : " ;
            cin  >> boy.id ;
            a++;
      }//end while

      TextFile.close();
      cout << "\nEnd File Creation" ;

      ifstream TextFile1 ;
      TextFile1.open("F:\\C++ Book Chapter Program\\Ch  7\\File.txt" );
      while ( TextFile1.read( (char*) &boy , sizeof (boy) ) )
      {
            cout << "\nEnter Name : " << boy.name; 
            cout << "\nEnter ID : " << boy.id ;


      }// end While

      getch();
      return 0 ;
}//end main

в Perl:

my %wordcount = ();
while(<>){map {$wordcount{$_}++} (split /\s+/)}
print "$_ = $wordcount{$_}\n" foreach sort keys %wordcount;

и в Perl Golf (просто для удовольствия):

my%w;                       
map{$w{$_}++}split/\s+/while(<>); 
print"$_=$w{$_}\n"foreach keys%w;