D'un traducteur: j'attire votre attention sur la traduction d'un très ancien article publié le 15 janvier 1983. Malgré un âge aussi impressionnant, l'article m'a paru intéressant et il est possible qu'il soit utile à quelqu'un aujourd'hui. Cet article, en passant, est référencé dans la section d'aide de man Locate (1) sur opennet.ru: https://www.opennet.ru/man.shtml?topic=locate .
Sommaire
Cet article décrit un mécanisme de recherche de fichiers rapide sous UNIX. Il combine deux méthodes de compression de données avec une nouvelle technique de recherche de ligne et est conçu pour rechercher rapidement des fichiers arbitraires. Le code, intégré à l'utilitaire de recherche standard, recherche la base de données précédemment créée, mise à jour quotidiennement. Cela le distingue du mécanisme habituel de recherche de correspondances clés avec les candidats, qui sont générées à la volée à partir d'une structure de répertoire dispersée (sur disque).La base de données des chemins d'accès aux fichiers est une liste codée de manière incrémentielle et triée lexicographiquement (parfois appelée fichier «compressé de face»), qui est également soumise à un codage bigramique régulier afin d'obtenir une compression efficace. Le taux de compression est de 5 à 6 par rapport à la représentation ASCII habituelle. La liste est analysée à l'aide d'une recherche linéaire modifiée, spécialement adaptée au codage incrémentiel, tandis que le temps typique passé par l'algorithme est de 40 à 50% inférieur à une recherche régulière.introduction
La recherche de fichiers dans un système informatique ou un réseau informatique est un processus complexe. Les utilisateurs UNIX peuvent l'implémenter de diverses manières, de la manipulation des commandes cd, ls et grep aux commandes spécialisées, telles que celles développées par Berkeley whereis et fleese, et à la commande find Unix plus courante.Malheureusement, fleece (de Berkeley) est limité au répertoire personnel, et whereis ne peut rechercher que le code système et la documentation situés dans des emplacements standard.Chercher:find / -name "*<filename>*" -print
bien sûr, il peut rechercher des fichiers arbitraires, mais très lentement, car il utilise une descente récursive dans tout le système de fichiers, impitoyablement dispersée sur le disque. L'impatience nous a incités à développer une recherche alternative (par rapport à la méthode «chercher et trouver») de chemins d'accès aux fichiers.Calculs préliminaires
Pourquoi ne pas simplement construire une liste statique de tous les fichiers du système et rechercher grep dessus? Un système typique contenant 20 000 fichiers contiendra 1 000 blocs de noms de fichiers, même si vous raccourcissez / usr en / u. Grep sur notre système PDP-11/70 non chargé traite 30 à 40 blocs par seconde, et il faudra une demi-minute pour numériser. Ce n'est pas acceptable pour une commande couramment utilisée.Mais si nous faisons un petit sacrifice - l'impossibilité de rechercher des fichiers de moins d'un jour, cela ne créera pas de gros problèmes, car celui qui a créé un tel fichier est probablement à portée de main, ou peut-être que le fichier n'est pas encore prêt utilisation. Les fichiers plus anciens créés par d'autres groupes d'utilisateurs avec différentes conventions de dénomination de fichier sont les candidats à la recherche les plus probables.Compression
Pour accélérer l'accès aux applications, vous pouvez suggérer d'utiliser une recherche binaire ou une table de hachage, mais de tels schémas ne fonctionnent pas bien pour les comparaisons partielles, si nous ne sommes intéressés que par une partie du nom. La technique de compression ordonnée des données, connue sous le nom de codage incrémental, qui a été utilisée pour une tâche de compression de dictionnaire similaire est facilement mise en œuvre [Morris / Thompson, 1974]. Dans ce cas, le préfixe le plus long du nom précédent est calculé. Par exemple:/usr/src
/usr/src/cmd/aardvark.c
/usr/src/cmd/armadillo.c
/usr/tmp/zoo
converti en0/usr/src
8/cmd/aardvark.c
14armadillo.c
5tmp/zoo
Le décodage sera simple (déclarations de variables omises)fp = fopen(COMPRESSED_FILELIST, "r");
while((count = (getc(fp) & 0177)) != EOF) {
for(p = path + count; (*p++ = getc(fp)) < 0200; )
;
ungetc(*--p, fp);
*p-- = NULL;
if(math(path, name) == YES)
puts(path);
}
où math est une fonction qui détermine si la sous-chaîne de nom est contenue dans la chaîne de chemin d'accès .En fait, comme la liste codée est environ cinq fois plus courte que la liste non codée et que le décodage est très simple, le programme s'exécute trois à quatre fois plus rapidement que grep sur le fichier texte.Même plus vite
Cette approche est déjà utile, mais laisse place à de nouvelles améliorations. (Remarque: ce code est utilisé dans l'utilitaire find. Il n'est pas nécessaire de charger UNIX avec une autre commande [et une page de manuel] lorsque nous pouvons améliorer un programme similaire existant. Heureusement, il n'y a pas d'appel find avec deux arguments, et nous pouvons remplir le vide sans embellissement :find name
Notez que le code ci-dessus recherche toujours la liste décompressée, bien qu'en mémoire, pas sur le disque. Cela peut être évité en comparant une chaîne avec une sous-chaîne dans le sens opposé. Laissez namend pointer vers le dernier caractère du nom de la chaîne et remplacez math par:for(s = p, cutoff = path + count; s > cutoff; s--) {
if(*s == namend) {
for(p = namend - 1, q = s - 1; *p != NULL; p--, q--)
if(*q != *p)
break;
if(*p == NULL) {
puts(path);
break;
}
}
}
Ceci est plus facile à comprendre en examinant trois cas. Si la sous-chaîne est complètement à droite de la coupure , la comparaison se terminera avec succès. S'ils se chevauchent, la coupure devient «douce» et la comparaison se poursuit. Si la sous-chaîne se trouve complètement à gauche de la coupure , alors une correspondance serait révélée pour les lignes précédentes, ce qui signifie que nous ne pouvons pas effectuer cette recherche! Techniquement, la coupure peut être portée sur le chemin immédiatement après la comparaison. Cette condition est omise ci-dessus.Équipement à deux niveaux
Vous pouvez éviter de ralentir la recherche provoquée par le traitement des caractères du modèle de recherche . Ce faisant, nous traitons la partie du nom qui ne contient pas de métacaractères et utilisons la fonction récursive plus lente qui se trouve dans find . C'est à dire,puts(path)
devientif(globchars == NO | amatch(path, name))
puts(path);
où globchars est défini si le nom contient des métacaractères. Un exemple d'utilisation d'un modèle de recherche pour une commande man simple :vtroff -man 'find '*man*'"$1"'.[1-9]
Améliorations supplémentaires
Le code de production de l'utilitaire find augmente le taux de compression de 20 à 25% supplémentaires en remplaçant les combinaisons de deux caractères les plus courantes par des codes ASCII non imprimables. ".c" et ".P" sont particulièrement courants.D'autres algorithmes qui implémentent d'autres compromis entre le temps et la taille des données, comme l'algorithme de Huffman [Reghbati, 1981], ne semblent pas prometteurs: ils remplacent simplement la limite de performance d'E / S par la limite de performance.Des méthodes de recherche sous-linéaire de Boyer-Moore [Boyer, 1977] ou des méthodes de macro-modèle [Storer / Szymanski, 1982] peuvent être utilisées.En conclusion, il convient de noter que nous avons scanné 19 000 noms de fichiers en quelques secondes, en utilisant 180 blocs et un code C qui tient sur deux pages.Références
Boyer, RS Un algorithme de recherche de chaîne rapide, Commun. ACM, vol. 20, no 10, octobre 1977.Morris, R. et Thompson, K. Webster's Second on the Head of a Pin, note technique non publiée, Bell Laboratories, Murray Hill, NY, 1974.Reghbati, HK An Overview of Data Compression Techinques, Computer, Vol. 14, non 4, avril 1981.Storer, JA et Szymanski, TG Data Compression via Textual Substitution, J. ACM, Vol. 29, non 4, octobre 1982.