Преобразование Барроуза-Уиллера(предварительная обработка для Хаффмана)

bwt

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// #include <stdbool.h> // bool
#define BLOCKSIZE 50
// Преобразование Барроуза-Уиллера
 

void swap(char *f, char *l, int memory)
{
    char temp;
    for (int i = 0; i < memory; ++i)
    {
        temp = f[i];
        f[i] = l[i];
        l[i] = temp;
    }
}

int mystrcmp(const char *a, const char *b){
    while ( *a && *b && *a == *b )
        ++a, ++b;
    return (*a - *b);
}


int cmp_min(char *f, char *l)
{
    int res = mystrcmp(f, l);
    if (res <= 0)
        return 1;
    return 0;
}


int cmp_max(char *f, char *l)
{
    int res = mystrcmp(f, l);
    if (res > 0)
        return 1;
    return 0;
}


void quickSortR(char *s_arr, int first, int last, int memory)
{
// На входе - массив a[], a[N] - его последний элемент.

  long i = 0, j = last;        // поставить указатели на исходные места
  char *x = s_arr+(first+(last-first)/2)*(memory+1);

  // процедура разделения
  do {
    while (mystrcmp(s_arr+i*(memory+1), x) < 0 ) i++;
    while (mystrcmp(s_arr+j*(memory+1), x) > 0 ) j--;

    if (i <= j) {
      swap(s_arr+i*(memory+1), s_arr+j*(memory+1), memory);
      i++; j--;
    }
  } while ( i<=j );

  // рекурсивные вызовы, если есть, что сортировать 
  if (i < last)
      quickSortR(s_arr, i, last, memory);
  if (first < j)
      quickSortR(s_arr, first,j, memory);
}


int bwt(int memory)
{
    FILE *file;
    file = fopen("/home/rag0n/Programming/C/MyProjects/kursovaya/text/sample.txt", "r");
    char bwt_array[memory][memory+1], result[memory+1]; // +1 для терминального нуля
    for (int i = 0; i < memory-1; ++i)
        bwt_array[0][i] = fgetc(file);
    fclose(file);
    bwt_array[0][memory-1] = '$';
    for (int i = 1; i < memory; ++i)
    {
        bwt_array[i][memory-1] = bwt_array[i-1][0];
        for (int j = 0; j < memory-1; ++j)
            bwt_array[i][j] = bwt_array[i-1][j+1];
    }
    for (int i = 0; i < memory; ++i)
        bwt_array[i][memory] = '\0';
    for (int i = 0; i < memory; ++i)
        printf("%s\n", bwt_array[i]);
    // printf("\n%s\n", bwt_array[memory/2]);
    printf("=======\n");
    quickSortR(bwt_array, 0, memory-1, memory);
    for (int i = 0; i < memory; ++i)
        printf("%s\n", bwt_array[i]);

    // выбираем последний столбец
    for (int i = 0; i < memory; ++i)
    {
        result[i] = bwt_array[i][memory-1];
    }
    result[memory] = '\0';
    printf("========\n%s\n", result);
    return 0;
}
 

int main()
{
    FILE *file;
    file = fopen("/home/rag0n/Programming/C/MyProjects/kursovaya/text/sample.txt", "r");
    int i, symbol, counter = 0;
    for (i = 0; symbol != EOF; ++i)
        symbol = fgetc(file);
    fclose(file);
    i -= 2;
    // printf("%d\n", i);
    while(i > 0)
    {
        counter++;
        i -= BLOCKSIZE;
    }
    // printf("%d\n", counter);
    while(counter > 1)
    {
        bwt(BLOCKSIZE+1);
        counter--;
    }
    // printf("%d\n", BLOCKSIZE+i+1);
    bwt(BLOCKSIZE+i+1);
    return 0;
}