Generation of Unique ID in R

ユニークかつセキュアなIDの生成タスク

調べものをしていて、R言語のコミュニティに次のような質問があるのを見かけました。

6桁のIDを発行して最大で400万個程度のユニークなIDを用意したいとのこと。IDは次の要件を満たしてほしいらしいです。

  1. It needs to be alphanumeric, start with letter and maybe end with letter (e.g AA34YB)
  2. Use only upper case alphabets
  3. Do not use the alphabets O or I (this is the alphabet after H and before J)
  4. Use only digits from 1- 9. Exclude 0
  5. First two digit should be letter, then followed by 2 digit number and end with 2 digit letter,e.g "AA22DD","EE34TY","ER67YU"
  6. All records must contain number as shown in rule 5
  7. IT MUST BE 6 DIGIT PLEASE

「これくらいならワイでもできるやろー」と思ったので、思いつきで次のようなスニペットを書いてみました。

f <- function(size) {  
    stopifnot(require(tidyverse))  

    nolooksalike <- str_subset(LETTERS, "[IO]", negate = TRUE)  
    return(  
        map(1:size, as_mapper(~  
            reduce(  
                c(sample(nolooksalike, 2), sample(1:9, 2), sample(nolooksalike, 2)), paste0  
            )  
        ))  
    )  
}  

クソ雑魚な英語しか書けないながらも回答してあげようかと思ったのですが、そもそもこのスニペットは実用に足るのでしょうか。質問者の要求するルールでIDを生成する場合、生成されうるIDは(24^2) * (9^2) * (24^2) = 26,873,856通りとなり、そこから4,000,000個を取るということであれば、IDがユニークであることは一応保証可能です。しかし、たかだか2687万個ほどの組み合わせから400万個も取るとなると、IDをその都度生成していたのではかなりの確率で衝突が起こってしまいます。

衝突可能性の計算

n個の要素からなる元からr個とって少なくとも1個重複する確率は次式のようになる気がします(私立文系出身なので自信ない)。

$$
1 - \frac{C_{r}^{n}}{H_{r}^{n}} = 1 - \frac{C_{r}^{n}}{C_{n}^{n+r-1}}
$$

実際にどの程度の確率で衝突が発生するか計算できればよいのですが、Rで簡単にchoose(2687*10^4, 400*10^4)などとやっていると桁があふれて計算できません。ただ、イメージとしては、先のルールの下ではある程度の個数までIDの生成を繰り返すとほとんど1に近い確率で重複が発生するようになるはずです。

prob <- map_df(100:200, function(choice){  
    tibble(idx = choice, p = (1 - choose(2687, choice) / choose(2687+choice-1, 2687)))  
})  

これはかなり桁を小さくしたうえで計算してみた例ですが、雰囲気的にはこんな感じになると思います。この例では2687個の要素からなる元からr個を取って重複が発生する確率についてrを100から200まで動かして図示しています。グラフを見ると125個取る段階で重複が発生する確率は90%を超えています。

Conclusion

以下のようなことを書こうと思ったけどサインアップできなかったのでやめました。ユニークかつセキュアなID文字列を生成したい場合は、既存のライブラリを活用するようにしましょう。

This function works well to satisfy your order, however, it is not a very clever way. In the first place, your rule is too much strict so that generated ID may easily collide. If you mind whether the ID is unique and secure, you had better to use libraries such as {ids}, {hashids} or {nanoidr} (I am the maintainer of this package!).

紹介しているRパッケージ