Существует ли циклическая хеш-функция?
Размышляя об этом вопросе при тестировании вращения строк, я задавался вопросом: была ли такая вещь, как циклическая/циклическая хеш-функция? Например.
h(abcdef) = h(bcdefa) = h(cdefab) etc
Использование для этого включает масштабируемые алгоритмы, которые могут проверять строки n друг против друга, чтобы увидеть, где некоторые из них являются вращениями других.
Я предполагаю, что суть хэша состоит в том, чтобы извлекать информацию, которая зависит от конкретного заказа, но не относится к конкретной позиции. Может быть, что-то, что находит детерминированное "первое положение", вращается и хеширует результат?
Все кажется правдоподобным, но немного выше моего понимания в данный момент; он должен быть там уже...
Ответы
Ответ 1
Я бы согласился с вашей детерминированной "первой позицией" - найти "наименее" характер; если он появляется дважды, используйте следующий символ в качестве тай-брейкера (и т.д.). Затем вы можете повернуть в "каноническую" позицию и хэш, что в обычном режиме. Если таймеры прерваны для всего курса строки, то у вас есть строка, которая является поворотным (если вы понимаете, что я имею в виду), и не имеет значения, что вы выбираете для того, чтобы быть "первым".
Итак:
"abcdef" => hash("abcdef")
"defabc" => hash("abcdef")
"abaac" => hash("aacab") (tie-break between aa, ac and ab)
"cabcab" => hash("abcabc") (it doesn't matter which "a" comes first!)
Ответ 2
Обновление: Как отметил Джон, первый подход не очень хорошо обрабатывает строки с повторением. Проблемы возникают, когда встречаются повторяющиеся пары букв, и полученный XOR равен 0. Вот модификация, которая, как я считаю, исправляет исходный алгоритм. Он использует последовательности Euclid-Fermat для генерации парных взаимно простых чисел для каждого дополнительного вхождения символа в строке. В результате XOR для повторяющихся пар отлична от нуля.
Я также немного очистил алгоритм. Обратите внимание, что массив, содержащий последовательности EF, поддерживает только символы в диапазоне от 0x00 до 0xFF. Это был просто дешевый способ продемонстрировать алгоритм. Кроме того, алгоритм все еще имеет время выполнения O (n), где n - длина строки.
static int Hash(string s)
{
int H = 0;
if (s.Length > 0)
{
//any arbitrary coprime numbers
int a = s.Length, b = s.Length + 1;
//an array of Euclid-Fermat sequences to generate additional coprimes for each duplicate character occurrence
int[] c = new int[0xFF];
for (int i = 1; i < c.Length; i++)
{
c[i] = i + 1;
}
Func<char, int> NextCoprime = (x) => c[x] = (c[x] - x) * c[x] + x;
Func<char, char, int> NextPair = (x, y) => a * NextCoprime(x) * x.GetHashCode() + b * y.GetHashCode();
//for i=0 we need to wrap around to the last character
H = NextPair(s[s.Length - 1], s[0]);
//for i=1...n we use the previous character
for (int i = 1; i < s.Length; i++)
{
H ^= NextPair(s[i - 1], s[i]);
}
}
return H;
}
static void Main(string[] args)
{
Console.WriteLine("{0:X8}", Hash("abcdef"));
Console.WriteLine("{0:X8}", Hash("bcdefa"));
Console.WriteLine("{0:X8}", Hash("cdefab"));
Console.WriteLine("{0:X8}", Hash("cdfeab"));
Console.WriteLine("{0:X8}", Hash("a0a0"));
Console.WriteLine("{0:X8}", Hash("1010"));
Console.WriteLine("{0:X8}", Hash("0abc0def0ghi"));
Console.WriteLine("{0:X8}", Hash("0def0abc0ghi"));
}
Теперь вывод:
7F7D7F7F
7F7D7F7F
7F7D7F7F
7F417F4F
C796C7F0
E090E0F0
A909BB71
A959BB71
Первая версия (которая не завершена): Использовать XOR, который является коммутативным (порядок не имеет значения) и еще один небольшой трюк с участием взаимных совпадений для объединения упорядоченных хэшей пар букв в строке. Вот пример в С#:
static int Hash(char[] s)
{
//any arbitrary coprime numbers
const int a = 7, b = 13;
int H = 0;
if (s.Length > 0)
{
//for i=0 we need to wrap around to the last character
H ^= (a * s[s.Length - 1].GetHashCode()) + (b * s[0].GetHashCode());
//for i=1...n we use the previous character
for (int i = 1; i < s.Length; i++)
{
H ^= (a * s[i - 1].GetHashCode()) + (b * s[i].GetHashCode());
}
}
return H;
}
static void Main(string[] args)
{
Console.WriteLine(Hash("abcdef".ToCharArray()));
Console.WriteLine(Hash("bcdefa".ToCharArray()));
Console.WriteLine(Hash("cdefab".ToCharArray()));
Console.WriteLine(Hash("cdfeab".ToCharArray()));
}
Вывод:
4587590
4587590
4587590
7077996
Ответ 3
Вы можете найти детерминированную первую позицию, всегда начиная с позиции с "нижней" (с точки зрения алфавитного порядка) подстрокой. Поэтому в вашем случае вы всегда начинаете с "a". Если было несколько "а", вам нужно было учитывать два символа и т.д.
Ответ 4
Я уверен, что вы можете найти функцию, которая может генерировать один и тот же хэш, независимо от позиции символа на входе, однако, как вы убедитесь, что h(abc)
!= h(efg)
для каждого мыслимого входа? (Столкновения будут возникать для всех хэш-алгоритмов, поэтому я имею в виду, как вы минимизируете этот риск.)
Вам понадобятся дополнительные проверки даже после генерации хэша, чтобы гарантировать, что строки содержат одни и те же символы.
Ответ 5
Здесь реализация с использованием Linq
public string ToCanonicalOrder(string input)
{
char first = input.OrderBy(x => x).First();
string doubledForRotation = input + input;
string canonicalOrder
= (-1)
.GenerateFrom(x => doubledForRotation.IndexOf(first, x + 1))
.Skip(1) // the -1
.TakeWhile(x => x < input.Length)
.Select(x => doubledForRotation.Substring(x, input.Length))
.OrderBy(x => x)
.First();
return canonicalOrder;
}
предполагающий общий метод расширения генератора:
public static class TExtensions
{
public static IEnumerable<T> GenerateFrom<T>(this T initial, Func<T, T> next)
{
var current = initial;
while (true)
{
yield return current;
current = next(current);
}
}
}
Использование образца:
var sequences = new[]
{
"abcdef", "bcdefa", "cdefab",
"defabc", "efabcd", "fabcde",
"abaac", "cabcab"
};
foreach (string sequence in sequences)
{
Console.WriteLine(ToCanonicalOrder(sequence));
}
выход:
abcdef
abcdef
abcdef
abcdef
abcdef
abcdef
aacab
abcabc
затем вызовите .GetHashCode() на результат, если это необходимо.
если ToCanonicalOrder() преобразуется в метод расширения:
sequence.ToCanonicalOrder().GetHashCode();
Ответ 6
Одна из возможностей состоит в объединении хэш-функций всех круговых сдвигов вашего ввода в один мета-хэш, который не зависит от порядка входов.
Более формально рассмотрим
for(int i=0; i<string.length; i++) {
result^=string.rotatedBy(i).hashCode();
}
Где вы могли бы заменить ^ = любой другой коммутативной операцией.
Более подробно рассмотрим ввод
"ABCD"
чтобы получить хеш, возьмем
hash ( "abcd" ) ^ hash ( "dabc" ) ^ hash ( "cdab" ) ^ hash ( "bcda" ).
Как мы видим, взятие хэша любой из этих перестановок изменит только порядок, который вы оцениваете XOR, который не изменит его значение.
Ответ 7
Я сделал что-то подобное для проекта в колледже. Было два подхода, которые я использовал, чтобы попытаться оптимизировать проблему Traveling-Salesman. Я думаю, что если элементы НЕ гарантированы быть уникальными, второе решение займет немного больше проверки, но первое должно работать.
Если вы можете представить строку как матрицу ассоциаций, то abcdef будет выглядеть как
a b c d e f
a x
b x
c x
d x
e x
f x
Но так будет любая комбинация этих ассоциаций. Было бы тривиально сравнивать эти матрицы.
Еще одним быстрым трюком было бы повернуть строку так, чтобы первая буква была первой. Тогда, если у вас есть одна и та же начальная точка, те же строки будут идентичными.
Вот какой код Ruby:
def normalize_string(string)
myarray = string.split(//) # split into an array
index = myarray.index(myarray.min) # find the index of the minimum element
index.times do
myarray.push(myarray.shift) # move stuff from the front to the back
end
return myarray.join
end
p normalize_string('abcdef').eql?normalize_string('defabc') # should return true
Ответ 8
Может быть, использовать кастинг для каждого смещения (например, RabinKarp) и вернуть минимальное значение хэша? Однако могут быть столкновения.