👩🏿 🍠 🍸 Pesquisa rápida de arquivos 👨🏼‍✈️ 🈴 👇🏾

De um tradutor: trago à sua atenção a tradução de um artigo muito antigo publicado em 15 de janeiro de 1983. Apesar de uma idade tão impressionante, o artigo me pareceu interessante e é possível que seja útil para alguém hoje. A propósito, este artigo é referenciado pelo tópico de ajuda do homem localizar (1) em opennet.ru: https://www.opennet.ru/man.shtml?topic=locate .

Sumário

Este artigo descreve um mecanismo de pesquisa rápida de arquivos no UNIX. Ele combina dois métodos de compactação de dados com uma nova técnica de pesquisa de linha e foi projetado para pesquisar rapidamente arquivos arbitrários. O código, integrado ao utilitário de localização padrão, pesquisa o banco de dados criado anteriormente, atualizado diariamente. Isso o diferencia do mecanismo usual de pesquisa de correspondências de chaves com candidatos, que são gerados em tempo real a partir de uma estrutura de diretório dispersa (em disco).

O banco de dados do caminho do arquivo é uma lista lexicograficamente codificada incrementalmente (às vezes chamada de arquivo "compactado pela frente"), que também é sujeita à codificação bigramática regular para obter uma compactação efetiva. A taxa de compressão é de 5 a 6 em comparação com a representação ASCII usual. A lista é examinada usando uma pesquisa linear modificada, especialmente adaptada para codificação incremental, enquanto o tempo típico gasto pelo algoritmo é 40-50% menor que uma pesquisa regular.

Introdução

Encontrar arquivos em um sistema de computador ou rede de computadores é um processo complexo. Os usuários do UNIX podem implementá-lo de várias maneiras, desde a manipulação dos comandos cd, ls e grep, a comandos especializados, como os desenvolvidos em Berkeley whereis e fleese, e até o comando find Unix mais comum.

Infelizmente, o velo (de Berkeley) é limitado ao diretório inicial e onde é possível pesquisar apenas o código e a documentação do sistema localizados em locais padrão.

Procurar:

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

é claro, ele pode procurar arquivos arbitrários, mas muito lentamente, porque usa uma descida recursiva em todo o sistema de arquivos, implacavelmente espalhada por todo o disco. A impaciência nos levou a desenvolver uma alternativa (em relação ao método "pesquisar e encontrar") para encontrar caminhos para os arquivos.

Cálculos preliminares

Por que não apenas criar uma lista estática de todos os arquivos no sistema e procurar grep? Um sistema típico contendo 20.000 arquivos conterá 1.000 blocos de nomes de arquivos, mesmo que você reduza / usr para / u. O Grep em nosso sistema PDP-11/70 descarregado processa 30 a 40 blocos por segundo e precisará de meio minuto para digitalizar. Isso não é aceitável para um comando comumente usado.

Mas se fizermos um pequeno sacrifício - a incapacidade de procurar arquivos com menos de um dia, isso não criará grandes problemas, pois quem criou um arquivo provavelmente está ao seu alcance ou o arquivo pode ainda não estar pronto. usar. Os arquivos mais antigos criados por outros grupos de usuários com diferentes convenções de nomenclatura de arquivos são os candidatos mais prováveis.

Compressão

Para acelerar o acesso a aplicativos, você pode sugerir o uso de uma pesquisa binária ou uma tabela de hash, mas esses esquemas não funcionam bem para comparações parciais, se estivermos interessados apenas em uma parte do nome. A técnica de compactação de dados ordenada, conhecida como codificação incremental, usada para uma tarefa semelhante de compactação de dicionário é facilmente implementada [Morris / Thompson, 1974]. Nesse caso, o prefixo mais longo do nome anterior é calculado. Por exemplo:

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

convertido para

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

A decodificação será simples (declarações variáveis omitidas)

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

onde math é uma função que determina se a subcadeia de nomes está contida na cadeia de caminho .

De fato, como a lista codificada é cerca de cinco vezes menor que a não codificada e a decodificação é muito simples, o programa é executado três a quatro vezes mais rápido que o grep no arquivo de texto.

Ainda mais rápido

Essa abordagem já é útil, mas deixa espaço para novas melhorias. (Nota: esse código é usado no utilitário find. Não há necessidade de sobrecarregar o UNIX com outro comando [e página de manual] quando podemos melhorar um programa similar existente. Felizmente, não há chamada de busca com dois argumentos e podemos preencher o vazio sem embelezamento :

find name

Observe que o código acima ainda pesquisa a lista descompactada, embora na memória, não no disco. Isso pode ser evitado comparando uma string com uma substring na direção oposta. Deixe namend apontar para o último caractere do nome da string e substitua math por:

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

É mais fácil entender isso analisando três casos. Se a substring estiver totalmente à direita do ponto de corte , a comparação será finalizada com êxito. Se eles se sobrepuserem, o ponto de corte se tornará "suave" e a comparação continuará. Se a substring estiver completamente à esquerda do ponto de corte , uma correspondência será revelada para as linhas anteriores, o que significa que não podemos realizar esta pesquisa! Tecnicamente, o ponto de corte pode ser portado para o caminho imediatamente após a comparação. Esta condição é omitida acima.

Equipamento de dois níveis

Você pode evitar a desaceleração da pesquisa causada pelo processamento de caracteres do padrão de pesquisa . Ao fazer isso, processamos a parte do nome que não contém metacaracteres e usamos a função recursiva mais lenta no interior de find . Ou seja,

puts(path)

torna-se

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

onde globchars é definido se o nome contiver metacaracteres. Um exemplo de uso de um padrão de pesquisa para um comando man simples :

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

Outras melhorias

O código de produção do utilitário find aumenta a taxa de compactação em outros 20 a 25%, substituindo as combinações de dois caracteres mais comuns por códigos ASCII não imprimíveis. ".c" e ".P" são especialmente comuns.

Outros algoritmos que implementam outras compensações entre tempo e tamanho dos dados, como o algoritmo de Huffman [Reghbati, 1981], não parecem promissores: eles apenas substituem o limite de desempenho de E / S pelo limite de desempenho.

Podem ser utilizados métodos de busca sub-lineares de Boyer-Moore [Boyer, 1977] ou métodos de macro-modelo [Storer / Szymanski, 1982].

Concluindo, deve-se notar que verificamos 19.000 nomes de arquivos em alguns segundos, usando 180 blocos e um código C que cabe em duas páginas.

Referências

Boyer, RS Um algoritmo de busca rápida de cadeias, Commun. ACM, vol. 20, nº 10, outubro de 1977.
Morris, R. e Thompson, segundo de K. Webster na cabeça de um alfinete, memorando técnico não publicado, Bell Laboratories, Murray Hill, NY, 1974.
Reghbati, HK An Overview of Data Compression Techinques, Computer, vol. 14, não. 4, abril de 1981.
Storer, JA e Szymanski, TG Data Compression via Textual Substitution, J. ACM, vol. 29, No. 4 de outubro de 1982.

Pesquisa rápida de arquivos