1. #ifndef CORRUPT_H
    2. #define CORRUPT_H
    3. #include "Random.h"
    4. #include "Triple.h"
    5. #include "Reader.h"
    6. #include "iso646.h"
    8. INT corrupt_head(INT id, INT h, INT r, bool filter_flag = true) {
    9.     INT lef, rig, mid, ll, rr;
    11.     // filter_flag是指要不要进行过滤，在这里t是随机生成的，它会带来什么问题呢？负采样得到的h,r,tmp很有可能也在三元组中出现过，这样效果就会适得其反
    12.     if (not filter_flag) {
    13.         INT tmp = rand_max(id, entityTotal - 1);
    14.         if (tmp < h)
    15.             return tmp;
    16.         else
    17.             return tmp + 1;
    18.     }
    20.     // trainHead是依据三元组头部的ID大小进行排序的列表，可以进行二分查找，因为头实体ID相同的话它是按关系RelationID大小排列的
    21.     // lef即当前头实体在有序TrainHead列表第一次出现的位置（从这里开始查找）
    22.     // rig即当前头实体在有序TrainHead列表最后一次出现的位置（查找区间尽头）
    23.     lef = lefHead[h] - 1;
    24.     rig = rigHead[h];
    25.     while (lef + 1 < rig) {
    26.         mid = (lef + rig) >> 1;
    27.         if (trainHead[mid].r >= r) rig = mid; else
    28.         lef = mid;
    29.     }
    30.     // ll是在区间lef~rig中第一次出现关系为r的三元组下标
    31.     ll = rig;
    33.     lef = lefHead[h];
    34.     rig = rigHead[h] + 1;
    35.     while (lef + 1 < rig) {
    36.         mid = (lef + rig) >> 1;
    37.         if (trainHead[mid].r <= r) lef = mid; else
    38.         rig = mid;
    39.     }
    40.     // rr是在区间lef~rig中最后一次出现关系为r的三元组下标
    41.     rr = lef;
    43.     // 那么我们最后想返回什么呢？就是一个没有在任何头实体为h、关系为r的三元组中出现过的t，其实就是很简单的一个事情
    44.     INT tmp = rand_max(id, entityTotal - (rr - ll + 1));
    45.     if (tmp < trainHead[ll].t) return tmp;
    46.     if (tmp > trainHead[rr].t - rr + ll - 1) return tmp + rr - ll + 1;
    47.     lef = ll, rig = rr + 1;
    48.     // 随机到的tmp恰好落入relation为r的tail区间里了，这种情况有点麻烦
    49.     // 但是好在所有头实体为h、关系为r的三元组中也是按尾实体ID升序排列的，所以还可以进行一次二分查找，找到未在tail区间中出现过的尾实体ID
    50.     while (lef + 1 < rig) {
    51.         mid = (lef + rig) >> 1;
    52.         if (trainHead[mid].t - mid + ll - 1 < tmp)
    53.             lef = mid;
    54.         else 
    55.             rig = mid;
    56.     }
    57.     return tmp + lef - ll + 1;
    58. }
    60. INT corrupt_tail(INT id, INT t, INT r, bool filter_flag = true) {
    61.     INT lef, rig, mid, ll, rr;
    62.     if (not filter_flag) {
    63.         INT tmp = rand_max(id, entityTotal - 1);
    64.         if (tmp < t)
    65.             return tmp;
    66.         else
    67.             return tmp + 1;
    68.     }
    69.     lef = lefTail[t] - 1;
    70.     rig = rigTail[t];
    71.     while (lef + 1 < rig) {
    72.         mid = (lef + rig) >> 1;
    73.         if (trainTail[mid].r >= r) rig = mid; else
    74.         lef = mid;
    75.     }
    76.     ll = rig;
    77.     lef = lefTail[t];
    78.     rig = rigTail[t] + 1;
    79.     while (lef + 1 < rig) {
    80.         mid = (lef + rig) >> 1;
    81.         if (trainTail[mid].r <= r) lef = mid; else
    82.         rig = mid;
    83.     }
    84.     rr = lef;
    85.     INT tmp = rand_max(id, entityTotal - (rr - ll + 1));
    86.     if (tmp < trainTail[ll].h) return tmp;
    87.     if (tmp > trainTail[rr].h - rr + ll - 1) return tmp + rr - ll + 1;
    88.     lef = ll, rig = rr + 1;
    89.     while (lef + 1 < rig) {
    90.         mid = (lef + rig) >> 1;
    91.         if (trainTail[mid].h - mid + ll - 1 < tmp)
    92.             lef = mid;
    93.         else 
    94.             rig = mid;
    95.     }
    96.     return tmp + lef - ll + 1;
    97. }
    100. INT corrupt_rel(INT id, INT h, INT t, INT r, bool p = false, bool filter_flag = true) {
    101.     INT lef, rig, mid, ll, rr;
    102.     if (not filter_flag) {
    103.         INT tmp = rand_max(id, relationTotal - 1);
    104.         if (tmp < r)
    105.             return tmp;
    106.         else
    107.             return tmp + 1;
    108.     }
    109.     lef = lefRel[h] - 1;
    110.     rig = rigRel[h];
    111.     while (lef + 1 < rig) {
    112.         mid = (lef + rig) >> 1;
    113.         if (trainRel[mid].t >= t) rig = mid; else
    114.         lef = mid;
    115.     }
    116.     ll = rig;
    117.     lef = lefRel[h];
    118.     rig = rigRel[h] + 1;
    119.     while (lef + 1 < rig) {
    120.         mid = (lef + rig) >> 1;
    121.         if (trainRel[mid].t <= t) lef = mid; else
    122.         rig = mid;
    123.     }
    124.     rr = lef;
    125.     INT tmp;
    126.     if(p == false) {    
    127.         tmp = rand_max(id, relationTotal - (rr - ll + 1));
    128.     }
    129.     else {
    130.         INT start = r * (relationTotal - 1);
    131.         REAL sum = 1;
    132.         bool *record = (bool *)calloc(relationTotal - 1, sizeof(bool));
    133.         for (INT i = ll; i <= rr; ++i){
    134.             if (trainRel[i].r > r){
    135.                 sum -= prob[start + trainRel[i].r-1];
    136.                 record[trainRel[i].r-1] = true;
    137.             }
    138.             else if (trainRel[i].r < r){
    139.                 sum -= prob[start + trainRel[i].r];
    140.                 record[trainRel[i].r] = true;
    141.             }
    142.         }        
    143.         REAL *prob_tmp = (REAL *)calloc(relationTotal-(rr-ll+1), sizeof(REAL));
    144.         INT cnt = 0;
    145.         REAL rec = 0;
    146.         for (INT i = start; i < start + relationTotal - 1; ++i) {
    147.             if (record[i-start])
    148.                 continue;
    149.             rec += prob[i] / sum;
    150.             prob_tmp[cnt++] = rec;
    151.         }
    152.         REAL m = rand_max(id, 10000) / 10000.0;
    153.         lef = 0;
    154.         rig = cnt - 1;
    155.         while (lef < rig) {
    156.             mid = (lef + rig) >> 1;
    157.             if (prob_tmp[mid] < m) 
    158.                 lef = mid + 1; 
    159.             else
    160.                 rig = mid;
    161.         }
    162.         tmp = rig;
    163.         free(prob_tmp);
    164.         free(record);
    165.     }
    166.     if (tmp < trainRel[ll].r) return tmp;
    167.     if (tmp > trainRel[rr].r - rr + ll - 1) return tmp + rr - ll + 1;
    168.     lef = ll, rig = rr + 1;
    169.     while (lef + 1 < rig) {
    170.         mid = (lef + rig) >> 1;
    171.         if (trainRel[mid].r - mid + ll - 1 < tmp)
    172.             lef = mid;
    173.         else 
    174.             rig = mid;
    175.     }
    176.     return tmp + lef - ll + 1;
    177. }
    180. bool _find(INT h, INT t, INT r) {
    181.     INT lef = 0;
    182.     INT rig = tripleTotal - 1;
    183.     INT mid;
    184.     while (lef + 1 < rig) {
    185.         INT mid = (lef + rig) >> 1;
    186.         if ((tripleList[mid]. h < h) || (tripleList[mid]. h == h && tripleList[mid]. r < r) || (tripleList[mid]. h == h && tripleList[mid]. r == r && tripleList[mid]. t < t)) lef = mid; else rig = mid;
    187.     }
    188.     if (tripleList[lef].h == h && tripleList[lef].r == r && tripleList[lef].t == t) return true;
    189.     if (tripleList[rig].h == h && tripleList[rig].r == r && tripleList[rig].t == t) return true;
    190.     return false;
    191. }
    193. INT corrupt(INT h, INT r){
    194.     INT ll = tail_lef[r];
    195.     INT rr = tail_rig[r];
    196.     INT loop = 0;
    197.     INT t;
    198.     while(true) {
    199.         t = tail_type[rand(ll, rr)];
    200.         if (not _find(h, t, r)) {
    201.             return t;
    202.         } else {
    203.             loop ++;
    204.             if (loop >= 1000) {
    205.                 return corrupt_head(0, h, r);
    206.             }
    207.         } 
    208.     }
    209. }
    210. #endif