C数组错误-期望元素被初始化，但它们不是，有时我的setter看起来不工作。

Question

我很难创建一个2d数组，用值填充它，然后读取数组，得到完全不同的值。奇怪的是，我有两个维护两个数组，其中一个是正确地存储值，另一个则不是。我很确定我也没有覆盖元素。我想我犯了一些愚蠢的错误，这对一个不讨厌C的人来说是显而易见的。

请注意，我正在实现viterbi算法，但是我理解并有一个有效的python实现，它只是c中的数组让我感到悲伤。

我在做什么：

1) Malloc两个数组，它们被用作2D数组，但我分配了一个连续的内存块。我不会显式地初始化数组，因为我应该在完成viterbi的前一步时填充它们中的每个条目。

double *viterbi_table = malloc(sizeof(double) * n_samples * n_states);
int *best_path_table = malloc(sizeof(int) * n_samples * n_states);

2)对于viterbi algo的前半部分，我遍历观察到的数据，并计算每个状态的最可能状态和概率。

for (t = 1; t < n_samples; t++) // for each piece of observed data
{
    for (i = 0; i < n_states; i++)
    {
        max_state_index = 0;
        max_p = -DBL_MAX;
        // calculate the max state and probability by looping through all the states
        // yada yada...

        // IMPORTANT PART: We set the array values here
        viterbi_table[t * n_samples + i] = max_p;
        best_path_table[t * n_samples + i] = max_state_index;
        printf("\tbest_path_table[%d][%d] or [%d] = %d => %d\n", 
            i, t, t * n_samples + i, best_path_table[t * n_samples + i], max_state_index);
    }

    // IMPORTANT PART: print out rows of best path table to see if what we thought we inserted is in there
    if (debug)
    {
        printf("best_path, [ ", t);
        for (i = 0; i < n_states; i++)
        {
            printf("[%d], %d ", t * n_samples + i, best_path_table[t * n_samples + i]);
        }
        printf("]\n");
    }
}

3)我运行代码，而不是让我设置的数组元素与我想要设置的元素匹配，而是得到了很大的负数或正数，看起来像未初始化的元素。怎么回事？我给这些区块分配了一个值。下面是输出中显示问题的部分。

t=36 => sample=X
    best_path_table[0][36] or [1404] = 0 => 0
    best_path_table[1][36] or [1405] = 0 => 0
    best_path_table[2][36] or [1406] = 0 => 0
    best_path_table[3][36] or [1407] = 0 => 0
    ...
best_path, [ [1404], 1399607453 [1405], -1070347604 [1406], 1399607453 [1407], 0 ... ]

通过对比，下面的一个是正确的。

t=37 => sample=X
    best_path_table[0][37] or [1443] = 3 => 3
    best_path_table[1][37] or [1444] = 3 => 3
    best_path_table[2][37] or [1445] = 3 => 3
    ...
best_path, [ [1443], 3 [1444], 3 [1445], ... ]

当我为一小部分数据运行代码时，比如< 12条观测，我就不会遇到这样的问题。当我运行更长的数据时，大多数最好的路径表都没有被正确地填充--看起来模式是这样的：

observation#
1) correct
2-3) garbage
4) correct
4-5) garbage
and so on

码

见这个要旨。它不依赖于第三方库。

编辑：

viterbi表的第一行是在算法前一步中初始化的。

for (i = 0; i < n_states; i++)
{
    state_i = states[i];
    sample_t = samples[0];
    viterbi_table[i*n_samples]
        = prior(state_i, 0, true) + emission(sample_t, state_i, true);
}

EDIT2:

在以前版本的代码中，我正在执行更标准的2D数组初始化(在非连续块中)和相应的数组访问。这给了我更大的输入数据的bus error，这是完全有意义的。

double **viterbi_table = malloc(sizeof * viterbi_table * n_states);
int **best_path_table = malloc(sizeof * best_path_table * n_states);
...
viterbi_table[j][t - 1] = ...

EDIT3，对解决方案的评论：

原来这是个愚蠢的下标错误。viterbi和最佳路径数组的大小为n_samples * n_states，即17 * 39 = 663。这排除了任何1404的索引，就像我的例子一样。

具体的问题是，我的数组索引非常混乱，因为我错误地使用了n_samples而不是n_states。对于给定的观察指标t (30)和给定的状态指数I (14)，计算如下：

// Original, wrong
t * n_samples + i = 30 * 39 + 14 = 1184

// New, correct
t * n_states + i = 30 * 17 + 14 = 524

变量t已经对我们所处的样本数进行了编码，所以我们只需要将其乘以状态数。

EDIT4，固定代码：固定代码可以找到这里。我还调整了我的用例的发射和转换概率。

Answer 1

我添加了一个宏CHECK_SUBSCRIPT来检查下标是否在范围内，使用assert。它发射了-有一个下标失去控制。

来源

删除注释。

#include <assert.h>
#include <float.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define CHECK_SUBSCRIPT(x, n_samples)   assert((x) >= 0 && (x) < (n_samples) * n_states)

typedef enum { false, true } bool;
typedef double (*prob_function_def)(char, char, bool);

int n_states = 17;
int n_observations = 17;
char states[17] =
    { 'X', '0', '1', '2', '3', '4', '5', '6', '7',
    '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
char observations[17] =
    { 'X', '0', '1', '2', '3', '4', '5', '6', '7',
    '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};

void viterbi_log (
                char *samples,
                int n_samples,
                char *best_path,
                prob_function_def prior,
                prob_function_def transition,
                prob_function_def emission,
                bool debug
             )
{
    printf("\nviterbi...\n");

    int i, j, t, max_state_index;
    char state_i, state_j, sample_t;
    double trans_p, max_p;

    double *viterbi_table = malloc(sizeof(double) * n_samples * n_states);
    int *best_path_table = malloc(sizeof(int) * n_samples * n_states);

    for (int n33 = 0; n33 < n_samples * n_states; n33++)
    {
        CHECK_SUBSCRIPT(n33, n_samples);
        viterbi_table[n33] = 3.14159;
        best_path_table[n33] = 314159;
    }

    if (debug) printf("\nInitialization:\n");
    for (i = 0; i < n_states; i++)
    {
        state_i = states[i];
        sample_t = samples[0];
        CHECK_SUBSCRIPT(i*n_samples, n_samples);
        viterbi_table[i*n_samples]
            = prior(state_i, 0, true) + emission(sample_t, state_i, true);
        if (debug)
        {
            printf("\t");
            printf("log(prior[%c]) + log(emission[%c][%c]) = %e\n",
                state_i, sample_t, state_i, viterbi_table[i*n_samples]);
        }
    }

    if (debug) printf("\nForward:\n");
    for (t = 1; t < n_samples; t++)
    {
        sample_t = samples[t];
        if (debug) printf("t=%d => sample=%c\n", t, sample_t);
        for (i = 0; i < n_states; i++)
        {
            state_i = states[i];
            max_state_index = 0;
            max_p = -DBL_MAX;

            for (j = 0; j < n_states; j++)
            {
                state_j = states[j];
                CHECK_SUBSCRIPT(((t-1)*n_samples)+j, n_samples);
                trans_p = viterbi_table[((t - 1) * n_samples) + j]
                    + transition(state_i, state_j, true)
                    + emission(sample_t, state_j, true);
                if (trans_p > max_p)
                {
                    max_state_index = j;
                    max_p = trans_p;
                }
            }

            CHECK_SUBSCRIPT(t*n_samples+i, n_samples);
            viterbi_table[t * n_samples + i] = max_p;
            best_path_table[t * n_samples + i] = max_state_index;
            printf("\tbest_path_table[%d][%d] or [%d] = %d => %d\n",
                    i, t, t * n_samples + i, best_path_table[t * n_samples + i], max_state_index);
        }

        if (debug)
        {
            printf("best_path, [ ");
            for (i = 0; i < n_states; i++)
            {
                CHECK_SUBSCRIPT(t*n_samples+i, n_samples);
                printf("[%d], %d ", t * n_samples + i, best_path_table[t * n_samples + i]);
            }
            printf("]\n");
        }
    }

    if (debug)
    {
        printf("\nbest path table:\n");
        for (t = n_samples - 1; t > 0; t--)
        {
            printf("t=%d, [ ", t);
            for (i = 0; i < n_states; i++)
            {
                CHECK_SUBSCRIPT(t*n_samples+i, n_samples);
                printf("[%d], %d ", t * n_samples + i, best_path_table[t * n_samples + i]);
            }
            printf("]\n");
        }
    }

    free(viterbi_table);
    free(best_path_table);
}

double prior_prob (char state_i, char state_j, bool log_prob)
{
    if (!log_prob)
        return 0.25;
    else
        return -1.3862943611198906;
}

double transition_prob (char state_i, char state_j, bool log_prob)
{
    if (!log_prob)
    {
        if (state_i == 0 && state_j == 0)
            return 0.9;
        else if (state_i == 0 || state_j == 0)
            return 0.1;
        else if (state_i == state_j)
            return 0.9;
        else
            return 0.1;
    }
    else
    {
        if (state_i == 0 && state_j == 0)
            return -0.10536051565782628;
        else if (state_i == 0 || state_j == 0)
            return -2.3025850929940455;
        else if (state_i == state_j)
            return -0.10536051565782628;
        else
            return -2.3025850929940455;
    }
}

double emission_prob (char observation, char state, bool log_prob)
{
    if (!log_prob)
    {
        if (state == observation)
            return 0.8;
        else
            return 0.2;
    }
    else
    {
        if (state == observation)
            return -0.2231435513142097;
        else
            return -1.6094379124341003;
    }
}

void dtmf_example()
{
    bool debug = true;
    char *samples = "XXXXXXXXXXXXXX6X66XXXXXXXXXXXXXXXXXXXXX";
    int n_samples = strlen(samples);
    char *best_path = malloc(sizeof(int) * n_samples);

    viterbi_log(samples, n_samples, best_path,
        &prior_prob, &transition_prob, &emission_prob, debug);

    printf("\nbest path = { ");
    for (int t = 0; t < n_samples; t++)
        printf("%d ", best_path[t]);
    printf("}\n");
}

int main(void)
{
    dtmf_example();
    return 0;
}

断言被触发：

best_path_table[13][16] or [637] = 0 => 0
best_path_table[14][16] or [638] = 0 => 0
best_path_table[15][16] or [639] = 0 => 0
best_path_table[16][16] or [640] = 0 => 0
best_path, [ [624], 0 [625], 0 [626], 0 [627], 0 [628], 0 [629], 0 [630], 0 [631], 7 [632], 0 [633], 0 [634], 0 [635], 0 [636], 0 [637], 0 [638], 0 [639], 0 [640], 0 ]
t=17 => sample=6
Assertion failed: ((t*n_samples+i) >= 0 && (t*n_samples+i) < (n_samples) * n_states), function viterbi_log, file viterbi3.c, line 89.
Abort trap: 6

这是CHECK_SUBSCRIPT在：

        CHECK_SUBSCRIPT(t*n_samples+i, n_samples);
        viterbi_table[t * n_samples + i] = max_p;
        best_path_table[t * n_samples + i] = max_state_index;

Answer 2

因为t以1开头，所以第一行似乎从未初始化过。我猜每一行都取决于前面的一行，所以垃圾值会通过。一个特定案例的存在完全是偶然的(未初始化的数据碰巧是有效的)。