Внедрение FAST Прокручивающегося хеша

Question

Внедрение FAST Прокручивающегося хеша

При создании библиотеки в среде POSIX имя по умолчанию будет иметь префикс lib. Это объясняется в add_library документации.

Таким образом, для целевой библиотеки find связанный файл будет иметь имя libfind.so, то есть имя файла, которое нужно передать в dlopen.

И, конечно же, рабочий каталог исполняемого файла (в основном, каталог, из которого вы запускаете программу) должен находиться там, где находится библиотека. Или вам нужно указать путь к библиотеке.

16

hash c++

задан River 18 October 2017 в 15:20

3 ответа

Некоторые указатели для внедрения FAST:

Избегайте n операции по модулю (% в C как языки) маска использования n - 1, где n 2^k, включайте операции для поиска хеш-таблицы. Да, возможно произвести хороший хеш с неначалом модули.
Выберите множители и экспоненты с хорошими показателями качества, см. данную статью для деталей.

4

ответ дан 30 November 2019 в 22:10

Я записал это некоторое время назад. Его записанный в c#, но это очень близко к c, необходимо будет только добавить несколько параметров. Это должно работать, но я не имею, тестируют эту версию, я удалил пару строк, которые будут игнорировать символы неслова или регистр. Я надеюсь, что это помогает

private const int primeBase = 101;
//primeBase^2*[0]+primeBase^1*[1]+primeBase^0*[2]
//==
//primeBase*(primeBase*[0]+[1])+[2]
public static int primeRollingHash(String input, int start, int end)
{
    int acc = 0;
    for (int i = start; i <= end; i++)
    {
        char c = input[i];
        acc *= primeBase;
        acc += c;
    }
    return acc;
}

public static int primeRollingHash(String input)
{
    return primeRollingHash(input, 0, input.Length - 1);
}

public static int rollHashRight(int currentHashValue, String input, 
                                int start, int newEnd)
{
    if (newEnd == input.Length)
        return currentHashValue;
    int length = newEnd - start - 1;
    int multiplier = primeBase;
    char newChar = input[newEnd];
    int firstValue = input[start];
    if(length>0)
        firstValue *= length * primeBase;
    return (currentHashValue - firstValue) * multiplier + newChar;
}

1

ответ дан 30 November 2019 в 22:10

Другие вопросы по тегам:

hash c++

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

score 16 · Accepted Answer

"Главная основная" идея шифра должна работать прилично - хотя решение он отправил немного поверхностные взгляды.

Я не думаю, что существует любая потребность в обратном умножении в этом методе. Вот мое решение:

Скажите строку, которую мы в настоящее время хешировали, "abc", и мы хотим добавить "d" и удалить "a".

Точно так же, как Шифр мой основной хеш-алгоритм будет:

unsigned hash(const string& s)
{
    unsigned ret = 0;
    for (int i = 0; i < s.size(); i++)
    {
        ret *= PRIME_BASE; //shift over by one
        ret += s[i]; //add the current char
        ret %= PRIME_MOD; //don't overflow
    }
    return ret;
}

Теперь, для реализации скольжения:

hash1 = [0]*base^(n-1) + [1]*base^(n-2) + ... + [n-1]

Мы хотели бы добавить что-то в конце и удалить первое значение, таким образом,

hash2 = [1]*base^(n-1) + [2]*base^(n-2) + ... + [n]

Сначала мы можем добавить последнюю букву:

hash2 = (hash1 * PRIME_BASE) + newchar;
=> [0]*base^n + [1]*base^(n-1) + ... + [n-1]*base + [n]

Затем просто вычтите первый символ:

hash2 -= firstchar * pow(base, n);
=> [1]*base^(n-1) + ... + [n]

Важное примечание: необходимо быть осторожны относительно переполнения. Можно принять решение просто позволить ему переполнить неподписанного интервала, но я думаю, что это намного более подвержено коллизии (но также и быстрее!)

Вот моя реализация:

#include <iostream>
#include <string>
using namespace std;

const unsigned PRIME_BASE = 257;
const unsigned PRIME_MOD = 1000000007;

unsigned hash(const string& s)
{
    long long ret = 0;
    for (int i = 0; i < s.size(); i++)
    {
        ret = ret*PRIME_BASE + s[i];
        ret %= PRIME_MOD; //don't overflow
    }
    return ret;
}

int rabin_karp(const string& needle, const string& haystack)
{
    //I'm using long longs to avoid overflow
    long long hash1 = hash(needle);
    long long hash2 = 0;

    //you could use exponentiation by squaring for extra speed
    long long power = 1;
    for (int i = 0; i < needle.size(); i++)
        power = (power * PRIME_BASE) % PRIME_MOD;

    for (int i = 0; i < haystack.size(); i++)
    {
        //add the last letter
        hash2 = hash2*PRIME_BASE + haystack[i];
        hash2 %= PRIME_MOD;

        //remove the first character, if needed
        if (i >= needle.size())
        {
            hash2 -= power * haystack[i-needle.size()] % PRIME_MOD;
            if (hash2 < 0) //negative can be made positive with mod
                hash2 += PRIME_MOD;
        }

        //match?
        if (i >= needle.size()-1 && hash1 == hash2)
            return i - (needle.size()-1);
    }

    return -1;
}

int main()
{
    cout << rabin_karp("waldo", "willy werther warhol wendy --> waldo <--") << endl;
}