algoritmo per la sostituzione della sottostringa perfetta

0

Ho una domanda interessante su stringa e delimitatori.

C'è una stringa casuale str .

Ci sono alcuni simboli (o sequenze di simboli) che sono predefiniti e dovrebbero essere temporaneamente sostituiti all'interno di quella stringa dalla funzione replace .

L'operazione dovrebbe essere simile alla sostituzione javascript

  • Step1:

var str1 = str.replace(/abc/g, 'newchar1').replace(/,/g, 'newchar2'); // che sostituisce abc occorrenze e virgole con newchar1 e newchar2 rispettivamente.

  • Fase 2:

Dopo alcuni calcoli faccio le sostituzioni "inverse" facendo

str1.replace(/newchar1/g, 'abc').replace(/newchar2/g, ',');

e si aspetta di avere lo stesso numero di abc e virgole e nelle stesse posizioni di prima di qualsiasi cambiamento.

Come hai capito, ci sono problemi con questo metodo:

newchar1 potrebbe esistere nella stringa precedente. e questo è un problema.

  1. In questo modo ho bisogno di creare un hash casuale per ciascun delimitatore (diciamo una stringa casuale di 4 caratteri) e controllare prima che non faccia parte di una stringa originale.

  2. Inoltre, gli hash per ciascun delimitatore dovrebbero differire l'uno dall'altro.

  3. Inoltre, gli hash non dovrebbero essere parte l'uno dell'altro. Altrimenti guarda cosa succede, se ("aa", "ac", "cd") - 3 hash generati rispettivamente ("abc", ",", "W"). Abbastanza buono? Beh ... Vediamo ... Guarda cosa succede male con questa stringa str : aabcW,kkk ====step1====> aaacdackkk ====step2====> abc,d,kkk. Oh, risultato inatteso - numero diverso di virgole, informazioni perse.

Vedi il problema?

Quindi, qual è l'algoritmo per generare correttamente, ad esempio, cinque hash per sostituire cinque sottostringhe all'interno di una stringa e effettuare l'operazione inversa come descritto sopra senza perdere alcuna informazione?

Qualsiasi algoritmo in javascript ma veloce andrebbe bene. E fornirò la mia soluzione in un istante. Immagino che possano esserci idee migliori.

    
posta Haradzieniec 24.02.2017 - 15:39
fonte

3 risposte

1

Quindi, ecco la mia risposta per Qual è l'algoritmo per generare correttamente chiamiamo cinque hash per sostituire cinque sottostringhe all'interno di una stringa e facendo l'operazione inversa come descritto sopra senza perdere alcuna informazione?

Proviamo ...

Crea la stringa "aaaa ... a" più breve che non si verifica all'interno di una stringa str originale. Lascia che sia "aaaaaa" (sei "a").

Quindi aggiungi un simbolo. Lascia che sia "1". Il primo "hash" per la stringa è pronto: "aaaaaa1aaaaaa".

Il secondo sarebbe "bb1bb" (o "bb2bb" o qualsiasi altra cosa al centro) se nessun bb mets nella stringa.

Il terzo sarebbe "ccc1ccc" (o "ccc9ccc" o qualsiasi altra cosa al centro) se nessun ccc incontra nella stringa (altrimenti, se ccc fa il mets nella stringa, controlla la presenza di quattro cccc e usa "cccc9cccc" ).

I quattro sarebbero "dddddddd1ddddddddd"

E il quinto sarebbe "e1e" (se non ci sono caratteri "e" soddisfatti in str ).

Possibili domande / commenti per il mio algoritmo sopra:

  1. Perché ho bisogno di "aaaaaa1aaaaaa" ma non di "aaaaaa"? questo perché "a" può essere incontrato subito prima del primo "delimitatore". Non voglio prendere sul rovescio il primo ma non ultimo da "aaaaaa". Ecco perché suggerisco "aaaaaa1aaaaaa".

  2. Per rendere più brevi questi hash, è possibile utilizzare due lettere (non una) per creare hash: diciamo qualsiasi combinazione di lettere (a, b) per il primo "hash", (c, d) per secondo hash e così via. Gli hash prevedevano di avere meno byte in media.

Ti piace il mio algoritmo o mi manca qualcosa? E dovrebbe essere abbastanza veloce in JavaScript da generare.

Qualsiasi commento è molto apprezzato. Grazie.

    
risposta data 24.02.2017 - 16:07
fonte
1

Suggerirei un approccio diverso. Ci sono due caratteri Unicode in Basic Multilingual Plane (BMP), U + FFFE e U + FFFF, che sono riservati, non rappresentano i caratteri reali e che Unicode dice sono intesi per usi interni al processo .

Poiché nessuna stringa Unicode valida può contenerli, puoi rimuovere quelli presenti nel tuo input, usarli (o combinazioni di essi) come sostituti e quindi sostituire le stringhe originali per loro alla fine senza preoccuparti che ci siano occorrenze valide di essi nella stringa.

Esistono altri caratteri non Unicode che potrebbero essere utilizzati. Vedi i caratteri Unicode Private-Use, Noncharacters & Domande frequenti sulle sentinelle per ulteriori informazioni. Nota che se usi non caratteri devi usarli solo internamente; devono essere rimossi dal testo prima di salvarlo, inviarlo o altrimenti passarlo a qualcun altro.

    
risposta data 25.02.2017 - 19:12
fonte
0

Con utf-16 hai 1,112,064 caratteri. Quindi ogni stringa più breve di un milione di caratteri ti darà più di centomila possibili caratteri sostitutivi.

In generale, non penso sia possibile creare segnaposti unici semplicemente aggiungendo carattere a loro. C'è sempre una stringa che, quando viene convertita, dà un risultato ambiguo.

    
risposta data 24.02.2017 - 17:51
fonte

Leggi altre domande sui tag