Brevet FR3078573A1 — publié le 20190906

La présente invention concerne le domaine de l'analyse sémantique dans un contexte de reconnaissance vocale. L'invention concerne plus particulièrement un procédé d'analyse lexicale d'une chaîne de caractères. L'analyse lexicale d'une chaîne de caractères (ou symboles) consiste en la transformation de la chaîne de caractères, c'est-à-dire d'une suite de caractères, en une liste ordonnée de mots, c'est-à-dire de sous-chaînes de caractères ayant un sens prédéterminé. Dans un contexte de reconnaissance vocale, la chaîne de caractères peut correspondre au résultat d'un algorithme de reconnaissance vocale. Il est alors nécessaire de pouvoir reconnaître au sein de cette chaîne de caractères d'éventuels mots clefs prédéterminés. Il est ainsi nécessaire de rechercher, au sein de la chaîne de caractères, des sous- chaînes de caractères prédéterminées. Toutefois, un algorithme de recherche classique nécessite un temps de calcul qui évolue de façon non linéaire suivant le nombre de sous-chaînes à rechercher. Ce temps de calcul qui peut devenir très important est à éviter particulièrement dans un système dans lequel la reconnaissance vocale est utilisée pour du pilotage vocal. En effet, si le temps d'analyse lexicale devient important, cela introduit une latence dans la réponse du système de pilotage vocale, latence qui peut perturber un utilisateur du système. Des algorithmes ont été proposés pour répondre à cette problématique, comme par exemple l'algorithme de Rabin-Karp ou bien l'algorithme de Boyer-Moore. Toutefois ces algorithmes ne répondent pas à toutes les caractéristiques attendues dans un système de pilotage vocal, c'est-à-dire : - une possibilité de recherche de sous-chaînes multiples, sans que le temps de calcul n'évolue de façon non linéaire, - pas de recours à une phase préalable nécessitant des calculs intensifs afin de pouvoir modifier une liste de sous-chaînes à rechercher sans devoir relancer ces calculs intensifs, - adaptabilité de l'algorithme à la longueur des sous-chaînes à rechercher, - adaptabilité de l'algorithme à la longueur de la chaîne de caractères à traiter. 2 Un objet de la présente invention est de proposer un procédé d'analyse lexicale d'une chaîne de caractères qui ne présente pas les inconvénients de l'art antérieur. L'invention concerne un procédé d'analyse lexicale d'une chaîne de caractères, le procédé étant exécuté par un dispositif électronique, le dispositif électronique 5 comprenant une mémoire dans laquelle est enregistrée une liste de sous-chaînes de caractères prédéterminées, le dispositif électronique étant adapté pour recevoir, en entrée, une chaîne de caractères et pour enregistrer dans la mémoire, en sortie, une liste ordonnée des sous-chaînes comprises dans la chaîne de caractères, le procédé comprenant les étapes préalables de : 10 pour chaque sous-chaîne de caractères prédéterminée, déterminer un condensat, dit condensat préfixe, en fonction des P premiers caractères de ladite sous-chaîne, P étant prédéterminé, - pour chaque sous-chaîne de caractères prédéterminée, déterminer, dans une table, dite table de hachage, enregistrée dans la mémoire du dispositif 15 électronique, une entrée correspondant au condensat préfixe associé à ladite sous- chaîne, - pour chaque entrée de la table de hachage correspondant à un préfixe, déterminer une liste ordonnée des sous-chaînes prédéterminées associées, chaque sous-chaîne prédéterminée étant associée à un condensat, dit condensat sous-chaîne, 20 fonction de la sous-chaîne prédéterminée, la liste étant ordonnée selon une longueur décroissante des sous-chaînes prédéterminées, et, - recevoir la chaîne de caractères et déterminer une position d'un pointeur sur la chaîne de caractères, la position correspondant initialement au premier caractère de la chaîne de caractères, 25 le procédé comprenant de plus les étapes itératives de : - déterminer un premier condensat de la sous-chaîne formée par P caractères de la chaîne de caractères à partir de la position du pointeur, - déterminer si une entrée condensat préfixe de la table de hachage correspond à ce premier condensat, 30 si oui, pour chaque longueur des sous-chaînes prédéterminées de la liste associée à ladite entrée condensat préfixe, et dans l'ordre de la liste, déterminer un condensat de la sous-chaîne formée par un nombre de caractères de la chaîne de caractères égal à ladite longueur à partir de la position du pointeur, et, si ledit 3 condensat est égal à un condensat sous-chaîne associé à l'une des sous-chaînes prédéterminées de même longueur, alors : o vérifier que ladite sous-chaîne prédéterminée est égale à la sous-chaîne formée par un nombre de caractères de la chaîne de caractères égal à ladite longueur à 5 partir de la position du pointeur, et, si c'est le cas, o enregistrer ladite sous-chaîne, dite sous-chaîne identifiée, dans la liste ordonnée des sous-chaînes prédéterminées comprises dans la chaîne de caractères, o positionner le pointeur sur la chaîne de caractères à une nouvelle position correspondant à la position additionnée d'un nombre de caractères correspondant à la 10 longueur de la sous-chaîne identifiée, - si non, positionner le pointeur sur la chaîne de caractères à une nouvelle position correspondant au déplacement d'un caractère sur la chaîne de caractères. Avantageusement, ce procédé permet une analyse lexicale d'une chaîne de caractères en réduisant le temps de calcul nécessaire par rapport à un procédé 15 nécessitant une comparaison caractère par caractère d'une sous-chaîne de caractères afin de déterminer la présence, ou non, de ladite sous-chaîne de caractères dans la chaîne de caractères. Le temps de calcul évolue ainsi de manière linéaire suivant la taille de la liste de sous-chaînes de caractères prédéfinies, et non de manière non-linéaire, ce qui garantit une analyse lexicale plus rapide. 20 Selon un mode de réalisation complémentaire de l'invention, le procédé comprend les étapes ultérieures de mise à jour de la liste de sous-chaînes de caractères prédéterminées : - recevoir une sous-chaîne, - déterminer le condensat dit condensat préfixe, en fonction des P premiers 25 caractères de ladite sous-chaîne, - déterminer une entrée dans la table de hachage correspondant audit condensat préfixe, - enregistrer dans la liste ordonnée des sous-chaînes associées à l'entrée déterminée de la sous-chaîne, la position dans la liste de la sous-chaîne étant 30 fonction de la longueur de la sous-chaîne, - déterminer et enregistrer un condensat de la sous-chaîne en association avec la sous-chaîne dans la liste. L'invention concerne également un dispositif électronique permettant une analyse lexicale d'une chaîne de caractères, le dispositif électronique comprenant une 4 mémoire dans laquelle est enregistrée une liste de sous-chaînes de caractères prédéterminées, le dispositif électronique étant adapté pour : - pour chaque sous-chaîne de caractères prédéterminée, déterminer un condensat, dit condensat préfixe, en fonction des P premiers caractères de 5 ladite sous-chaîne, P étant prédéterminé, - pour chaque sous-chaîne de caractères prédéterminée, déterminer, dans une table, dite table de hachage, enregistrée dans la mémoire du dispositif électronique, une entrée correspondant au condensat préfixe associé à ladite sous-chaîne, 10 - pour chaque entrée de la table de hachage correspondant à un préfixe, déterminer une liste ordonnée des sous-chaînes prédéterminées associées, chaque sous-chaîne prédéterminée étant associée à un condensat, dit condensat sous-chaîne, fonction de la sous-chaîne prédéterminée, la liste étant ordonnée selon une longueur décroissante des sous-chaînes prédéterminées, et, 15 - recevoir une chaîne de caractères et déterminer une position d'un pointeur sur la chaîne de caractères, la position correspondant initialement au premier caractère de la chaîne de caractères, le procédé comprenant de plus les étapes itératives de : - déterminer un premier condensat de la sous-chaîne formée par P caractères de 20 la chaîne de caractères à partir de la position du pointeur, - déterminer si une entrée condensat préfixe de la table de hachage correspond à ce premier condensat, - si oui, pour chaque longueur des sous-chaînes prédéterminées de la liste associée à ladite entrée condensat préfixe, et dans l'ordre de la liste, déterminer 25 un condensat de la sous-chaîne formée par un nombre de caractères de la chaîne de caractères égal à ladite longueur à partir de la position du pointeur, et, si ledit condensat est égal à un condensat sous-chaîne associé à l'une des sous-chaînes prédéterminées de même longueur, alors : o vérifier que ladite sous-chaîne prédéterminée est égale à la sous-chaîne 30 formée par un nombre de caractères de la chaîne de caractères égal à ladite longueur à partir de la position du pointeur, et, si c'est le cas, o enregistrer ladite sous-chaîne, dite sous-chaîne identifiée, dans une liste ordonnée des sous-chaînes prédéterminées comprises dans la chaîne de 5 caractères, ladite liste étant enregistrée dans la mémoire du dispositif électronique, o positionner le pointeur sur la chaîne de caractères à une nouvelle position correspondant à la position additionnée d'un nombre de 5 caractères correspondant à la longueur de la sous-chaîne identifiée, si non, positionner le pointeur sur la chaîne de caractères à une nouvelle position correspondant au déplacement d'un caractère sur la chaîne de caractères. L'invention concerne également un programme d'ordinateur comprenant des 10 instructions pour mettre en oeuvre, par un processeur d'un dispositif électronique, un procédé d'analyse lexicale décrit dans le présent document lorsque le programme d'ordinateur est exécuté par le processeur. L'invention concerne également un support d'enregistrement, lisible par un dispositif électronique, sur lequel est stocké ledit programme d'ordinateur. 15 La Fig. 1 représente un organigramme d'un procédé d'analyse lexicale d'une chaîne de caractères selon un mode de réalisation de l'invention, les Fig. 2A à 2J représentent une illustration de la mise en oeuvre du procédé d'analyse lexicale d'une chaîne de caractères selon un mode de réalisation de l'invention, 20 la Fig. 3 représente un organigramme de mise à jour d'une table de hachage pour un procédé d'analyse lexicale d'une chaîne de caractères selon un mode de réalisation de l'invention, la Fig. 4 représente schématiquement l'architecture matérielle d'un dispositif électronique adapté pour mettre en oeuvre un procédé d'analyse lexicale d'une chaîne 25 de caractères selon un mode de réalisation de l'invention. La Fig. 1 représente un organigramme d'un procédé 100 d'analyse lexicale d'une chaîne de caractères selon un mode de réalisation de l'invention. Le procédé 100 d'analyse lexicale d'une chaîne de caractères peut être exécuté par un dispositif électronique tel que décrit ci-après dans la Fig. 4. Ledit dispositif électronique 30 comprend une mémoire dans laquelle est enregistrée une liste de sous-chaînes de caractères prédéterminées. Ces sous-chaînes correspondent à des mots prédéterminés ou « mots clefs » que le procédé 100 d'analyse lexicale se propose de retrouver (ou d'identifier) au sein de la chaîne de caractères. Le dispositif électronique est adapté pour recevoir, en entrée, la chaîne de caractères. Selon un mode de réalisation de 6 l'invention, la chaîne de caractères est issue d'un module de reconnaissance vocale du dispositif électronique. Le dispositif électronique est adapté pour enregistrer dans une mémoire, en sortie, une liste ordonnée des sous-chaînes comprises dans la chaîne de caractères. Dit autrement, le dispositif électronique mettant en oeuvre le procédé 100 5 d'analyse lexicale, reçoit d'un côté la chaîne de caractères et, en sortie, détermine une liste des sous-chaînes de caractères prédéterminées identifiées dans la chaîne de caractères. Cette liste est ordonnée dans le sens où les sous-chaînes de caractères apparaissent dans le même ordre que leur ordre d'apparition dans la chaîne de caractères. Le procédé peut être mis en oeuvre par un dispositif électronique sur une 10 chaîne de caractères de longueur finie. Selon un autre mode de réalisation de l'invention, le procédé 100 d'analyse lexicale peut être mis en oeuvre de manière continue sur une chaîne de caractères de type « buffer » constamment alimentée, par exemple par un module de reconnaissance vocale. Le procédé permet avantageusement de ne parcourir la chaîne de caractères à 15 analyser qu'une seule fois, sans devoir effectuer aucun aller-retour. Comme décrit ci- après, à chaque position testée, le procédé permet de tester la présence d'une des sous-chaînes prédéterminées. Le procédé s'appuie sur une table de hachage, avantageusement enregistrée dans une mémoire du dispositif électronique mettant en oeuvre le procédé. Cette table de hachage peut être initialement prédéterminée. La 20 table de hachage peut aussi être complétée par l'ajout de nouvelles sous-chaînes de caractères. Le procédé d'ajout d'une sous-chaîne de caractères dans la table de hachage est plus particulièrement décrit dans la Fig. 3, comme décrit ci-après. La présente description de la Fig. 1 considère qu'une table de hachage prédéterminée est enregistrée dans la mémoire du dispositif électronique mettant en 25 oeuvre le procédé. Une table de hachage comprend une pluralité d'entrées, chaque entrée correspondant à un condensat (ou « hash » en anglais, c'est-à-dire le résultat d'une fonction de hachage) d'un préfixe d'une sous-chaîne de caractères, ainsi que dudit préfixe. On entend par préfixe les P premiers caractères d'une sous-chaîne de 30 caractères. Le paramètre P permet donc de définir une longueur de préfixe. La valeur du paramètre P doit être à la fois la plus petite possible afin de pouvoir traiter des sous-chaînes de petite taille, tout en étant en même temps d'une valeur suffisante pour permettre une bonne discrimination des condensats. P est avantageusement fixé à la valeur « 3 », valeur qui permet un bon compromis. Ainsi, par exemple, le préfixe de la 7 sous-chaîne de caractères « ETAGE », avec P = 3, est « ETA ». Pour chaque entrée correspondant à un préfixe est associée une liste de sous-chaînes comprenant ce même préfixe. Cette liste de sous-chaînes est ordonnée, les sous-chaînes étant ainsi ordonnées en fonction de leur taille, de la plus grande vers la plus petite. La longueur 5 de chaque sous-chaîne de caractères est enregistrée dans la liste, ainsi qu'un condensat de la sous-chaîne de caractères. Un exemple d'une table de hachage est donné ci-après : Condelisat Préfixe Sous-chaîne de caractères préfixe Sous-chaîne Lona_&_ttetir Condensat Hash(Préfixe A) Préfixe A Sous-chaîne 1 Longueur sous-chaîne 1 Hash(sous-chaîne 1) Sous-chaîne 2 Longueur sous-chaîne 2 Hash(sous-chaîne 2) Sous-chaîne 3 Longueur sous-chaîne 3 Hash(sous-chaîne 3) Hash(Préfixe B) Préfixe B Sous-chaîne 4 Longueur sous-chaîne 4 Hash(sous-chaîne 4) Hash(Préfixe C) Préfixe C Sous-chaîne 5 Longueur sous-chaîne 5 Hash(sous-chaîne 5) Sous-chaîne 6 Longueur sous-chaîne 6 Hash(sous-chaîne 6) 10 Tableau 1 - exemple de table de hachage Dans cet exemple de table de hachage illustrée dans le tableau 1, « sous-chaîne i », avec i = 1 à 6, correspondent à des sous-chaînes de caractères différentes. Les trois sous-chaînes 1, 2 et 3 partagent un même « préfixe A ». C'est-à-dire que ces trois sous-chaînes commencent par les mêmes P premiers caractères. Ces trois 15 sous-chaînes sont associées au préfixe A. Dit autrement, une liste de sous-chaînes est associée au préfixe A, cette liste comprenant ici les trois sous-chaînes de caractères 1, 2 et 3. De même, les sous-chaînes 5 et 6 partagent un même préfixe « préfixe C », c'est-à-dire qu'elles commencent par les mêmes P premiers caractères correspondant à « préfixe C ». Le préfixe est indiqué dans la deuxième colonne intitulée « Préfixes ». 20 La première colonne « condensat » correspond au résultat d'une fonction de hachage sur ledit préfixe (fonction notée « Hash0 »). La colonne « Longueurs » comprend la longueur de la sous-chaîne correspondante. Cela permet avantageusement d'ordonner chaque liste de sous-chaînes associées à un préfixe dans le sens décroissant. La dernière colonne 25 « Condensat » comprend un condensat de la sous-chaîne correspondante. La fonction de hachage utilisée pour déterminer le condensat du préfixe et la fonction de hachage 8 utilisée pour déterminer le condensat d'une sous-chaîne de caractères peuvent être différentes. Dit autrement, l'entrée correspondant au préfixe C est associée à une liste comprenant ici deux sous-chaînes de caractères, la sous-chaîne 5 et la sous-chaîne 6. 5 Cette liste comprend de plus, pour chaque sous-chaîne, la longueur de la sous-chaîne et un condensat de la sous-chaîne de caractères. La liste est ordonnée. Ainsi, dans l'exemple donné, la longueur de la sous-chaîne 5 est supérieure ou égale à la longueur de la sous-chaîne 6. La table de hachage étant définie ou prédéterminée, le procédé d'analyse 10 lexicale 100 peut être mis en oeuvre. Dans une première étape (non représentée), le dispositif électronique reçoit une chaîne de caractères à analyser. Cette chaîne de caractères peut être fournie par un module de reconnaissance vocale du dispositif électronique. Dans une étape 100, le dispositif électronique positionne un pointeur sur le 15 premier caractère de la chaîne de caractères. Cette position peut correspondre par exemple à un indice « n = 0» (cf par exemple Fig. 2A). Dans une étape suivante 105, le dispositif électronique détermine un condensat de la sous-chaîne formée par les P premiers caractères de la chaîne de caractères à partir de la position actuelle du pointeur. Dit autrement, si le pointeur est positionné à 20 la position « n » de la chaîne de caractères, et si «P = 3 », alors le dispositif électronique détermine un condensat de la sous-chaîne de trois caractères comprenant les caractères aux positions « n », « n+ 1» et « n+2 ». Dans une étape suivante 110, le dispositif électronique détermine si le condensat déterminé à l'étape précédente 105 correspond à l'un des condensats « préfixe » de la 25 table de hachage (cf Fig. 2C ou bien 2F). Le dispositif électronique parcourt donc la table de hachage pour rechercher l'éventuelle présence d'un condensat préfixe égal au condensat calculé lors de l'étape 105 précédente. Comparer des condensats plutôt que des chaînes de caractères permet d'accélérer le temps de la comparaison et de réduire le temps de calcul nécessaire. En effet, la comparaison porte alors sur des condensats, 30 c'est-à-dire des nombres, plutôt que sur des chaînes de caractères qui nécessiteraient d'être comparées caractère par caractère. La comparaison est ainsi plus rapide et/ou nécessite moins de temps de calcul. Si aucun condensat ne correspond, alors le dispositif électronique passe à l'étape 115. Dans cette étape 115, le dispositif électronique incrémente la position du pointeur 9 sur la chaîne de caractères afin de tester la position suivante (cf. passage de la Fig. 2A à la Fig. 2B, ou bien de la Fig. 2E à la Fig. 2F). Dit autrement, si le pointeur était à la position « n» de la chaîne de caractères, cette position du pointeur est incrémentée de un, « n » prenant la valeur de « n+1 ». Le procédé se poursuit alors par une nouvelle 5 étape 105. Si un condensat préfixe est retrouvé (cf. Fig. 2C ou bien 2F), de valeur identique au condensat calculé lors de l'étape 105, alors le dispositif électronique passe à l'étape 120. Dans cette étape 120, le dispositif électronique retrouve la liste ordonnée des sous-chaînes de caractères associée au préfixe correspondant au condensat préfixe 10 retrouvé. Les étapes 125 et 130 sont ensuite exécutées pour chaque sous-chaîne de caractères de la liste. Dans une étape 125, et successivement pour chaque longueur des sous-chaînes de caractères de la liste associée à ladite entrée condensat préfixe, et dans l'ordre de cette liste, le dispositif électronique détermine un condensat de la sous-chaîne de 15 caractères formée par un nombre de caractères de la chaîne de caractères égal à ladite longueur à partir de la position du pointeur. Dit autrement, le dispositif électronique détermine, en commençant par la longueur de la sous-chaîne la plus grande dans la liste, un condensat de la sous-chaîne de caractères de même longueur formée par les caractères de la chaîne de caractères à partir de la position actuelle du pointeur. 20 Si les deux condensats ne correspondent pas, alors, dans une étape 130, le dispositif électronique sélectionne la sous-chaîne de caractères de taille immédiatement inférieure pour répéter une étape 125. Si les deux condensats correspondent, et que le condensat est associé à plusieurs sous-chaînes de caractères dans la liste, alors ces sous-chaînes de caractères sont testées (lors de l'étape 125) 25 l'une après l'autre, dans l'ordre dans lequel elles apparaissent dans la liste. Cet ordre, à longueur de sous-chaîne de caractères identique, importe peu. Si aucun condensat déterminé lors de l'étape 125 ne correspond à un condensat d'une sous-chaîne de caractères de la liste, et quand la liste a été parcourue en totalité, alors le dispositif électronique passe ensuite à l'étape 115 afin d'incrémenter la 30 position du pointeur. Cela signifie qu'aucune sous-chaîne de caractères de la liste de sous-chaînes de caractères associées au condensat préfixe n'a été identifiée et que le procédé est repris à partir de la position suivante (n = n+1) de la chaîne de caractères à partir de l'étape 105. 10 Si au contraire le condensat déterminé lors de l'étape 125 correspond à un condensat d'une sous-chaîne de caractères dans la liste associée au condensat préfixe, cela signifie que très probablement ladite sous-chaîne de caractères a été identifiée dans la chaîne de caractères. Selon le mode de réalisation de l'invention, une étape 5 optionnelle 135 de vérification de l'égalité entre la sous-chaîne de caractères identifiée et la sous-chaîne de caractères de même longueur formée par les caractères de la chaîne de caractères à partir de la position actuelle du pointeur est effectuée. Dit autrement, le dispositif électronique vérifie que la sous-chaîne de la table de hachage retrouvée est égale à la sous-chaîne formée par un nombre de caractères de la chaîne 10 de caractères égal à ladite longueur à partir de la position du pointeur. Cette étape est optionnelle, en fonction en particulier de la fonction de hachage utilisée. Cette étape a pour objectif d'éviter les situations de collisions de la fonction de hachage. Une fois une sous-chaîne de la table de hachage identifiée dans la chaîne de caractères, le dispositif électronique enregistre ladite sous-chaîne de caractères dans la 15 mémoire. Avantageusement, ladite sous-chaîne de caractères est enregistrée dans une liste ordonnée correspondant à une liste des sous-chaînes de caractères de la table de hachage qui ont été identifiées dans la chaîne de caractères. Le dispositif électronique peut enregistrer aussi la position dans la chaîne de caractères (c'est-à-dire la valeur de «n »), et possiblement la longueur, de chaque sous-chaîne de caractères ainsi 20 identifiée. Cette liste ordonnée, à ne pas confondre avec les listes ordonnées de la table de hachage, correspond in fine au résultat du procédé d'analyse lexicale. Le procédé 100 d'analyse lexicale permet d'enregistrer dans cette liste les sous-chaînes de caractères identifiées (ou reconnues). 25 Une fois une sous-chaîne de caractères enregistrée dans la mémoire, le dispositif électronique passe à l'étape 145. Dans cette étape 145, la position du pointeur sur la chaîne de caractères est déplacée d'un nombre de caractères correspondant à la longueur de la sous-chaîne de caractères identifiée. Dit autrement, suite à l'étape 145, le procédé 100 d'analyse lexicale se poursuit à partir du premier caractère de la chaîne 30 de caractères après la sous-chaîne de caractères venant d'être identifiée (cf Fig. 2J). Les Figs. 2A à 2J représentent une illustration de la mise en oeuvre du procédé 100 d'analyse lexicale d'une chaîne de caractères selon un mode de réalisation de l'invention. 11 Une table de hachage prédéterminée est enregistrée dans la mémoire du dispositif électronique mettant en oeuvre le procédé. Ladite table de hachage est représentée ci-après : Condensat Préfixe Sous-chaîne de caractères Préfixe Sous-chaîne Longueur Condensat Hash(ET A) ETA ETAGERE 7 Hash(ET AGERE) ETAGE 5 Hash(ET AGE) ETAL 4 Hash(ET AL) 5 Tableau 2 - Exemple de table de hachage Dans la Fig. 2A, un pointeur (représenté dans les figures par une flèche pointant vers le bas) est positionné en tout début de la chaîne de caractères. Dans l'exemple donné, la valeur de P est égale à 3. Ainsi les trois premiers caractères de la chaîne de caractères, à partir de la position du pointeur, apparaissent en grisé. Le dispositif 10 électronique, conformément à l'étape 105 du procédé 100 illustré précédemment, détermine un condensat des trois caractères « AAE » de la chaîne de caractères grisés. Ce condensat ne correspondant pas au condensat du préfixe « ETA » enregistré dans la table de hachage, le pointeur est déplacé d'une position sur la chaîne de caractères (étape 115 du procédé 100) comme illustré dans la Fig. 2B. 15 Dans la Fig. 2B, de même, le condensat de « AET », les P (P =3) caractères de la chaîne de caractères, est déterminé. Comme il ne correspond pas non plus au condensat du préfixe « ETA » dans la table de hachage, le pointeur est encore déplacé, comme illustré dans la Fig. 2C. Dans la Fig. 2C, le condensat des trois caractères grisés « ETA » de la chaîne de 20 caractères correspond au condensat du préfixe « ETA » dans la table de hachage, le dispositif électronique retrouve alors les sous-chaînes de caractères associées au préfixe ETA, c'est-à-dire « ETAGERE », « ETAGE » et « ETAL » et peut les rechercher une par une (étapes 120, 125, 130 et 135 du procédé 100). Comme indiqué dans la Fig. 2D, le dispositif électronique commence par 25 rechercher la sous-chaîne de plus grande longueur, c'est-à-dire « ETAGERE ». Pour cela, le dispositif électronique détermine un condensat correspondant aux caractères grisés dans la Fig. 2D, c'est-à-dire la sous-chaîne de caractères de même longueur que la sous-chaîne « ETAGERE » de la chaîne de caractères formée à partir du pointeur. Dans le cas illustré, le condensat déterminé correspond bien au condensat de la sous- 12 chaîne « ETAGERE » dans la table de hachage. Une vérification caractère par caractère de la sous-chaîne de caractères peut ensuite être exécutée (étape 135 du procédé 100). La sous-chaîne de caractères « ETAGERE » a donc été identifiée dans la chaîne de caractères. Cette sous-chaîne est enregistrée dans une liste ordonnée 5 comprenant le résultat de l'analyse lexicale. Dans la Fig. 2E, conformément à l'étape 145 du procédé 100, le pointeur est déplacé à la suite de la sous-chaîne identifiée. Le condensat de la sous-chaîne de caractères grisés ne correspondant pas à un condensat connu, le pointeur est déplacé d'une position, comme illustré dans la Fig. 2F. 1() Dans la Fig. 2F, le dispositif électronique détermine que le condensat de la sous- chaîne de caractères formée par les caractères grisés correspond au condensat du préfixe « ETA ». Dans la Fig. 2G, le dispositif électronique détermine le condensat de la sous-chaîne de caractères de même longueur que la sous-chaîne de caractères 15 « ETAGERE » à partir de la position actuelle du pointeur, c'est-à-dire des caractères grisés dans la Fig. 2G. Les condensats étant différents, le dispositif électronique passe à la sous-chaîne de caractères associée au préfixe ETA suivant, c'est-à-dire « ETAGE ». Ainsi, dans la Fig. 2H, le dispositif électronique détermine le condensat de la 20 sous-chaîne de caractères de même longueur que la sous-chaîne de caractères « ETAGE » à partir de la position actuelle du pointeur, c'est-à-dire des caractères grisés dans la Fig. 2H. Les condensats étant différents, le dispositif électronique passe à la sous-chaîne de caractères associée au préfixe ETA suivant, c'est-à-dire « ETAL ». Ainsi, dans la Fig. 21, le dispositif électronique détermine le condensat de la 25 sous-chaîne de caractères de même longueur que la sous-chaîne de caractères « ETAL » à partir de la position actuelle du pointeur, c'est-à-dire des caractères grisés dans la Fig. 21. Les condensats correspondent. La sous-chaîne « ETAL » est identifiée, le dispositif électronique peut déplacer ensuite le pointeur à la suite de la sous-chaîne de caractères identifiée, comme illustrée dans la Fig. 2J. 30 Le procédé 100 est ainsi exécuté de façon itérative sur la chaîne de caractères, et ce jusqu'à la fin de la chaîne de caractères. Selon un mode de réalisation de l'invention, la chaîne de caractères est continue, c'est-à-dire qu'elle peut être complétée en permanence par exemple par un module de reconnaissance vocale. 13 La Fig. 3 représente un organigramme d'un procédé 300 de mise à jour d'une table de hachage pour un procédé d'analyse lexicale d'une chaîne de caractères selon un mode de réalisation de l'invention. Ce procédé 300 peut être exécuté préalablement à la réalisation du procédél00. Le procédé 300 peut aussi être réalisé à tout moment 5 lors de l'exécution du procédé 100, la table de hachage étant alors mise à jour dynamiquement. Possiblement, si une analyse lexicale d'une chaîne de caractères est en cours lors de la mise à jour de la table de hachage, le procédé peut être réinitialisé à sa première étape afin de prendre en compte la ou les nouvelles entrées ajoutées ou supprimées dans la table de hachage. Cela n'est toutefois pas obligatoire. 10 Le procédé 300 de mise à jour est illustré avec la table de hachage illustrée précédemment dans le tableau 2. Dans une première étape 301, le dispositif électronique reçoit une sous-chaîne de caractères (par exemple ici « ETAT »). Cette sous-chaîne de caractères est a priori différente des sous-chaînes de caractères déjà enregistrées dans la table de hachage. 15 Une étape de vérification de la non présence de la sous-chaîne de caractères peut être exécutée. Dans ce cas, la sous-chaîne peut être ignorée si la vérification montre que la sous-chaîne est déjà présente dans la table de hachage. Dans une étape suivante 305, le dispositif électronique détermine un condensat correspondant au préfixe de la sous-chaîne reçue, c'est-à-dire fonction des P premiers 20 caractères de ladite sous-chaîne. Dit autrement, le dispositif électronique détermine un condensat de la sous-chaîne de caractères formée par le P premiers caractères de la sous-chaîne de caractères reçue (dans notre exemple, hash(ETA)). Dans une étape 310, le dispositif électronique détermine si une entrée de la table de hachage, c'est-à-dire un « hash(préfixe) », correspond au condensat déterminé lors 25 de l'étape précédente. Si non, une nouvelle entrée est créée dans la table de hachage et la sous-chaîne de caractères est placée dans une nouvelle liste associée à cette nouvelle entrée. Si oui, la sous-chaîne de caractères reçue doit être enregistrée dans la liste associée au condensat préfixe identifié (ici dans notre exemple, hash(ETA)). 30 Dans une étape 315, le dispositif électronique parcourt la liste associée afin de déterminer la position d'enregistrement de la sous-chaîne de caractères reçue en fonction de la longueur de ladite sous-chaîne. En effet, la liste est ordonnée, chaque sous-chaîne de caractères de la liste étant classée en fonction de sa longueur. Les sous-chaînes de caractères sont ordonnées par ordre décroissant. Il s'agit d'une convention, 14 les sous-chaînes pourraient être ordonnées par ordre croissant, il faudrait alors juste modifier le procédé 100 afin de parcourir la liste par sa fin. La sous-chaîne de caractères reçue est enregistrée dans la liste en fonction de sa longueur et de la longueur des autres sous-chaînes déjà présentes dans la table de hachage. La longueur 5 de la sous-chaîne est aussi enregistrée. Dans une étape suivante 320, le dispositif électronique détermine le condensat de la sous-chaîne de caractères reçue. Dans une étape 325, le dispositif électronique enregistre le condensat de la sous-chaîne de caractères dans la table de hachage, en association avec la sous-chaîne. In 10 fine, le dispositif électronique enregistre, dans la liste ordonnée des sous-chaînes associées à l'entrée déterminée, la sous-chaîne reçue en association avec sa longueur et un condensat, la position dans la liste de la sous-chaîne étant fonction de la longueur de la sous-chaîne reçue. La table de hachage, telle que précédemment illustrée, est ainsi modifiée (la 15 sous-chaîne de caractères ajoutée est identifiée ci-dessous en gras et souligné) : Condensat Préfixe Sous-chaîne de caractères préfixe Sous-chaîne Longueur Condensat Hash(ET A) ETA ETAGERE 7 Hash(ET AGERE) ETAGE 5 Hash(ET AGE) ETAT 4 Hash(ETAT) ETAL 4 Hash(ET AL) Tableau 3 - Table de hachage mise à jour La Fig. 4 représente schématiquement l'architecture matérielle d'un dispositif électronique 400 adapté pour mettre en oeuvre un procédé d'analyse lexicale d'une 20 chaîne de caractères selon un mode de réalisation de l'invention. Le dispositif électronique 400 est par exemple adapté pour mettre en oeuvre les procédés décrits dans la Fig. 2 et dans la Fig. 3. Selon un mode de réalisation de l'invention, le dispositif électronique 400 comprend une mémoire dans laquelle est enregistrée une liste de sous-chaînes de 25 caractères prédéterminées. Le dispositif électronique 400 est adapté pour : pour chaque sous-chaîne de caractères prédéterminée, déterminer un condensat, dit condensat préfixe, en fonction des P premiers caractères de ladite sous-chaîne, P étant prédéterminé, 15 - pour chaque sous-chaîne de caractères prédéterminée, déterminer, dans une table, dite table de hachage, enregistrée dans la mémoire du dispositif électronique, une entrée correspondant au condensat préfixe associé à ladite sous-chaîne, 5 - pour chaque entrée de la table de hachage correspondant à un préfixe, déterminer une liste ordonnée des sous-chaînes prédéterminées associées, chaque sous-chaîne prédéterminée étant associée à un condensat, dit condensat sous-chaîne, fonction de la sous-chaîne prédéterminée, la liste étant ordonnée selon une longueur décroissante des sous-chaînes prédéterminées, et, 10 - recevoir une chaîne de caractères et déterminer une position d'un pointeur sur la chaîne de caractères, la position correspondant initialement au premier caractère de la chaîne de caractères. Le dispositif électronique 400 est adapté pour mettre en oeuvre les étapes itératives de : 15 - déterminer un premier condensat de la sous-chaîne formée par P caractères de la chaîne de caractères à partir de la position du pointeur, - déterminer si une entrée condensat préfixe de la table de hachage correspond à ce premier condensat, - si oui, pour chaque longueur des sous-chaînes prédéterminées de la liste 20 associée à ladite entrée condensat préfixe, et dans l'ordre de la liste, déterminer un condensat de la sous-chaîne formée par un nombre de caractères de la chaîne de caractères égal à ladite longueur à partir de la position du pointeur, et, si ledit condensat est égal à un condensat sous-chaîne associé à l'une des sous-chaînes prédéterminées de même longueur, alors : 25 o vérifier que ladite sous-chaîne prédéterminée est égale à la sous-chaîne formée par un nombre de caractères de la chaîne de caractères égal à ladite longueur à partir de la position du pointeur, et, si c'est le cas, o enregistrer ladite sous-chaîne, dite sous-chaîne identifiée, dans une liste ordonnée des sous-chaînes prédéterminées comprises dans la chaîne de 30 caractères, ladite liste étant enregistrée dans la mémoire du dispositif électronique, o positionner le pointeur sur la chaîne de caractères à une nouvelle position correspondant à la position additionnée d'un nombre de caractères correspondant à la longueur de la sous-chaîne identifiée, 16 - si non, positionner le pointeur sur la chaîne de caractères à une nouvelle position correspondant au déplacement d'un caractère sur la chaîne de caractères. Ainsi, selon un mode de réalisation de l'invention, le dispositif électronique 400 5 comprend, reliés par un bus de communication : un processeur ou CPU (« Central Processing Unit » en anglais) 401 ; une mémoire MEM 402 de type RAM (« Random Access Memory » en anglais) et/ou ROM (« Read Only Memory » en anglais), un module réseau NET 403, un module de stockage STCK 404 de type stockage interne et possiblement une pluralité de modules 405 à 40N pour mettre en oeuvre des 10 fonctionnalités du dispositif électronique 400. Par exemple, le module 405 peut être un module de reconnaissance vocale, lequel module comprenant un microphone est adapté pour convertir un signal audio capté en une chaîne de caractères. Ladite chaîne de caractères peut faire l'objet du procédé d'analyse lexicale, objet du présent document. Un module 40N peut être un module de contrôle d'un équipement 15 domotique connecté au dispositif électronique 400. Le module de stockage STCK 404 peut être de type disque dur HDD (« Hard Disk Drive » en anglais) ou SSD (« Solid-State Drive » en anglais), ou de type lecteur de support de stockage externe, tel un lecteur de cartes SD (« Secure Digital » en anglais). Le processeur CPU 401 peut enregistrer des données, ou informations, dans 20 la mémoire MEM 402 ou dans le module de stockage STCK 404. Selon un mode de réalisation de l'invention, le module de stockage STCK 404 peut être la mémoire telle que décrite précédemment lors de la description de la Fig. 2 ou de la Fig. 3. Le processeur CPU 401 peut lire des données enregistrées dans la mémoire MEM 402 ou dans le module de stockage STCK 404. Ces données peuvent correspondre à des 25 paramètres de configuration, des instructions, à une chaîne de caractères reçue par le dispositif électronique 400, à la table de hachage, à une liste de sous-chaînes prédéterminées ou à toute donnée précédemment décrite. Le module réseau NET 403 permet la connexion du dispositif électronique 400 à un réseau local et/ou Internet. Le dispositif électronique 400 peut donc recevoir une chaîne de caractères via le module 30 réseau NET 403. Le dispositif électronique 400 peut accéder à un stockage ou une mémoire distante afin de retrouver et/ou enregistrer toute donnée précédemment décrite. Le processeur CPU 401 est capable d'exécuter des instructions chargées dans la mémoire MEM 402, par exemple à partir du module de stockage STCK 404 ou via le 17 module réseau NET 403. Lorsque le dispositif électronique 400 est mis sous tension, le processeur CPU 401 est capable de lire de la mémoire MEM 402 des instructions et de les exécuter. Ces instructions forment un programme d'ordinateur causant la mise en oeuvre, par le processeur CPU 401, de tout ou partie des procédés et étapes décrits 5 ci-avant, particulièrement le procédé décrit dans les Figs. 1, 2 ou 3. Ainsi, tout ou partie des procédés et étapes décrits ci-avant peut être implémenté sous forme logicielle par exécution d'un ensemble d'instructions par une machine programmable, telle qu'un DSP (« Digital Signal Processor » en anglais) ou un microcontrôleur. Tout ou partie des procédés et étapes décrits ici peuvent aussi être implémentés sous forme 10 matérielle par une machine ou un composant dédié, tel qu'un FPGA (« Field-Programmable Gate Array » en anglais) ou un ASIC (« Application-Specific Integrated Circuit » en anglais). Les fonctions du dispositif électronique 400 peuvent être intégrées dans un dispositif électronique existant par une mise à jour d'un logiciel, c'est-à-dire par exemple par mise à jour du microprogramme (« firmware » en 15 anglais) du dispositif électronique. Le dispositif électronique 400 peut être tout ou partie d'un dispositif de contrôle d'une installation domotique. Il est à noter que le procédé est adapté pour reconnaître des sous-chaînes de caractères de longueur supérieure ou égale à P. Selon un mode de réalisation 20 complémentaire de l'invention, le procédé comprend un procédé spécifique permettant de reconnaître des sous-chaînes de caractères de taille inférieure à P. Ce procédé spécifique n'utilise pas la notion de hachage (ou condensat) et permet de reconnaître ces sous-chaînes de taille inférieure à P par comparaison directe des sous-chaînes de caractères, possiblement caractère par caractère. Ces étapes peuvent avantageusement 25 être intercalées après l'étape 101 (ou l'étape 115 après une itération) et avant l'étape REVENDICATIONS1) Procédé d'analyse lexicale d'une chaîne de caractères, le procédé étant exécuté par un dispositif électronique, le dispositif électronique comprenant une mémoire dans laquelle est enregistré une liste de sous-chaînes de caractères prédéterminées, le dispositif électronique étant adapté pour recevoir, en entrée, une chaîne de caractères et pour enregistrer dans la mémoire, en sortie, une liste ordonnée des sous-chaînes comprises dans la chaîne de caractères, le procédé comprenant les étapes préalables de : pour chaque sous-chaîne de caractères prédéterminée, déterminer un condensat, dit condensat préfixe, en fonction des P premiers caractères de ladite sous- chaîne, P étant prédéterminé, - pour chaque sous-chaîne de caractères prédéterminée, déterminer, dans une table, dite table de hachage, enregistrée dans la mémoire du dispositif électronique, une entrée correspondant au condensat préfixe associé à ladite sous-chaîne, - pour chaque entrée de la table de hachage correspondant à un préfixe, déterminer une liste ordonnée des sous-chaînes prédéterminées associées, chaque sous-chaîne prédéterminée étant associée à un condensat, dit condensat sous-chaîne, fonction de la sous-chaîne prédéterminée, la liste étant ordonnées selon une longueur décroissante des sous-chaînes prédéterminées, et, - recevoir la chaîne de caractères et déterminer une position d'un pointeur sur la chaîne de caractères, la position correspondant initialement au premier caractère de la chaîne de caractères, le procédé comprenant de plus les étapes itératives de : déterminer un premier condensat de la sous-chaîne formée par P caractères de la chaîne de caractères à partir de la position du pointeur, - déterminer si une entrée condensat préfixe de la table de hachage correspond à ce premier condensat, si oui, pour chaque longueur des sous-chaînes prédéterminées de la liste associée à ladite entrée condensat préfixe, et dans l'ordre de la liste, déterminer un condensat de la sous-chaîne formée par un nombre de caractères de la chaîne de caractères égal à ladite longueur à partir de la position du pointeur, et, si ledit condensat est égal à un condensat sous-chaîne associé à l'une des sous-chaînes prédéterminées de même longueur, alors : 19 o vérifier que ladite sous-chaîne prédéterminée est égale à la sous-chaîne formée par un nombre de caractères de la chaîne de caractères égal à ladite longueur à partir de la position du pointeur, et, si c'est le cas, o enregistrer ladite sous-chaîne, dite sous-chaîne identifiée, dans la liste 5 ordonnée des sous-chaînes prédéterminées comprises dans la chaîne de caractères, o positionner le pointeur sur la chaîne de caractères à une nouvelle position correspondant à la position additionnée d'un nombre de caractères correspondant à la longueur de la sous-chaîne identifiée, 10 - si non, positionner le pointeur sur-la chaîne de caractères à une nouvelle position correspondant au déplacement d'un caractère sur la chaîne de caractères. 2) Procédé selon la revendication précédente, le procédé comprenant les étapes ultérieures de mise à jour de la liste de sous-chaînes de caractères prédéterminées : 15 - recevoir une sous-chaîne, - déterminer le condensat dit condensat préfixe, en fonction des P premiers caractères de ladite sous-chaîne, - déterminer une entrée dans la table de hachage correspondant audit condensat préfixe, 20 - enregistrer dans la liste ordonnée des sous-chaînes associées à l'entrée déterminée la sous-chaîne, la position dans la liste de la sous-chaîne étant fonction de la longueur de la sous-chaîne, - déterminer et enregistrer un condensat du la sous-chaîne en association avec la sous-chaîne dans la liste. 25 3) Dispositif électronique permettant une analyse lexicale d'une chaîne de caractères, le dispositif électronique comprenant une mémoire dans laquelle est enregistrée une liste de sous-chaînes de caractères prédéterminées, le dispositif électronique étant adapté pour : 30 pour chaque sous-chaîne de caractères prédéterminée, déterminer un condensat, dit condensat préfixe, en fonction des P premiers caractères de ladite sous-chaîne, P étant prédéterminé, pour chaque sous-chaîne de caractères prédéterminée, déterminer, dans une table, dite table de hachage, enregistrée dans la mémoire du dispositif 20 électronique, une entrée correspondant au condensat préfixe associé à ladite sous-chaîne, pour chaque entrée de la table de hachage correspondant à un préfixe, déterminer une liste ordonnée des sous-chaînes prédéterminées associées, chaque sous- 5 chaîne prédéterminée étant associée à un condensat, dit condensat sous-chaîne, fonction de la sous-chaîne prédéterminée, la liste étant ordonnées selon une longueur décroissante des sous-chaînes prédéterminées, et, - recevoir une chaîne de caractères et déterminer une position d'un pointeur sur la chaîne de caractères, la position correspondant initialement au premier caractère 10 de la chaîne de caractères, le dispositif électronique étant de plus adapté pour : - déterminer un premier condensat de la sous-chaîne formée par P caractères de la chaîne de caractères à partir de la position du pointeur, - déterminer si une entrée condensat préfixe de la table de hachage correspond à 15 ce premier condensat, - si oui, pour chaque longueur des sous-chaînes prédéterminées de la liste associée à ladite entrée condensat préfixe, et dans l'ordre de la liste, déterminer un condensat de la sous-chaîne formée par un nombre de caractères de la chaîne de caractères égal à ladite longueur à partir de la position du pointeur, et, si ledit 20 condensat est égal à un condensat sous-chaîne associé à l'une des sous-chaînes prédéterminées de même longueur, alors : o vérifier que ladite sous-chaîne prédéterminée est égale à la sous-chaîne formée par un nombre de caractères de la chaîne de caractères égal à ladite longueur à partir de la position du pointeur, et, si c'est le cas, 25 o enregistrer ladite sous-chaîne, dite sous-chaîne identifiée, dans une liste ordonnée des sous-chaînes prédéterminées comprises dans la chaîne de caractères, ladite liste étant enregistrée dans la mémoire du dispositif électronique, o positionner le pointeur sur la chaîne de caractères à une nouvelle position 30 correspondant à la position additionnée d'un nombre de caractères correspondant à la longueur de la sous-chaîne identifiée, si non, positionner le pointeur sur la chaîne de caractères à une nouvelle position correspondant au déplacement d'un caractère sur la chaîne de caractères. 21 4) Programme d'ordinateur, caractérisé en ce qu'il comprend des instructions pour mettre en oeuvre, par un processeur d'un dispositif électronique, le procédé d'analyse lexicale, selon l'une des revendications 1 à 2, lorsque le programme d'ordinateur est 5 exécuté par le processeur. 5) Support d'enregistrement, lisible par un dispositif électronique, sur lequel est stocké le programme d'ordinateur selon la revendication précédente.