C言語関係掲示板

過去ログ

No.430.出現頻度の高い順に単語を表示

[戻る] [ホームページ]
No.3023

出現頻度
投稿者---瞳(2002/10/20 22:04:39)


今、英文ファイルを読み込んで、ハッシュ法を使い、出現頻度の高い順に表示するって言うプログラムを作成してるんですが、
ファイルを読み込んで、単語の総数を数え、異なる単語の数を数えるところまでできているのですが、高い順に表示するができません。
どーしようもなくなってしまったので、どなたかご教授ください。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

#define HASHSIZE 101 /* ハッシュ表の大きさ (素数) */
#define MAXWORDLEN 128 /* 最大単語長 */
#define FNAME "file2.txt"

int wordlen; /* 単語長 */
unsigned long words, newwords; /* 単語, 新単語カウンタ */
char word[MAXWORDLEN + 1]; /* 現在の単語 */

typedef struct node { /* 2分木のノード */
struct node *left, *right; /* 左右の子 */
char *key; /* キー (文字列) */
} *nodeptr;

struct node nil = {NULL, NULL, word}; /* 番人 */
nodeptr hashtable[HASHSIZE]; /* ハッシュ表 */

int hash(char *s) /* 簡単なハッシュ関数 */
{
unsigned v;

for (v = 0; *s != '\0'; s++)
v = ((v << CHAR_BIT) + *s) % HASHSIZE;
return (int)v;
}

void insert(void) /* 挿入 (登録) */
{
int cmp;
nodeptr *p, q;

words++;
p = &hashtable[hash(word)];
while ((cmp = strcmp(word, (*p)->key)) != 0)
if (cmp < 0) p = &((*p)->left );
else p = &((*p)->right);
if (*p != &nil) return; /* すでに登録されている */
newwords++;
if ((q = malloc(sizeof *q)) == NULL
|| (q->key = malloc(wordlen + 1)) == NULL) {
printf("メモリ不足.\n"); exit(EXIT_FAILURE);
}
strcpy(q->key, word);
q->left = &nil; q->right = *p; *p = q;
}

void getword(void)
{
int c;

wordlen = 0;
do {
if ((c = getchar()) == EOF) return;
} while (! isalpha(c));
do {
if (wordlen < MAXWORDLEN) word[wordlen++] = tolower(c);
c = getchar();
} while (isalpha(c));
word[wordlen] = '\0';
}

int main()
{
int i;

words = newwords = 0;
for (i = 0; i < HASHSIZE; i++) hashtable[i] = &nil;
if (freopen(FNAME, "r", stdin) == NULL)
return fprintf(stderr, "can't open %s\n", FNAME), 1;
while (getword(), wordlen != 0) insert();
printf("%lu words, %lu different words\n", words, newwords);
return EXIT_SUCCESS;
}




No.3024

Re:出現頻度
投稿者---かずま(2002/10/21 02:25:53)


> 今、英文ファイルを読み込んで、ハッシュ法を使い、出現頻度の高い順に
> 表示するって言うプログラムを作成してるんですが

以前、質問された、標準入力をファイル入力に変更するプログラムから、全然
進展がないようなのですが、ほんとうに、プログラムを作成しようとしていますか。

さて、この掲示板の過去ログの No.335 に、私の書いた、単語の出現頻度順に表示する
プログラムがありますが、ハッシュは使っていません。だから、質問者の期待に答える
ことはできませんが、何かの参考になりませんか。

そのプログラムですが、今見たら、バグを見つけてしまったので、あらためて提示します。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define TABLE_SIZE   3000
#define FNAME        "file2.txt"

typedef struct {
    char *word;
    int count;
} Word;

int get_word(FILE *fp, char *word, int size)
{
    int c, i = 0;

    do {
        if ((c = getc(fp)) == EOF) return EOF;
    } while (! isalpha(c));
    size--;
    do {
        if (i < size) word[i++] = tolower(c);
        c = getc(fp);
    } while (isalpha(c));
    word[i] = '\0';
    return i;
}

int compare(const void *a, const void *b)
{
    const Word *p1 = a, *p2 = b;
    return p2->count - p1->count;
}

int main()
{
    Word table[TABLE_SIZE];
    char word[128];
    int  n = 0, i;
    FILE *fp = fopen(FNAME, "r");

    if (fp == NULL) return printf("can't open %s\n", FNAME), 1;

    while (get_word(fp, word, sizeof(Word)) != EOF) {
        for (i = 0; i < n; i++)
            if (strcmp(word, table[i].word) == 0) break;
        if (i == n) {
            if (++n == TABLE_SIZE) return printf("too many words\n"), 1;
            table[i].word = strdup(word);
            if (table[i].word == NULL) return printf("out of memory\n"), 1;
            table[i].count = 1;
        } else
            table[i].count++;
    }

    qsort(table, n, sizeof *table, compare);

    for (i = 0; i < n; i++)
        printf("%4d %s\n", table[i].count, table[i].word);
    return 0;
}


No.3033

Re:出現頻度
投稿者---かずま(2002/10/21 18:49:35)


>    while (get_word(fp, word, sizeof(Word)) != EOF) {

訂正です。

    while (get_word(fp, word, sizeof word) != EOF) {


No.3034

Re:出現頻度
投稿者---瞳(2002/10/21 20:33:31)


参考プログラムありがとうございます。

No.3038

Re:出現頻度
投稿者---かずま(2002/10/21 23:12:56)


> Word table[TABLE_SIZE];

表を順番に探索するのは時間が掛かるので、二分木にしてみました。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define FNAME   "file2.txt"

typedef struct Node Node;
struct Node {
    char *word; int count;
    Node *left, *right;
};

typedef struct {
    Node *np;  int count;
    Node **sp; int index;
} Tree;

void *Malloc(size_t size)
{
    void *p = malloc(size);
    if (p == NULL) fprintf(stderr, "out of memory\n"), exit(1);
    return p;
}

Tree *create_tree(void)
{
    Tree *tp = Malloc(sizeof(Tree));
    tp->np = NULL;  tp->count = 0;
    tp->sp = NULL;  tp->index = 0;
    return tp;
}

char *Strdup(const char *s)
{
    return strcpy(Malloc(strlen(s) + 1), s);
}

void add_tree(Tree *tp, const char *word)
{
    Node *np, **npp = &tp->np;  int diff;

    while (*npp) {
        np = *npp;
        diff = strcmp(word, np->word);
        if (diff == 0) { np->count++; return; }
        npp = (diff < 0) ? &np->left : &np->right;
    }
    np = Malloc(sizeof(Node));
    np->word = Strdup(word);
    np->count = 1;
    np->left = np->right = NULL;
    *npp = np;
    tp->count++;
}

void add_node(Tree *tp, Node *np)
{
    if (np == NULL) return;
    add_node(tp, np->left);
    tp->sp[tp->index++] = np;
    add_node(tp, np->right);
}

int compare_tree(const void *a, const void *b)
{
    Node **p1 = (Node **)a, **p2 = (Node **)b;
    return (*p2)->count - (*p1)->count;
}

void sort_tree(Tree *tp)
{
    tp->sp = Malloc(sizeof(Tree *) * tp->count);
    add_node(tp, tp->np);
    qsort(tp->sp, tp->count, sizeof(Tree *), compare_tree);
}

void print_tree(Tree *tp)
{
    int i;
    for (i = 0; i < tp->count; i++)
        printf("%5d %s\n", tp->sp[i]->count, tp->sp[i]->word);
}

void free_node(Node *np)
{
    if (np == NULL) return;
    free_node(np->left);
    free_node(np->right);
    free(np);
}

void release_tree(Tree *tp)
{
    free_node(tp->np);
    free(tp);
}

int get_word(FILE *fp, char *word, int size)
{
    int c, i = 0;

    do {
        if ((c = getc(fp)) == EOF) return EOF;
    } while (! isalpha(c));
    size--;
    do {
        if (i < size) word[i++] = tolower(c);
        c = getc(fp);
    } while (isalpha(c));
    word[i] = '\0';
    return i;
}

int main()
{
    char word[128];
    Tree *tp;
    FILE *fp = fopen(FNAME, "r");

    if (fp == NULL) return printf("can't open %s\n", FNAME), 1;
    tp = create_tree();
    while (get_word(fp, word, sizeof word) != EOF)
        add_tree(tp, word);
    sort_tree(tp);
    print_tree(tp);
    release_tree(tp);
    return 0;
}


No.3044

Re:出現頻度
投稿者---かずま(2002/10/22 01:59:08)


> 表を順番に探索するのは時間が掛かるので、二分木にしてみました。

malloc() が返すポインタで、free() し忘れているものがありました。
このプログラムは、終了してしまうので、メモリーリークはありませんが、
次のように訂正しておきます。
void free_node(Node *np)
{
    if (np == NULL) return;
    free_node(np->left);
    free_node(np->right);
    free(np->word);     /* <-- */
    free(np);
}

void release_tree(Tree *tp)
{
    free_node(tp->np);
    free(tp->sp);       /* <-- */
    free(tp);
}


C++ だと、標準ライブラリを使えば、メモリ管理は考えなくてもよくなります。
また、道具立てがそろっているので、プログラムはこんなに短くなります。
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <cctype>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

const char fname[] = "file2.txt";

string get_word(istream& is)
{
    string word;
    int c;
    do {
        c = is.get();
        if (c == EOF) return word;
    } while (! isalpha(c));
    do {
        word += tolower(c);
        c = is.get();
    } while (isalpha(c));
    return word;
}

typedef pair<string, int> SI;

bool compare(const SI& a, const SI& b) { return a.second > b.second; }

int main()
{
    ifstream ifs(fname);
    if (! ifs) return cerr << "can't open " << fname << endl, 1;

    map<string, int> data;
    string word;
    while (word = get_word(ifs), !word.empty())
        data[word]++;

    vector<SI> v(data.begin(), data.end());
    sort(v.begin(), v.end(), compare);
    for (vector<SI>::const_iterator it = v.begin(); it != v.end(); ++it)
        cout << setw(5) << it->second << ' ' << it->first << endl;
}


No.3062

Re:出現頻度
投稿者---瞳(2002/10/23 02:48:07)


いろいろ参考プログラム教えていただき、ありがとうございます。
ですが、ぎりぎりまでがんばってみたけど、これから先に進むことができません。
非常に、不快に思うかもしれませんが、ハッシュ法でのやり方をよろしかったら教えてください

No.3065

Re:出現頻度
投稿者---かずま(2002/10/23 04:13:16)


> ハッシュ法でのやり方をよろしかったら教えてください

なぜ、ハッシュ法でやろうとするのですか。

この問題の出所を教えてください。
書名(出版社名と著者名)と、何ページ目にある問題なのか。
あるいは、学校の課題だったら、問題の正確な記述をもらさず書いてください。

No.3082

Re:出現頻度
投稿者---瞳(2002/10/23 20:42:07)


この問題は学校の課題です。問題は、英語で書かれたテキストファイルを読み込み,単語の出現頻度を求め,
高い順に表示するプログラムを作成せよ.
このときハッシュ表を利用すること.です



No.3096

Re:出現頻度
投稿者---かずま(2002/10/24 03:21:29)


> この問題は学校の課題です。
> 問題は、英語で書かれたテキストファイルを読み込み,単語の出現頻度を求め,
> 高い順に表示するプログラムを作成せよ.
> このときハッシュ表を利用すること.です

これだけですか?

では、なぜ、最初のプログラムで、ハッシュだけでなく、二分木を使い、さらに
「番人」というテクニックまで使ったのですか。

また、出現頻度を求めるのなら、単語のカウンタは、個々の単語ごとに持つべきもの
であるのに、単語の総数と新語の総数のカウンタしか用意しなかったのはなぜですか。

元のプログラムは、グローバル変数でデータのやり取りをしていて、好ましくないの
ですが、最小限の修正で、目的のプログラムにしてみました。

修正内容は、
(1) struct node に count を追加。
(2) ソート用の配列 nodearray と index を追加。
(3) insert() 内に、count = 1 と、count++ を追加。
(4) traverse(), compare(), sort_print() を追加。
(5) 単語数の printf() を sort_print() の呼び出しに変更。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

#define HASHSIZE 101 /* ハッシュ表の大きさ (素数) */
#define MAXWORDLEN 128 /* 最大単語長 */
#define FNAME "file2.txt"

int wordlen; /* 単語長 */
unsigned long words, newwords; /* 単語, 新単語カウンタ */
char word[MAXWORDLEN + 1]; /* 現在の単語 */

typedef struct node { /* 2分木のノード */
    struct node *left, *right; /* 左右の子 */
    char *key; /* キー (文字列) */
    int count;                                        /* KAZUMA */
} *nodeptr;

struct node nil = {NULL, NULL, word}; /* 番人 */
nodeptr hashtable[HASHSIZE]; /* ハッシュ表 */
nodeptr *nodearray;                                   /* KAZUMA */
int index;                                            /* KAZUMA */

int hash(char *s) /* 簡単なハッシュ関数 */
{
    unsigned v;

    for (v = 0; *s != '\0'; s++)
        v = ((v << CHAR_BIT) + *s) % HASHSIZE;
    return (int)v;
}

void insert(void) /* 挿入 (登録) */
{
    int cmp;
    nodeptr *p, q;

    words++;
    p = &hashtable[hash(word)];
    while ((cmp = strcmp(word, (*p)->key)) != 0)
        if (cmp < 0) p = &((*p)->left );
        else p = &((*p)->right);
    if (*p != &nil) { (*p)->count++; return; }     /* KAZUMA */
    newwords++;
    if ((q = malloc(sizeof *q)) == NULL
        || (q->key = malloc(wordlen + 1)) == NULL) {
        printf("メモリ不足.\n"); exit(EXIT_FAILURE);
    }
    strcpy(q->key, word);
    q->count = 1;                                  /* KAZUMA */
    q->left = &nil; q->right = *p; *p = q;
}

void traverse(nodeptr p)                              /* KAZUMA */
{
    if (p == &nil) return;
    traverse(p->left);
    nodearray[index++] = p;
    traverse(p->right);
}

int compare(const void *a, const void *b)             /* KAZUMA */
{
    nodeptr x = *(nodeptr *)a, y = *(nodeptr *)b;
    return y->count - x->count;
}

void sort_print(void)                                 /* KAZUMA */
{
    unsigned long i;

    nodearray = malloc(newwords * sizeof nodearray);
    if (nodearray == NULL) printf("メモリ不足.\n"), exit(EXIT_FAILURE);
    index = 0;
    for (i = 0; i < HASHSIZE; i++)
        traverse(hashtable[i]);
    qsort(nodearray, newwords, sizeof nodearray, compare);
    for (i = 0; i < newwords; i++)
        printf("%5d %s\n", nodearray[i]->count, nodearray[i]->key);
}

void getword(void)
{
    int c;

    wordlen = 0;
    do {
        if ((c = getchar()) == EOF) return;
    } while (! isalpha(c));
    do {
        if (wordlen < MAXWORDLEN) word[wordlen++] = tolower(c);
        c = getchar();
    } while (isalpha(c));
    word[wordlen] = '\0';
}

int main()
{
    int i;

    words = newwords = 0;
    for (i = 0; i < HASHSIZE; i++) hashtable[i] = &nil;
    if (freopen(FNAME, "r", stdin) == NULL)
    return fprintf(stderr, "can't open %s\n", FNAME), 1;
    while (getword(), wordlen != 0) insert();
    sort_print();                                     /* KAZUMA */
    return EXIT_SUCCESS;
}


No.3104

Re:出現頻度
投稿者---かずま(2002/10/24 10:49:43)


> nodearray = malloc(newwords * sizeof nodearray);

> qsort(nodearray, newwords, sizeof nodearray, compare);

sort_print() の中のこの 2行ですが、sizeof nodearray は、
意味的には間違いです。
たまたま、ポインタということでサイズは同じなんですが、
sizeof *nodearray または sizeof (nodeptr) に訂正します。

No.3253

Re:出現頻度
投稿者---瞳(2002/10/31 01:45:12)


返信ありがとうございます。レス遅れてすいません。
かずまさんには、ほんとにご迷惑をおかけしました。おかげさまで問題は解決しました。