Salut à tous et à toutes,
J’ai un fichier qui contient environ 40.000 entrées, chacune contenant quelques sous-entrées. Je voudrais pouvoir comparer l’information des entrées une à une, ce qui fait un nombre de comparaisons important.
Quelle est la manière la plus rapide de le faire selon vous ? J’ai un dictionnaire/un fichier json pour l’instant, mais je ne sais pas si c’est le plus efficace…
Matthias
Qu’est-ce que tu appelles « comparer l’information des entrées une à une » ?
Quelle est l’opération que tu veux faire en fait ? Parce qu’il y a plusieurs opérations faisables sur des bases de données :
Et du coup, selon ce que tu veux faire, la façon optimale de stocker les données variera.
Coucou,
Je rejoins Simon sur ce coup, le plus simple serait un exemple avec deux entrées et sous-entrées et montrer ce que tu souhaites faire dessus. Pour l’instant, le format de stockage n’est pas très important, ce qui est important c’est les opérations que tu souhaites faire dessus !
Rémy
Salut !
Effectivement ma question n’est pas forcément très bien posée.
Pour l’instant j’ai une structure de données qui prend la forme suivante:
"CAT_000100_e3": {
"desc": "L. a. s., 1869, 1 p. in-8. 3",
"number_of_pages": "1",
"date": "1869",
"price": "3"
},
"CAT_000100_e4": {
"desc": "L. a. s., 1820, 1 p. 1/2 in 4. 5",
"number_of_pages": "1.5",
"date": "1820",
"price": "5"
}
Chaque entrée correspond à un document dans un catalogue de vente.
Certains items peuvent être reconciliés: le même document peut être vendu plusieurs fois, sur 10 ans par exemple. Il aura donc des attributs proches, si ce n’est similaires. C’est donc l’information de ces sous-entrées qui m’intéresse.
Nous avons quelques idées sur comment arriver à déterminer quels items sont identiques; ce que je voudrais savoir, c’est quelle est la méthode la plus efficace pour arriver à cette réconciliation (mon présupposé est qu’il va falloir comparer chaque entrée une à une, et que ça peut être très long si il y a beaucoup d’entrée et que je m’y prends mal).
Merci de votre réponse !
Matthias
Salut,
c’est en effet plus clair, et c’est intéressant comme problème. J’ai pas de bonne réponse à ça, vu que je ne m’y connais pas beaucoup.
Quelques remarques qui peuvent être intéressantes, je pense:
J’ai l’impression que les données sont assez structurées, avec des nombres, des dates, des choses dont on pourrait modifier le type (plutôt qu’avoir une chaîne de caractères) pour les rendre comparables entre elles plus facilement. Petit exemple: entre « 1921 », « 1821 » et « 1822 », on a une distance de un caractère entre chaque élément et le suivant, pourtant, « 1821 » ça serait à classer plus proche de « 1822 » si c’est une date. Je pense donc qu’il faudrait pré-traiter les données dans la mesure du possible (convertir les chaines de caractères qui représentent des nombres en entiers ou flottants, convertir les chaines de caractères qui représentent des dates en objets dates).
Je ne pense pas qu’il faille comparer les entrées une à une, mais plutôt les sous-entrées. Une idée pourrait être de faire des clusters de sous-entrées semblables (et donc obtenir des sortes de classes d’équivalence), clusters qui référenceraient quelles entrées sont rattachées aux valeurs contenues dans le cluster, et ensuite de comparer uniquement les entrées avec celles qui possèdent une sous-entrée contenue dans un cluster commun (je sais pas si c’est très clair, je peux faire un dessin)
C’est uniquement quelques pistes.
Oui, je vais effectivement transformer mes chaînes de caractères en entiers ou en flottants, c’est un travail en cours. Merci pour les dates, je n’y avais pas pensé.
Je vais bien nettoyer les données; je crois avoir compris ce que tu me dis ensuite mais il faut que j’y réfléchisse.
Merci encore
Matthias
Bonjour,
Si j’ai bien compris tu cherches à retrouver des documents avec des champs similaires.
Mon idée rejoint l’idée de cluster de Rémy. Si tu peux définir une distance entre deux entités (par exemple, le nombre de champs en commun) tu peux utiliser des arbres BK (cf. un article d’introduction ou wikipedia) pour trouver tous les champs à une distance d d’une entrée de ton dictionnaire.
Dans ton cas, tu peux probablement utiliser une combinaison de distance de Levenshtein et d’arbres BK, en effet si tu penses que des gens peuvent être similaire mais pas totalement identiques tu peux les considérer égaux si leur distance de Levenshtein est petite.
La construction de l’arbre prend du temps mais normalement c’est un coup unique, et d’après le l’article que j’ai mentionné pour trouver des nœuds à distance 2-3 on ne parcourt plus qu’environ 25% de l’arbre ce qui est nettement mieux que de parcourir tout l’arbre.
Salut,
Merci pour ta réponse.
J’ai pu avancer un peu sur la structuration de mes données. Ça ressemble à ça maintenant.
"CAT_000064_e4": {
"price": 6,
"date": null,
"number_of_pages": 1,
"format": "in-8.",
"term": "L.a.s."
},
"CAT_000064_e5": {
"price": 8,
"date": "1872",
"number_of_pages": 1,
"format": "in-18.",
"term": "L.a.s."
},
J’ai converti tant que faire se pouvait mes chaînes de caractères en entiers ou flottants, suivant les suggestions de Rémy. Si je comprends bien Paul, tu me suggères des algorithmes de comparaison de chaînes de caractères, et de travailler plus précisément sur la distance entre deux chaînes.
Les catalogues sur lesquels nous travaillons sont très standardisés, et les informations qui sont contenues dans les descriptions que je traite sont elles aussi standardisées. Par exemple,
"L. a. s., (1872), 1. p. in-18. Jolie lettre. 8"
"L. a. s., 28 janvier 1857, 1 p. in-8. 4"
On note l’abbréviation ‹ L.a.s. › pour lettre autographe signée (une lettre écrite de la main d’un auteur donné): c’est le type de document. Il n’y a qu’une dizaine de possibilités différentes pour décrire le type de document. Il me semble donc possible d’arriver à la fin à des données purement numériques, si par exemple je convertis les « l.a.s. » en une valeur numérique donnée avec un tableau de correspondance. Pareil pour le format: il n’y a qu’une dizaine de formats possibles différents (in-folio, in-4, in-6, in-8, etc), on peut réussir à attribuer une valeur numérique… In fine on aurait ce type de données:
"CAT_000064_e4": {
"price": 6,
"date": null,
"number_of_pages": 1,
"format": 2,
"term": 1
},
"CAT_000064_e5": {
"price": 8,
"date": "1872",
"number_of_pages": 1,
"format": 5,
"term": 1
},
J’ai l’intuition (corrigez moi si je me trompe) qu’il serait beaucoup plus efficace de comparer des nombres, non ?
A priori, on ne cherche que des correspondances exactes: si on considère qu’il n’y a pas d’erreur dans les données, un même document ne peut logiquement pas changer de format d’une vente à l’autre, ni de date, ni de type; son prix peut éventuellement évoluer, mais dans l’intervalle qui nous intéresse, les prix ont peu varié; à la limite, il pourrait changer de nombre de page, si un document est coupé en deux (mais on considèrera dans un premier temps que ce n’est pas le cas). Il faut que je voie comment gérer les dates, mais a priori c’est moins important car pour le résultat attendu pour la comparaison des dates est une égalité ou une inégalité (si deux entrées ont des dates différentes, ce sont des documents différents), donc une comparaison de chaîne de caractère peut suffire.
Qu’est-ce que vous en pensez ?
Merci beaucoup
Matthias
Bon, j’avance au moins du point de vue technique.
J’ai commencé par essayer de créer des groupes par sous-ensemble (prix, format, etc). Ça marche relativement bien.
Pour le prix, j’arrive à quelque chose du style:
{"3.5": [
"CAT_000058_e91",
"CAT_000021_e4389",
"CAT_000082_e106",
"CAT_000050_e2"
],
"5.50": [
"CAT_000020_e4091",
"CAT_000020_e4289",
"CAT_000081_e127",
"CAT_000123_e47",
"CAT_000123_e242",
"CAT_000123_e243",
"CAT_000123_e276",
"CAT_000123_e277",
"CAT_000123_e287",
"CAT_000123_e305",
"CAT_000123_e336"
]
}
Et pour le nombre de pages:
{"9.5": [
"CAT_000147_e134",
"CAT_000154_e1",
"CAT_000149_e188"
],
"9.25": [
"CAT_000118_e243",
"CAT_000106_e27"
]
}
Etc. J’ai ainsi mes groupes, qu’il faut comparer pour déterminer si on peut retrouver des ensembles qui se répètent. J’ai l’intuition qu’en superposant des listes, on devrait pouvoir faire quelque chose.
Deux questions: est-ce que je suis totalement à l’ouest (1), et (2), pensez-vous que cette méthode est meilleure qu’une méthode de pure itération ?
Je suppose que cette méthode fonctionne, mais elle me semble très lourde à mettre en place sur autant de données: 40.000 (au carré donc); ceci dit je ne sais pas si pour un informaticien, c’est un large volume de données ou non…
Le papier: https://hcommons.org/deposits/objects/hc:31906/datastreams/CONTENT/content
J’ai décidé de simplifier le travail en opérant un filtrage des entrées en amont (au lieu de tout comparer, on va comparer avec un auteur donné).
Je ne désespère pas de trouver une solution au problème (mal) posé ici !
Merci à vous (vous êtes dans les remerciements),
Matthias