Raya Berova (DMRG)
28 novembre 2024
1️⃣ Contexte
2️⃣ Les données
3️⃣ Méthodologie
4️⃣ Résultats obtenus
5️⃣ Structure du projet
6️⃣ Discussion
1️⃣ Contexte
2️⃣ Les données
3️⃣ Méthodologie
4️⃣ Résultats obtenus
5️⃣ Structure du projet
6️⃣ Discussion
1️⃣ Contexte
2️⃣ Les données
3️⃣ Méthodologie
4️⃣ Résultats obtenus
5️⃣ Structure du projet
6️⃣ Discussion
Table 1: Exemple de base de données
| id | nom de voie |
|---|---|
| A | du général leclerc |
| B | du général charles de gaulle |
| C | du point du jour |
| D | verdier |
| E | des cours |
Un token = un mot
Si on cherche “88 avenue du général charles de gaulle”, pour chaque nom de voie, on doit compter le nombre de : “88”, “avenue”, “du”, “général”…
C’est extrêment long
Table 2: Exemple d’index inversé
| token | occurrences |
|---|---|
| général | {“A”: 1, “B”: 1} |
| jour | {“C”: 1} |
| verdier | {“B”: 1} |
| … | … |
On a directement le comptage de chaque token par voie
Pour retourner la voie la plus pertinente, on construit un score pour chaque voie : \[ \sum_{\text{∀t} \in \text{T}} occurence_t \]
t = token
T = ensemble des tokens de l’adresse recherchée
Contourner les fautes d’orthographes : chaque token est découpé en sous-chaînes de n caractères consécutifs
Exemple : découpage en 3-grams de caractères du texte “avenue verdier”
| token | 3-grams |
|---|---|
| avenue | ave, ven, enu, nue |
| verdier | ver, erd, rdi, die, ier |
Table 3: Exemple d’index inversé 3-grams
| 3-grams | occurrences |
|---|---|
| gén | {“A”: 1, “B”: 1} |
| char | {“B”: 1} |
| our | {“C”: 1, “E”: 1} |
| … | … |
Pour retourner la voie la plus pertinente, on construit un score pour chaque voie : \[ \sum_{\text{∀ngram} \in \text{N}} occurence_{ngram} \]
N = ensemble des n-grams de l’adresse recherchée
\[ \downarrow \text{taille n-grams} \Rightarrow \text{taille index inversé} \uparrow \Rightarrow \text{temps de recherche} \uparrow \]
Limitation à minimum n=3 pour notre cas
Contourner les fautes d’orthographes d’une autre façon : fuzziness
Pour matcher deux tokens avec une fuzziness de niveau 1 = corriger l’un des tokens :
Le score global va donc combiner la somme des matchs au niveau :
Ce score prendra en compte les boosts, le n des n-grams et le niveau de fuzziness choisis au moment du paramétrage du moteur : ceci constitue la requête
On peut donner plus ou moins d’importance aux différents matchs grâce aux boosts
Chaque occurence est multipliée par un facteur choisi : boost
Exemple de boosts :
| match au niveau | boost |
|---|---|
| token | 20 |
| fuzzi 1 | 15 |
| 3-grams | 1 |
| 4-ngrams | 1 |
| 5-grams | 1 |
\[ \sum_{\text{∀dn} \in \text{N}} \sum_{\text{∀sc} \in \text{dn}} boost_{dn}*occurence_{sc} \]
N = ensemble des niveaux de découpage de l’adresse recherchée (niveau token, niveau fuzzi…) dn = découpage de l’adresse recherchée selon le niveau (boost associé) sc = sous-chaîne (un token, un 3-grams…)
1️⃣ Contexte
2️⃣ Les données
3️⃣ Méthodologie
4️⃣ Résultats obtenus
5️⃣ Structure du projet
6️⃣ Discussion
1️⃣ Contexte
2️⃣ Les données
3️⃣ Méthodologie
4️⃣ Résultats obtenus
5️⃣ Structure du projet
6️⃣ Discussion
1️⃣ Contexte
2️⃣ Les données
3️⃣ Méthodologie
4️⃣ Résultats obtenus
5️⃣ Structure du projet
6️⃣ Discussion