情報ファイルの最速な圧縮転送を求める2つの線形時間アルゴリズム

概要

論文の詳細を見る
本研究では, コンピュータネットワーク上で, 情報ファイルを理論的に最高速で圧縮転送するためには, どこでその情報ファイルを圧縮・展開すべきかを決める問題を扱う. この問題では, 必要な情報ファイルが置かれているコンピュータをソースと呼び, その情報ファイルを必要としているコンピュータをシンクと呼ぶ. また, 転送の途中で, その情報ファイルを圧縮するコンピュータを圧縮マシンと呼び, 圧縮された情報ファイルを展開する (元の形に戻す) コンピュータを展開マシンと呼ぶ. 現在のファイル転送では, 圧縮マシン及び展開マシンは, それぞれソース及びシンクに限られている. 本研究での「ファイルの圧縮転迭」は, 転送経路上のソースやシンク以外のコンピュータでも, 圧縮マシンや展開マシンとなりうることを仮定する. その上で, ソースから圧縮マシンへのファイルの転送時間, 圧縮マシンでのファイルの圧縮時間, 圧縮マシンから展開マシンへのファイルの転送時間, 展開マシンでのファイルの展開時間, 及び展開マシンからシンクへのファイルの転送時間, これら全ての時間の総和を以て, ファイルの圧縮転送時間と定義し, この時間を最小にするような圧縮マシン及び展開マシンをいかに速く求めるかがファイルの最適な圧縮転送を求める問題である. この問題自体は, 最短路問題に帰着できることが既に示されている. また, 情報ファイルが転送される経路が固定されている場合, この問題は線形時間で解くことができることが示されているが, そのアルゴリズムは, 1. 最短路問題によるもの, 2. 点上の2つのパラメータを使ったもの, の2種類である. 本報告では, これらのアルゴリズムを, 実際にコーディングしてシミュレーションを行うことで, どちらが効率的であるかを比較検証する.
1998-01-29

情報ファイルの最速な圧縮転送を求める2つの線形時間アルゴリズム

スポンサーリンク

概要

著者

関連論文

スポンサーリンク