Dans des scénarios comme les forums et les salles de discussion, afin d'assurer l'expérience utilisateur, nous devons souvent bloquer beaucoup de mauvais mots. Pour la recherche de mots clés unique, il est naturellement plus efficace dans l'index et les méthodes régulières. Cependant, s'il existe de nombreux mots clés, si vous appelez à plusieurs reprises l'index ou les mots réguliers pour correspondre au texte intégral, la consommation de performances est très élevée. Étant donné que la chaîne cible est généralement de grande taille, il est nécessaire de s'assurer que le résultat est obtenu en une traversée. Sur la base de ces besoins, il est facile de penser aux moyens de faire correspondre chaque personnage dans tout le texte en séquence. Par exemple, pour ce texte: "Mike Jordan avait dit" juste le faire ", donc Mark a été un codeur." Si notre mot-clé est "Mike" et "Mark", vous pouvez traverser toute la phrase. Lorsque vous trouvez "M", voyez si vous pouvez faire correspondre "I" ou "A". Si vous pouvez correspondre jusqu'à la fin, vous trouverez avec succès un mot-clé, sinon vous continuerez à traverser. Ensuite, la structure des mots clés devrait être comme ceci:
Var Keywords = {m: {i: {k: {e: {end: true}}}, a: {r: {k: {end: true}}}}}À partir de ce qui précède, nous pouvons voir que ces données sont une structure d'arbre, et il est toujours longue de créer une structure d'arbre basée sur le groupe de mots clés, tandis que les mots clés sont déjà donnés, vous pouvez donc créer une telle structure de données à l'avance avant de correspondre. Le code est le suivant:
fonction buildTree (mots clés) {var tblcur = {}, key, str_key, longueur, j, i; var tblroot = tblcur; for (j = keywords.length - 1; j> = 0; j - = 1) {str_key = keywords [j]; Length = str_key.length; pour (i = 0; i <longueur; i + = 1) {key = str_key.charat (i); if (tblcur.hasownproperty (key)) {tblcur = tblcur [key]; } else {tblcur = tblcur [key] = {}; }} tblcur.end = true; // le dernier mot-clé tblcur = tblroot; } return tblroot;}Ce code utilise une instruction continue: tblcur = tblcur [key] = {}. L'ordonnance d'exécution ici est l'ordonnance d'exécution des instructions. Étant donné que le niveau de fonctionnement de [] est supérieur à =, la première chose est de créer un attribut clé dans l'objet TBLCUR. Combiné avec tblroot = tblcur = {}, l'ordre d'exécution est:
var tblroot = tblcur = {}; tblroot = tblcur; tblcur ['key'] = undefined; // maintenant tblroot = {key: undefined} tblcur ['key'] = {}; tblcur = tblcur ['key'];Grâce au code ci-dessus, les données de requête requises sont construites. Jetons un coup d'œil à la méthode d'écriture de l'interface de requête.
Pour chaque mot de la chaîne cible, nous commençons par le haut de ces mots clés. Tout d'abord, les mots clés [A]. S'il y en a, regardez le mot-clé [a] [b]. Si le dernier mot-clé [a] [b]… [x] = true, cela signifie que le match réussit. Si le mot-clé [a] [b]… [x] = non défini, la correspondance sera redémarrée à partir de la position suivante.
Fonction Search (Content) {var tblcur, p_star = 0, n = content.length, p_end, match, // s'il faut trouver un match_key, match_str, arrmatch = [], // stockage le résultat arrrlength = 0; // L'indice de longueur d'Arrmatch while (p_star <n) {tblcur = tblroot; // suivi à la racine p_end = p_star; match_str = ""; matches = false; do {match_key = content.charat (p_end); if (! (tblcur = tblcur [match_key])) {// la fin de ce match p_star + = 1; rupture } else {match_str + = match_key; } p_end + = 1; if (tblcur.end) // s'il faut correspondre à la queue {match = true; }} while (true); if (correspond) {// maximum correspond à Arrmatch [arrrlength] = {key: match_str, begin: p_star - 1, end: p_end}; Arrrlength + = 1; p_star = p_end; }} return Arrmatch;}Ce qui précède est le cœur de l'ensemble du système de correspondance des mots clés. Ici, nous utilisons très bien les fonctionnalités linguistiques de JS, et l'efficacité est très élevée. J'ai utilisé un "Soushen Ji" de 500 000 mots pour le tester et j'ai trouvé les 300 idioms donnés. L'effet de correspondance est d'environ 1 seconde. Surtout, puisque le texte cible est traversé immédiatement, la longueur du texte cible a peu d'effet sur le temps de requête. Le nombre de mots clés qui ont un impact plus important sur le temps de requête est le nombre de mots clés. Chaque mot du texte cible traverse les mots clés, il a donc un certain impact sur la requête.
Analyse simple
Je suppose que vous vous demandez quand vous lisez l'article ci-dessus. Vous pouvez traverser tous les mots clés pour chaque mot. Même si certains mots clés sont partiellement les mêmes, il est tout à fait long de les traverser complètement. Cependant, les propriétés des objets dans JS sont construites à l'aide d'une table de hachage. Les données de cette structure sont très différentes de la simple traversée du tableau, et l'efficacité est beaucoup plus élevée que celle de la traversée du tableau basée sur l'ordre. Certains étudiants peuvent ne pas être familiers avec les structures de données, donc je parlerai brièvement du contenu pertinent de la table de hachage.
Tout d'abord, jetons un coup d'œil au stockage des données.
Le stockage des données en mémoire se compose de deux parties, l'une est la valeur et l'autre est l'adresse. Pensez à la mémoire comme un dictionnaire Xinhua, l'explication du mot est la valeur, et le répertoire est l'adresse. Le dictionnaire est trié par Pinyin, par exemple, "Ni" avec la même prononciation est organisé dans la même pièce, c'est-à-dire que le tableau est soigneusement disposé dans une zone de mémoire. Cette structure est un tableau, vous pouvez spécifier "Ni" numéro 1 et 10 pour y accéder. Le diagramme de structure est le suivant:
L'avantage des tableaux est qu'ils sont simples à traverser, et ils peuvent accéder directement aux données correspondantes via des indices. Mais il est très difficile d'ajouter ou de supprimer un certain élément. Par exemple, si vous souhaitez supprimer l'élément 6, les données après l'élément 5 doivent être avancées par une seule position. Si vous souhaitez supprimer le premier bit, l'ensemble du tableau doit être déplacé, ce qui consomme beaucoup.
Afin de résoudre le problème de l'addition et de la suppression du tableau, des listes liées apparaissent. Si nous divisons la valeur en deux parties, une partie est utilisée pour stocker la valeur d'origine, et l'autre pièce est utilisée pour stocker une adresse, qui pointe vers une autre structure, etc., former une liste liée. La structure est la suivante:
Il peut être clairement vu à partir de la figure ci-dessus que l'ajout et la suppression de la liste liée est très simple. Réécrivez simplement l'élément cible et l'élément suivant de l'élément précédent et il sera terminé. Cependant, il est très difficile d'interroger la valeur d'un élément. Vous devez le traverser à son tour pour accéder à l'emplacement cible.
Afin d'intégrer les avantages de ces deux structures, vous devez avoir pensé à la structure suivante.
Cette structure de données est une structure de table de hachage. L'adresse d'en-tête de la liste liée est stockée dans le tableau et une table de données bidimensionnelle peut être formée. Quant à la façon dont les données sont distribuées, il s'agit d'un algorithme de hachage, et une traduction régulière devrait être un algorithme de hachage. Bien qu'il existe de nombreux types d'algorithmes, ils résolvent la clé à travers une fonction, puis placent les données en fonction des résultats obtenus à partir de la solution. En d'autres termes, un mappage est formé entre la clé et l'adresse réelle, donc pour le moment, nous n'accédons plus au tableau par indication du tableau ou en le traversant simplement, mais localisons plutôt les données par la fonction inverse de la fonction de hachage. L'objet en JS est une structure de hachage. Par exemple, nous définissons un OBJ. OBJ.name à travers le hachage, et sa position en mémoire peut être de 90 dans la figure ci-dessus. Lorsque nous voulons utiliser obj.name, la couche sous-jacente nous aidera automatiquement à localiser la position de 90 via l'algorithme de hachage, ce qui signifie que nous commençons directement à rechercher la liste liée à partir des 12 éléments du tableau, plutôt que de traverser l'ensemble du bloc de mémoire de 0.
Définissez un objet obj {key: valeur} dans js. La clé est convertie en une chaîne puis hachée pour obtenir une adresse mémoire, puis y mettez la valeur. Cela nous permet de comprendre pourquoi nous pouvons ajouter et supprimer les attributs à volonté, et pourquoi nous pouvons également attribuer des attributs aux tableaux en js, et il n'y a pas de soi-disant tableau transfrontalier.
Dans les situations où le volume de données est important, le tableau de hachage a un avantage très évident car il réduit beaucoup de calculs inutiles à travers l'algorithme de hachage. La soi-disant optimisation des performances consiste en fait à rendre les ordinateurs moins informatiques; La plus grande optimisation consiste à ne pas calculer!
Optimisation des algorithmes
Maintenant que vous comprenez l'implémentation sous-jacente de l'algorithme, vous pouvez envisager d'optimiser l'algorithme rétrospectivement. Cependant, avant d'optimiser, vous devez souligner une chose: ne poursuivez pas les performances aveuglément! Par exemple, dans ce cas, nous pouvons faire correspondre jusqu'à 5 000 mots au maximum, donc l'algorithme existant est suffisant, et toutes les optimisations ne sont pas nécessaires. La raison pour laquelle je parle toujours de l'optimisation est d'améliorer ma compréhension de l'algorithme et du programme, plutôt que de vraiment faire l'optimisation 1MS.
Nous avons constaté qu'aucun de nos mots clés n'avait un seul mot, donc ce serait un gaspillage pour nous de traverser les mots clés en fonction de l'unité d'un mot. L'optimisation ici est de pré-statistique la longueur maximale et minimale du mot-clé et de rechercher en unités de la longueur minimale à chaque fois. Par exemple, le mot-clé de mon cas de test est un idiome, et le plus court est de 4 caractères, donc chaque fois que je correspond, je correspond à 4 caractères ensemble. Si je frappe, continuez à rechercher en profondeur pour trouver la longueur maximale. En d'autres termes, lorsque nous construisons l'arbre pour la première fois, il est d'abord construit avec la longueur minimale, puis il est ajouté mot pour mot.
Un calcul simple est effectué. Selon notre cas de test, pour 300 idiomes, nous n'avons besoin de comparer qu'un seul mot, et pour une requête unique, nous devons comparer 4 fois, et chaque comparaison nous devons accéder à notre structure d'arbre, qui est la consommation de performances évitables. Plus important encore, la comparaison ici n'est pas une comparaison de cordes. Nos mots clés ici existent tous en tant que clés, et l'effet est le même que la clé dans OBJ, qui a haché la clé puis accéder à l'adresse correspondante! Alors ne vous inquiétez pas de la différence entre la comparaison d'un mot et la comparaison de quatre mots. Nous n'avons pas comparé les cordes!
Il s'agit de faire correspondre plusieurs mots clés. Je ne publierai pas la version optimisée du code car elle n'est généralement pas disponible.