Вопрос по c#, algorithm, string – Алгоритм сравнения строк Рабина Карпа

14

Я видел этот алгоритм сравнения строк Рабина Карпа на форумах на веб-сайте, и мне было интересно его реализовать, но мне было интересно, если кто-нибудь может сказать мне, почему переменные ulong Q и ulong D равны 100007 и 256 соответственно: S ? Какое значение имеют эти ценности с ними?

static void Main(string[] args)
{
    string A = "String that contains a pattern.";
    string B = "pattern";
    ulong siga = 0;
    ulong sigb = 0;
    ulong Q = 100007;
    ulong D = 256;
    for (int i = 0; i < B.Length; i++)
    {
        siga = (siga * D + (ulong)A[i]) % Q;
        sigb = (sigb * D + (ulong)B[i]) % Q;
    }
    if (siga == sigb)
    {
        Console.WriteLine(string.Format(">>{0}<<{1}", A.Substring(0, B.Length), A.Substring(B.Length)));
        return;
    }
    ulong pow = 1;
    for (int k = 1; k <= B.Length - 1; k++)
        pow = (pow * D) % Q;

    for (int j = 1; j <= A.Length - B.Length; j++)
    {
        siga = (siga + Q - pow * (ulong)A[j - 1] % Q) % Q;
        siga = (siga * D + (ulong)A[j + B.Length - 1]) % Q;
        if (siga == sigb)
        {
            if (A.Substring(j, B.Length) == B)
            {
                Console.WriteLine(string.Format("{0}>>{1}<<{2}", A.Substring(0, j),
                                                                    A.Substring(j, B.Length),
                                                                    A.Substring(j + B.Length)));
                return;
            }
        }
    }
    Console.WriteLine("Not copied!");
}
Я не знаком с этим алгоритмом. Я добрался до первогоfor () {} цикл, который содержит ошибку. Что если B.Length & gt; A.length?IndexOutOfRangeException Tergiver
Значение D, равное 256, по существу сдвигает 8 бит влево, чтобы освободить место для следующего символа (хотя это представление, ориентированное на ascii) payo
После прочтения статьи в Википедии (en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm), Я могу видеть, что Q является «большим простым числом» используется для хеширования подстрок. Кажется, что D представляет собой масштабный коэффициент, который учитывает каждое новое положение символа кратное 256, но это, по-видимому, предполагает, что никакое значение символа не будет & gt; = 256. Хотя я здесь вообще не являюсь экспертом. Tergiver

Ваш Ответ

2   ответа
6

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

Вы можете видеть эти типы магических чисел, используемые для хеширования многих мест. Пример ниже - декомпилированное определение функции GetHashCode строкового типа .NET 2.0:

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
public override unsafe int GetHashCode()
{
    char* chrPointer = null;
    int num1;
    int num2;
    fixed (string str = (string)this)
    {
        num1 = 352654597;
        num2 = num1;
        int* numPointer = chrPointer;
        for (int i = this.Length; i > 0; i = i - 4)
        {
            num1 = (num1 << 5) + num1 + (num1 >> 27) ^ numPointer;
            if (i <= 2)
            {
                break;
            }
            num2 = (num2 << 5) + num2 + (num2 >> 27) ^ numPointer + (void*)4;
            numPointer = numPointer + (void*)8;
        }
    }
    return num1 + num2 * 1566083941;
}

Вот еще один пример из сгенерированной R # функции переопределения GetHashcode для типа образца:

    public override int GetHashCode()
    {
        unchecked
        {
            int result = (SomeStrId != null ? SomeStrId.GetHashCode() : 0);
            result = (result*397) ^ (Desc != null ? Desc.GetHashCode() : 0);
            result = (result*397) ^ (AnotherId != null ? AnotherId.GetHashCode() : 0);
            return result;
        }
    }
Error: User Rate Limit Exceeded c grum
7

Что касается кода, то основная идея Рабина Карпа состоит в том, чтобы выполнить сравнение хеша между скользящей частью строки и шаблоном.

Хэш не может быть вычислен каждый раз для целых подстрок, иначе сложность вычисления будет квадратичнойO(n^2) вместо линейногоO(n).

Следовательно,переходящий хэш применяется функция, например, на каждой итерации требуется только один символ для обновления значения хеша подстроки.

Итак, давайте прокомментируем ваш код:

for (int i = 0; i < B.Length; i++)
{
    siga = (siga * D + (ulong)A[i]) % Q;
    sigb = (sigb * D + (ulong)B[i]) % Q;
}
if (siga == sigb)
{
    Console.WriteLine(string.Format(">>{0}<<{1}", A.Substring(0, B.Length), A.Substring(B.Length)));
    return;
}

^ Эта часть вычисляет хэш шаблонаB (sigb) и хеш-код начальной подстрокиA одинаковой длиныB. Actually it's not completely correct because hash can collide¹ and so, it is necessary to modify the if statement : if (siga == sigb && A.Substring(0, B.Length) == B).

ulong pow = 1;
for (int k = 1; k <= B.Length - 1; k++)
    pow = (pow * D) % Q;

^ Здесь вычисленоpow что необходимо для выполнения хеширования.

for (int j = 1; j <= A.Length - B.Length; j++)
{
    siga = (siga + Q - pow * (ulong)A[j - 1] % Q) % Q;
    siga = (siga * D + (ulong)A[j + B.Length - 1]) % Q;
    if (siga == sigb)
    {
        if (A.Substring(j, B.Length) == B)
        {
            Console.WriteLine(string.Format("{0}>>{1}<<{2}", A.Substring(0, j),
                                                                A.Substring(j, B.Length),
                                                                A.Substring(j + B.Length)));
            return;
        }
    }
}

^ Наконец, оставшаяся строка (т.е. от второго символа до конца) сканируется, обновляя значение хеша подстроки A и сравнивается с хешем B (вычисляется в начале).

Если два хэша равны, подстрока и шаблон сравниваются & # xB9; и если они фактически равны, возвращается сообщение.

& # XB9;Хеш-значения могут сталкиваться; следовательно, если две строки имеют разные значения хеша, ониdefinitely разные, но если два хеша равны ониcan быть равным или нет.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded c grum

Похожие вопросы