Convertir la cadena a otra cadena a través de una más pequeña del alfabeto, y viceversa.

Question

Estoy tratando de encontrar el más adecuado algoritmo para convertir una cadena de caracteres $\alpha$ sobre el alfabeto $\Sigma$ del tamaño de la $| \Sigma | = n$ string $\beta$ sobre el alfabeto $\Omega$ del tamaño de la $| \Omega | = n-1$, y viceversa. Mediante una adecuada quiero decir que el balance de algoritmo de velocidad, la implementación de la complejidad y la sobrecarga de la longitud de la cadena de $| \beta | - | \alpha |$.

He encontrado varios algoritmos, pero tal vez hay algunos desconocidos para mí. Tal vez usted sabe que este tipo de algoritmos. He aquí lo que he encontrado:

1. Convencional byte (carácter) relleno. Bastante simple, pero el peor de los casos los gastos generales es de 200%.
2. Consecuente sobrecarga de bytes de relleno (MAZORCAS). También es bastante fácil de implementar. El peor caso de sobrecarga es mucho mejor que los convencionales de bytes de relleno.
3. Pensar en la cadena de entrada como de un largo número de base $n$, convertir este número en base $n-1$. Muy complejo y computacional pesados en comparación con los métodos anteriores, pero de los peores casos de sobrecarga es mejor si no me equivoco.

Cualquier otra cosa?

Answer 1

No estoy seguro de si esto cuenta, pero es una idea que podría estar interesado en. En aplicaciones del mundo real, se puede identificar una cadena en la $\Omega$ alfabeto que nunca jamás surgir en un mensaje real. Ni en el $\Omega$ alfabeto, ni en el $\Sigma$ alfabeto después de que el simple incrustación de$\Omega$$\Sigma$. A continuación, puede utilizar la cadena para representar una letra de $\Sigma$.

Vamos a decir $\omega$ es una cadena, algo así como "fhqwhgads" en inglés, a pesar de que usted podría conseguir lejos con algo más corto. Para la notación, vamos a $$\Sigma=\{s_0,s_1,\ldots, s_{n-1}\}\qquad\Omega=\{w_1,w_2,\ldots,w_{n-1}\}$$

A continuación, mapa $$\DeclareMathOperator{\strings}{strings}f:\strings(\Sigma)\to\strings(\Omega)\quad f(s_i)=w_i\text{ when }i>0\quad f(s_0)=\omega$$ The inverse map would first examine a string $\beta$ for instances of $\omega$ and convert them to $s_0$, and then convert remaining $w_i$ to $s_i$. This relies on you knowing that $\omega$ nunca prácticamente surgir en un verdadero mensaje de alfabeto.

Answer 2

Esto es probablemente lo que usted está buscando en (este un sitio de matemáticas, no de una programación de sitio), pero de todas formas: una simple convencional de bytes de relleno algoritmo con una entrada desplazamiento (cada vez que necesitamos para "escapar", le cambio el desplazamiento, así como a miminize la probabilidad de que el peor de los casos). Sobrecarga (promedio) debe ser inferior a 1%. Probado.

Codificador:

/********************  encode. c **************************/
#include<stdio.h>

#define N 255                   //restricted alphabet 
#define NP1 (N+1)

#define DISALLOWED_CHAR 0 // only restrction: these three must be different 
#define ESCAPE_CHAR     1
#define ESCAPE_CHAR2    2

#define STEP            7 // any number, preferably coprime with NP1

int offset = 0;

void txraw(int c) {
    putchar(c);
}

void tx(int c) {
    c = (c + offset) % NP1;
    if (c == DISALLOWED_CHAR || c == ESCAPE_CHAR) {
    txraw(ESCAPE_CHAR);
    txraw(c == ESCAPE_CHAR ? ESCAPE_CHAR : ESCAPE_CHAR2);
    offset = (offset + STEP) % NP1;
    } else {
    txraw(c);
    }
}

int main(void) {
    int c;
    while ((c = getchar()) >= 0) {
    tx(c);
    }
    return 0;
}

Decodificador:

/********************  decode. c **************************/
#include<stdio.h>

#define N 255                   //restricted alphabet 
#define NP1 (N+1)

#define DISALLOWED_CHAR 0 // only restrction: these must be different 
#define ESCAPE_CHAR     1
#define ESCAPE_CHAR2    2

#define STEP            7

int offset = 0;
int pendingEsc = 0;

int decode(int c) { // -2 if more to read
    int oo = offset;
    if (pendingEsc) {
        c = c  != ESCAPE_CHAR ? DISALLOWED_CHAR : ESCAPE_CHAR;
        pendingEsc = 0;
        offset = (offset + STEP) % NP1;
    } else {
        if (c == ESCAPE_CHAR) {
            pendingEsc = 1;
            return -2;
        }
    }
    return (c - oo) % NP1;
}

int readx() { // -2 if more to read
    int c = getchar();
    if (c == -1)       return c;
    else        return decode(c);
}

int main(void) { // decodes stdin -> stdout
    int c;
    while (1) {
        c = readx();
        if (c >= 0)
            putchar(c);
        else if (c == -1)
            break;
    }
    return 0;
}