{'fraction_non_alphanumeric': 0.0322265625, 'fraction_numerical': 0.0078125, 'mean_word_length': 5.137724550898204, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An efficient algorithm for computing the edit distance with non-overlapping inversions

Given two sequences with lengths m and n, the edit distance is the minimum cost required to transform one into the other. The classical operations involved in the traditional edit distance problem include insertion, deletion and replacement. In 2004, Gao et al. [5] proposed an algorithm for calculating the edit distance with non-overlapping inversion, where an inversion may overlap the classical operations, but not another inversion. The time complexity of their algorithm is O(m2n2). In this paper, we introduce a new variant of the traditional edit distance problem, the edit distance with non-overlapping inversion (EDI) problem, which is to determine the minimum edit distance with four operations: insertion, deletion, replacement and inversion. The used operations cannot overlap one another. We propose an efficient algorithm for the EDI problem. The time complexity is O(m2n) in the worst case and O(mn) in the average case.