{'fraction_non_alphanumeric': 0.056463068181818184, 'fraction_numerical': 0.0171875, 'mean_word_length': 3.72834116856951, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Shift-Match Number and String Matching Probabilities for Binary Sequences

We define the ``shift-match number'' for a binary string and we compute the probability of occurrence of a given string as a subsequence in longer strings in terms of its shift-match number. We thus prove that the string matching probabilities depend not only on the length of shorter strings, but also on the equivalence class of the shorter string determined by its shift-match number.


I. INTRODUCTION
The sequence-matching problem can be defined as deciding whether a given string over any alphabet occurs at least once as a subsequence in another set of strings and it is a problem of interest in informatics and genetics. From the informatics point of view, the string-matching problem is essentially the development of fast algorithms for determining exact or approximate occurrences of a short string in longer strings. The "words" searched for are context and language dependent, hence they should not be considered merely as a random selection from the set of n-digit sequences of the given alphabet [1]. On the other hand genomic interactions [2] can be modelled as a valued graph, or "network" in which the nodes are strings of a given length. In a previous set of papers, a model network has been proposed where the edges joining two nodes (a, b) are placed according to whether the string a occurs at least once as subsequence in the string b [3,4]. The number of nodes with a given number of outgoing and incoming edges determine the "out-degree" and "indegree" distributions, which require the knowledge of the string matching probabilities for arbitrary strings of given lengths. A closely related problem in biology is the string alignment problem where it is important to determine the probabilities of chance multiple occurrences of a random string within a specific target string, allowing mismatches and gaps [5,6].
In the present paper we show that for an alphabet of length 2, i.e., binary strings, the matching probabilities of short strings of length n in generic longer strings of length L fall into equivalence classes with respect to a property of the short strings which we identify as the "shift-match number." We obtain a recursive formula for the computation of the string matching probabilities in terms of the "shift-match number" of the shorter string, and the length L of the longer strings. Counting the total number occurrences (with multiplicities) of strings of length n in strings of length L ≥ n, however, washes out the fine structure induced by the shift-match number.
The paper is organized as follows. Section 2 is devoted to the definition of the shift-match number, and proving the dependence of the number of occurrences in longer strings to these numbers. In Section 3 this is applied to the computation of the degree distribution.

II. THE SHIFT-MATCH NUMBER
Let a be a given binary string and let P (a, L) be the probability of occurrence of a in binary strings of length L. Since the number of distinct binary sequences of length L is 2 L , this probability can be expressed as 1) where N(a, L) is the number of binary sequences of length L that contain a as a subsequence at least once. Clearly, if a is a sequence of length n, then N(a, L) = 0 for L < n and N(a, n) = 1. Furthermore the probability P (a, L) approaches 1 as L increases.
We first computed P (a, L) numerically for arbitrary a of a given length n and for increasing values of L. We then observed that although all sequences a are equally likely to occur, for fixed L, the probability P (a, L) shows a variation with respect to a which reveals an equivalence class structure. For example, for sequences of length n = 4 we computed the following probabilities P (a, L), for a as given in the first line of the Table 1, and for L = 4, . . . , 10.
Note that for L = 4, the probabilities P (a, 4) are all equal to 0.0625 = 2 −4 . For L = 5, we see that the sequences fall into two classes, with a = 1111 being distinguished from the rest with respect to its probability of inclusion, P (a, 5). For L = 6 and L = 7 we see that the equivalence classes branch further, into three, then four. This structure stabilizes after L = 7. We also note that P (1000, L) = P (1100, L) = P (1110, L) > P (1001, L) = P (1011, L) for each L. This observation was the starting point for our definition of the "shift-match number," which explains perfectly the equivalence class structure in the P (a, L)'s. In dealing with binary numbers we use the following convention. If a is an n-digit binary number, the i'th digit of a counted from left is denoted by a i , i.e., a = a 1 a 2 . . . a n . (2.3) We note that ifā denotes the binary number obtained from a by replacing zeros with ones and vice versa, i.e., for a = 00100110,ā = 11011001, then P (a, L) = P (ā, L). Hence without loss of generality we may assume that a 1 = 1 wherever convenient. We now define the shiftmatch number s(a) for a given binary number a and the shift-match equivalence on the set of binary numbers of a fixed length.

A. The shift-match number and shift-match equivalence
Let a be the n-digit binary number a = a 1 a 2 a 3 . . . a n . Its shift-match number s(a) is an n-digit binary number s(a) = s 1 s 2 s 3 . . . s n where the s i = s i (a)'s are defined by s 1 (a) = 1 , s 2 (a) = δ(a 2 , a 1 ) δ(a 3 , a 2 ) . . . δ(a n , a n−1 ) , s 3 (a) = δ(a 3 , a 1 ) δ(a 4 , a 2 ) . . . δ(a n , a n−2 ) , . . . s n−1 (a) = δ(a n−1 , a 1 ) δ(a n , a 2 ) , s n (a) = δ(a n , a 1 ) . Hence s(a) = 1001001. We note that in many cases s(s(a)) = s(a), i.e., the shift match number of a is frequently an element of the equivalence class of a, but this is not always true, as for a = 11011, s(a) = 10011 and s(s(a)) = 10001, where the latter does not belong to the equivalence class of a.
As we will show below that the probability of occurrence of a in longer strings will depend only on s(a), we shall suppress the dependency of the shift-match number on a and work with s. The cardinality of the equivalence class whose shift-match number is s plays a crucial role in the computation of the network connectivities and the corresponding probability will be denoted by P (s). We give in Table 2 the list of possible shift-match numbers s for binary sequences of length n ≤ 6 together with the corresponding equivalence class E(s) and its probability P (s).

B. The shift-match indices
Recall that a is a n digit binary string starting with 1, s = s(a) = 1 s 2 . . . s n is the shift-match number of a, and s also is a n digit binary number starting with 1. We shall now give the definition of the shift-match indices j i and j i,m for 1 ≤ i ≤ n and 1 ≤ m ≤ n − 1.
If we replace * 's with 0's or 1's, the ith line represents 2  The "conditional" shift-match indices j i,m for 1 ≤ m ≤ n − 1 are defined by The numbers j i,m correspond to distinct sequences added at line i, where first m digits match with the last m digits of a. For example for n = 5 we have These indices will be used in the computation of the string matching probability for all short strings whose shift-match number is s.

C. The number of occurrences
We define the conditional number of occurrences N(a, L, m) for m = 1, . . . n − 1, defined to be the number of times a occurs as a subsequence in sequences of length L whose first m digits match with the last m digits of a. For simplicity of the presentation we write We shall now give the expression of N(a, L) in terms of N(a, L − n) , N(a, L − n, m) for m = 1, . . . , n − 1. This result shows, in particular, that P (a, L) depends only on the shiftmatch equivalence class of a.
Proposition 2.1. Let a be a binary string of length n, s be its shift-match number and the shift-match indices j i and j i,m be defined by (2.6-7). Then Proof. We can enumerate the sequences of length L containing a by counting the number of sequences of length L where the first occurrence of a starts at the kth digit, for k = 1, . . . , L − n + 1, as seen below.
Hence the proof is complete.
The probability of occurrence of any element of the corresponding equivalence class is shift-match number s in a string of length L are displayed in Figure 1.
We display the numerical values of the N(s, L) in Table 3, where s denotes the shift match number of any representative of a given equivalence class and P (s) is the probability of this equivalence class. The L values appear at the top of the respective columns. An inspection of Table 3 shows that for each pair of lengths n, L, proceeding up the column of shift-match numbers s, there exists a special value s c of s, such that N(s, L) = N(s c , L) for all s ≤ s c . Moreover, the total probability s>sc P (s) of finding strings of length n with shift match numbers larger than s c decreases rapidly with n, as can be seen in Table 3.
Thus the expected value N(s, L) = s P (s)N(s, L) → N(s c , L) from below, as n becomes large, as shown in Table 4.
We will now use these findings to discuss the probability of occurrence of a given string of length n in a string of length L, which is p(n, L) = s P (s) P (s, L) = P (s, L) . (2.11) In a previous paper by Mungan et al. [4], an approximate expression has been given for the probability p(n, L), namely, The frequencies N(s, L) reported in Table 4 have been obtained using Eqs.(2.10) (first line for each n value) and from 2 L p M (n, L) (second line for each n value). A comparison of the numbers shows that they are extremely close, which is gratifying since the approximation (2.12) has been derived by a completely independent route.
Furthermore, note that for n and L−n large, the expression in Eq.(2.12) is approximately p M (n, L) ∼ (L − n + 1)/2 n ≡ p e (n, L) . (2.13) This corresponds to the limit where the corrections to the probability, coming from correlations between successive shifted sequences, can be neglected. In fact, we find that p e (n, L) = N(s c , L)/2 L exactly, or N(s c , L) = 2 L−n (L − n + 1). It is once more instructive to note that in all cases N(s c , L) is the frequency associated with the smallest shift-match numbers.
Had we asked for the total number of multiple occurrences of a given string of length n in a string of length L ≥ n, we would have found that the sum of these numbers over all sequences of length L depends only on L − n, and does not depend on the shift-match number of the short sequence. This total value happens to be equal to the limiting values given in the last line of Table 4, namely N(s c , L) = 2 L−n (L − n + 1).

III. APPLICATIONS
Assume that we are given a collection C of strings of lengths L ≤ L max and let N L denote the number of strings of length L. If a is a binary string in this collection, the degree of a, d(a), is the number of sequences in C that contain a as a subsequence. The considerations in Section 2 allow us to compute the degree distribution in C, over its elements a. A brief inspection of Table 3 shows that the degree of a node decreases with the string length n and for fixed n, with the shift-match number. Thus for fixed L max we have the ordering For lower values of s these numbers are strictly decreasing, but if the number N(s, L) and N(s ′ , L) coincide in the range of n ≤ L ≤ L max then d(s) and d(s ′ ) will be the same, hence the equivalence classes s and s ′ will be indistinguishable with respect to their stringmatching probabilities. We can view the computation of the string matching probabilities on a collection of binary strings as a splitting effect revealing a spectral structure.
In the numerical simulation of Ref. [3], faithfully reproduced by the analytical approach of Refs. [4], the average degree was computed for strings of length n, and the degree distribution exhibited peaks centered at these average values, with a certain variation about this value.
We now see that the degree distribution for strings of length n in fact splits into discrete spectral lines, identified with different shift-match numbers. Thus, in the ideal case, where we can replace d(a) by d(s), the spectrum is discrete.
The strength of the spectral lines correspond to the number of strings ν(d(s)) that have degree d(s). If s is the shift-match number for the string of length n, then ν(d(s)) is given by ν(d(s)) = P (s) N n , where P (s) is the probability of the equivalence class as given in Table 1 and N n is the total number of strings of length n. As an example, for s = 100 and L max = 6 by using Table 3, we easily get The results obtained for ν(d(s)) with respect to d(s) have been shown in Figure 2, where we have chosen N n = L 0 p 2 (1 − p) n , for p = 0.05 and L 0 = 15000, as in Refs. [3,4]. Figure 2 may be compared to Figure 3 of Ref. [4], where ν(d), averaged over 500 random realisations of C, has been plotted. Note that unless L max is large enough, the splitting between the values of d(s) for successive s, does not show up, as can be seen from the Table 3. Moreover, the ν(d(s)) values are degenerate for different values of s, for small n.
The total number q(n, L) of connections leading from strings of length n to strings of length L ≥ n, averaged over 1000 random realisations, is also displayed in Table 5. These numbers q(n, L) should coincide with a weighted averages of d(s)'s over shift-match numbers s's. 4) where |s| = n denotes the sequences having shift-match number s of length n. The numbers computed from (3.4) agree with the numbers given in Table 5, given that the numbers N n and N L are taken to be the number of sequences of length n and L respectively, averaged over the ensemble of realisations.  For n = 4, a first splitting occurs at L = 5 and a further ones at L = 6 and 7. See Table 3 for the degeneracies in the number of occurrences N (s, L), that give rise to this progressive splitting.
(Color online)       [3], assuming a length distribution N n = L 0 p 2 (1 − p) n for p = 0.05 and L 0 = 15000. The numbers given above show the average number of out going bonds from strings of length n (where n is indicated in the first column) to strings of length L (first row).