Nasıl bir URL törpüsü kodu?

SORU

12 NİSAN 2009, Pazar

Nasıl bir URL törpüsü kodu?

Giriş alanı içine uzun bir URL yazabilirsiniz URL törpüsü bir hizmet oluşturmak istiyorum ve hizmet URL kısaltır "http://www.example.org/abcdef". "5* *" altı karakter a-z, A-Z and 0-9. içeren başka herhangi bir dize olabilir yerine 56~57 milyar Olası dizeleri yapar.

Düzenleme:Bu konuda devam eden ilgisi nedeniyle Java, PHP JavaScript uygulamaları to GitHub, kullandığım kod yükledim. Eğer isterseniz : çözümlerinizi ekleyin)

Benim yaklaşım:

Üç sütun ile bir veritabanı tablo var:

kimliği, tamsayı, otomatik artış
uzun, dize, uzun URL kullanıcı girdi
kısa, string, kısaltılmış URL (veya sadece altı karakter)

Daha sonra tabloya uzun URL eklemek istiyorum. Sonra otomatik artış "id" ve karma yapı. değeri seçmek istiyorum Bu karma olarak girilmelidir "short". Ama ne tür bir karma örmeli miyim? MD5 gibi Hash algoritmaları çok uzun dizeleri oluşturun. Bu algoritmalar bilmiyorum, sanırım. Kendi kendini inşa algoritması bir iş, çok.

Benim fikrim:

"http://www.google.de/" otomatik artış alacağım kimliği *10.* Daha sonra aşağıdaki adımları yapıyorum:

short = '';
if divisible by 2, add "a" the result to short
if divisible by 3, add "b" the result to short
... until I have divisors for a-z and A-Z.

Bu sayı bölünebilir değil kadar tekrarlanır. Bu iyi bir yaklaşım olduğunu düşünüyor musunuz? Daha iyi bir fikrin var mı?

CEVAP

12 NİSAN 2009, Pazar

"Dize" yaklaşımı. numarasını convert devam ediyorum Ancak eğer bir KİMLİK ise önerilen algoritma başarısız olduğunu fark edeceksinizBaşbakan ve 52'den büyük.

Teorik arka plan

Bijective Function gerekirf. Bu ters bir fonksiyonu bulabilmek için gereklidir('abc') = 123 . g senin içinf(123) = 'abc'işlevi. Bu şu anlama gelir:

Hayır olmalıx1, x2 (x1 ≠ x2)o yapacakf(x1) = f(x2),
ve her içinybir bulmak için olması gerekirxo kadarf(x) = y.

Ne kadar kısaltılmış bir URL İD dönüştürmek için

Kullanmak istediğimiz bir alfabe düşün. Senin durumunda bu [a-zA-Z0-9]. İçerir62 mektuplar.
Oluşturulan otomatik, sayısal benzersiz bir anahtar (örneğin bir MySQL tablonun otomatik artan id).

Bu örneğin 125 kullanacağım10(10 üssü ile 125).
Şimdi 125 dönüştürmek zorunda10X için62(temel 62).

12510= 2 62×¹62×1⁰= 14**

Bu tamsayı bölme ve mod kullanımını gerektirir. Pseudo-kod bir örnek:
```
digits = []

while num > 0
  remainder = modulo(num, 62)
  digits.push(remainder)
  num = divide(num, 62)

digits = digits.reverse
```
Şimdi gösterendeks 2 ve 1senin alfabe. Bu eşleştirme örneğin bir dizi () istiyorum
```
0  → a
1  → b
...
25 → z
...
52 → 0
61 → 9
```
2 seçeneğine c ve 1 seçeneğine b ile cb alırsınız62olarak kısaltılmış URL.
```
http://shor.ty/cb
```

Nasıl ilk KİMLİĞİ için kısaltılmış bir URL çözmek için

Tersi daha da kolay olur. Sadece alfabede geriye doğru arama yapmak.

e9a62çözülecek "alfabe 4, 61 ve 0 mektup".

e9a62= [4,61,0] = 4 62 ×²61 x 62¹0×62⁰= 1915810
Şimdi WHERE id = 19158 ile kayıt veritabanı bulmak ve yönlendirmek.