On the size of the neighborhoods of a word
Cedric Chauve, Louxin Zhang · 2025
Read On the size of the neighborhoods of a word by Cedric Chauve, Louxin Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-13796.txt.
Introduction
Cedric Chauve and Louxin Zhang size the near neighbourhoods of words under edit distance, in work from 2025. The neighbourhood of a word holds all words within a set edit gap from it. Such sets drive fast search tools that must bound work before they scan large text pools.
Exact size formulas cover shrunk neighbourhood forms for words made of one repeated letter. A new upper bound caps the shrunk neighbourhood size for any word of set length. A long guessed bound for that same max size is also proved in full. These bounds feed cost analysis for near match search in strings. The note stays tight and proof based.
Catalog record
| CREATOR | Cedric Chauve, Louxin Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-13796
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the size of the neighborhoods of a word Cedric Chauve, Louxin Zhang Abstract The d d -neighborhood of a word W W in the Levenshtein distance is the set of all words at distance at most d d from W W . Generating the neighborhood of a word W W , or related sets of words such as the condensed neighborhood or the super-condensed neighborhood has applications in the design of approximate pattern matching algorithms. It follows that bounds on the maximum size of the neighborhood of words of a given length can be used in the complexity analysis of such approximate pattern matching algorithms. In this note, we present exact formulas for the size of the condensed and super condensed neighborhoods of a unary word, a novel upper bound for the maximum size of the condensed neighborhood of an arbitrary word of a given length, and we prove a conjectured upper bound again for the maximum size of the condensed neighborhood of an arbitrary word of a given length. 1 Introduction Aiming to search for all approximate occurrences of a query sequence within a text, a problem known as approximate pattern matching, is at the heart of many basic applications in bioinformatics [ 1 , 2 ] , particularly in searching large biological sequence databases with the BLAST tool [ 3 ] . The BLAST algorithm proceeds in two phases. First, it identifies seeds that are short sequences present in both the query sequence and the target text. These seed occurrences in the searched ext are then extended , using dynamic programming, to form approximate occurrences of the query. This approach to approximate pattern matching is known as the seed-and-extend approach. Conceptually, a key part of the first phase of seed-and-extend methods consists in generating, for every subsequence W of length k of the query sequence and for a distance value d – chosen accordingly to the maximum distance between the query and the searched approximate occurrences of the query – the set of all words at Levenshtein distance (also known as edit distance) from W at most d , known as the d -neighborhood of W . In practice, variants of the neighborhood concept are used in approximate pattern matching algorithms. One example is the condensed neighborhood, used in BLAST [ 4 ] , which is obtained by discarding from the neighborhood any word having a prefix that is itself a word in the neighborhood. Another variant is the super condensed neighborhood, which discards any word that has a subword already in the neighborhood [ 5 ] . Bounds on the maximum size of the neighborhood over all words of a given length over a given alphabet play an important role in the complexity analysis of seed-and-extend approximate pattern matching algorithms. However, there are still few known results on this topic [ 6 , 7 , 8 , 4 ] . In this note, we provide several results on the size of the condensed and super condensed neighborhoods of a word. In Section 3 we provide exact formulas for the size of the condensed and super condensed neighborhoods of unary words. In Section 4 we provide a novel upper bound on the size of the condensed neighborhood of arbitrary words, which we use in Section 5 to prove a conjecture introduced in [ 7 ] , namely that the size of the condensed d -neighborhood of any word of length w over an alphabet of size s is bounded above by \frac{(2s-1)^{d}w^{d}}{d!} . 2 Preliminaries In this section, we introduce formal definitions and notations that will be used in this Note. Words. Let \Sigma be a finite set of characters, called an alphabet. A word W over \Sigma is an ordered sequence of characters W=\sigma_{1}\sigma_{2}\cdots\sigma_{k} , where \sigma_{i}\in\Sigma . Its length is defined as the number of characters appearing in W , denoted by |W| . The empty word of length 0 is denoted by \epsilon . We denote by \Sigma^{+} the set of all nonempty words and \Sigma^{*}=\Sigma^{+}\cup\{\epsilon\} . For words U and V , we use uv to denote the word obtained by concatenating U and V . We also define U^{0}=\epsilon and, for a positive integer k\geq 1 , U^{k}=U^{k-1}U is the concatenation of k copies of U . For two subsets of words {\cal U} and {\cal V} , we define {\cal UV}=\{UV\mid U\in{\cal U},V\in{\cal V}\} as the set of concatenations of a word from {\cal U} and a word from {\cal V} . A word is unary if it consists of repeated occurrences of a single character from \Sigma , i.e. W=\sigma^{w} for some \sigma\in\Sigma . For words U and V , U is said to a prefix (resp. suffix) of V if V=UW (resp. V=WU ) for some W\in\Sigma^{*} . We say that U is a subword of V if V=XUY for some X,Y\in\Sigma^{*} . Sequence Alignment and Levenshtein distance. The Levenshtein distance between two words U and V , denoted by d_{lev}(U,V) , is the minimum number of edit operations needed to transform U into V , where edit operations can be: • Insertion: inserting a character at some position in a word; • Deletion: deleting a character from a word; • Substitution: replacing a character in a word with a different character. An alignment A is a two-row array, where each row is a word over the alphabet \Sigma\cup\{-\} and no column contains two occurrences of - ; the character - is called a gap . We denote by A_{1} (resp. A_{2} ) the word on \Sigma obtained by deleting gaps from the top (resp. bottom) row of A . The cost of an alignment is the number of columns containing two different characters. A column containing twice the same character is called a match column. A column with two different characters is a deletion column is the bottom character is a gap, an insertion column if the top character is a gap, and a mismatch column otherwise. The Levenshtein distance between two words U and V is equal to the minimum cost of an alignment A such that A_{1}=U and A_{2}=V . For example: a l - i g n a s s i g n represents an optimal (minimum cost) alignment between the words U=align and V=assign ; it has cost 2 as it contains a column encoding a substitution of l into s , and a column encoding an insertion of the character s . An optimal alignment between any two words u,v , so their Levenshtein distance, can be computed in quadratic O(|U||V|) time and space using dynamic programming [ 1 ] . Neighborhoods of a word. For a non-negative integer d , the d -neighborhood of a query word W , is the following subset of words: (2.1) N(W,d)=\{U\mid d_{lev}(U,W)\leq d\} Clearly, each word of N(W,d) contains at most d+|W| characters and thus N(W,d) is a finite subset. The condensed d -neighborhood of W , written as {CN}(W,d) , consists of the words of N(W,d) which do not have a prefix in N(W,d) , that is, (2.2) CN(W,d)=N(W,d)\setminus\left[N(W,d)\Sigma^{+}\right]. Lastly, the super condensed d -neighborhood of W , written as SCN(W,d) , consists of the