Linux Fu: rouler avec les sommes de contrôle

Nous sommes souvent frappés par la fréquence à laquelle nous passons du temps à essayer d’optimiser quelque chose alors qu’il serait préférable de choisir un meilleur algorithme. Il y a la vieille histoire du mathématicien Gauss qui, lorsqu’il était à l’école, était chargé d’additionner les nombres entiers de 1 à 100. Tandis que les autres élèves ajoutaient laborieusement chaque nombre, Gauss s’est rendu compte que 100 + 1 est 101 et 99 + 2 est aussi 101. Devinez ce que 98 + 3 est ? Bien sûr, 101. Vous pouvez donc facilement trouver qu’il y a 50 paires qui totalisent 101 et savoir que la réponse est 5 050. Peu importe la vitesse à laquelle vous pouvez ajouter, vous n’êtes pas susceptible de battre quelqu’un qui connaît cet algorithme. Alors voici une question : vous avez un grand corps de texte et vous voulez le rechercher. Quel est le meilleur moyen ?

Bien sûr, c’est une question chargée. Le meilleur peut signifier beaucoup de choses et dépendra du type de données que vous traitez et même du type de machine que vous utilisez. Si vous recherchez simplement une chaîne, vous pouvez bien sûr utiliser l’algorithme de force brute. Disons que nous recherchons le mot « condamné » dans le texte de Guerre et Paix :

  1. Commencer par la première lettre de Guerre et Paix
  2. Si la lettre actuelle n’est pas la même que la lettre actuelle de « condamné », passez à la lettre suivante, réinitialisez la lettre actuelle dans « condamné » et revenez à l’étape 2 jusqu’à ce qu’il n’y ait plus de lettres.
  3. Si les lettres actuelles sont les mêmes, passez à la lettre suivante du forçat et, sans oublier la lettre actuelle du texte, comparez-la à la lettre suivante. Si c’est la même chose, répétez cette étape jusqu’à ce qu’il n’y ait plus de lettres dans « convict » (à quel point vous avez une correspondance). Si ce n’est pas la même chose, réinitialisez la lettre actuelle de « convict » et revenez également à la lettre actuelle d’origine du texte, puis passez à la lettre suivante, en revenant à l’étape 2.

C’est en fait difficile à décrire en anglais. Mais, en d’autres termes, comparez simplement le texte avec la chaîne de recherche, caractère par caractère jusqu’à ce que vous trouviez une correspondance. Cela fonctionne et, en fait, avec du matériel moderne, vous pouvez écrire du code rapide pour cela. Peut-on faire mieux ?

Meilleurs algorithmes

Recherche de base

Encore une fois, cela dépend vraiment de votre définition de mieux. Supposons que le texte contienne de nombreuses chaînes qui correspondent presque à ce que nous recherchons, mais pas tout à fait. Par exemple, Guerre et Paix contient probablement de nombreuses occurrences du mot « le ». Mais il y a aussi « là », « alors » et « autre » qui contiennent tous notre mot cible. Pour le mot « le », ce n’est pas un gros problème car il est court, mais que se passerait-il si vous parcouriez de grandes chaînes de recherche ? (Je ne sais pas – des données sur le génome de l’ADN ou quelque chose comme ça.) Vous passeriez beaucoup de temps à chercher des impasses. Lorsque vous découvrez que le texte actuel contient 199 des 200 caractères que vous recherchez, cela va être décevant.

Il y a un autre inconvénient. Bien qu’il soit facile de dire où la chaîne correspond et, par conséquent, où elle ne correspond pas, il est difficile de déterminer s’il y a eu juste une petite insertion ou suppression lorsqu’elle ne correspond pas. Ceci est important pour des outils comme diff et rsync où ils ne veulent pas seulement savoir ce qui correspond, ils veulent comprendre pourquoi les choses ne correspondent pas.

Il regardait rsyncen fait, cela m’a amené à voir comment rsync compare deux fichiers à l’aide d’une somme de contrôle glissante. Bien que ce ne soit pas pour toutes les applications, c’est quelque chose d’intéressant à avoir dans votre sac à malice. Évidemment, l’une des meilleures utilisations de cet algorithme de « somme de contrôle glissante » est exactement comment rsync l’utilise. C’est-à-dire qu’il trouve très rapidement quand les fichiers sont différents, mais peut également faire un travail raisonnable pour déterminer quand ils redeviennent identiques. En faisant rouler le référentiel, rsync peut détecter que quelque chose a été inséré ou supprimé et apporter les modifications appropriées à distance, économisant ainsi la bande passante du réseau.

À la recherche de

Cependant, vous pouvez utiliser la même stratégie pour gérer les recherches de texte volumineux. Pour ce faire, vous avez besoin d’un algorithme de hachage capable d’insérer et de retirer facilement des éléments. Par exemple, supposons que l’algorithme de somme de contrôle soit extrêmement simple. Ajoutez simplement les codes ASCII pour chaque lettre ensemble. Ainsi, la chaîne « AAAB » est hachée en 65 + 65 + 65 + 66 ou 261. Supposons maintenant que le caractère suivant soit un C, c’est-à-dire « AAABC ». Nous pouvons calculer la somme de contrôle à partir de la deuxième position en soustrayant le premier A (65) et en ajoutant un C (67). C’est idiot avec ce petit ensemble de données, bien sûr, mais au lieu d’ajouter des centaines de nombres chaque fois que vous voulez calculer un hachage, vous pouvez maintenant le faire avec une addition et une soustraction chacune.

Nous pouvons ensuite calculer le hachage de notre chaîne de recherche et commencer à calculer les hachages du fichier pour la même longueur. Si les codes de hachage ne correspondent pas, nous savons qu’il n’y a pas de correspondance et nous passons à autre chose. S’ils correspondent, nous devons probablement vérifier la correspondance car les hachages sont généralement inexacts. Deux chaînes peuvent avoir la même valeur de hachage.

Il y a cependant quelques problèmes avec cela. Si vous ne recherchez qu’une seule chaîne, le coût du calcul du hachage est élevé. Dans le pire des cas, vous devrez faire une comparaison, une addition et une soustraction pour chaque caractère, plus peut-être quelques tests lorsque vous avez une collision de hachage : deux chaînes avec le même hachage qui ne correspondent pas réellement. Avec le schéma normal, vous n’aurez qu’à faire un test pour chaque personnage ainsi que des tests inutiles pour les faux positifs.

Pour optimiser l’algorithme de hachage, vous pouvez faire un hachage plus sophistiqué. Mais cela coûte également plus cher à calculer, ce qui aggrave encore les frais généraux. Cependant, que se passerait-il si vous recherchiez un tas de cordes similaires, toutes de la même longueur ? Ensuite, vous pouvez calculer le hachage une fois et le sauvegarder. Chaque recherche après cela serait très rapide car vous ne perdrez pas de temps à enquêter sur de nombreuses impasses pour revenir en arrière.

Une recherche de hachage avec une collision à « le » lors de la recherche de « le »

Mon algorithme de hachage est très simple, mais pas très bon. Par exemple, vous pouvez voir dans l’exemple qu’il y a un faux positif qui entraînera une comparaison supplémentaire. Bien sûr, de meilleurs algorithmes de hachage existent, mais il y a toujours un risque de collision.

Quelle est la différence en utilisant cette stratégie de hachage ? Eh bien, j’ai décidé d’écrire un petit code pour le savoir. J’ai décidé d’ignorer le coût du calcul du hachage du modèle de recherche et de la partie initiale du hachage roulant, car ceux-ci seront mis à zéro sur suffisamment d’interactions.

Condamné

Si vous recherchez le mot « condamné » dans le texte de Guerre et Paix du Projet Gutenberg, vous constaterez qu’il n’apparaît que quatre fois sur 3,3 millions de caractères. Une recherche normale devait faire environ 4,4 millions de comparaisons pour comprendre cela. L’algorithme de hachage gagne facilement avec un peu moins de 4,3 millions. Mais le calcul de hachage le ruine. Si vous comptez l’addition et la soustraction comme le même coût que deux comparaisons, cela ajoute environ 5,8 millions de pseudo-comparaisons au total.

Est-ce typique? Il n’y a probablement pas trop de faux positifs pour « condamné ». Si vous exécutez le code avec le mot « le » qui devrait avoir beaucoup de faux résultats, l’algorithme conventionnel prend environ 4,5 millions de comparaisons et le total ajusté pour l’algorithme de hachage est d’environ 9,6 millions. Ainsi, vous pouvez voir comment les faux positifs affectent l’algorithme normal.

Vous remarquerez que mon algorithme de hachage terne entraîne également un grand nombre de faux positifs de hachage qui érodent certains des avantages. Un algorithme plus complexe aiderait, mais coûterait également des calculs initiaux, de sorte qu’il n’aide pas autant que vous ne le pensez. Presque tout algorithme de hachage pour une chaîne arbitraire aura des collisions. Bien sûr, pour les petites chaînes de recherche, le hachage pourrait être la chaîne de recherche et ce serait parfait, mais ce n’est pas faisable dans le cas général.

Le code n’enregistre pas les hachages, mais supposons qu’il l’ait fait et que le taux de faux positifs de la première recherche soit dans la moyenne. Cela signifie que nous économisons un peu plus de 100 000 comparaisons par recherche une fois les hachages précalculés. Ainsi, une fois que vous devez rechercher une soixantaine de chaînes, vous vous équilibrez. Si vous recherchez 600 chaînes – mais n’oubliez pas qu’elles doivent toutes avoir la même taille – vous pouvez économiser un peu sur le code de comparaison facile.

Je n’ai pas chronométré les choses, car je ne voulais pas optimiser chaque bit de code. En général, moins d’opérations vaudra mieux que plus d’opérations. Il existe de nombreuses façons d’augmenter l’efficacité du code et également certaines heuristiques que vous pouvez appliquer si vous analysez un peu la chaîne de recherche. Mais je voulais juste vérifier mon intuition pour savoir combien chaque algorithme a dépensé pour rechercher le texte.

Reflets

J’ai d’abord commencé à y penser après avoir lu le code de rsync et le programme de sauvegarde kup. Il s’avère qu’il existe un nom pour cela, l’algorithme de Rabin-Karp. Il existe de meilleures fonctions de hachage qui peuvent réduire les faux positifs et obtenir quelques points d’efficacité supplémentaires.

Quel est mon point? Je ne dis pas qu’une recherche RK est votre meilleure approche pour les choses. Vous avez vraiment besoin d’un ensemble de données volumineux avec de nombreuses recherches de taille fixe pour en tirer un avantage. Si vous pensez à quelque chose comme rsync, il utilise en fait les hachages pour rechercher des endroits où deux très longues chaînes pourraient être égales. Mais je pense qu’il y a des cas où ces algorithmes bizarres pourraient avoir un sens, il vaut donc la peine de les connaître. Il est également amusant de défier votre intuition en écrivant un peu de code et en obtenant des estimations de la qualité d’un algorithme par rapport à un autre.