「固定幅部分レンジ」の列に変換するレンジアダプタを書いてみた

動機

系列データの処理にでは、隣接する複数要素間の関係性について調べたいということが良くあると思う。自然言語処理なんかだと、単語の列（文）に対して「2つの単語X, Yが連続して現われたら、次はどんな単語が来るだろう？」というような事を考えたりする（N-gramモデルとか)。

このような場合に、系列中の「隣接するN要素を列挙」できると嬉しいのだけど、現行のBoost.RangeやP-Stade.Ovenには、そういう列挙を直接的に表現するアダプタが無いので自作してみた、という話。
以下、「隣接するN要素」を「長さNの部分レンジ」と言うことにする。

使用例

使用例は以下の通り。
自作したアダプタは yuttie::windowed(3) の部分で、これが入力レンジを「長さ3の部分レンジの集まりを表わすレンジ」に変換する。

#include <iostream>
#include <string>
#include <iterator>
#include <boost/range/algorithm/copy.hpp>
#include <boost/xpressive/xpressive.hpp>
#include <pstade/oven/foreach.hpp>
#include <pstade/oven/stream_writer.hpp>
#include <pstade/oven/xpressive_tokenized.hpp>

#include "windowed.hpp"


int main(int argc, char *argv[]) {
    using namespace std;
    namespace xp = boost::xpressive;
    namespace oven = pstade::oven;

    string const str = "The quick brown fox jumps over the lazy dog.";

    PSTADE_OVEN_FOREACH(r, str | oven::xpressive_tokenized(+xp::alnum)
                               | yuttie::windowed(3))
    {
        boost::copy(r, oven::stream_writer(cout, ", "));
        cout << endl;
    }

    return 0;
}

実行結果:

The, quick, brown
quick, brown, fox
brown, fox, jumps
fox, jumps, over
jumps, over, the
over, the, lazy
the, lazy, dog

ソースコード

#ifndef WINDOWED_HPP
#define WINDOWED_HPP


#include <boost/iterator/iterator_facade.hpp>
#include <boost/range/sub_range.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/utility.hpp>


namespace yuttie {


    template <class Range>
    struct windowed_iterator
        : public boost::iterator_facade<
            windowed_iterator<Range>,
            boost::sub_range<Range> const,
            boost::forward_traversal_tag
        >
    {
        windowed_iterator()
            : cur_rng_(), end_it_()
        {}

        windowed_iterator(Range const& r, std::size_t len)
            : cur_rng_(boost::begin(r), boost::next(boost::begin(r), len)),
              end_it_(boost::end(r))
        {}

    private:
        friend class boost::iterator_core_access;

        typedef typename boost::range_iterator<Range>::type rng_iterator;
        typedef boost::sub_range<Range> sub_range;

        sub_range const& dereference() const {
            return cur_rng_;
        }

        bool equal(windowed_iterator const& other) const {
            return this->cur_rng_ == other.cur_rng_;
        }

        void increment() {
            if (cur_rng_.end() == end_it_) {
                cur_rng_ = sub_range();
                end_it_ = rng_iterator();
            }
            else {
                cur_rng_.advance_begin(1);
                cur_rng_.advance_end(1);
            }
        }

    private:
        sub_range cur_rng_;
        rng_iterator end_it_;
    };


    template <class Range>
    struct windowed_range : boost::iterator_range<windowed_iterator<Range> > {
        typedef windowed_iterator<Range> iterator;

    private:
        typedef boost::iterator_range<windowed_iterator<Range> > base;

    public:
        windowed_range(Range& r, std::size_t length)
            : base(iterator(r, length), iterator())
        {}
    };

    struct windowed {
        windowed(std::size_t length)
            : length_(length)
        {}
        std::size_t length_;
    };

    template <class ForwardRng>
    inline windowed_range<ForwardRng>
    operator|(ForwardRng& r, windowed const& f) {
        return windowed_range<ForwardRng>(r, f.length_);
    }

    template <class ForwardRng>
    inline windowed_range<const ForwardRng>
    operator|(ForwardRng const& r, windowed const& f) {
        return windowed_range<const ForwardRng>(r, f.length_);
    }


}  // namespace yuttie


#endif  /* WINDOWED_HPP */