文字列の頻度とソート【C言語】

[mathematica1995]

1行1000バイト以下で最大1,000,000バイト以下のASCII文字テキストを標準入力から入力し，連続するアルファベットの組を，頻度とアルファベットの組を(\t)で区切って頻度の高い順に出力する（大文字と小文字の区別はせず，さらに同じ頻度のものは辞書式順序で出力する．ただし，頻度０のものは出力しない．）という問題で，初心者のため，何をどうしたらいいかわかりません．小文字にするところまではしたのですが，手詰まりです．よろしくお願いします．

コード:

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define LINE_SIZE 1000
#define TEXT_SIZE 1000000

//関数プロトタイプ宣言


//メイン関数
int main()
{
	char line[LINE_SIZE];
	char text[TEXT_SIZE] = "";
	
	//ファイル終端に達するまで１行ずつ文字列を読み込む
	while(!feof(stdin))
	{
		if (fgets(line, LINE_SIZE, stdin) == NULL) break;
		strcat(text, line);
	}
	
	//小文字に変換
	int n = strlen(text);
	for (int i = 0; i < n; i ++) text[i] = tolower(text[i]);
	
	//読み込んだテキスト全体を出力
	printf("%s", text);
	
	return 0;
}

[metaphor]

ソートのアルゴリズムは何を学ばれましたか。

[みけCAT]

入力を読み込んだので、次は連続するアルファベットの組の数を数えましょう。
例えばこんな感じでしょうか？
※省略があり、これだけでは動きません
※ASCIIのようなアルファベットの文字コードが連続している環境でのみうまく動きます

コード:

int main(void) {
	char text[TEXT_SIZE];

	int pair_num[26][26] = {{0}};
	int i;

	/* textにデータを入力する */

	for (i = 0; text[i] != '\0' && text[i + 1] != '\0'; i++) {
		if (islower(text[i]) && islower(text[i + 1])) {
			/* 連続するアルファベットの組なので、数える */
			pair_num[text[i] - 'a'][text[i + 1] - 'a']++;
		}
	}
}

[metaphor]

問題が少し曖昧かなとおもいます。

コード:

//①1行1000バイト以下で最大1,000,000バイト以下のASCII文字テキストを標準入力から入力
//②連続するアルファベットの組を，頻度とアルファベットの組を(\t)で区切って
//③頻度の高い順に出力する（大文字と小文字の区別はせず，
//④さらに同じ頻度のものは辞書式順序で出力する
//⑤ただし，頻度０のものは出力しない
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define LINE_SIZE 1000//1行1000バイト以下
#define TEXT_SIZE 1000000//最大1,000,000バイト以下
 
//関数プロトタイプ宣言
//②連続するアルファベットの組に分割 
int pair(char *s);
// ...
//③頻度の検出
//
int my_sort(char* s,char* word);

//メイン関数
int main()
{
    char line[LINE_SIZE];
    //char text[TEXT_SIZE] = "";

    char text[]="This is a pen CAA UUW YYYZ";//[サンプル]
    char text[TEXT_SIZE];
    //---関数化
	int pair_num[26][26] = {{0}};
    int i;
    /* textにデータを入力する */
 
    for (i = 0; text[i] != '\0' && text[i + 1] != '\0'; i++) {
        if (islower(text[i]) && islower(text[i + 1])) {
            /* 連続するアルファベットの組なので、数える */
            pair_num[text[i] - 'a'][text[i + 1] - 'a']++;
        }
    }
    //---
    //ファイル終端に達するまで１行ずつ文字列を読み込む.
	/*
    while(!feof(stdin))
    {
        if (fgets(line, LINE_SIZE, stdin) == NULL) break;
        strcat(text, line);//ASCII文字テキスト
    }
    */
    //小文字に変換:[=//③（大文字と小文字の区別はせず]
    int n = strlen(text);
    for (int i = 0; i < n; i ++) text[i] = tolower(text[i]);
    
    //読み込んだテキスト全体を出力
    printf("%s", text);
	//②連続するアルファベットの組を，頻度とアルファベットの組を(\t)で区切って
    // 
    //④さらに同じ頻度のものは辞書式順序で出力する
    //
	//⑤ただし，頻度０のものは出力しない
	
    return 0;
}

[mathematica1995]

ソートは幾つか習いましたがメインで習ったのは、バブル、クイック、マージ、ヒープの４つです。

[metaphor]

それでは簡単なバブル・ソートで考えとあとで得意なソートアルゴリズムに変えましょう。あと自分の考えをコメントに書き加えてください。問題がを間違えてとらえている可能性があります。具体的に何かサンプル入力とサンプル出力を考え付きますか(最初は簡単なサンプル

コード:

char text[]="This is a pen CAA UUW YYYZ";//[サンプル]

みたいな感じでいいですか?この場合の出力はどうなると思われますか。

[mathematica1995]

この例文での場合出力は

コード:

is 2
yy 2
aa 1
ca 1
en 1
hi 1
pe 1
th 1
uu 1
uw 1
yz 1

こんな感じになってほしいです。

[かずま]

テキストの読み込みですが、サイズが 1メガバイト近い自動変数を関数の
ローカル変数として用意するのは、ちょっと気になります。

入力に fgets を使う場合、EOF の検出は fgets が NULL を返すかどうかで
判断します。feof は使いません。

strcat は、第1引数の文字列の最後を見つけるために無駄なコストがかかるので
何度も繰り返すのは避けたいと思います。

次のように書くことをお勧めします。

コード:

    static char text[TEXT_SIZE + 1];  // 静的変数にしました
    int n = fread(text, 1, TEXT_SIZE, stdin);

しかし、連続するアルファベットの組の頻度が欲しいだけですから、
テキストを全部メモリー中に読み込む必要はないでしょう。

頻度を 2次元配列に持つと、どうやってソートしたらいいか困りませんか？

ということで、私なら次のようにします。

コード:

#include <stdio.h>  // getchar, printf
#include <ctype.h>  // isalpha, tolower

int main(void)
{
    int i, j, n = 0, a[26*26], c[26*26] = { 0 };

    while ((i = getchar()) != EOF)
        if (isalpha(i)) 
            for (; isalpha(j = getchar()); i = j)
                c[(tolower(i)-'a')*26+(tolower(j)-'a')]++;
    for (i = 0; i < 26*26; i++)

        if (c[i]) {
            for (j = n++; j > 0 && c[a[j-1]] < c[i]; j--)
                a[j] = a[j-1];
            a[j] = i;
        }
    for (i = 0; i < n; i++) {
        j = a[i];
        printf("%d\t%c%c\n", c[j], j/26+'a', j%26+'a');
    }
    return 0;
}

[mathematica1995]

かずまさん

二次元配列のソートがわからなかったので、かずまさんのソースを入力しコンパイルしたところ上手いこと実行できたのですが，初心者が故，何を行っているのかがよくわからないので「//（/* */）」で何を行っているかという説明コメントをしていただけるととても助かります．

[かずま]

アルファベット 2文字の組み合わせは、26 x 26 = 676通り。
辞書順に並べて次のようにインデックス番号を付けます。

コード:

  aa ab ac ad ... az ba bb bc ... zy  zz
  0  1  2  3      25 26 27 28     674 675

変数 i、j に 'a'～'z' が入っているとき
(i - 'a') * 26 + (j - 'a') でインデックス番号が求まります。
逆に、インデックス番号 i が与えられたとき、
i / 26 + 'a'、i % 26 + 'a' で 2文字が求まります。

コード:

#include <stdio.h>  // getchar, printf
#include <ctype.h>  // isalpha, tolower

int main(void)
{
    int i, j;
    int n = 0;      // ソート結果の個数(頻度が 0 以外のもの)
    int a[26*26];   // ソート結果が入る配列(array)
    int c[26*26] = { 0 };  // 頻度カウンター(counter)

    while ((i = getchar()) != EOF)  // ファイルの終わりになるまで、変数 i に 1文字ずつ読み込む。
        if (isalpha(i))             // 1文字目がアルファベットなら、
            for (; isalpha(j = getchar()); i = j) // 2文字目を変数 j に読み込み、それがアルファベットなら、
                c[(tolower(i)-'a')*26+(tolower(j)-'a')]++; // 2文字の組み合わせのカウンターを 1増やす。
                                   // for文の i = j で、2文字目を新たな 1文字目として、繰り返す。

    for (i = 0; i < 26*26; i++)    // 頻度カウンターを全部調べる。i は 2文字の組み合わせのインデックス番号
        if (c[i]) {                // i番目の頻度が 0 でなければ、
            for (j = n++; j > 0 && c[a[j-1]] < c[i]; j--)  // a の末尾から順に、c[i] より頻度が小さい
                a[j] = a[j-1];　　                         // ものをずらし、i を入れる場所を確保する。
            a[j] = i;              // i を入れる。n は for文の最初で 1増えている。挿入ソートである。
        }

    for (j = 0; j < n; j++) {      // ソート結果を順にみていく。
        i = a[j];                  // ソート結果から頻度カウンターのインデックス番号を取り出す。
        printf("%d\t%c%c\n", c[i], i/26+'a', i%26+'a'); // 表示
    }
    return 0;
}

[かずま]

バブルソートにしてみました。

コード:

#include <stdio.h>  // getchar, printf
#include <ctype.h>  // isalpha, tolower

int main(void)
{
    int i, j, k, n = 0, a[26*26], c[26*26] = { 0 };

    while ((i = getchar()) != EOF)
        if (isalpha(i))
            for (; isalpha(j = getchar()); i = j)
                c[(tolower(i)-'a')*26+(tolower(j)-'a')]++;

    for (i = 0; i < 26*26; i++)
        if (c[i]) a[n++] = i;  // 頻度が 0 でないものだけを a に入れる

    for (i = 1; i < n; i++)    // a[0]～a[n-1] をバブルソート
        for (j = n; --j >= i; )
            if (c[a[j-1]] < c[a[j]])
                k = a[j-1], a[j-1] = a[j], a[j] = k;

    for (j = 0; j < n; j++) {
        i = a[j];
        printf("%d\t%c%c\n", c[i], i/26+'a', i%26+'a');
    }
    return 0;
}

バブルソートは安定ソートだから、頻度が同じものを入れ替えることはなく、
辞書順が保たれます。

[mathematica1995]

かずまさん、ありがとうございます。
非常に丁寧でわかりやすく理解できました。

この問題はかずまさんの返信によりいくつかの解決方法が示され解決しました。