|
|
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
Есть такая задача: поставить строке в соответствие уникальное число. Строка может быть, ну скажем 256 или 512 символов. Какие есть предложения? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.05.2008, 17:18 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
hash ? crc ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.05.2008, 17:26 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
Ну наскока я понимаю crc это просто контрольная сумма. Разьве она будет уникальной с достоточной вероятностью? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.05.2008, 17:31 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
смотря как рассчитывать будете, какой полином и т.д., опять же, какой размер числа. в целом да, она будет уникальна ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.05.2008, 17:37 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
вообще советую посмотреть в сторону алгоритмов SHA1 и MD5 . их реализация есть на большинстве языков программирования ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.05.2008, 17:40 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
Ну там другие заморочки. Там просто слишком большое число получиться при md5. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.05.2008, 17:42 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
Хотя не, ступил. MD5 же 128 бит выдаёт. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.05.2008, 17:44 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
Для гарантии уникальности нужно, чтобы уникальное число имело ту же информационную ёмкость, что и строка. Т.е., в случае 1 байта на символ, в числе будет 256 или 512 байт. То есть, можно тупо сконкатенировать числовые коды букв строки в гигантское число. Всё остальное, как то хэши и контрольные суммы, будут давать одинаковые числа для разных строк в конце концов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.05.2008, 17:59 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
ДыкДля гарантии уникальности нужно, чтобы уникальное число имело ту же информационную ёмкость, что и строка. Т.е., в случае 1 байта на символ, в числе будет 256 или 512 байт. То есть, можно тупо сконкатенировать числовые коды букв строки в гигантское число. Всё остальное, как то хэши и контрольные суммы, будут давать одинаковые числа для разных строк в конце концов. Читай методичку по теории кодирования информации ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.05.2008, 18:26 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
Читай теорию множеств и про взаимно однозначное соответствие. Пример для детского сада. Строка длиной в 256 байт. Каждый байт -- число от (будем великодушны и учтём только заглавный английский алфавит) 65 до 90. Всего 26^256 комбинаций. Хэш длиной 128 бит. Каждый бит -- число от 0 до 1. Всего 2^128 комбинаций. Что во сколько раз больше и к каким следствиям в соответствии двух множеств это ведёт, старшая группа считает самостоятельно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.05.2008, 18:45 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
>Читай теорию множеств смеялсо. как же тогда архиваторы работают? Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.05.2008, 14:46 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
ScareCrow >Читай теорию множеств смеялсо. как же тогда архиваторы работают? Там комбинаций меньше, т.к. все комбинации - в словаре ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.05.2008, 15:05 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
Ziva SupernovaЕсть такая задача: поставить строке в соответствие уникальное число. Строка может быть, ну скажем 256 или 512 символов. Какие есть предложения? Для однозначного отображения строка=>число=>строка существуют способы кодирования BinHex, Base64 e.t.c. Если вы хотите получить полезный эффект уменьшения размера то нужно использовать коды Шеннона (Хаффмена), Арифметический код. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.05.2008, 23:44 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
Ziva SupernovaКакие есть предложения? из .... cpguide/html/cpconCryptographyOverView.htm Хэш-коды Алгоритмы хэширования преобразуют двоичные последовательности произвольной длины в двоичные последовательности фиксированного небольшого размера, известные как хэш-коды. Хэш-код является уникальным и очень компактным отображением порции данных. Если вы осуществляете хэширование абзаца текста и изменяете в нем даже одну букву, результат хэширования изменится. В вычислительном плане немыслимо найти два разных входных набора данных, результаты хэширования которых полностью совпадают. Хэш-функции кода подлинности сообщения обычно используются для создания цифровой подписи к данным, в то время как хэш-функции кода обнаружения ошибок предназначены для обеспечения целостности данных. Алиса и Боб могут использовать хэш-функцию для обеспечения целостности данных следующим образом. Если Алиса создает сообщение для Боба и осуществляет хэширование этого сообщения, Боб может впоследствии произвести хэширование и сравнить полученный им и оригинальный хэш-коды. Если результаты хэширования совпадают, значит, сообщение не изменялось; если же они не совпадают, сообщение изменялось после написания его Алисой. Для того чтобы такая система работала, Алиса должна скрывать оригинальный хэш-код от всех, кроме Боба. .NET Framework предоставляет следующие классы, которые реализуют алгоритмы цифровой подписи: HMACSHA1 MACTripleDES RC2CryptoServiceProvider SHA1Managed SHA256Managed SHA256Managed SHA256Managed ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.05.2008, 14:35 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
mcccВ вычислительном плане немыслимо найти два разных входных набора данных, результаты хэширования которых полностью совпадают. Как тонко написано. В сочетании с "Хэш-код является уникальным..." создаёт неверное представление. Дескать, для всех строк хэши будут разные всегда. На самом деле здесь сказано "хрен найдёте, если искать начнёте", что правда. Но разным строкам всё равно будут соответствовать одинаковые хэши. Несмотря на то, что хрен найдёшь такие пары. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.05.2008, 15:04 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
Дык mcccВ вычислительном плане немыслимо найти два разных входных набора данных, результаты хэширования которых полностью совпадают. Как тонко написано. за что купил... был по FW1.1 русскоязычный но куда-то засунули. сейчас Content not found ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.05.2008, 15:20 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
Дык[quot mccc] На самом деле здесь сказано "хрен найдёте, если искать начнёте", что правда. Но разным строкам всё равно будут соответствовать одинаковые хэши. Несмотря на то, что хрен найдёшь такие пары. Согласен, а то у нас были бы чудо-архиваторы ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.05.2008, 15:57 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
Возникла глупая мысль. Сесть и побыстрячку написать такой архиватор. Чтобы доказать методом от противногo его тык-скыть принципиальную невозможность. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.05.2008, 18:22 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
zloy den Дык[quot mccc] На самом деле здесь сказано "хрен найдёте, если искать начнёте", что правда. Но разным строкам всё равно будут соответствовать одинаковые хэши. Несмотря на то, что хрен найдёшь такие пары. Согласен, а то у нас были бы чудо-архиваторы А причем тут архиваторы? Они, всего лишь, исключают избыточность данных путем изменения способа их кодирования. Хэши, кстати, не упаковываются. Да и другие данные без избыточности. Например "1234567890" - не упакуется, ибо некуда. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.06.2008, 01:14 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
Николай1Хэши, кстати, не упаковываются. Да и другие данные без избыточности. Например "1234567890" - не упакуется, ибо некуда. Упакуется. Дельта-кодером. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.06.2008, 10:33 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
mayton Николай1Хэши, кстати, не упаковываются. Да и другие данные без избыточности. Например "1234567890" - не упакуется, ибо некуда. Упакуется. Дельта-кодером. Не стану спорить, ибо не в курсе. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.06.2008, 17:51 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
Николай1 zloy den Дык[quot mccc] На самом деле здесь сказано "хрен найдёте, если искать начнёте", что правда. Но разным строкам всё равно будут соответствовать одинаковые хэши. Несмотря на то, что хрен найдёшь такие пары. Согласен, а то у нас были бы чудо-архиваторы А причем тут архиваторы? Они, всего лишь, исключают избыточность данных путем изменения способа их кодирования. Хэши, кстати, не упаковываются. Да и другие данные без избыточности. Например "1234567890" - не упакуется, ибо некуда. Я имел в виду ту мысль, что любой строке произвольной длины можно поставить взаимнооднозначный хэш, это по сути и будет чудо-архивацией:) А насчет невозможности создания архиватора лучше определенного порога все уже вроде было доказано(правда не помню точно кем, может Хаффманом) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2008, 12:31 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
zloy den Николай1 zloy den Дык[quot mccc] На самом деле здесь сказано "хрен найдёте, если искать начнёте", что правда. Но разным строкам всё равно будут соответствовать одинаковые хэши. Несмотря на то, что хрен найдёшь такие пары. Согласен, а то у нас были бы чудо-архиваторы А причем тут архиваторы? Они, всего лишь, исключают избыточность данных путем изменения способа их кодирования. Хэши, кстати, не упаковываются. Да и другие данные без избыточности. Например "1234567890" - не упакуется, ибо некуда. Я имел в виду ту мысль, что любой строке произвольной длины можно поставить взаимнооднозначный хэш, это по сути и будет чудо-архивацией:) А насчет невозможности создания архиватора лучше определенного порога все уже вроде было доказано(правда не помню точно кем, может Хаффманом) Одна тонкость - архиватор работает в обе стороны. А хэш - только в одну. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.06.2008, 23:14 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
Правильнее было-бы сказать, что функция хэша является сюръективной или сюръекцией на множестве Y, если F : X -> Y ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.06.2008, 00:37 |
|
||
|
Соответствие строки числу.
|
|||
|---|---|---|---|
|
#18+
Николай1 Одна тонкость - архиватор работает в обе стороны. А хэш - только в одну. Знаю, но если бы соответствие было бы взаимнооднозначным, то был бы шанс найти обратную функцию, а это уже и был бы архиватор, который сжимает больше предельно допустимой границы алгоритмов сжатия без потерь. Но хэши не взаимнооднозначны с данными на входе, так что в деле построения архиваторов это не поможет:) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.06.2008, 11:00 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=35340400&tid=1345246]: |
0ms |
get settings: |
4ms |
get forum list: |
9ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
151ms |
get topic data: |
6ms |
get forum data: |
1ms |
get page messages: |
36ms |
get tp. blocked users: |
1ms |
| others: | 224ms |
| total: | 436ms |
| 0 / 0 |
