algoritmo per la generazione di un codice univoco (costante) per una stringa che dovrebbe essere reversibile

Question

Il requisito:

Abbiamo valori nel DB come

Chennai 
Baroda 
Bangalore 
New Delhi 
São Paulo, Lisboa 
San Jose 

ecc ...

quindi voglio per convertire queste stringhe in una stringa breve unica. Ad esempio

Chennai –> xy67kr 

San Jose –> iuj73d 

in pratica qualcosa di simile a URL shortner.

E l'algoritmo per convertire questo dovrebbe essere reversibile .. cioè quando passo "xy67kr" a una funzione di decodifica dovrebbe restituirmi "Chennai".

In cerca di aiuto.

Answer 1

Come altri posters hanno dichiarato, non è possibile avere una funzione che accorcia le stringhe arbitrarie, che è matematicamente impossibile. Ma puoi creare una funzione personalizzata che funzioni bene con il tuo particolare set di stringhe.

Un approccio esempio sarebbe calcolare la frequenza carattere nel set, poi solo codificare i caratteri con un prefix code tale che le lettere più frequenti sono codificati con brevi prefissi (cioè Huffman coding.)

Tale approccio fa non approfittare del fatto che nel linguaggio naturale il prossimo personaggio può essere predetto in modo abbastanza accurato da quelli precedenti, quindi è possibile estendere l'algoritmo di cui sopra in modo che invece di codificare i caratteri in modo indipendente, codifichi il prossimo carattere in un n-grammo. Ciò richiede ovviamente una tabella di compressione più grande rispetto all'approccio semplice, dal momento che si sta effettivamente avendo un codice separato in base al prefisso. Ad esempio se 'e' è molto frequente dopo 'th', quindi 'e' dopo 'th' è codificato con un prefisso molto breve. Se 'e' è molto raro dopo 'ee', allora in questo caso può essere codificato con un prefisso molto lungo. L'algoritmo di decodifica ha ovviamente bisogno di guardare il prefisso attualmente decompresso per verificare come decodificare il prossimo carattere.

Questo approccio generale presuppone che le frequenze non cambino o almeno cambino lentamente. Se il tuo set di dati cambia rispetto a quello che potresti dover ricalcolare le statistiche e ricodificare le stringhe.

Answer 2

Vedi my answer alla domanda simile, e solo riscriverlo a PHP:

Encoding:

$encoded = base64_encode(gzdeflate("São Paulo, Lisboa")) 

decodifica:

$decoded = gzinflate(base64_decode($encoded)) 

Nota che gzdeflate si comporta meglio di gzcompress su brevi stringhe.

Ma in ogni caso il problema è che per le stringhe brevi rende la stringa più lunga. Questo funziona meglio su testi più lunghi. Ovviamente sarebbe meglio utilizzare un algoritmo di compressione con informazioni a priori, come il metodo ppm o suffisso con albero di suffisso iniziale ... quindi funzionerebbe perfettamente anche su stringhe corte.

Answer 3

Non è possibile accorciare le stringhe di lunghezza arbitraria a una lunghezza fissa.

Che cosa è possibile fare è creare quelle stringhe corte per l'ID univoco della riga di quella stringa specifica nel database. Ecco alcuni suggerimenti: How to design a sequential hash-like function.

Answer 4

Questo non è necessariamente deterministico, ma ovviamente è possibile utilizzare una tabella di ricerca. Il servizio sarebbe simile a goo.gl o imgur