List update problem とは

リスト更新またはリストアクセスの問題は、オンラインアルゴリズムの競合分析の研究で使用される単純なモデルです。アイテムにアクセスするコストがリストの先頭からの距離に比例するリスト内のアイテムのセット、例えば、リンクされたリスト、およびアクセスの要求シーケンスであるため、アクセスの総コストが最小になるようにリストを並べ替える戦略が必要です。並べ替えはいつでも実行できますが、コストがかかります。標準モデルには、次の2つの並べ替え操作が含まれます。
 現在の位置よりも先にアクセスされているアイテムの自由転置。リスト内の2つのアイテムを交換するための単価の払い戻し。アルゴリズムの性能は、様々なAdversaryモデルの下での敵による要求シーケンスの構築に依存する
この問題のオンラインアルゴリズムは、以前に要求されたアイテムの知識のみに基づいて要素を並べ替え、要求を処理しなければならないため、要求シーケンス全体を見ることができるオフラインアルゴリズムと比較して、最初のリクエストを処理する前に完全な戦略。
オリジナルの使用に加えて、この問題は、Burrows-Wheeler Transformに続くグローバルコンテキストと圧縮性の改善の問題と強い類似性を持つことが示唆されています。この変換に続いて、ファイルは局所的に高い周波数を有する大きな領域を有する傾向があり、頻繁に発生する文字をゼロに向かって移動させる傾向のある技術、または「リスト」の前面に圧縮効率が大幅に向上する。このため、Move-to-Frontおよび周波数カウントの方法および変種は、しばしば圧縮性を改善するためにBWTアルゴリズムに従います。