Procura eficientemente o arquivo ordenado

Question

Eu tenho um arquivo grande contendo uma string em cada linha. Eu gostaria de poder determinar rapidamente se uma string está no arquivo. Idealmente, isso seria feito usando um algoritmo de tipo binário.

Alguns Googling revelaram o comando look com o sinalizador -b , que promete localizar e exibir todas as strings começando com um prefixo específico usando um algoritmo de busca binária. Infelizmente, parece que não funciona corretamente e retorna resultados nulos para cadeias de caracteres que eu sei que estão no arquivo (elas são retornadas corretamente pela pesquisa grep equivalente).

Alguém sabe de outro utilitário ou estratégia para pesquisar esse arquivo com eficiência?

    

Answer 1

Há uma diferença essencial entre grep e look :

A menos que seja explicitamente indicado, grep encontrará padrões até mesmo em algum lugar dentro das linhas. Para look , a página de manque declara:

  

look - exibe linhas começando com uma determinada string

Não estou usando look com muita frequência, mas funcionou bem em um exemplo trivial que acabei de experimentar.

    

Answer 2

sgrep pode funcionar para você:

sudo apt-get install sgrep
sgrep -l '"needle"' haystack.txt

A página do projeto link diz:

  

O Sgrep usa um algoritmo de busca binária, que é muito rápido, mas requer entrada classificada.

Para inserção, no entanto, acho que não há solução melhor do que usar um banco de dados: link

    

Answer 3

Você pode transformar o arquivo em partes e depois usar a peça desejada:

for line in $(cat /usr/share/dict/american-english | tr '[:upper:]' '[:lower:]' | sort | uniq)
do
    prefix=$(echo $line | md5sum - | cut -c 1-2)
    mkdir -p $prefix
    echo $line | gzip >> $prefix/subwords
done

então a pesquisa ficaria assim:

    prefix=$(echo $word | md5sum - | cut -c 1-2)
    zgrep -m 1 -w word $prefix/subwords

Isso faz duas coisas:

1. leia e escreva arquivos compactados. Geralmente é mais rápido colocar a carga na CPU (muito rápido) em vez do disco (muito lento)
2. coisas hash para obter uma distribuição aproximadamente igual, você pode usar um hash mais curto ou mais longo, como você gostaria, a fim de reduzir o tamanho de cada peça (mas eu recomendo usar subdiretórios aninhados se você fizer)

Answer 4

Se você quiser realmente rápido (O (1) rápido) você pode construir um conjunto de hash para analisar. Não consegui encontrar uma implementação que me permitisse armazenar um conjunto de hash pré-compilado em um arquivo e sondá-lo sem ter que ler o arquivo inteiro na memória, portanto Eu rolei meu próprio .

Crie o conjunto de hash ( -b / --build ):

./hashset.py --build string-list.txt strings.pyhashset

Teste o conjunto de hash ( -p / --probe ):

./hashset.py --probe strings.pyhashset \
    'Is this string in my string list?' 'What about this one?'

… ou com string para procurar na entrada padrão:

printf '%s\n' 'Is this string in my string list?' 'What about this one?' |
./hashset.py --probe strings.pyhashset

Você pode silenciar a saída de --probe com a opção -q / --quiet se estiver interessado apenas no status de saída:

if ./hashset.py --quiet --probe strings.pyhashset ...; then
    echo 'Found'
else
    echo 'Not found'
fi

Para mais opções, consulte a descrição de uso acessível por meio da opção -h / --help ou o arquivo README acompanhante.