Есть ли круговая хеш-функция?

Question

Размышляя над этим вопросом о проверке вращения строки , я подумал: существует ли такая вещь, как круговая / циклическая хеш-функция? Э.Г.

h(abcdef) = h(bcdefa) = h(cdefab) etc

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

Полагаю, суть хэша заключается в извлечении информации, которая зависит от порядка, но не зависит от позиции. Может быть, что-то, что находит детерминистическую «первую позицию», поворачивается к ней и хэширует результат?

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

Answer 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!)

Answer 2

Обновление: Как указал Джон, первый подход не очень хорошо обрабатывает строки с повторениями. Проблемы возникают, когда встречаются повторяющиеся пары букв и результирующий XOR равен 0. Вот модификация, которая, я считаю, исправляет исходный алгоритм. Он использует последовательности Евклида-Ферма для генерации парных взаимно простых чисел для каждого дополнительного вхождения символа в строке. В результате 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, который является коммутативным (порядок не имеет значения), и еще один маленький трюк с использованием взаимных кодов для объединения упорядоченных хэшей пар букв в строке. Вот пример на C #:

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

Answer 3

Вы можете найти детерминированную первую позицию, всегда начиная с позиции с «самой низкой» (с точки зрения алфавитного порядка) подстроки. Так что в вашем случае вы всегда начинаете с «а». Если бы было несколько «а», вам нужно было бы учитывать два символа и т. Д.

Answer 4

Одной из возможностей является объединение хеш-функций всех циклических сдвигов вашего ввода в один мета-хеш, который не зависит от порядка входов.

Более формально, рассмотрим

for(int i=0; i<string.length; i++) {
  result^=string.rotatedBy(i).hashCode();
}

Где вы могли бы заменить ^ = любой другой коммутативной операцией.

Более точно, рассмотрим ввод

"ABCD"

чтобы получить хеш, который мы берем

hash ("abcd") ^ hash ("dabc") ^ hash ("cdab") ^ hash ("bcda").

Как мы видим, взятие хэша любой из этих перестановок только изменит порядок вычисления XOR, который не изменит его значение.

Answer 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));
}

выход: * +1010 *

abcdef
abcdef
abcdef
abcdef
abcdef
abcdef
aacab
abcabc

затем при необходимости вызовите .GetHashCode () для результата.

пример использования, если ToCanonicalOrder () преобразован в метод расширения:

sequence.ToCanonicalOrder().GetHashCode();

Answer 6

Я уверен, что вы могли бы найти функцию, которая может генерировать один и тот же хеш независимо от положения символа на входе, однако, как вы будете гарантировать, что h(abc)! = h(efg) для каждого мыслимого ввода?(Столкновения будут происходить для всех алгоритмов хеширования, поэтому я имею в виду, как минимизировать этот риск.)

Вам потребуются некоторые дополнительные проверки даже после генерации хеша, чтобы убедиться, что строки содержат одинаковые символы.1005 *

Answer 7

Может быть, использовать скользящий хеш для каждого смещения (как RabinKarp) и вернуть минимальное значение хеша? Там могут быть столкновения, хотя.

Answer 8

Я сделал что-то подобное для проекта в колледже. Было два подхода, которые я использовал, чтобы попытаться оптимизировать задачу коммивояжера. Я думаю, что если элементы НЕ гарантированно будут уникальными, второе решение потребует больше проверки, но первое должно работать.

Если вы можете представить строку в виде матрицы ассоциаций, чтобы 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