2010年05月21日

やっと分かったフーリエ変換

私は大学で力学関係を専攻して主に振動を扱っていたにもかかわらず、何故かフーリエ変換を学ばなかったので、今更ですが自分で勉強してみました。

フーリエ変換やその高速化したアルゴリズムのFFTは有名なので、どんなものかは知っている人も多いと思います。簡単に言うと、ある振動に対してフーリエ変換を適用すると、周波数成分を得ることができます。

今回はPC上で信号を扱う場合に使う、離散フーリエ変換に限定します。

n個の数列x0 , … , xn-1に対する離散フーリエ変換の式は次のようになります。

離散フーリエ変換の式

ここでπは円周率、eは自然対数の底(ネイピア数)、iは虚数単位を表し、kはΣの添え字、jは結果の数列fの添え字を表します。この計算を言葉で説明すると、x0からxn-1全てにexp(-2πi/n*jk)を掛けて足し合わせるという計算を、jを変化させながらn回行うという計算になります。結果のfjはn個の複素数の数列になります。入力値のxnの数列も複素数です。(ただし通常は入力値は実数なので虚部が全て0の数列)

フーリエ変換がよく分からないのは、なぜ複素数が出てきたり、この計算で周波数が求まるのか、という点だと思います。これを理解するには、まずは複素数の幾何学的な性質を知っておく必要があります。

ガウス平面

複素数の実部を横軸、虚部を縦軸とした座標系をガウス平面といいます。ガウス平面内では、複素数の演算は座標変換に相当し、特に絶対値が1の複素数を掛けるのは原点中心の回転になります。例えば、1にiを掛けて行くと、1→i→-1→-i→1と変化しますが、これはガウス平面内では90度の回転になります。

gaussian-plane

ここでは1という分かりやすい値を例にしましたが、どんな値でも成り立ちます。

任意の複素数 x+iy と絶対値が1の複素数 cosθ+isinθ を掛け合わせた (x+iy)*(cosθ+isinθ) という式を展開してみると、見慣れた回転の公式に帰着します。このことからも、複素数の掛け算=回転が確認できます。

ところで、exp(i*θ)というよく分からない方程式は、ガウス平面内で半径1の円になります。eのi乗という常人には想像もできない不思議な計算ですが、何故かそうなります。θは角度を表していて、単位はラジアンです。θが0から2πまで変化すると、円に沿って一周することになります。また、オイラーの公式という次のような等式があります。

オイラーの公式

幾何学な得意な方ならば、三角関数の表現の方がイメージしやすいと思います。なぜこの式が成り立つのかは、ここでは証明しません。

この式や、少し変形した e+1=0 の意味まで考えると、何かとてつもない真理に触れたような気分になります。我々は恐ろしい魔物の影を見てπと名付け、鳴き声を聞いてeと呼んでいただけなのかもしれません。

exp(i*θ)は絶対値1の複素数で、これを掛けることはガウス平面内でθラジアンの回転をするのに等しくなります。

さて、フーリエ変換の式をもう一度見てみると、exp(-2πi/n*jk) の部分は θ=-2π/n*jk と置くと exp(i*θ) になり、回転を表していることが分かります。もう少し形を変えると θ=-2π*(k/n)*j で、kが0からn-1まで変化する(k/nが0〜1に変化する)間にj=1のとき1回転、j=2なら2回転することが分かります。

ようするに、離散フーリエ変換というのは、入力値をグルグル回転させながら足し合わせる計算ということです。出力値は、0回転からn-1回転まで回転速度を変化させた数列になります。

何故これで周波数に分解できるのかという話は次回

2010年05月21日 【プログラミング】 | コメント(0) |
2010年05月04日

Twitter botのライブラリをtwythonからtweepyへ変更

以前作成したTwitterでニュースを配信するbotは、Twitterへのアクセスにtwythonというライブラリを使用していましたが、tweepyという別のライブラリに変更しました。

Twitter APIではユーザ認証にBASIC認証とOAuthという2種類の認証方法があるのですが、BASIC認証は6月末に廃止予定で、今後はOAuthだけになるようです。

OAuthはTwitterの中の人が発案した認証方式で、外部のWebサービス等を経由してTwitterにアクセスする際に、自分のパスワードを教えることなくアカウントへのアクセス権を与えることができます。

現在twythonはBASIC認証にしか対応しておらず、作者も忙しくて作業が進まないようなので、既にOAuthに対応しているtweepyに乗り換えることにしました。(2010/11/11追記)twythonもOAuth対応になっていました。

twythonとtweepyで大きく違うのは、Twitterから情報を取得する関数が返すオブジェクトがtwythonは辞書的なインターフェースなのに対して、tweepyでは属性になっている点です。例えばtwythonでダイレクトメッセージの送信者名を取得する場合は sender = message[“sender_screen_name”] としますが、tweepyでは sender = message.sender_screen_name とします。

また、twythonではエラーの種類ごとに例外が定義されていましたが、tweepyではエラーの種類に関わらずTweepErrorという例外が発生します。この点はちょっと不便です。

OAuthの登録

OAuthを使うには、先にいくつか登録が必要になります。

まずTwitterのアプリケーション登録ページからOAuthを使うアプリケーションを登録します。日本語のページはおかしくて意味が分からないので、言語設定を英語にしておいた方がいいかもしれません。登録すると得られるConsumer keyとConsumer secretがTwitterへのアクセスに必要になります。

次に、OAuthは本来は3者間での認証方式なので、先ほど登録したアプリケーションにツイートするためのアカウントへのアクセス権を与えます。Twitterクライアントであれば、この処理も組み込む必要がありますが、botは自分のアカウントを登録するだけなので、tweepy-examplesにあるgetaccesstoken.pyを使いました。ここで得られるKeyとSecretが、ユーザのIDとパスワード代わりになります。

後はこれらを使って、OAuthHandlerを初期化するだけです。

auth = tweepy.OAuthHandler(consumer_key, consumer_secret)
auth.set_access_token(access_key, access_secret)
api = tweepy.API(auth)
api.update_status('Hello, world!')

ちなみに、認証が済んでいるapiオブジェクトをGAEのmemcacheに保存できないか試してみましたが、駄目でした。Twitterのサーバは重くて、cronでチェックするたびに認証処理をすると結構な時間を取られるので、使いまわせればかなり節約できそうなんですけどね。

IDLEで文字化け

ライブラリの使い方を学習する際にPythonのインタラクティブシェルが便利なのですが、IDLE上からtweepyを使って日本語のツイートをするとものの見事に文字化けしまくります。

これはtweepyに問題があるのではなく、IDLEの問題でした。通常のシェルや、PyScripterの内蔵シェルでは日本語でも問題ありませんでした。

tweepy以外でもIDLEは日本語の入出力が怪しいので、気をつけないといけませんね。

2010年05月04日 【プログラミング】 | コメント(2) |
2010年04月22日

HTTPステータスコードの定義がいつの間にか変わっていた

WebサーバがHTTPリクエストに対するレスポンスに、レスポンスの意味を表現するステータスコードがありますが、いつの間にか定義が変わっているものがありました。

定義が変わったのは302で、従来は「Moved Temporarily」(一時的な移動)だったのですが、今では「Found」というよく分からない意味に変わっていました。

これは、掲示板やWiki等に投稿した後に、投稿用のURLから表示用のURLに移動させる目的で302を乱用していたのが原因で、そのための新しいコードの定義と共に302は意味が変えられました。

これに関連して新しく定義されたコードは303と307です。

303は「See Other」で、別のURLをGETメソッドで取得すると決められています。掲示板などの投稿用アドレスから転送する場合はこのコードを使います。

307は「Temporary Redirect」で、元々の302がこちらに変更になった感じです。303とは違い、リクエストメソッドは変更せずに別のアドレスを参照すると定義されています。例えばPOSTメソッドでアクセスしていたら、転送先のアドレスもPOSTメソッドでアクセスします。

302にはリクエストメソッドに関する決まりが明記されていなかったと思うので、新しいコードで明文化されたのは互換性の点でも良いことだと思います。(301はどうなっているんだろう?)

RFCまでは見ていないので302の新しい定義の意味はよく分かりませんが、互換性のために残されているだけで、新しいアプリケーションでは積極的に使うコードではないということでしょうか?

Webアプリケーションが返すステータスコードなんて200と302くらいしか使わないので長年確認もしていませんでしたが、たまにはチェックしないと駄目ですね。

タグ:Webサービス
2010年04月22日 【プログラミング】 | コメント(0) |
2010年04月16日

Silverlight4が正式リリースされました

SilverlightのVersion4が遂に正式にリリースされました。開発者用のツールやドキュメントはまだ英語版しかリリースされていませんが、私は英語でも構わないので早速インストールしてみました。

Silverlight4の開発に関する点を簡単にまとめておきます。

  • 開発にはVisual Studio 2010かVisual Web Developer 2010 Expressが必要(2008不可)
  • XAML parserがアップデートされ一部互換性が無くなりました(ランタイムにSL3用XAML parserも入っているのでSL3アプリケーションの変更は不要)
  • Silverlight ToolsのXAMLデザイナがコントロールのドラッグ&ドロップやマウスでのリサイズに対応
  • C# 4.0になった…らしいがドキュメントに記述が見つからず(明記されている文書を探し中)

個人的にVS2008が使えなくなったのが痛いです。2010ではStandard Editionが廃止になり、無料のExpressの次がいきなりProfessionalになってしまったので、ちょっと手が出しにくくなりました。とりあえず、しばらくはVWDで様子を見ようと思います。

XAMLデザイナの強化は良い感じですね。Windowsフォームアプリケーションの感覚でSilverlightもデザインできるようになりました。

新規コントロールではViewBox、WebBrowser、RichTextBoxあたりが良い感じです。ViewBoxは子要素をViewBoxにフィットするように自動的に拡大縮小するコントロールです。最上位のコントロールをViewBoxにすればフルスクリーン対応とかも簡単になりそうです。RichTextBoxはその名の通りのリッチエディットコントロールです。ブログエディタなどリッチエディットが欲しい場面は結構あるので色々と使えそうです。WebBrowserはOut-of-Browser専用のコントロールで、Silverlightアプリケーション内でHTMLを表示できます。

他には、ブラウザ外からのファイルのドラッグ&ドロップ対応、各種コントロールがマウスホイールに対応、右クリックをアプリケーションで利用可能、印刷対応、OOBアプリケーションの権限を昇格させてセキュリティの壁を取っ払える…等があります。

何故かSilverlightでは使えなかったHashSetも使えるようになりました。もうDictionaryのKeyだけ使うなんて実装とはオサラバです。

タグ:Silverlight
2010年04月16日 【プログラミング】 | コメント(0) |
2010年03月19日

GAEで不定期のイベント処理をするならTask Queue

決まった時刻や間隔で定期的に何か処理をしたい場合はCronを使用しますが、直前になるまで時刻が分からなかったり、突発的に発生するイベントの処理にはTask Queueを使います。

Task Queueはプログラム上から実行する時間を指定して登録できるCronに似たシステムです。CronがGETメソッドでパラメータ無しで呼び出されるのに対して、Task Queueは基本的にPOSTメソッドで呼び出され、パラメータも渡すことができます。

ちなみに、Task Queueはまだ実験的なシステムで現在はgoogle.appengine.api.labs.taskqueueというパスになっていますが、正式サービスに昇格する際にgoogle.appengine.api.taskqueueに変わる予定なので注意してください。

呼び出し元がユーザではなくGAEのシステムというだけで、それ以外は普通のCGIと同じなので基本的なことは説明するまでもないと思います。

タスク名とTombstonedTaskError

現在の仕様では、Task Queueはキューにタスクを追加する機能しかないので、あるタスクが既に登録されているか等の問い合わせができません。

タスクには名前を付けることができ、既にキュー内に同じ名前のタスクがある場合は、2つ目を登録しようとするとTaskAlreadyExistsErrorの例外が発生します。これで同じタスクの重複登録を防ぐことができます。

しかし、名前付きのタスクは無事に実行が完了してもしばらくの間は墓地に保管され、同名のタスクを再度登録しようとするとTombstonedTaskErrorという例外が発生してしまいます。この保管期間は明示されていませんが、24時間以上のようです。

TombstonedTaskErrorを避けつつ重複登録も防ぎたい場合は、タスク名に日付けと時刻のsufixを付けると良いようです。sufixの時間の粒度を調節することで、重複防止の期間もコントロールすることができます。例えば1日1回実行するタスクならば日付けまでで時刻は付けず、1時間に1回ならば分以下を省略、15分に1回ならば15分単位に切り捨てた時刻のようにします。

重複登録を防ぐ必要がなければ、タスク名は指定しない方がいいでしょう。

自動リトライ

cronもTask Queueも、例外が発生して処理が中断した場合は自動的に再実行されます。自分のコードに問題がなくてもDatastoreのアクセス等でエラーが発生することがありますが、そのような場合でも自動的にリトライしてくれます。エラー時に自前のリトライ処理をすると30秒制限が心配になりますが、自動リトライならば新たなセッションで開始されるので心配ありません。

GAE内のサービスだけを利用しているならばいくらリトライされても自己責任で済むのでいいのですが、外部のWebサービスにアクセスしている場合は自動リトライによってDoS攻撃まがいのことをしてしまうことがあるので注意が必要です。私も何度かtwitterやbit.lyに対して大量のアクセスをしてしまった経験があります。

自動リトライ自体はとても便利なので、私はcronやTask Queueではほとんどの例外を自分で処理せずにそのままエラーで終了させています。また、なるべく1つのジョブで複数のWebサービスにはアクセスしないようにしています。(2つ目のサービスへのアクセスでエラーが発生すると、リトライで再度1つ目のサービスにアクセスする必要があるので)

2010年03月19日 【プログラミング】 | コメント(1) |
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。