長い可変長文字列の挿入操作に関する一考察

概要

論文の詳細を見る
本稿では,非常に長い可変長文字列を表現するデータ構造とその操作法を提示して,計算時間と記憶領域の関係を考察する.汎用のテキストエディタや文字列処理システムでは,可変長の文字列を表現する方法として,文字列を一次元配列にべたづめする方法を基本にすることがほぼ定説になっている.そして,非常に長い文字列の挿入や削除の変形操作にも対応するために,配列を基本にして,リストを併用する方法が使われている.本稿では,このデータ構造と挿入と削除の操作について再考し,データ構造として環状配列の環状リストを使い,文字列の挿入操作を行う部分を(操作する部分の近辺しか触わらないという意味で)局所的に限定する方法を提示する.この方法の特徴として,(1)挿入操作が文字列全体の大きさに依存しない時間で実行できること,それと同時に,(2)文字列の表現に要する記憶領域の大きさが(どの時点でも)絶対的に必要な大きさの一定数倍以内ですますことができること,さらに,(3)局所的であるという条件の下で,これより記憶領域が少なくてすむ方法は鮭いという意味で最適なものであることを示す.またこの方法を一般化する.最後に,この方法の実用的意味を議論して,リアルタイム的応用や探索操作の頻度が高い応用に向いていることを指摘する.
社団法人情報処理学会の論文
1991-05-15

長い可変長文字列の挿入操作に関する一考察

スポンサーリンク

概要

著者

関連論文

スポンサーリンク