VPF::нужно получить уникальное число из строки

DooZ

Дата 3.11.2009, 22:51 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 206
Регистрация: 25.11.2005

Репутация: нет
Всего: 1

Здравствуйте, задача следующая
есть строки

"строка номер один"
"строка номер два"
"строка номер три"

нужно по каждой строке получить свой уникальный номер (ИД)
вроде md5 но только цифры
причем они должны быть не большими
скажем в диапазоне от 0 до пусть будет 100000000 (сто миллионов)

я делаю щас вот так:
привожу код c# для примера,

Код


        public long GetUniqPos(string input)
        {
            long id = 0;

            for (int i = 0; i < input.Length; i++)
            {
                id += GetWordNum(input[i]);
            }

            return id;
        }

        private long GetWordNum(char c)
        {
            switch (c)
            {
                case ' ': return 1;
                case '.': return 2;
                case ',': return 3;
                case 'а': return 4;
                case 'б': return 5;
                case 'в': return 6;
                case 'г': return 7;
                case 'д': return 8;
                case 'е': return 9;
                case 'ё': return 10;
                case 'ж': return 11;
                case 'з': return 12;
                case 'и': return 13;
                case 'й': return 14;
                case 'к': return 15;
                case 'л': return 16;
                case 'м': return 17;
                case 'н': return 18;
                case 'о': return 19;
                case 'п': return 20;
                case 'р': return 21;
                case 'с': return 22;
                case 'т': return 23;
                case 'у': return 24;
                case 'ф': return 25;
                case 'х': return 26;
                case 'ц': return 27;
                case 'ч': return 28;
                case 'ш': return 29;
                case 'щ': return 30;
                case 'ъ': return 31;
                case 'ы': return 32;
                case 'ь': return 33;
                case 'э': return 34;
                case 'ю': return 35;
                case 'я': return 36;
                case 'a': return 37;
                case 'b': return 38;
                case 'c': return 39;
                case 'd': return 40;
                case 'e': return 41;
                case 'f': return 42;
                case 'g': return 43;
                case 'h': return 44;
                case 'i': return 45;
                case 'j': return 46;
                case 'k': return 47;
                case 'l': return 48;
                case 'm': return 49;
                case 'n': return 50;
                case 'o': return 51;
                case 'p': return 52;
                case 'q': return 53;
                case 'r': return 54;
                case 's': return 55;
                case 't': return 56;
                case 'u': return 57;
                case 'v': return 58;
                case 'w': return 59;
                case 'x': return 60;
                case 'y': return 61;
                case 'z': return 62;
                case '0': return 63;
                case '1': return 64;
                case '2': return 65;
                case '3': return 66;
                case '4': return 67;
                case '5': return 68;
                case '6': return 69;
                case '7': return 70;
                case '8': return 71;
                case '9': return 72;
                default: return 0;
            }
        }

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

вот собственно вопрос, как его можно доработать что бы слова (разные) не пересекались?

пример пересекающихся строк:
"cudo счастливые знакомства"
"знакомства клайпеда marina"

не спрашивайте что за слова, просто для теста попались...

DooZ

Дата 3.11.2009, 23:45 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 206
Регистрация: 25.11.2005

Репутация: нет
Всего: 1

Вообщем проблема решилась crc суммой
нашел вот такой код в сети
пример на c#

Код


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Utils
{
    public class Crc16
    {
        const ushort polynomial = 0xA001;
        ushort[] table = new ushort[256];

        public ushort ComputeChecksum(byte[] bytes)
        {
            ushort crc = 0;

            for (int i = 0; i < bytes.Length; i++)
            {
                byte index = (byte)(crc ^ bytes[i]);
                crc = (ushort)((crc >> 8) ^ table[index]);
            }

            return crc;
        }

        public byte[] ComputeChecksumBytes(byte[] bytes)
        {
            ushort crc = ComputeChecksum(bytes);
            return new byte[] { (byte)(crc >> 8), (byte)(crc & 0x00ff) };
        }

        public Crc16()
        {
            ushort value;
            ushort temp;

            for (ushort i = 0; i < table.Length; i++)
            {
                value = 0;
                temp = i;

                for (byte j = 0; j < 8; j++)
                {
                    if (((value ^ temp) & 0x0001) != 0)
                    {
                        value = (ushort)((value >> 1) ^ polynomial);
                    }

                    else
                    {
                        value >>= 1;
                    }

                    temp >>= 1;
                }

                table[i] = value;
            }
        }
    }
}

как работать с ним:

Код


Crc16 crc16 = new Crc16();

в месте где нужно получить crc сумму делаем:
long crc = crc16.ComputeChecksum(Encoding.UTF8.GetBytes("моя строка"));

пока глюков не заметил...
тем немения жду комментариев, реально ли решит этот способ мою задачу? (уникальное число уникальной строке)?

Добавлено через 14 минут и 45 секунд
эхх рано я начал радоваться =)
строки все равно пересекаются :-(

вот например
"форекс мтс, pos"
"система торговли форекс"

строки разные а crc одна :-(

как быть то?

Это сообщение отредактировал(а) DooZ - 3.11.2009, 23:45

Akina

Дата 4.11.2009, 00:03 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Цитата(DooZ @ 4.11.2009, 00:45

)

строки разные а crc одна

Это нормально. Хэш гарантированно имеет коллизии, если вариантов данных больше, чем вариантов хэша.
И нерешаемо.

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

cardinal

Дата 4.11.2009, 00:45 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 5
Всего: 99

Цитата(Akina @ 3.11.2009, 22:03

)

И нерешаемо.

А какие альтернативы? smile

--------------------

Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино". А. и Б. Стругацкие

DooZ

Дата 4.11.2009, 10:19 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 206
Регистрация: 25.11.2005

Репутация: нет
Всего: 1

2Akina не бывает нерешаемых задач, просто надо немного подумать =)
вот я щас опять сажусь решать эту задачу =)

если у кого-то есть идеи, буду рад услышать =)
я думаю тут многим интересно решить данную задачу

DooZ

Дата 4.11.2009, 15:22 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 206
Регистрация: 25.11.2005

Репутация: нет
Всего: 1

вопрос снят, в миллиард не уложиться... тема видимо закрыта =)

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »