読者です 読者をやめる 読者になる 読者になる

継続的データ処理

今、わりと本格的なテキスト処理のプログラムを書いているんですが、処理するテキストが大きいせいで、思わぬところで苦労しています。大きいと言ってもGoogleとかの扱っているような「莫大な」サイズではないんですが、数キロバイトから数百メガバイトの、メモリに全部読み込む気にはならない程度には大きなサイズなので、少し面倒だったりします。

「別にフィルター的に処理を順次かけていけばいいんじゃないの?」と思う人がいると思うので、例として擬似BNF記法のファイルを読み込んで、そこに書かれた文法に従って入力をパースするプログラムを考えます。この場合、後者のパースすべき入力が大きい分には、確かにフィルター的な処理をしていけばそれで済みます。しかし、前者の擬似BNF記法のファイルが大きい場合には少し面倒なことになります。

例えば、次のような擬似BNF記法(yacc記法)のファイルがあるとします。

main: "a" x "b";
x: "c" "d" | "e" "f";

これだけなら全部最初に読み込めばいいのですが、これが大きくなった場合、

  1. ルールの数(行数)が多い。
  2. 一つ一つのルールが長い。

という2種類の「大きさ」があるんじゃないかと思います。
1のパターンでは、あらかじめ擬似BNFファイルをパースしておいて、それを利用して入力を処理する、という方法が使えなくなります。さらに、普通の擬似BNF記法パーサを書くと、おそらく一行単位(セミコロン間)で完全な解析をするので、2のパターンでは普通の「よくある」パーサではうまく行きません。これが私の言いたかった大きいファイルを処理する場合の面倒さです。

この両方に同時に対応するために、私は最終的に「ファイルのどの位置をどういう状態で読んでいるか」を記憶することで、処理を途中で中断・再開できるようするという方法をとりました。

上の例を使って具体例を書くと、「今29バイト目にいて、そこはxという名前のルールの中で、これから2個目のOR部を読む」ということを覚えておけば自由に再開が出来るので、そこまでの処理結果を返すことが出来ます。逆に再開するときには、そこまでの処理結果は捨てられるかも知れません。これによってメモリに多量のデータを読み込むことを防ぐことが出来ました。

・・・が、これってプログラム的にはどうにも汚いコードになってしまうんですよねー。こういう、データを中断を入れつつ連続的に、継続的に処理しなければならない場面って結構ある気がするんですが、皆さんはどうやってるんでしょうね?