Cалют!
Кто подскажет, как сделать инвариантную характеристику конкретной строке из букв. То есть нужна числовая оченка, не изменяющаяся при перестановке букв в строке, но меняющаяся при замене (или добавлении) хотя бы одной бувы на другую "чужую".
Здравствуйте, gmkraprike, Вы писали:
G>Cалют! G>Кто подскажет, как сделать инвариантную характеристику конкретной строке из букв. То есть нужна числовая оченка, не изменяющаяся при перестановке букв в строке, но меняющаяся при замене (или добавлении) хотя бы одной бувы на другую "чужую".
G>Есть мысли?
Посчитать количество букв в строке.
Затем выписать эти значения для букв от .. до .. и рассматривать полученную последовательность как одно большое число.
Здравствуйте, gmkraprike, Вы писали:
G>Cалют! G>Кто подскажет, как сделать инвариантную характеристику конкретной строке из букв. То есть нужна числовая оченка, не изменяющаяся при перестановке букв в строке, но меняющаяся при замене (или добавлении) хотя бы одной бувы на другую "чужую".
G>Есть мысли?
Здравствуйте, Буравчик, Вы писали:
Б>Посчитать количество букв в строке. Б>Затем выписать эти значения для букв от .. до .. и рассматривать полученную последовательность как одно большое число.
Правильно ли я понял:
Числовая оценка представляет большое число (26 разрядов — по количеству букв в англ.алфавите), где в каждом разряде(i) стоит значение array[i] равное количеству вхождений бувкы (под номером i в алфавите) в слове.
Здравствуйте, gmkraprike, Вы писали:
G>Здравствуйте, Юрий Жмеренецкий, Вы писали:
ЮЖ>>Хеш упорядоченной (отсортированной) строки.
G>Благодарю. Можно ли сделать экономнее? Предполагается, что данная функция (к строкам) будет выполняться очень часто (в цикле).
О, требования начинают изменяться =) Тогда то, что предложил Буравчик — сначала заполнить массив из 26 элементов (вхождения каждой буквы) для эталонной строки, потом выполнять тоже самое для каждой и сравнивать содержимое двух массивов (memcmp).
Здравствуйте, gmkraprike, Вы писали:
G>Правильно ли я понял: G>Числовая оценка представляет большое число (26 разрядов — по количеству букв в англ.алфавите), где в каждом разряде(i) стоит значение array[i] равное количеству вхождений бувкы (под номером i в алфавите) в слове.
Правильно.
G>Можно ли сократить объем?
Натравить хэш-функцию на этот массив.
Надо побольше информации о задаче...
Откуда ограничения по памяти, откуда по скорости?
Зачем это все? Что со строками происходит потом?
Здравствуйте, gmkraprike, Вы писали:
G>Cалют! G>Кто подскажет, как сделать инвариантную характеристику конкретной строке из букв. То есть нужна числовая оченка, не изменяющаяся при перестановке букв в строке, но меняющаяся при замене (или добавлении) хотя бы одной бувы на другую "чужую".
G>Есть мысли?
десятичное число где по порядку идут количества всех букв: например для "example" это
10002000000110010000000100
результат в большинстве случаев будет помещаться в 64 бита.
Здравствуйте, Caracrist, Вы писали:
C>десятичное число где по порядку идут количества всех букв: например для "example" это C>10002000000110010000000100 C>результат в большинстве случаев будет помещаться в 64 бита.
Так нельзя. Будет много коллизий, когда количество вхождений букв в строке станет большим.
Например
Строка a+10b: "abbbbbbbbbb"
Получаем: 11000000000000000000000000 (выделил количество букв B)
Строка 11a: "aaaaaaaaaaa"
Получаем: 11000000000000000000000000 (выделил количество букв A)
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, Caracrist, Вы писали:
C>>десятичное число где по порядку идут количества всех букв: например для "example" это C>>10002000000110010000000100 C>>результат в большинстве случаев будет помещаться в 64 бита.
Б>Так нельзя. Будет много коллизий, когда количество вхождений букв в строке станет большим.
Б>Например Б>Строка a+10b: "abbbbbbbbbb" Б>Получаем: 11000000000000000000000000 (выделил количество букв B)
Б>Строка 11a: "aaaaaaaaaaa" Б>Получаем: 11000000000000000000000000 (выделил количество букв A)
Б>Видим одинаковый результат.
Тогда все варианты хеш тоже отпадают... Из моей практики, они очень часто повторяются...
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, Caracrist, Вы писали:
C>>десятичное число где по порядку идут количества всех букв: например для "example" это C>>10002000000110010000000100 C>>результат в большинстве случаев будет помещаться в 64 бита.
Б>Так нельзя. Будет много коллизий, когда количество вхождений букв в строке станет большим.
Б>Например Б>Строка a+10b: "abbbbbbbbbb" Б>Получаем: 11000000000000000000000000 (выделил количество букв B)
Б>Строка 11a: "aaaaaaaaaaa" Б>Получаем: 11000000000000000000000000 (выделил количество букв A)
Б>Видим одинаковый результат.
другой вариант:
берём все буквы и ассоциируем их с простыми числами для нескольки частей. допустим 4 части:
a 2, b 3,c 5,d 7,e 11,f 13,
g 2,h 3,i 5,j 7,k 11,l 13,
m 2,n 3,o 5,p 7,q 11,r 13,s 17,
t 2,u 3,v 5,w 7,x 11,y 13,z 17
И теперь считаем число для каждой части умножая на простое число по количеству присутствия. Можно добавлять дополнительные числа по мере надобности. Например выделить по 64 бита для каждого изначально.
"example"
242
13
14
11
Здравствуйте, gmkraprike, Вы писали:
G>Cалют! G>Кто подскажет, как сделать инвариантную характеристику конкретной строке из букв. То есть нужна числовая оченка, не изменяющаяся при перестановке букв в строке, но меняющаяся при замене (или добавлении) хотя бы одной бувы на другую "чужую".
G>Есть мысли?
Вот исчо
первые 26 бит это маска того что есть, потом 6 бит(от 1 до 64) на количество бит для каждого числа(которое присутствует) и далее сами биты в порядке возрастания по маске (0 = 1).
Получаем число от 0 до 2^(32+64 *32)
"example"
10001000000110010000000100 000000 010000
10001000000110010000000100000000 = 2283340032
01000000000000000000000000000000 = 1073741824
то есть "example" можно представить ввиде 64 битного числа... конечно желательно выделить побольше бит если ожидаются длинные сроки...
Здравствуйте, gmkraprike, Вы писали:
G>Cалют! G>Кто подскажет, как сделать инвариантную характеристику конкретной строке из букв. То есть нужна числовая оченка, не изменяющаяся при перестановке букв в строке, но меняющаяся при замене (или добавлении) хотя бы одной бувы на другую "чужую".
G>Есть мысли?
А если просто считать 32-х битную сумму кодов символов и 32-битное же произведение и использовать эту пару как инвариант? Только что проверил строки от "aaaaa" до "zzzzz" — коллизий не нашлось
Здравствуйте, Caracrist, Вы писали:
C>другой вариант: C>берём все буквы и ассоциируем их с простыми числами для нескольки частей. допустим 4 части: C>a 2, b 3,c 5,d 7,e 11,f 13, C>g 2,h 3,i 5,j 7,k 11,l 13, C>m 2,n 3,o 5,p 7,q 11,r 13,s 17, C>t 2,u 3,v 5,w 7,x 11,y 13,z 17 C>И теперь считаем число для каждой части умножая на простое число по количеству присутствия. Можно добавлять дополнительные числа по мере надобности. Например выделить по 64 бита для каждого изначально. C>"example" C>242 C>13 C>14 C>11
Мысль интересна. Но пока не все понимаю, а точнее не могу понять обоснование, почему это должно работать.
Вопросы:
1)Почему были выбраны именно простые числа?
2)За что отвечает выбор количества "частей". Понятно, что, если частей много, то максимальное простое число в ней будет меньше, чем в случае малого числа таких "частей". Зная ответ на этот вопрос, я могу, наверное, определить, что будет эффективнее (экономнее).
3)Какой мат.операцией лучше объединить эти четыре оценки в одну числовую характеристику — число. Чтобы добиться ее уникальности.
PS Кстати, в таком случае можно использовать информацию о частоте букв в языке. К примеру, бука "e" в англ. — maximum, "z" — minimum.
Здравствуйте, komaz, Вы писали:
K>А если просто считать 32-х битную сумму кодов символов и 32-битное же произведение и использовать эту пару как инвариант? Только что проверил строки от "aaaaa" до "zzzzz" — коллизий не нашлось
Мне тоже интересно.
Получается, чтобы убедиться в уникальности такой оценки, нужно дать обоснование в единственности (однозначности) решения системы двух уравнений
(например)
1) x + y + z = const1
2) x * y * z = const2
Здравствуйте, gmkraprike, Вы писали:
G>Мысль интересна. Но пока не все понимаю, а точнее не могу понять обоснование, почему это должно работать. G>Вопросы: G>1)Почему были выбраны именно простые числа? G>2)За что отвечает выбор количества "частей". Понятно, что, если частей много, то максимальное простое число в ней будет меньше, чем в случае малого числа таких "частей". Зная ответ на этот вопрос, я могу, наверное, определить, что будет эффективнее (экономнее). G>3)Какой мат.операцией лучше объединить эти четыре оценки в одну числовую характеристику — число. Чтобы добиться ее уникальности.
G>PS Кстати, в таком случае можно использовать информацию о частоте букв в языке. К примеру, бука "e" в англ. — maximum, "z" — minimum.
Не против, если я отвечу?
1. Потому что результатом умножения простых чисел никогда не будет другое простое число. В результате умножения получим уникальный набор простых множителей.
3,2. Например, логическим ИЛИ. Каждую группу в нужные 2 байта 64-битного числа. Вот, видимо, отсюда и 4 группы.
Лично от меня, продолжение идеи:
Присвоить уникальное простое число каждой букве, причём в зависимости от частоты её встречаемости.
То есть:
Здравствуйте, BuHTu4eK, Вы писали:
BHT>Здравствуйте, gmkraprike, Вы писали:
G>>PS Кстати, в таком случае можно использовать информацию о частоте букв в языке. К примеру, бука "e" в англ. — maximum, "z" — minimum.
BHT>Не против, если я отвечу? BHT>1. Потому что результатом умножения простых чисел никогда не будет другое простое число. В результате умножения получим уникальный набор простых множителей.
BHT>3,2. Например, логическим ИЛИ. Каждую группу в нужные 2 байта 64-битного числа. Вот, видимо, отсюда и 4 группы.
BHT>Лично от меня, продолжение идеи: BHT>Присвоить уникальное простое число каждой букве, причём в зависимости от частоты её встречаемости. BHT>То есть:
BHT>e — 2 BHT>t — 3 BHT>o — 5 BHT>... BHT>z — 101
Тогда уже так:
e — 2
t — 2
a — 2
o — 2
i — 3
n — 3
s — 3
h — 3
r — 5
d — 5
l — 5
c — 5
u — 7
m — 7
w — 7
f — 7
g — 11
y — 11
p — 11
b — 11
v — 13
k — 13
j — 13
x — 13
q — 17
z — 17
Здравствуйте, gmkraprike, Вы писали:
G>Здравствуйте, komaz, Вы писали:
K>>А если просто считать 32-х битную сумму кодов символов и 32-битное же произведение и использовать эту пару как инвариант? Только что проверил строки от "aaaaa" до "zzzzz" — коллизий не нашлось
G>Мне тоже интересно. G>Получается, чтобы убедиться в уникальности такой оценки, нужно дать обоснование в единственности (однозначности) решения системы двух уравнений G>(например) G>1) x + y + z = const1 G>2) x * y * z = const2
Ну в условиях переполнения оценка наверняка будет неуникальна, как и любое другое отображение строк на 64 бита
А задача кстати не позволяет использовать, например, "быстрые" хэши с потенциальными коллизиями и "честную" проверку в случае оных?
Здравствуйте, gmkraprike, Вы писали:
G>Мне тоже интересно. G>Получается, чтобы убедиться в уникальности такой оценки, нужно дать обоснование в единственности (однозначности) решения системы двух уравнений G>(например) G>1) x + y + z = const1 G>2) x * y * z = const2
Две строки — "\4" и "\2\2". Так что ещё надо как минимум включить длину строк.
Здравствуйте, komaz, Вы писали:
K>А задача кстати не позволяет использовать, например, "быстрые" хэши с потенциальными коллизиями и "честную" проверку в случае оных?
Это как это? Коллизия-то и определяется через "честную" проверку.
С другой стороны — да, есть же хэши, для которых коллизии пока неизвестны.
