Algorithme assortie rangée rangée rabin carpe

J'ai vu cet algorithme pour faire des lignes de carpes rabin sur les forums sur le site Web et je suis intéressé à essayer de le réaliser, mais je me demandais si quelqu'un me dise pourquoi les variables ulong Q et ulong D égal 100007 et 256 respectivement :S?
Quelle valeur ces valeurs ont-elles?


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!"/;
}
Invité:

Gaspard

Confirmation de:

Quant aux nombres magiques, la réponse de l'étage est plutôt claire.

Quant au code, l'idée principale de rabin carpe est de comparer hash Entre la partie coulissante de la ligne et le gabarit.

hash ne peut pas être calculé à chaque fois sur des substrats entiers, sinon la complexité de calcul serait quadratique
O/n^2/

Au lieu de linéaire
O/n/

.

Par conséquent, il est appliqué
http://en.wikipedia.org/wiki/Rolling_hash
fonction hash, Par exemple, chaque itération ne nécessite qu'un seul caractère de mettre à jour la valeur. hash Substrage.

Alors commençons votre code:


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



^

Ce fragment calcule hash Modèle
B

/
sigb

/ et code initial de code de hachage
A

La même longueur
B

.
En fait, ce n'est pas tout à fait raison, parce que hash peut faire face à 1 et donc il est nécessaire de changer 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;



^

Ici est calculé
pow

, ce qui est nécessaire pour effectuer un roulement hash.


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



^

Enfin la rangée restante /I.e. Du deuxième symbole à la fin/, La mise à jour est numérisée hash Sous-chaîne A et compare S. hash Sous-chaîne B /Il est calculé au début/.

Si deux hachages sont égaux, la sous-chaîne et le modèle sont comparés 1, Et s'ils sont vraiment égaux, le message est renvoyé.

1
http://en.wikipedia.org/wiki/C ... %2529
; Par conséquent, si deux lignes ont des significations différentes hash, elles ou ils

définitivement

différent, mais si deux hachages sont égaux, ils

peut être

être égal ou pas.

Florian

Confirmation de:

L'algorithme utilise le hachage pour comparer rapidement les chaînes. Q et d est les nombres magiques auxquels l'encodeur est probablement venu avec un peu d'échantillons et d'erreurs et donne bon
http://en.wikipedia.org/wiki/H ... _data
Valeurs hash Pour cet algorithme particulier.

Vous pouvez voir ces types de nombres magiques utilisés pour le hachage dans de nombreux endroits. Vous trouverez ci-dessous un exemple de définition de fonction décompilée. GetHashCode Type de chaîne .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;
}


Voici un autre exemple de R# Fonction de redéfinition générée GetHashcode Pour le type d'échantillon:


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

Pour répondre aux questions, connectez-vous ou registre