Optimisation de la recherche MySQL à l'aide de caractères similaires et génériques

Quelle est la longueur de vos cordes ?

S'ils sont relativement courts (par exemple, des mots anglais ; avg_len=5) et que vous avez suffisamment d'espace de stockage dans la base de données, essayez cette approche :

• Pour chaque mot que vous souhaitez stocker dans le tableau, prenez à la place tous les suffixes possibles de ce mot. En d'autres termes, vous continuez à supprimer le premier caractère jusqu'à ce qu'il ne reste plus rien. Par exemple, le mot value donne :
  • value
  • alue
  • lue
  • ue
  • e
• Stocker chaque de ces suffixes dans la base de données.
• Vous pouvez désormais rechercher des sous-chaînes en utilisant LIKE 'alu%' (qui trouvera 'alu' dans le cadre de 'value').

En stockant tous les suffixes, vous avez supprimé le besoin du caractère générique de tête (ce qui permet d'utiliser un index pour une recherche rapide), au détriment de l'espace de stockage.

Coût de stockage

Le nombre de caractères requis pour stocker un mot devient word_len*word_len / 2 , c'est-à-dire quadratique dans la longueur du mot, mot par mot. Voici le facteur d'augmentation pour différentes tailles de mots :

• Mot de 3 lettres :(3*3/2) / 3 = 1.5
• Mot de 5 lettres :(5*5/2) / 5 = 2.5
• Mot de 7 lettres :(7*7/2) / 7 = 3.5
• Mot de 12 lettres :(12*12/2) / 12 = 6

Le nombre de lignes nécessaires pour stocker un mot passe de 1 à word_len . Soyez conscient de cette surcharge. Les colonnes supplémentaires doivent être réduites au minimum pour éviter de stocker de grandes quantités de données redondantes. Par exemple, un numéro de page sur lequel le mot a été trouvé à l'origine devrait convenir (pensez à un petit entier non signé), mais des métadonnées détaillées sur le mot devraient être stockées dans une table séparée par mot, plutôt que pour chaque suffixe.

Considérations

Il y a un compromis dans l'endroit où nous divisons les « mots » (ou fragments). À titre d'exemple concret :que faisons-nous des traits d'union ? Stockons-nous l'adjectif five-letter en un mot ou deux ?

Le compromis est le suivant :

• Tout ce qui est décomposé ne peut pas être trouvé en tant qu'élément unique. Si nous stockons five et letter séparément, en recherchant five-letter ou five-letter échouera.
• Tout ce qui n'est pas cassé prendra plus d'espace de stockage. N'oubliez pas que l'exigence de stockage augmente de manière quadratique dans la longueur du mot.

Pour plus de commodité, vous pouvez supprimer le trait d'union et stocker five-letter . Le mot peut maintenant être trouvé en recherchant five , letter , et five-letter . (Si vous supprimez également les traits d'union de toute requête de recherche, les utilisateurs peuvent toujours trouver avec succès five-letter .)

Enfin, il existe des moyens de stocker des tableaux de suffixes qui n'entraînent pas beaucoup de surcharge, mais je ne suis pas encore sûr qu'ils se traduisent bien dans les bases de données.