25 July 2014
将Python实现的short_url.py改写成了Golang实现。

上文提到在GitHub找到一个Python实现的打散ID压缩成62进制的算法,今天抽空翻译成了Golang。虽然说代码都看懂了,但是动手翻译的时候发现还是有一些细节的东西挺有意思的。代码放到了go_code项目下。源码也贴在这里。

import (
	"bitbucket.org/tebeka/base62"
	"fmt"
)

var (
	DEFAULT_BLOCK_SIZE = uint(24)
	DEFAULT_ENCODER    *UrlEncoder
	MIN_LENGTH         = 5
)

type UrlEncoder struct {
	BlockSize uint
	Mask      uint64
	Mapping   []uint
}

func NewUrlEncoder(blocksize uint) (u *UrlEncoder) {
	u = new(UrlEncoder)
	u.BlockSize = blocksize
	u.Mask = (1 << blocksize) - 1
	for i := uint(0); i < blocksize; i++ {
		u.Mapping = append(u.Mapping, blocksize-i-1)
	}
	return u
}

func (this *UrlEncoder) Encode(n uint64) uint64 {
	return (n & ^this.Mask) | this.encode(n&this.Mask)
}

func (this *UrlEncoder) encode(n uint64) (result uint64) {
	for i, b := range this.Mapping {
		if n&(1<<uint(i)) > 0 {
			result |= (1 << b)
		}
	}
	return result

}

func (this *UrlEncoder) Decode(n uint64) uint64 {
	return (n & ^this.Mask) | this.decode(n&this.Mask)
}

func (this *UrlEncoder) decode(n uint64) (result uint64) {
	for i, b := range this.Mapping {
		if n&(1<<uint(b)) > 0 {
			result |= (1 << uint(i))
		}
	}
	return result
}

func (this *UrlEncoder) Enbase(n uint64) string {
	return base62.Encode(n)
}

func (this *UrlEncoder) Debase(n string) uint64 {
	return base62.Decode(n)
}

func (this *UrlEncoder) EncodeUrl(n uint64) (short_url string) {
	return DEFAULT_ENCODER.Enbase(DEFAULT_ENCODER.Encode(n))
}

func DecodeUrl(short_url string) (n uint64) {
	return DEFAULT_ENCODER.Decode(DEFAULT_ENCODER.Debase(short_url))
}

func init() {
	DEFAULT_ENCODER = NewUrlEncoder(DEFAULT_BLOCK_SIZE)
}

func Disperse(i uint64) (disperse_i uint64) {
	fmt.Println(DEFAULT_ENCODER)
	a := DEFAULT_ENCODER.Encode(i)
	b := DEFAULT_ENCODER.Enbase(a)
	c := DEFAULT_ENCODER.Debase(b)
	disperse_i = DEFAULT_ENCODER.Decode(c)
	fmt.Println(i, a, b, c, disperse_i)
	return disperse_i
}

里面用到了别人实现的62进制压缩包。实现原理在上一篇文章《网址压缩的调研分析》的最后一篇文章里面已经说得很清楚了,可以参考那篇文章。

下面接着说一下短网址的调研情况。这之前,都只是讲了算法的实现,而具体的存储数据库还没有介绍。GitHub上面与此相关的项目都是使用MySQL实现的。用数据库实现确实很方便,表很简单,两个字段ID和网址就可以了。但是,在数据结构是如此简单的情况下,一般都是使用Redis来实现。Redis是将Key缓存在内存当中,查询速度快。然而,MySQL有一个Redis无法比拟的优势:Redis只能通过Key查询Value的值,而数据库可以实现双向映射。在用户添加网址的时候,需要去库里查询是否已经存在于库中了,这时需要使用网址来作为查询字段;而在解析短网址的时候,还会需要通过ID查询原始网址。这里就用到了双向查询。

看来使用ID进行编码短网址的方式,目前只能使用传统数据库了。


######参考文献

原文链接:网址压缩的调研分析(续),转载请注明来源!

EOF

欢迎加微信交流与吐槽



本站总访问量次; 本站访客数人次; 本文总阅读量次;