Re: sb-exconn.el

[TSUCHIYA Masatoshi <tsuchiya@xxxxxxxxxx>]

>> On Tue, 29 Jun 2004 16:44:13 +0900
>> 「土」== tsuchiya@namazu.org (TSUCHIYA Masatoshi) said as follows:

山> (md5 url) ってのは一意性が保証されないのでは?

土> (md5 url-a) と (md5 url-b) の結果が偶然に一致(= ハッシュ値が衝突)
土> することを心配されているのですよね? 確かに，保証はされませんけど，
土> 非常に低い確率でしか衝突は起こらないはずなので，無視できるのではな
土> いかと思うのですが．

と書きましたが，冷静に考えてみると

  (a) shimbun-generate-id() で encode した url が 998 バイトを越える確率
  (b) md5() で得られたハッシュ値が衝突する確率

のどちらが大きいと考えるか，という単純な問題なんですね．

;; で，山岡さんは(b)が大きいと想定し，私は(a)が大きいと想定している，と．

でまあ，はっきり言って，(a)も(b)も実用上問題ないほど小さい確率だと思い
ます．ただ，(a)の方は，それが生じた場合には RFC 違反になってしまうのに
対して，(b)の方は，RFC に常に適合することが保証されているので，それが
メリットかなと思います．

-- 
土屋 雅稔 ( TSUCHIYA Masatoshi )

(defun shimbun-generate-id (server group url)
  (let ((pos 0) buf)
    (while (string-match "[^0-9a-zA-Z_:.]" url pos)
      (setq buf (cons (format "%%%02x" (aref url (match-beginning 0)))
                      (cons (substring url pos (match-beginning 0))
                            buf))
            pos (match-end 0)))
    (setq buf (concat "<"
                      (apply (function concat)
                             (nreverse (cons (substring url pos) buf)))
                      "@" group "." server ".shimbun.namazu.org>"))
    (if (<= (length buf) 986) ;; == (- 998 (length "Message-Id: "))
        buf
      (concat "<" (md5 url) "@" group "." server ".shimbun.namazu.org>"))))

みたいな関数を書けば，より安全になるのは分かりきっているのですが，こん
な汚い処理は見たくない．md5() だけで済むのなら，それで片付けたい．