明月机器学习系列031：特殊二分图的最优匹配算法（二）

    def match(self, min_score=0.2, sort_min_score=0.01):
        """快速配对算法（类似贪心算法）
        :return items: numpy.ndarray: [(idx1, idx2)]
        """
        scores = self.scores
        len1, len2 = scores.shape
        if len1 < 1 or len2 < 1:
            return np.array([])
        if len1 == 1 and len2 == 1:
            return np.array([[0, 0]])
        is_T = False    # 是否转置
        if len1 > len2:
            is_T = True
            scores = scores.T  # 转置之后，保证行数是比较少的

        # 每行最大值的索引
        max_index = np.argmax(scores, axis=1)
        eq_index = max_index == np.sort(max_index)
        len_index = len(max_index)
        if all(eq_index) and len_index == len(set(max_index)):
            # 顺序一致且每个值都不同
            data = [[i, v] for i, v in enumerate(max_index) if scores[i, v] >= sort_min_score]
            if is_T:
                data = [[v, i] for i, v in data]
            return np.array(data)

        # 顺序不一致或者存在相同的值
        eq_index = np.zeros((len_index,), dtype=bool)
        min_arr, max_arr = self.get_min_max(max_index)
        for i in range(len_index):
            # 比前面的值都大，比后面的值都小
            if i > 0:
                if max_index[i] <= max_arr[i-1]:
                    eq_index[i] = True
                    continue
            if i < len_index-1:
                if max_index[i] >= min_arr[i+1]:
                    eq_index[i] = True

        data = []
        is_true = False
        # self.min_score = min_score
        for (i, v), flag in zip(enumerate(max_index), eq_index):
            if not flag:
                is_true = False
                if scores[i, v] >= min_score:
                    data.append([i, v])
                if v == scores.shape[1]:     # 已经是最大的值
                    break
                continue
            if is_true:
                continue
            # 找到连续的True块
            is_true = True
            true_len = 0
            for j in range(i, len_index):
                if eq_index[j]:
                    true_len += 1
                else:
                    break

            # 在小区域[min_i:max_i, min_j:max_j]内进行匹配
            min_j = 0 if len(data) == 0 else data[-1][1]+1
            max_j = scores.shape[1] if i+true_len >= len_index else max_index[i+true_len]
            min_i, max_i = i, i+true_len
            self.scores = scores[min_i:max_i, min_j:max_j].copy()
            tmp_data = self.match_old(min_score=min_score)
            if debug:
                print("tmp data: ", tmp_data)

            for tmp_i, tmp_v in tmp_data:
                data.append([tmp_i+min_i, tmp_v+min_j])

        if is_T:
            data = [[v, i] for i, v in data]
        return np.array(data)