質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

2回答

2619閲覧

C言語による算術符号化

mamimumemo700

総合スコア12

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2018/12/13 04:25

編集2018/12/13 05:06

アルファベットとその出現確率を与え、入力された文字列を算術符号化するプログラムを書いたのですが、小数が希望の桁数まで計算されていないのか上手くいきません。double型で計算しているのに結果の桁数がとても小さいです。どうかご教授をお願いいたします。

分割された区間の中央を代表値とし、その二進表記の小数点下l桁を符号語としています。

C

1#include <stdio.h> 2#include <string.h> 3#include <math.h> 4 5struct SET{ 6 char s; 7 double p; 8};//アルファベットとその確率を格納 9 10 11void encode(int asize,struct SET *S,char *s){//符号化のための関数 12 double range[asize],buf,m; 13 int l; 14 range[0]=0; 15 16 for(int i=1;i<=asize;i++){ 17 range[i]=range[i-1]+S[i-1].p; 18 }//区間[0,1)の分割 19 20 for(int i=0;i<strlen(s);i++){ 21 for(int j=0;j<asize;j++){ 22 if(S[j].s==s[i]){ 23 printf("s[%d]=%s\n",i,&S[j].s); 24 range[0]=range[j]; 25 buf=range[j+1]; 26 for(int k=1;k<=asize;k++){ 27 range[k]=range[k-1]+S[k-1].p*(buf-range[0]); 28 } 29 printf("range:[%lf,%lf)\n",range[0],range[asize]);//最終的な区間を表示 30 } 31 } 32 } 33 34 m=(range[0]+range[asize])/2; 35 36 printf("range:[%lf,%lf)\n",range[0],range[asize]); 37 printf("encoded:"); 38 l=ceil(-log2l(m))+1;//符号語の長さを決定するl 39 for(int i=1;i<=l;i++){ 40 printf("%d",(int)floor(m*2));//符号語を表示 41 m=m*2-floor(m*2); 42 } 43 printf("\n"); 44 45} 46 47int main (){ 48 int asize,i; 49 char s[256];//文字列 50 struct SET S[256]; 51//アルファベットと出現確率を入力 52 printf("alphabet size:"); 53 scanf("%d",&asize); 54 55 for(i=0;i<asize;i++){ 56 57 printf("symbol_%d:",i); 58 scanf("%s",&S[i].s); 59 60 printf("p_%d:",i); 61 scanf("%lf",&S[i].p); 62 } 63 64 printf("symbols:"); 65 scanf("%s",s);//文字列を入力 66 67 encode(asize,S,s); 68 69 70 return 0; 71 72} 73

例えば
a
0.1
b
0.2
c
0.4
d
0.2
を与えると
記号列aadbbdcccc
符号語は
000010001100001010001
のはずが先頭6桁しか表示されません、区間の両端の値も桁数が小さいです。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

yohhoy

2018/12/13 04:58

符号化対象の文字列データは何ですか?(質問文中から欠落しているように見受けられます)
guest

回答2

0

ベストアンサー

ご質問のコードにはy_waiwaiさんご指摘の点以外にもいろいろ危なっかしい間違いがあります(※)が、本質的には符号の長さ(l)を求めるのに単順にmを用いてるのが根本的な問題といえると思います。lを求める式を見ますと「最上位ビットがあるあたりまでのビット数」となっています。それを最終的な符号語mに対して求めてしまうと当然ながら先頭の1のビットあたりまでしか結果に現れず、本来必要なビットのほとんどが欠落してしまいます。

充分かどうかはひとまずおいて、ここはmではなく少なくとも最終的なrangeに対してrange[asize] - range[0]で求まる「区間の幅を表す値」の最上位ビットの程度までは必要です。そうしておくと最後のアルファベットの違いが符号語の最終ビットあたりに現われると期待できると思います。

C

1l = ceil(-log2l(m)) + 1; 2// ではなくて 3double gap = range[asize] - range[0]; 4l = ceil(-log2l(gap)) + 1;

ところで・・・ご質問のコードのy_waiwaiさんご指摘の点のみ変更し、実際に動かしてみても
encoded:000010
とはならず
encoded:000000011
となったのですが、コードの内容や入力データはご質問に提示しておられるとおりでしょうか?
例えばa=0.1, b=0.2, c=0.4, d=0.2だと全部加えても確率は0.9ですが、それはそれでいいのでしょうか?そうしたとしても符号化自体は行えますが、全アルファベットの出現確率の合計が1.0となるような入力を与えるか、合計が1.0となるように各アルファベットの確率を正規化すべきであると思います。そうしないと符号化した際のビット数が長くなるからです。


※:危なっかしい間違い
例えば

scanf("%s",&S[i].s);
printf("%s", &S[i].s);

はコンパイラーが構造体メンバーのアラインメントを(多くの環境で)8と仮定し、sとpの間に7バイトほどのパディング領域が入るためなんとか動いてくれますが

scanf("%s", s); S[i].s = s[0];
printf("%c", S[i].s);

などのように「構造体の中のパディングを期待しない」コードにしたほうがよいと思います。

投稿2018/12/13 14:28

KSwordOfHaste

総合スコア18392

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

mamimumemo700

2018/12/14 02:43

ありがとうございました。とりあえず符号化については解決できました。質問に記載した確率も間違えてましたね...困惑させてしまい申し訳ありません。(a=0.2でした。)
KSwordOfHaste

2018/12/14 04:32

> a=0.2 なるほど納得しました~
guest

0

まず気のついたところで、

double range[asize]

と定義したなら、配列の範囲は、0からasize-1 までです

for(int i=1;i<=asize;i++){

これでは範囲をオーバします

投稿2018/12/13 05:04

y_waiwai

総合スコア87719

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

mamimumemo700

2018/12/13 05:18

見落としていました、range[asize+1]とすべきでした。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問