Подсчет триграмм (трехбуквенная последовательность) в C?

Я пытаюсь подсчитать количество триграмм или последовательностей из трех букв в блоке текста. У меня уже есть код, который успешно подсчитывает количество биграмм (двухбуквенная последовательность) с использованием двумерного массива, но у меня возникли проблемы с его изменением для приема триграмм.

#include <stdio.h>

int main(void) {
int count['z' - 'a' + 1]['z' - 'a' + 1] = {{ 0 }};
int c0 = EOF, c1;
FILE *plain = fopen("filename.txt", "r");

if (plain != NULL) {
    while ((c1 = getc(plain)) != EOF) {
        if (c1 >= 'a' && c1 <= 'z' && c0 >= 'a' && c0 <= 'z') {
            count[c0 - 'a'][c1 - 'a']++;
        }
        c0 = c1;
    }
    fclose(plain);
    for (c0 = 'a'; c0 <= 'z'; c0++) {
        for (c1 = 'a'; c1 <= 'z'; c1++) {
            int n = count[c0 - 'a'][c1 - 'a'];
            if (n) {
                printf("%c%c: %d\n", c0, c1, n);
            }
        }
    }
}
return 0;
}

Изменить: вот код, который я уже пробовал. Я надеялся просто расширить массив 2d до массива 3d, но это ничего не возвращает.

#include <stdio.h>

int main(void) {
int count['z' - 'a' + 1]['z' - 'a' + 1]['z' - 'a' + 1] = {{{ 0 }}};
int c0 = EOF, c1, c2;
FILE *plain = fopen("filename.txt", "r");

if (plain != NULL) {
    while ((c1 = getc(plain)) != EOF) {
        if (c1 >= 'a' && c1 <= 'z' && c0 >= 'a' && c0 <= 'z' && c2 >= 'a' && c2 <= 'z') {
            count[c0 - 'a'][c1 - 'a'][c2 - 'a']++;

        }
        c0 = c1;
        c1 = c2;
    }
    fclose(plain);
    for (c0 = 'a'; c0 <= 'z'; c0++) {
        for (c1 = 'a'; c1 <= 'z'; c1++) {
            for (c2 = 'a'; c2 <= 'z'; c2++) {
                    int n = count[c0 - 'a'][c1 - 'a'][c2 - 'a'];
                    if (n) {
                            printf("%c%c%c: %d\n", c0, c1, c2, n);
                    }
            }
        }
    }
}
return 0;
}

Например, этот код выводит все вхождения биграмм, таких как aa, ab, ac и т. д. Но мне нужно, чтобы он подсчитывал вхождения aaa, aab, ... zzz. Любая помощь будет принята с благодарностью!

Редактировать 2: теперь он успешно печатает правильный вывод, но он должен быть в порядке убывания (наиболее часто используемая триграмма вверху)


c multidimensional-array trigram
person nhlyoung    schedule 11.09.2019    source источник
comment
Сколько aaa в aaaa?   -  person Eugene Sh.    schedule 11.09.2019
comment
Это будет считаться как 2   -  person nhlyoung    schedule 11.09.2019
comment
Что вы уже пытались получить эти триграммы? Покажите нам код, который вы пробовали (даже если он не работает).   -  person S.S. Anne    schedule 11.09.2019
comment
Извините, это уже там :)   -  person nhlyoung    schedule 11.09.2019
comment
c1 = getc(plain) - вы перезаписываете сохраненный c1. Я думаю, что вы хотите прочитать в c2   -  person Eugene Sh.    schedule 11.09.2019
comment
ДА!! Я перезаписывал c1. переключил это на c2, и все заработало отлично. Благодарю вас!   -  person nhlyoung    schedule 11.09.2019
comment
Ну почти идеально. Это успешно напечатало все триграммы, но они не в порядке убывания.   -  person nhlyoung    schedule 11.09.2019
comment
Я думаю, было бы лучше использовать тройной цикл for и функцию strstr, чтобы найти количество всех триграмм   -  person Miradil Zeynalli    schedule 11.09.2019
comment
Заказ напрямую связан с индексом; Я думаю, что нужно иметь более сложный struct, если вы собираетесь эффективно переупорядочивать их (или иметь два шага).   -  person Neil    schedule 12.09.2019

Ответы (1)


arrow_upward
0
arrow_downward

Нужно больше информации, если вы собираетесь сортировать корзины; в этом коде это массив указателей order, который указывает на все триграммы один к одному. Однако с исходным кодом трудно сказать, какая триграмма с каким индексом в O(1). Таким образом, я упаковал и сгладил массив, тем самым обеспечив биекцию индекса массива на все пространство триграмм (их 17576).

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct Tri { const char c0, c1, c2; };

static size_t tri_to_idx(const struct Tri tri) {
    return (tri.c0 - 'a') * ('z' - 'a' + 1) * ('z' - 'a' + 1)
        + (tri.c1 - 'a') * ('z' - 'a' + 1)
        + (tri.c2 - 'a');
}

static struct Tri idx_to_tri(const size_t idx) {
    struct Tri tri = {
        idx / (('z' - 'a' + 1) * ('z' - 'a' + 1)) + 'a',
        (idx % (('z' - 'a' + 1) * ('z' - 'a' + 1))) / ('z' - 'a' + 1) + 'a',
        idx % ('z' - 'a' + 1) + 'a' };
    assert(tri.c0 >= 'a' && tri.c0 <= 'z'
        && tri.c1 >= 'a' && tri.c1 <= 'z'
        && tri.c2 >= 'a' && tri.c2 <= 'z');
    return tri;
}

static const char *tri_to_str(const struct Tri tri) {
    static char str[4];
    str[0] = tri.c0, str[1] = tri.c1, str[2] = tri.c2, str[3] = '\0';
    return str;
}

static int int_reverse_cmp(const int *const a, const int *const b) {
    return (*a < *b) - (*b < *a);
}

static int compar(const void *a, const void *b) {
    return int_reverse_cmp(*(int **)a, *(int **)b);
}

int main(void) {
    const char *const fn = "filename.txt";
    int count[('z' - 'a' + 1) * ('z' - 'a' + 1) * ('z' - 'a' + 1)] = { 0 };
    int *order[('z' - 'a' + 1) * ('z' - 'a' + 1) * ('z' - 'a' + 1)];
    int c0 = EOF, c1 = EOF, c2;
    size_t i;
    FILE *plain = fopen(fn, "r");

    if(!plain) return perror(fn), EXIT_FAILURE;

    while ((c2 = getc(plain)) != EOF) {
        if (c1 >= 'a' && c1 <= 'z'
            && c0 >= 'a' && c0 <= 'z'
            && c2 >= 'a' && c2 <= 'z') {
            struct Tri tri = { c0, c1, c2 };
            count[tri_to_idx(tri)]++;
        }
        c0 = c1;
        c1 = c2;
    }
    fclose(plain);

    for (c0 = 'a'; c0 <= 'z'; c0++) {
        for (c1 = 'a'; c1 <= 'z'; c1++) {
            for (c2 = 'a'; c2 <= 'z'; c2++) {
                struct Tri tri = { c0, c1, c2 };
                order[tri_to_idx(tri)] = &count[tri_to_idx(tri)];
            }
        }
    }

    qsort(order, sizeof order / sizeof *order, sizeof *order, &compar);
    for(i = 0; i < ('z' - 'a' + 1) * ('z' - 'a' + 1) * ('z' - 'a' + 1)
        && *order[i]; i++) {
        printf("%s: %d\n", tri_to_str(idx_to_tri(order[i] - count)), *order[i]);
    }

    return EXIT_SUCCESS;
}

Теперь можно отсортировать указатели на массив и по-прежнему иметь биекцию обратно в триграммы по индексу триграммы, order[i] - count в printf.

person Neil    schedule 12.09.2019