🚼 🏿 👨‍🔧 Búsqueda rápida de archivos 💛 😈 🚣🏾

De un traductor: traigo a su atención una traducción de un artículo muy antiguo publicado el 15 de enero de 1983. A pesar de una edad tan impresionante, el artículo me pareció interesante, y es posible que hoy sea útil para alguien. Por cierto, este artículo está referenciado por el tema de ayuda man localizar (1) en opennet.ru: https://www.opennet.ru/man.shtml?topic=locate .

Resumen

Este artículo describe un mecanismo de búsqueda rápida de archivos en UNIX. Combina dos métodos de compresión de datos con una nueva técnica de búsqueda de línea y está diseñado para buscar rápidamente archivos arbitrarios. El código, integrado en la utilidad de búsqueda estándar, busca en la base de datos creada previamente, actualizada diariamente. Esto lo distingue del mecanismo habitual para buscar coincidencias clave con candidatos, que se generan sobre la marcha a partir de una estructura de directorios dispersos (en disco).

La base de datos de la ruta del archivo es una lista ordenada lexicográficamente de forma incremental (a veces denominada archivo "comprimido frontal"), que también está sujeta a una codificación bigramic regular para obtener una compresión efectiva. La relación de compresión es de 5 a 6 en comparación con la representación ASCII habitual. La lista se escanea utilizando una búsqueda lineal modificada, especialmente adaptada para la codificación incremental, mientras que el tiempo típico empleado por el algoritmo es 40-50% menos que una búsqueda normal.

Introducción

Encontrar archivos en un sistema informático o red informática es un proceso complejo. Los usuarios de UNIX pueden implementarlo de varias maneras, desde manipular los comandos cd, ls y grep, hasta comandos especializados, como los desarrollados en Berkeley whereis y fleese, y el comando más común para encontrar Unix.

Desafortunadamente, el paño grueso y suave (de Berkeley) se limita al directorio de inicio, y donde solo puede buscar el código del sistema y la documentación ubicada en lugares estándar.

Buscar:

find / -name "*<filename>*" -print

por supuesto, puede buscar archivos arbitrarios, pero muy lentamente, porque utiliza un descenso recursivo en todo el sistema de archivos, despiadadamente disperso por todo el disco. La impaciencia nos impulsó a desarrollar una búsqueda alternativa (en relación con el método "buscar y encontrar") para buscar rutas a los archivos.

Cálculos preliminares

¿Por qué no simplemente construir una lista estática de todos los archivos en el sistema y buscar grep en él? Un sistema típico que contiene 20,000 archivos contendrá 1,000 bloques de nombres de archivos, incluso si acorta / usr a / u. Grep en nuestro sistema PDP-11/70 descargado procesa 30-40 bloques por segundo, y requerirá medio minuto para escanear. Esto no es aceptable para un comando de uso común.

Pero si hacemos un pequeño sacrificio: la incapacidad de buscar archivos con menos de un día de antigüedad, entonces esto no creará grandes problemas, ya que el que creó dicho archivo probablemente esté al alcance, o el archivo puede no estar listo todavía utilizar. Los archivos más antiguos creados por otros grupos de usuarios con diferentes convenciones de denominación de archivos son los candidatos de búsqueda más probables.

Compresión

Para acelerar el acceso a las aplicaciones, puede sugerir el uso de una búsqueda binaria o una tabla hash, pero dichos esquemas no funcionan bien para comparaciones parciales, si solo estamos interesados en una parte del nombre. La técnica de compresión de datos ordenada, conocida como codificación incremental, que se utilizó para una tarea de compresión de diccionario similar se implementa fácilmente [Morris / Thompson, 1974]. En este caso, se calcula el prefijo más largo del nombre anterior. Por ejemplo:

/usr/src
/usr/src/cmd/aardvark.c
/usr/src/cmd/armadillo.c
/usr/tmp/zoo

convertido a

0/usr/src
8/cmd/aardvark.c
14armadillo.c
5tmp/zoo

La decodificación será simple (se omiten las declaraciones de variables)

fp = fopen(COMPRESSED_FILELIST, "r");
while((count = (getc(fp) & 0177)) != EOF) {
    for(p = path + count; (*p++ = getc(fp)) < 0200; )
        ; /*overlay old path with new*/
    ungetc(*--p, fp);
    *p-- = NULL;
    if(math(path, name) == YES)
        puts(path);
}

donde matemática es una función que determina si la subcadena de nombre está contenida en la cadena de ruta .

De hecho, dado que la lista codificada es aproximadamente cinco veces más corta que la no codificada, y la decodificación es muy simple, el programa se ejecuta de tres a cuatro veces más rápido que grep en el archivo de texto.

Aun más rápido

Este enfoque ya es útil, pero deja espacio para nuevas mejoras. (Nota: este código se usa en la utilidad find. No hay necesidad de cargar UNIX con otro comando [y página de manual] cuando podemos mejorar un programa similar existente. Afortunadamente, no hay una llamada find con dos argumentos, y podemos llenar el vacío sin adornos :

find name

Tenga en cuenta que el código anterior aún busca en la lista desempaquetada, aunque en la memoria, no en el disco. Esto se puede evitar comparando una cadena con una subcadena en la dirección opuesta. Deje que namend apunte al último carácter del nombre de la cadena y reemplace las matemáticas con:

for(s = p, cutoff = path + count; s > cutoff; s--) {
    if(*s == namend) { /*quick first char check*/
        for(p = namend - 1, q = s - 1; *p != NULL; p--, q--)
            if(*q != *p)
                break;
        if(*p == NULL) {
            puts(path);
            break;
        }
    }
}

Esto es más fácil de entender al observar tres casos. Si la subcadena está completamente a la derecha del corte , la comparación finalizará con éxito. Si se superponen, el corte se vuelve "suave" y la comparación continúa. Si la subcadena se encuentra completamente a la izquierda del límite , se revelaría una coincidencia para las líneas anteriores, lo que significa que no podemos realizar esta búsqueda. Técnicamente, el corte se puede portar a la ruta inmediatamente después de que se realiza la comparación. Esta condición se omite anteriormente.

Equipo de dos niveles

Puede evitar ralentizar la búsqueda causada por el procesamiento de los caracteres del patrón de búsqueda . Al hacerlo, procesamos la parte del nombre que no contiene metacaracteres y usamos la función recursiva más lenta amath dentro de find . Es decir,

puts(path)

se convierte

if(globchars == NO | amatch(path, name))
    puts(path);

donde globchars se establece si el nombre contiene metacaracteres. Un ejemplo de uso de un patrón de búsqueda para un comando man simple :

vtroff -man 'find '*man*'"$1"'.[1-9]

Futuras mejoras

El código de producción de la utilidad de búsqueda aumenta la relación de compresión en otro 20-25% al reemplazar las combinaciones de dos caracteres más comunes con códigos ASCII no imprimibles. ".c" y ".P" son especialmente comunes.

Otros algoritmos que implementan otras compensaciones entre el tiempo y el tamaño de los datos, como el algoritmo Huffman [Reghbati, 1981], no parecen prometedores: simplemente reemplazan el límite de rendimiento de E / S con el límite de rendimiento.

Se pueden utilizar los métodos de búsqueda sub-lineal de Boyer-Moore [Boyer, 1977] o los métodos de macromodelo [Storer / Szymanski, 1982].

En conclusión, debe tenerse en cuenta que escaneamos 19,000 nombres de archivos en unos segundos, usando 180 bloques y un código C que cabe en dos páginas.

Referencias

Boyer, RS Un algoritmo de búsqueda de cadena rápida, Commun. ACM, vol. 20, N ° 10, octubre de 1977.
Morris, R. y Thompson, K. Webster's Second on the Head of a Pin, Memo técnico inédito, Bell Laboratories, Murray Hill, NY, 1974.
Reghbati, HK Una descripción general de las técnicas de compresión de datos, Computer, vol. 14, no. 4 de abril de 1981.
Storer, JA y Szymanski, TG Compresión de datos mediante sustitución textual, J. ACM, vol. 29, no. 4 de octubre de 1982.

Búsqueda rápida de archivos