今，シークが可能な入力ストリームがあったとして，そのストリームに何らかの変換，例えば文字コード変換を行ってその変換結果を読むようなフィルタを実装するとする．
便宜上，（フィルタから見た立場で）変換前の入力ストリームを「入力ストリーム」，変換後に出力するストリームを「出力ストリーム」と呼ぶことにする．（フィルタのクライアントから見れば，ここで言っている「出力ストリーム」は入力ストリームになる．）
このようなフィルタの出力ストリームに，シークの操作を提供するにはどうすれば良いか？という問題．
シークの操作を提供したい理由は，例えば出力ストリーム上でダイレクトに正規表現マッチ，あるいは LL 再帰降下によるパージングをしたい，というモチベーションがあるため．正規表現マッチや LL 再帰降下では現在の読み込み位置から後ろへ戻る，という操作が要求される．
入力ストリームを全部読み切って，メモリ上で上記の操作を行うのが一番楽だけれど，今その方法を嫌う（例えば入力が巨大なファイル）とする．
問題となるのは，現在の出力位置から前に戻るために
- 変換の状態を巻き戻さないといけない
- 出力ストリーム上のオフセット値で戻る量を指定するため，対応する入力ストリームの戻る量を探索しないといけない
変換の状態というのは，例えば入力ストリームが ISO-2022-JP のテキストで，それを UTF-16 に変換するような場合を考えたときに，入力ストリームにシフト状態が存在するようなことを指す．このように変換が状態を持つ (stateful) な場合，最悪，入力ストリームを最初から読み直さないといけない．
また，変換の前後で可変長な変換がなされる場合，指定された出力ストリーム上のオフセット値でストリーム位置を戻すためには，対応するオフセット値で入力ストリームの位置を戻さなければならないが，これは実際に変換をしてみないと分からない．
結果として，このようなフィルタ上のシークを行う場合，少なくとも指定するオフセット値に線形な時間計算量が必要となる．下手をすると，1つだけ戻るための操作に入力ストリームの長さに線形な時間計算量が必要になるかも知れない．
ここで言及している「変換」が何か決め打ちされていれば，ad-hoc な解法もあるかもしれない．けれど，今変換がパラメータ化されているとして，純粋にこのようなシーク可能なフィルタを変換の詳細と切り離して実装できるか？という問題．
ただし，このままだと「変換」の自由度が高すぎるので仮定を入れる．ここで考慮する「変換」は有限状態変換器 (finite state transducer, FST)に限る．（コーディング変換って FST の範疇ですよね？）
で，このようなフィルタの実装として，「一定間隔で状態のキャッシュを保存する」というアイデアを思いついたんですが，これだと
- 未読のストリーム位置へのシークにかかる時間計算量がシークのオフセット量に線形（まあ，これは仕方ない）
- 状態のキャッシュにかかる空間計算量がストリームサイズに線形（キャッシュ間隔とのトレードオフになる）
なんですが，誰かこんな良い方法ありますよ〜って方いらっしゃいませんか？
