C# でウェーブレット木を実装する話 (2018年秋応用情報技術者試験で出題された件)

私も今回受けてきたのですが、なかなか勉強が捗らず不安しかありません。

ただ、問題解いててほんと 目から鱗 って感じたのが、今回実装する ウェーブレット木 でした。

小さいころから文字列の操作ってめちゃくちゃ苦手で、線形探索くらいしか思いつかなかったんですよね (その当時は 線形探索 なんて言葉も知りませんでしたが)。

そんな中、構文木みたいなノリで木さえ作ってしまえばあとはカウントも簡単みたいなそんな素晴らしいアルゴリズムが目の前に現れて、もう大歓喜ですよね。

これは解くしかない！と思ってやけくそで解きました (やけくそ)

というわけで、そんなウェーブレット木を C# で実装してみました。

ソース

using System;
using System.Collections.Generic;
using System.Linq;

namespace WaveletTreeNS
{
    /// <summary>
    /// ウェーブレット木を表します
    /// </summary>
    /// <typeparam name="T">列挙される値の型</typeparam>
    public class WaveletTree<T>
    {
        #region Private variables

        /// <summary> 出現する値と符号 </summary>
        private Dictionary<T, int> _dist { get; set; }
        /// <summary> 葉までの深さ </summary>
        private int _depth { get; set; }

        #endregion

        #region Public properties

        /// <summary> 左の子節 </summary>
        public WaveletTree<T> Left { get; private set; }
        /// <summary> 右の子節 </summary>
        public WaveletTree<T> Right { get; private set; }
        /// <summary> 割り当てられている列挙可能な値 </summary>
        public IEnumerable<T> Value { get; private set; }
        /// <summary> 割り当てられている列挙可能な値と符号 </summary>
        public IEnumerable<ValueTuple<T, int>> Pairs { get; private set; }

        #endregion

        #region Constructors

        /// <summary>
        /// ウェーブレット木を作成します
        /// </summary>
        /// <param name="value">列挙可能な値</param>
        public WaveletTree(IEnumerable<T> value)
        {
            // 値の種類ごとに符号をつける
            var dist = value
                .Distinct()
                .Select((item, index) => (index, item))
                .ToDictionary((item) => item.item, (item) => item.index);

            // 符号と実際の値をペアにする
            var pairs = value
                .Select((item) => (item, dist[item]));

            // 葉までの深さを計算する
            var depth = (int)Math.Ceiling(Math.Log(dist.Count(), 2));

            // フィールドに格納
            this._dist = dist;
            this._depth = depth;
            this.Value = value;
            this.Pairs = pairs;

            // 子節の計算
            if (dist.Count() != 1)
            {
                // 符号の最上位ビットを見て左右に分割
                this.Left = new WaveletTree<T>(
                    pairs
                        .Where((item) => (item.Item2 & (1 << (depth - 1))) == 0)
                        .Select((item) => item.item)
                        .ToArray()
                    );
                this.Right = new WaveletTree<T>(
                    pairs
                        .Where((item) => (item.Item2 & (1 << (depth - 1))) != 0)
                        .Select((item) => item.item)
                        .ToArray()
                    );
            }
            else
            {
                // 葉になるため子を持たない
                this.Left = this.Right = null;
            }
        }

        #endregion

        #region Public methods

        /// <summary>
        /// 指定された値の出現回数を取得します
        /// </summary>
        /// <param name="value">数える値</param>
        /// <returns>出現回数</returns>
        /// <exception cref="ArgumentNullException"><c>value</c> is <c>null</c>.</exception>
        public int Rank(T value) => _dist.ContainsKey(value) ? this._RankInner(value) : 0;

        #endregion

        #region Private methods

        /// <summary>
        /// 指定された値の出現回数を取得します
        /// </summary>
        /// <param name="value">数える値</param>
        /// <returns>出現回数</returns>
        /// <exception cref="ArgumentNullException"><c>value</c> is <c>null</c>.</exception>
        /// <exception cref="KeyNotFoundException">
        /// The property is retrieved and<c>value</c> does not exist in the collection.
        /// </exception>
        private int _RankInner(T value) =>
            this._depth == 0 ?
            this.Pairs.Count() :
            (((_dist[value] & (1 << (_depth - 1))) == 0) ? this.Left : this.Right).Rank(value);

        #endregion
    }

    /// <summary>
    /// ウェーブレット木に対する汎用的な操作を提供します
    /// </summary>
    public static class WaveletTree
    {
        /// <summary>
        /// ウェーブレット木を作成します
        /// </summary>
        /// <typeparam name="T">列挙される値の型</typeparam>
        /// <param name="value">列挙可能な値</param>
        /// <returns>ウェーブレット木</returns>
        public static WaveletTree<T> Create<T>(IEnumerable<T> value) => new WaveletTree<T>(value);
    }
}

とりあえずテストメソッドと簡単なコンソールアプリ含め、 GitHub に上げてみました。

github.com

GitHub 使ったことないので使い方がよくわからない。誰か教えて。

解説

今回は LINQ を使った抽象的な実装にしてみました。

本来であれば byte[] とか MemoryStream とか使った低レベル操作を必要としますが、簡単に実装できそうな感じでやってみました。

yuzutan-hnk.hatenablog.com

コンストラクタ

コンストラクタは基本的にウェーブレット木の構築を一貫して行ってしまいます。

LINQ 使っているとはいえ実行時計算だと遅いかもなと思って、全体的にゲートを設けて Array に変換しています。

あと Tuple とかと同じように、静的クラスのメソッドで型引数無しでコンストラクタを呼べるようにしてます。 C# でこのハックはほんと使い勝手いいですよね。

// 値の種類ごとに符号をつける
var dist = value
    .Distinct()
    .Select((item, index) => (index, item))
    .ToDictionary((item) => item.item, (item) => item.index);

この部分でとりあえず値の種類ごとに符号化しています。単純にインデックスつけてるだけです。

LINQ の Distinct() メソッドで重複を省けるのめちゃくちゃ楽です。そして ValueTuple を使ってめちゃくちゃ簡略的に書いてます。

で、後から各要素をキーに符号を検索できるように Dictionary にします。これで dist["a"] とかやれば 1 だの 2 だの返ってくるんですよね。楽。

// 符号と実際の値をペアにする
var pairs = value
    .Select((item) => (item, dist[item]));

ここは Dictionary と似ていますが、コンストラクタで渡された配列の各要素に対して先ほど算出した符号をそれぞれ紐づけています。

たとえば new WaveletTree<char>("abcdeabc") を呼ぶと、pairs は { ('a', 0), ('b', 1), ('c', 2), ('d', 3), ('e', 4), ('a', 0), ('b', 1), ('c', 2), } みたいな感じになりますね。

// 葉までの深さを計算する
var depth = (int)Math.Ceiling(Math.Log(dist.Count(), 2));

これはなんか、応用情報の問題に出ていたので適当に計算してみただけです。数学よくわからないのでよくわかりません。

ただ、この後なんだかんだ役に立つ値だということが判明。

// 子節の計算
if (dist.Count() != 1)
{
    // 符号の最上位ビットを見て左右に分割
    this.Left = new WaveletTree<T>(
        pairs
            .Where((item) => (item.Item2 & (1 << (depth - 1))) == 0)
            .Select((item) => item.item)
            .ToArray()
        );
    this.Right = new WaveletTree<T>(
        pairs
            .Where((item) => (item.Item2 & (1 << (depth - 1))) != 0)
            .Select((item) => item.item)
            .ToArray()
        );
}
else
{
    // 葉になるため子を持たない
    this.Left = this.Right = null;
}

もし自身が持ってる値の種類が 1個でない場合は、左右の子節を作成します。

このとき、左右に分ける条件は 符号の最上位ビットが 0 か 1 か です。

ここで先ほど算出した depth が役に立ちます。これをもとにビットシフトしてアンド掛けしてやれば最上位ビットを取り出せます。

~~あれ、 item.Item2 をビットシフトしたほうが速くない…？~~

ここで重要なのは、実は子節が符号を再計算している、ということですね。

ウェーブレット木の基本的な考え方としては、ここで符号の再計算は行われず伝搬していくはずです。

ただし今回は簡単に実装したかったので、これをすっ飛ばして毎回再計算させることにしています。実際には再計算したとしても depth ビットより下位に関しては同じ順序になるはずですし、現状は最上位ビットしか見ることがないので他ビットは情報を持たなくても問題ないんですよね。

もし再計算無しでやるとしたら、 private WaveletTree<T>(IEnumable value, Dictionary<T, int> dist) を実装するとかいかがですかね。やだめんどくさい。

そして、最後は値の種類が 1個の場合 (つまり depth が 0、葉の場合)。左右の子節には null を割り当てておきます。

Rank メソッド (出現回数をカウントする関数)

Rank メソッドは応用情報技術者試験の問題にも出てきた関数です。

例えば "aaaaabbbccccdeeaaabbcddddeeeee" の中に "a" は何個含まれているか、を取得する関数ですね。

public int Rank(T value) => _dist.ContainsKey(value) ? this._RankInner(value) : 0;

private int _RankInner(T value) =>
    this._depth == 0 ?
    this.Pairs.Count() :
    (((_dist[value] & (1 << (_depth - 1))) == 0) ? this.Left : this.Right).Rank(value);

とりあえずコメントを省くとこんな感じになります。めっちゃ短い。

まず public のほうですが、こちらは まず値が存在するかどうかをチェック します。これがないと KeyNotFoundException で落ちます。

で、ワンライナーをきれいにするために内部関数に処理を投げてます。こちらは何をしているかというと…

深さが0 … つまり葉、つまり自身の値の種類が 1個の場合は、自身の要素数をそのまま返す
それ以外の場合、 value の現在の節における最上位ビットが 0 の場合、 this.Left.Rank(value) を実行
それ以外の場合、 this.Right.Rank(value) を実行

という感じです。こっちはちょっとワンライナーで書きたくて意地汚くなってます。もうちょっと読みやすくしたかったですね。

結論

LINQ って楽しいな

最近は本職で JavaScript しか触っていないので、ここまで型をしっかり保っていろいろなメソッドが用意されててスラスラ書ける感覚が気持ちいいです。

次実装するときは MemoryStream か byte[] か何かで実装できればいいな。時期 C# に来る Span<T> でも面白そう。

あと、なぜかわかりませんがこれ struct にするとどのプロジェクトからも実行時に型を見失って動けなくなるので、仕方なく class にしています。誰か情報欲しいな。

yuzutan-hnk.hatenablog.com

あと。受かっててほしいな、応用。

手続き型音楽の日常

関数型音楽に乗り換えたい

C# でウェーブレット木を実装する話 (2018年秋応用情報技術者試験で出題された件)

ソース

解説

コンストラクタ

Rank メソッド (出現回数をカウントする関数)

結論