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

namuid(r21 판)

보기RAWBlame되돌리기비교
[주의!] 문서의 이전 버전(에 수정)을 보고 있습니다. 최신 버전으로 이동
분류
1. collision probability research

1. collision probability research[편집]

유니코드 기준 현대 한글의 모든 완성형 글자는 총 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\%의 확률로 충돌이 발생할 가능성이 있다는 뜻입니다.

이어서 실제로 나무위키 모든 문서를 대상으로 하는 1회의 작업을 수행하였을 때, 동일 작업 내에서 식별자 충돌이 발생할 실제 확률 pp를 구하고자 합니다. 단순한 비교를 위해 테일러 전개로 적절한 하한을 찾아 근사하도록 합니다. 일단 자명하게
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개에 불과합니다.