Recherchez efficacement les fichiers triés

J'ai un gros fichier contenant une chaîne sur chaque ligne. Je voudrais pouvoir déterminer rapidement si une chaîne est dans le fichier. Idéalement, cela se ferait en utilisant un algorithme de type binaire chop.

Certains googleurs ont révélé la lookcommande avec le -bdrapeau qui promet de localiser et de sortir toutes les chaînes commençant par un préfixe donné en utilisant un algorithme de recherche binaire. Malheureusement, cela ne semble pas fonctionner correctement et renvoie des résultats nuls pour les chaînes que je connais dans le fichier (elles sont correctement renvoyées par la greprecherche équivalente ).

Quelqu'un connaît-il un autre utilitaire ou stratégie pour rechercher ce fichier efficacement?

Il y a une différence essentielle entre grepet look:

Sauf indication contraire explicite, greptrouvera des motifs même quelque part dans les lignes. Pour lookla page de manuel déclare:

look - affiche les lignes commençant par une chaîne donnée

Je n'utilise pas looktrès souvent, mais cela a bien fonctionné sur un exemple trivial que je viens d'essayer.

Peut-être une petite réponse tardive:

Sgrep vous aidera.

Sgrep (grep trié) recherche dans les fichiers d'entrée triés les lignes qui correspondent à une clé de recherche et sort les lignes correspondantes. Lors de la recherche de fichiers volumineux, sgrep est beaucoup plus rapide que grep Unix traditionnel, mais avec des restrictions importantes.

• Tous les fichiers d'entrée doivent être triés en fichiers normaux.
• La clé de tri doit commencer au début de la ligne.
• La clé de recherche ne correspond qu'au début de la ligne.
• Aucun support d'expression régulière.

Vous pouvez télécharger la source ici: https://sourceforge.net/projects/sgrep/?source=typ_redirect

et les documents ici: http://sgrep.sourceforge.net/

Autrement:

Je ne sais pas quelle est la taille du fichier. Peut-être devriez-vous essayer en parallèle:

/programming/9066609/fastest-possible-grep

Je fais toujours du grep avec des fichiers dont la taille est> 100 Go, ça marche bien.

Vous pouvez hacher le fichier en morceaux, puis grep juste la pièce que vous vouliez:

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

alors la recherche ressemblerait à:

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

Cela fait deux choses:

1. lire et écrire des fichiers compressés. Il est généralement plus rapide de mettre la charge sur le processeur (très rapide) au lieu du disque (très lent)
2. hash afin d'obtenir une distribution à peu près égale, vous pouvez utiliser un hachage plus court ou plus long comme vous le souhaitez afin de réduire la taille de chaque pièce (mais je recommanderais d'utiliser des sous-répertoires imbriqués si vous le faites)

sgrep peut fonctionner pour vous:

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

La page du projet http://sgrep.sourceforge.net/ dit:

Sgrep utilise un algorithme de recherche binaire, qui est très rapide, mais nécessite une entrée triée.

Pour l'insertion cependant, je pense qu'il n'y a pas de meilleure solution que d'utiliser une base de données: /programming/10658380/shell-one-liner-to-add-a-line-to-a-sorted-file/ 33859372 # 33859372

Si vous le voulez vraiment rapide (O (1) rapide), vous pouvez créer un ensemble de hachage à examiner. Je ne pouvais pas trouver une implémentation qui me permettrait de stocker un ensemble de hachage pré-construit dans un fichier et de le sonder sans avoir à lire le fichier entier en mémoire, alors j'ai roulé le mien .

Construisez l'ensemble de hachage ( -b/ --build):

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

Sondez l'ensemble de hachage ( -p/ --probe):

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

… Ou avec une chaîne à rechercher sur l'entrée standard:

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

Vous pouvez désactiver la sortie de --probeavec l' option -q/ --quietsi vous êtes uniquement intéressé par l'état de sortie:

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

Pour plus d'options, voir la description d'utilisation accessible via l' option -h/ --helpou le READMEfichier d' accompagnement .