Résumé
This paper introduces a novel and more efficient method for constructing oriented hierarchies within the framework of Statistical Implicative Analysis. The primary focus of this study is the computational complexity of the original algorithm proposed by Gras, whose cubic time complexity is established in this work. To address this limitation, a detailed combinatorial analysis of hierarchical structures is performed, leveraging tools from analytic combinatorics. This methodology facilitates the enumeration of the number of possible configurations as a function of input size and enables the investigation of both the depth and width characteristics of the hierarchy’s block structure. This study then proposes a reconstruction algorithm based on a formal correspondence between the statistical implication graph and the oriented hierarchy. The proposed method achieves quadratic worst-case complexity, thereby resulting in a substantial improvement in computational performance. Moreover, the analytic framework also makes it possible to characterise the average-case behaviour of the algorithm. The findings of the comparative computational experiments demonstrate the clear advantage of the proposed method over Gras’s algorithm, both in terms of execution time and overall algorithmic efficiency.