cClaude.rocks ☕ Le blog

[Nouvelles technologies, sciences et coups de gueule…]

Menu

Contexte

La recherche de doublons est un besoin assez fréquent, l’implémentation en bash n’est pas nécessairement simple.

Je vous propose une solution très simple à mettre en œuvre utilisant jq.



Exemples

Pour rechercher une valeur en double, il faut mémoriser cette valeur qu’on appellera la clé et garder il faut également mémoriser un identificateur correspondant à cette valeur.

De manière générale, vous devrez donc prévoir du code pour construire la valeur de la clé et un mécanisme pour construire l’identificateur.

Cas d’un fichier texte

Supposons un fichier texte dans lequel on souhaite retrouver les lignes en doubles, sans changer l’ordre du fichier.

Dans ce cas la valeur à mémoriser est le contenu de la ligne (ce sera notre clé) et l’identificateur sera, par exemple, le numéro de la ligne.

Il sera possible, par exemple, de supprimer les dernières lignes en double, sans pour autant changer l’ordre du fichier.

Cas de fichiers sur le disque

Si on souhaite rechercher des fichiers ayant le même contenu dans une arborescence donnée, la clé devient le contenu du fichier, comme cela n’est pas acceptable (trop de mémoire et trop lent), on passe par un calcul de hachage, par exemple à l’aide de sha512sum et, dans ce cas, l’identificateur sera le nom du fichier.



L’algorithme

Initialisation

L’initialisation est à faire une seule fois au début du traitement. On va utiliser une variable globale pour répondre au cas général.

declare -g _entries_json_='{}'

Il s’agit ici de construire un objet JSON vide.

Itération

_key_=…Le truc potentiellement en double…
_id_=…Un truc permettant d’identifier les doubles…
_entries_json_="$(
  jq -c --arg key "${_key_}" --arg id "${_id_}" '.[$key] |= .+ [ $id ]' <<<"${_entries_json_}"
  )"

Attention, la clé doit est une chaîne de caractère raisonnable : en particulier, elle ne doit pas être trop longue.

Résultat

Une fois toutes les valeurs stockées dans la structure JSON, on supprime toutes les entrées qui n’ont pas de double :

_resultat_="$(
  jq '[ to_entries[] | select( .value | length >1 ) ] | from_entries' <<<"${_entries_json_}"
  )"

Et pour détecter s’il y a des doubles, il suffit regarder le nombre d’entrées, par exemple :

if [ -n "$( jq -r 'to_entries[] | length' <<<"${_resultat_}" )" ] ; then
  echo 'Les doubles:'
  jq '.' <<<"${_resultat_}"
else
  echo 'Pas de double'
fi

Exemple de code concret

La bibliothèque:

function init_duplicate {
  declare -g _entries_json_='{}'
}

function add_for_duplicate {
  local -r _key_="$1"
  local -r _id_="$2"

  _entries_json_="$(
    jq -c --arg key "${_key_}" --arg id "${_id_}" '.[$key] |= .+ [ $id ]' <<<"${_entries_json_}"
    )"
}

function finalize_duplicate {
  _entries_json_="$(
    jq '[ to_entries[] | select( .value | length >1 ) ] | from_entries' <<<"${_entries_json_}"
    )"
}

Imaginons le code suivant :

init_duplicate

add_for_duplicate 'k1' 'v1-1'
add_for_duplicate 'k1' 'v1-2'
add_for_duplicate 'k2' 'v1-2'
add_for_duplicate 'k2' 'v2-2'
add_for_duplicate 'k3' 'v3-1'

jq '.' <<<"${_entries_json_}"

Le résultat intermédiaire sera :

{
  "k1": [ "v1-1", "v1-2" ],
  "k2": [ "v2-1", "v2-2" ],
  "k3": [ "v3-1" ]
}

Ensuite pour obtenir que les doubles, on peut faire :

finalize_duplicate

jq '.' <<<"${_entries_json_}"

Et voilà :

{
  "k1": [ "v1-1", "v1-2" ],
  "k2": [ "v1-2", "v2-2" ]
}


Utilisation de la mémoire

Cette solution est assez gourmande en mémoire et en CPU, mais il est très facile de l’adapter et de stocker le résultat dans un fichier (au détriment du temps d’exécution, bien évidement).

Le principal intérêt de cette solution étant qu’elle est assez générique et s’adapte à presque tous les cas.



Références

ᦿ


ℹ 2006 - 2022 | 🏠 Accueil du domaine | 🏡 Accueil du blog