タグ

algorithmに関するdlive1のブックマーク (3)

  • http://www.asahi.com/science/update/0722/JJT200707220007.html

    dlive1
    dlive1 2007/07/23
    格子の盤上で12個の丸い駒を斜めに動かして相手の駒を取るゲームで『ミスがなければ必ず引き分け』を発見。5*10^20通りを解析。スパコンでも18年かかったのか?名人は数十年前から予想という人間の経験則と直感はすごい
  • アルゴリズム/画像処理 - osdev-j (MMA)

    このサイトについて major PC section... AT互換機 PC-98x1 FM-TOWNS minor PC section... 8BitPC 16BitPC 32BitPC 68kFamilyPC other technical... 家庭用ゲーム機 携帯用ゲーム機 その他のコンピュータ CPU/コントローラ他 プロトコル/拡張子 アルゴリズム ライブラリ/API other section... ツール プログラミング言語 UI/フォント OS一覧 興味深い Information/Fun 書籍 Communication... けいじばん/一言 Resource... ScreenShot DiskImage Link... projects 関連サイト 最新の30件

    dlive1
    dlive1 2007/02/22
    画像処理系のツールの紹介。
  • ユビキタスの街角 データ圧縮手法の応用

    PPM (Prediction by Partial Matching)というデータ圧縮アルゴリズムがある。 一般に、あるデータ列が与えられているとき、次に来るデータを予測することができればデータ圧縮を行なうことができる。 データ列から判断して次に来るデータが「a」だと確実に判断できるときは「a」を記述する必要が無いからである。 PPM法では、既存のデータ列中の文字列出現頻度を計算することによってこのような予測を行なう。 たとえば「abracadab」というデータの次にどの文字が来るか予測する場合、 「a」は4回、「b」は2回出現している 「b」の後に「r」が続いたことがある 「ab」の後に「r」が続いたことがある ... といった情報を累積して確率を推定する。 この場合、 (3)から考えて次の文字は「r」である確率が高いが、 (1)も考慮すると「a」の確率もある、という風に計算を行なう。

    dlive1
    dlive1 2007/02/15
    PPM法は既存のデータ列の文字列出現頻度を計算で次にくる文字の予測を行い圧縮する。PPM法でspam圧縮を学習させると別のspamも効率よく圧縮できる。こんなのでうまくいくのか、Spamは時系列による偏りが強いんだな
  • 1