2
$\begingroup$

I know what a bigram is, intuitively (in a string it's two contiguous symbols). However, I found this mathematical definition in a book and there is one part that keeps tripping me up, namely the $2-grams(w)$ function.

Definition 3.2 (Bigrams). Given a string $w$ over alphabet $\Sigma$, its augmented counterpart $\hat{w} := \$ \cdot w \cdot \$ $ is obtained by adding the left and right edge markers \$ and \$ to $w$, where \$ and \$ are distinguished symbols not contained in $\Sigma$. Furthermore, $2-grams(w) := \{ab \; |\; \exists u, v \in \Sigma^* \; s.t. \; u \cdot ab \cdot v = \hat{w}\}$ denotes the set of bigrams over $\hat{w}$, i.e. the smallest set that contains all substrings of $\hat{w}$ that consist of exactly 2 symbols.

I am reading this as "the function 2-grams is defined as the set of a string $ab$ such that there exist a symbol $u$ and a symbol $v$ in the alphabet Sigma star such that the concatenation of $u$, $ab$, and $v$ is equal to the augmented string $\hat{w}$"

My question is, if $\hat{w}$ is already the augmented string as we defined it above, why do we still concatenate it with $u$ and $v$? Am I supposed to assume that $u$ and $v$ are the edge markers $\$\;\$$? I am not seeing how this function gives us |the smallest set that contains all substrings of $\hat{w}$. What am I missing?

PS. Apologies for using the dollar symbol as edge marker symbols, I couldn't find the actual edge markers my textbook uses.

$\endgroup$
6
  • 2
    $\begingroup$ Looks wrong to me - by the very definition of $\hat w,$ it contains a letter not in $\Sigma,$ so there is no way to have any $u,v\in \Sigma^*$ with $\hat w=uabv.$ $\endgroup$
    – Thomas Andrews
    Sep 23, 2021 at 4:29
  • 3
    $\begingroup$ The intent seems to be that if $xyz$ is your string then $xy$ is a bigram, because $u=\$,v=z\$,$ but this is problematic because it is explicitly said that $\$ $ is not in $\Sigma,$ so these $u,v$ are not in $\Sigma^*.$ The definition needs a new alphabet, $\Sigma_1=\Sigma\cup\{\$\}$ and the function should use $\Sigma_1^*.$ Or the definition could just use $w.$ The definition should also say: $a,b\in \Sigma,$if you don’t want to allow $\$x$ and $z\$$ as bigrams $\endgroup$
    – Thomas Andrews
    Sep 23, 2021 at 4:35
  • $\begingroup$ Where are you seeing this definition? $\endgroup$
    – Thomas Andrews
    Sep 23, 2021 at 4:40
  • $\begingroup$ those were exactly my thoughts on $u, v \in \Sigma$ which is why I think I was so confused. What you are saying sounds correct but I don't know, I am not a mathematician. This definition is in a mathematical linguistics book draft. I am now thinking it might be a mistake on the part of the author? $\endgroup$
    – alpablo20
    Sep 23, 2021 at 4:55
  • 1
    $\begingroup$ Be careful not to confuse $\Sigma$ for $\Sigma^*.$ $\Sigma$ is the set of single letters ($1-$grams?) and $\Sigma^*$ is all words that can be constructed in those letters, including the empty string. $u,v$ are not, in general, single letters. $\endgroup$
    – Thomas Andrews
    Sep 23, 2021 at 5:19

1 Answer 1

Reset to default
2
$\begingroup$

I think the definition says that we can obtain all $|w|-1$ bigrams in the string $w$ by partitioning the augmented string $\hat{w}$ into 3 non-empty parts: $u$, $ab$, $v$, assuming that $|w|\geq 2$.

Here, $u, v \in \Sigma^*=\Sigma\cup{\{`\text{.'}\}}$, $a,b \in \Sigma$ and $ab$ is a length-2 substring of $w$.

Start from $u=`.\text{'}$ and finish at $v=`.\text{'}$, to obtain all the bigrams in $w$ (slide $ab$ over $w$), as shown in the below figure.

enter image description here

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .