🈹 🏖️ 🦁 Algorithme de recherche floue TextRadar. Artefacts (partie 2) 👩🏿‍🤝‍👩🏾 🤸🏾 👨🏼‍🌾

Dans une publication précédente, l' algorithme de recherche floue TextRadar. Les principales approches (partie 1) sont considérées comme les principales approches. Lors de la résolution de problèmes pratiques, des situations ont été identifiées où l'utilisation de la seule méthodologie de base ne fournit pas la qualité requise de la recherche. En conséquence, des modules complémentaires (options d'algorithme) ont été créés, qui seront discutés.

Les fragments d'un mot d'une chaîne de recherche sont situés dans plusieurs mots d'une chaîne de données

Soit la chaîne de recherche ABCD et la chaîne de données ABCE DFG.

L'application de l'algorithme de base donnera le résultat suivant:

Lorsque de telles collisions se produisent, des groupes supplémentaires sont supprimés. Le choix des groupes à supprimer est une question distincte et complexe. En conséquence, les groupes les plus importants devraient rester. Dans le cas de l'exemple ci-dessus, la réponse est évidente - le plus petit des groupes doit être supprimé.

Le fragment de début du mot de chaîne de recherche se trouve à l'intérieur du mot de chaîne de données

Prenons l'exemple de la recherche de la chaîne ABC dans la chaîne XYZAB.

L'algorithme de base produira ce qui suit:

En règle générale, un tel résultat n'a aucune valeur pratique et doit être rejeté.

Couverture insuffisante d'un mot dans une ligne de données avec des fragments trouvés

Si nous recherchons dans la ligne ABCDEF le mot ABXYZ,

nous obtenons:

Ce résultat est également sans valeur et doit être rejeté.

Overgroups

Étant donné la chaîne de recherche ABCXEF et la chaîne de données ABCEF ABCDEF.

Du point de vue de l'algorithme de base, les deux mots de la chaîne de données sont équivalents, mais le premier d'entre eux aura la priorité (si, ceteris paribus, le premier mot rencontré est sélectionné), puis le résultat de la recherche sera le suivant:

Si nous introduisons le concept d'un supergroupe comme une union de groupes de mots situés sur la même diagonale (ou décalage, voir la publication précédente, qui discute les bases de l'algorithme) et augmentons la priorité des groupes inclus dans le supergroupe à travers le paramètre la taille du supergroupe calculée pour chaque groupe et supposons que si le groupe ne fait pas partie du supergroupe, alors la taille du supergroupe pour lui sera égale à la taille du groupe lui-même - pour notre exemple, nous obtenons le résultat suivant:

Mots longs surestimés

Lors de la recherche d'une phrase contenant un mot long et court, les fragments trouvés d'un mot long peuvent «obscurcir» les fragments d'un mot court. Cela est dû à l'utilisation d'une fonction quadratique dans le calcul du coefficient de pertinence.

De plus, du point de vue de la qualité de la recherche, un mot plus long n'est pas toujours plus significatif.

Prenons un exemple. Supposons que vous ayez besoin de trouver la ligne ABCDEFG XYZ dans un texte composé de deux pages:

1. ABCDEFG ... QWE

2. ABCDEFO ... XYZ

Le numérateur du coefficient de composition du groupe (le dénominateur n'a pas d'effet qualitatif sur le résultat, voir la formule ci-dessus) pour la première page est 49, pour la seconde - 36 + 9 = 45. Autrement dit, si nous omettons l'influence sur le résultat du facteur de longueur, le résultat de la recherche sur la première page sera d'une plus grande pertinence, ce qui ne répond pas aux attentes - dans certains cas, le résultat de la recherche à la page 2 sera plus précieux.

Une des solutions peut être d' introduire des restrictions sur la longueur maximale des groupes . Dans notre exemple, si la longueur maximale du groupe est limitée à 6, par exemple, nous obtenons 36 pour la première page et 45 pour la seconde, ce qui fournira le résultat attendu - la pertinence de la deuxième page sera plus élevée que la première.

Une autre façon de résoudre le problème de l'incohérence de la signification des mots de l'expression de recherche dans le résultat global de leur longueur est de calculer la pertinence de l'expression de recherche comme la moyenne de la pertinence des mots qu'elle contient , calculée indépendamment. Mais ici se pose le problème inverse - la nécessité de réduire la signification des mots courts, qui peut être résolu de manière similaire - en fixant la valeur seuil à la longueur des mots impliqués dans la formation de la pertinence globale, mais déjà à la valeur minimale.

Répétitions répétées des fragments souhaités

Comme il ressort de l'instruction, la tâche consiste à rechercher la chaîne de recherche la plus pertinente pour un ensemble de fragments, par conséquent le fait de la répétition répétée des fragments souhaités dans le texte n'affecte pas le résultat - le premier fragment approprié sera utilisé comme résultat de la recherche, le reste sera ignoré pendant le traitement. Prenons un exemple de recherche de la chaîne ABC dans la chaîne ABCD ABCE ABCF ABCG.

L'application de l'algorithme de base donnera le résultat suivant:

Du point de vue de la recherche de la page la plus pertinente, c'est correct, mais lors de la formation d'une présentation détaillée des résultats de la recherche, il est nécessaire de rechercher et de sélectionner tous les fragments appropriés. Pour ce faire, vous pouvez utiliser plusieurs répétitions de la procédure de recherche sur la page affichée avec un arrêt séquentiel des fragments trouvés dans les itérations précédentes. Dans notre exemple, cela nous permettra de trouver toutes les occurrences appropriées de la chaîne souhaitée.

Vitesse de traitement des données

Le traitement des données à la volée a certaines exigences de vitesse - la recherche ne devrait pas prendre trop de temps.

Limitation de la taille minimale des groupes traités, désactivation des options de recherche

Pour augmenter la vitesse de recherche, vous pouvez limiter la longueur minimale des groupes traités.

En pratique, l'approche suivante est appliquée - d'abord la première passe «approximative» est effectuée avec une restriction sur la taille minimale du groupe et la désactivation de certaines options de l'ensemble du tableau de données de recherche et l'identification de la première partie de données (la taille de la partie de données optimale est déterminée à partir du contexte du problème résolu), puis la seconde, plus approfondie. en contournant uniquement les pages de cette partie, déjà sans limitation sur la taille des groupes et avec l'inclusion de toutes les options nécessaires.

Traitement parallèle des données

Une autre façon d'augmenter la vitesse de recherche est le traitement parallèle des données. En conséquence, avec une grande base de données de recherche, un temps de traitement total acceptable peut être atteint en augmentant le nombre de processus parallèles, ce qui nécessitera naturellement d'augmenter la capacité de l'équipement.

résultats

L'application des approches décrites nous a permis d'améliorer considérablement la qualité de la recherche, de réduire la dépendance de ses résultats à divers types de fautes de frappe - caractères superflus, manquants, permutations, etc., et, plus important encore, peu importe où ces fautes de frappe sont situées - dans la barre de recherche elle-même ou dans le texte, qui est recherché.

Les résultats de l'application des approches décrites sont visibles sur le stand de démonstration déployé sur le site textradar.ru . Sur l'exemple d'une recherche dans le texte du roman L.N. «Guerre et paix» de Tolstoï peut comparer les résultats de recherche en utilisant les versions de base et avancées de l'algorithme.

Téléchargez ou regardez le projet de démonstration avec des fonctionnalités avancées (C # ASP.NET MVC) ici .

Algorithme de recherche floue TextRadar. Artefacts (partie 2)