{'fraction_non_alphanumeric': 0.03410024650780608, 'fraction_numerical': 0.002054231717337716, 'mean_word_length': 4.881642512077295, '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}}
Proposal : Decimation-inFrequency Fast Fourier Transforms for the Symmetric Group

In recent years, researchers have begun to approach Fourier transforms from a more algebraic perspective. For example, the classical Discrete Fourier Transform (DFT) takes n evenly spaced samples of a periodic function and transforms them into n amplitudes for different frequencies, called the Fourier coefficients of the sample data. If the data sample is considered as a function on the group Z/nZ, that is, as an element of the group ring C[Z/nZ], then the DFT becomes an isomorphism of C[Z/nZ] into the algebra of complex diagonal n × n matrices. The elements along the diagonal of the matrix corresponding to a given f ∈ C[Z/nZ] represent the Fourier coefficients of f [3]. Wedderburn’s Theorem states that, for any finite group G, CG is isomorphic to some block diagonal matrix algebra ⊕h j=1 Cdj×dj . It is therefore possible to construct a generalization of the usual DFT for any finite group. DFTs for infinite groups (such as Lie groups) can also be defined, although there must be a way to sample the function on the group. A Fast Fourier Transform (FFT) is any efficient implementation of a DFT. The classic example of an FFT is the Cooley-Tukey FFT for the traditional DFT, which computes the DFT in O(N log N) time, rather than the O(N) time required by a naive implementation of the DFT. Similar techniques have yielded FFTs for all abelian groups G of complexity O(|G| log |G|) [3]. Determining the upper bound for the complexity of FFTs on an arbitrary finite group G remains an open problem, although a number of conjectures regarding this bound exist. Most existing generalized FFTs follow the Cooley-Tukey algorithm in using a decimation-in-time decomposition. This approach constructs a series of coset partitions of the group from a chain of subgroups and then computes smaller transforms for each level of the partition. A different approach, effectively dual to the decimationin-time method, is the decimation-in-frequency FFT, in which the frequency space is decomposed instead of the group. This decomposition may be accomplished by successively projecting the data into different subspaces to construct increasingly finer frequency information. As decimation-in-time algorithms have become increasingly difficult to improve, more attention has focused on the alternatives offered by decimation-in-frequency approaches [14].