Newsgroup: it.scienza.informatica
Titolo: string to numeric

Qualcuno mi sa dare una mano?
Devo produrre un algoritmo che ricevendo in input una stringa di 
caratteri, deve produrre in output un numero intero.
La funzione deve fare in modo che non vi siano due stringhe
che vanno a generare lo stesso numero.
Nella stringa sono ammessi tutti i 26 caratteri alfabetici, i 10
caratteri numerici, lo spazio e l'underscore. Totale 38 simboli.
La lunghezza della stringa, in generale non dovrebbe mai superare i 
13 caratteri, ma il massimo consentito è 20.
Il vero problema è che il numero intero che viene restituito 
lo devo memorizzare in una variabile "integer" di 4 byte.
Grazie da subito a chiunque riesca a darmi qualche dritta.
Ciao
Stefano Lessi

]

 Stefano Lessi
--
--------------------------------------Stefano Pancaldi-------
  Work:
       Xtel Srl    Centergross-Funo Blocco 4a Galleria b n°56
       Tel  
+39 051862706
------s...@xtel.it--------------------------------------

 lo devo memorizzare in una variabile "integer" di 4 byte.
Apparentemente il problema è senza soluzione!
Per generare un numero che sa univoco per ogni possibile stringa, hai per
forza bisogno di log2 (38*20) bits, certo molti di più di quelli contenuti
in 4 bytes!
L'unica cosa che mi viene in mente è di analizzare le stringhe per sapere
cosa conterranno, quindi cambiare il meccanismo di "conta" delle stringhe,
in modo da portare oltre il limite dei 4 bytes solo quelle che hanno una
probabilità molto bassa di essere generate.
Se, per esempio, la stringa contiene una parola italiana, allora potresti
contare in ordine tutte le parole che hanno al massimo 13 (o 20) caratteri,
e quindi salvare solo il numero (credo che le parole italiane siano in tutto
meno di 4 miliardi gestibili con 4 bytes).
Se poi riduci il numero di parole ammesse, puoi avere fino a 2 parole scelte
tra 65'565 del vocabolario e separate da spazio. Se poi riduci ancora, puoi
avere a disposizione anche 1 bit per decidere se sono separate da uno spazio
o da un undersore. Se poi riduci ulteriormente, puoi ammettere anche 1 cifra
(5 bit), ecc.
Al limite, puoi costruirti un cifrario di tutte le sillabe ammesse dalla
lingua italiana (un sillabario?), e partire da lì. Quante saranno? se sono
meno di 64, bastano 6 bit per sillaba, altrimenti 7, ecc.
Un miglioramento potresti anche ottenerlo, magari in congiunzione con i
metodi sopra esposti, comprimendo i dati. Ovvero: essendo la sillaba "qua"
molto più rara che la sillaba "ar", potresti dedicare un numero di bit
diverso.
Oppure ancora, senza perdere in generalità, puoi affidarti a qualche
meccanismo di compressione già esistente e tarato per la lingua italiana,
con codifica ridotta per usare il tuo numero di simboli ridotto. Ovviamente
la tabella di compressione/decomp deve essere già nota.
Una piccola nota: a meno di avere qualche conoscenza specifica sul testo,
non è possibile "comprimere" 20 caratteri nello spazio normalmente occupato
da soli 4 caratteri. Questo perchè la rappresentazione dei caratteri sui PC
è già abbastanza compressa in partenza. Mi spiego meglio: se tu avessi le
stringhe in Unicode (2 bytes per carattere) potresti dire che 1 bytes è
totalmente sprecato, a patto di conoscere già il set di caratteri.
Per il codice ASCII, ogni carattere utilizza 7 bits, che permettono 128
diversi caratteri. Questi comprendono le 26 lettere dell'alfabeto inglese,
maiuscolo e minuscolo (52), le cifre (10), e alcuni segni di interpunzione
(10?). Il totale fa già così 72 simboli, che non possono essere contenuti in
6 bit, rendendo così necessaria una codifica a 7 bit. Poichè, a questo
punto, rimangono a disposizione altri 58 simboli, aggiungiamo pure alcune
lettere accentate, alcuni codice di controllo, e alcuni simboli grafici,
dato che sul computer ogni tanto è carino vedere il testo incorniciato o
sottolineato. Ah, mettiamoci pure i simboli matematici: 4 per le operazioni
matematiche,il maggiore, il minore, l'uguale e le parentesi, che servono
anche per il testo!
Come vedi, la situazione più generale possibile deve utilizzare almeno 7 bit
per carattere, e pensare di utilizzarne di meno è piuttosto difficile.
Un consiglio finale: ma come è possibile che sia davvero necessario
convertire 20 caratteri in 4 bytes? Non è che questo sia un vincolo
"mentale", piuttosto che una limitazione del progetto? Trovo difficile che
tra le specifiche di un progetto vi sia una cosa tanto assurda. (sempre, a
meno che non si abbia una conoscenza molto precisa di quali siano le
stringhe ammesse e che queste siano limitate in numero) Io proverei a
ripensare al tutto, cercando di risparmiare i bytes da un'altra parte, se
proprio si deve farlo.
--
Alessandro Monti

lo devo memorizzare in una variabile "integer" di 4 byte.
Con 20 cifre, anche solo accettando i numeri e non i caratteri
dell'alfabeto, esistono 10^20 diversi valori, mentre con 4 byte si
possono rappresentare "solo" 2^32 (=circa 4*10^9) valori differenti.
Quindi o diminuisci la lunghezza delle stringhe, o aumenti la
dimensione della variabile numerica ove memorizzi il risultato.
Ciao,
      __
     (__
      __)tefano.