コード中の文字の頻度分析 in C++ DouKaku?

コード中の文字の頻度分析

プログラムコード中の文字の頻度は言語によって相当にばらつきがあると思います。ある言語はピリオドが頻出するとか、別の言語はカッコの頻出頻度が高い、とか。そこで、

文字の頻度解析をするプログラムを作成し、
適当なプログラムに対して実行し、結果を出力して、そのような頻度になっている理由を教えてください。

(その言語で書かれた「典型的な」プログラムコード、といえるようなものがあると良いのですが・・）

簡単すぎるという方は、複数文字にしてみたり単語の頻度にしてみてください。

参考；Wikipedia 頻度分析

http://ja.wikipedia.org/wiki/%E9%A0%BB%E5%BA%A6%E5%88%86%E6%9E%90

出題者です。こちらで用意していた回答は awk を使ったものでした。一応解説すると、組み込み変数FSを空にし、１行単位の文字毎に連想配列に格納しています。

# １文字版
BEGIN { FS="" }
{ for (i=1; i<=NF; i++) ht[$i]++}
END { for (c in ht) print ht[c],c }

# ３文字版
BEGIN { FS="" }
{ for (i=1; i<=NF-2; i++) { ht[$i$(i+1)$(i+2)]++}}
END { for (c in ht) print ht[c],c }

post comment

Posted feedbacks - C++

アプリケーションのソースじゃなくて、
cygwin g++ の C++ ヘッダファイル群(全218個)を分析してみました。

  1:0x20  548301 (0.20355)
  2:   e  189982 (0.07053)
  3:   t  166220 (0.06171)
  4:   _  144935 (0.05380)
  5:   r  117461 (0.04361)
  6:   a  113395 (0.04210)
  7:   i  111175 (0.04127)
  8:   s  103785 (0.03853)
  9:   o   99888 (0.03708)
 10:   n   98172 (0.03644)
 11: 0xa   81784 (0.03036)
 12:   l   62672 (0.02327)
 13:   c   61995 (0.02301)
 14:   p   55391 (0.02056)
 15:   u   44881 (0.01666)
<以下省略>

スペースや改行は置いておくとして。
上位10位以内で、int や iterator が
(もうちょっと広げるとconst_iteratorも)
作れるのが興味深いところかと。

"_" が多いのはヘビ記法とローカル用識別子の影響かな。

括弧の類を見てみると、
"(", ")" はそれぞれ24,25位(0.9%),
templateにも使用する"<", ">" は それぞれ 38,33位 (0.4～0.5%),
"{", "}" に至っては 44,45位(0.26%) となっていました。

意外に括弧使ってないのね。。

ちなみに最下位は "$" (8件) でしたが、コメントの中かな...

#include <map>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <functional>
#include <fstream>
#include <stdexcept>
#include <numeric>
#include <cctype>
#include <iterator>
#include <utility>

typedef std::map<char, int> freq_t;
typedef std::vector< std::pair<char, int> > freqv_t;

struct calc_freq
: std::unary_function< freq_t, char* >
{
  freq_t operator()(char* filename) const
  {
    std::ifstream ifs(filename);
    if ( !ifs )
      throw std::runtime_error(std::string("failed to open : ")+filename);

    freq_t f;
    while ( ifs )
    {
      int c = ifs.get();
      if (c >= 0) ++f[c];
    }

    return f;
  }
};

struct merge_freq
: std::binary_function<freq_t, freq_t, freq_t>
{
  freq_t& operator()(freq_t& lhs, const freq_t& rhs) const
  {
    for ( freq_t::const_iterator it = rhs.begin();
        it != rhs.end(); ++it )
      lhs[it->first] += it->second;

    return lhs;
  }
};

struct count_total
: public std::binary_function< int, int, freq_t::value_type >
{
  int& operator()(int& total, const freq_t::value_type& v) const
  {
    return total += v.second;
  }
};

template<class C>
struct freq_print_each
: std::unary_function< void, typename C::value_type >
{
  std::size_t total_;
  mutable std::size_t i_;
  freq_print_each<C>(std::size_t total) : total_(total), i_(0) {}

  void operator()(const typename C::value_type& v) const
  {
    std::cout << std::setw(3) << ++i_ << ":" << std::setw(4);
    if ( !isprint(v.first) || isspace(v.first) )
      std::cout << std::showbase << std::hex
                 << static_cast<int>(v.first) << std::dec;
    else
      std::cout << v.first;

    std::cout << std::setw(8)
      << v.second << " ("
      << std::setprecision(5) << std::fixed
      << static_cast<double>(v.second)/total_
      << ")\n";
  }
};

template <class C>
struct sorter
: std::binary_function<bool, typename C::value_type, typename C::value_type>
{
  typedef typename C::value_type value_type;
  bool operator()(const value_type& lhs, const value_type& rhs) const
  {
    return lhs.second > rhs.second;
  }
};

int main(int c, char** v)
{
  try {
    std::vector< freq_t > freqs;
    std::transform(v+1, v+c, std::back_inserter(freqs), calc_freq());

    const freq_t all_freq = std::accumulate(freqs.begin(), freqs.end(), freq_t(), merge_freq());
    const int total = std::accumulate(all_freq.begin(), all_freq.end(), 0, count_total());

    freqv_t all_freq2;
    all_freq2.reserve(all_freq.size());

    std::copy(all_freq.begin(), all_freq.end(), std::back_inserter(all_freq2));
    std::sort(all_freq2.begin(), all_freq2.end(), sorter<freqv_t>());

    std::for_each(all_freq2.begin(), all_freq2.end(), freq_print_each<freqv_t>(total));
  }
  catch (const std::exception& e) {
    std::cerr << e.what() << std::endl;
  }

  return 0;
}

自分自身を解析した結果(上位10件)。 ' ':305 /'e':104 /'t':93 /0ah:76 /'r':72 /'s':61 /'i':54 /':':52 /'a':51 /'o':50

#include <iostream>
#include <iomanip>
#include <fstream>
#include <map>
#include <list>
#include <algorithm>
#include <iterator>
#include <cctype>

typedef std::map<char, int> freq_type;

class Loader
{
public:
    explicit Loader(freq_type& freq) : freq_(freq) {}

    void operator () (const char* filename)
    {
        std::ifstream src(filename);
        char c;
        while(src.get(c))
        {
            ++freq_[c];
        }
    }

private:
    freq_type& freq_;
};

bool comp(const freq_type::value_type& lhs, const freq_type::value_type& rhs)
{
    return (lhs.second != rhs.second) ? (lhs.second > rhs.second) : (lhs.first < rhs.first);
}

std::ostream& operator << (std::ostream& out, const freq_type::value_type& value)
{
    if(std::isprint(value.first))
    {
        out << "'" << value.first << "'";
    }
    else
    {
        int fill = out.fill('0');
        out << std::hex << std::setw(2) << (static_cast<unsigned int>(value.first) & 0xffu) << 'h' << std::dec;
        out.fill(fill);
    }
    return out << ":" << value.second;
}

int main(int argc, char* argv[])
{
    // 読み込み
    freq_type freq;
    std::for_each(argv + 1, argv + argc, Loader(freq));

    // 出現頻度で並べ替え
    std::list<freq_type::value_type> f(freq.begin(), freq.end());
    f.sort(comp);

    // 出力

//  エラーになる理由がわからず…(;_;)マダマダ、ミジュクモノ…
//  std::copy(f.begin(), f.end(), std::ostream_iterator<freq_type::value_type>(std::cout, "\n"));

    for(std::list<freq_type::value_type>::const_iterator i = f.begin(); i != f.end(); ++i)
    {
        std::cout << *i << std::endl;
    }

    return 0;
}

文字数カウントは既に投稿されていたので、半角スペース・タブ・改行で区切って似非単語分割してみました。
typedefが少し汚いです・・・。
分割はboost::tokenizerを使ってますが、ここをmecab等に置き換えればもう少し遊べるかもしれません。

自分自身を分析：
} :: 8
#include :: 7
typedef :: 7
i :: 6
// :: 5
= :: 4
<< :: 4
!= :: 4
i++){ :: 3
> :: 3
return :: 2
FreqmapCIter& :: 2
count(std::string :: 2
Freqmap* :: 2
str, :: 2
{ :: 2
" :: 2
int :: 2
void :: 2
operator()(const :: 1

// frequency analysis

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <boost/tokenizer.hpp>


typedef std::map< std::string, int > Freqmap;
typedef Freqmap::value_type FreqmapType; 
typedef Freqmap::const_iterator FreqmapCIter;
typedef std::vector< FreqmapCIter > FreqmapCIterVec;
typedef FreqmapCIterVec::const_iterator FreqmapCIterVecCIter;


struct FreqmapCIterVecSort{
    bool operator()(const FreqmapCIter& lhs, const FreqmapCIter& rhs){
    return (lhs->second > rhs->second);// ordered by desc
    }
};


void count(std::string str, Freqmap* vec);


int main(int argc, char* argv[])
{
    // open
    std::ifstream ifs(argv[1]);

    // count
    Freqmap map;
    std::string strbuf;
    while(ifs && getline(ifs, strbuf)){
    count(strbuf, &map);
    }
    ifs.close();


    // sort
    FreqmapCIterVec mapvec;
    for(FreqmapCIter i = map.begin(); i != map.end(); i++){
    mapvec.push_back(i);
    }
    std::sort(mapvec.begin(), mapvec.end(), FreqmapCIterVecSort());

    // output
    for(FreqmapCIterVecCIter i = mapvec.begin(); i != mapvec.end(); i++){
    std::cout << (*i)->first << " :: " << (*i)->second << std::endl;
    }

    return 0;
}



typedef boost::char_separator<char> Sep;
typedef boost::tokenizer<Sep> Tok;


void count(std::string str, Freqmap* map)
{
    Sep sep(" \t\n");
    Tok tok(str, sep);
    Freqmap::iterator mapiter;

    for(Tok::iterator i = tok.begin(); i != tok.end(); i++){
    mapiter = map->find(*i);
    if(mapiter != map->end()){
        mapiter->second++;
    }else{
        map->insert(std::pair<std::string, int>(*i, 1));
    }
    }
}

DouKaku?

コード中の文字の頻度分析

Posted feedbacks - C++

Index

Feed

Other

Link

Pathtraq