arbre lexicographique

Regarde ça, si ça ne pourrait pas t'aider :

http://effbot.org/zone/element-index.htm

Marc <mdt@noos.fr> writes:

Bonjour,

Tout nouveau dans Python. Comme exercice je cherche à faire un arbre
lexicographique. Cad un arbre des lettres d'une série de mots.

par exemple à partir des mots:

balle
ballon
bals
bas

on obtiendrait quelque chose comme ça:

b->a->l->l->e
| | |
| | -->o ->n
| |
| -->s
|
-->s

Quelle type de données utiliser? Liste? Dictionnaire?
Comment écrire une fonction récursive?

en gros:

def append_word(tree, word):
if len(word):
char = word[0]
if not tree.has_key(char):
tree[char] = {}
append_word(tree[char], word[1:])

def make_tree(tree, words):
for w in words:
append_word(tree, w)

def dump_tree(tree, indent=0):
for c in tree.keys():
print " " * indent + c
dump_tree(tree[c], indent + 2)

words = ['balle', 'ballon', 'bals', 'bas']
tree = {}
make_tree(tree, words)
dump_tree(tree)


--
js

Le 23/12/2004 20:53, dans 87brckzt81.fsf@mouret.org, « Jean-Sebastien
Mouret » <js@mouret.org> a écrit :

en gros:

def append_word(tree, word):
if len(word):
char = word[0]
if not tree.has_key(char):
tree[char] = {}
append_word(tree[char], word[1:])
[etc]

Merci beaucoup (et à Michel Claveau) c'est exactement ce que je n'arrivais
pas écrire...

je suis soufflé par la concision de Python :-)

je vais essayer maintenant de construire mon arbre à partir d'un fichier
texte. Ça ne devrait pas poser trop de problème.

Marc (newbie)

#!/usr/bin/python



class node :
def __init__(self) :
self.desc = {}
self.IsWord = False
def add(self,word):
print "add",self, word
if word == "" : self.IsWord = True;return
initiale = word[0]
if not initiale in self.desc.keys() : self.desc[initiale] = node()
self.desc[initiale].add(word[1:])
def affiche(self) :
print self, self.IsWord
for i in self.desc.keys() :
self.desc[i].affiche()
def cherche(self,word) :
if word == "" : return self.IsWord
initiale = word[0]
if not initiale in self.desc.keys() : return False
return self.desc[initiale].cherche(word[1:])






n = node()
n.add('poi')
n.add('mlk')
n.add('mlklk')
print n.cherche('poi')
print n.cherche('poim')
print n.cherche('mlk')
print n.cherche('mlklk')
print n.cherche('mllk')