Catene di parole
Word chains

di leonardo maffi
by leonardo maffi

Ultima revisione: 16 Aprile 2005
Last revision: April 16 2005

Programma Python - Python program: word_chains.zip

Ho affrontato in Python il Katà di programmazione n.9:
http://blogs.pragprog.com/cgi-bin/pragdave.cgi/Practices/Kata
Ecco il problema: costruire una catena di parole, che inizia con una parola specificata, e termina con un'altra specificata. Gli elementi della catena devono essere tutti parole reali, e possono differire dalla precedente parole solo per una lettera. Tutte le parole di una catena devono avere la stessa lunghezza. Esempio, da cat a dog:
cat cot cog dog
Questo programma deve accettere in input una parola di partenza, e una di arrivo, e usando le parole da un dizionare, deve restituire la catena di parole più corta tra loro.

I've tried with Python the code kata #9:
http://blogs.pragprog.com/cgi-bin/pragdave.cgi/Practices/Kata
Problem: build a chain of words, starting with one particular word and ending with another. Successive entries in the chain must all be real words, and each can differ from the previous word by just one letter. Words of a chain must all have the same length. Example, from cat to dog:
cat cot cog dog
This program must accept start and end words and, using words from the dictionary, return the shortest word chain between them.

Se affrontato male, in Python questo programma può risultare molto lento, per la notevole lentezza di questo linguaggio. Ma con alcune accortezze, può risultare veloce, compatto, e abbastanza semplice da capirsi. Per risolvere il problema ho deciso di usare la mia libreria Graph, e il suo metodo shortestPath. Questa è la routine principale che ho scritto per risolvere il problema (conversione in html ottenuta con una mia modifica di PySourceColor di M.E.Farmer Jr.):

def generateWordsGraph(words):
    d, daw = {}, {}
    g = Graph()
    for w in words:
        g.addNode(w)
        alternativeWords = [ w[:i]+"*"+w[i+1:] for i in xrange(len(w)) ]
        daw[w] = alternativeWords
        for wa in alternativeWords:
            if wa in d:
                d[wa].add(w)
            else:
                d[wa] = set([w])

    for w in words:
        l = set()
        for wa in daw[w]:
            l.update(d[wa])
        for n in l:
            g._fastAddBiArc(n, w, 1) # 1 is the arc weight. This creates absent nodes too.
    return g

Per velocizzare notevolmente (passare da una complessità quadratica ad una lineare ammortizzata) ho usato un dizionario (hash), creando varianti di una parola nelle quali una lettera è sostituita da *.

Usando un dizionario contenente solo le seguenti parole:
words = """Bill ball call came care cold come face fact fall fast find fine fire five food foot full game gave give gold good have held help hold home kind last life like line list live mind name part past same some talk tall tell than that them then they told walk well what when wild will wind""".split()

Otteniamo un grafo di questo tipo (ottenuto dal programma word_chains1.py con l'ausilio di GraphViz):


Immagine ottenuta da word_chains1.py col buon GraphViz:
Image produced by word_chains1.py with the good GraphViz:
http://www.research.att.com/sw/tools/graphviz/

Qui si possono vedere i sorgenti dei due programmi Python, differiscono di poco, il secondo (word_chains2.py) è più ottimizzato, e adatto a dizionari di dimensioni reali. (Si noti che word_chains2.py utilizza funzioni di basso livello sul grafo e inizializza solo gli archi uscenti da ogni nodo. Quindi se si desidera effettuare varie elaborazioni del grafo conviene prima rigenerarlo con una g._regenerate()): word_chains1.py     word_chains1.py

Su un dizionario di più di 45400 parole (allegato ai sorgenti), con Python2.4 su un PentiumIII a 500MHz, il programma impiega circa 9.5s per generare il grafo (la ricerca di un percorso ottimale avviene poi con una routine che implementa l'algoritmo di Dijkstra, scritta da Eppstein, che gira in pochi decimi di secondo). Il grafo può anche essere salvato e caricato molto velocemente su/da disco.

Un breve studio del grafo ottenuto dal dizionario completo

Per prima cosa rigenero gli archi entranti del il grafo, in modo da averlo completo:

>>> g._regenerate()

Poi creo una lista che contiene la lunghezza ordinata delle componenti connesse del grafo:

>>> cc = sorted( map(len, g.connectedComponents()) )
>>> len(cc)
30289

Come si vede il grafo è composto da moltissime parole isolate, e poche componenti molto grandi:

>>> [cc.count(i) for i in xrange(1,25)]
[26351, 2766, 670, 205, 104, 50, 28, 21, 18, 13, 11, 1, 6, 6, 1, 2, 7, 2, 1, 1, 1, 0, 4, 3]
>>> cc[-21:]
[23, 24, 24, 24, 25, 27, 28, 30, 35, 38, 94, 131, 148, 188, 222, 337, 501, 572, 1686, 1916, 2537]

Col buon MatPlotLib si può visualizzare l'istrogramma di una parte di cc:

>>> from pylab import *
>>> hist( filter(lambda x: x<8, cc), 8 )


Questo è il programma completo:
This is the complete software:
word_chains.zip

[Vai all'indice - Go back to index]

Pagina visitata volte dal 16 aprile 2005.