Newsgroup: it.scienza.informatica
Titolo: [a bit long] tastiera ottimizzata sul testo...

Qualche sera fa un amico mi si è avvicinato e complice il mio stato di
alterazione alcolica mi ha proposto un problemino che da allora continua a
perseguitarmi nei momenti un cui la mente è libera.
Dato un testo si vuole determinare quale sia la migliore disposizione dei
tasti sulla tastiera in modo da ridurre al minimo gli spostamenti di un
eventuale digitazione (assumo a dito singolo per semplicità). In sostanza
salvando la forma su tre righe e considerando solo le lettere (26) per
semplicità qual'è la successione delle stesse lungo le righe che garantisce
minori spostamenti per una testina battente?
Premetto che non sono un esperto di computer science, ma tuttavia la mia
qualifica di ingengnere mi consente di delineare alcune strategie:
1)Strategia brutale.
Si scandiscono tutte le possibili tastiere valutando il numero di passi
reativo al testo in analisi ed alla fine si ottiene la soluzione ottima.
Purtroppo questa soluzione ha il difetto di essere np al crescere del numero
delle lettere e se andrebbe a stento bene per la tastierina numerica (9!
combinazioni ossia 360k combinazioni) è improponibile per la tastiera
alfabetica (26! combinazioni circa 4 10^26).
2)Strategia risolutiva.
Analizzando il testo si determinano un bel po' di fattori di correlazione
(26*25 a considerare tutte le relazioni) fra le lettere e si costruisce a
partire da questi la tastiera ottimale. Ovviamente non sono in grado di
esprimere un tale algoritmo con chiarezza, ma tendo ad immaginare (e
sperare) che un problema di sort come questo sia stato analizzato in
letteratura.
3)Soluzione brutale sub-ottima (o presunta tale)
Ponendo dei vincoli (dettati dall'osservazione empirica dal buon senso o
dalla statistica) si può cercare di eliminare dall'analisi i rami morti
ponendo dei vincoli strutturali. Per esempio si possono arbitrariamente
relegare le lettere meno ricorrenti agli estremi della tastiera e quelle
maggiormente utilizzate nelle posizioni centrali. Altri vincoli portebbero
essere la non consequenzialità di vocali o consonanti dal ruolo simile tipo
p e b che mai saranno consecutive in un testo italiano. Riducendo la
complessità del problema si può ricorrere ad un meccanismo di valutazione
dei risultati ma con la garanzia di una soluzione sub ottimale (peggiore o
uguale a quella ottima a seconda della bontà dei vincoli)
4)Metodo permutativo
Si parte da una tastiera di default diciamo statisticamente adattata a testi
in italiano. Poi si definisce un indice come per esempio il rapporto fra il
numero di spostamenti della testina e il numero di lettere. A questo punto
si assegna un valore da raggiungere per tale indice e si prosegue per
permutazioni casuali preservando solo quelle che provocano una diminuzione
dell'indice. Purtroppo tale metodo è inutilizzabile estrapolato da una
dimostrazione di convergenza di un tale algoritmo (convergenza invero molto
dubbia) e dalla dimostrazione della possibilità di far scendere
arbitriamente il livello. Immagino che si possano trovare teoremi per dare
estremi ai valori assumibili dall'indice (sicuramente nella teoria numerica
sui codici qualcosa del genere è presente).
Per ora non mi viene in mente altro. Se siete a conoscenza di come si
affronti correttamente tale problema fatemelo sapere.
Trini.
----------TAF----------
Se ti disegnassi una linea in faccia sembreresti proprio un culo
Trini alla frutta aka potenza del pesante (abbonato nord n°833)
ICQ number 15461418
Homepage 
http://utenti.lycos.it/triniallafrutta

affronti correttamente tale problema fatemelo sapere.
ti dico il criterio usato in dattilografia: le lettere piu' frequenti
nei punti corrispondenti agli attuali F e J, poi D e K e cosi' via
sino a completare la riga, poi passa analogamente alle righe sopra e
sotto

 [....]
E' un problema di Ricerca Operativa. Cosi' "a occhio" si risolva con un
simplesso intero. Chiaramente rimane un problema combinatorio, ma un
algoritmo del simplesso intero puo', in media fornire prestazioni piu'
ragionevoli rispetto al metodo di ricerca esaustiva che proponi tu.
Ciao. Federico.

 Ciao. Federico.
Scusa l'ignoranza ma cosa sarebbe un "simplesso intero"?... E' il genere di
cosa che rimpiango di non sapere, con un simile nome deve essere realmente
significativo...
Come alternativa (sia pure in via teorica) sto vagliando il ricorso ad un
processo di selezione evoluzionistico con un centinaio  di tastiere in vita.
Delle quali le migliori passerebbero alla generazione sucessiva insieme ad
altre date dalla combinazione delle genitrici (riproduzione sessuata) ed
infine un piccolo gruppo ottenuto mutando alcune tastiere di partenza in
modo casuale. Ritengo che un buon balancing dei fattori #tastiere in vita
%(preservate combinate mutate) e #generazioni dovrebbe condurmi se non nel
fosso della soluzione minima almeno nelle sue vicinanze.
Cosa ne pensate?
Trini

 Cosa ne pensate?
Ricerca di minimo con un algoritmo genetico, mi sembra. Puo' funzionare.
Ma fors e' meglio ottimizzare la soluzione che proponevi in precedenza (=
tentare tutte le possibilita'), con una ottimizzazione di tipo branch&bound.
Ogni volta che scendi di un livello nell'albero delle soluzioni (=branch,
cioe' quando assegni un tasto) puoi gia' stimare un costo minimo (=bound)
della tua soluzione. Se tale costo e' maggiore della migliore soluzione
trovata sino a quel momento e' inutile proseguire; l'intero sottoalbero non
potra' avere soluzioni migliori.
Federico.