Faire des automates avec PHP?

20 juil. 2009, 10:57

Bonjour tout le monde,

J'ai besoin d'appliquer la grammaire formelle pour créer des automates (à états finis) qui reconnaissent les phrases françaises en sortant les mots clés importants dans chaque phrase, est-ce que c'est possible avec PHP?

Par exemple, pour la question "quel temps fait-il demain à Paris?", les mots que je veux trouver sont: "temps", "demain" et "Paris".

Merci!

20 juil. 2009, 11:13

Hey

,

Bien sûr qu'on peut faire des automates en PHP, pourquoi on ne pourrait pas ?
Mais faut pas être presser par contre … Je l'ai fait sur des petites données, mais sur des grosses, tu laisses tomber (c'était dans le cas d'un compilateur en PHP, si si).

Mais pour ton problème, peut-être qu'on peut le résoudre plus simplement en utilisant soit les expressions régulières (qui ne sont que des automates hein), soit un bête strpos() ?

20 juil. 2009, 12:22

Bonjour HyWaN,

Je dois traiter des petites phrases, donc des petites données comme tu disais. Mais c'est pas possible d'utiliser les expressions régulières, parce que je dois appliquer des règles de grammaire à mon programme pour trouver les mots.

Par exemple, pour la phrase "Quel temps fait-il demain à Paris?".
D'abord je la passe par TreeTagger (écrit en Perl) pour avoir un analyse en chunks:

Code : Tout sélectionner

<s>
<AP>
quel	PRO:INT	quel
</AP>
<SENT>
temps	NOM	temps
</SENT>
<VN>
fait	VER:pres	faire
-il	PRO:PER	il
demain	ADV	demain
</VN>
<PP>
à	PRP	à
<NP>
Paris	NAM	Paris
</NP>
</PP>
?	SENT	?
</s>

Puis je dois appliquer une grammaire, telle que:

S -> AP SENT VN PP
AP -> pro:int
SENT -> nom
VN -> ver:pres
VN -> adv
PP -> NP
NP -> nam

Le but est d'avoir à la fin: le nom commun ("temps"), l'adverbe ("demain") et le nom propre ("Paris").

Est-ce que tu vois le moyen de résoudre ce problème?

Merci beaucoup!

20 juil. 2009, 12:35

Bah avec un automate, ça roule nickel. Si tu dois traiter des petites données, PHP peut très bien le faire.
Tu peux utiliser une structure par listes d'adjacences pour ton automate, ça correspond bien à ton besoin et PHP peut très très bien le gérer. Ensuite tu l'appliques sans problème.

20 juil. 2009, 12:43

Tu peux utiliser une structure par listes d'adjacences pour ton automate, ça correspond bien à ton besoin et PHP peut très très bien le gérer. Ensuite tu l'appliques sans problème.

Oulaa, désolé mais c'est trop "abstrait" pour moi

Que veut dire "une structure par listes d'adjacences"?

20 juil. 2009, 14:18

Bah, tu pensais le programmer comment ton automate … ?

Une liste d'adjacence pour un automate (pour un graphe c'est plus simple), c'est un truc de ce genre là :

Code : Tout sélectionner

array(
    0 => array(
        'a' => array(0, 1, 4),
        'b' => array(2),
        'c' => array()
    ),
    1 => array(
        'a' => array(0, 4),
        'b' => array( …
    ),
    …
    4 => array( …
);

Tu as 2 dimensions et une liste. Ça se lit comme ça : soit A ton alphabet, et S tes états, alors : alors pour chaque état i ∈ S (ici de 0 à 4), si on prend la transition ß ∈ A (ici de 'a' à 'c'), alors on peut atteindre l'état j ∈ S. Cette représentation est utile si ton automate n'est pas déterministe (donc que tu as une fonction de transition, et pas une relation, comprendre que tu peux avoir plusieurs états possibles pour une seule transition), et peut se simplifier si ton automate est complet.

Si ton automate est à coup sûr déterministe, tu peux le coder par matrice d'adjacence. Ça ressemble à ça :

Code : Tout sélectionner

array(
    0 => array('a' => 1, 'b' => 4, 'c' => 2),
    1 => array(…
);

Ça se lit : on est en 0, on utilise b pour aller vers 4.

Dans tous les cas, il te faut des tableaux pour coder tes états initiaux et terminaux, mais tu t'en serais douté tout seul. Un bête tableau :

Code : Tout sélectionner

array(
    0 => true,
    1 => false,
    2 => true,
    …
);

suffit à dire si un état i est initial ou terminal selon ton tableau.

Je passe les théories sur les complexités en temps et en mémoire. Je t'ai dégrossi le travail, à toi d'approfondir si tu veux aller plus loin (ou me demander

).

20 juil. 2009, 18:28

Caml les gars, caml

20 juil. 2009, 18:32

Des automates en Caml … en C c'est mieux

.

20 juil. 2009, 19:01

Des automates en Caml … en C c'est mieux .

Ah mais tu prêches un converti !

Tout est mieux en C :p
(D'ailleurs faudra que je pense à faire mon premier site web en C

)

21 juil. 2009, 06:52

Merci HyWaN, je vais réfléchir plus sur ce que tu m'as dit.

Oui je sais qu'on peut faire avec C, mais je connais très peu C/C++, alors je souhaite arriver à faire avec PHP, comme c'est un langage que j'aime bien

21 juil. 2009, 09:57

Tu ne penses pas si bien dire Sékil', je voulais arrêter Hoa pour me lancer dans un framework Web écrit en C y a pas longtemps …

Et Doviet, tu as raison te t'amuser à faire ça en PHP. Il peut très bien le supporter et ça change des utilisations basiques qu'on en a. PHP a un fort potentiel très souvent inconnu …

21 juil. 2009, 11:42

Tu ne penses pas si bien dire Sékil', je voulais arrêter Hoa pour me lancer dans un framework Web écrit en C y a pas longtemps …

PHP, c'est pas un framework web écrit en C ^^ ?

21 juil. 2009, 11:55

On peut déjà dire ça uè, très bien vu

.

21 juil. 2009, 12:12

Cher HyWaN,

Qu'est-ce qu'on utilise pour faire fonctionner l'automate? une fonction récursive? une boucle?

Et... on n'a toujours qu'un état initial, non?

Je n'ai suivi que quelques cours de grammaire formelle (un plus, trop théoriques, je n'arrive pas bien à suivre), je ne maitrise pas les théories des automates. Alors je peux te poser des fois des questions très bêtes, j'espère que ça ne te gènera pas.

21 juil. 2009, 14:17

Tu ne penses pas si bien dire Sékil', je voulais arrêter Hoa pour me lancer dans un framework Web écrit en C y a pas longtemps …

Et Doviet, tu as raison te t'amuser à faire ça en PHP. Il peut très bien le supporter et ça change des utilisations basiques qu'on en a. PHP a un fort potentiel très souvent inconnu …

Euh :
1/ T'aurais arrêté hoa ? Et tes utilisateurs ?
2/ Un framework C, pour quoi faire ? Pas des sites Web rassure moi ?

Faire des automates avec PHP?

Qui est en ligne