Complexité : décomposition des nombres

Bonjour à tous !

Dans mon application de reconnaissance vocale, je remarque que lorsque je lui dit de reconnaitre le nombre "12 345" (avec un espace) (nombre spécifié dans la grammaire qu'il charge), le temps de reconnaissance est beaucoup plus long que lorsqu'il lit "12345" sans espace.

J'ai aussi remarqué que lors du chargement de mon fichier, lorsqu'il contient un nombre non formaté (sans espace), le temps de chargement est beaucoup plus long, multiplié par 4 ou 5 (je n'ai pas pu obtenir de mesure précise, et c'est ce qui me manque ...

J'en déduis que le moteur de reconnaissance décompose chaque nombre de toutes les façons possibles de le dire (12345, 12 345, 1 2345, 1 2 3 4 5, ...). Et qu'en formatant le nombre avec un espace, je réduis ainsi les possibilités de prononciations. Bref.

Quelle pourrait être la complexité en temps de reconnaissance d'un tel nombre en fonction de sa longueur ?

Ca revient à énumérer toutes les parties de ton ensemble constitué de tes n digits :

123 : {{123}, {1, 23}, {12, 3}, {1, 2, 3}}

=> 2^n

Edit : En fait je pense pas que ça réponde à ta question (que je ne suis pas sûr de comprendre :D)

Je pense que tu m'offres un élément de réponse :D


Je cherche surtout à identifier le temps que je perds à donner à mon moteur le nombre "123456" (sans espace) plutôt que le nombre "123 456" (avec espace).

Dans le premier cas, il va donc (thériquement) avec une complexité temps de 2^6 pour charger, soit 64.

Dans le second, il aura une complexité temps (à quelque chose près) de 2 * 2^3, soit 16.

Ce qui représente 4 fois moins de temps pour un nombre formaté. Ca correspond à peu près à ce que je trouve en temps de chargement avant/après.

Il s'agissait d'un problème de conception, maintenant j'y vois plus clair. Je te remercie :D

Citation:

---

Envoyé par Furikawari

123 : {{123}, {1, 23}, {12, 3}, {1, 2, 3}}

=> 2^n

---

Sauf que ce que tu proposes là, ça ne fait pas 2^n mais 2^(n-1), mais c'est la même idée :mrgreen:

y'en manquent : ensemble vide, {13, 2}, etc...

Mais la formule est la bonne.

Non non ce n'est pas le cas d'un langage normal : il faut s'imaginer que "123456" sera lu par l'utilisateur comme étant une référence. Donc les chiffres seront dit dans cet ordre, mais il existe différentes façons de le dire :

• cent vingt trois mille quatre cent cinquante six

• cent vingt trois, quatre cent cinquante six

• un deux trois quatre cinq six

etc.

C'est pour ça que la première décomposition que tu as donné est la bonne :)

Je suis désolée si je n'ai pas été claire sur le contexte. N'hésite pas si tu veux d'autres détails.

Ouh là, ça m'apprendra à faire des exemples aussi bêtes :D

Première réponse rapide, c'est la somme des C(n-1,p), avec n ton nombre de chiffres, et p qui varie entre 1 et n-1. Ce sont toutes les façons que tu as d'insérer des espaces dans ta chaîne.

Je pense que cette somme a une solution simple, mais je m'en souviens pas :D
Je cherche un peu, mais nul doute que qulequ'un ici connaîtra la réponse.

Edit: c'est n-1 le coefficient, pas n, on s'intéresse aux intervalles, pas aux piquets ;)

Bon, il se pourrait que je sois nul en maths et que ce soit 2(n-1)-1 (le -1 est si tu ignores la chaîne sans espace), à valider par un fort en thème du fofo.