CRC32 сделать короткий URL для веб - PullRequest
Новая
       18

CRC32 сделать короткий URL для веб

4 голосов
/ 09 сентября 2009

Я пытаюсь понять crc32, чтобы сгенерировать уникальный URL для веб-страницы.

Если мы используем crc32, какое максимальное количество URL-адресов можно использовать, чтобы избежать дубликатов?

Какой может быть приблизительная длина строки, чтобы контрольная сумма равнялась 2 ^ 32?

Когда я попробовал UUID для URL и преобразовал байты uuid в базу 64, я мог сократить длину до 22 символов. Интересно, я могу уменьшить еще больше.

В основном я хочу преобразовать URL (максимум 1024 символа) в сокращенный идентификатор.

Ответы [ 6 ]

6 голосов
/ 09 сентября 2009

Для CRC32 не существует такого числа, как «максимальное количество URL-адресов, чтобы мы могли избежать дубликатов».

Проблема в том, что CRC32 может создавать дубликаты, и это не функция количества значений, которые вы кидаете в него, а функция того, как эти значения выглядят.

Так что вы можете столкнуться со вторым URL, если вам не повезло.

Вы не должны основывать свой алгоритм на создании уникального хэша, вместо этого вы должны создавать уникальное значение для каждого URL-адреса вручную.

4 голосов
/ 09 сентября 2009

Если вы уже храните полный URL-адрес в таблице базы данных, целочисленный идентификатор довольно короткий, и его можно сделать короче, преобразовав его в основание 16, 64 или 85. Если вы можете использовать UUID, вы можете используйте целое число, и вы тоже можете, так как оно короче, и я не вижу, какое преимущество UUID даст в вашей таблице поиска.

1 голос
/ 09 сентября 2009

Правильный способ сделать короткий URL-адрес - сохранить полный в базе данных и опубликовать что-то, сопоставленное с индексом строки. Компактным способом является использование Base64 идентификатора строки, например. Или вы можете использовать UID для первичного ключа и показать это.

Не используйте контрольную сумму, потому что она слишком мала и очень вероятно конфликтует. Криптографический хэш больше и менее вероятен, но все равно это неправильный путь.

1 голос
/ 09 сентября 2009

CRC32 означает циклическая проверка избыточности с 32 битами, где любое произвольное количество бит суммируется до 32-битной контрольной суммы. А функции контрольной суммы сюръективны, это означает, что несколько входных значений имеют одинаковое выходное значение. Таким образом, вы не можете инвертировать функцию.

0 голосов
/ 09 сентября 2009

Самый быстрый (и, возможно, лучший!) Способ решения проблем может заключаться в простом использовании хэша локального пути и запроса заданного URI следующим образом: 

using System;

namespace HashSample
{
    class Program
    {
        static void Main(string[] args)
        {
            Uri uri = new Uri(
                "http://host.com/folder/file.jpg?code=ABC123");

            string hash = GetPathAndQueryHash(uri);

            Console.WriteLine(hash);
        }

        public static string GetPathAndQueryHash(Uri uri)
        {
            return uri.PathAndQuery.GetHashCode().ToString();
        }
    }
}

Вышеприведенное предполагает, что схема URI и хост остаются неизменными. Если нет, GetHashCode будет работать с любой строкой.

Для большой дискуссии о посещении CRC32 Hash Collision: http://episteme.arstechnica.com/eve/forums/a/tpc/f/6330927813/m/821008399831

0 голосов
/ 09 сентября 2009

Нет, даже если вы используете md5 или любую другую контрольную сумму, URL МОЖЕТ быть дубликатом, все зависит от вашей удачи.

Так что не делайте уникальную базу URL на этой контрольной сумме

...