더시드위키
최근 변경최근 토론
특수 기능

namuid(r19 판)

보기RAWBlame되돌리기비교
[주의!] 문서의 이전 버전(에 수정)을 보고 있습니다. 최신 버전으로 이동
분류
유니코드 기준 현대 한글의 모든 완성형 글자는 총 19×21×28=11,17219 \times 21 \times 28 = 11,172자이며, 44개의 문자가 연달아 사용되므로 표본 공간의 크기는
11,1724=15,578,430,750,925,056≈1.5578430751×101611,172^4 = 15,578,430,750,925,056 \approx 1.5578430751 \times 10^{16}

입니다. 편의상 이를 NN이라고 하겠습니다.

하나의 작업에서 xx개의 식별자를 생성했을 때, 이중 '적어도 하나의 식별자 충돌이 발생할 확률'을 구하고자 합니다. 이 확률을 pp로 둡시다. 예를 들어 p=30%p = 30\%라면 대략 30%30\%의 확률로 충돌이 발생할 가능성이 있다는 뜻입니다.

이어서 이 확률식을 역으로 계산하여 '식별자 충돌이 발생할 확률이 pp 이상이기 위해서는 적어도 xx개의 식별자를 생성해야 하는지'를 보이려고 합니다. namuid의 식별자 충돌이 거의 불가능함을 보이고 싶으므로 p=0.1%p = 0.1\%로 두고 테일러 전개로 필요한 표본의 수 xx의 하한을 근사해 봅시다. 일단 자명하게
p=1−NPxNx\displaystyle p = 1 - \frac{_N\mathrm P_x}{N^x}

이므로 어떤 함수 f(x)f(x)에 대해 f(x)≤1−pf(x) \leq 1 - p 를 성립시키는 가장 큰 xx를 근사하면 됩니다. 우선 위에 쓴 pp를 구하는 수식을 곱의 형태로 정리해 봅시다.
1−p=∏k=1x−11−kN\displaystyle 1 - p = \prod^{x-1}_{k = 1} 1 - \frac kN

이어서 e−kNe^{-\frac kN}을 테일러 전개하고 선형 근사를 구하면
e−kN=∑i=0(−kN)ii!≈1−kN\displaystyle e^{-\frac kN} = \sum_{i = 0} \frac{\left(-\frac kN\right)^i}{i!} \approx 1 - \frac kN

이 근사를 적용해서 '어떤 함수' f(x)f(x)가 1−p1 - p를 근사하도록 조립해 봅시다.
f(x)=e−x(x−1)2N=∏k=1x−1e−kN≈∏k=1x−11−kN=1−p\displaystyle f(x) = e^{-\frac{x(x-1)}{2N}} = \prod^{x - 1}_{k = 1} e^{-\frac kN} \approx \prod^{x - 1}_{k = 1} 1 - \frac kN = 1 - p

보기 편하게 로그 형태로 전개하면 다음과 같이 xx에 대한 이차방정식이 나옵니다. 편의상 f(x)f(x)를 yy라고 두었습니다.
x2−x+2Nln⁡y=0\displaystyle x^2 - x + 2N \ln y= 0

방정식을 풀면 역함수를 구할 수 있겠군요. 시행 횟수 xx는 양의 정수임이 자명하니 음수근은 버리겠습니다.
f−1(y)=x=12+14−2Nln⁡y\displaystyle f^{-1}(y) = x = \frac12 + \sqrt{\frac14 - 2N \ln y}

보다시피 이 함수 f−1f^{-1}에 찾고자 하는 충돌 확률 1−p1 - p를 넣으면 이를 만족시키는 xx의 근사값을 구할 수 있습니다. 앞서 p=0.1%=10−3p = 0.1\% = 10^{-3}로 주었으므로
x=12+14−2Nln⁡0.999=5,583,229.881461706≈5.5832298814617×106\displaystyle\begin{aligned} x &= \frac12 + \sqrt{\frac14 - 2N \ln 0.999} \\ &= 5,583,229.881461706 \\ &\approx 5.5832298814617 \times 10^6 \\ \end{aligned}

다시 말하면 한번에 5백만개 정도의 문서를 편집하는 경우 0.1%0.1\% 정도의 충돌 가능성이 있을 수 있다는 소리입니다.

반면에 나무위키:통계에 따르면 2025-05-08 20:04:05-0400 기준 나무위키의 모든 문서는 7,149,0877,149,087개에 불과합니다.