Zählen überlappender Wortpaare
Counting Overlapping Pairs of Words
Combinatoire des chevauchements d'une paire de mots
Résumé
Eine Korrelation ist ein binärer Vektor, der alle möglichen Positionen von Überschneidungen zweier Wörter kodiert, wobei eine Überschneidung für ein geordnetes Wortpaar (u, v) auftritt, wenn ein Suffix von u mit einem Präfix von v übereinstimmt. Da mehrere Paare dieselbe Korrelation aufweisen können, ist es relevant zu zählen, wie viele Wortpaare dieselbe Korrelation teilen, abhängig von der Alphabetgröße und der Wortlänge n. Wir zeigen Rekursionen auf, um die Anzahl solcher Paare – die als Populationsgröße bezeichnet wird – für jede Korrelation zu berechnen; dazu nutzen wir eine Beziehung zwischen Überschneidungen zweier Wörter und der Selbstüberschneidung eines Wortes. Dieser Satz ermöglicht es uns, die Anzahl der Paare mit der längsten Überschneidung einer gegebenen Länge zu berechnen und damit zwei offene Fragen zu lösen, die Gabric 2022 aufgeworfen hat. Schließlich liefern wir auch Grenzen für das asymptotische Populationsverhältnis jeder Korrelation. Angesichts der Bedeutung von Wortüberlappungen in Bereichen wie der Kombinatorik auf Wörtern, der Bioinformatik und der digitalen Kommunikation können unsere Ergebnisse die Analyse von Algorithmen für die Zeichenfolgenverarbeitung, das Codedesign oder die Genomassemblierung 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 the longest overlap of a given length, solving two open questions Gabric raised in 2022. Finally, we also provide bounds for the asymptotic population ratio of any correlation. Given the importance of word overlaps in areas like combinatorics on words, 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 entre deux mots, où un chevauchement pour une paire ordonnée de mots (u, v) se produit si un suffixe de u correspond à un préfixe de v. Étant donné que plusieurs paires peuvent avoir la même corrélation, il est pertinent de compter combien de paires de mots partagent la même corrélation, en fonction de la taille de l'alphabet et de la longueur des mots n. Nous présentons des récurrences pour calculer le nombre de ces paires - appelé taille de population - pour toute 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 ayant le plus long chevauchement d'une longueur donnée, résolvant ainsi deux questions ouvertes soulevées par Gabric en 2022. Enfin, nous fournissons également des limites pour le rapport asymptotique de population de toute corrélation. Compte tenu de l'importance des chevauchements de mots dans des domaines tels que la combinatoire sur les mots, la bio-informatique et la communication numérique, nos résultats pourraient faciliter l'analyse des algorithmes pour le traitement des chaînes de caractères, la conception de codes ou l'assemblage de génomes.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|---|
| Licence |
