Многоосновное преобразование - использование всех комбинаций для сокращения URL - PullRequest
Новая
       22

Многоосновное преобразование - использование всех комбинаций для сокращения URL

1 голос
/ 30 апреля 2010

Я сокращаю URL и пытаюсь найти оптимальный способ кодирования числа (id) в строку символов.

Я использую символы 0-9, A-Z, a-z, так что в основном это будет кодировка base-62. Это довольно простой, но он не использует все возможные коды. Коды, которые он будет производить, будут: 

0, 1, ... y, z, 10, 11, ... zy, zz, 100, 101, ...

Обратите внимание, что коды от 00 до 0z не используются, то же самое для 000 до 0zz и т. Д. Я хотел бы использовать все коды, например: 

0, 1, ... y, z, 00, 01, ... zy, zz, 000, 001, ...

Это будет некоторая комбинация base-62 и base-63, с различными базами в зависимости от положения ... Использовать base-62 легко, например: 

create procedure tiny_GetCode
    @UrlId int
as
set nocount on

declare @Code varchar(10)
set @Code = ''

while (@UrlId > 0 or len(@Code) = 0) begin
    set @Code = substring('0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz', @UrlId % 62 + 1, 1) + @Code
    set @UrlId = @UrlId / 62
end

select @Code

Но мне пока не удалось сделать из него многоосновное преобразование, чтобы использовать все коды.

1 Ответ

4 голосов
/ 30 апреля 2010

Мне удалось сделать преобразование. Хитрость в том, что это не просто смешанная базовая конверсия, более высокая база первого символа также влияет на значения более длинных кодов.

Я начал с более простого случая; коды Base-10. Я видел, что у двузначного диапазона есть 10 дополнительных кодов, у трехзначного диапазона есть 100 дополнительных кодов, и так далее: 

0 - 9        : '0' - '9'
10 - 109     : '00' - '99'
110 - 1109   : '000' - '999'
1110 - 11109 : '0000' - '9999'

Таким образом, значение первого символа в коде является не только основанием, поднятым на позицию, но также имеет смещение.

После применения этого к кодировке base-62 я получил следующее: 

create function tiny_Encode(@UrlId int) returns varchar(10)
as
begin

  declare
    @Chars varchar(62),
    @Code varchar(10),
    @Value int,
    @Adder int

  set @Chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
  if (@UrlId < 63) begin
    set @Code = substring(@Chars, @UrlId, 1)
  end else begin
    set @UrlId = @UrlId - 1
    set @Value = 62
    set @Adder = 0
    while (@UrlId >= @Value * 63 + @Adder) begin
      set @Adder = @Adder + @Value
      set @Value = @Value * 62
    end
    set @Code = substring(@Chars, (@UrlId - @Adder) / @Value, 1)
    set @UrlId = ((@UrlId - @Adder) % @Value)
    while (@Value > 1) begin
      set @Value = @Value / 62
      set @Code = @Code + substring(@Chars, @UrlId / @Value + 1, 1)
      set @UrlId = @UrlId % @Value
    end
  end
  return @Code

end
...