日本人の名字をランダムに抽出する 〜 Alias Method 〜

なにがやりたいか

日本人の名字をランダムに取得したい。

ただし、佐藤さんや鈴木さんはより多く、大柿さんや桑畑さんは低頻度といった具合に、名字の分布に応じた確率で取得したい。

重み付きランダム

発生確率に重み付けされたランダムで、復元抽出(ある特定の単位が重複して標本に選ばれることを許す抽出方式)を行う。

ダーツだったり、よくあるソシャゲのガシャと同じ。

{0.5, 0.3, 0.1, 0.1} といった確率のリストが合った場合、単純に考えると 0.0 ～ 1.0 の間でランダム値を取り、確率を加算していき、ランダム値を超えたらそのインデックスを返すといった感じ。

public static int sample(List<Double> probabilities) {
    double value = random.nextDouble();
    double s = 0.0;
    for (int i = 0; i < probabilities.size(); i++) {
        s += probabilities.get(i);
        if (s >= value) {
            return i;
        }
    }
    return probabilities.size() - 1;
}

線形探索になるので、計算量は O(n) で母数が多い場合にはどうも・・

Alias method

Alias method を使えば、準備に O(n) 、値の抽出は O(1) でできてしまう。

概念的には以下の流れ。

4色の抽選で、それぞれの確率が 1/2、1/3、1/12、1/12 だったとすると、以下のようなダーツ抽選になる。

横にならべると以下のようになる。

4色なので4倍して、高さ1のオレンジの枠を付けてみる。

1〜4のインデックスが崩れないように、オレンジの枠に収めるように移動させる。 青を3分割して、インデックスが3の箇所と4の箇所に割り当てる。

同じように赤を分割して残ったスペースに割り当てる。

整頓されてきもちよいですね。ここでポイントは、

• 4つの列の各ボックス内にはたかだか2つの色しかない
• 1〜4のインデックスは、ボックスの下側の箱の色との対応がくずれていない
  • つまり1は青、2は赤、3は緑、4は紫

という点です。

ダーツを投げる

各ボックスに Alias を定義しましょう。

Alias は、各ボックスの上側の色のインデックス値を割り当てます。

Probability には、各Box内で色の変わる箇所(確率)の値を割り当てます。

左端のボックスの例で言えば、インデックス1 のボックスは、2/3 を超えれば赤(Alias[2])、超えなければ元のインデックスのまま1。 その隣は常にインデックスと同じ2のまま。

抽選がどのように行われるかと言うと、

• 要素数の範囲(1〜4)の乱数(整数)を得た結果 1 だった
• インデックス 1 として左端のボックスを選択
• 0〜1の範囲で乱数を得た結果 0.8 だった
• 0.8 は左端のボックスの色の境界をまたぐため、Alias にある 2 を結果とする
  • またがなければ そのままインデックスの 1 を結果とする

という流れ。

Alias Method の実装

準備段階のボックスの移動のやり方でいくつか方法がある。

Vose's Alias Method では最初にボックスに収まるものとはみ出るものを分類して割り当てていく。

public class AliasMethod {

    private final Random random;
    private final int[] aliasTable;
    private final double[] probTable;

    public AliasMethod(List<Double> probabilities) {

        probabilities = new ArrayList<>(probabilities);

        random = new Random();
        probTable = new double[probabilities.size()];
        aliasTable = new int[probabilities.size()];

        final double average = 1.0d / probabilities.size();

        final Deque<Integer> small = new ArrayDeque<>();
        final Deque<Integer> large = new ArrayDeque<>();
        for (int i = 0; i < probabilities.size(); ++i) {
            if (probabilities.get(i) >= average) {
                large.add(i);
            } else {
                small.add(i);
            }
        }

        while (!small.isEmpty() && !large.isEmpty()) {

            int less = small.removeLast();
            int more = large.removeLast();

            probTable[less] = probabilities.get(less) * probabilities.size();
            aliasTable[less] = more;

            probabilities.set(more, (probabilities.get(more) + probabilities.get(less)) - average);
            if (probabilities.get(more) >= average) {
                large.add(more);
            } else {
                small.add(more);
            }
        }

        while (!small.isEmpty()) {
            int index = small.removeLast();
            probTable[index] = 1.0;
        }

        while (!large.isEmpty()) {
            int index = large.removeLast();
            probTable[index] = 1.0;
        }

    }
    // ・・・
}

で、抽選自体は以下のようになる。

    public int next() {
        int block = random.nextInt(probTable.length);
        boolean coinToss = random.nextDouble() < probTable[block];
        return coinToss ? block : aliasTable[block];
    }

日本人の名前の分布

名字由来netより名字の順位を拝借して以下のようなテキストにする。

佐藤,1894000
鈴木,1809000
高橋,1425000
・・・
後藤田,2500
中松,2500
蓼沼,2500

やっつけですが、テキスト読んで AliasMethod に食べさせます。

public class JapaneseName {

    private List<String> familyNames;
    private AliasMethod aliasMethod;

    public JapaneseName() {

        try (BufferedReader br = new BufferedReader(new InputStreamReader(
                JapaneseName.class.getClassLoader().getResourceAsStream("japaneseNames.txt"),
                StandardCharsets.UTF_8))) {

            familyNames = new ArrayList<>();
            long total = 0;
            List<Integer> counts = new ArrayList<>();

            for (String line; (line = br.readLine()) != null; ) {

                if (line.startsWith("#") || line.isEmpty()) continue;

                String[] elm = line.split(",");
                familyNames.add(elm[0]);
                int count = Integer.parseInt(elm[1]);
                counts.add(count);
                total += count;

            }

            ArrayList<Double> probabilities = new ArrayList<>(counts.size());
            for (int i = 0; i < counts.size(); i++) {
                probabilities.add((double)counts.get(i) / total);
            }
            aliasMethod = new AliasMethod(probabilities);

        } catch (IOException e) {
            throw new RuntimeException("can't read resource", e);
        }

    }

    public String nextFamilyName() {
        return familyNames.get(aliasMethod.next());
    }
}

1億総人口のサンプル取ってみます。

    public static void main(String... args) {
        JapaneseName jn = new JapaneseName();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < 100_000_000; i++) {
            String name = jn.nextFamilyName();
            if (map.containsKey(name)) {
                map.put(name, map.get(name) + 1);
            } else {
                map.put(name, 1);
            }
        }
        for (Map.Entry<String, Integer> entry : sortByValue(map).entrySet()) {
            System.out.println(entry.getKey() + "\t" + entry.getValue());
        }
    }

   static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> map) {
        return map.entrySet()
                .stream()
                .sorted(Map.Entry.comparingByValue(Collections.reverseOrder()))
                .collect(Collectors.toMap(
                        Map.Entry::getKey,
                        Map.Entry::getValue,
                        (e1, e2) -> e1,
                        LinkedHashMap::new
                ));
    }
}

やはり佐藤さん強し。

佐藤   1708077
鈴木  1634994
高橋  1286110
田中  1216995
伊藤  978678
渡辺  969684
山本  956552
中村  953475
小林  935913
加藤  807017
・・・