(57)【特許請求の範囲】
【請求項１】
入力されるデータ系列のうち等価のものをグループ化してグループ毎に当該等価データの出現頻度を計数する方法であって、
入力されるデータ系列を所定数記憶する記憶領域を備えた記憶装置を設けておくとともに、
前記記憶領域を許容計数誤差に等しい個数の区間に分割しておき、
前記記憶領域に前記データ系列を入力しながら等価データをグループ化するとともにグループ毎に当該等価データの出現頻度を計数する計数ステップと、
前記記憶領域に入力する前記データ系列の数が当該記憶領域の最大サイズに達した時、初期段階で計数された計数結果の全部または一部を破棄する破棄ステップと、
各前記グループのうち出現頻度が少ないものを削除する低頻度データ削除ステップと、
前記データ系列を１個の前記区間に相当する個数追加入力して計数結果を更新する更新ステップと、
を有し、
前記計数ステップでは、
各前記グループの計数結果とそのグループの許容計数誤差を組にして前記記憶装置に記憶させておき、
前記破棄ステップでは、
計数結果を破棄するグループの許容計数誤差を、破棄前の当該グループの計数結果を用いて更新することにより、破棄前後に係る計数誤差を前記許容計数誤差の範囲内に収める
ことを特徴とする計数方法。
【請求項２】
前記計数ステップでは、
出現頻度の計数結果が前記許容計数誤差を超えた時点における前記区間の１つ前の区間までの計数結果を、前記グループ毎に、当該グループの許容計数誤差更新値として前記記憶装置に記憶させておき、
前記破棄ステップでは、
計数結果を破棄するグループの許容計数誤差を、前記許容計数誤差更新値で更新する
ことを特徴とする請求項１に記載の計数方法。
【請求項３】
前記破棄ステップにおいて、
計数結果を破棄する前記グループの前記許容計数誤差を、前記許容計数誤差更新値で更新する際に、
当該グループの出現頻度の計数結果を、前記許容計数誤差更新値で減算する
ことを特徴とする請求項２に記載の計数方法。
【請求項４】
前記破棄ステップ、前記低頻度データ削除ステップ、および前記更新ステップを、前記データ系列が終了するまで繰り返し、
前記計数ステップでは、
出現頻度の計数結果が前記許容計数誤差を超えた時点における前記区間の番号を前記記憶装置に記憶させておき、
前記破棄ステップにおいて、
計数結果を破棄する前記グループの前記許容計数誤差を、前記許容計数誤差更新値で更新する際に、
前記計数ステップで前記記憶装置に記憶させた前記区間の番号を、当該グループの計数結果と組にして前記記憶装置に記憶させておく
ことを特徴とする請求項２または請求項３に記載の計数方法。
【請求項５】
前記更新ステップを実行する毎に、
前記破棄ステップで前記記憶装置に記憶させた前記区間の番号を１減算しておき、
その番号が０である場合に限り、前記破棄ステップを実行する
ことを特徴とする請求項４に記載の計数方法。
【請求項６】
前記低頻度データ削除ステップでは、
各前記グループの計数結果と、そのグループの前記許容計数誤差との和を求め、
その和が前記区間の個数以下である場合は、当該グループの計数結果を削除する
ことを特徴とする請求項１ないし請求項５のいずれかに記載の計数方法。
【請求項７】
請求項１ないし請求項６のいずれかに記載の計数方法をコンピュータに実行させることを特徴とする計数プログラム。
【請求項８】
入力されるデータ系列のうち等価のものをグループ化してグループ毎に当該等価データの出現頻度を計数する装置であって、
入力されるデータ系列を所定数記憶する記憶領域を備えた記憶装置と、
前記記憶領域に前記データ系列を入力しながら等価データをグループ化するとともにグループ毎に当該等価データの出現頻度を計数する計数部と、
前記記憶領域に入力する前記データ系列の数が当該記憶領域の最大サイズに達した時、初期段階で計数された計数結果の全部または一部を破棄する破棄部と、
各前記グループのうち出現頻度が少ないものを削除する低頻度データ削除部と、
前記データ系列を１個の前記区間に相当する個数追加入力して計数結果を更新する更新部と、
を備え、
前記記憶領域は許容計数誤差に等しい個数の区間に分割されており、
前記計数部は、
各前記グループの計数結果とそのグループの許容計数誤差を組にして前記記憶装置に記憶させ、
前記破棄部は、
計数結果を破棄するグループの許容計数誤差を、破棄前の当該グループの計数結果を用いて更新することにより、破棄前後に係る計数誤差を前記許容計数誤差の範囲内に収める
ことを特徴とする計数装置。
【請求項９】
前記計数部は、
出現頻度の計数結果が前記許容計数誤差を超えた時点における前記区間の１つ前の区間までの計数結果を、前記グループ毎に、当該グループの許容計数誤差更新値として前記記憶装置に記憶させ、
前記破棄部は、
計数結果を破棄するグループの許容計数誤差を、前記許容計数誤差更新値で更新する
ことを特徴とする請求項８に記載の計数装置。
【請求項１０】
前記破棄部は、
計数結果を破棄する前記グループの前記許容計数誤差を、前記許容計数誤差更新値で更新する際に、
当該グループの出現頻度の計数結果を、前記許容計数誤差更新値で減算する
ことを特徴とする請求項９に記載の計数装置。
【請求項１１】
前記破棄部、前記低頻度データ削除部、および前記更新部の各処理を、前記データ系列が終了するまで繰り返し、
前記計数部は、
出現頻度の計数結果が前記許容計数誤差を超えた時点における前記区間の番号を前記記憶装置に記憶させ、
前記破棄部は、
計数結果を破棄する前記グループの前記許容計数誤差を、前記許容計数誤差更新値で更新する際に、
前記計数部が前記記憶装置に記憶させた前記区間の番号を、当該グループの計数結果と組にして前記記憶装置に記憶させる
ことを特徴とする請求項９または請求項１０に記載の計数装置。
【請求項１２】
前記更新部は、
当該更新部の処理を実行する毎に、前記破棄部が前記記憶装置に記憶させた前記区間の番号を１減算しておき、
前記破棄部は、
その番号が０である場合に限り当該破棄部の処理を実行する
ことを特徴とする請求項１１に記載の計数装置。
【請求項１３】
前記低頻度データ削除部は、
各前記グループの計数結果と、そのグループの前記許容計数誤差との和を求め、
その和が前記区間の個数以下である場合は、当該グループの計数結果を削除する
ことを特徴とする請求項８ないし請求項１２のいずれかに記載の計数装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ系列中の各値の出現頻度を計数する方法に関するものである。
【背景技術】
【０００２】
継続的に流れる大規模な時系列データから、一定以上の頻度で現れる値を抽出する手段は、様々な場面で必要になる。例えば、トラフィック中からパケットロス等のエラーの発生を検出したＩＰアドレスをデータ列とし、ＩＰアドレス毎にエラー検出数を集計し、一定割合以上のエラーの要因となっているＩＰアドレスもしくは経路を得るような場合などがある。
【０００３】
このような場合、最も単純な計数方法としては、ＩＰアドレス毎にカウンタを持ち、エラーの発生毎にカウンタを増加させることが考えられる。しかし、ＩＰアドレス空間は膨大であり、少なくとも繋がっている端末分程度のカウンタが必要となるため、大きなメモリ容量を要する。
また、一定頻度以上のカウンタを探索するために大きなメモリ空間をスキャンする必要がある。
【０００４】
この点に関し、下記非特許文献１では、確率的に、もしくはある一定誤差範囲内に収まるように、頻度が低いデータを随時削除することにより、少ないメモリ量で、一定以上の頻度で出現するデータとその頻度を計数する手法が論じられている。
下記非特許文献１の４．２節”Ｌｏｓｓｙ  Ｃｏｕｎｔｉｎｇ  Ａｌｇｏｒｉｔｈｍ”に記載の手法を簡単に説明すると、以下のようになる。
【０００５】
（１）データ系列をカウントするためのＮ個分の領域を確保し、許容誤差率εの逆数個の容量を有する区間に分割する。区間には、０から始まる番号をつけておく。
【０００６】
（２）上記領域にＮ個分のデータをセットし、１番目のデータ（＝１番目の区間の最初のデータ）から順にカウントを開始する。新たな値が出現する毎に、その時の区間番号Δを、そのデータの値とともに記録していく。
既に記録済みの値が再度出現したときは、その値のカウント数ｆを１増やす。
【０００７】
（３）区間の境界に到達する度に、以下の基準に従い、カウント数ｆの少ないデータを、カウント結果の集計から削除する。
（３．１）ｆ＋Δ≦現在の区間番号となるデータは、集計結果から削除する。
（３．２）上記式を満たさないデータは、そのまま残す。
【０００８】
以上のステップを最後のデータ（Ｎ番目のデータ）まで繰り返すと、一定のカウント数以上のデータは全て保持されることが数学的に保証されており、かつカウント数の少ないデータはステップ（３．１）で削除されて残らない。
したがって、カウント数の多い重要なデータのカウントに必要なメモリ容量のみが必要となり、より少ないメモリ容量で、大量のデータ系列中の各値の出現頻度をカウントすることができる。
【０００９】
【非特許文献１】Ｇｕｒｍｅｅｔ  Ｓｉｎｇｈ  Ｍａｎｋｕ，Ｒａｊｅｅｖ  Ｍｏｔｗａｎｉ，”Ａｐｐｒｏｘｉｍａｔｅ  Ｆｒｅｑｕｅｎｃｙ  Ｃｏｕｎｔｓ  ｏｖｅｒ  Ｄａｔａ  Ｓｔｒｅａｍ”，ＶＬＤＢ  ２００２（２８ｔｈ  ＶＬＤＢ），ｐ．３４６−３５７，Ａｕｇｕｓｔ  ２００２
【発明の開示】
【発明が解決しようとする課題】
【００１０】
トラフィック観測のように、データが継続して終端なく流れ、かつ、実際に通信を行っているＩＰアドレスが頻繁に入れ替わる場合には、観測されるデータ系列の中で頻出するＩＰアドレスが時間とともに変化することが多い。
この場合、頻出するＩＰアドレスの経時変化をできる限りリアルタイムで把握する観点から、頻度が高いデータを、断続することなく継続的に抽出できることが、トラフィック観測の上で望ましい。
【００１１】
しかし、上記非特許文献１に記載の技術では、Ｎ個のデータが処理された時点で一区切りの処理となるため、頻度が高いデータを継続的に抽出したい場合でも、次のＮ個が処理されるまで待たなければならない。
例えば、時系列に得られる１０万個のデータから高頻度データを抽出する処理を、１００個の新たなデータが得られる度に行いたいというような処理を行うことはできず、Ｎ個のデータのカウントが完了するまで待たなければならない。
【００１２】
もし、Ｎ個のデータのカウントが完了するまで待つことなく、上述のようなことを実現しようとすると、複数の処理を所望のデータ数だけずらして平行して行う必要がある。
この場合、各並行処理のために、個別のメモリ領域とデータ処理能力が必要となり、多大なリソースを消費してしまう。
【００１３】
そのため、統計上の出現頻度の低いデータを削除することでメモリ容量を抑えつつ、個別の並行処理を実行することなく、カウントの途中経過を逐次得ることのできる計数方法が望まれていた。
【課題を解決するための手段】
【００１４】
本発明に係る計数方法は、入力されるデータ系列のうち等価のものをグループ化してグループ毎に当該等価データの出現頻度を計数する方法であって、入力されるデータ系列を所定数記憶する記憶領域を備えた記憶装置を設けておくとともに、前記記憶領域を許容計数誤差の逆数個の区間に分割しておき、前記記憶領域に前記データ系列を入力しながら等価データをグループ化するとともにグループ毎に当該等価データの出現頻度を計数する計数ステップと、前記記憶領域に入力する前記データ系列の数が当該記憶領域の最大サイズに達した時、初期段階で計数された計数結果の全部または一部を破棄する破棄ステップと、各前記グループのうち出現頻度が少ないものを削除する低頻度データ削除ステップと、前記データ系列を１個の前記区間に相当する個数追加入力して計数結果を更新する更新ステップと、を有し、前記計数ステップでは、各前記グループの計数結果とそのグループの許容計数誤差を組にして前記記憶装置に記憶させておき、前記破棄ステップでは、計数結果を破棄するグループの許容計数誤差を、破棄前の当該グループの計数結果を用いて更新することにより、破棄前後に係る計数誤差を前記許容計数誤差の範囲内に収めるものである。
【発明の効果】
【００１５】
本発明に係る計数方法によれば、統計上の出現頻度が少ないデータを計数結果から削除するので、計数結果を格納するメモリ容量を抑えることができる。
また、更新ステップにおいて、１区間分のデータを追加入力して計数結果を更新するので、データの計数結果を逐次得ることができる。
また、古い計数結果は重要でないとの観点から、入力するデータ数が最大サイズに達すると、破棄ステップにおいて初期段階で計数された計数結果の全部または一部を削除するので、これによるメモリ容量の節約効果がある。
また、破棄ステップで初期の計数結果を削除する際には、許容計数誤差を破棄前の計数結果に基づき更新するので、古い計数結果を削除しても、一定の誤差範囲内の計数結果が維持され、計数の精度が維持される。
【発明を実施するための最良の形態】
【００１６】
実施の形態１．
図１は、本発明の実施の形態１に係る計数装置１００の機能ブロック図である。
計数装置１００は、データ系列を入力して、系列中に出現する同一データ値の出現頻度をカウントする装置であり、計数部１１０、記憶部１２０、破棄処理部１３０、低頻度データ削除部１４０、更新部１５０を備える。
【００１７】
計数部１１０は、データ系列を受け取り、同一データ値の出現頻度をカウントして、その計数結果を記憶部１２０に格納する。
記憶部１２０は、データ系列の計数結果を格納する記憶装置である。
破棄処理部１３０は、記憶部１２０に格納されている計数結果のうち、初期段階で計数された計数結果を削除するものである。
低頻度データ削除部１４０は、記憶部１２０に格納されている計数結果のうち、出現頻度が低いものを削除する。
更新部１５０は、計数部１１０が一定数のデータ系列のカウントを終えた後、追加分のデータ系列を逐次受け取り、その計数結果を記憶部１２０に格納する。先に記憶部１２０に格納されている計数結果は、追加分の計数結果で更新する。
これら各部の具体的な処理手順は、後述の図３〜図６で説明する。
【００１８】
計数部１１０、破棄処理部１３０、低頻度データ削除部１４０、更新部１５０は、これらの機能を実現する回路デバイスなどのハードウェアで構成することもできるし、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）やマイコンなどの演算装置と、その動作を規定するソフトウェアとで構成することもできる。
これらの構成部のうち全部または一部を、一体的に構成することもできる。
記憶部１２０は、容量の観点から、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）のような比較的大容量の記憶装置で構成することが好ましい。
【００１９】
図２は、計数部１１０がカウントするデータ系列の分割区分を説明するものである。
計数部１１０は、データ系列のカウントを行うに際し、一定サイズの入力バッファを記憶部１２０上に設定し、バッファ中にデータ系列を取り込んだ上でカウントを実行する。ここでは、Ｎ個分のデータをカウントできるだけのバッファサイズを確保するものとして以下の説明を行う。
また、後述する処理手順の便宜上、上述の入力バッファを、複数の区分に分割する。分割基準は以下の通りである。
【００２０】
（１）データ系列のカウントに際し許容される誤差（許容誤差）をεとする。
（２）１区間のデータ数を、（１／ε）個とする。
（３）総区間数は、εＮ個となる。各区間に０から開始する区間番号をつけておく。
【００２１】
最初のＮ個のデータ、即ち「区間番号＝εＮ−１」までのデータは、計数部１１０がカウントを実行する。以後の区間のデータは、更新部１５０がカウントを実行する。
計数部１１０が行うカウント処理は、Ｎ個分のデータをバッファに入力して行うが、以後の更新部１５０が行うカウント処理は、１区間分のデータ毎にカウントを行う。そのため、これ以後のカウント結果は、１区間毎に逐次得られる。
【００２２】
ここで、本実施の形態１に係る計数装置１００との対比のため、上記非特許文献１に記載の従来技術におけるカウント手法について説明しておく。その後、本実施の形態１に係る計数装置１００の動作説明に戻る。
【００２３】
図８は、従来技術における計数結果の格納例を示すものである。ここではテーブル形式の格納例を示した。なお、データ系列は、図２で説明したものと同じように、複数の区間に分割されてカウントされるものとする。
【００２４】
図８のテーブルは、「データ値」列、「出現頻度」列、「計数開始位置」列を有する。
「データ値」列には、データ系列中に出現したデータの値が格納される。
「出現頻度」列には、「データ値」列で示されるデータの出現頻度が格納される。
「計数開始位置」列には、「データ値」列で示されるデータがデータ系列中で最初に出現したときの区間番号が格納される。本列の値は、当該データ値の計数に際しての許容誤差を表す値でもある。これは、１区間のデータ数を（１／ε）個としたことによる。
【００２５】
図８の例では、「データ値＝Ｄ１」のデータは、「区間番号＝０」で最初に出現し、これまでに同値のデータが４１０個カウントされていることが分かる。
同様に、「データ値＝Ｄ２」のデータは、「区間番号＝１０」で最初に出現し、これまでに同値のデータが３２０個カウントされていることが分かる。
【００２６】
非特許文献１に記載の従来技術では、計数結果が下記（式１）を満たすデータは、出現頻度の低い低頻度データとして削除対象となる。これにより、重要度が高いと思われる出現頻度の高いデータのみを残し、メモリ容量を抑えることを図っている。
【００２７】
出現頻度＋統計開始位置≦現在の区間番号  ・・・（式１）
【００２８】
ただし、非特許文献１に記載の従来技術では、入力バッファをＮ個分のデータ相当に設定しているため、Ｎ個分のカウントが完了するまでの間は、計数結果を利用する他のアプリケーション等は待たされることになる。
これは、リアルタイムまたはこれに近い頻度で計数結果を得たいアプリケーションでは都合が悪い。そこで、本実施の形態１に係る計数装置１００では、最初のＮ個分のデータのカウントが完了した後は、計数結果を逐次更新することのできる手法を提案する。
【００２９】
ただし、計数結果を逐次更新すると、計数の母数が変動するため、母数がＮ個であることを前提に設けられている上記（式１）がそのまま使えなくなる。
そこで、本実施の形態１に係る計数装置１００では、許容誤差を都度更新し、上記（式１）を使用できるように配慮する。具体的には、後述の図３〜図６で説明する。
【００３０】
以上、非特許文献１に記載の従来技術におけるカウント手法について説明した。
以下、本実施の形態１に係る計数装置１００の動作説明に戻る。
【００３１】
図３は、計数部１１０が実行するカウント処理を説明するものである。
計数部１１０は、入力されたデータ系列中のデータの出現頻度をカウントする際に、出現頻度が所定の閾値をどの時点で超えたかを、出現頻度と併せて記録部１２０に記録しておく。図３では、上述の閾値の１例として、「εＮ＝５０」と設定して記載した。
ここで設定する閾値は、新たな許容誤差の基準となるものである。具体例は後述の図４〜図６で改めて説明する。
計数部１１０は、「データ値＝Ｄ１」のデータの出現頻度をカウントするに際し、出現頻度が前述の閾値５０を超える毎に、その時点の区間番号を記憶部１２０に記録する。格納形式は、後述の図４で説明する。
【００３２】
図３の例では、「区間番号＝５」で出現頻度が５０を超え、さらに１２区間進んだ「区間番号＝１７」で再び出現頻度が５０を超えている。計数部１１０は、これらの区間番号を後に特定できるよう、記憶部１２０に記録する。
【００３３】
図４は、計数部１１０のカウント結果の記憶部１２０への格納例を示すものである。
図４（ａ）は計数結果テーブル、図４（ｂ）は閾値位置テーブルの構成とデータ例を示している。
【００３４】
計数結果テーブルは、データ系列の計数結果を格納するためのテーブルであり、図８で説明した従来技術におけるテーブル例に加えて、新たに「許容誤差」列を有する。
従来技術では、許容誤差はカウントの進行によらず一定であるが、本実施の形態１では後述する図５の手順により許容誤差が逐次変動するため、本列が新たに設けられている。
【００３５】
図４（ａ）の例では、「許容誤差」列の値は「計数開始位置」列の値と同じになっている。これは、後述する図５の手順を実行するまでは、許容誤差は変動せず、初期状態（＝統計開始位置の値）に等しくなっているためである。
【００３６】
閾値位置テーブルは、図３で説明した、計数結果が閾値（５０）を超えた位置を逐次格納するためのテーブルであり、「データ値」列、「次回更新までの区間距離」列、「許容誤差更新値」列、「初期区間頻度値」列、「データ値通番」列を有する。
【００３７】
「データ値」列には、データ系列中に出現したデータの値が格納される。
「次回更新までの区間距離」列には、計数結果が前回閾値（５０）を超えてから次に閾値（５０）を超えるまでに要した区間数が格納される。
「許容誤差更新値」列には、計数結果が閾値（５０）を超えてから次に閾値（５０）を超える直前の区間までの計数結果が格納される。
なお、最初の区間（区間番号０）あるいは、前記閾値位置テーブルに閾値を越えたことにより各列に値を格納した後、同一区間内でさらに係数結果が閾値を超えた場合、「次回更新までの区間距離」列には「０」を、「許容誤差更新値」列には、現在の区間までの計数結果が格納される。
「初期区間頻度値」列には、計数結果が閾値（５０）を超えた区間内のみでのデータの出現頻度が格納される。
「データ値通番」列には、計数結果が閾値（５０）を超える毎に新たに採番される番号で、同一の「データ値」列の値の記録順を識別するために便宜上設けられたものである。
【００３８】
図４（ｂ）の例では、１行目〜２行目のデータは、図３で説明した例に即したデータ例を示した。
即ち、最初の区間からカウントを開始して６番目の区間で初めて計数結果が５０を超えたため、１行目では「次回更新までの区間距離＝６」とし、その直前の区間までの計数結果は４３であるから、「許容誤差更新値＝４３」とし、閾値位置テーブルに「Ｄ１」に関するデータがなかったので、「初期頻度値＝０」とした。
次に計数結果が５０を超えたのはさらに１２区間進んだ時点であるため、２行目では「次回更新までの区間距離＝１２」とし、その直前の区間までの計数結果は３２であるから、「許容誤差更新値＝３２」とし、また、前回５０を越えた区間（区間番号＝５）のみでデータが出現した頻度は８であるから、「初期頻度値＝８」した。
１行目と２行目は同じ「データ値＝Ｄ１」に対する閾値位置であるため、「データ値通番」列の値は、１から順番に１ずつ増やして採番した。
【００３９】
本実施の形態１における「許容計数誤差」は、εＮがこれに相当する。
また、「許容計数誤差更新値」は、閾値位置テーブルの「許容誤差更新値」列の値がこれに相当する。
【００４０】
図５は、破棄処理部１３０の処理手順を説明するものである。以下、図５のステップ順に説明する。なお、図５において、色付きの両端矢印は、各ステップにおける計数対象範囲を示すものである。
【００４１】
（１）Ｎ個をカウント
計数部１１０は、最初のＮ個分のデータをカウントし、計数結果を記憶部１２０に格納する。ここでは、図３〜図４で説明したものと同様の計数結果が得られたものとする。
【００４２】
（２）初期の計数結果を削除
破棄処理部１３０は、以下の処理を実行する。
（２．１）破棄処理部１３０は、区間０〜４におけるデータＤ１の計数結果を全て削除する。
（２．２）計数結果の削除によりデータＤ１の計数結果に同数の誤差が生じるので、図４（ｂ）で説明した閾値位置テーブルを用いて、データＤ１に関する許容誤差の値を同数で更新する。更新の手順は、後述の図６で説明する。
【００４３】
（３）区間を１ずらす
計数対象範囲を１区間分進め、以後のデータのカウントは、更新部１５０が担当する。
ここでは、「区間番号＝εＮ」の区間のデータがカウントされる。更新部１５０は、以後同様に、１区間ずつ区間を先に進めながら、計数結果を記憶部１２０に逐次格納する。他のアプリケーションは、１区間毎に逐次格納される計数結果を取得することができる。
【００４４】
（４）初期の計数結果を削除
計数対象区間の左端が、データＤ１の計数結果が５０を超えた区間（区間番号＝５）に達すると、破棄処理部１３０は、以下の処理を実行する。
（４．１）破棄処理部１３０は、区間５〜１６におけるデータＤ１の計数結果を全て削除する。
（４．２）計数結果の削除によりデータＤ１の計数結果に同数の誤差が生じるので、図４（ｂ）で説明した閾値位置テーブルを用いて、データＤ１に関する許容誤差の値を同数で更新する。更新の手順は、後述の図６で説明する。
【００４５】
以下同様に、破棄処理部１３０は、データＤ１の計数結果が５０を超えた区間に計数対象区間の左端が達する毎に、古い計数結果を破棄するとともに、データＤ１に関する許容誤差の値を同数で更新する。
【００４６】
図６は、閾値位置テーブルに格納されているデータの使用手順を説明するものである。データ値は、図４で説明したものと同じものを用いた。
図６（１）は、破棄処理部１３０が、図５（２）の破棄処理を行う前の状態である。
破棄処理部１３０は、区間の境界毎に、計数結果テーブルの「計数開始位置」列の値を確認し、同列の値が「０」となっているデータを探す。ここでは、データＤ１は区間番号０から出現しているため、データＤ１の同列の値が「０」となっている。
【００４７】
次に、破棄処理部１３０は、閾値位置テーブルのデータのうち、「データ値＝Ｄ１」のものを検索し、さらに「データ値通番」が最も小さいものを取得する。ここでは、図６（１）（ｂ）の１行目のデータが相当する。もし、そのようなデータが見つからなければ、「データ値＝Ｄ１」の計数結果が許容誤差「εＮ＝５０」未満になることを示すので、計数結果テーブルから「Ｄ１」の計数結果を削除する。
【００４８】
次に、破棄処理部１３０は、図６（１）（ｂ）の１行目のデータを用いて、計数結果テーブルのデータＤ１に関するデータを更新する。具体的には、以下のような処理を行う。
【００４９】
（１）破棄処理部１３０は、計数結果テーブルの「出現頻度」列の値から、閾値位置テーブルの「許容誤差更新値」列の値と「初期区間頻度値」列の和の数を減算する。これは、区間番号５以前の計数結果を削除するものであり、図５のステップ（２）の処理に相当する。
【００５０】
（２）破棄処理部１３０は、計数結果テーブルの「許容誤差」列の値を、閾値位置テーブルの「許容誤差更新値」列の値で更新する。ただし、「次回更新までの区間距離」列の値が０の場合は、「許容誤差」列の値を０で更新する。これは、区間番号５以前の計数結果を削除したことに伴う補填処理であり、計数結果に削除分の誤差が生じていることに鑑みたものである。
【００５１】
（３）破棄処理部１３０は、計数結果テーブルの「計数開始位置」列の値を、閾値位置テーブルの「次回更新までの区間距離」列の値から１減算した値で更新する。ただし、「次回更新までの区間距離」列の値が０の場合は、「係数開始位置」列の値を０のままにする（つまり、更新しない）。これは、図５のステップ（４）に備えるための処理である。
以後、更新部１５０は、計数対象区間が１進む毎に、計数結果テーブルの全ての「計数開始位置」列の値を１ずつ減算し、同列の値が０になったデータに対し、その時点で上述の（１）〜（２）と同様の破棄処理が実行される。
例えばデータＤ１における次回の破棄処理の実行は、「計数開始位置」列の値が０になる時点であるから、５区間先、即ち図５のステップ（４）の時点である。
【００５２】
図６（２）は、破棄処理部１３０が以上の処理を行った後の各テーブルの状態である。
計数結果テーブルの１行目のデータが更新されて古い計数結果が削除されるとともに、「許容誤差」列の値が更新され、さらに閾値位置テーブルの１行目のデータが削除されていることが分かる。
【００５３】
以後、破棄処理部１３０は、区間の境界に達する毎に同様の手順を繰り返す。これにより、計数結果テーブルのデータは、古い計数結果が削除されて新しいデータのみが保持されるとともに、「許容誤差」列の値は、破棄した分のデータに相当する値で更新されるため、メモリ容量を節約するとともに、計数結果の精度も一定レベルに維持される。
【００５４】
なお、古い計数結果を削除しているのは、次々に最新のデータが計数装置１００に到達するようなデータ系列を計数対象とする場合、昔のデータであればあるほど、現在の状態を統計的に把握するためには不要となることに鑑みたものである。
図６に即して説明すると、「計数開始位置」列の値が０となっているようなデータは、計数のごく初期段階で出現したデータであり、これを一定数削除しても、現在の同データの状態を統計的に知る上では、あまり影響がないものと考えられるからである。
【００５５】
なお、破棄処理部１３０が図５〜図６で説明した破棄処理を行うことに加えて、非特許文献１に記載の従来技術と同様に、低頻度データ削除部１４０は、上記（式１）を用いて出現頻度の少ないデータを計数結果テーブルから削除する。
これら２重の削除処理により、消費するメモリ容量を効果的に抑えることができ、かつ更新部１５０が逐次データ更新を行うので、１区間分のデータ更新に要する時間間隔で計数結果を逐次得ることができる。
【００５６】
以上をまとめると、本実施の形態１に係る計数装置１００の動作手順は、概ね以下の通りである。
【００５７】
（１）計数部１１０は、最初のＮ個分のデータをバッファ中にセットした上で計数し、計数結果を計数結果テーブルに格納するとともに、閾値位置テーブルに逐次値をセットしていく。
【００５８】
（２）破棄処理部１３０は、計数部１１０がＮ個分のデータをカウントした後、区間の境界毎に、古いデータの破棄を行うか否かを、「統計開始位置」列の値が０となっているか否かで判定し、図５で説明したような破棄処理を行う。
【００５９】
（３）低頻度データ削除部１４０は、１区間毎に上記（式１）の条件を満たす低頻度データを削除する。
（４）更新部１５０は、計数部１１０がＮ個分のデータをカウントした後、１区間毎に追加データのカウント結果を計数結果テーブルおよび閾値位置テーブルに格納する。
【００６０】
本実施の形態１では、計数結果等の格納形式として、図４のようなテーブル形式を例として説明したが、これに限られるものではなく、例えばリスト形式など、任意の格納形式を用いることができる。
【００６１】
以上のように、本実施の形態１に係る計数装置１００では、計数部１１０は、出現頻度が閾値（εＮ＝５０）を超えた時点の区間番号を閾値位置テーブルに記録しておき、破棄処理部１３０は、Ｎ個のカウントが完了した以後は、区間の境界毎に閾値位置テーブルを参照し、所定条件の下で初期段階の計数結果を削除する。
これにより、計数結果を格納するためのメモリ容量を節約することができる。
また、初期段階の計数結果は最新の状態を統計的に知る観点からはあまり重要でないため、このような削除処理を行っても、計数結果の精度は一定レベルに維持される。
【００６２】
また、破棄処理部１３０が初期段階の計数結果を削除する際には、閾値位置テーブルの「許容誤差更新値」、即ち計数結果が設定した閾値（許容誤差）を超える直前までの計数結果を用いて、計数結果テーブルの「許容誤差」列の値を更新するので、古い計数結果を削除しても、一定の誤差範囲内の計数結果が維持され、計数結果の精度が維持される。
【００６３】
また、更新部１５０は、計数部１１０がＮ個分のデータをカウントした後は、１区間分のデータのカウントを行う毎に計数結果を計数結果テーブルに逐次格納するので、他のアプリケーションは、計数結果をリアルタイムまたはこれに近い時間間隔で得ることができる。
これにより、計数結果を逐次利用したいアプリケーションが、計数の完了まで処理を待たされることがなくなり、処理の迅速に資する。
【００６４】
また、低頻度データ削除部１４０は、統計上の出現頻度が少ないデータを計数結果から削除するので、計数結果を格納するメモリ容量を抑えることができる。
【００６５】
実施の形態２．
図７は、本発明の実施の形態２に係るパケット収集装置２００の機能ブロック図である。パケット収集装置２００は、ネットワーク上を流れる通信パケットを収集し、パケット中の所定の情報、例えば送受信アドレスをカウントして、その結果を記憶するための装置である。
パケット収集装置２００は、実施の形態１の図１で説明した計数装置１００の構成に加え、新たにパケット収集部２１０ａ、２１０ｂを備える。図７では、計数部１１０と更新部１５０にそれぞれパケット収集部２１０を接続したが、これらは共通化してよい。
【００６６】
パケット収集部２１０ａ、２１０ｂは、ネットワークに接続され、通信パケットを収集して、計数対象の情報、例えばパケットの送受信アドレスなどを抽出し、それぞれ計数部１１０、更新部１５０に出力する。
最初のＮ個分の送受信アドレスはパケット収集部２１０ａが収集し、以後はパケット収集部２１０ｂが収集する。
パケットを収集した以後の処理は、実施の形態１と同様であるため、説明を省略する。
【００６７】
ネットワークの通信パケットの送受信アドレスは、膨大な数が存在するため、これを計数対象とする場合、メモリ容量を多く必要とする。
そこで、実施の形態１で説明したような計数装置１００の構成を用いて、送受信アドレスを計数することにより、少ないメモリ容量で、効率的に送受信アドレスの計数を行うことができる。
【００６８】
実施の形態３．
以上の実施の形態１〜２では、データ系列中に出現する同一の値、例えば同一の送受信アドレスをカウントする手法について説明したが、カウントする対象は、必ずしも同一のデータに限る必要はなく、カウントの目的に合致するのであれば、「等価」な値の個数をカウントするようにしてもよい。
【００６９】
例えば、実施の形態２におけるパケット収集装置２００において、同一のネットワークアドレスに関して送受信されるパケットをカウントしたいような場合は、計数部１１０がカウントを行う際に、サブネットマスクを掛け合わせて同値となるアドレスは、同じ値としてカウントするようにしてもよい。
【図面の簡単な説明】
【００７０】
【図１】実施の形態１に係る計数装置１００の機能ブロック図である。
【図２】計数部１１０がカウントするデータ系列の分割区分を説明するものである。
【図３】計数部１１０が実行するカウント処理を説明するものである。
【図４】計数部１１０のカウント結果の記憶部１２０への格納例を示すものである。
【図５】破棄処理部１３０の処理手順を説明するものである。
【図６】閾値位置テーブルに格納されているデータの使用手順である。
【図７】実施の形態２に係るパケット収集装置２００の機能ブロック図である。
【図８】従来技術における計数結果の格納例を示すものである。
【符号の説明】
【００７１】
１００  計数装置、１１０  計数部、１２０  記憶部、１３０  破棄処理部、１４０  低頻度データ削除部、１５０  更新部、２００  パケット収集装置、２１０ａ〜２１０ｂ  パケット収集部。
【図１】
0004420114.tif 000002
【図２】
0004420114.tif 000003
【図３】
0004420114.tif 000004
【図４】
0004420114.tif 000005
【図５】
0004420114.tif 000006
【図６】
0004420114.tif 000007
【図７】
0004420114.tif 000008
【図８】
0004420114.tif 000009