Codifica delle stringhe di tipi primitivi che preservano l'ordine lessicografico

Qualcuno sa di una libreria per codificare un numero di tipi primitivi (come interi, float, stringhe, ecc.) In una stringa ma preservando il tipo lexicographical order?Codifica delle stringhe di tipi primitivi che preservano l'ordine lessicografico

Idealmente, sto cercando una libreria C++, ma anche altre lingue vanno bene. Inoltre, si può presumere che il formato non abbia bisogno di essere codificato nella stringa stessa (cioè, se è int64/string/float, allora la stringa codificata non ha bisogno di codificare questa informazione, solo la codifica dei dati è sufficiente).

fonte

2009-11-19 nilton

Potrebbe chiarire ciò che si vuole? –

Cosa intendi per ordine lessicografico rispetto a numeri interi e float? Il loro ordinamento lessicografico dipende da come li si codifica, ad es. binario, ottale, decimale, esadecimale ecc. (supponendo che le cifre iniziali rimosse) daranno tutti diversi tipi lessicografici per una data lista di numeri. –

Per ordine lessicografico intendo l'ordine originale dei tipi primitivi (non la stringa, ovviamente). Dire, codificare "(a, b, c)" in una stringa "s", tale che "(a, b, c) <(a ', b', c ')" implica che "s nilton

Basta scrivere valori numerici in una larghezza di colonna fissa con zero iniziali e stringhe come di consueto. Quindi, in questo modo:

0.1 -> 0000000.1000000 
123 -> 0000123.0000000 
foo -> foo 
X -> X

Poi si può ordinare come testo (ad esempio Unix sort senza -n). Che ne dici di quello?

fonte

2009-11-19 13:02:06

Vorrei evitare di codificare i numeri in larghezza fissa. Inoltre, le stringhe di codifica come se non funzionassero danno il giusto ordine di ordinamento se la stringa ha lo stesso carattere che si sta utilizzando come separatore. – nilton

Quindi scrivi la tua routine di ordinamento. –

Dai un'occhiata a questo documento ("Efficiente codifica lessicografica dei numeri") che mostra come rappresentare qualsiasi tipo numerico come una stringa tale che l'ordine lessicografico delle stringhe sia lo stesso dell'ordine numerico dei numeri sottostanti. Gestisce numeri di lunghezza arbitrari.

http://www.zanopha.com/docs/elen.pdf

fonte

2010-07-29 19:48:34 Peter

Interessante ... sto dando un'occhiata al giornale. – nilton

Appena implementato. I lavori hanno apportato una piccola modifica. Il carattere ASCII ''+'' ha un valore intero 43, che è più basso e ''0'' (valore intero 48). Ciò fornisce una semantica di ordinamento errata. Usando un carattere più in alto nel piano ASCII, come ''='' (valore intero 61) fornisce risultati corretti anche quando si confrontano stringhe con un numero diverso di caratteri di prefisso. –

ho avuto il problema di convertire interi e anela alle stringhe che conservano ordinazione. E poiché stavo lavorando in Java, avevo solo tipi firmati.

mio algoritmo era molto semplice:

flip il bit del segno (toEncode^Long.MAX_VALUE per anela) altrimenti i numeri negativi sono maggiori di numeri positivi.
Esegue una codifica Base64 modificata dei byte. Sfortunatamente, la normale codifica base64 non conserva l'ordine; i caratteri speciali (+ e /) seguono i numeri che seguono i caratteri. Questo è completamente all'indietro da ASCII. La mia codifica modificata utilizza semplicemente l'ordinamento ASCII. (Per far capire che non era Base64 normale, ho cambiato i caratteri speciali per - e _ con ~ come l'imbottitura. Questi sono ancora utilizzabili all'interno di un URL, che era un altro un vincolo che ho avuto.)

fonte

2012-07-07 23:44:58

BTW ... Nel SimpleDB di Amazon Web Service, tutti i dati sono memorizzati come stringhe. I suoi comparatori select usano l'ordinamento lessicografico. AWS fornisce funzioni di utilità per codificare vari tipi. Ad esempio, gli interi sono codificati conoscendo l'intervallo degli interi apriori e regolando tramite riempimento e offset zero (ad esempio per numeri interi negativi). Ovviamente potresti dargli la peggiore gamma possibile.

Vedere "Domanda 201: Trucchi e consigli per Amazon SimpleDB query" - http://aws.amazon.com/articles/1232

http://typica.s3.amazonaws.com/com/xerox/amazonws/sdb/DataUtils.html

fonte

2013-02-19 03:33:37

Codifica delle stringhe di tipi primitivi che preservano l'ordine lessicografico

risposta

Problemi correlati