Является ли алгоритм RLE некорректным? - PullRequest
Новая
       14

Является ли алгоритм RLE некорректным?

0 голосов
/ 12 февраля 2010

Я смотрел на недавний Код Гольф на удаление повторяющихся символов в строке. я обдумал это и подумал, что алгоритм RLE решит его, на самом деле, я уверен, что это разрешит удаление дубликатов, я написал реализацию здесь на C, чтобы посмотреть, как далеко я смогу пойти с этим 

char *rle(const char *src){
    char *p=(char *)src;
    char *q=(char *)src+1;
    char *rle_enc=NULL, *tmp_rle, buf[10];
    int run=1;
    while (*p){
        while(*q){
            if (*p==*q++) run++,p++;
        }
        sprintf(buf,"%d%c",run,*(p-1));
        p++;
        if (!rle_enc){
            if ((rle_enc=malloc(strlen(buf)+1))!=NULL){
                strcpy(rle_enc,buf);
            }
        }else{
            if ((tmp_rle=realloc(rle_enc,(strlen(rle_enc)+strlen(buf)+1)))!=NULL){
                rle_enc=tmp_rle;
                strcat(rle_enc,buf);
            }
        }
        q=(p+1);
        run=1;
    }
    return rle_enc;
}

Конечно, вот главное для этого: 

int main(int argc, char **argv){
    char *test1 = "HHHHHHeeeeeelllllloooooooo";
    char *test2 = "nbHHkRvrXbvkn";
    char *p = rle(test1);
    printf("s = %s\n", test1);
    printf("p = %s\n", p);
    if (p) free(p);
    return 0;
}

Согласно Code Golf на мета, он должен быть многократно используемым и решать множество проблем, НО в самом коротком наборе символов, достаточно справедливо, я думал, что я просто изменил бы переменные на 1 букву и компактный код, чтобы сделать его маленьким ... но что-то было не совсем правильно с ним, так как это заставило меня задуматься о самом алгоритме RLE, вот страница в Wikipedia о том, что он должен сказать, и реализация на Java.

Код, похоже, делает то, что должен, поэтому я подумал, что теперь нужно просто просмотреть закодированный строковый результат из rle и найти те, которые имеют 1, за которым следует буква.

Однако я заметил ограничение алгоритма RLE, он подходит только для тех, у которых есть набор повторяющихся символов, смежных друг с другом. Но он не прошел тестовый пример для Code Golf, который выглядит обманчиво простым, что приводит меня к этому вопросу:

Является ли алгоритм RLE некорректным? Где бы он использовался в наши дни? Я предполагаю, что собираю пыль из-за большого объема данных и информации, которая распространяется вокруг этой RLE, которая больше не соответствует цели ...

Редактировать: Спасибо Лунной Тени, Джону и Стиву за публикацию своих ответов.

Есть фундаментальный урок, который я до сих пор не усвоил - никогда не переходите на OTT и не мыслите комплексно, когда дело доходит до такого рода вещей, что является ошибкой с моей стороны и показывает, как большое мышление может мешать и я могу погрузиться в это слишком глубоко и увлечься, не глядя под прямым углом !!!!! Еще раз спасибо! :)

С уважением, Том.

Ответы [ 3 ]

4 голосов
/ 12 февраля 2010

RLE не решит эту проблему с гольф-кодом для вас.

Проблема кода гольф требует, чтобы вы удалили все символы, которые встречаются на входе более одного раза, независимо от того, где они встречаются. Однако RLE, «кодирование длины серий», кодирует «серии» - повторяющиеся последовательности одного и того же символа; несколько строк одного и того же символа могут встречаться в строке, и RLE будет кодировать их отдельно, по замыслу.

RLE предназначен для более компактного кодирования последовательностей повторяющихся элементов данных путем замены последовательности только одним элементом с последующим количеством повторений. Для этого это вполне адекватно. Любой «недостаток» не в алгоритме, а скорее в решении использовать его для цели, для которой он плохо подходит.

2 голосов
/ 12 февраля 2010

RLE обычно использовался для 8-битных растровых изображений, так как они обычно имели бы длинные серии с одним и тем же символом. Windows по-прежнему поддерживает видеокодек RLE, который использовался аналогичным образом. В настоящее время кодирование LZW + Хаффмана заменило RLE как «простой» алгоритм сжатия.

RLE использовался в течение многих лет, поэтому нам довольно трудно сказать, что он "несовершенен", но, безусловно, не эффективен.

Большинство форматов RLE будут иметь «escape-символ», так что не будет никакой путаницы в отношении вывода.

Например, если мы используем «е» в качестве escape-символа ...

Это приведет к буквальному «е»: 

ee

Это будет буква "а", повторенная дважды: 

ea2
1 голос
/ 12 февраля 2010

Почему вы думаете, что это неправильно? RLE работает для сжатия повторяющихся символов. Он не предназначен для других действий и не поможет сжать данные без длин серий> 1.

В контексте этой проблемы я бы сказал, что RLE был просто неправильным ответом, он не ошибочен, в этом случае он просто не помог.

...