Уникальный идентификатор строки
От: Аноним  
Дата: 27.12.05 13:25
Оценка:
Добрый день!
Возникла такая задача — по строке получить ее идентификатор типа long (4 байта в С++). Для разных строк идентификатор должен быть разным, для одинаковых — одинаковым. Т.е. нужна функция, которая для строк генерить ключи с гарантированной вероятностью коллизии 1/(2*2147483647). Все известные мне хеш-функции имеют гораздо большую вероятность коллизии. Может нужно воспользоваться к.-л. алгоритмом шифрования? Я ни одного подходящего не знаю, к тому же желательно обойтись без сторонних бинарных библиотек.
Кто что посоветует?
Благодарен заранее.
Re: Уникальный идентификатор строки
От: Mab Россия http://shade.msu.ru/~mab
Дата: 27.12.05 13:29
Оценка: +2 :))
Здравствуйте, Аноним, Вы писали:

Задача поставлена некорректно.

А>Для разных строк идентификатор должен быть разным, для одинаковых — одинаковым.

Очевидно, это требование выполнить невозможно, т.к. возможных строк больше, чем 2^32.

А>Т.е. нужна функция, которая для строк генерить ключи с гарантированной вероятностью коллизии 1/(2*2147483647

Говорить о вероятности коллизии можно лишь есть фиксировать распределение на строках. Итак, какое у Вас оно будет?
Re[2]: Уникальный идентификатор строки
От: Аноним  
Дата: 27.12.05 13:48
Оценка:
Mab>Очевидно, это требование выполнить невозможно, т.к. возможных строк больше, чем 2^32.
Я это понимаю, поэтому и спрашиваю возможное решение. Но видимо, здесь для произвольных строк решения нет, прийдется отталкиваться от структуры конкретных строк. У меня она такова: "5:1020,2460,0,1,1;2460,3900,0,0,1;3900,5340,0,1,1;5340,6780,0,1,1;6780,8220,0,1,1" — это пример. Т.е. одни цифры, запятые и точки с запятой. Длина строки может меняться, но в среднем ок. 100 символов, и редко превышает 150.

Mab>Говорить о вероятности коллизии можно лишь есть фиксировать распределение на строках. Итак, какое у Вас оно будет?

А что такое распределение на строках?
Re[3]: Уникальный идентификатор строки
От: Mab Россия http://shade.msu.ru/~mab
Дата: 27.12.05 13:57
Оценка:
Здравствуйте, Аноним, Вы писали:

Mab>>Говорить о вероятности коллизии можно лишь есть фиксировать распределение на строках. Итак, какое у Вас оно будет?

А>А что такое распределение на строках?
Ну как бы Вы оперируете термином "вероятность", значит и про распределения вероятностей должны знать... Для того, чтобы понять, какова вероятность колиизии, нужно знать, с какой вероятностью встречается каждая строка у Вас во входных данных.

Пока что Вы представили два формальных требования (отсутствие коллизий и верхняя оценка на вероятность таковых), которые выглядят без дополнительной информации весьма загадочно.
Re: Уникальный идентификатор строки
От: Кодт Россия  
Дата: 27.12.05 13:57
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Возникла такая задача — по строке получить ее идентификатор типа long (4 байта в С++). Для разных строк идентификатор должен быть разным, для одинаковых — одинаковым. Т.е. нужна функция, которая для строк генерить ключи с гарантированной вероятностью коллизии 1/(2*2147483647). Все известные мне хеш-функции имеют гораздо большую вероятность коллизии. Может нужно воспользоваться к.-л. алгоритмом шифрования? Я ни одного подходящего не знаю, к тому же желательно обойтись без сторонних бинарных библиотек.


Гораздо большую — это какую? (На твоём наборе). Вот, скажем, CRC32.
Перекуём баги на фичи!
Re: Уникальный идентификатор строки
От: Trean Беларусь http://axamit.com/
Дата: 27.12.05 14:03
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Добрый день!

А>Возникла такая задача — по строке получить ее идентификатор типа long (4 байта в С++). Для разных строк идентификатор должен быть разным, для одинаковых — одинаковым. Т.е. нужна функция, которая для строк генерить ключи с гарантированной вероятностью коллизии 1/(2*2147483647). Все известные мне хеш-функции имеют гораздо большую вероятность коллизии. Может нужно воспользоваться к.-л. алгоритмом шифрования? Я ни одного подходящего не знаю, к тому же желательно обойтись без сторонних бинарных библиотек.
А>Кто что посоветует?
А>Благодарен заранее.

Если набор строк известен, то можно найти такую хэш-функцию. Гуглить по словам perfect hashing, начать можно отсюда

Bob Jenkins
Re[4]: Уникальный идентификатор строки
От: Аноним  
Дата: 27.12.05 14:13
Оценка:
Здравствуйте, Mab, Вы писали:

Mab>Здравствуйте, Аноним, Вы писали:


Mab>>>Говорить о вероятности коллизии можно лишь есть фиксировать распределение на строках. Итак, какое у Вас оно будет?

А>>А что такое распределение на строках?
Mab>Ну как бы Вы оперируете термином "вероятность", значит и про распределения вероятностей должны знать... Для того, чтобы понять, какова вероятность колиизии, нужно знать, с какой вероятностью встречается каждая строка у Вас во входных данных.
Что такое распределение вероятностей я знаю, просто не понял, что Вы имели в виду именно его. Распредения для этого типа строк я не знаю, но знаю, что числа в строках не превышают 90000. Видимо, исходя из этого прийдется сочинять алгоритм.
Re[2]: Уникальный идентификатор строки
От: Аноним  
Дата: 27.12.05 14:17
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Гораздо большую — это какую? (На твоём наборе). Вот, скажем, CRC32.

На моем наборе — не считал, т.к. у меня нет полного набора строк. Теоретически для произвольных строк — примерно 1/2^16.
К своему стыду, не знаю алгоритма CRC32 — раньше не был нужен. Возможно он и подойдет. Не подскажете, где можно о нем почитать?
Re[3]: Уникальный идентификатор строки
От: Mab Россия http://shade.msu.ru/~mab
Дата: 27.12.05 14:23
Оценка:
Здравствуйте, Аноним, Вы писали:

А>На моем наборе — не считал, т.к. у меня нет полного набора строк. Теоретически для произвольных строк — примерно 1/2^16.

Опять же, Вы оперируете числами, называя их 'вероятностями', причем делаете это весьма странным образом. Не нужно так делать.

Возможно Вы имели в виду, что у Вас хешфункция 16-битная?

А>К своему стыду, не знаю алгоритма CRC32 — раньше не был нужен. Возможно он и подойдет. Не подскажете, где можно о нем почитать?

www.google.com: crc-32 algorithm
Re[2]: Уникальный идентификатор строки
От: Аноним  
Дата: 27.12.05 14:25
Оценка:
Здравствуйте, Trean, Вы писали:

T>Если набор строк известен, то можно найти такую хэш-функцию. Гуглить по словам perfect hashing, начать можно отсюда


T>Bob Jenkins

Тут набор строк можно получить, только рассмотрев все возможные числовые комбинации — боюсь, это будет слишком большой набор. В любом случае, большое спасибо, наверняка это пригодится в другой раз!
Re[4]: Уникальный идентификатор строки
От: Аноним  
Дата: 27.12.05 14:31
Оценка:
Здравствуйте, Mab, Вы писали:

Mab>Возможно Вы имели в виду, что у Вас хешфункция 16-битная?

Именно это.
Re: Уникальный идентификатор строки
От: c-smile Канада http://terrainformatica.com
Дата: 01.01.06 04:27
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Добрый день!

А>Возникла такая задача — по строке получить ее идентификатор типа long (4 байта в С++). Для разных строк идентификатор должен быть разным, для одинаковых — одинаковым. Т.е. нужна функция, которая для строк генерить ключи с гарантированной вероятностью коллизии 1/(2*2147483647). Все известные мне хеш-функции имеют гораздо большую вероятность коллизии. Может нужно воспользоваться к.-л. алгоритмом шифрования? Я ни одного подходящего не знаю, к тому же желательно обойтись без сторонних бинарных библиотек.
А>Кто что посоветует?
А>Благодарен заранее.

Это называется perfect hash (function).

Если список строк статический то генерация такой функции дело
gperf.exe.
http://www.gnu.org/software/gperf/manual/html_mono/gperf.html

Для win32 gperf.exe можно взять здесь:
http://gnuwin32.sourceforge.net/packages.html
Re[4]: Уникальный идентификатор строки
От: Lepsik Индия figvam.ca
Дата: 10.01.06 19:12
Оценка:
А>>К своему стыду, не знаю алгоритма CRC32 — раньше не был нужен. Возможно он и подойдет. Не подскажете, где можно о нем почитать?
Mab>www.google.com: crc-32 algorithm

да чего уж мелочится, когда crc64 есть


static const __int64 POLYNOM64 = 0xC96C5795D7870F42;
static unsigned __int64 CRCtbl[256];

__int64  crc64( const void *data, const unsigned long len  )
{
    if( len <= 0 )
    {
        return 0;
    }
    unsigned __int64 crc = 0;
    try
    {
        unsigned char *pdata = (unsigned char *)data;
        static bool init = false;
        if( !init )
        {
            init = true;
            for(int i = 0; i <= 255; i++) 
            {
              unsigned __int64 wrd = i;
              for( int j = 0; j < 8; j++) 
              {
                if( wrd & 1 )
                {
                  wrd = (wrd >> 1) ^ POLYNOM64;
                }else
                {
                  wrd >>= 1;
                }
              }
              CRCtbl[i] = wrd;
            }
        }
        for(unsigned long i = 0; i < len; i++, pdata++ ) 
        {
            unsigned __int64 t1 = crc >> 8;
            unsigned __int64 t2 = CRCtbl[ (crc ^ (unsigned __int64) *pdata) & 0xff ];
            crc = t1 ^ t2;
        }
    }catch(...){}
    return crc;
}
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.