Counting overlapping pairs of strings
Compter les paires de mots qui se chevauchent
Résumé
Eine Korrelation ist ein binärer Vektor, der alle möglichen Überlappungspositionen zweier Wörter codiert, wobei eine Überlappung für ein geordnetes Paar von Wörtern (u,v) auftritt, wenn ein Suffix des Wortes u mit einem Präfix des Wortes v übereinstimmt. Da mehrere Paare die gleiche Korrelation haben können, ist es relevant zu zählen, wie viele Wortpaare die gleiche Korrelation teilen, abhängig von der Größe des Alphabets und der Länge der n-Wörter. Wir stellen Rekursionen vor, um die Anzahl dieser Paare - Populationsgröße genannt - für jede beliebige Korrelation zu berechnen; dazu nutzen wir eine Beziehung zwischen den Überlappungen zweier Wörter und die Selbstüberlappung eines Wortes aus. Mit diesem Theorem können wir die Anzahl der Paare berechnen, deren längste Überlappung eine bestimmte Länge hat, und zeigen, dass die erwartete Länge der längsten "Border" zweier Wörter asymptotisch divergiert, was zwei offene Fragen löst, die Gabric 2022 aufgeworfen hat. Schließlich stellen wir auch Grenzwerte für das asymptotische Populationsverhältnis jeglicher Korrelation zur Verfügung. Angesichts der Bedeutung von Wortüberschneidungen in Bereichen wie Wortkombinatorik, Bioinformatik und digitaler Kommunikation können unsere Ergebnisse die Analyse von Algorithmen für die Verarbeitung von Zeichenketten, das Design von Codes oder die Zusammenstellung von Genomen erleichtern.
A correlation is a binary vector that encodes all possible positions of overlaps of two words, where an overlap for an ordered pair of words $(u,v)$ occurs if a suffix of $u$ matches a prefix of $v$. As multiple pairs can have the same correlation, it is relevant to count how many pairs of words share the same correlation depending on the alphabet size and word length $n$. We exhibit recurrences to compute the number of such pairs -- which is termed population size -- for any correlation; for this, we exploit a relationship between overlaps of two words and self-overlap of one word. This theorem allows us to compute the number of pairs with a longest overlap of a given length and to show that the expected length of the longest border of two words asymptotically diverges, which solves two open questions raised by Gabric in 2022. Finally, we also provide bounds for the asymptotic of the population ratio of any correlation. Given the importance of word overlaps in areas like word combinatorics, bioinformatics, and digital communication, our results may ease analyses of algorithms for string processing, code design, or genome assembly.
Une corrélation est un vecteur binaire qui encode toutes les positions possibles de chevauchement de deux mots. Un chevauchement pour une paire ordonnée de mots (u,v) existe (et est défini) si un suffixe du mot u égale un préfixe du mot v. Comme plusieurs paires de mots peuvent avoir la même corrélation, il est pertinent de compter combien de paires de mots partagent une même corrélation en fonction de la taille de l'alphabet et de la longueur des mots notée n. Nous présentons des récurrences pour calculer le nombre de ces paires - nombre appelé taille de la population - pour n'importe quelle corrélation ; pour cela, nous exploitons une relation entre les chevauchements de deux mots et l'auto-chevauchement d'un mot. Ce théorème nous permet de calculer le nombre de paires dont le plus long chevauchement est d'une longueur donnée, ainsi que de montrer que la longueur moyenne du plus long bord de deux mots diverge asymptotiquement. Ceci résout deux questions ouvertes soulevées par Gabric en 2022. Enfin, nous fournissons également des bornes asymptotiques du ratio de population pour une corrélation quelconque. Étant donnée l'importance des chevauchements de mots dans des domaines tels que la combinatoire des mots, la bioinformatique et la communication digitale, nos résultats peuvent faciliter l'analyse des algorithmes pour le traitement des chaînes de caractères, la conception de codes ou l'assemblage de génomes.
