Da stringa a numero tramite conversione di base

Calcolabilità, modelli di calcolo, complessità, linguaggi formali.

Da stringa a numero tramite conversione di base

Messaggioda alfo82 il dom 17 ott 2010, 14:09

Buongiorno,

per prima cosa perdonate il mio linguaggio impropio... la matematica non è il mio forte!

Vorrei capire come è possibile trasformare una stringa alfanumerica in un numero intero; questo per poter confrontare, o meglio
ottenere un valore numerico che indica il "gap" tra due stringhe (alfanumeriche e di differente lunghezza). In rete non ho trovato molti spunti e quel poco che ho trovato non è per me di facile comprensione. Vi riporto uno stralcio della documentazione di un software che permette questo calcolo. E' in inglese ma di facile traduzione. Qualcuno è in grado di spiegarlo meglio magari facendo un ulteriore esempio?

Grazie mille,
AL

---

...uses a per-position base-conversion algorithm to convert a string into a number.
What this really means is that the string is converted to a number using the same
approach that one uses to convert a number of one base (e.g. hex - base 16) to another
(e.g. decimal - base 10). The major difference is that the base can change for each
position/index, according to what characters have actually been observed in that position
throughout the sampled series. This means that if you have a constant character in the
middle of your series, the base ends up being "1", the only possible value in a base-1
number system is 0, and so the constant character plays no part in actually calculating
the numerical value of the total.

Here is a worked example, on a small scale.

Assuming we have the following session ids:

AAAA
AAAC
ABAB
ABAD

Starting from the left-most column (MSB), we have the following observed character sets:

1: "A"
2: "A", "B"
3: "A"
4: "A", "B", "C", "D"

So, our bases are, in order (1,2,1,4).

Let's calculate the value of each id. In order to translate each character to a number,
we use its zero-based position in the sorted character set:

AAAA = 0 * (2*1*4) + 0 * (1*4) + 0 * (4) + 0 = 0
AAAC = 0 * (2*1*4) + 0 * (1*4) + 0 * (4) + 2 = 2
ABAB = 0 * (2*1*4) + 1 * (1*4) + 0 * (4) + 1 = 5
ABAD = 0 * (2*1*4) + 1 * (1*4) + 0 * (4) + 3 = 7

Se invece che queste stringhe utilizzano dei caratteri in squenza ci fosse stato:

R E E E
A A A A
A A A C
A B A B
A B A D
R R R R

In questo caso la lettera R e la lettera E che valore avrebbero? Avrei una cosa del genere:

0 1 2 3 4 5 6
1 A R
2 A B E R
3 A E R
3 A B C D E R

A vale 0
B vale 1
C vale 2
D vale 3
E vale ? (2 o 1 o 5)
R vale ? (1 o 3 o 2 o 6)

Grazie mille,
AL
alfo82
 
Messaggi: 1
Iscritto il: dom 17 ott 2010, 14:06

Messaggioda vict85 il dom 17 ott 2010, 14:40

Il metodo presentato mi sembra abbastanza macchinoso. Non vedo la ragione di usarlo.

Per trovare la distanza tra due numeri puoi usare per esempio la somma dei valori assoluti delle differenze tra i vari elementi della stringa (o il loro quadrato). La codifica del carattere associa automaticamente un numero ad ogni carattere (in memoria una stringa non è altro che un array di numeri). Il metodo che ti presento è quindi abbastanza naturale e abbastanza semplice da implementare. Un po' più complicata è se la differenza la poni case insensitive.

Per quanto riguarda invece una funzione di ugualianza generalmente si pone semplicemente come risultato della funzione la differenza tra la prima coppia diversa.

es.:
AAAAAAA
AAAABCD

Nel mio primo metodo si avrebbe 0+0+0+0+1+2+3=6 oppure 0+0+0+0+1+4+9=14
Nel secondo caso si avrebbe come risultato 1. Questo è il modo in cui sono implementati gli '=' tra stringhe in C.

[edit] Ok, ho capito il senso del programma. Il numero che viene dovrebbe permetterti in teoria di ricavare tutte le stringhe se conosci gli insiemi per ogni elemento di lunghezza. In pratica immagino sia una sorta di sistema di compressione. Immagino che possa essere relativamente efficiente se le stringhe seguono regole abbastanza rigide.

Immagino funzioni così:

Prendiamo le seguenti stringhe

ABCDE
ACDEE
CDAAB
RAAAA
AAAAA

la 'codifica' è:

1 - 'A' 'C' 'R' (3 caratteri) A=0, C=1, R=2
2 - 'A' 'B' 'C' 'D' (4 caratteri) A=0, B=1, C=2, D=3
3 - 'A' 'C' 'D' (3 caratteri) A=0, C=1, D=2
4 - 'A' 'D' 'E' (3 caratteri) A=0, D=1, E=2
5 - 'A' 'B' 'E' (3 caratteri) A=0, B=1, E=2

P.S: riordinare i caratteri invece di scriverli in ordine di comparizione non è indispensabile.
Le basi sono quindi 3,4,3,3,3

si ha:
ABCDE = 0*(4*3*3*3) + 1*(3*3*3) + 1*(3*3) + 1*(3) + 2 = 0*108 + 1*27 + 1*9 + 2 = 27+9+2 = 38
ACDEE = 0*(4*3*3*3) + 2*(3*3*3) + 2*(3*3) + 2*(3) + 2 = 0*108 + 2*27 + 2*9 + 2 = 54+18+2 = 74
CDAAB = 1*(4*3*3*3) + 3*(3*3*3) + 0*(3*3) + 0*(3) + 1 = 1*108 + 3*27 + 0*9 + 1 = 108 + 81+1 = 190
RAAAA = 2*(4*3*3*3) + 0*(3*3*3) + 0*(3*3) + 0*(3) + 0 = 2*108 + 0*27 + 0*9 + 0 = 216
AAAAA = 0*(4*3*3*3) + 0*(3*3*3) + 0*(3*3) + 0*(3) + 0 = 0*108 + 0*27 + 0*9 + 0 = 0

Questo metodo può essere invertito se si conoscono le basi e le codifiche dei caratteri.
Avatar utente
vict85
 
Messaggi: 243
Iscritto il: sab 4 lug 2009, 13:36
Località: Torino


Torna a Fondamenti dell'Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

cron